Adaptive Martingale Boosting

Philip M. Long
Googleplong@google.com

Rocco A. Servedio
Columbia University
rocco@cs.columbia.edu

Abstract
In recent work Long and Servedio [LS05] presented a “martingale boosting” algorithm that works by constructing a branching program over weak classifiers andhas a simple analysis based on elementary properties of random walks. [LS05]
showed that this martingale booster can tolerate random classification noise when
it is run with a noise-tolerant weak learner; however, a drawback of the algorithm
is that it is not adaptive, i.e. it cannot effectively take advantage of variation in thequality of the weak classifiers it receives.
We present an adaptive variant of the martingale boosting algorithm. This adaptiveness is achieved by modifying the original algorithm so that the random walks
that arise in its analysis have different step size depending on the quality of the
weak learner at each stage. The new algorithm inherits the desirable properties ofthe original [LS05] algorithm, such as random classification noise tolerance, andhas other advantages besides adaptiveness: it requires polynomially fewer calls to
the weak learner than the original algorithm, and it can be used with confidencerated weak hypotheses that output real values rather than Boolean predictions.

1 Introduction
Boosting algorithms are efficient procedures that can be used to convert a weak learning algorithm(one which outputs a weak hypothesis that performs only slightly better than random guessing fora binary classification task) into a strong learning algorithm (one which outputs a high-accuracy
classifier). A rich theory of boosting has been developed over the past two decades; see [Sch03,
MR03] for some overviews. Two important issues for boosting algorithms which are relevant to thecurrent work are adaptiveness and noise-tolerance; we briefly discuss each of these issues before
describing the contributions of this paper.
Adaptiveness. “Adaptiveness” refers to the ability of boosting algorithms to adjust to different
accuracy levels in the sequence of weak hypotheses that they are given. The first generation of
boosting algorithms [Sch90, Fre95] required the user to input an “advantage” parameter γ such thatthe weak learner was guaranteed to always output a weak hypothesis with accuracy at least 1/2 + γ.
Given an initial setting of γ, even if the sequence of weak classifiers generated by the runs of the
weak learner included some hypotheses with accuracy (perhaps significantly) better than 1/2+γ, theearly boosting algorithms were unable to capitalize on this extra accuracy; thus, these early boosters
were not adaptive. Adaptiveness is an important property since it is often the case that the advantage
of successive weak classifiers grows smaller and smaller as boosting proceeds.
A major step forward was the development of the AdaBoost algorithm [FS97]. AdaBoost does
not require a lower bound γ on the minimum advantage, and the error rate of its final hypothesis
depends favorably on the different advantages of the different weak classifiers in the sequence. Moreprecisely, if the accuracy of the t-th weak classifier is 21 + γt , then the AdaBoost final hypothesishas error at mostQT −1 p1 − 4γt2 . This error rate is usually upper bounded (see [FS97]) by
t=0
!
T
−1
X
2
exp −2
γt

(1)

t=0

and indeed (1) is a good approximation if no γt is too large.

Noise tolerance. One drawback of many standard boosting techniques, including AdaBoost, is thatthey can perform poorly when run on noisy data [FS96, MO97, Die00, LS08]. Motivated in part by
this observation, in recent years boosting algorithms that work by constructing branching programs
over the weak classifiers (note that this is in contrast with AdaBoost, which constructs a single
weighted sum of weak classifiers) have been developed and shown to enjoy some provable noise
tolerance. In particular, the algorithms of [KS05, LS05] have been shown to boost to optimally highaccuracy in the presence of random classification noise when run with a random classification noise
tolerant weak learner. (Recall that “random classification noise at rate η” means that the true binary
label of each example is independently flipped with probability η. This is a very well studied noisemodel, see e.g. [AL88, Kea98, AD98, BKW03, KS05, RDM06] and many other references.)
While the noise tolerance of the boosters [KS05, LS05] is an attractive feature, a drawback of thesealgorithms is that they do not enjoy the adaptiveness of algorithms like AdaBoost. The MMM
booster of [KS05] is not known to have any adaptiveness at all, and the “martingale boosting”
algorithm of [LS05] only has the following limited type of adaptiveness. The algorithm works instages t = 0, 1, . . . where in the t-th stage a collection of t + 1 weak hypotheses are obtained; let γtdenote the minimum advantage of these t + 1 hypotheses obtained in stage t. [LS05] shows that the
final hypothesis constructed by martingale boosting has error at most!
PT −1
( t=0 γt )2
exp −
.
(2)
2T
(2) is easily seen to always be a worse bound than (1), and the difference can be substantial. Consider,for example, a sequence of weak classifiers in which the advantages decrease as√
γt = 1/ t + 1 (this is in line with the oft-occurring situation, mentioned above, that advantages
grow smaller and √smaller as boosting progresses). For any ǫ > 0 we can bound (1) from above by ǫ
by taking T ≈ 1/ ǫ, whereas for this sequence of advantages the error bound (2) is never less than
0.5 (which is trivial), and in fact (2) approaches 1 as t → ∞.
Our contributions: adaptive noise-tolerant boosting.
give the first boosting algorithm thatWe
PT −1 2 and is provably tolerant tois both adaptive enough to satisfy a bound of exp −Ω
t=0 γtrandom classification noise. We do this by modifying the martingale boosting algorithm of [LS05]
to make it adaptive; the modification inherits the noise-tolerance of the original [LS05] algorithm. In
addition to its adaptiveness, the new algorithm also improves on [LS05] by constructing a branching
program with polynomially fewer nodes than the original martingale boosting algorithm (thus itrequires fewer calls to the weak learner), and it can be used directly with weak learners that generateconfidence-rated weak hypotheses (the original martingale boosting algorithm required the weak
hypotheses to be Boolean-valued).
Our approach. We briefly sketch the new idea that lets us achieve adaptiveness. Recall that theoriginal martingale booster of Long and Servedio formulates the boosting process as a random walk;
intuitively, as a random example progresses down through the levels of the branching program constructed by the [LS05] booster, it can be viewed as performing a simple random walk with step size 1
on the real line, where the walk is biased in the direction (positive or negative) corresponding to thecorrect classification of the example. (The quantity tracked during the random walk is the difference
between the number of positive predictions and the number of negative predictions made by baseclassifiers encountered in the braching program up to a given point in time.) This means that after
enough stages, a random positive example will end up to the right of the origin with high probability,
and contrariwise for a random negative example. Thus a high-accuracy classifier is obtained simply
by labelling each example according to the sign (+ or −) of its final location on the real line.
The new algorithm extends this approach in a simple and intuitive way, by having examples performa random walk with variable step size: if the weak classifier at a given internal node has large

advantage, then the new algorithm makes the examples that reach that node take a large step inthe random walk. This is a natural way to exploit the fact that examples reaching such a largeadvantage node usually tend to walk in the right direction. The idea extends straightforwardly to
let us handle confidence-rated weak hypotheses (see [SS99]) whose predictions are real values in[−1, 1] as opposed to Boolean values from {−1, 1}. This is done simply by scaling the step size for agiven example x from a given node according to the numerical value h(x) that the confidence-rated
weak hypothesis h at that node assigns to example x.
While using different step sizes at different levels is a natural idea, it introduces some complications.
In particular, if a branching program is constructed naively based on this approach, it is possible forthe number of nodes to increase exponentially with the depth. To avoid this, we use a randomized
rounding scheme together with the variable-step random walk to ensure that the number of nodes
in the branching program grows polynomially rather than exponentially in the number of stages
in the random walk (i.e. the depth of the branching program). In fact, we actually improve on
the efficiency of the original martingale boosting algorithm of [LS05] by a polynomial factor, bytruncating “extreme” nodes in the branching program that are “far” from the origin. Our analysis
shows that this truncation has only a small effect on the accuracy of the final classifier, while giving
a significant asymptotic savings in the size of the final branching program (roughly 1/γ 3 nodes as
opposed to the 1/γ 4 nodes of [KS05, LS05]).

2 Preliminaries
We make the following assumptions and notational conventions throughout the paper. There is an
initial distribution D over a domain of examples X. There is a target function c : X → {−1, 1} that
we are trying to learn. Given the target function c and the distribution D, we write D+ to denotethe distribution D restricted to the positive examples {x ∈ X : c(x) = 1}. Thus, for any event
S ⊆ {x ∈ X : c(x) = 1} we have PrD+ [x ∈ S] = PrD [x ∈ S]/PrD [c(x) = 1]. Similarly, we
write D− to denote D restricted to the negative examples {x ∈ X : c(x) = −1}.
As usual, our boosting algorithms work by repeatedly passing a distribution D′ derived from D toa weak learner, which outputs a classifier h. The future behavior will be affected by how well hperforms on data distributed according to D′ . To keep the analysis clean, we will abstract away
issues of sampling from D′ and estimating the accuracy of the resulting h. These issues are trivial
if D is uniform over a moderate-sized domain (since all probabilities can be computed exactly), andotherwise they can be handled via the same standard estimation techniques used in [LS05].

Martingale boosting. We briefly recall some key aspects of the martingale boosting algorithm of[LS05] which are shared by our algorithm (and note some differences). Both boosters work by
constructing a leveled branching program. Each node in the branching program has a location; thisis a pair (β, t) where β is a real value (a location on the line) and t ≥ 0 is an integer (the level of thenode; each level corresponds to a distinct stage of boosting). The initial node, where all examples
start, is at (0, 0). In successive stages t = 0, 1, 2, . . . the booster constructs nodes in the branching
program at levels 0, 1, 2, . . . . For a location (β, t) where the branching program has a node, letDβ,t be the distribution D conditioned on reaching the node at (β, t). We sometimes refer to this
distribution Dβ,t as the distribution induced by node (β, t).
As boosting proceeds, in stage t, each node (β, t) at level t is assigned a hypothesis which wecall hβ,t . Unlike [LS05] we shall allow confidence-rated hypotheses, so each weak hypothesis is amapping from X to [−1, 1]. Once the hypothesis hβ,t has been obtained, out-edges are constructedfrom (β, t) to its child nodes at level t + 1. While the original martingale boosting algorithm of[LS05] had two child nodes at (β − 1, t + 1) and (β + 1, t + 1) from each internal node, as we
describe in Section 3 our new algorithm will typically have four child nodes for each node (but may,for a confidence-rated base classifier, have as many as eight).
Our algorithm. To fully specify our new boosting algorithm we must describe:(1) How the weak learner is run at each node (β, t) to obtain a weak classifier. This is straightforward for the basic case of “two-sided” weak learners that we describe in Section 3 andsomewhat less straightforward in the usual (non-two-sided) weak learner setting. In Section 5.1 we describe how to use a standard weak learner, and how to handle noise – both
extensions borrow heavily from earlier work [LS05, KS05].

(2) What function is used to label the node (β, t), i.e. how to route subsequent examples thatreach (β, t) to one of the child nodes. It turns out that this function is a randomized versionof the weak classifier mentioned in point (1) above.
(3) Where to place the child nodes at level t + 1; this is closely connected with (2) above.
As in [LS05], once the branching program has been fully constructed down through some level T
the final hypothesis it computes is very simple. Given an input example x, the output of the final
hypothesis on x is sgn(β) where (β, T ) is the location in level T to which x is ultimately routed as
it passes through the branching program.

3 Boosting a two-sided weak learner
In this section we assume that we have a two-sided weak learner. This is an algorithm which, givena distribution D, can always obtain hypotheses that have two-sided advantage as defined below:
Definition 1 A hypothesis h : X → [−1, 1] has two-sided advantage γ with respect to D if itsatisfies both Ex∈D+ [h(x)] ≥ γ and Ex∈D− [h(x)] ≤ −γ.
As we explain in Section 5.1 we may apply methods of [LS05] to reduce the typical case, in which
we only receive “normal” weak hypotheses rather than two-sided weak hypotheses, to this case.
The branching program starts off with a single node at location (0, 0). Assuming the branching
program has been constructed up through level t, we now explain how it is extended in the t-th stage
up through level t + 1. There are two basic steps in each stage: weak training and branching.
Weak training. Consider a given node at location (β, t) in the branching program. As in [LS05] weconstruct a weak hypothesis hβ,t simply by running the two-sided weak learner on examples drawn
from Dβ,t and letting hβ,t be the hypothesis it generates. Let us write γβ,t to denote
def

γβ,t = min{Ex∈(Dβ,t )+ [hβ,t (x)], Ex∈(Dβ,t )− [−hβ,t (x)]}.
We call γβ,t the advantage at node (β, t).
We do this for all nodes at level t. Now we define the advantage at level t to bedef

γt = min γβ,t .
β(3)Branching. Intuitively, we would like to use γt as a scaling factor for the “step size” of the random
walk at level t. Since we are using confidence-rated weak hypotheses, it is also natural to havethe step that example x takes at a given node be proportional to the value of the confidence-rated
hypothesis at that node on x. The most direct way to do this would be to label the node (β, t) withthe weak classifier hβ,t and to route each example x to a node at location (β + γt hβ,t (x), t + 1).
However, there are obvious difficulties with this approach; for one thing a single node at (β, t) could
give rise to arbitrarily many (infinitely many, if |X| = ∞) nodes at level t+1. Even if the hypotheses
hβ,t were all guaranteed to {−1, 1}-valued, if we were to construct a branching program in this way
then it could be the case that by the T -th stage there are 2T −1 distinct nodes at level T .
We get around this problem by creating nodes at level t + 1 only at integer multiples of γ2t . Note that
this “granularity” that is used is different at each level, depending on the advantage at each level (weshall see in the next section that this is crucial for the analysis). This keeps us from having too many
nodes in the branching program at level t + 1. Of course, we only actually create those nodes in the
branching program that have an incoming edge as described below (later we will give an analysis tobound the number of such nodes).
We simulate the effect of having an edge from (β, t) to (β + γt hβ,t (x), t + 1) by using two edges
from (β, t) to (i · γt /2, t + 1) and to ((i + 1) · γt /2, t + 1), where i is the unique integer such thati · γt /2 ≤ β + γt hβ,t (x) < (i + 1) · γt /2. To simulate routing an example x to (β + γt hβ,t (x), t + 1),
the branching program routes x randomly along one of these two edges so that the expected location
at which x ends up is (β + γt hβ,t (x), t + 1). More precisely, if β + γt hβ,t (x) = (i + ρ) · γt /2 where0 ≤ ρ < 1, then the rule used at node (β, t) to route an example x is “with probability ρ send x to((i + 1) · γt /2, t + 1) and with probability (1 − ρ) send x to (i · γt /2, t + 1).”

Since |hβ,t (x)| ≤ 1 for all x by assumption, it is easy to see that at most eight outgoing edges
are required from each node (β, t). Thus the branching program that the booster constructs uses
a randomized variant of each weak hypothesis hβ,t to route examples along one of (at most) eight
outgoing edges.

4 Proof of correctness for boosting a two-sided weak learner
The following theorem shows that the algorithm described above is an effective adaptive booster for
two-sided weak learners:
Theorem 2 Consider running the above booster for T stages. For t = 0, . . . , T − 1 let the values γ0 , . . . , γT −1 > 0 be defined as described above, so each invocation of the two-sided weaklearner on distribution Dβ,t yields a hypothesis hβ,t that has γβ,t ≥ γt . Then the final hypothesis hconstructed by the booster satisfies
!
T −1
1X 2
Prx∈D [h(x) 6= c(x)] ≤ exp −(4)γ .
8 t=0 tPT −1 Pt−1
The algorithm makes at most M ≤ O(1) · t=0 γ1t j=0 γj calls to the weak learner (i.e. constructs a branching program with at most M nodes).
PT −1 Proof: We will show that Prx∈D+ [h(x) 6= 1] ≤ exp − 81 t=0 γt2 ; a completely symmetricargument shows a similar bound for negative examples, which gives (4).
For t = 1, . . . , T we define the random variable At as follows: given a draw of x from D+ (theoriginal distribution D restricted to positive examples), the value of At is γt−1 hβ,t−1 (x), where(β, t − 1) is the location of the node that x reaches at level t of the branching program. Intuitively
At captures the direction and size of the move that we would like x to make during the branching
step that brings it to level t.
We define Bt to be the random variable that captures the direction and size of the move that x
actually makes during the branching step that brings it to level t. More precisely, let i be the integer
such that i · (γt−1 /2) ≤ β + γt−1 hβ,t−1 (x) < (i + 1) · (γt−1 /2), and let ρ ∈ [0, 1) be such thatβ + γt−1 hβ,t−1 (x) = (i + ρ) · (γt−1 /2). Then((i + 1) · (γt−1 /2) − β) with probability ρ, andBt =(i · (γt−1 /2) − β)with probability 1 − ρ.
We have that E[Bt ] (where the expectation is taken only over the ρ-probability in the definition ofPt
Bt ) equals ((i + ρ) · (γt−1 /2) − β)hβ,t−1 (x) = γt−1 hβ,t−1 (x) = At . Let Xt denote i=1 Bt , so
the value of Xt is the actual location on the real line where x ends up at level t.
Fix 1 ≤ t ≤ T and let us consider the conditional random variable (Xt |Xt−1 ). Conditioned on
Xt−1 taking any particular value (i.e. on x reaching any particular location (β, t − 1)), we have thatx is distributed according to (Dβ,t−1 )+ , and thus we have
2
E[Xt |Xt−1 ] = Xt−1 + Ex∈(Dβ,t )+ [γt−1 hβ,t−1 (x)] ≥ Xt−1 + γt−1 γβ,t−1 ≥ Xt−1 + γt−1, (5)where the first inequality follows from the two-sided advantage of hβ,t−1 .
P
2
For t = 0, . . . , T , define the random variable Yt as Yt = Xt − t−1
i=0 γi (so Y0 = X0 = 0). Since
conditioning on the value of Yt−1 is equivalent to conditioning on the value of Xt−1 , using (5) we
get
#
"
t−2
t−1
t−1
X
X
X
2
γi2 = Yt−1 ,γi2 ≥ Xt−1 −γi Yt−1 = E[Xt |Yt−1 ] −E[Yt |Yt−1 ] = E Xt −
i=0

i=0

i=0

so the sequence of random variables Y0 , . . . , YT is a sub-martingale.1 To see that this sub-martingale
has bounded differences, note that we have22
|Yt − Yt−1 | = |Xt − Xt−1 − γt−1
| = |Bt − γt−1|.
1

The more common definition of a sub-martingale requires that E[Yt |Y0 , ..., Yt−1 ] ≥ Yt−1 , but the weakerassumption that E[Yt |Yt−1 ] ≥ Yt−1 suffices for the concentration bounds that we need (see [ASE92, Hay05]).

The value of Bt is obtained by first moving by γt−1 hβ,t−1 (x), and then rounding to a neighboring2
multiple of γt−1 /2, so |Bt | ≤ (3/2)γt−1 , which implies |Yt − Yt−1 | ≤ (3/2)γt−1 + γt−1
≤ 2γt−1 .
Now recall Azuma’s inequality for sub-martingales:
Let 0 = Y0 , . . . , YT be a sub-martingale which has |Yi − Yi−1| ≤ ci for each2
i = 1, . . . , T . Then for any λ > 0 we have Pr[YT ≤ −λ] ≤ exp − 2 PλT c2 .
i=1

PT −1

We apply this with each ci = 2γi−1 and λ =positive examples, Prx∈D+ [h(x) = −1], equals
Pr[XT < 0] = Pr[YT < −λ] ≤t=0i

γt2 . This gives us that the error rate of h on
λ2

exp − PT −1
8 t=0 γt2

!

T −1

1X 2
= exp −
γ
8 t=0 t!

.

(6)

So we have established (4); it remains to bound the number of nodes constructed in the branching
PT −1program. Let us write Mt to denote the number of nodes at level t, so M = t=0 Mt .
The t-th level of boosting can cause the rightmost (leftmost) node to be at most 2γt−1 distancefarther away from the origin than the rightmost (leftmost) node at the (t − 1)-st level. This means
Pt−1that at level t, every node is at a position (β, t) with |β| ≤ 2 j=0 γj . Since nodes are placed at
PT −1 Pt−1
PT −1
integer multiples of γt /2, we have that M = t=0 Mt ≤ O(1) · t=0 γ1t j=0 γj .

Remark. Consider the case in which each advantage γt is just γ and we are boosting to accuracy
ǫ. As usual taking T = O(log(1/ǫ)/γ 2) gives an error bound of ǫ. With these parameters we havethat M ≤ O(log2 (1/ǫ)/γ 4), the same asymptotic bound achieved in [LS05]. In the next section we
describe a modification of the algorithm that improves this bound by essentially a factor of γ1 .
4.1 Improving efficiency by freezing extreme nodes
Here we describe a variant of the algorithm from the previous section that constructs a branching
program with fewer nodes.
The algorithm requires an input parameter ǫ which is an upper bound on the desired final error of theaggregate classifier. For t ≥ 1, after the execution of
step t − 1 of boosting, when all nodes at levelr
Pt−1 
t have been created, each node (α, t) with |α| >8 s=0 γs2 2 ln t + ln 4ǫ is “frozen.” The
algorithm commits to classifying any test examples routed to any such nodes according to sgn(α),
and these nodes are not used to generate weak hypotheses during the next round of training.
We have the following theorem about the performance of this algorithm:
Theorem 3 Consider running the modified booster for T stages. For t = 0, . . . , T − 1 let thevalues γ1 , . . . , γT > 0 be defined as described above, so each invocation of the weak learner on
distribution Dβ,t yields a hypothesis hβ,t that has γβ,t ≥ γt . Then the final output hypothesis h of
the booster satisfies


−1
ǫ
1 TP
2
Prx∈D [h(x) 6= c(x)] ≤ + exp −
(7)
γ .
2
8 t=0 tr
 PT −1 1
PT −1 2 
1
The algorithm makes O
ln T + ln ǫ · t=0 γt calls to the weak learner.
t=0 γtProof: As in the previous proof it suffices to bound Prx∈D+ [h(x) 6= 1]. The
of Theorem 2
 proofPT −1 2 
1gives us that if we never did any freezing, then Prx∈D+ [h(x) 6= 1] ≤ exp − 8 t=0 γt . Now
let us analyze the effect of freezing in a given stage t q< T . Let At be the distance from the origin
Pt−1
past which examples are frozen in round t; i.e. At = (8 s=0 γs2 )(2 ln t + ln 4ǫ ). Nearly exactly
the same analysis as proves (6) can be used here: for a positive example x to be incorrectly frozen

in round t, it must be the case Xt < −At , or equivalently Yt < −At −of At gives us that Prx∈D+ [x incorrectly frozen in round t] is at mostPr[Yt ≤ −At −

t−1
X
i=0

γt2 ] ≤ Pr[Yt ≤ −At ] ≤Pt−1

2
i=0 γi . Thus our choice

ǫ
,
4t2

so consequently we have Prx∈D+ [x ever incorrectly frozen ] ≤ 2ǫ . From here we may argue as in[LS05]: we have that Prx∈D+ [h(x) = 0] equals
T −1

1X 2
ǫ
γ
Prx∈D+ [h(x = 0 and x is frozen] + Prx∈D+ [h(x) = 0 and x is not frozen] ≤ + exp −2
2 t=0 twhich gives (7). The bound on the number of calls to the weak learner follows from thefact
there are O(At /γt ) such calls in each stage of boosting, and the fact that At ≤q thatPT −1 2(8 s=0 γs )(2 ln T + ln 4ǫ ) for all t.

It is easy to check that if γt = γ for all t, taking T = O(log(1/ǫ)/γ 2) the algorithm in this section
will construct an ǫ-accurate hypothesis that is an O(log2 (1/ǫ)/γ 3 )-node branching program.

5 Extensions
5.1 Standard weak learners
In Sections 3 and 4, we assumed that the boosting algorithm had access to a two-sided weak learner,
which is more accurate than random guessing on both the positive and the negative examples separately. To make use of a standard weak learner, which is merely more accurate than random guessing
on average, we can borrow ideas from [LS05].
The idea is to force a standard weak learner to provide a hypothesis with two-sided accuracy by (a)balancing the distribution so that positive and negative examples are accorded equal importance, (b)balancing the predictions of the output of the weak learner so that it doesn’t specialize on one kindof example.
b be the distribution obtained
Definition 4 Given a probability distribution D over examples, let Dbby rescaling the positive and negative examples so that they have equal weight: i.e., let D[S]
=
1 +
1 −
D
[S]
+
D
[S].
2
2

Definition 5 Given a confidence-rated classifier h : X → [−1, 1] and a probability distribution D
over X, let the balanced variant of h with respect to D be the function ĥ : X → [−1, 1] defined as
h(x)+1
follows: (a) if Ex∈D [h(x)] ≥ 0, then, for all x ∈ X, ĥ(x) = Ex∈D
[h(x)]+1 − 1. (b) if Ex∈D [h(x)] ≤h(x)−10, then, for all x ∈ X, ĥ(x) = −Ex∈D[h(x)]+1 + 1.

The analysis is the natural generalization of Section 5 of [LS05] to confidence-rated classifiers.
Lemma 6 If D is balanced with respect to c, and h is a confidence-rated classifier such that
Ex∈D [h(x)c(x)] ≥ γ, then Ex∈D [ĥ(x)c(x)] ≥ γ/2.
Proof. Assume without loss of generality that Ex∈D [h(x)] ≥ 0 (the other case can be handled
symmetrically). By linearity of expectation

1
Ex∈D [h(x)c(x)]+ Ex∈D [c(x)]−1 .
Ex∈D [ĥ(x)c(x)] =Ex∈D [h(x)] + 1
Ex∈D [h(x]) + 1[h(x)c(x)], so theSince D is balanced we have Ex∈D [c(x)] = 0, and hence Ex∈D [ĥ(x)c(x)] = EEx∈Dx∈D [h(x)]+1
lemma follows from the fact that Ex∈D [h(x)] ≤ 1.

We will use a standard weak learner to simulate a two-sided weak learner as follows. Given ab to the standard weak learner, take its output
distribution D, the two-sided weak learner will pass D
g, and return h = ĝ. Our next lemma analyzes this transformation.

!

Lemma 7 If Ex∈Db [g(x)c(x)] ≥ γ, then Ex∈D+ [h(x)] ≥ γ/2 and Ex∈D− [−h(x)] ≥ γ/2.
b we have
Proof: Lemma 6 implies that Ex∈Db [h(x)c(x)] ≥ γ/2. Expanding the definition of D,
Ex∈D+ [h(x)] − Ex∈D− [h(x)] ≥ γ.

(8)b and c, we have E b [h(x)] = 0. Once again expanding
Since h balanced g with respect to Dx∈Db we get that Ex∈D+ [h(x)] + Ex∈D− [h(x)] = 0 which implies Ex∈D− [h(x)] =the definition of D,−Ex∈D+ [h(x)] and Ex∈D+ [h(x)] = −Ex∈D+ [h(x)]. Substituting each of the RHS for its respective LHS in (8) completes the proof.

Lemma 7 is easily seen to imply counterparts of Theorems 2 and 3 in which the requirement of a
two-sided weak learner is weakened to require only standard weak learning, but each γt is replacedwith γt /2.
5.2 Tolerating random classification noise
As in [LS05], noise tolerance is facilitated by the fact that the path through the network is notaffected by altering the label of an example. On the other hand, balancing the distribution before
passing it to the weak learner, which was needed to use a standard weak learner, may disturb the
independence between the event that an example is noisy, and the random draw of x. This can be
repaired exactly as in [KS05, LS05]; because of space constraints we omit the details.

References[AD98][AL88]

J. Aslam and S. Decatur. Specification and simulation of statistical query algorithms for efficiency
and noise tolerance. J. Comput & Syst. Sci., 56:191–208, 1998.
Dana Angluin and Philip Laird. Learning from noisy examples. Machine Learning, 2(4):343–370,
1988.

[ASE92] N. Alon, J. Spencer, and P. Erdos. The Probabilistic Method (1st ed.). Wiley-Interscience, New
York, 1992.
[BKW03] A. Blum, A. Kalai, and H. Wasserman. Noise-tolerant learning, the parity problem, and the statistical query model. J. ACM, 50(4):506–519, 2003.
[Die00] T.G. Dietterich. An experimental comparison of three methods for constructing ensembles of decision trees: bagging, boosting, and randomization. Machine Learning, 40(2):139–158, 2000.
[Fre95]

Y. Freund. Boosting a weak learning algorithm by majority. Information and Computation,
121(2):256–285, 1995.

[FS96]

Y. Freund and R. Schapire. Experiments with a new boosting algorithm. In ICML, pages 148–156,
1996.

[FS97][Hay05]

Y. Freund and R. E. Schapire. A decision-theoretic generalization of on-line learning and an application to boosting. JCSS, 55(1):119–139, 1997.
T. P. Hayes. A large-deviation inequality for vector-valued martingales. 2005.

[Kea98]

M. Kearns. Efficient noise-tolerant learning from statistical queries. JACM, 45(6):983–1006, 1998.

[KS05]

A. Kalai and R. Servedio. Boosting in the presence of noise. JCSS, 71(3):266–290, 2005.

[LS05][LS08]

P. Long and R. Servedio. Martingale boosting. In Proc. 18th Annual COLT, pages 79–94, 2005.
P. Long and R. Servedio. Random classification noise defeats all convex potential boosters. In
ICML, 2008.

[MO97]

R. Maclin and D. Opitz. An empirical evaluation of bagging and boosting. In AAAI/IAAI, pages
546–551, 1997.

[MR03]

R. Meir and G. Rätsch. An introduction to boosting and leveraging. In LNAI Advanced Lectures on
Machine Learning, pages 118–183, 2003.
[RDM06] L. Ralaivola, F. Denis, and C. Magnan. CN=CNNN. In ICML, pages 265–272, 2006.
[Sch90]R. Schapire. The strength of weak learnability. Machine Learning, 5(2):197–227, 1990.

[Sch03]

R. Schapire. The boosting approach to machine learning: An overview. Springer, 2003.

[SS99]

R. Schapire and Y. Singer. Improved boosting algorithms using confidence-rated predictions. Machine Learning, 37:297–336, 1999.