AdaBoost

1. Training Idea

• When training an AdaBoost model, the algorithm starts by training a base classifier on the original dataset.
• The algorithm then increases the weights of the misclassified instances and trains another classifier on the dataset.
• This iterative process continues until a specified number of classifiers are trained or the model achieves a perfect score.
• AdaBoost is similar to gradient descent, but instead of tweaking a single model’s parameters to minimize a cost function, AdaBoost adds models to the ensemble, making the new model correct the errors of its predecessor.
• Once the training is complete, the model makes predictions using the ensemble of classifiers.

2. Algorithm

1. Initialize the weights of the instances:

   $$w_i^{(1)}=1/m.$$

2. Train a base classifier on the dataset, and compute the weighted error rate:

   $${ϵ}_j=\frac{{\sum }_{i=1}^m{w}_i^{(j)}\times 1_{\text{misclassified}}}{{\sum }_{i=1}^m{w}_i^{(j)}}.$$

3. Compute the predictor’s weight:

   $${\alpha }_j=\eta \log \left(\frac{1-{ϵ}_j}{{ϵ}_j}\right).$$

4. Update the weights of the instances:

   $$w_i^{(j+1)}=\{\begin{array}{ll}{w}_i^{(j)}& \text{if }{h}_j(x_i)=y_i,\\ w_i^{(j)}\times \exp ({\alpha }_j)& \text{if }{h}_j(x_i)\ne y_i.\end{array}$$

5. Normalize the weights:

   $$w_i^{(j+1)}=\frac{w_i^{(j+1)}}{{\sum }_{i=1}^m{w}_i^{(j+1)}}.$$

6. Repeat steps 2-5 using the updated weights, until the desired number of classifiers is reached.

7. Make predictions using the ensemble of classifiers:

   $$\hat{y}(x)=\arg \underset{k}{\max }\sum _{j=1}^N{\alpha }_j\times 1_{h_j(x)=k}.$$

Related Notes

• Boosting
• Gradient Boosting