One-Pass Boosting

Zafer Barutcuoglu
zbarutcu@cs.princeton.edu

Philip M. Long
plong@google.com

Rocco A. Servedio
rocco@cs.columbia.edu

Abstract
This paper studies boosting algorithms that make a single pass over a set of baseclassifiers.
We first analyze a one-pass algorithm in the setting of boosting with diverse baseclassifiers. Our guarantee is the same as the best proved for any boosting algorithm, but our one-pass algorithm is much faster than previous approaches.
We next exhibit a random source of examples for which a “picky” variant of AdaBoost that skips poor base classifiers can outperform the standard AdaBoost algorithm, which uses every base classifier, by an exponential factor.
Experiments with Reuters and synthetic data show that one-pass boosting can substantially improve on the accuracy of Naive Bayes, and that picky boosting cansometimes lead to a further improvement in accuracy.

1 Introduction
Boosting algorithms use simple “base classifiers” to build more complex, but more accurate, aggregate classifiers. The aggregate classifier typically makes its class predictions using a weighted voteover the predictions made by the base classifiers, which are usually chosen one at a time in rounds.
When boosting is applied in practice, the base classifier at each round is usually optimized: typically,each example is assigned a weight that depends on how well it is handled by the previously chosenbase classifiers, and the new base classifier is chosen to minimize the weighted training error. But
sometimes this is not feasible; there may be a huge number of base classifiers with insufficient
apparent structure among them to avoid simply trying all of them out to find out which is best. For
example, there may be a base classifier for each word or k-mer. (Note that, due to named entities, thenumber of “words” in some analyses can far exceed the number of words in any natural language.)In such situations, optimizing at each round may be prohibitively expensive.
The analysis of AdaBoost, however, suggests that there could be hope in such cases. Recall
that if AdaBoost is run with a sequence of base classifiers b1 , . . . , bn that achieve weighted error 12 − γ1 , . . . , 12 − γn , then the training error of AdaBoost’s final output hypothesis is at mostPnexp(−2 t=1 γt2 ). One could imagine applying AdaBoost without performing optimization: (a)fixing an order b1 , ..., bn of the base classifiers without looking at the data, (b) committing to usebase classifier bt in round t, and (c) setting the weight with which bt votes as a function of its
weighted training error using AdaBoost. (In a one-pass scenario, it seems sensible to use AdaBoost
since, as indicated by the above bound, it can capitalize on the advantage over random guessingof every hypothesis.) The resulting algorithm uses essentially the same computational resources as
Naive Bayes [2, 7], but benefits from taking some account of the dependence among base classifiers. Thus motivated, in this paper we study the performance of different boosting algorithms in a
one-pass setting.
Contributions. We begin by providing theoretical support for one-pass boosting using the “diversebase classifiers” framework previously studied in [1, 6]. In this scenario there are n base classifiers.
For an unknown subset G of k of the base classifiers, the events that the classifiers in G are correct
on a random item are mutually independent. This formalizes the notion that these k base classifiersare not redundant. Each of these k classifiers is assumed to have error 21 − γ under the initial
distribution, and no assumption is made about the other n − k base classifiers. In [1] it is shownthat if Boost-by-Majority is applied with a weak learner that does optimization (i.e. always uses the“best” of the n candidate base classifiers at each of Θ(k) stages of boosting), the error rate of the
combined hypothesis with respect to the underlying distribution is (roughly) at most exp(−Ω(γ 2 k)).
In Section 2 we show that a one-pass variant of Boost-by-Majority achieves a similar bound with asingle pass through the n base classifiers, reducing the computation time required by an Ω(k) factor.
We next show in Section 3 that when running AdaBoost using one pass, it can sometimes be advantageous to abstain from using base classifiers that are too weak. Intuitively, this is because using
many weak base classifiers early on can cause the boosting algorithm to reweight the data in a waythat obscures the value of a strong base classifier
Pn that comes later. (Note that the quadratic dependence on γt in the exponent of the exp(−2 t=1 γt2 ) means that one good base classifier is morevaluable than many poor ones.) In a bit more detail, suppose that base classifiers are consideredin the order b1 , . . . , bn , where each of b1 , . . . , bn−1 has a “small” advantage over random guessing
under the initial distribution D and bn has a “large” advantage under D. Using b1 , . . . , bn−1 for the
first n − 1 stages of AdaBoost can cause the distributions D2 , D3 , . . . to change from the initial D1
in such a way that when bn is finally considered, its advantage under Dn is markedly smaller thanits advantage under D0 , causing AdaBoost to assign bn a small voting weight. In contrast, a “picky”
version of AdaBoost would pass up the opportunity to use b1 , . . . , bn−1 (since their advantages are
too small) and thus be able to reap the full benefit of using bn under distribution D0 (since when bn
is finally considered the distribution D is still D0 , since no earlier base classifiers have been used).
Finally, Section 4 gives experimental results on Reuters and synthetic data. These show that one-passboosting can lead to substantial improvement in accuracy over Naive Bayes while using a similar
amount of computation, and that picky one-pass boosting can sometimes further improve accuracy.

2 Faster learning with diverse base classifiers
We consider the framework of boosting in the presence of diverse base classifiers studied in [1].
Definition 1 (Diverse γ-good) Let D be a distribution over X × {−1, 1}. We say that a set G ofclassifiers is diverse and γ-good with respect to D if (i) each classifier in G has advantage at least
γ (i.e., error at most 21 − γ) with respect to D, and (ii) the events that the classifiers in G are correct
are mutually independent under D.
We will analyze the Picky-One-Pass Boost-by-Majority (POPBM) algorithm, which we define asfollows. It uses three parameters, α, T and ǫ.
1. Choose a random ordering b1 , ..., bn of the base classifiers in H, and set i1 = 1.
2. For as many rounds t as it ≤ min{T, n}:(a) Define Dt as follows: for each example (x, y),i. Let rt (x, y) be the the number of previously chosen base classifiers h1 , . . . , ht−1that are correct on (x, y);
 1
T
T
−t−1
ii. Let wt (x, y) = ⌊ T T⌋−r
( 2 + α)⌊ 2 ⌋−rt (x,y) ( 12 − α)⌈ 2 ⌉−t−1+rt (x,y) , lett (x,y)2
Zt = E(x,y)∼D (wt (x, y)), and let Dt (x, y) = wt (x,y)D(x,y).
Zt(b) Compare Zt to ǫ/T , andi. If Zt ≥ ǫ/T , then try bit , bit +1 , ... until you encounter a hypothesis bj with advantage at least α with respect to Dt (and if you run out of base classifiers before thishappens, then go to step 3). Set ht to be bj (i.e. return bj to the boosting algorithm)
and set it+1 to j + 1 (i.e. the index of the next base classifier in the list).
ii. If Zt < ǫ/T , then set ht to be the constant-1 hypothesis (i.e. return this constanthypothesis to the boosting algorithm) and set it+1 = it .
3. If t < T + 1 (i.e. the algorithm ran out of base classifiers before selecting T of them), abort.
Otherwise, output the final classifier f (x) = M aj(h1 (x), . . . , hT (x)).

The idea behind step 2.b.ii is that if Zt is small, then Lemma 4 will show that it doesn’t much matter
how good this weak hypothesis is, so we simply use a constant hypothesis.
To simplify the exposition, we have assumed that POPBM can exactly determine quantities such
as Zt and the accuracies of the weak hypotheses. This would provably be the case if D wereconcentrated on a moderate number of examples, e.g. uniform over a training set. With slightcomplications, a similar analysis can be performed when these quantities must be estimated.
The following lemma from [1] shows that if the filtered distribution is not too different from theoriginal distribution, then there is a good weak hypothesis relative to the original distribution.
Lemma 2 ([1]) Suppose a set G of classifiers of size k is diverse and γ-good with respect to D. For2any probability distribution Q such that Q(x, y) ≤ γ3 eγ k/2 D(x, y) for all (x, y) ∈ X × {−1, 1},
there is a g ∈ G such thatPr(x,y)∼Q (g(x) = y) ≥ 21 + γ4 .
(1)
The following simple extension of Lemma 2 shows that, given a stronger constraint on the filtered
distribution, there are many good weak hypotheses available.
Lemma 3 Suppose a set G of classifiers of size k is diverse and γ-good with respect to D. Fix anyℓ < k. For any probability distribution Q such that
γ 2(2)Q(x, y) ≤ eγ ℓ/2 D(x, y)
3
for all (x, y) ∈ X × {−1, 1}, there are at least k − ℓ + 1 members g of G such that (1) holds.
Proof: Fix any distribution Q satisfying (2). Let g1 , ..., gℓ be an arbitrary collection of ℓ elementsof G. Since the {g1 , ..., gℓ } and Q satisfy the requirements of Lemma 2 with k set to ℓ, one of
g1 , . . . , gℓ must satisfy (1); so any set of ℓ elements drawn from G contains an element that satisfies(1). This yields the lemma.
We will use another lemma, implicit in Freund’s analysis [3], formulated as stated here in [1]. It
formalizes two ideas: (a) if the weak learners perform well, then so will the strong learner; and (b)the performance of the weak learner is not important in rounds for which Zt is small.
Lemma 4 Suppose that Boost-by-Majority is run with parameters α and T , and generates classifiers h1 , ..., hT for which D1 (h1 (x) = y) = 21 + γ1 , . . . , DT (hT (x) = y) = 12 + γT . Then,for a random element of D, a majority vote over h1 , ..., hT is incorrect with probability at mostPT2e−2α T + t=1 (α − γt )Zt .
Now we give our analysis.

Theorem 5 Suppose the set H of base classifiers used by POPBM contains a subset G of k elementsthat is diverse and γ-good with respect to the initial distribution D, where γ is a constant (say 1/4).
Then there is a setting of the parameters of POPBM so that, with probability 1 − 2−Ω(k) , it outputs
a classifier with accuracy exp(−Ω(γ 2 k)) with respect to the original distribution D.
2

3k −γ k/16
Proof: We prove that α = γ/4, T = k/64, and ǫ = 8γeis a setting of parameters as
required. We will establish the following claim:

Claim 6 For the above parameter settings we have Pr[POPBM aborts in Step 3] = 2−Ω(k) .
Suppose for now that the claim holds, so that with high probability POPBM outputs a classifier.
In case it does, let f be this output. Then since POPBM runs for a full T rounds, we may apply
Lemma 4 which bounds the error rate of the Boost-by-Majority final classifier. The lemma gives usthat D(f (x) 6= y) is at most2e−2α T +TP(α − γt )Zt=2e−γ T /8 +P

t:Zt < Tǫ

t=1

≤

2

(α − γt )Zt +P

t:Zt ≥ Tǫ2e−Ω(γ k) + T (ǫ/T ) + 0 = e−Ω(γ k) .

(α − γt )Zt(Theorem 5)

The final inequality holds since α − γt ≤ 0 if Zt ≥ ǫ/T and α − γt ≤ 1 if Zt < ǫ/T.
Proof of Claim 6: In order for POPBM to abort, it must be the case that as the k base classifiers in
G are encountered in sequence as the algorithm proceeds through h1 , . . . , hn , more than 63k/64 ofthem are skipped in Step 2.b.i. We show this occurs with probability at most 2−Ω(k) .
For each j ∈ {1, ..., k}, let Xj be an indicator variable for the event that the jth member of G
in the ordering b1 , . . . , bn is encountered during the boosting process and skipped, and for eachPℓℓ ∈ {1, ..., k}, let Sℓ = min{( j=1 Xj ) − (3/4)ℓ, k/8}. We claim that S1 , ..., Sk/8 is a supermartingale, i.e. that E[Sℓ+1 |S1 , . . . , Sℓ ] ≤ Sℓ for all ℓ < k/8. If Sℓ = k/8 or if the boostingprocess has terminated by the ℓth member of G, this is obvious. Suppose that Sℓ < k/8 and that thealgorithm has not terminated yet. Let t be the round of boosting in which the ℓth member of G is encountered. The value wt (x, y) can be interpreted as a probability, and so we have that wt (x, y) ≤ 1.
Consequently, we have that
T
γ 2
γ 2
D(x, y)≤ D(x, y) · = D(x, y) · eγ k/16 < D(x, y) · eγ k/8 .
Dt (x, y) ≤
Zt
ǫ
24
3
Now Lemma 3 implies that at least half of the classifiers in G have advantage at least α w.r.t. Dt .
Since ℓ < k/4, it follows that at least k/4 of the remaining (at most k) classifiers in G that have notyet been seen have advantage at least α w.r.t. Dt . Since the base classifiers were ordered randomly,
any order over the remaining hypotheses is equally likely, and so also is any order over the remaining
hypotheses from G. Thus, the probability that the next member of G to be encountered has advantage
at least α is at least 1/4, so the probability that it is skipped is at most 3/4. This completes the proof
that S1 , ..., Sk/8 is a supermartingale.
Since |Sℓ − Sℓ−1 | ≤ 1, Azuma’s inequality for supermartingales implies that Pr(Sk/8 > k/64) ≤e−Ω(k) . This means that the probability that at least k/64 good elements were not skipped is at least
1 − e−O(k) , which completes the proof.

3 For one-pass boosting, PickyAdaBoost can outperform AdaBoost
AdaBoost is the most popular boosting algorithm. It is most often applied in conjunction with aweak learner that performs optimization, but it can be used with any weak learner. The analysis
of AdaBoost might lead to the hope that it can profitably be applied for one-pass boosting. In thissection, we compare AdaBoost and its picky variant on an artificial source especially designed toillustrate why the picky variant may be needed.
AdaBoost. We briefly recall some basic facts about AdaBoost (see Figure 1). If we run AdaBoost
for T stages with weak hypotheses h1 , . . . , hT , it constructs a final hypothesisTP
H(x) = sgn(f (x)) where f (x) =αt ht (x)
(3)

t=1
1−ǫt
1
with αt = 2 ln ǫt . Here ǫt = Pr(x,y)∼Dt [ht (x) 6= y] where Dt is the t-th distribution constructedby the algorithm (the first distribution D1 is just D, the initial distribution). We write γt to denote12 − ǫt , the advantage of the t-th weak hypothesis under distribution Dt . Freund and Schapire [5]proved that if AdaBoost is run with an initial distribution D over a set of labeled examples, then thePTerror rate of the final combined classifier H is at most exp(−2 i=1 γt2 ) under D:


T
P
2
(4)
γt .
Pr(x,y)∼D [H(x) 6= y] ≤ exp −2
i=1(We note that AdaBoost is usually described in the case in which D is uniform over a training set, but
the algorithm and most of its analyses, including (4), go through in the greater generality presented
here. The fact that the definition of αt depends indirectly on an expectation evaluated according to
D makes the case in which D is uniform over a sample most directly relevant to practice. However,
it is easiest to describe our construction using this more general formulation of AdaBoost.)
PickyAdaBoost. Now we define a “picky” version of AdaBoost, which we call PickyAdaBoost.
The PickyAdaBoost algorithm is initialized with a parameter γ > 0. Given a value γ, the PickyAdaBoost algorithm works like AdaBoost but with the following difference. Suppose that PickyAdaBoost is performing round t of boosting, the current distribution is some D′ , and the current

Given a source D of random examples.
• Initialize D1 = D.
• For each round t from 1 to T :– Present Dt to a weak learner, and receive base classifier ht ;t
– Calculate error ǫt = Pr(x,y)∼Dt [ht (x) 6= y] and set αt = 21 ln 1−ǫǫt ;′– Update the distribution:
Define Dt+1 by setting Dt+1
(x, y)=′exp(−αt yht (x))Dt (x, y) and normalizing Dt+1
to get the probability distribu′
tion Dt+1 = Dt+1
/Zt+1 ;P
• Return the final classification rule H(x) = sgn ( t αt ht (x)) .
Figure 1: Pseudo-code for AdaBoost (from [4]).
base classifier ht being considered has advantage γ under D′ , where |γ| < γ. If this is the casethen PickyAdaBoost abstains in that round and does not include ht into the combined hypothesis it
is constructing. (Note that consequently the distribution for the next round of boosting will also beD′ .) On the other hand, if the current base classifier has advantage γ where |γ| ≥ γ, then PickyAdaBoost proceeds to use the weak hypothesis just like AdaBoost, i.e. it adds αt ht to the function f
described in (3) and adjusts D′ to obtain the next distribution.
Note that we only require the magnitude of the advantage to be at least γ. Whether a given baseclassifier is used, or its negation is used, the effect that it has on the output of AdaBoost is the sameǫ(briefly, because ln 1−ǫ
ǫ = − ln 1−ǫ ). Consequently, the appropriate notion of a “picky” version of
AdaBoost is to require the magnitude of the advantage to be large.
3.1 The construction
We consider a sequence of n + 1 base classifiers b1 , . . . , bn , bn+1 . For simplicity we suppose thatthe domain X is {−1, 1}n+1 and that the value of the i-th base classifier on an instance x ∈ {0, 1}nis simply bi (x) = xi .
Now we define the distribution D over X ×{−1, 1}. A draw of (x, y) is obtained from D as follows:
the bit y is chosen uniformly from {+1, −1}. Each bit x1 , . . . , xn is chosen independently to equal
y with probability 12 + γ, and the bit xn+1 is chosen to equal y if there exists an i, 1 ≤ i ≤ n, forwhich xi = y; if xi = −y for all 1 ≤ i ≤ n then xn+1 is set to −y.
3.2 Base classifiers in order b1 , . . . , bn , bn+1
Throughout Section 3.2 we will only consider parameter settings of γ, γ, n for which γ < γ ≤
1
1
1
1
1
1
n
n
n
2 − ( 2 − γ) . Note that the inequality γ < 2 − ( 2 − γ) is equivalent to ( 2 − γ) < 2 − γ, whichholds for all n ≥ 2.
PickyAdaBoost. In the case where γ < γ ≤ 12 − ( 12 − γ)n , it is easy to analyze the error rate of
PickyAdaBoost(γ) after one pass through the base classifiers in the order b1 , . . . , bn , bn+1 . Since
each of b1 , . . . , bn has advantage exactly γ under D and bn+1 has advantage 21 − ( 21 − γ)n under D,
PickyAdaBoost(γ) will abstain in rounds 1, . . . , n and so its final hypothesis is sgn(bn+1 (·)), whichis the same as bn+1 . It is clear that bn+1 is wrong only if each xi 6= y for i = 1, . . . , n, which occurs
with probability ( 12 − γ)n . We thus have:
Lemma 7 For γ < γ ≤ 21 − ( 21 − γ)n , PickyAdaBoost(γ) constructs a final hypothesis which has
error rate precisely ( 12 − γ)n under D.
AdaBoost. Now let us analyze the error rate of AdaBoost after one pass through the base classifiersin the order b1 , . . . , bn+1 . We write Dt to denote the distribution that AdaBoost uses at the t-th stageof boosting (so D = D1 ). Recall that γt is the advantage of bt under distribution Dt .
The following claim is an easy consequence of the fact that given the value of y, the values of thebase classifiers b1 , . . . , bn are all mutually independent:

Claim 8 For each 1 ≤ t ≤ n we have that γt = γ.
1/2+γ
1+2γ
It follows that the coefficients α1 , . . . , αn of b1 , . . . , bn are all equal to 12 ln 1/2−γ= 12 ln 1−2γ.

The next claim can be straightforwardly proved by induction on t:
Claim 9 Let Dr denote the distribution constructed by AdaBoost after processing the base classifiers b1 , . . . , br−1 in that order. A draw of (x, y) from Dr is distributed as follows:• The bit y is uniform random from {−1, +1};
• Each bit x1 , . . . , xr−1 independently equals y with probability 12 , and each bit xr , . . . , xn
independently equals y with probability 21 + γ;
• The bit xn+1 is set as described in Section 3.1, i.e. xn+1 = −y if and only if x1 = · · · =xn = −y.
Claim 9 immediately gives ǫn+1 = Pr(x,y)∼Dn+1 [bn+1 (x) 6= y] = 1/2n. It follows that αn+1 =
1−ǫn+11
1n
2 ln ǫn+1 = 2 ln(2 − 1). Thus an explicit expression for the final hypothesis of AdaBoost after
one pass over the n + 1 classifiers b1 , . . . , bn+1 is H(x) = sgn(f (x)), where
 

1+2γ
(x1 + · · · + xn ) + 21 (ln(2n − 1))xn+1 .
f (x) = 21 ln 1−2γ
Using the fact that H(x) 6= y if and only if yf (x) < 0, it is easy to establish the following:
Claim 10 The classifier H(x) makes a mistake on (x, y) if and only if more than A of the variablesn−1)x1 , . . . , xn disagree with y, where A = n2 + 2ln(2.
ln 1+2γ
1−2γ

For (x, y) drawn from source D, we have that each of x1 , . . . , xn independently agrees with y withprobability 21 + γ. Thus we have established the following:
Lemma 11 Let B(n, p) denote a binomial random variable with parameters n, p (i.e. a draw from
B(n, p) is obtained by summing n i.i.d. 0/1 random variables each of which has expectation p).
Then the AdaBoost final hypothesis error rate is Pr[B(n, 21 − γ) > A], which equals
 
n
P
n
(1/2 − γ)i (1/2 + γ)n−i .
(5)i=⌊A⌋+1 i
In terms of Lemma 11, Lemma 7 states that the PickyAdaBoost(γ) final hypothesis has error
Pr[B(n, 21 − γ) ≥ n]. We thus have that if A < n − 1 then AdaBoost’s final hypothesis has
greater error than PickyAdaBoost.
We now give a few concrete settings for γ, n with which PickyAdaBoost beats AdaBoost. First
we observe that even in some simple cases the AdaBoost error rate (5) can be larger than the PickyAdaBoost error rate by a fairly large additive constant. Taking n = 3 and γ = 0.38, we find thatthe error rate of PickyAdaBoost(γ) is ( 12 − 0.38)3 = 0.001728, whereas the AdaBoost error rate is( 21 − 0.38)3 + 3( 12 − 0.38)2 · ( 21 + 0.38) = 0.03974.
Next we observe that there can be a large multiplicative factor difference between the AdaBoost andPn−⌊A⌋−1 n
PickyAdaBoost error rates. We have that Pr[B(n, 1/2 − γ) > A] equals i=0i (1/2 −γ)n−i (1/2 + γ)i . This can be lower bounded by n−⌊A⌋−1Pnn;(6)Pr[B(n, 1/2 − γ) > A] ≥ (1/2 − γ)ii=0this bound is rough but good enough for our purposes. Viewing n as an asymptotic parameter and γ
as a fixed constant, we have
 
αn n
P
(7)
(6) ≥ (1/2 − γ)n
i=0 i

2
− o(1). Using the boundwhere α = 21 − 2 lnln1+2γ
1−2γ

Pαn

i=0

n
i



= 2n·(H(α)±o(1)) , which holds for

0 < α < 21 , we see that any setting of γ such that α is bounded above zero by a constant gives an
exponential gap between the error rate of PickyAdaBoost (which is (1/2 − γ)n) and the lower boundon AdaBoost’s error provided by (7). As it happens any γ ≥ 0.17 yields α > 0.01. We thus have
Claim 12 For any fixed γ ∈ (0.17, 0.5) and any γ < γ, the final error rate of AdaBoost on thesource D is 2Ω(n) times that of PickyAdaBoost(γ).
3.3 Base classifiers in an arbitrary ordering
The above results show that PickyAdaBoost can outperform AdaBoost if the base classifiers are
considered in the particular order b1 , . . . , bn+1 . A more involved analysis (omitted because of spaceconstraints) establishes a similar difference when the base classifiers are chosen in a random order:
Proposition 13 Suppose that 0.3 < γ < γ < 0.5 and 0 < c < 1 are fixed constants independent ofdef

n that satisfy Z(γ) < c, where Z(γ) =4
ln (1−2γ)2
1+2γ
ln (1−2γ)
3. Suppose the base classifiers are listed in anorder such that bn+1 occurs at position c · n. Then the error rate of AdaBoost at least 2n(1−c) − 1 =2Ω(n) times greater than the error of PickyAdaBoost(γ).
For the case of randomly ordered base classifiers, we may view c as a real value that is uniformly
distributed in [0, 1], and for any fixed constant 0.3 < γ < 0.5 there is a constant probability (at least
1 − Z(γ)) that AdaBoost has error rate 2Ω(n) times larger than PickyAdaBoost(γ). This probability
can be fairly large, e.g. for γ = 0.45 it is greater than 1/5.

4 Experiments
We used Reuters data and synthetic data to examine the behavior of three algorithms: (i) Naive
Bayes; (ii) one-pass Adaboost; and (iii) PickyAdaBoost.
The Reuters data was downloaded from www.daviddlewis.com. We used the ModApte splits
into training and test sets. We only used the text of each article, and the text was converted into
lower case before analysis. We compared the boosting algorithms with multinomial Naive Bayes[7]. We used boosting with confidence-rated base classifiers [8], with a base classifier for each stemof length at most 5; analogously to the multinomial Naive Bayes, the confidence of a base classifier
was taken to be the number of times its stem appeared in the text. (Schapire and Singer [8, Section
3.2] suggested, when the confidence of base classifiers cannot be bounded a priori, to choose eachvoting weight αt in order to maximize the reduction in potential. We did this, using Newton’s
method to do this optimization.) We averaged over 10 random permutations of the features. The
results are compiled in Table 1. The one-pass boosting algorithms usually improve on the accuracyof Naive Bayes, while retaining similar simplicity and computational efficiency. PickyAdaBoost
appears to usually improve somewhat on AdaBoost. Using a t-test at level 0.01, the W-L-T for
PickyAdaBoost(0.1) against multinomial Naive Bayes is 5-1-4.
We also experimented with synthetic data generated according to a distribution D defined as follows:
to draw (x, y), begin by picking y ∈ {−1, +1} uniformly at random. For each of the k features
x1 , . . . , xk in the diverse γ-good set G, set xi equal to y with probability 1/2 + γ (independently
for each i). The remaining n − k variables are influenced by a hidden variable z which is set
independently to be equal to y with probability 4/5. The features xk+1 , . . . , xn are each set to
be independently equal to z with probability p. So each such xj (j ≥ k + 1) agrees with y withprobability (4/5) · p + (1/5) · (1 − p).
There were 10000 training examples and 10000 test examples. We tried n = 1000 and n = 10000.
Results when n = 10000 are summarized in Table 2. The boosting algorithms predictably performbetter than Naive Bayes, because Naive Bayes assigns too much weight to the correlated features.
The picky boosting algorithm further ameliorates the effect of this correlation. Results for n = 1000
are omitted due to space constraints: these are qualitatively similar, with all algorithms performing
better, and the differences between algorithms shrinking somewhat.

Data

NB

earn
acq
money-fx
crude
grain
trade
interest
wheat
ship
corn

0.042
0.036
0.043
0.026
0.038
0.068
0.026
0.022
0.013
0.027

Error rates
PickyAdaBoost
0.001 0.01
0.1
0.023 0.020 0.018 0.027
0.094 0.065 0.071 0.153
0.042 0.041 0.041 0.048
0.031 0.027 0.026 0.040
0.021 0.023 0.019 0.018
0.028 0.028 0.026 0.029
0.032 0.029 0.032 0.035
0.014 0.013 0.013 0.017
0.018 0.018 0.017 0.016
0.014 0.014 0.014 0.013

OPAB

NB
19288
19288
19288
19288
19288
19288
19288
19288
19288
19288

Feature counts
OPAB
PickyAdaBoost
0.001 0.01 0.1
19288 2871 542 52
19288 3041 508 41
19288 2288 576 62
19288 2865 697 58
19288 2622 650 64
19288 2579 641 61
19288 2002 501 58
19288 2294 632 61
19288 2557 804 67
19288 2343 640 67

Table 1: Experimental results. On the left are error rates on the 3299 test examples for Reutersdata sets. On the right are counts of the number of features used in the models. NB is the multinomial Naive Bayes, and OPAB is one-pass AdaBoost. Results are shown for three PickyAdaBoost
thresholds: 0.001, 0.01 and 0.1.
k

p

γ

NB

OPAB

20
20
20
50
50
50
100
100
100

0.85
0.9
0.95
0.7
0.75
0.8
0.63
0.68
0.73

0.24
0.24
0.24
0.15
0.15
0.15
0.11
0.11
0.11

0.2
0.2
0.21
0.2
0.2
0.21
0.2
0.2
0.2

0.11
0.09
0.06
0.13
0.12
0.11
0.14
0.13
0.1

PickyAdaBoost
0.07 0.1 0.16
0.04 0.04 0.03
0.03 0.03 0.03
0.02 0.02 0.02
0.06 0.04 0.09
0.05 0.04 0.03
0.04 0.03 0.03
0.07 0.05
0.06 0.05
0.05 0.04

Table 2: Test-set error rate for synthetic data. Each value is an average over 100 independent runs
(random permutations of features). Where a result is omitted, the corresponding picky algorithm did
not pick any base classifiers.

References[1] S. Dasgupta and P. M. Long. Boosting with diverse base classifiers. COLT, 2003.
[2] R. O. Duda and P. E. Hart. Pattern Classification and Scene Analysis. Wiley, 1973.
[3] Y. Freund. Boosting a weak learning algorithm by majority. Inf. and Comput., 121(2):256–285,
1995.
[4] Y. Freund and R. Schapire. Experiments with a new boosting algorithm. In ICML, pages 148–
156, 1996.
[5] 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.
[6] N. Littlestone. Redundant noisy attributes, attribute errors, and linear-threshold learning using
Winnow. In COLT, pages 147–156, 1991.
[7] A. Mccallum and K. Nigam. A comparison of event models for naive bayes text classification.
In AAAI-98 Workshop on Learning for Text Categorization, 1998.
[8] R. Schapire and Y. Singer. Improved boosting algorithms using confidence-rated predictions.
Machine Learning, 37:297–336, 1999.