AdaBoost
AdaBoost, short for Adaptive Boosting, is a machine learning meta-algorithm formulated by Yoav Freund and Robert Schapire, who won the 2003 Gödel Prize for their work. It can be used in conjunction with many other types of learning algorithms to improve performance. The output of the other learning algorithms is combined into a weighted sum that represents the final output of the boosted classifier. AdaBoost is adaptive in the sense that subsequent weak learners are tweaked in favor of those instances misclassified by previous classifiers. AdaBoost is sensitive to noisy data and outliers. In some problems it can be less susceptible to the overfitting problem than other learning algorithms. The individual learners can be weak, but as long as the performance of each one is slightly better than random guessing, the final model can be proven to converge to a strong learner.
Every learning algorithm tends to suit some problem types better than others, and typically has many different parameters and configurations to adjust before it achieves optimal performance on a dataset. AdaBoost is often referred to as the best out-of-the-box classifier. When used with decision tree learning, information gathered at each stage of the AdaBoost algorithm about the relative 'hardness' of each training sample is fed into the tree growing algorithm such that later trees tend to focus on harder-to-classify examples.
Overview
Problems in machine learning often suffer from the curse of dimensionality — each sample may consist of a huge number of potential features, and evaluating every feature can reduce not only the speed of classifier training and execution, but in fact reduce predictive power. Unlike neural networks and SVMs, the AdaBoost training process selects only those features known to improve the predictive power of the model, reducing dimensionality and potentially improving execution time as irrelevant features need not be computed.Training
AdaBoost refers to a particular method of training a boosted classifier. A boost classifier is a classifier in the formwhere each is a weak learner that takes an object as input and returns a value indicating the class of the object. For example, in the two-class problem, the sign of the weak learner output identifies the predicted object class and the absolute value gives the confidence in that classification. Similarly, the th classifier is positive if the sample is in a positive class and negative otherwise.
Each weak learner produces an output hypothesis,, for each sample in the training set. At each iteration, a weak learner is selected and assigned a coefficient such that the sum training error of the resulting -stage boost classifier is minimized.
Here is the boosted classifier that has been built up to the previous stage of training, is some error function and is the weak learner that is being considered for addition to the final classifier.
Weighting
At each iteration of the training process, a weight is assigned to each sample in the training set equal to the current error on that sample. These weights can be used to inform the training of the weak learner, for instance, decision trees can be grown that favor splitting sets of samples with high weights.Derivation
This derivation follows Rojas :Suppose we have a data set where each item has an associated class, and a set of weak classifiers each of which outputs a classification for each item. After the -th iteration our boosted classifier is a linear combination of the weak classifiers of the form:
At the -th iteration we want to extend this to a better boosted classifier by adding another weak classifier, with another weight :
So it remains to determine which weak classifier is the best choice for, and what its weight should be. We define the total error of as the sum of its exponential loss on each data point, given as follows:
Letting and for, we have:
We can split this summation between those data points that are correctly classified by and those that are misclassified :
Since the only part of the right-hand side of this equation that depends on is, we see that the that minimizes is the one that minimizes , i.e. the weak classifier with the lowest weighted error.
To determine the desired weight that minimizes with the that we just determined, we differentiate:
Setting this to zero and solving for yields:
We calculate the weighted error rate of the weak classifier to be, so it follows that:
which is the negative logit function multiplied by 0.5.
Thus we have derived the AdaBoost algorithm: At each iteration, choose the classifier, which minimizes the total weighted error, use this to calculate the error rate, use this to calculate the weight, and finally use this to improve the boosted classifier to.
Statistical understanding of boosting
Boosting is a form of linear regression in which the features of each sample are the outputs of some weak learner applied to.While regression tries to fit to as precisely as possible without loss of generalization, typically using least square error, the AdaBoost error function takes into account the fact that only the sign of the final result is used, thus can be far larger than 1 without increasing error. However, the exponential increase in the error for sample as increases results in excessive weight 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,. Thus it can be seen that the weight update in the AdaBoost algorithm is equivalent to recalculating the error on 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 provides a loss function based on least squares, a modified Huber loss function:
This function is more well-behaved than LogitBoost for close to 1 or -1, does not penalise ‘overconfident’ predictions, 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, whereas LogitBoost performs logistic regression, minimizing.In the gradient descent analogy, the output of the classifier for each training point is considered a point in n-dimensional space, where each axis corresponds to a training sample, each weak learner corresponds to a vector of fixed orientation and length, and the goal is to reach the target point , in the least number of steps. Thus AdaBoost algorithms perform either Cauchy or Newton optimization of training error.
Example algorithm (Discrete AdaBoost)
With:- Samples
- Desired outputs
- Initial weights set to
- Error function
- Weak learners
- Choose :
- * Find weak learner that minimizes, the weighted sum error for misclassified points
- * Choose
- Add to ensemble:
- *
- Update weights:
- * for in
- * Renormalize such that
- *
Choosing
Minimize:
Using the convexity of the exponential function, and assuming that we have:
We then differentiate that expression with respect to and set it to zero to find the minimum of the upper bound:
Note that this only applies when, though it can be a good starting guess in other cases, such as when the weak learner is biased, has multiple leaves or is some other function. In such cases the choice of weak learner and coefficient can be condensed to a single step in which is chosen from all possible as the minimizer of by some numerical searching routine.
Variants
Real AdaBoost
The output of decision trees is a class probability estimate, the probability that is in the positive class. Friedman, Hastie and Tibshirani derive an analytical minimizer for for some fixed :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 error of with respect towhere
That is is the Newton–Raphson approximation of the minimizer of the log-likelihood error at stage, and the weak learner is chosen as the learner that best approximates by weighted least squares.
As p approaches either 1 or 0, the value of 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 greedily, minimizing the overall test error as much as possible at each step, GentleBoost features a bounded step size. is chosen to minimize, and no further coefficient is applied. Thus, in the case where a weak learner exhibits perfect classification performance, GentleBoost chooses exactly equal to, while steepest descent algorithms try to set. Empirical observations about the good performance of GentleBoost appear to back up Schapire and Singer's remark that allowing excessively large values of 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.