A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting

A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting[^1]

Yoav Freund and Robert E. Schapire²

AT&T Labs, 180 Park Avenue, Florham Park, New Jersey 07932

Received December 19, 1996

In the first part of the paper we consider the problem of dynamically apportioning resources among a set of options in a worst-case on-line framework. The model we study can be interpreted as a broad, abstract extension of the well-studied on-line prediction model to a general decision-theoretic setting. We show that the multiplicative weight-update Littlestone–Warmuth rule can be adapted to this model, yielding bounds that are slightly weaker in some cases, but applicable to a considerably more general class of learning problems. We show how the resulting learning algorithm can be applied to a variety of problems, including gambling, multiple-outcome prediction, repeated games, and prediction of points in $\mathbb{R}^n$. In the second part of the paper we apply the multiplicative weight-update technique to derive a new boosting algorithm. This boosting algorithm does not require any prior knowledge about the performance of the weak learning algorithm. We also study generalizations of the new boosting algorithm to the problem of learning functions whose range, rather than being binary, is an arbitrary finite set or a bounded segment of the real line. © 1997 Academic Press

1 INTRODUCTION

A gambler, frustrated by persistent horse-racing losses and envious of his friends’ winnings, decides to allow a group of his fellow gamblers to make bets on his behalf. He decides he will wager a fixed sum of money in every race, but that he will apportion his money among his friends based on how well they are doing. Certainly, if he knew psychically ahead of time which of his friends would win the most, he would naturally have that friend handle all his wagers. Lacking such clairvoyance, however, he attempts to allocate each race’s wager in such a way that his total winnings for the season will be reasonably close to what he would have won had he bet everything with the luckiest of his friends.

In this paper, we describe a simple algorithm for solving such dynamic allocation problems, and we show that our solution can be applied to a great assortment of learning problems. Perhaps the most surprising of these applications is the derivation of a new algorithm for “boosting,” i.e., for converting a “weak” PAC learning algorithm that performs just slightly better than random guessing into one with arbitrarily high accuracy.

We formalize our on-line allocation model as follows. The allocation agent $A$ has $N$ options or strategies to choose from; we number these using the integers $1, ..., N$. At each time step $t = 1, 2, ..., T$, the allocator $A$ decides on a distribution $\mathbf{p}^t$ over the strategies; that is $p_i^t \geq 0$ is the amount allocated to strategy $i$, and $\sum_{i=1}^N p_i^t = 1$. Each strategy $i$ then suffers some loss $\ell_i^t$ which is determined by the (possibly adversarial) “environment.” The loss suffered by $A$ is then $\sum_{i=1}^N p_i^t \ell_i^t = \mathbf{p}^t \cdot \boldsymbol{\ell}^t$, i.e., the average loss of the strategies with respect to $A$’s chosen allocation rule. We call this loss function the mixture loss.

In this paper, we always assume that the loss suffered by any strategy is bounded so that, without loss of generality, $\ell_i^t \in [0, 1]$. Besides this condition, we make no assumptions about the form of the loss vectors $\boldsymbol{\ell}^t$, or about the manner in which they are generated; indeed, the adversary’s choice for $\boldsymbol{\ell}^t$ may even depend on the allocator’s chosen mixture $\mathbf{p}^t$.

The goal of the algorithm $A$ is to minimize its cumulative loss relative to the loss suffered by the best strategy. That is, $A$ attempts to minimize its net loss

where

is the total cumulative loss suffered by algorithm $A$ on the first $T$ trials, and

is strategy $i$’s cumulative loss. In Section 2, we show that Littlestone and Warmuth’s [20] “weighted majority” algorithm can be generalized to

0022-0000/97 \$25.00 Copyright © 1997 by Academic Press All rights of reproduction in any form reserved.

handle this problem, and we prove a number of bounds on the net loss. For instance, one of our results shows that the net loss of our algorithm can be bounded by $O(\sqrt{T \ln N})$ or, put another way, that the average per trial net loss is decreasing at the rate $O(\sqrt{(\ln N)/T})$. Thus, as $T$ increases, this difference decreases to zero.

Our results for the on-line allocation model can be applied to a wide variety of learning problems, as we describe in Section 3. In particular, we generalize the results of Littlestone and Warmuth [20] and Cesa-Bianchi et al. [4] for the problem of predicting a binary sequence using the advice of a team of “experts.” Whereas these authors proved worst-case bounds for making on-line randomized decisions over a binary decision and outcome space with a $\{0, 1\}$-valued discrete loss, we prove (slightly weaker) bounds that are applicable to any bounded loss function over any decision and outcome spaces. Our bounds express explicitly the rate at which the loss of the learning algorithm approaches that of the best expert.

Related generalizations of the expert prediction model were studied by Vovk [25], Kivinen and Warmuth [19], and Haussler et al. [15]. Like us, these authors focused primarily on multiplicative weight-update algorithms. Chung [5] also presented a generalization, giving the problem a game-theoretic treatment.

Boosting

Returning to the horse-racing story, suppose now that the gambler grows weary of choosing among the experts and instead wishes to create a computer program that will accurately predict the winner of a horse race based on the usual information (number of races recently won by each horse, betting odds for each horse, etc.). To create such a program, he asks his favorite expert to explain his betting strategy. Not surprisingly, the expert is unable to articulate a grand set of rules for selecting a horse. On the other hand, when presented with the data for a specific set of races, the expert has no trouble coming up with a “rule-of-thumb” for that set of races (such as, “Bet on the horse that has recently won the most races” or “Bet on the horse with the most favored odds”). Although such a rule-of-thumb, by itself, is obviously very rough and inaccurate, it is not unreasonable to expect it to provide predictions that are at least a little bit better than random guessing. Furthermore, by repeatedly asking the expert’s opinion on different collections of races, the gambler is able to extract many rules-of-thumb.

In order to use these rules-of-thumb to maximum advantage, there are two problems faced by the gambler: First, how should he choose the collections of races presented to the expert so as to extract rules-of-thumb from the expert that will be the most useful? Second, once he has collected many rules-of-thumb, how can they be combined into a single, highly accurate prediction rule?

Boosting refers to this general problem of producing a very accurate prediction rule by combining rough and moderately inaccurate rules-of-thumb. In the second part of the paper, we present and analyze a new boosting algorithm inspired by the methods we used for solving the on-line allocation problem.

Formally, boosting proceeds as follows: The booster is provided with a set of labelled training examples $(x_1, y_1), ..., (x_N, y_N)$, where $y_i$ is the label associated with instance $x_i$; for instance, in the horse-racing example, $x_i$ might be the observable data associated with a particular horse race, and $y_i$ the outcome (winning horse) of that race. On each round $t = 1, ..., T$, the booster devises a distribution $D_t$ over the set of examples, and requests (from an unspecified oracle) a weak hypothesis (or rule-of-thumb) $h_t$ with low error $\varepsilon_t$ with respect to $D_t$ (that is, $\varepsilon_t = \Pr_{i \sim D_t}[h_t(x_i) \neq y_i]$). Thus, distribution $D_t$ specifies the relative importance of each example for the current round. After $T$ rounds, the booster must combine the weak hypotheses into a single prediction rule.

Unlike the previous boosting algorithms of Freund [10, 11] and Schapire [22], the new algorithm needs no prior knowledge of the accuracies of the weak hypotheses. Rather, it adapts to these accuracies and generates a weighted majority hypothesis in which the weight of each weak hypothesis is a function of its accuracy. For binary prediction problems, we prove in Section 4 that the error of this final hypothesis (with respect to the given set of examples) is bounded by $\exp(-2 \sum_{t=1}^T \gamma_t^2)$ where $\varepsilon_t = 1/2 - \gamma_t$ is the error of the $t$th weak hypothesis. Since a hypothesis that makes entirely random guesses has error $1/2$, $\gamma_t$ measures the accuracy of the $t$th weak hypothesis relative to random guessing. Thus, this bound shows that if we can consistently find weak hypotheses that are slightly better than random guessing, then the error of the final hypothesis drops exponentially fast.

Note that the bound on the accuracy of the final hypothesis improves when any of the weak hypotheses is improved. This is in contrast with previous boosting algorithms whose performance bound depended only on the accuracy of the least accurate weak hypothesis. At the same time, if the weak hypotheses all have the same accuracy, the performance of the new algorithm is very close to that achieved by the best of the known boosting algorithms.

In Section 5, we give two extensions of our boosting algorithm to multi-class prediction problems in which each example belongs to one of several possible classes (rather than just two). We also give an extension to regression problems in which the goal is to estimate a real-valued function.

2 THE ON-LINE ALLOCATION ALGORITHM AND ITS ANALYSIS

In this section, we present our algorithm, called Hedge($\beta$), for the on-line allocation problem. The algorithm and its analysis are direct generalizations of Littlestone and Warmuth’s weighted majority algorithm [20].

The pseudo-code for Hedge(β) is shown in Fig. 1. The algorithm maintains a weight vector whose value at time t is denoted $\mathbf{w}^t = \langle w_1^t, ..., w_N^t \rangle$. At all times, all weights will be nonnegative. All of the weights of the initial weight vector $\mathbf{w}^1$ must be nonnegative and sum to one, so that $\sum_{i=1}^N w_i^1 = 1$. Besides these conditions, the initial weight vector may be arbitrary, and may be viewed as a “prior” over the set of strategies. Since our bounds are strongest for those strategies receiving the greatest initial weight, we will want to choose the initial weights so as to give the most weight to those strategies which we expect are most likely to perform the best. Naturally, if we have no reason to favor any of the strategies, we can set all of the initial weights equally so that $w_i^1 = 1/N$. Note that the weights on future trials need not sum to one.

Our algorithm allocates among the strategies using the current weight vector, after normalizing. That is, at time t, Hedge(β) chooses the distribution vector

After the loss vector $\ell^t$ has been received, the weight vector $\mathbf{w}^t$ is updated using the multiplicative rule

More generally, it can be shown that our analysis is applicable with only minor modification to an alternative update rule of the form

where $U_\beta : [0, 1] \to [0, 1]$ is any function, parameterized by $\beta \in [0, 1]$ satisfying

for all $r \in [0, 1]$.

2.1. Analysis

The analysis of Hedge(β) mimics directly that given by Littlestone and Warmuth [20]. The main idea is to derive upper and lower bounds on $\sum_{i=1}^N w_i^{T+1}$ which, together, imply an upper bound on the loss of the algorithm. We begin with an upper bound.

Lemma 1. For any sequence of loss vectors $\ell^1, ..., \ell^T$,

Algorithm Hedge(β) Parameters: $\beta \in [0, 1]$ initial weight vector $\mathbf{w}^1 \in [0, 1]^N$ with $\sum_{i=1}^N w_i^1 = 1$ number of trials $T$ Do for $t = 1, 2, ..., T$

1. Choose allocation

1. Receive loss vector $\ell' \in [0, 1]^N$ from environment.
2. Suffer loss $\mathbf{p}' \cdot \ell'$.
3. Set the new weights vector to be

FIG. 1. The on-line allocation algorithm.

Proof. By a convexity argument, it can be shown that

for $\alpha \geq 0$ and $r \in [0, 1]$. Combined with Eqs. (1) and (2), this implies

Applying repeatedly for $t = 1, ..., T$ yields

since $1 + x \leq e^x$ for all $x$. The lemma follows immediately. □

Thus,

Note that, from Eq. (2),

This is all that is needed to complete our analysis.

THEOREM 2. For any sequence of loss vectors $\ell^1, ..., \ell^T$, and for any $i \in \{1, ..., N\}$, we have

More generally, for any nonempty set $S \subseteq \{1, ..., N\}$, we have

Proof. We prove the more general statement (8) since Eq. (7) follows in the special case that $S = \{i\}$.

From Eq. (6),

The theorem now follows immediately from Eq. (5). □

The simpler bound (7) states that Hedge($\beta$) does not perform “too much worse” than the best strategy $i$ for the sequence. The difference in loss depends on our choice of $\beta$ and on the initial weight $w_i^1$ of each strategy. If each weight is set equally so that $w_i^1 = 1/N$, then this bound becomes

Since it depends only logarithmically on $N$, this bound is reasonable even for a very large number of strategies.

The more complicated bound (8) is a generalization of the simpler bound that is especially applicable when the number of strategies is infinite. Naturally, for uncountable collections of strategies, the sum appearing in Eq. (8) can be replaced by an integral, and the maximum by a supremum.

The bound given in Eq. (9) can be written as

where $c = \ln(1/\beta)/(1 - \beta)$ and $a = 1/(1 - \beta)$. Vovk [24] analyzes prediction algorithms that have performance bounds of this form, and proves tight upper and lower bounds for the achievable values of $c$ and $a$. Using Vovk’s results, we can show that the constants $a$ and $c$ achieved by Hedge($\beta$) are optimal.

THEOREM 3. Let $B$ be an algorithm for the on-line allocation problem with an arbitrary number of strategies. Suppose that there exists positive real numbers $a$ and $c$ such that for any number of strategies $N$ and for any sequence of loss vectors $\ell^1, ..., \ell^T$

Then for all $\beta \in (0, 1)$, either

The proof is given in the appendix.

2.2. How to Choose $\beta$

So far, we have analyzed Hedge($\beta$) for a given choice of $\beta$, and we have proved reasonable bounds for any choice of $\beta$. In practice, we will often want to choose $\beta$ so as to maximally exploit any prior knowledge we may have about the specific problem at hand.

The following lemma will be helpful for choosing $\beta$ using the bounds derived above.

LEMMA 4. Suppose $0 \leq L \leq \tilde{L}$ and $0 < R \leq \tilde{R}$. Let $\beta = g(\tilde{L}/\tilde{R})$ where $g(z) = 1/(1 + \sqrt{2/z})$. Then

Proof. (Sketch) It can be shown that $-\ln \beta \leq (1 - \beta^2)/(2\beta)$ for $\beta \in (0, 1]$. Applying this approximation and the given choice of $\beta$ yields the result. □

Lemma 4 can be applied to any of the bounds above since all of these bounds have the form given in the lemma. For example, suppose we have $N$ strategies, and we also know a prior bound $\tilde{L}$ on the loss of the best strategy. Then, combining Eq. (9) and Lemma 4, we have

for $\beta = g(\tilde{L}/\ln N)$. In general, if we know ahead of time the number of trials $T$, then we can use $\tilde{L} = T$ as an upper bound on the cumulative loss of each strategy $i$.

Dividing both sides of Eq. (11) by $T$, we obtain an explicit bound on the rate at which the average per-trial loss of Hedge($\beta$) approaches the average loss for the best strategy:

Since $\tilde{L} \leq T$, this gives a worst case rate of convergence of $O(\sqrt{(\ln N)/T})$. However, if $\tilde{L}$ is close to zero, then the rate of convergence will be much faster, roughly, $O((\ln N)/T)$.

Lemma 4 can also be applied to the other bounds given in Theorem 2 to obtain analogous results.

The bound given in Eq. (11) can be improved in special cases in which the loss is a function of a prediction and an outcome and this function is of a special form (see Example 4 below). However, for the general case, one cannot improve the square-root term $\sqrt{2\tilde{L} \ln N}$, by more than a constant factor. This is a corollary of the lower bound given by Cesa-Bianchi et al. ([4], Theorem 7) who analyze an on-line prediction problem that can be seen as a special case of the on-line allocation model.

3 APPLICATIONS

The framework described up to this point is quite general and can be applied in a wide variety of learning problems.

Consider the following set-up used by Chung [5]. We are given a decision space $\Delta$, a space of outcomes $\Omega$, and a bounded loss function $\lambda : \Delta \times \Omega \to [0, 1]$. (Actually, our results require only that $\lambda$ be bounded, but, by rescaling, we can assume that its range is $[0, 1]$.) At every time step $t$, the learning algorithm selects a decision $\delta^t \in \Delta$, receives an outcome $\omega^t \in \Omega$, and suffers loss $\lambda(\delta^t, \omega^t)$. More generally, we may allow the learner to select a distribution $\mathcal{D}^t$ over the space of decisions, in which case it suffers the expected loss of a decision randomly selected according to $\mathcal{D}^t$; that is, its expected loss is $\Lambda(\mathcal{D}^t, \omega^t)$ where

To decide on distribution $\mathcal{D}^t$, we assume that the learner has access to a set of $N$ experts. At every time step $t$, expert $i$ produces its own distribution $\mathcal{E}_i^{t}$ on $\Delta$, and suffers loss $\Lambda(\mathcal{E}_i^{t}, \omega^t)$.

The goal of the learner is to combine the distributions produced by the experts so as to suffer expected loss “not much worse” than that of the best expert.

The results of Section 2 provide a method for solving this problem. Specifically, we run algorithm Hedge($\beta$), treating each expert as a strategy. At every time step, Hedge($\beta$) produces a distribution $p^t$ on the set of experts which is used to construct the mixture distribution

For any outcome $\omega^t$, the loss suffered by Hedge($\beta$) will then be

Thus, if we define $\ell_i^t = \Lambda(\mathcal{E}_i^t, \omega^t)$ then the loss suffered by the learner is $p^t \cdot \ell^t$, i.e., exactly the mixture loss that was analyzed in Section 2.

Hence, the bounds of Section 2 can be applied to our current framework. For instance, applying Eq. (11), we obtain the following:

Theorem 5. For any loss function $\lambda$, for any set of experts, and for any sequence of outcomes, the expected loss of Hedge($\beta$) if used as described above is at most

where $\tilde{L} \leq T$ is an assumed bound on the expected loss of the best expert, and $\beta = g(\tilde{L}/\ln N)$.

Example 1. In the $k$-ary prediction problem, $\Delta = \Omega = \{1, 2, ..., k\}$, and $\lambda(\delta, \omega)$ is 1 if $\delta \neq \omega$ and 0 otherwise. In other words, the problem is to predict a sequence of letters over an alphabet of size $k$. The loss function $\lambda$ is 1 if a mistake was made, and 0 otherwise. Thus, $\Lambda(\mathcal{D}, \omega)$ is the probability (with respect to $\mathcal{D}$) of a prediction that disagrees with $\omega$. The cumulative loss of the learner, or of any expert, is therefore the expected number of mistakes on the entire sequence. So, in this case, Theorem 2 states that the expected number of mistakes of the learning algorithm will exceed the expected number of mistakes of the best expert by at most $O(\sqrt{T \ln N})$, or possibly much less if the loss of the best expert can be bounded ahead of time.

Bounds of this type were previously proved in the binary case ($k = 2$) by Littlestone and Warmuth [20] using the same algorithm. Their algorithm was later improved by Vovk [25] and Cesa-Bianchi et al. [4]. The main result of this section is a proof that such bounds can be shown to hold for any bounded loss function.

Example 2. The loss function $\lambda$ may represent an arbitrary matrix game, such as “rock, paper, scissors.” Here, $\Delta = \Omega = \{R, P, S\}$, and the loss function is defined by the matrix:

The decision $\delta$ represents the learner’s play, and the outcome $\omega$ is the adversary’s play; then $\lambda(\delta, \omega)$, the learner’s loss, is 1 if the learner loses the round, 0 if it wins the round, and 1/2 if the round is tied. (For instance, $\lambda(S, P) = 0$ since “scissors cut paper.”) So the cumulative loss of the learner

(or an expert) is the expected number of losses in a series of rounds of game play (counting ties as half a loss). Our results show then that, in repeated play, the expected number of rounds lost by our algorithm will converge quickly to the expected number that would have been lost by the best of the experts (for the particular sequence of moves that were actually played by the adversary).

Example 3. Suppose that $\Delta$ and $\Omega$ are finite, and that $\lambda$ represents a game matrix as in the last example. Suppose further that we create one expert for each decision $\delta \in \Delta$ and that expert always recommends playing $\delta$. In game-theoretic terminology such experts would be identified with pure strategies. Von Neumann’s classical min-max theorem states that for any fixed game matrix there exists a distribution over the actions, also called a mixed strategy, which achieves the min-max optimal value of the expected loss against any adversarial strategy. This min-max value is also called the value of the game.

Suppose that we use algorithm Hedge($\beta$) to choose distributions over the actions when playing a matrix game repeatedly. In this case, Theorem 2 implies that the gap between the learner’s average per-round loss can never be much larger than that of the best pure strategy, and that the maximal gap decreases to zero at the rate $O(1/\sqrt{T \log |\Delta|})$. However, the expected loss of the optimal mixed strategy is a fixed convex combination of the losses of the pure strategies, thus it can never be smaller than the loss of the best pure strategy for a particular sequence of events. We conclude that the expected per-trial loss of Hedge($\beta$) is upper bounded by the value of the game plus $O(1/\sqrt{T \log |\Delta|})$. In other words, the algorithm can never perform much worse that an algorithm that uses the optimal mixed strategy for the game, and it can be better if the adversary does not play optimally. Moreover, this holds true even if the learner knows nothing at all about the game that is being played (so that $\lambda$ is unknown to the learner), and even if the adversarial opponent has complete knowledge both of the game that is being played and the algorithm that is being used by the learner. Algorithms with similar properties (but weaker convergence bounds) were first devised by Blackwell [2] and Hannan [14]. For more details see our related paper [13].

Example 4. Suppose that $\Delta = \Omega$ is the unit ball in $\mathbb{R}^n$, and that $\lambda(\delta, \omega) = \| \delta - \omega \|$. Thus, the problem here is to predict the location of a point $\omega$, and the loss suffered is the Euclidean distance between the predicted point $\delta$ and the actual outcome $\omega$. Theorem 2 can be applied if probabilistic predictions are allowed. However, in this setting it is more natural to require that the learner and each expert predict a single point (rather than a measure on the space of possible points). Essentially, this is the problem of “tracking” a sequence of points $\omega^1, ..., \omega^T$ where the loss function measures the distance to the predicted point.

To see how to handle the problem of finding deterministic predictions, notice that the loss function $\lambda(\delta, \omega)$ is convex with respect to $\delta$:

for any $a \in [0, 1]$ and any $\omega \in \Omega$. Thus we can do as follows. At time $t$, the learner predicts with the weighted average of the experts’ predictions: $\delta^t = \sum_{i=1}^N p_i^t \varepsilon_i^t$ where $\varepsilon_i^t \in \mathbb{R}^n$ is the prediction of the $i$th expert at time $t$. Regardless of the outcome $\omega^t$, Eq. (13) implies that

Since Theorem 2 provides an upper bound on the right hand side of this inequality, we also obtain upper bounds for the left hand side. Thus, our results in this case give explicit bounds on the total error (i.e., distance between predicted and observed points) for the learner relative to the best of a team of experts.

In the one-dimensional case ($n = 1$), this case was previously analyzed by Littlestone and Warmuth [20], and later improved upon by Kivinen and Warmuth [19].

This result depends only on the convexity and the bounded range of the loss function $\lambda(\delta, \omega)$ with respect to $\delta$. Thus, it can also be applied, for example, to the squared-distance loss function $\lambda(\delta, \omega) = \| \delta - \omega \|^2$, as well as the log loss function $\lambda(\delta, \omega) = -\ln(\delta \cdot \omega)$ used by Cover [6] for the design of “universal” investment portfolios. (In this last case, $\Delta$ is the set of probability vectors on $n$ points, and $\Omega = [1/B, B]^n$ for some constant $B > 1$.)

In many of the cases listed above, superior algorithms or analyses are known. Although weaker in specific cases, it should be emphasized that our results are far more general, and can be applied in settings that exhibit considerably less structure, such as the horse-racing example described in the introduction.

4 BOOSTING

In this section we show how the algorithm presented in Section 2 for the on-line allocation problem can be modified to boost the performance of weak learning algorithms.

We very briefly review the PAC learning model (see, for instance, Kearns and Vazirani [18] for a more detailed description). Let $X$ be a set called the domain. A concept is a Boolean function $c : X \to \{0, 1\}$. A concept class $\mathcal{C}$ is a collection of concepts. The learner has access to an oracle which provides labelled examples of the form $(x, c(x))$ where $x$ is chosen randomly according to some fixed but unknown and arbitrary distribution $\mathcal{D}$ on the domain $X$, and $c \in \mathcal{C}$ is the target concept. After some amount of time, the learner must output a hypothesis $h : X \to [0, 1]$. The value $h(x)$ can be interpreted as a randomized prediction of the label of $x$ that is 1 with probability $h(x)$ and 0 with probability $1 - h(x)$. (Although we assume here that we have direct access to the bias of this prediction, our results can be extended to the case that $h$ is instead a random mapping into $\{0, 1\}$.) The error of the hypothesis $h$ is the expected value $E_{x \sim \mathcal{D}}(|h(x) - c(x)|)$ where $x$ is chosen according to $\mathcal{D}$. If $h(x)$ is interpreted as a stochastic prediction, then this is simply the probability of an incorrect prediction.

A strong PAC-learning algorithm is an algorithm that, given $\varepsilon, \delta > 0$ and access to random examples, outputs with probability $1 - \delta$ a hypothesis with error at most $\varepsilon$. Further, the running time must be polynomial in $1/\varepsilon, 1/\delta$ and other relevant parameters (namely, the “size” of the examples received, and the “size” or “complexity” of the target concept). A weak PAC-learning algorithm satisfies the same conditions but only for $\varepsilon \geq 1/2 - \gamma$ where $\gamma > 0$ is either a constant, or decreases as $1/p$ where $p$ is a polynomial in the relevant parameters. We use WeakLearn to denote a generic weak learning algorithm.

Schapire [22] showed that any weak learning algorithm can be efficiently transformed or “boosted” into a strong learning algorithm. Later, Freund [10, 11] presented the “boost-by-majority” algorithm that is considerably more efficient than Schapire’s. Both algorithms work by calling a given weak learning algorithm WeakLearn multiple times, each time presenting it with a different distribution over the domain $X$, and finally combining all of the generated hypotheses into a single hypothesis. The intuitive idea is to alter the distribution over the domain $X$ in a way that increases the probability of the “harder” parts of the space, thus forcing the weak learner to generate new hypotheses that make less mistakes on these parts.

An important, practical deficiency of the boost-by-majority algorithm is the requirement that the bias $\gamma$ of the weak learning algorithm WeakLearn be known ahead of time. Not only is this worst-case bias usually unknown in practice, but the bias that can be achieved by WeakLearn will typically vary considerably from one distribution to the next. Unfortunately, the boost-by-majority algorithm cannot take advantage of hypotheses computed by WeakLearn with error significantly smaller than the presumed worst-case bias of $1/2 - \gamma$.

In this section, we present a new boosting algorithm which was derived from the on-line allocation algorithm of Section 2. This new algorithm is very nearly as efficient as boost-by-majority. However, unlike boost-by-majority, the accuracy of the final hypothesis produced by the new algorithm depends on the accuracy of all the hypotheses returned by WeakLearn, and so is able to more fully exploit the power of the weak learning algorithm.

Also, this new algorithm gives a clean method for handling real-valued hypotheses which often are produced by neural networks and other learning algorithms.

4.1. The New Boosting Algorithm

Although boosting has its roots in the PAC model, for the remainder of the paper, we adopt a more general learning framework in which the learner receives examples $(x_i, y_i)$ chosen randomly according to some fixed but unknown distribution $\mathcal{P}$ on $X \times Y$, where $Y$ is a set of possible labels. As usual, the goal is to learn to predict the label $y$ given an instance $x$.

We start by describing our new boosting algorithm in the simplest case that the label set $Y$ consists of just two possible labels, $Y = \{0, 1\}$. In later sections, we give extensions of the algorithm for more general label sets.

Freund [11] describes two frameworks in which boosting can be applied: boosting by filtering and boosting by sampling. In this paper, we use the boosting by sampling framework, which is the natural framework for analyzing “batch” learning, i.e., learning using a fixed training set which is stored in the computer’s memory.

We assume that a sequence of $N$ training examples (labelled instances) $(x_1, y_1), ..., (x_N, y_N)$ is drawn randomly from $X \times Y$ according to distribution $\mathcal{P}$. We use boosting to find a hypothesis $h_f$ which is consistent with most of the sample (i.e., $h_f(x_i) = y_i$ for most $1 \leq i \leq N$). In general, a hypothesis which is accurate on the training set might not be accurate on examples outside the training set; this problem is sometimes referred to as “over-fitting.” Often, however, overfitting can be avoided by restricting the hypothesis to be simple. We will come back to this problem in Section 4.3.

The new boosting algorithm is described in Fig. 2. The goal of the algorithm is to find a final hypothesis with low error relative to a given distribution $D$ over the training examples. Unlike the distribution $\mathcal{P}$ which is over $X \times Y$ and is set by “nature,” the distribution $D$ is only over the instances in the training set and is controlled by the learner. Ordinarily, this distribution will be set to be uniform so that $D(i) = 1/N$. The algorithm maintains a set of weights $w^t$ over the training examples. On iteration $t$ a distribution $p^t$ is computed by normalizing these weights. This distribution is fed to the weak learner WeakLearn which generates a hypothesis $h_t$ that (we hope) has small error with respect to the distribution.\footnote{Some learning algorithms can be generalized to use a given distribution directly. For instance, gradient based algorithms can use the probability associated with each example to scale the update step size which is based on the example. If the algorithm cannot be generalized in this way, the training sample can be re-sampled to generate a new set of training examples that is distributed according to the given distribution. The computation required to generate each re-sampled example takes $O(\log N)$ time.} Using the new hypothesis $h_t$, the boosting

Algorithm AdaBoost Input: sequence of N labeled examples $\langle (x_1, y_1), ..., (x_N, y_N) \rangle$ distribution D over the N examples weak learning algorithm WeakLearn integer T specifying number of iterations Initialize the weight vector: $w_i^1 = D(i)$ for $i = 1, ..., N$. Do for $t = 1, 2, ..., T$

1. Set

1. Call WeakLearn, providing it with the distribution $\mathbf{p}'$; get back a hypothesis $h_t : X \to [0, 1]$.

1. Calculate the error of $h_t$: $\varepsilon_t = \sum_{i=1}^N p_i' |h_t(x_i) - y_i|$.

1. Set $\beta_t = \varepsilon_t / (1 - \varepsilon_t)$.

5 Set the new weights vector to be

Output the hypothesis

FIG. 2. The adaptive boosting algorithm.

algorithm generates the next weight vector $\mathbf{w}^{t+1}$, and the process repeats. After T such iterations, the final hypothesis $h_f$ is output. The hypothesis $h_f$ combines the outputs of the T weak hypotheses using a weighted majority vote.

We call the algorithm AdaBoost because, unlike previous algorithms, it adjusts adaptively to the errors of the weak hypotheses returned by WeakLearn. If WeakLearn is a PAC weak learning algorithm in the sense defined above, then $\varepsilon_t \leq 1/2 - \gamma$ for all $t$ (assuming the examples have been generated appropriately with $y_i = c(x_i)$ for some $c \in \mathcal{C}$). However, such a bound on the error need not be known ahead of time. Our results hold for any $\varepsilon_t \in [0, 1]$, and depend only on the performance of the weak learner on those distributions that are actually generated during the boosting process.

The parameter $\beta_t$ is chosen as a function of $\varepsilon_t$ and is used for updating the weight vector. The update rule reduces the probability assigned to those examples on which the hypothesis makes a good prediction and increases the probability of the examples on which the prediction is poor.$^2$

Note that AdaBoost, unlike boost-by-majority, combines the weak hypotheses by summing their probabilistic predictions. Drucker, Schapire and Simard [9], in experiments they performed using boosting to improve the performance of a real-valued neural network, observed that summing the outcomes of the networks and then selecting the best prediction performs better than selecting the best prediction of each network and then combining them with a majority rule. It is interesting that the new boosting algorithm’s final hypothesis uses the same combination rule that was observed to be better in practice, but which previously lacked theoretical justification.

Since it was first introduced, several successful experiments have been conducted using AdaBoost, including work by the authors [12], Drucker and Cortes [8], Jackson and Craven [16], Quinlan [21], and Breiman [3].

4.2. Analysis

Comparing Figs. 1 and 2, there is an obvious similarity between the algorithms Hedge($\beta$) and AdaBoost. This similarity reflects a surprising “dual” relationship between the on-line allocation model and the problem of boosting. Put another way, there is a direct mapping or reduction of the boosting problem to the on-line allocation problem. In such a reduction, one might naturally expect a correspondence relating the strategies to the weak hypotheses and the trials (and associated loss vectors) to the examples in the training set. However, the reduction we have used is reversed: the “strategies” correspond to the examples, and the trials are associated with the weak hypotheses. Another reversal is in the definition of the loss: in Hedge($\beta$) the loss $\ell_i^t$ is small if the ith strategy suggests a good action on the tth trial while in AdaBoost the “loss” $\ell_i^t = 1 - |h_t(x_i) - y_i|$ appearing in the weight-update rule (Step 5) is small if the tth hypothesis suggests a bad prediction on the ith example. The reason is that in Hedge($\beta$) the weight associated with a strategy is increased if the strategy is successful while in AdaBoost the weight associated with an example is increased if the example is “hard.”

The main technical difference between the two algorithms is that in AdaBoost the parameter $\beta$ is no longer fixed ahead of time but rather changes at each iteration according to $\varepsilon_t$. If we are given ahead of time the information that $\varepsilon_t \leq 1/2 - \gamma$ for some $\gamma > 0$ and for all $t = 1, ..., T$, then we could instead directly apply algorithm Hedge($\beta$) and its analysis as follows: Fix $\beta$ to be $1 - \gamma$, and set $\ell_i^t = 1 - |h_t(x_i) - y_i|$, and $h_f$ as in AdaBoost, but with equal weight assigned to all T hypotheses. Then $\mathbf{p}' \cdot \ell^t$ is exactly the accuracy of $h_t$ on distribution $\mathbf{p}'$, which, by assumption, is at least $1/2 + \gamma$. Also, letting $S = \{ i : h_f(x_i) \neq y_i \}$, it is straightforward to show that if $i \in S$ then

$^2$ Furthermore, if $h_t$ is Boolean (with range $\{0, 1\}$), then it can be shown that this update rule exactly removes the advantage of the last hypothesis. That is, the error of $h_t$ on distribution $\mathbf{p}'^{t+1}$ is exactly 1/2.

by $h_f$'s definition, and since $y_i \in \{0, 1\}$. Thus, by Theorem 2,

since $-\ln(\beta) = -\ln(1-\gamma) \leq \gamma + \gamma^2$ for $\gamma \in [0, 1/2]$. This implies that the error $\varepsilon = \sum_{i \in S} D(i)$ of $h_f$ is at most $e^{-T\gamma^2/2}$.

The boosting algorithm AdaBoost has two advantages over this direct application of Hedge($\beta$). First, by giving a more refined analysis and choice of $\beta$, we obtain a significantly superior bound on the error $\varepsilon$. Second, the algorithm does not require prior knowledge of the accuracy of the hypotheses that WeakLearn will generate. Instead, it measures the accuracy of $h_t$ at each iteration and sets its parameters accordingly. The update factor $\beta_t$ decreases with $\varepsilon_t$ which causes the difference between the distributions $p^t$ and $p^{t+1}$ to increase. Decreasing $\beta_t$ also increases the weight $\ln(1/\beta_t)$ which is associated with $h_t$ in the final hypothesis. This makes intuitive sense: more accurate hypotheses cause larger changes in the generated distributions and have more influence on the outcome of the final hypothesis.

We now give our analysis of the performance of AdaBoost. Note that this theorem applies also if, for some hypotheses, $\varepsilon_t \geq 1/2$.

Theorem 6. Suppose the weak learning algorithm WeakLearn, when called by AdaBoost, generates hypotheses with errors $\varepsilon_1, ..., \varepsilon_T$ (as defined in Step 3 of Fig. 2.) Then the error $\varepsilon = \Pr_{i \sim D}[h_f(x_i) \neq y_i]$ of the final hypothesis $h_f$ output by AdaBoost is bounded above by

Proof. We adapt the main arguments from Lemma 1 and Theorem 2. We use $p^t$ and $w^t$ as they are defined in Fig. 2.

Similar to Eq. (4), the update rule given in Step 5 in Fig. 2 implies that

Combining this inequality over $t = 1, ..., T$, we get that

The final hypothesis $h_f$, as defined in Fig. 2, makes a mistake on instance $i$ only if

(since $y_i \in \{0, 1\}$). The final weight of any instance $i$ is

Combining Eqs. (17) and (18) we can lower bound the sum of the final weights by the sum of the final weights of the examples on which $h_f$ is incorrect:

where $\varepsilon$ is the error of $h_f$. Combining Eqs. (16) and (19), we get that

As all the factors in the product are positive, we can minimize the right hand side by minimizing each factor separately. Setting the derivative of the $t$th factor to zero, we find that the choice of $\beta_t$ which minimizes the right hand side is $\beta_t = \varepsilon_t/(1-\varepsilon_t)$. Plugging this choice of $\beta_t$ into Eq. (20) we get Eq. (14), completing the proof. $\blacksquare$

The bound on the error given in Theorem 6, can also be written in the form

where $\mathrm{KL}(a \parallel b) = a \ln(a/b) + (1-a) \ln((1-a)/(1-b))$ is the Kullback–Leibler divergence, and where $\varepsilon_t$ has been replaced by $1/2 - \gamma_t$. In the case where the errors of all the hypotheses are equal to $1/2 - \gamma$, Eq. (21) simplifies to

This is a form of the Chernoff bound for the probability that less than $T/2$ coin flips turn out “heads” in $T$ tosses of a random coin whose probability for “heads” is $1/2 - \gamma$. This bound has the same asymptotic behavior as the bound given for the boost-by-majority algorithm [11]. From Eq. (22) we get that the number of iterations of the boosting algorithm that is sufficient to achieve error $\varepsilon$ of $h_f$ is

Note, however, that when the errors of the hypotheses generated by WeakLearn are not uniform, Theorem 6 implies that the final error depends on the error of all of the weak hypotheses. Previous bounds on the errors of boosting algorithms depended only on the maximal error of the weakest hypothesis and ignored the advantage that can be gained from the hypotheses whose errors are smaller. This advantage seems to be very relevant to practical applications of boosting, because there one expects the error of the learning algorithm to increase as the distributions fed to WeakLearn shift more and more away from the target distribution.

4.3. Generalization Error

We now come back to discussing the error of the final hypothesis outside the training set. Theorem 6 guarantees that the error of $h_f$ on the sample is small; however, the quantity that interests us is the generalization error of $h_f$, which is the error of $h_f$ over the whole instance space $X$; that is, $\varepsilon_g = \Pr_{(x, y) \sim \mathcal{P}}[h_f(x) \neq y]$. In order to make $\varepsilon_g$ close to the empirical error $\hat{\varepsilon}$ on the training set, we have to restrict the choice of $h_f$ in some way. One natural way of doing this in the context of boosting is to restrict the weak learner to choose its hypotheses from some simple class of functions and restrict $T$, the number of weak hypotheses that are combined to make $h_f$. The choice of the class of weak hypotheses is specific to the learning problem at hand and should reflect our knowledge about the properties of the unknown concept. As for the choice of $T$, various general methods can be devised. One popular method is to use an upper bound on the VC-dimension of the concept class. This method is sometimes called “structural risk minimization.” See Vapnik’s book [23] for an extensive discussion of the theory of structural risk minimization. For our purposes, we quote Vapnik’s Theorem 6.7:

Theorem 7 (Vapnik). Let $H$ be a class of binary functions over some domain $X$. Let $d$ be the VC-dimension of $H$. Let $\mathcal{P}$ be a distribution over the pairs $X \times \{0, 1\}$. For $h \in H$, define the (generalization) error of $h$ with respect to $\mathcal{P}$ to be

Let $S = \{(x_1, y_1), ..., (x_N, y_N)\}$ be a sample (training set) of $N$ independent random examples drawn from $X \times \{0, 1\}$ according to $\mathcal{P}$. Define the empirical error of $h$ with respect to the sample $S$ to be

Then, for any $\delta > 0$ we have that

where the probability is computed with respect to the random choice of the sample $S$.

Let $\theta : \mathbb{R} \to \{0, 1\}$ be defined by

and, for any class $H$ of functions, let $\Theta_T(H)$ be the class of all functions defined as a linear threshold of $T$ functions in $H$:

Clearly, if all hypotheses generated by WeakLearn belong to some class $H$, then the final hypothesis of AdaBoost, after $T$ rounds of boosting, belongs to $\Theta_T(H)$. Thus, the next theorem provides an upper bound on the VC-dimension of the class of final hypotheses generated by AdaBoost in terms of the weak hypothesis class.

THEOREM 8. *Let H be a class of binary functions of VC-dimension d \geq 2. Then the VC-dimension of $\Theta_T(H)$ is at most $2(d+1)(T+1)\log_2(e(T+1))$ (where e is the base of the natural logarithm).

Therefore, if the hypotheses generated by WeakLearn are chosen from a class of VC-dimension $d \geq 2$, then the final hypotheses generated by AdaBoost after T iterations belong to a class of VC-dimension at most $2(d+1)(T+1)\log_2[e(T+1)]$.

Proof. We use a result about the VC-dimension of computation networks proved by Baum and Haussler [1]. We can view the final hypothesis output by AdaBoost as a function that is computed by a two-layer feed-forward network where the computation units of the first layer are the weak hypotheses and the computation unit of the second layer is the linear threshold function which combines the weak hypotheses. The VC-dimension of the set of linear threshold functions over $\mathbb{R}^T$ is $T+1$ [26]. Thus the sum over all computation units of the VC-dimensions of the classes of functions associated with each unit is $Td + (T+1) < (T+1)(d+1)$. Baum and Haussler’s Theorem 1 [1] implies that the number of different functions that can be realized by $h \in \Theta_T(H)$ when the domain is restricted to a set of size m is at most $((T+1)\ em/(T+1)(d+1))^{(T+1)(d+1)}$. If $d \geq 2$, $T \geq 1$ and we set $m = \lceil 2(T+1)(d+1)\log_2[e(T+1)] \rceil$, then the number of realizable functions is smaller than $2^m$ which implies that the VC-dimension of $\Theta_T(H)$ is smaller than m. $\blacksquare$

Following the guidelines of structural risk minimization we can do the following (assuming we know a reasonable upper bound on the VC-dimension of the class of weak hypotheses). Let $h_f^T$ be the hypothesis generated by running AdaBoost for T iterations. By combining the observed empirical error of $h_f^T$ with the bounds given in Theorems 7 and 8, we can compute an upper bound on the generalization error of $h_f^T$ for all T. We would then select the hypothesis $h_f^T$ that minimizes the guaranteed upper bound.

While structural risk minimization is a mathematically sound method, the upper bounds on $\varepsilon_g$ that are generated in this way might be larger than the actual value and so the chosen number of iterations T might be much smaller than the optimal value, leading to inferior performance. A simple alternative is to use “cross-validation” in which a fraction of the training set is left outside the set used to generate $h_f$ as the so-called “validation” set. The value of T is then chosen to be the one for which the error of the final hypothesis on the validation set is minimized. (For an extensive analysis of the relations between different methods for selecting model complexity in learning, see Kearns et al. [17].)

Some initial experiments using AdaBoost on real-world problems conducted by ourselves and Drucker and Cortes [8] indicate that AdaBoost tends not to over-fit; on many problems, even after hundreds of rounds of boosting, the generalization error continues to drop, or at least does not increase.

4.4. A Bayesian Interpretation

The final hypothesis generated by AdaBoost is closely related to one suggested by a Bayesian analysis. As usual, we assume that examples $(x, y)$ are being generated according to some distribution $\mathcal{P}$ on $X \times \{0, 1\}$; all probabilities in this subsection are taken with respect to $\mathcal{P}$. Suppose we are given a set of $\{0, 1\}$-valued hypotheses $h_1, ..., h_T$ and that our goal is to combine the predictions of these hypotheses in the optimal way. Then, given an instance $x$ and the hypothesis predictions $h_t(x)$, the Bayes optimal decision rule says that we should predict the label with the highest likelihood, given the hypothesis values, i.e., we should predict 1 if

and otherwise we should predict 0.

This rule is especially easy to compute if we assume that the errors of the different hypotheses are independent of one another and of the target concept, that is, if we assume that the event $h_t(x) \neq y$ is conditionally independent of the actual label $y$ and the predictions of all the other hypotheses $h_1(x), ..., h_{t-1}(x), h_{t+1}(x), ..., h_T(x)$. In this case, by applying Bayes rule, we can rewrite the Bayes optimal decision rule in a particularly simple form in which we predict 1 if