Algorithms and Data Structures

Mathematics Machine Learning Artificial Intelligence Graph Data Algorithm Programming Digital Transformation Navigation of this blog

Algorithms and Data Structures

Overview

Algorithms and data structures are fundamental concepts in computer science, and the procedures for solving a problem (algorithms) and the methods for efficiently storing and manipulating data (data structures) are closely related.

Algorithms are explicit procedures that process inputs and return outputs, and mathematics can be used to formalize problems and design efficient ways to solve them. Algorithms are evaluated in terms of correctness, efficiency, and generality, and there are various types of algorithms, including sorting, search, and shortest path problems; typical examples include bubble sort, Dijkstra method, quick sort, and linear search.

Data structures, on the other hand, include arrays, lists, stacks, queues, trees, and graphs, which are important for efficient data manipulation. Each data structure has a suitable algorithm, for example, binary search for arrays and Dijkstra method for graphs.

Algorithms and data structures are core elements in programming, and understanding both is essential for efficient program design. This blog discusses these theories and implementations in detail.

Basic Algorithms

Introduction to Algorithms

Introduction to Algorithms. This is the third edition of a comprehensive textbook on computer algorithm theory written for teaching at MIT by four world-renowned experts in the fundamental field of computer science. The previous editions have already established themselves as world-standard textbooks on algorithms and data structures, but the book has been extensively revised once again, including the addition of new chapters and sections based on a comprehensive review of the descriptions to improve the textbook.
The book not only explains algorithms in an easy-to-understand manner, but also explains in scientific detail what concepts are necessary and how they are backed up by analysis before the final algorithm is designed.
The book also contains 957 exercises at the end of each section and 158 problems of various levels at the end of each chapter, making it a textbook for undergraduate and graduate courses, a handbook for technical specialists, and an encyclopedia of algorithms.

Economics, market design and algorithms

Economics, market design and algorithms. The economy is the system and state of production, distribution and consumption of goods and services, and how people, companies and governments produce, distribute and consume goods using limited resources, making economics a discipline that seeks to understand and elucidate the workings of the economy. This section describes market design and algorithms, one of the applications of economics.

Generating a unique ID

Generating a unique ID. A unique ID (Unique Identifier) is a unique, non-duplicate number or string of characters assigned to identify data or objects, which is used to distinguish specific information within a system or database.

Overview of the Stable Marriage Problem algorithm and examples of implementation and application

Overview of the Stable Marriage Problem algorithm and examples of implementation and application. The Stable Marriage Problem (SMP) algorithm is a type of problem and solution method for achieving ‘stable matching’ between two groups. The most famous solution to this problem is the Gale-Shapley Algorithm (Gale-Shapley Algorithm), which can efficiently find stable combinations, and this algorithm has been used in particular for matching medical students and hospitals, job applicants and companies, and It will be applied to many real-world matching problems, in particular matching medical students with hospitals and job seekers with companies.

Machine learning and algorithms used for surge pricing and examples of implementation

Machine learning and algorithms used for surge pricing and examples of implementation. Surge pricing (dynamic pricing based on demand) will be one in which prices fluctuate under certain conditions and the optimum price is set in real time according to consumer demand and supply conditions. To achieve this, various machine learning and algorithms are utilised, with demand forecasting and market analysis techniques playing a particularly important role.

Overview, implementation examples and applications of optimisation algorithms that take into account the Kelly criterion and equity

Overview, implementation examples and applications of optimisation algorithms that take into account the Kelly criterion and equity. The Kelly criterion and equity-aware optimisation algorithms are methods used for various capital allocations. The Kelly criterion is a method for optimally allocating capital in gambling and investment, which calculates how much money should be invested when the expected value of an investment or bet is positive.

Overview of Search Algorithms and Various Algorithms and Implementations

Overview of Search Algorithms and Various Algorithms and Implementations. Search Algorithm (Search Algorithm) refers to a family of computational methods used to find a target within a problem space. These algorithms have a wide range of applications in a variety of domains, including information retrieval, combinatorial optimization, game play, route planning, and more. This section describes various algorithms, their applications, and specific implementations with respect to these search algorithms.

Overview of evolutionary algorithms and examples of algorithms and implementations

Overview of evolutionary algorithms and examples of algorithms and implementations. Evolutionary algorithms are optimisation techniques designed based on the principles of natural selection and genetic information transfer in evolutionary biology. In evolutionary algorithms, candidate solutions are represented as individuals, and individuals are evolved through genetic manipulation (crossover, mutation, etc.) to search for the optimal solution.

SADE(Self-Adaptive Differential Evolution) Overview, Algorithms and Implementation Examples

SADE(Self-Adaptive Differential Evolution) Overview, Algorithms and Implementation Examples. Self-Adaptive Differential Evolution (SADE) is a method based on Differential Evolution (DE), a type of evolutionary algorithm, in which parameter adjustment is automated and the adaptability of the algorithm is enhanced. In normal Differential Evolution (DE), multiple parameters (e.g. mutation rate \(F\) and crossover rate \(CR\)) need to be set in advance during the search, but these settings are problem-dependent and therefore difficult to adjust, SADE adjusts these parameters in a self-adaptive manner in the evolutionary process, thereby improving search efficiency and The method improves the quality of the solution.

Overview of Evolutionary Annealing-Search (EAS), algorithms and implementation examples

Overview of Evolutionary Annealing-Search (EAS), algorithms and implementation examples. EAS (Evolutionary Annealing-Search) is a meta-heuristic optimisation algorithm that integrates the Evolutionary Algorithm (EA) and the Simulated Annealing (SA) method. It aims to provide efficient solutions to complex optimisation problems by combining an evolutionary search mechanism with the temperature parameter adjustment mechanism of the annealing method.

ABC (Artificial Bee Colony Algorithm) overview, algorithm and implementation examples

ABC (Artificial Bee Colony Algorithm) overview, algorithm and implementation examples. ABC (Artificial Bee Colony Algorithm) is an optimisation algorithm based on swarm intelligence, which mimics the foraging behaviour of bees in nature. It is widely used as a simple but effective method, with particularly good performance in continuous optimisation problems.

Overview of Adaptive PSO (Self-Adaptive Particle Swarm Optimisation), algorithm and implementation examples

Overview of Adaptive PSO (Self-Adaptive Particle Swarm Optimisation), algorithm and implementation examples. Adaptive PSO (self-adaptive particle swarm optimisation) is a type of particle swarm optimisation algorithm described in ‘Overview and implementation of particle swarm optimisation’, which aims to improve search performance by dynamically adjusting the algorithm parameters.

Overview of linear programming and examples of algorithms and implementations

Overview of linear programming and examples of algorithms and implementations. Linear Programming (LP) is a mathematical method for solving the problem of optimising (maximising or minimising) a linear function, which is applied to many optimisation problems and is widely used, especially in resource allocation, scheduling and transport planning.

Overview of Predictive Control with Constraints (Predictive Control with Constraints), algorithms and implementation examples

Overview of Predictive Control with Constraints (Predictive Control with Constraints), algorithms and implementation examples. Predictive Control with Constraints (Predictive Control with Constraints) is a control method for designing control inputs to predict the future behaviour of a system while satisfying constraints. The method aims to optimise system performance under constraints.

Overview, algorithms and implementation examples of linear quadratic programming (LQ problem)

Overview, algorithms and implementation examples of linear quadratic programming (LQ problem). Linear quadratic programming (LQ problem, Linear Quadratic Problem) is a widely used method in control theory and optimisation problems, and is particularly important in the field of optimal control.

Linear Quadratic Control (LQC) overview, algorithms and implementation examples

Linear Quadratic Control (LQC) overview, algorithms and implementation examples. Linear Quadratic Control (LQR) is a control theory and one of the optimal control methods for systems with linear dynamics.LQR is a method for obtaining feedback control laws to optimally control the state of a system, in particular to minimise the quadratic cost function, which is performance is used in designing control strategies that minimise the cost function based on the state and control inputs in order to optimise the performance of the system.

Overview of Self-Adaptive Search Algorithms and Examples of Applications and Implementations

Overview of Self-Adaptive Search Algorithms and Examples of Applications and Implementations. Self-Adaptive Search Algorithms, or Self-Adaptive Search Algorithms, are a family of algorithms used in the context of evolutionary computation and optimization, where the parameters and strategies within the algorithm are characterized by adaptive adjustment to the problem. These algorithms are designed to adapt to changes in the nature of the problem and the environment in order to efficiently find the optimal solution. This section describes various algorithms and examples of implementations with respect to this self-adaptive search algorithm.

Overview of Multi-Objective Search Algorithm and Examples of Application and Implementation

Overview of Multi-Objective Search Algorithm and Examples of Application and Implementation. Multi-Objective Search Algorithm (Multi-Objective Optimization Algorithm) is an algorithm for optimizing multiple objective functions simultaneously. Multi-objective optimization aims to find a balanced solution (Pareto optimal solution set) among multiple optimal solutions rather than a single optimal solution, and such problems have been applied to many complex systems and decision-making problems in the real world. This section provides an overview of this multi-objective search algorithm and examples of algorithms and implementations.

Exploratory Ranking Overview, Algorithm and Example Implementation

Exploratory Ranking Overview, Algorithm and Example Implementation. Exploratory Ranking is a technique for identifying items that are likely to be of interest to users in ranking tasks such as information retrieval and recommendation systems. This technique aims to find the items of most interest to the user among ranked items based on the feedback given by the user.

Overview of Maximum Marginal Relevance (MMR) and Examples of Algorithms and Implementations

Overview of Maximum Marginal Relevance (MMR) and Examples of Algorithms and Implementations. Maximum Marginal Relevance (MMR) is a ranking method for information retrieval and information filtering that aims to optimize the ranking of documents provided to users by information retrieval systems. MMR was developed as a method for selecting documents that are relevant to the user’s interests from among multiple documents. The method will rank documents based on both the relevance and diversity of each document, specifically emphasizing the selection of documents that are highly relevant but have low similarity to other options.

Overview, algorithm and implementation examples of Diversity-Enhanced Ranking

Overview, algorithm and implementation examples of Diversity-Enhanced Ranking. Diversity-Enhanced Ranking is a ranking method that aims to display a variety of items higher in search results and recommendation systems, rather than just on the basis of relevance and popularity. This gives users access to a variety of options, increasing satisfaction and increasing opportunities for new discoveries. Traditional ranking algorithms typically determine the top results based on relevance, click-through rate and popularity for a user’s query, but this method can lead to a concentration of items of the same type or genre at the top, limiting the options available to users. For this reason, diversity-promoting ranking has the following objectives

Overview of location bias-corrected ranking, algorithm and implementation examples

Overview of location bias-corrected ranking, algorithm and implementation examples. Position bias-corrected ranking is a method of creating rankings that more accurately reflect actual quality and popularity by correcting for click and selection bias (bias) due to an item’s display position in search results and product lists. This bias correction can correct the tendency for higher click rates to be displayed at the top and lower click rates to be displayed at the bottom. Items in search results and listings are more likely to be clicked on if they appear higher up, and less likely to be clicked on if they appear lower down. This ‘position bias’ may not accurately reflect the actual quality or popularity of the item, and the purpose of position bias correction is to correct this bias and provide a ranking that reflects the true value of the item.

Overview of the Minimax Method and Examples of Algorithms and Implementations

Overview of the Minimax Method and Examples of Algorithms and Implementations. The minimax method is a type of search algorithm widely used in game theory and artificial intelligence, which is used to select the optimal move in a perfect information game (a game in which both players know all information). Typical games include chess, shogi, Othello, and Go.

Alpha-beta pruning: overview, algorithm, and implementation examples

Alpha-beta pruning: overview, algorithm, and implementation examples. Alpha-beta pruning is a type of search algorithm used in the fields of artificial intelligence and computer games. This is a common approach used in combination with tree search algorithms such as the minimax method described in “Overview of the Minimax Method, Algorithms and Examples of Implementation. This algorithm is used to efficiently find a solution by reducing unnecessary search when searching the tree structure of a game. Specifically, the possible combinations of moves in a game are represented by a tree structure, and unnecessary moves are removed during the search, thereby reducing computation time.

Overview of Monte Carlo Tree Search and Examples of Algorithms and Implementations

Overview of Monte Carlo Tree Search and Examples of Algorithms and Implementations. Monte Carlo Tree Search (MCTS), a type of decision tree search, is a probabilistic method for exploring the state space of a game to find the optimal action, and is a particularly effective approach in games and decision-making problems.

Overview of UCT (Upper Confidence Bounds for Trees), Algorithm and Example Implementation

Overview of UCT (Upper Confidence Bounds for Trees), Algorithm and Example Implementation. UCT (Upper Confidence Bounds for Trees) is an algorithm used in the selection phase of Monte Carlo Tree Search (MCTS), which aims to balance the search value of each node in the search. It is important to strike a balance between exploration and utilization. That is, the more nodes being explored are visited, the higher the value of the node will be estimated, but at the same time, the unexplored nodes will be given an appropriate opportunity to be explored.

Overview of Information Set Monte Carlo Tree Search (ISMCTS) and Examples of Algorithms and Implementations

Overview of Information Set Monte Carlo Tree Search (ISMCTS) and Examples of Algorithms and Implementations. Information Set Monte Carlo Tree Search (ISMCTS) is a variant of Monte Carlo Tree Search (MCTS) used in games such as incomplete information games (e.g. poker) and information hiding games (e.g. Go, Shogi). The characteristic feature of this method is that it handles groups of game states, called information sets, when searching the game tree by applying MCTS.

Overview of Nested Monte Carlo Search (NMC) and Examples of Algorithms and Implementations

Overview of Nested Monte Carlo Search (NMC) and Examples of Algorithms and Implementations. Nested Monte Carlo Search (NMC) is a type of Monte Carlo Tree Search (MCTS), which is a method for efficiently exploring a search space.

Rapid Action Value Estimation (RAVE) Overview, Algorithm, and Example Implementation

Rapid Action Value Estimation (RAVE) Overview, Algorithm, and Example Implementation. Rapid Action Value Estimation (RAVE) is a game tree search method developed as an extension of Monte Carlo Tree Search (MCTS) described in “Overview of Monte Carlo Tree Search, Algorithms and Examples”. RAVE is used to estimate the value of moves selected during game tree search. While the usual MCTS uses statistics of the moves explored to estimate the value of moves when the model is incomplete or as the search progresses, RAVE improves on this and aims to find suitable moves more quickly.

Overview of Ranking Algorithms and Examples of Implementations

Overview of Ranking Algorithms and Examples of Implementations. A ranking algorithm is a method for sorting a given set of items in order of most relevance to the user, and is widely used in various fields such as search engines, online shopping, and recommendation systems. This section provides an overview of common ranking algorithms.

Random Forest Ranking Overview, Algorithm and Implementation Examples

Random Forest Ranking Overview, Algorithm and Implementation Examples. Random Forest is a very popular ensemble learning method in the field of machine learning (a method that combines multiple machine learning models to obtain better performance than individual models). This approach combines multiple Decision Trees to build a more powerful model. There are many variations in ranking features using random forests.

Diversity-Promoting Ranking Overview, Algorithm, and Implementation Example

Diversity-Promoting Ranking Overview, Algorithm, and Implementation Example. Diversity-Promoting Ranking is one of the methods that play an important role in information retrieval and recommendation systems, which aim to make users’ information retrieval results and the list of recommended items more diverse and balanced. This will be the case. Usually, the purpose of ranking is to display items that match the user’s interests at the top, but at this time, multiple items with similar content and characteristics may appear at the top. For example, in a product recommendation system, similar items or items in the same category often appear at the top of the list. However, because these items are similar, they may not adequately cover the user’s interests, leading to information bias and limiting choices, and diversity promotion ranking is used to address these issues.

Overview of Rank SVM, Algorithm and Implementation Example

Overview of Rank SVM, Algorithm and Implementation Example. Rank SVM (Ranking Support Vector Machine) is a type of machine learning algorithm applied to ranking tasks, especially for ranking problems in information retrieval and recommendation systems. Related papers include “Optimizing Search Engines using Clickthrough Data” and “Ranking Support Vector Machine with Kernel Approximation”.

Diversified Top-k Retrieval (DTkR) Overview, Algorithm and Example Implementation

Diversified Top-k Retrieval (DTkR) Overview, Algorithm and Example Implementation. Diversified Top-k Retrieval (DTkR) is a method for obtaining diversified top-k search results in information retrieval and ranking tasks, aiming to obtain search results with different perspectives and diversity rather than simple Top-k results. In general Top-k search, the objective is simply to obtain the top k results with the highest scores, but similar results tend to rank high and lack diversity. On the other hand, DTkR aims to make the search results more diverse and different, and can perform information retrieval with diversity that cannot be obtained with simple Top-k search results.

Overview of Submodular Diversification and examples of algorithms and implementations

Overview of Submodular Diversification and examples of algorithms and implementations. Submodular Diversification is a method for selecting the top k items with diversity in information retrieval and ranking tasks. The basis of Submodular Diversification is the Submodular function, also described in “Submodular Optimisation and Machine Learning”, which is a set function \( f: 2^V \rightarrow \mathbb{R} \), with the following properties.

Overview of Cluster-based Diversification and examples of algorithms and implementations

Overview of Cluster-based Diversification and examples of algorithms and implementations. Cluster-based Diversification is a method for introducing diversity into a recommendation system using clustering of items. In this method, similar items are grouped into the same cluster and diversity is achieved by selecting items from different clusters.

Overview, algorithms and implementation examples of neural ranking models

Overview, algorithms and implementation examples of neural ranking models. A neural ranking model is a type of machine learning model used in search engines and recommendation systems, where the main objective is to sort items (e.g. web pages, products, etc.) in the best ranking based on given queries and user information. For a typical search engine, it is important to display first the web pages that are most relevant to the user’s query, and to achieve this, the search engine considers a number of factors to determine the ranking of web pages. These include keyword match, page credibility and the user’s previous click history.

Overview, algorithms and implementation examples of personalised ranking

Overview, algorithms and implementation examples of personalised ranking. Personalised ranking is a ranking method that provides items in the most suitable rank for each user. While general ranking systems present items in the same rank for all users, personalised ranking takes into account the individual preferences and behaviour of the user and Personalised ranking takes into account the user’s individual preferences and behaviour and ranks items in the most appropriate order for that user. The purpose of personalised ranking is to increase user engagement by showing items that are likely to be of interest to the user at a higher rank, increase user engagement, increase user purchases, clicks and other actions, and increase conversion rates Increased conversion rates, users find the information and products they are looking for more quickly, which increases user satisfaction, which increases user satisfaction, and so on.

Overview of Beam Search and Examples of Algorithms and Implementations

Overview of Beam Search and Examples of Algorithms and Implementations. Beam Search is a search algorithm mainly applied to combinatorial optimization and finding meaningful solutions. It is mainly used in areas such as machine translation, speech recognition, and natural language processing.

Heuristic Search (Hill Climbing, Greedy Search, etc.) Based Structural Learning

Heuristic Search (Hill Climbing, Greedy Search, etc.) Based Structural Learning. Structural learning based on heuristic search is a method that combines heuristic methods for searching the architecture and hyperparameters of machine learning models to find the optimal model or structure, and heuristics are intuitive and simple rules or approach. Below we describe some common methods related to heuristic search-based structure learning.

Overview of Random Walks, Algorithms and Examples of Implementations

Overview of Random Walks, Algorithms and Examples of Implementations. Random Walk is a basic concept used in graph theory and probability theory to describe random movement patterns in graphs and to help understand the structure and properties within a graph.

Overview of Message Passing in Machine Learning and Examples of Algorithms and Implementations

Overview of Message Passing in Machine Learning and Examples of Algorithms and Implementations. Message passing in machine learning is an effective approach to data and problems with graph structures, and is a widely used technique, especially in methods such as Graph Neural Networks (GNN).

Mathematical Metaheuristics Reading Notes

Mathematical Metaheuristics Reading Notes. Meta-heuristics is an organic combination of empirical methods (heuristics) for solving difficult optimization problems. Recently, it has become a popular optimization algorithm among practitioners as a framework for solving practical problems with ease. When solving practical problems, a robust solution can be designed in a relatively short time if one has some programming skills, an eye for selecting metaheuristics, and a knack for design.

Metaheuristics and Applications Reading Notes

Metaheuristics and Applications Reading Notes. This book systematically summarizes algorithms and applications of a new optimization method, meta-heuristics. The Algorithms section covers a wide range of state-of-the-art methods such as the Memetic algorithm, artificial immune systems, ant colony optimization methods, Particle Swarm Optimization, etc. The Applications section covers a wide range of scheduling problems, delivery planning problems, applications to structural optimal design, etc. The applications section covers a wide range of scheduling problems, delivery planning problems, and applications to structural optimal design. This book can be used as a handbook and is a must-have for students, engineers, and researchers involved in systems engineering and information technology.

Multidimensional Scaling (MDS)

Multidimensional Scaling (MDS). Multidimensional Scaling (MDS) is a statistical method for visualizing multivariate data that provides a way to place data points in a low-dimensional space (usually two or three dimensions) while preserving distances or similarities between the data. This technique is used to transform high-dimensional data into easily understandable low-dimensional plots that help visualize data features and clustering.

Metric MDS overview, algorithms and implementation examples

Metric MDS overview, algorithms and implementation examples. Metric Multidimensional Scaling (Metric MDS) is a method for embedding multidimensional data into a low-dimensional space and visualising similarities and distances between data, where given a distance (or similarity) between data, a point is It finds a low-dimensional space in which to place the points so as to represent them as faithfully as possible, given the distances (or similarities) between the data.

Overview of non-metric MDS and examples of algorithms and implementations

Overview of non-metric MDS and examples of algorithms and implementations. Non-metric MDS will be a method of embedding data into a low-dimensional space based on the similarity or dissimilarity of the data (often given as ‘ordinal data’ or ‘ranking’).’ Whereas metric MDS, as described in ‘Overview, algorithms and implementation examples of metric MDS’, seeks to preserve absolute values of distances (e.g. Euclidean distance), non-metric MDS prioritises the ‘ordinal relationship’ of the data.

Self-Organising Map (SOM) overview, algorithms and implementation examples

Self-Organising Map (SOM) overview, algorithms and implementation examples. Self-Organising Map (SOM) is a type of artificial neural network and a method for mapping and visualising high-dimensional data in a low-dimensional (usually two-dimensional) space. The maps are constructed in such a way that similar data are brought into close proximity, while preserving the features of the data. This method is useful for data clustering, dimensionality reduction and visualisation.

Overview of Shepard’s method, algorithm and implementation examples

Overview of Shepard’s method, algorithm and implementation examples. Shepard’s method is a non-linear dimensionality reduction method, specifically used as part of MDS, which is also described in ‘Multidimensional Scaling (MDS),’ and is mainly used to effectively map distances or similarities between data into a low-dimensional space. Shepard’s method can be characterised as a non-linear distance reduction method, an approach that is particularly capable of successfully representing diverse relationships between data.

Overview of SMACOF (Scaling by Majorizing a Complex Function) and examples of algorithms and implementations

Overview of SMACOF (Scaling by Majorizing a Complex Function) and examples of algorithms and implementations. SMACOF is a type of MDS described in ‘Multidimensional Scaling (MDS)’ and is an algorithm for placing data in a low-dimensional space based on distance information. It is a particularly effective approach when dealing with non-linear data and approximate distance information.

ISOMAP (Isometric Mapping) overview, algorithm and implementation examples

ISOMAP (Isometric Mapping) overview, algorithm and implementation examples. ISOMAP (Isometric Mapping) is one of the non-linear dimensionality reduction methods and is an algorithm for embedding high-dimensional data into low-dimensional space. It is particularly effective when the data has a ‘manifold structure’, such as a curved distribution, and was proposed by Tenenbaum, De Silva, and Langford in 2000.

Overview, algorithms and implementation examples of the Bias Correction Method in non-metric MDS

Overview, algorithms and implementation examples of the Bias Correction Method in non-metric MDS. The Bias Correction Method in Non-Metric Multidimensional Scaling (NMS) is a technique for improving the accuracy of mapping from a distance matrix to a lower dimensional space, which is usually This method is usually used to deal with non-linearity and structural biases in the data that cannot be well represented by metric MDS, which is also described in ‘Overview of Metric MDS and Examples of Algorithms and Implementations’

t-SNE (t-distributed Stochastic Neighbor Embedding)

t-SNE (t-distributed Stochastic Neighbor Embedding). t-SNE is a nonlinear dimensionality reduction algorithm that embeds high-dimensional data into lower dimensions. t-SNE is mainly used for tasks such as data visualization and clustering, where its particular strength is its ability to preserve the nonlinear structure of high-dimensional data. t-SNE’s main ideas are The main idea of t-SNE is to reflect the similarity of high-dimensional data in a low-dimensional space.

About LLE (Locally Linear Embedding)

About LLE (Locally Linear Embedding). LLE (Locally Linear Embedding) is a nonlinear dimensionality reduction algorithm that embeds high-dimensional data into a lower dimension. It assumes that the data is locally linear and reduces the dimension while preserving the local structure of the data. It is primarily used for tasks such as clustering, data visualization, and feature extraction.

UMAP (Uniform Manifold Approximation and Projection)

UMAP (Uniform Manifold Approximation and Projection). UMAP is a nonlinear dimensionality reduction method for high-dimensional data, which aims to embed the data in a lower dimension while preserving its structure. It is used for visualization and clustering in the same way as t-SNE (t-distributed Stochastic Neighbor Embedding) described in “About t-SNE (t-distributed Stochastic Neighbor Embedding)” but adopts a different approach in some respects.

Overview of Dynamic Programming and Examples of Application and Implementation in python

Overview of Dynamic Programming and Examples of Application and Implementation in python. Dynamic Programming is a mathematical method for solving optimization problems, especially those with overlapping subproblems. Dynamic programming provides an efficient solution method because it dramatically reduces the amount of exponential computation by saving and reusing the results once computed. This section describes various algorithms and specific implementations in python for this dynamic programming.

Dynamic Programming Algorithms and Data Structures

Dynamic Programming Algorithms and Data Structures. It is an effective approach for programming and algorithm design to record the results of a calculation in a memo and reuse them to improve efficiency while avoiding the wasteful repetition of the same calculation. One such approach is dynamic programming.

Search engine matching algorithms Matching strings in search engines

Search engine matching algorithms Matching strings in search engines. Introduction to string matching algorithms for search engines (n-grams, meta word indexing, etc.)

Search Engine Page Rank Algorithm

Search Engine Page Rank Algorithm. About the pagerank algorithm that determines search rankings, which is one of the search engine algorithms that has dramatically improved google.

Overview of Exponential Smoothing and Examples of Algorithms and Implementations

Overview of Exponential Smoothing and Examples of Algorithms and Implementations. Exponential Smoothing is a statistical method used for forecasting and smoothing time series data, especially for forecasting future values based on past observations. Exponential smoothing is a simple but effective method that allows for weighting against time and adjusting for the effect of past data.

Pattern recognition algorithm Nearest neighbor, decision tree, neural net

Pattern recognition algorithm Nearest neighbor, decision tree, neural net. Introduction to nearest neighbor methods, decision trees, and neural networks as basic algorithms for pattern recognition.

Database Algorithms (1) Database Consistency

Database Algorithms (1) Database Consistency. One of the biggest differences between a database and other information storage methods is that the information in the database has a predefined structure. Another characteristic is “consistency”.

Consistency means that the information contained in the database does not contradict each other even if the data is moved in and out of the database. In this paper, three algorithms are described to achieve these characteristics. The first one is “write log ahead”, the second one is “two-stage commit”, and the last one is “relational database”.

Database algorithms (2) Relational databases

Database algorithms (2) Relational databases. A database is data with a structure, the simplest of which is a table structure. Sometimes it is more efficient to divide the table structure into multiple parts instead of just one.

This simple structure saves the memory of the computer and also has the advantage that when changing the data, all the repeated information (class information) can be changed at once instead of changing it one by one.

The data (class number in the above example) that is commonly used in the two split tables is called the key. The database uses this key to access the data as a chunk, and this chunk is called a “B-tree” in computer science.

Data compression algorithm (1) Lossless compression

Data compression algorithm (1) Lossless compression. There are two main types of compression technology: “lossy compression” and “lossy compression. Lossy compression can reproduce the original data perfectly even when it is compressed, so it is normally sufficient to have only one compression technique, but it has the problem that the compression ratio cannot be that good, so lossy compression is used.

The basic principle of “lossless compression” is to find the repetitive parts of the data and omit them.

Data compression algorithm (2) Lossy compression

Data compression algorithm (2) Lossy compression. An introduction to data compression algorithms used in image information (JPEG) and other applications.

Proof of Indeterminacy About problems that cannot be calculated

Proof of Indeterminacy About problems that cannot be calculated. This article is about what computers (algorithms) cannot do. The algorithms here are not about hard problems like driving a car perfectly or evaluating a student’s performance, but essentially about problems that cannot be computed.

The subject of the explanation is about a checking tool that detects bugs and crashes in software. The conclusion is that it can be proven that it is impossible for any program tool to find all possible crash locations.

error-correcting code algorithm

error-correcting code algorithm. It defines the three jobs that a computer does. The first is to perform calculations, the second is to store data, and the third is to transmit data. From a software point of view, the function of storing data is represented by database technology, and the function of transmitting data is represented by the Internet and other web technologies.

When considering the transmission and storage of data, the most important thing is to store or transmit the data “completely and accurately. On the other hand, hardware such as memory and communication is always subject to noise and malfunctions, and 100% operation cannot be guaranteed. Therefore, it is necessary to ensure “complete accuracy” by using software, and one of the technologies to achieve this is “error correction technology”.

The method of storing and transmitting data with “perfect accuracy” is to increase the redundancy of the data. For example, if the number “5123” is transmitted in the form of “five one two three,” in the former case, even if a single character error occurs, the original data will be completely lost, but in the latter case, for example, even if one of the characters in “five” is replaced by “fave,” there is a high possibility that it can be corrected to “five” using the information before and after. In the latter case, for example, even if one of the letters in “five” is replaced by “fave,” it is likely to be corrected to “five” with the information before and after.

digital signature algorithm

digital signature algorithm. The “signature” of a digital signature is defined as something that can be read but cannot be copied by anyone. This is the complete opposite of the concept of “digital” which can be copied by anyone. Digital signatures provide a solution to this paradox.

The purpose of a digital signature is not to sign something that you send to someone else, like a regular letter, but to check a computer when someone sends you something that is signed by someone else.

There are two requirements for a signature: (1) the place where the original signature is kept must be a trustworthy place, and (2) the signature cannot be easily forged by a third party.

Public-key Cryptography

Public-key Cryptography. The simplest cryptographic technique starts with “having a secret to share”. When you send some data to a specific person, you have a secret number that you share only with that person. (e.g. 322) Then, when you send 8 as data, you send the added number to the other person (322+8=400), and the other person can subtract the shared number from the sent number.

To make this even more practical, you can send a longer number, for example, one that is not easily recognized as a shared number. (For example, there are 999 ways to use a 3-digit number as a secret number, but a computer can easily try all combinations at this level. This is a larger number than a trillion times a trillion. It would take a billion years to calculate this on a current computer, so we can conclude that it is a secure method.

Data sorting Bubble sort, quick sort, merge sort, selection sort, heap sort

Data sorting Bubble sort, quick sort, merge sort, selection sort, heap sort. Sorting (rearranging) data is the basis of algorithms. Sorting algorithms include the following.

Bubble sort, which repeats the process of comparing and replacing adjacent values; Quick sort, which determines a standard value called a pipot and repeatedly divides a group of data into two groups, one above the standard value and the other below the standard value, to replace elements; Merge sort, which decomposes data to the smallest unit (single element) and repeatedly sorts and merges elements from the smallest unit.

Selective sorting” involves finding the minimum value in the first and subsequent elements and exchanging it with the first element, then finding the minimum value in the second and subsequent elements and exchanging it with the second element, and so on, and “Insertion sorting” involves taking two elements from the front and reordering them if they are in reverse order, then taking the third element and inserting it in the appropriate place among up to two elements, and so on.

In “heap sort,” the original data is converted into an ordered tree as shown below, and the children and parents of the converted ordered tree are compared, and if the parent is smaller than the child, the parent and child are exchanged.

Can you program that formula?

Can you program that formula?. The theme of the book is programming, but unlike most programming books, in addition to algorithms and code, it includes mathematical proofs and historical background on mathematical discoveries from ancient to modern times.

To be more specific, the theme is generic programming. Generic programming is a programming technique that emerged in the 1980s, and the C++ TL (Standard Template Library) was developed in the 1990s. Generic programming is a programming technique that focuses on designing algorithms and data structures to make them work in the most common environments without reducing efficiency.

A Textbook of Algorithms in Python

A Textbook of Algorithms in Python. This book discusses the basics of Python programming and basic algorithm construction as shown in the table of contents below.

The content of the book begins with a basic knowledge of pyhtpn and how to handle basic data structures such as vectors, arrays, stacks, queues, lists, trees, and graphs in python, search algorithms such as linear search, binary trees, and tree search, sorting algorithms such as selection sort, bubble sort, insertion sort, quicksort, merge sort, heap sort, hash and Euclidean reciprocity, string search, and heap sort. Sorting algorithms such as selection sort, bubble sort, insertion sort, quick sort, merge sort, heap sort, etc., specific algorithms such as hash and Euclidean reciprocity, string search, shortest path problem, etc., and finally understanding of algorithms through visualization of algorithms, etc.

Implementation of a simple recommendation algorithm using Clojure

Implementation of a simple recommendation algorithm using Clojure. A recommendation system is an information system that attempts to predict user preferences and tastes for an item. A recommendation system is an information filtering system that aims to provide useful information to the user. A recommendation system uses the user’s behavioral history or recommends items that other users like. These two approaches form the basis of the two types of algorithms (content-based filtering and collaborative filtering) used in recommendation systems.

Mathematics in Machine Learning

According to the wiki, “Mathematics is generally classified as a formal science, distinct from the natural sciences. Ultimately, regardless of methodology, mathematical results are not the result of experimentation or observation as in the natural sciences. It goes on to say

Formal science is an abstract structure described by a symbolic system, which means that mathematics abstracts the structure (model) of things using some symbols, and draws results by making inferences using the abstracted model.

By using mathematics, algorithms used in machine learning can be described rigorously and without error. The inference functions used in artificial intelligence also rely on the formal scientific rigor of mathematics. This rigor is the opposite of a highly ambiguous symbolic system such as natural language.

In the following pages of this blog, I will summarize the information that I think is necessary for the use of these mathematics in computers such as artificial intelligence and machine learning.

Mathematics of Optimization

First Time Optimization  Reading Notes

First Time Optimization  Reading Notes. This book is explained in detail in an easy-to-understand manner, making extensive use of graphic explanations so that the reader can understand concrete problems. The goal is to promote intuitive understanding of the problem and solution method, and to enable the reader to solve specific problems. We have endeavored to present the text in a concise manner, and have included side notes for additional explanations or other things that we would like to mention. Practice problems are provided at the end of each chapter, and answers to all problems are included at the end of the book. For the beginning student learning optimization problems for the first time, this book is a good book because it starts with a mathematical review, making it very easy to understand and learn.

Stochastic Optimization

With the development of the Internet, sensor technology, and computers, a large amount of data of various types is now available, and machine learning technology has been attracting attention and making great progress in extracting meaningful information from large amounts of data. While the availability of a wide variety of data has made it possible to solve a wide range of problems, it has also created the problem of increased computational complexity due to the increased size of the data.

In order to fully utilize machine learning technology, it is necessary to learn large amounts of data as efficiently as possible. Stochastic optimization is a powerful method for solving large-scale learning problems with large amounts of data and is a fundamental component of current machine learning. In this section, we will discuss various methods of stochastic optimization in machine learning.

In the following pages of this blog discuss stochastic optimization.

Statistical Learning Theory

The purpose of this content is to understand the theory of statistical properties of machine learning algorithms. For this purpose, we mainly discuss (a) the law of large uniform numbers, (b) the universal kernel, and (c) discriminant fitting loss. Many domestic and foreign works describe (a), and the Foundation of Machine Learning (Mohri, MIT Press) develops a prospective theory of (a) with Rademacher complexity as the main axis. On the other hand, there are few works that systematically explain (b) and (c).

In the following pages of this blog, we will discuss the details of this statistical learning theory.

Sequential optimization for machine learning

In today’s highly information-oriented society, gaining useful insights from data has become an extremely important issue for making important scientific discoveries and promoting industry and economic society. Today, data are becoming larger, more dimensional, and more diverse. As a fundamental technology for appropriately handling such data, a field called machine learning has emerged in recent years and is developing rapidly. In traditional academic fields that deal with data, such as statistics and data science, modeling techniques have been developed mainly to perform statistical inference appropriately.

Machine learning, on the other hand, is unique in that it focuses more on the development of efficient computational methods. In the era of big data, various methods developed in the field of machine learning are having a significant impact on society.

In the following pages of this blog, we will discuss the method of continuous optimization, which is an indispensable computational method for constructing machine learning algorithms.

Graph algorithms

Graphs are a way of expressing connections between objects such as objects and states. Since many problems can be attributed to graphs, many algorithms have been proposed for graphs.

In the following pages of this blog, we discuss the basic algorithms for graph data, such as the search algorithm, shortest path algorithm, minimum global tree algorithm, data flow algorithm, DAG based on strongly connected component decomposition, SAT, LCA, decision tree, etc., and applications such as knowledge data processing and Bayesian processing based on graph structures.

Markov chain Monte Carlo methods

MCMC is an abbreviation for Markov Chain Monte Carlo Method, which is an algorithm for extracting samples (generating random numbers) from a multivariate probability distribution.

MCMC is just a computational method, and in order to solve a task, it is necessary to organize the problem so that it can be solved by MCMC (statistical modeling). This is similar to the way that “what to calculate” is more important than the calculation of addition, subtraction, and multiplication itself in arithmetic problems.

Matrix decomposition” and “optimization” are necessary to fit a curve by the least-squares method or to estimate the parameters of a probability distribution by the maximum likelihood method. In contrast, in Bayesian statistics, the “answer” is first given in the form of a “distribution” called the “posterior distribution. In contrast, in Bayesian statistics, the “answer” is first given in the form of a “distribution” called the “posterior distribution,” which makes it a perfect match for MCMC, which generates samples from the distribution. The final necessary information such as point estimates, errors, prediction intervals, etc. are obtained from the many samples generated by MCMC.

The difference between MCMC and optimization is that MCMC keeps moving and generating samples all the time, while optimization stops somewhere (the real optimal solution when it works, or the first time when it doesn’t). In fact, MCMC may also move close to optimization, but even in that case, it moves around the optimal solution forever, expressing error in the Bayesian sense.

MCMC is a general-purpose method for handling probability distributions, and is also used in statistical physics described in “Statistical physics and its application to artificial intelligence technology” and frequency theory statistics. On the other hand, in Bayesian statistics, various computational methods are used such as Laplace approximation, Kalman filter, successive Monte Carlo method, variational Bayesian method, etc. MCMC is one of them.

In the following pages of this blog, we discuss the basic theory of the Markov chain Monte Carlo method, the specific algorithm and the implementation code.