AdaBoost

Derivation

This derivation follows Rojas (2009):

Suppose we have a data set ${\displaystyle \{(x_1,y_1),\dots ,(x_N,y_N)\}}$ where each item ${\displaystyle x_i}$ has an associated class ${\displaystyle y_i\in \{-1,1\}}$, and a set of weak classifiers ${\displaystyle \{k_1,\dots ,k_L\}}$ each of which outputs a classification ${\displaystyle k_j(x_i)\in \{-1,1\}}$ for each item. After the ${\displaystyle (m-1)}$-th iteration our boosted classifier is a linear combination of the weak classifiers of the form: $${\displaystyle C_{(m-1)}(x_i)={\alpha }_1{k}_1(x_i)+\cdots +{\alpha }_{m-1}{k}_{m-1}(x_i),}$$ where the class will be the sign of ${\displaystyle C_{(m-1)}(x_i)}$. At the ${\displaystyle m}$-th iteration we want to extend this to a better boosted classifier by adding another weak classifier ${\displaystyle k_m}$, with another weight ${\displaystyle {\alpha }_m}$: $${\displaystyle C_m(x_i)=C_{(m-1)}(x_i)+{\alpha }_m{k}_m(x_i)}$$

So it remains to determine which weak classifier is the best choice for ${\displaystyle k_m}$, and what its weight ${\displaystyle {\alpha }_m}$ should be. We define the total error ${\displaystyle E}$ of ${\displaystyle C_m}$ as the sum of its exponential loss on each data point, given as follows: $${\displaystyle E=\sum _{i=1}^N{e}^{-y_i{C}_m(x_i)}=\sum _{i=1}^N{e}^{-y_i{C}_{(m-1)}(x_i)}{e}^{-y_i{\alpha }_m{k}_m(x_i)}}$$

Letting ${\displaystyle w_i^{(1)}=1}$ and ${\displaystyle w_i^{(m)}=e^{-y_i{C}_{m-1}(x_i)}}$ for ${\displaystyle m>1}$, we have: $${\displaystyle E=\sum _{i=1}^N{w}_i^{(m)}{e}^{-y_i{\alpha }_m{k}_m(x_i)}}$$

We can split this summation between those data points that are correctly classified by ${\displaystyle k_m}$ (so ${\displaystyle y_i{k}_m(x_i)=1}$) and those that are misclassified (so ${\displaystyle y_i{k}_m(x_i)=-1}$): $${\displaystyle \begin{array}{cc}E& =\sum _{y_i=k_m(x_i)}{w}_i^{(m)}{e}^{-{\alpha }_m}+\sum _{y_i\ne k_m(x_i)}{w}_i^{(m)}{e}^{{\alpha }_m}\\ & =\sum _{i=1}^N{w}_i^{(m)}{e}^{-{\alpha }_m}+\sum _{y_i\ne k_m(x_i)}{w}_i^{(m)}\left(e^{{\alpha }_m}-e^{-{\alpha }_m}\right)\end{array}}$$

Since the only part of the right-hand side of this equation that depends on ${\displaystyle k_m}$ is $\sum _{y_i\ne k_m(x_i)}{w}_i^{(m)}$, we see that the ${\displaystyle k_m}$ that minimizes ${\displaystyle E}$ is the one in the set ${\displaystyle \{k_1,\dots ,k_L\}}$ that minimizes $\sum _{y_i\ne k_m(x_i)}{w}_i^{(m)}$ [assuming that ${\displaystyle {\alpha }_m>0}$], i.e. the weak classifier with the lowest weighted error (with weights ${\displaystyle w_i^{(m)}=e^{-y_i{C}_{m-1}(x_i)}}$).

To determine the desired weight ${\displaystyle {\alpha }_m}$ that minimizes ${\displaystyle E}$ with the ${\displaystyle k_m}$ that we just determined, we differentiate: $${\displaystyle \frac{dE}{d{\alpha }_m}=\frac{d(\sum _{y_i=k_m(x_i)}{w}_i^{(m)}{e}^{-{\alpha }_m}+\sum _{y_i\ne k_m(x_i)}{w}_i^{(m)}{e}^{{\alpha }_m})}{d{\alpha }_m}}$$

The value of ${\displaystyle {\alpha }_m}$ that minimizes the above expression is: $${\displaystyle {\alpha }_m=\frac{1}{2}\ln \left(\frac{\sum _{y_i=k_m(x_i)}{w}_i^{(m)}}{\sum _{y_i\ne k_m(x_i)}{w}_i^{(m)}}\right)}$$

Proof

$${\displaystyle \frac{dE}{d{\alpha }_m}=-\sum _{y_i=k_m(x_i)}{w}_i^{(m)}{e}^{-{\alpha }_m}+\sum _{y_i\ne k_m(x_i)}{w}_i^{(m)}{e}^{{\alpha }_m}=0}$$ because ${\displaystyle e^{-{\alpha }_m}}$ does not depend on ${\displaystyle i}$ $${\displaystyle e^{-{\alpha }_m}\sum _{y_i=k_m(x_i)}{w}_i^{(m)}=e^{{\alpha }_m}\sum _{y_i\ne k_m(x_i)}{w}_i^{(m)}}$$ $${\displaystyle -{\alpha }_m+\ln \left(\sum _{y_i=k_m(x_i)}{w}_i^{(m)}\right)={\alpha }_m+\ln \left(\sum _{y_i\ne k_m(x_i)}{w}_i^{(m)}\right)}$$ $${\displaystyle -2{\alpha }_m=\ln \left({\displaystyle \frac{\sum _{y_i\ne k_m(x_i)}{w}_i^{(m)}}{\sum _{y_i=k_m(x_i)}{w}_i^{(m)}}}\right)}$$ $${\displaystyle {\alpha }_m=-{\displaystyle \frac{1}{2}}\ln \left({\displaystyle \frac{\sum _{y_i\ne k_m(x_i)}{w}_i^{(m)}}{\sum _{y_i=k_m(x_i)}{w}_i^{(m)}}}\right)}$$ $${\displaystyle {\alpha }_m={\displaystyle \frac{1}{2}}\ln \left({\displaystyle \frac{\sum _{y_i=k_m(x_i)}{w}_i^{(m)}}{\sum _{y_i\ne k_m(x_i)}{w}_i^{(m)}}}\right)}$$

We calculate the weighted error rate of the weak classifier to be ${\displaystyle {ϵ}_m=\frac{\sum _{y_i\ne k_m(x_i)}{w}_i^{(m)}}{\sum _{i=1}^N{w}_i^{(m)}}}$, so it follows that: $${\displaystyle {\alpha }_m=\frac{1}{2}\ln \left(\frac{1-{ϵ}_m}{{ϵ}_m}\right)}$$ which is the negative logit function multiplied by 0.5. Due to the convexity of ${\displaystyle E}$ as a function of ${\displaystyle {\alpha }_m}$, this new expression for ${\displaystyle {\alpha }_m}$ gives the global minimum of the loss function.

Note: This derivation only applies when ${\displaystyle k_m(x_i)\in \{-1,1\}}$, though it can be a good starting guess in other cases, such as when the weak learner is biased (${\displaystyle k_m(x)\in \{a,b\},a\ne -b}$), has multiple leaves (${\displaystyle k_m(x)\in \{a,b,\dots ,n\}}$) or is some other function ${\displaystyle k_m(x)\in \mathbb{R}}$.

Thus we have derived the AdaBoost algorithm: At each iteration, choose the classifier ${\displaystyle k_m}$, which minimizes the total weighted error $\sum _{y_i\ne k_m(x_i)}{w}_i^{(m)}$, use this to calculate the error rate ${\displaystyle {ϵ}_m=\frac{\sum _{y_i\ne k_m(x_i)}{w}_i^{(m)}}{\sum _{i=1}^N{w}_i^{(m)}}}$, use this to calculate the weight ${\displaystyle {\alpha }_m=\frac{1}{2}\ln \left(\frac{1-{ϵ}_m}{{ϵ}_m}\right)}$, and finally use this to improve the boosted classifier ${\displaystyle C_{m-1}}$ to ${\displaystyle C_m=C_{(m-1)}+{\alpha }_m{k}_m}$.

Statistical understanding of boosting

Boosting is a form of linear regression in which the features of each sample ${\displaystyle x_i}$ are the outputs of some weak learner ${\displaystyle h}$ applied to ${\displaystyle x_i}$.

While regression tries to fit ${\displaystyle F(x)}$ to ${\displaystyle y(x)}$ as precisely as possible without loss of generalization, typically using least square error ${\displaystyle E(f)=(y(x)-f(x){)}^2}$, whereas the AdaBoost error function ${\displaystyle E(f)=e^{-y(x)f(x)}}$ takes into account the fact that only the sign of the final result is used, thus ${\displaystyle |F(x)|}$ can be far larger than 1 without increasing error. However, the exponential increase in the error for sample ${\displaystyle x_i}$ as ${\displaystyle -y(x_i)f(x_i)}$ increases, resulting in excessive weights being assigned to outliers.

One feature of the choice of exponential error function is that the error of the final additive model is the product of the error of each stage, that is, ${\displaystyle e^{\sum _m-y_i{f}_m(x_i)}=\prod _m{e}^{-y_i{f}_m(x_i)}}$. Thus it can be seen that the weight update in the AdaBoost algorithm is equivalent to recalculating the error on ${\displaystyle F_t(x)}$ after each stage.

There is a lot of flexibility allowed in the choice of loss function. As long as the loss function is monotonic and continuously differentiable, the classifier is always driven toward purer solutions. Zhang (2004) provides a loss function based on least squares, a modified Huber loss function: $${\displaystyle \varphi (y,f(x))=\{\begin{array}{ll}-4yf(x)& \text{if }yf(x)<-1,\\ (yf(x)-1{)}^2& \text{if }-1\le yf(x)\le 1.\\ 0& \text{if }yf(x)>1\end{array}}$$

This function is more well-behaved than LogitBoost for ${\displaystyle f(x)}$ close to 1 or -1, does not penalise ‘overconfident’ predictions (${\displaystyle yf(x)>1}$), unlike unmodified least squares, and only penalises samples misclassified with confidence greater than 1 linearly, as opposed to quadratically or exponentially, and is thus less susceptible to the effects of outliers.

Boosting as gradient descent

Boosting can be seen as minimization of a convex loss function over a convex set of functions. Specifically, the loss being minimized by AdaBoost is the exponential loss $${\displaystyle \sum _i\varphi (i,y,f)=\sum _i{e}^{-y_{i}f(x_i)},}$$ whereas LogitBoost performs logistic regression, minimizing $${\displaystyle \sum _i\varphi (i,y,f)=\sum _i\ln \left(1+e^{-y_{i}f(x_i)}\right).}$$

In the gradient descent analogy, the output of the classifier for each training point is considered a point ${\displaystyle \left(F_t(x_1),\dots ,F_t(x_n)\right)}$ in n-dimensional space, where each axis corresponds to a training sample, each weak learner ${\displaystyle h(x)}$ corresponds to a vector of fixed orientation and length, and the goal is to reach the target point ${\displaystyle (y_1,\dots ,y_n)}$ (or any region where the value of loss function ${\displaystyle E_T(x_1,\dots ,x_n)}$ is less than the value at that point), in the fewest steps. Thus AdaBoost algorithms perform either Cauchy (find ${\displaystyle h(x)}$ with the steepest gradient, choose ${\displaystyle \alpha }$ to minimize test error) or Newton (choose some target point, find ${\displaystyle \alpha h(x)}$ that brings ${\displaystyle F_t}$ closest to that point) optimization of training error.

Example algorithm (Discrete AdaBoost)

With:

• Samples ${\displaystyle x_1\dots x_n}$
• Desired outputs ${\displaystyle y_1\dots y_n,y\in \{-1,1\}}$
• Initial weights ${\displaystyle w_{1,1}\dots w_{n,1}}$ set to ${\displaystyle \frac{1}{n}}$
• Error function ${\displaystyle E(f(x),y_i)=e^{-y_{i}f(x_i)}}$
• Weak learners ${\displaystyle h:x\to \{-1,1\}}$

For ${\displaystyle t}$ in ${\displaystyle 1\dots T}$:

• Choose ${\displaystyle h_t(x)}$:
  • Find weak learner ${\displaystyle h_t(x)}$ that minimizes ${\displaystyle {ϵ}_t}$, the weighted sum error for misclassified points ${\displaystyle {ϵ}_t=\sum _{\stackrel{i=1}{h_t(x_i)\ne y_i}}^n{w}_{i,t}}$
  • Choose ${\displaystyle {\alpha }_t=\frac{1}{2}\ln \left(\frac{1-{ϵ}_t}{{ϵ}_t}\right)}$
• Add to ensemble:
  • ${\displaystyle F_t(x)=F_{t-1}(x)+{\alpha }_t{h}_t(x)}$
• Update weights:
  • ${\displaystyle w_{i,t+1}=w_{i,t}{e}^{-y_i{\alpha }_t{h}_t(x_i)}}$ for ${\displaystyle i}$ in ${\displaystyle 1\dots n}$
  • Renormalize ${\displaystyle w_{i,t+1}}$ such that ${\displaystyle \sum _i{w}_{i,t+1}=1}$
  • (Note: It can be shown that ${\displaystyle \frac{\sum _{h_t(x_i)=y_i}{w}_{i,t+1}}{\sum _{h_t(x_i)\ne y_i}{w}_{i,t+1}}=\frac{\sum _{h_t(x_i)=y_i}{w}_{i,t}}{\sum _{h_t(x_i)\ne y_i}{w}_{i,t}}}$ at every step, which can simplify the calculation of the new weights.)

Variants

Real AdaBoost

The output of decision trees is a class probability estimate ${\displaystyle p(x)=P(y=1|x)}$, the probability that ${\displaystyle x}$ is in the positive class. Friedman, Hastie and Tibshirani derive an analytical minimizer for ${\displaystyle e^{-y\left(F_{t-1}(x)+f_t(p(x))\right)}}$ for some fixed ${\displaystyle p(x)}$ (typically chosen using weighted least squares error):

${\displaystyle f_t(x)=\frac{1}{2}\ln \left(\frac{x}{1-x}\right)}$.

Thus, rather than multiplying the output of the entire tree by some fixed value, each leaf node is changed to output half the logit transform of its previous value.

LogitBoost

LogitBoost represents an application of established logistic regression techniques to the AdaBoost method. Rather than minimizing error with respect to y, weak learners are chosen to minimize the (weighted least-squares) error of ${\displaystyle f_t(x)}$ with respect to $${\displaystyle z_t=\frac{y^{\ast }-p_t(x)}{2p_t(x)(1-p_t(x))},}$$ where $${\displaystyle p_t(x)=\frac{e^{F_{t-1}(x)}}{e^{F_{t-1}(x)}+e^{-F_{t-1}(x)}},}$$ $${\displaystyle w_t=p_t(x)(1-p_t(x))}$$ $${\displaystyle y^{\ast }=\frac{y+1}{2}.}$$

That is ${\displaystyle z_t}$ is the Newton–Raphson approximation of the minimizer of the log-likelihood error at stage ${\displaystyle t}$, and the weak learner ${\displaystyle f_t}$ is chosen as the learner that best approximates ${\displaystyle z_t}$ by weighted least squares.

As p approaches either 1 or 0, the value of ${\displaystyle p_t(x_i)(1-p_t(x_i))}$ becomes very small and the z term, which is large for misclassified samples, can become numerically unstable, due to machine precision rounding errors. This can be overcome by enforcing some limit on the absolute value of z and the minimum value of w

Gentle AdaBoost

While previous boosting algorithms choose ${\displaystyle f_t}$ greedily, minimizing the overall test error as much as possible at each step, GentleBoost features a bounded step size. ${\displaystyle f_t}$ is chosen to minimize $\sum _i{w}_{t,i}(y_i-f_t(x_i){)}^2$, and no further coefficient is applied. Thus, in the case where a weak learner exhibits perfect classification performance, GentleBoost chooses ${\displaystyle f_t(x)={\alpha }_t{h}_t(x)}$ exactly equal to ${\displaystyle y}$, while steepest descent algorithms try to set ${\displaystyle {\alpha }_t=\mathrm{\infty }}$. Empirical observations about the good performance of GentleBoost appear to back up Schapire and Singer's remark that allowing excessively large values of ${\displaystyle \alpha }$ can lead to poor generalization performance.

Early termination

A technique for speeding up processing of boosted classifiers, early termination refers to only testing each potential object with as many layers of the final classifier necessary to meet some confidence threshold, speeding up computation for cases where the class of the object can easily be determined. One such scheme is the object detection framework introduced by Viola and Jones: in an application with significantly more negative samples than positive, a cascade of separate boost classifiers is trained, the output of each stage biased such that some acceptably small fraction of positive samples is mislabeled as negative, and all samples marked as negative after each stage are discarded. If 50% of negative samples are filtered out by each stage, only a very small number of objects would pass through the entire classifier, reducing computation effort. This method has since been generalized, with a formula provided for choosing optimal thresholds at each stage to achieve some desired false positive and false negative rate.

In the field of statistics, where AdaBoost is more commonly applied to problems of moderate dimensionality, early stopping is used as a strategy to reduce overfitting. A validation set of samples is separated from the training set, performance of the classifier on the samples used for training is compared to performance on the validation samples, and training is terminated if performance on the validation sample is seen to decrease even as performance on the training set continues to improve.

Totally corrective algorithms

For steepest descent versions of AdaBoost, where ${\displaystyle {\alpha }_t}$ is chosen at each layer t to minimize test error, the next layer added is said to be maximally independent of layer t: it is unlikely to choose a weak learner t+1 that is similar to learner t. However, there remains the possibility that t+1 produces similar information to some other earlier layer. Totally corrective algorithms, such as LPBoost, optimize the value of every coefficient after each step, such that new layers added are always maximally independent of every previous layer. This can be accomplished by backfitting, linear programming or some other method.

Pruning

Pruning is the process of removing poorly performing weak classifiers to improve memory and execution-time cost of the boosted classifier. The simplest methods, which can be particularly effective in conjunction with totally corrective training, are weight- or margin-trimming: when the coefficient, or the contribution to the total test error, of some weak classifier falls below a certain threshold, that classifier is dropped. Margineantu & Dietterich suggested an alternative criterion for trimming: weak classifiers should be selected such that the diversity of the ensemble is maximized. If two weak learners produce very similar outputs, efficiency can be improved by removing one of them and increasing the coefficient of the remaining weak learner.