Algorithms have extremely stringent requirements for clarity

Modeling is the essence of algorithm advantage

Algorithms are not good or bad, they are all human thoughts behind them

Difficulties in evaluating algorithm efficiency: using absolute time to evaluate efficiency is not applicable

time complexity

Ways to reduce time complexity

Utility choice model: approximating reality while maintaining solvability

Texas Hold'em Poker: Problem Size Reduction

Explore and exploit: iterate to get results

Algorithms cannot be held responsible for problems

Algorithms cannot be responsible for data

Algorithms cannot be held accountable for interpretation

clarify the problem

Modeling

Algorithm selection

Iterate

Determine the hypothesis

Validate model

Weigh feasibility

Relationship: Models and algorithms are not one-to-one correspondence

Choice: The trade-off between quality and efficiency

Advanced: More considerations for algorithm engineers

Iterative algorithm: An algorithm that repeats a fixed operation through a loop, with each step starting from the result of the previous step and gradually approaching the answer.

The conditions for the iterative algorithm to be effective: first, the algorithm must converge; second, the fixed point must be unique

The iterative strategy allows for errors in the process of finding the solution, and this error decreases very quickly, so the iterative algorithm is also very fast.

Divide-and-conquer algorithm: a backtracking algorithm that splits large problems into small ones; through backtracking, the same problem is continuously decomposed until the problem is small enough to be solved directly, and then the solutions to the small problems are merged into the original problem solution.

Traceback: nested loop calls its own procedure

Conditions for the effectiveness of the divide-and-conquer algorithm

The divide-and-conquer algorithm can be calculated in parallel with multiple CPUs, while the iterative algorithm requires that each step should be based on the result of the previous step and calculated in sequence, so it cannot be calculated in parallel with multiple CPUs.

Solution: Start with the end in mind, build from the small to the big

When facing a multi-step decision-making problem, the optimal decision of a certain step includes and depends on the optimal strategy for smaller-scale problems. This is the optimal substructure.

The efficiency of dynamic programming is affected by the circumference explosion. At this time, the algorithm engineer may not necessarily solve all the sub-problems accurately, but may only solve a part of them, and it is an inexact solution. Only one estimate is made for the solution of other sub-problems.

Portfolio Optimization

branch and bound

How to make branch-and-bound method efficient

When encountering a particularly complex combinatorial optimization problem, if you cannot find the optimal solution, you can turn to heuristic algorithms to find a good feasible solution.

Heuristic algorithms: either consistent with human intuition or natural laws

Applicable: Too many possibilities to count

Monte Carlo: Sampling random events in the problem, performing independent calculations for a limited number of samples, and finally statistics of the sample results

It relies heavily on the correctness of the parameters and is not very helpful in revealing the nature of the problem.

Machine learning algorithms are a series of algorithms that allow computers to learn autonomously. They are most suitable for problems that humans cannot solve using clear rules.

Machine learning has learned many details that humans have not been taught and do not understand.

Machine learning learns the complex relationships between things

K neighbor algorithm, based on memory, finally expresses a bunch of historical data

The decision tree model summarizes the conditional judgments through data induction, and finally expresses some complex conditional judgments.

The neural network model simulates the transmission of nerve signals and the process of nerve responses to different external information, and finally expresses a series of parameter values.

People can accept a certain degree of ambiguity when doing things, but algorithms have extremely strict requirements for clarity.

An algorithm is a set of tools that solve problems with deterministic guarantees.

Modeling means treating different problems in the same way and using the same set of algorithms to solve them.

The greatest value of modeling is to give the algorithm extraordinary problem migration capabilities.

Algorithmic models are only the reflection of human thoughts

The algorithm will not be good or bad, but in different scenarios, we need different value preferences and design ideas.

Hardware dependencies

"Infinity" problem

Time complexity is the total number of certain basic operations in an algorithm, which is a functional relationship that grows with the size of the input to the algorithm.

The job of the algorithm engineer is to find better "blueprints" and algorithms with higher efficiency and lower time complexity.

Space complexity: It is a functional relationship that increases as the input size increases as the space resources occupied by the algorithm increase.

"Divide and conquer" is to divide a complex 1 problem into two or more identical or similar sub-problems, and then divide the sub-problems into smaller sub-problems until the final sub-problem can be solved simply and directly. The solution of the original problem is the sub-problem. Combination of solutions to problems

The divide and conquer algorithm has a backtracking process. The "divide and conquer" we usually talk about does not. The divide and conquer algorithm has a backtracking process. The usual "divide and conquer" does not.

When people make choices, they usually choose the option that brings them the greatest satisfaction, that is, they choose the option that is most useful to them.

In reality, there are many factors that affect utility, and there are very complex relationships between them. An algorithm that is completely close to reality cannot get a solution.

"Linear utility model" - Assume that the relationship between all factors is just a linear superposition, without complex interactions between each other. In this way, the model becomes solvable.

The Libratus algorithm reduces the total possibilities that need to be processed several times by merging the same situations in Texas Hold'em.

The idea behind the scale reduction algorithm is to reduce a problem that is too large to be calculated to a scale that the computer can handle by discarding a small amount of information.

"Explore and exploit"

Algorithms often use iterative methods to gradually approach the answer to a problem. How to ensure convergence and convergence efficiency reflects the ingenuity of algorithm design.

The algorithm only executes the instructions given to it by humans, but what problem this operation solves cannot be understood by the algorithm.

The algorithm is just a tool, just like a hammer in your hand that can drive nails. It is only responsible for driving nails and does not understand what problem it is trying to solve by driving nails.

Algorithms only care about "calculation" and don't care about "input" and "output"

Data is garbage, and no matter how good the algorithm is, it is useless. “Garbage in, garbage out”

Algorithms can only provide solutions, not explanations

Give up some accuracy and choose algorithms that are easier to explain and accept

First - clarify the purpose

Secondly - clarify the restrictions

Finally - clarify the evaluation criteria

A mathematical model is needed to build a "bridge" to the computer

Model building is the process of converting real-life problems into algorithmic problems, and using another language to re-describe the problem.

The same problem, different algorithms have very different efficiencies

Most of the time there is no optimal solution, nor is there a unique solution

Algorithms cannot directly solve problems, and models are only approximations and abstractions of real problems, which requires algorithm engineers to continuously iterate.

After completing the algorithm design and implementation, keep returning to the original problem to evaluate the algorithm.

Iteration is also a requirement of hardware

First, we need to figure out what accuracy of prediction results we need to get.

Determining hypotheses is actually a process of establishing important variables and core relationships step by step.

There is no fixed method for verifying a model, nor is it static. We have to demonstrate it from multiple angles, and sometimes we need some creative ideas.

Whether a model is the best choice depends not only on whether the model is reliable, but also on whether it can be implemented.

There is no unified standard for what is best. But it has a bottom line, that is, the model must be able to obtain effective solutions.

Backpack problem: The capacity of the backpack is limited, so choosing what to put in it is a problem

There are many algorithms corresponding to the same model

Modeling does not mean that the algorithm selection is completed. Whether the problem can be effectively solved in the end, finding the appropriate algorithm is still crucial.

2. Choice: Trade-off between quality and efficiency

Data issues

Data has redefined the way we think about models, which is also a dimension that algorithm engineers today pay great attention to.

It is clear how each step of the iterative algorithm is performed, and there is also a definite judgment on whether the final answer to the problem can be obtained.

The algorithm can converge

fixed point

The "residual error" continues to decrease during iterations

The divide-and-conquer algorithm has a backtracking process, but the "divide-and-conquer" we usually talk about does not.

1️⃣ Can it be disassembled?

2️⃣ Fast or not?

The divide-and-conquer algorithm can use "hardware" to perform "parallel operations"

Get solutions to small problems first, then build solutions to big problems

Solve problems from back to front. Apply the right amount of propulsion with every step

Dynamic programming algorithm: When a multi-step decision-making optimization problem satisfies the optimal substructure, it is an algorithmic strategy that uses the idea of ​​starting with the end in mind and building the big from the small to solve the problem.

The efficiency of dynamic programming will be affected by "dimensional explosion"

Combination: Every decision has several possibilities, such as "putting" or "not putting" a charging station somewhere, these are the two possibilities. When the number of decision variables increases, many decision combinations will be generated between them.

Optimization: Maximizing or minimizing a goal

The characteristic of combinatorial optimization problems is that it is not difficult to find a feasible solution, but it is particularly difficult to find the optimal solution.

Branching: consider the different possibilities of the problem separately.

Delimitation: It is the process of estimating the upper bound of the optimal solution in a certain sub-search space (first determine a "temporary optimal solution" as the standard)

Pruning: When the target upper bound that can be obtained in a certain sub-search space is not comparable to a known feasible solution, the sub-space is directly eliminated.

Effective pruning: In order to further improve the efficiency of the branch and bound method, we can use the "early stopping" strategy.

Heuristic algorithms are a type of algorithm that people develop based on a certain set of rules through their understanding of the problem.

Heuristic algorithms are designed for specific problems and require detailed analysis of specific problems.

A series of general heuristic algorithms summarized through people's observation and simulation of nature or general logic when humans solve problems.

Use it when you can't find the optimal solution and "fall back to the next best solution"

Two disadvantages

The strategy of sampling random events in the problem, conducting independent calculations for a limited number of samples, and finally statisticalizing the sample results

Each sample represents a simulation of reality. A finite number of simulations are used to replace the possibility of all parallel universes.

The Monte Carlo method is used when there are too many possibilities for us to calculate. If there are very few possibilities that need to be considered, just calculate them directly.

1️⃣The Monte Carlo method is an estimate of the problem, not an exact calculation.

2️⃣The success of the Monte Carlo method relies heavily on the correctness of the model and parameters

3️⃣The Monte Carlo method will reduce our chance of discovering the essence of the problem

Machine learning algorithms are a series of algorithms that allow computers to learn autonomously. They are best used on problems that humans cannot solve with clear rules.

Machine learning has learned many details that humans have not been taught and do not understand themselves.

The complex relationship between things, especially certain pattern characteristics in the relationship

Knowledge is our understanding of information and the relationships between things

Ability is the ability to apply knowledge into practice

Having knowledge does not mean having ability, but without knowledge there is no ability

k neighbor algorithm: judge by comparing with historical data

Decision tree model: Summarize the conditional judgment through data induction; compare the correlation between each feature and the object to be learned, put the high correlation in the conditional judgment, and throw away the low correlation.

Neural network model: simulates the transmission of nerve signals and the process of nerve responses to different information from the outside world. There are no real nerves in the algorithm, nor the strength of the nerve responses. Instead there are a lot of parameters. The closer the parameter is to zero, the less important the feature it represents

difficulty

Current approach