## 2 AdaBoost Algorithm
```
\(x_{i}\): the input (predictor variable) \(c_{i}\): output (response variable) \(w_{i}\): observation weights \(n\): number of samples \(M\): number of iterations \(T(x)\): weak classifier \(err^{(m)}\): error rate \(\alpha\) (\(m\)): weight assigned to classifier \(C(x)\): final classification rule \(K\): number of classes (1, 2,..., \(k\))
```  
**Algorithm 1**Two class AdaBoost [3]  
As shown in the steps of Algorithm 1, first the weight (\(w_{i}\)) of all samples is initialized, meaning that it is equal for all the samples. 1. Initialization of the observation weight \(w_{i}=1/n\), \(i=1\), 2,..., \(n\). Secondly, a number of iterations (\(M\)) are performed, where they go through all possible weak classifiers to find the best one that minimizes the error rate with respect to \(w_{i}\). 2. For \(m=1\) to \(M\):  
1. Fitting a classifier \(T^{(m)}(x)\) to the training data using weights \(w_{i}\). 2. Calculate \[err^{(m)}=\sum_{i=1}^{n}w_{i}\less(c_{i}\
eq T^{(m)}(x_{i}))/\sum_{i=1}^{n}w_{i}\] The error rate \(err^{(m)}\) is the summation of the previous process for all the samples. 3. Calculate \[\alpha^{(m)}=\log\left(1-err^{(m)}/err^{(m)}\right)\] A weight \(\alpha(m)\) is assigned to the classifier. 4. Set \[w_{i}\gets w_{i}\cdot\exp\left(\alpha^{(m)}\cdot\less\left(c_{i}\
eq T^ {(m)}(x_{i})\right)\right),\;i=1,2,\ldots,n.\] The weight \(w_{i}\) is then updated where the wrongly classified samples will have more weight. 5. Re-normalization of \(w_{i}\)  
3. Output \[C(x)=\arg\max_{k}\sum_{m=1}^{M}\alpha^{(m)}\cdot\less\left(T^{(m)}(x)=k\right)\] After \(M\) such iterations, the final classification rule \(C(x)\) is formed. Figure 1: Adaptive Boosting (AdaBoost) algorithm flowchart. Notice that in order for the misclassified training data to be boosted, it is necessary that the error of each weak classifier \(err^{(m)}\) be less than \(1/2\) (in reference to the distribution on which it was trained), otherwise \(\alpha^{(m)}\) will be negative and the weights of the training samples will be updated in the wrong direction. For two-class classification problems, this condition is about the same as random guessing, but when \(K>2\), accuracy \(1/2\) may be much harder to reach than the random guessing accuracy rate \(1/K\). Therefore, AdaBoost may fail if the weak classifier \(T(x)\) is not chosen correctly. Typically, one may build 500 or 1000 classifiers in this way. A score is given to each classifier, and the final classifier is defined as the linear combination of the classifiers from every stage. Specifically, let \(T(x)\) denote a weak multi-class classifier that gives a class label to \(x\), then, the AdaBoost Algorithm 2 proceeds as follows [1]. It is a multi-class classifier algorithm, where the variable \(K\) is the number of classes. As for the overall sequence of the algorithm, it is almost the same as Algorithm 1. ```
\(x_{i}\): the input (predictor variable) \(c_{i}\): output (response variable) \(w_{i}\): observation weights \(n\): number of samples \(M\): number of iterations \(T(x)\): weak classifier \(err^{(m)}\): error rate \(\alpha(m)\): weight assigned to classifier \(C(x)\): final classification rule \(K\): number of classes (1, 2,..., \(k\))
```  
**Algorithm 2**Multi-Class AdaBoost [1]  
As shown in the steps of Algorithm 1, first the weight (\(w_{i}\)) of all samples is initialized, meaning that it is equal for all the samples. 1. Initialization of the observation weight \(w_{i}=1/n\), i = 1, 2,..., \(n\). Secondly, a number of iterations (\(M\)) are performed, where they go through all possible weak classifiers to find the best one. This will minimize the error rate with respect to \(w_{i}\). 2. For \(m=1\) to \(M\):  
1. Fitting a classifier \(T^{(m)}(x)\) to the training data using weights \(w_{i}\). 2. Calculate \[err^{(m)}=\sum_{i=1}^{n}w_{i}\less\left(c_{i}\
eq T^{(m)}(x_{i})\right)/\sum_ {i=1}^{n}w_{i}\] The error rate \(err^{(m)}\) is the summation of the previous process for all the number of samples. 3.