A Brief Introduction to Boosting

A Brief Introduction to Boosting

Robert E. Schapire

AT&T Labs, Shannon Laboratory

180 Park Avenue, Room A279, Florham Park, NJ 07932, USA

www .research.att.com/ "-'SChapire schapire@research.att.com

Abstract

Boosting is a general method for improving the accuracy of any given learning algorithm. This short paper introduces the boosting algorithm AdaBoost, and explains the underlying theory of boosting, including an explanation of why boosting often does not suffer from overfitting. Some examples of recent applications of boost­ ing are also described.

Background

Boosting is a general method which attempts to "boost" the accuracy of any given learning algorithm. Boosting has its roots in a theoretical framework for studying ma­ chine learning called the "PAC" learning model, due to Valiant [37]; see Kearns and Vazirani [24] for a good in­ troduction to this model. Kearns and Valiant [22, 23] were the first to pose the question of whether a "weak" learning algorithm which performs just slightly bet­ ter than random guessing in the PAC model can be "boosted" into an arbitrarily accurate "strong" learning algorithm. Schapire [30] came up with the first prov­ able polynomial-time boosting algorithm in 1989. A year later , Freund [14] developed a much more efficient boosting algorithm which, although optimal in a certain sense, nevertheless suffered from certain practical draw­ backs. The first experiments with these early boosting algorithms were carried out by Drucker, Schapire and Simard [13] on an OCR task.

AdaBoost

The AdaBoost algorithm, introduced in 1995 by Freund and Schapire [18], solved many of the practical difficul­ ties of the earlier boosting algorithms, and is the fo­ cus of this paper. Pseudocode for AdaBoost is given in Fig. 1. The algorithm takes as input a training set (x1 , yl), ... , (xm, Ym) where each Xi belongs to some domain or instance space X, and each label Yi is in some label set Y . For most of this paper, we assume Y = { -1, + 1} ; later, we discuss extensions to the multi­ class case. AdaBoost calls a given weak or base learning algorithm repeatedly in a series of rounds t = 1, ... , T .

• Train weak learner using distribution Dt.
• Get weak hypothesis ht : X -+ { -1, + 1} with error

• Update:

where Zt is a normalization factor (chosen so that Dt+l will be a distribution).

Output the final hypothesis:

Figure 1: The boosting algorithm AdaBoost .

One of the main ideas of the algorithm is to maintain a distribution or set of weights over the training set. The weight of this distribution on training example i on round t is denoted Dt ( i). Initially, all weights are set equaily, but on each round, the weights of incorrectly classified examples are increased so that the weak learner is forced to focus on the hard examples in the training set.

The weak learner's job is to find a weak hypothesis ht : X-+ {-1,+1} appropriate for the distribution Dt. The goodness of a weak hypothesis is measured by its error

Notice that the error is measured with respect to the distribution Dt on which the weak learner was trained.

In practice, the weak learner may be an algorithm that can use the weights Dt on the training examples. Alter­ natively, when this is not possible, a subset of the train­ ing examples can be sampled according to Dt, and these (unweighted) resampled examples can be used to train the weak learner.

Once the weak hypothesis ht has been received, Ada­ Boost chooses a parameter O:t as in the figure. Intu­ itively, O:t measures the importance that is assigned to ht. Note that O:t 2: 0 if Et :::; 1/2 (which we can assume without loss of generality), and that O:t gets larger as Et gets smaller.

The distribution Dt is next updated using the rule shown in the figure. The effect of this rule is to increase the weight of examples misclassified by ht, and to de­ crease the weight of correctly classified examples. Thus, the weight tends to concentrate on "hard" examples.

The final hypothesis H is a weighted majority vote of the T weak hypotheses where O:t is the weight assigned to ht.

Schapire and Singer [33] show how AdaBoost and its analysis can be extended to handle weak hypotheses which output real-valued or confidence-rated predictions. That is, for each instance x, the weak hypothesis ht out­ puts a prediction ht(x) E IR whose sign is the predicted label (-1 or +1) and whose magnitude iht(x)l gives a measure of "confidence" in the prediction.

Analyzing the training error

The most basic theoretical property of AdaBoost con­ cerns its ability to reduce the training error. Let us write the error Et of ht as t -It. Since a hypothesis that guesses each instance's class at random has an error rate of 1/2 (on binary problems), It thus measures how much better than random are ht 's predictions. Freund and Schapire [18] prove that the training error (the fraction of mistakes on the training set) of the final hypothesis His at most

Thus, if each weak hypothesis is slightly better than ran­ dom so that It 2: 1 for some 1 > 0, then the training error drops exponentially fast.

A similar property is enjoyed by previous boosting al­ gorithms. However, previous algorithms required that such a lower bound 1 be known a priori before boost­ ing begins. In practice, knowledge of such a bound is very difficult to obtain. AdaBoost, on the other hand, is adaptive in that it adapts to the error rates of the indi­ vidual weak hypotheses. This is the basis of its name­ "Ada" is short for "adaptive."

The bound given in Eq. (1), combined with the bounds on generalization error given below prove that AdaBoost is indeed a boosting algorithm in the sense that. it can efficiently convert a weak learning algorithm (which can always generate a hypothesis with a weak edge for any distribution) into a strong learning algorithm (which can generate a hypothesis with an arbitrarily low error rate, given sufficient data).

Generalization error

Freund and Schapire [18] showed how to bound the generalization error of the final hypothesis in terms of its training error, the size m of the sample, the VC­ dimension d of the weak hypothesis space and the number of rounds T of boosting. (The VC-dimension is a standard measure of the "complexity" of a space of hy­ potheses. See, for instance, Blumer et al. [4] .) Specifi­ cally, they used techniques from Baum and Haussler [3] to show that the generalization error, with high proba­ bility, is at most

where Pr [·] denotes empirical probability on the train­ ing sample. This bound suggests that boosting will overfit if run for too many rounds, i.e., as T becomes large. In fact, this sometimes does happen. However, in early experiments, several authors [8, 12, 28] observed empirically that boosting often does not overfit, even when run for thousands of rounds. Moreover, it was ob­ served that AdaBoost would sometimes continue to drive down the generalization error long after the training er­ ror had reached zero, clearly contradicting the spirit of the bound above. For instance, the left side of Fig. 2 shows the training and test curves of running boost­ ing on top of Quinlan's C4.5 decision-tree learning al­ gorithm [29] on the "letter" dataset.

In response to these empirical findings, Schapire et al. [32], following the work of Bartlett [1], gave an alternative analysis in terms of the margins of the training examples. The margin of example (x,y) is defined to be

It is a number in [-1, +1] which is positive if and only if H correctly classifies the example. Moreover, the mag­ nitude of the margin can be interpreted as a measure of confidence in the prediction. Schapire et al. proved that larger margins on the training set translate into a su­ perior upper bound on the generalization error. Specifi­ cally, the generalization error is at most

for any 0 > 0 with high probability. Note that this bound is entirely independent of T, the number of rounds of boosting. In addition, Schapire et al. proved that boost­ ing is particularly aggressive at reducing the margin (in a quantifiable sense) since it concentrates on the examples with the smallest margins (whether positive or negative) . Boosting's effect on the margins can be seen empirically, for instance, on the right side of Fig. 2 which shows the cumulative distribution of margins of the training ex­ amples on the "letter" dataset. In this case, even after the training error reaches zero, boosting continues to in­ crease the margins of the training examples effecting a corresponding drop in the test error.

Attempts (not always successful) to use the insights gleaned from the theory of margins have been made by several authors [6, 20, 26]. In addition, the mar­ gin theory points to a strong connection between boost­ ing and the support-vector machines of Vapnik and oth­ ers [5, 9, 38] which explicitly attempt to maximize the minimum margin.

The behavior of AdaBoost can also be understood in a game-theoretic setting as explored by Freund and Schapire [17, 19] (see also Grove and Schuurmans [20] and Breiman [7]). In particular, boosting can be viewed as repeated play of a certain game, and AdaBoost can be shown to be a special case of a more general algo­ rithm for playing repeated games and for approximately solving a game. This also shows that boosting is related to linear programming.

M ulticlass classification

There are several methods of extending AdaBoost to the multiclass case. The most straightforward general­ ization [18], called AdaBoost .M1, is adequate when the weak learner is strong enough to achieve reasonably high accuracy, even on the hard distributions created by Ada­ Boost. However, this method fails if the weak learner cannot achieve at least 50% accuracy when run on these hard distributions.

For the latter case, several more sophisticated meth­ ods have been developed. These generally work by re­ ducing the multiclass problem to a larger binary prob­ lem. Schapire and Singer's [33] algorithm AdaBoost.MH works by creating a set of binary problems, for each ex­ ample x and each possible label y, of the form: "For example x, is the correct label y or is it one of the other labels?" Freund and Schapire's [18] algorithm AdaBoost.M2 (which is a special case of Schapire and Singer's [33] AdaBoost.MR algorithm) instead creates binary problems, for each example x with correct label y and each incorrect label y' of the form: "For example x, is the correct label y or y'?"

These methods require additional effort in the de­ sign of the weak learning algorithm. A differ­ ent technique [31], which incorporates Dietterich and Bakiri's [11] method of error-correcting output codes, achieves similar provable bounds to those of Ada­ Boost.MH and AdaBoost .M2, but can be used with any weak learner which can handle simple, binary la­ beled data. Schapire and Singer [33] give yet another method of combining boosting with error-correcting out­ put codes.

Experiments and applications

Practically, AdaBoost has many advantages. It is fast , simple and easy to program. It has no parameters to tune (except for the number of round T). It requires no prior knowledge about the weak learner and so can be flexibly combined with any method for finding weak hy­ potheses. Finally, it comes with a set of theoretical guar­ antees given sufficient data and a weak learner that can reliably provide only moderately accurate weak hypothe­ ses. This is a shift in mind set for the learning-system designer: instead of trying to design a learning algorithm that is accurate over the entire space, we can instead focus on finding weaking learning algorithms that only need to be better than random.

On the other hand, some caveats are certainly in or­ der. The actual performance of boosting on a partic­ ular problem is clearly dependent on the data and the weak learner. Consistent with theory, boosting can fail to perform well given insufficient data, overly complex weak hypotheses or weak hypotheses which are too weak. Boosting seems to be especially susceptible to noise [10] .

AdaBoost has been tested empirically by many re­ searchers, including [2, 10, 12, 21, 25, 28, 36]. For in­ stance, Freund and Schapire [16] tested AdaBoost on a set of UCI benchmark datasets [27] using C4.5 [29] as a weak learning algorithm, as well as an algorithm which Figure 5: A sample of the examples that have the largest weight on an OCR task as reported by Freund and Schapire [16] . These examples were chosen after 4 rounds of boosting (top line), 12 rounds (middle) and 25 rounds (bottom). Underneath each image is a line of the form d:£I/w1,£2/w2, where dis the label of the example, £1 and £2 are the labels that get the highest and second highest vote from the combined hypothesis at that point in the run of the algorithm, and w1, w2 are the corre­ sponding normalized scores.

finds the best "decision stump" or single-test decision tree. Some of the results of these experiments are shown in Fig. 3. As can be seen from this figure, even boost­ ing the weak decision stumps can usually give as good results as C4.5, while boosting C4.5 generally gives the decision-tree algorithm a significant improvement in per­ formance.

In another set of experiments, Schapire and Singer [34] used boosting for text categorization tasks. For this work, weak hypotheses were used which test on the pres­ ence or absence of a word or phrase. Some results of these experiments comparing AdaBoost to four other methods are shown in Fig. 4. In nearly all of these exper­ iments and for all of the performance measures tested, boosting performed as well or significantly better than the other methods tested. Boosting has also been ap­ plied to text filtering [35] and "ranking" problems [15] .

A nice property of AdaBoost is its ability to identify outliers, i.e. , examples that are either mislabeled in the training data, or which are inherently ambiguous and hard to categorize. Because AdaBoost focuses its weight on the hardest examples, the examples with the highest weight often turn out to be outliers. An example of this phenomenon can be seen in Fig. 5 taken from an OCR experiment conducted by Freund and Schapire [16] .