AdaBoost, short for "Adaptive Boosting", is a machine learning meta-algorithm
formulated by Yoav Freund and Robert Schapire who won the Gödel Prize in 2003
for their work. It can be used in conjunction with many other types of
learning algorithms to improve their 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, however, 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
While every learning algorithm will tend to suit some problem types better than
others, and will typically have many different parameters and configurations
to be adjusted before achieving 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, per the Hughes Effect.
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 do
not need to be computed. = Training=
AdaBoost refers to a particular method of training a boosted classifier. A
boost classifier is a classifier in the form
where each is a weak learner that takes an object as input and returns a real
valued result indicating the class of the object. The sign of the weak learner
output identifies the predicted object class and the absolute value gives the
confidence in that classification. Similarly, the -layer classifier will be
positive if the sample is believed to be in the 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 a multiple of one of the weak
classifiers: 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 to be 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 which 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.
In order 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 . Specifically, in the case
where all weak learners are known a priori, AdaBoost corresponds to a single
iteration of the backfitting algorithm in which the smoothing splines are the
minimizers of , that is: fits an exponential cost function and is linear
with respect to the observation. Thus, boosting is seen to be a specific type
of linear regression. 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 will be 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 will always be 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 to be 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 With:
Samples Desired outputs
Initial weights set to Error function
Weak learners For in :
Choose : Find weak learner that minimizes , the
weighted sum error for misclassified points
Choose Add to ensemble:
Update weights: for all i
Renormalize such that (Note: It can be shown that at every
step, which can simplify the calculation of the new weights.)
= Choosing = is chosen as it can be analytically
shown to be the minimizer of the exponential error function for Discrete
AdaBoost. 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 to
, where , and . 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 will be 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 will choose exactly equal to , while steepest descent algorithms
will 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.
= Totally Corrective Algorithms= For steepest descent versions of
AdaBoost, where 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
that a weak learner t+1 will be chosen 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 refers to the process of
removing poorly performing weak classifiers, in order to improve the
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 suggest an alternative criteria 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. See also
Bootstrap aggregating CoBoosting
BrownBoost Gradient boosting
References Implementations
AdaBoost and the Super Bowl of Classifiers - A Tutorial on AdaBoost.
AdaBoost in C++, an implementation of AdaBoost in C++ and boost by Antonio
Gulli icsiboost, an open source implementation
of Boostexter JBoost, a site offering a classification
and visualization package, implementing AdaBoost among other boosting
algorithms. MATLAB AdaBoost toolbox. Includes Real
AdaBoost, Gentle AdaBoost and Modest AdaBoost implementations.
A Matlab Implementation of AdaBoost Multi-threaded MATLAB-compatible
implementation of Boosted Trees milk for Python implements AdaBoost.
MPBoost++, a C++ implementation of the original AdaBoost.MH algorithm and of an
improved variant, the MPBoost algorithm. multiboost, a fast C++ implementation of
multi-classmulti-task boosting algorithms. It is based on AdaBoost.MH
but also implements popular cascade classifiers and FilterBoost along with a
batch of common multi-class base learners.
NPatternRecognizer , a fast machine learning algorithm library written in
C#. It contains support vector machine, neural networks, bayes, boost, k-nearest
neighbor, decision tree, ..., etc. OpenCV implementation of several
boosting variants Into contains open source
implementations of many AdaBoost and FloatBoost variants in C++.
Mallet Java implementation. adabag adabag: An R package for binary
and multiclass Boosting and Bagging. Scikit-learn Python implementation.
fertilized forests A general purpose, platform independent, easy to extend
decision forest library that supports boosted training based on multiclass
AdaBoost.M2, Samme and Samme.R External links
"A decision-theoretic generalization of on-line learning and an application to
boosting". Journal of Computer and System Sciences 55. 1997.
doi:10.1006/jcss.1997.1504. CiteSeerX: 10.1.1.32.8918: original paper of Yoav
Freund and Robert E.Schapire where AdaBoost is first introduced.
"Boosting.org": a site on boosting and related ensemble learning methods
"AdaBoost": presentation summarizing AdaBoost.
"AdaBoost example": presentation showing an AdaBoost example.
Freund; Schapire. "A Short Introduction to Boosting": introduction to AdaBoost
"An applet demonstrating AdaBoost". Polikar, R.. "Ensemble Based Systems in
Decision Making". IEEE Circuits and Systems Magazine 6: 21–45: a tutorial
article on ensemble systems including pseudocode, block diagrams and
implementation issues for AdaBoost and other ensemble learning algorithms.