Adaboost algorithm

1. The basic idea of the improvement method

The promotion method is based on the idea that for a complex task, the judgment obtained by appropriately synthesizing the judgments of multiple experts is better than the judgment of any one of the experts alone. In fact, it is the principle of "three stinky cobblers topped by Zhuge Liang".

Let's introduce two concepts:

Strongly learnable: In the probably approximately correct (PAC) learning framework, a concept, if there is a polynomial learning algorithm that can learn it, and the accuracy rate is very high, then the concept is said to be strongly learnable.

Weak learnable: A concept, if there is a polynomial learning algorithm that can learn it, the correct rate of learning is only slightly better than random guessing, then the concept is called weak learnable.

For classification problems, given a training sample set, it is much easier to find rough classification rules (weak classifiers) than to find accurate classification rules (strong classifiers). The improvement method is to start from the weak learning algorithm, repeatedly learn, get a series of weak classifiers (also known as basic classifiers), and then combine these weak classifiers to form a strong classifier. Most lifting methods are to change the probability distribution of the training data (weight distribution of the training data) and call a weak learning algorithm to learn a series of weak classifiers for different training data distributions.

As a result, there are two problems that need to be solved:

(1) How to change the weight or probability distribution of the training data in each round?

(2) How to combine weak classifiers into a strong classifier?

2, the idea of AdaBoost algorithm

Explaining the idea of the AdaBoost algorithm is mainly to answer how to solve the two questions raised above.

For the first question, AdaBoost's approach is to increase the weights of samples that were incorrectly classified by the previous round of weak hmmms, and to lower the weights of those samples that were correctly classified. As a result, data that are not properly classified receive greater attention from the weak classifiers of the later round due to their increased weights.

For the second question, AdaBoost takes a weighted majority vote on combinations of weak classifiers. Specifically, increase the weight of the weak classifier with a small classification error rate, so that it plays a larger role in the Extinction of the Biao, and reduce the weight of the weak classifier with a large classification error rate, so that it plays a smaller role in the voting.

3. AdaBoost algorithm steps:

According to Teacher Li Hang's book, here I directly screenshot, the teacher for AdaBoost's steps to sort out very well: