A Bayesian Framework for Online Classifier Ensemble

Qinxun Bai
Department of Computer Science, Boston University, Boston, MA 02215 USA
Henry Lam
Department of Mathematics and Statistics, Boston University, Boston, MA 02215 USA
Stan Sclaroff
Department of Computer Science, Boston University, Boston, MA 02215 USA

Abstract
We propose a Bayesian framework for recursively estimating the classifier weights in online
learning of a classifier ensemble. In contrast withpast methods, such as stochastic gradient descentor online boosting, our framework estimates theweights in terms of evolving posterior distributions. For a specified class of loss functions, weshow that it is possible to formulate a suitably defined likelihood function and hence use the posterior distribution as an approximation to the global
empirical loss minimizer. If the stream of training data is sampled from a stationary process, we
can also show that our framework admits a superior rate of convergence to the expected loss minimizer than is possible with standard stochastic
gradient descent. In experiments with real-world
datasets, our formulation often performs better
than online boosting algorithms.

1. Introduction
The literature on online ensemble classification has studied
recursive mechanisms to combine several weak classifiers,
when given labeled training data {xt , yt }Tt=1 that arrive
sequentially. Different approaches have been proposed,
including online extensions of boosting (Oza & Russell,
2001; Pelossof et al., 2009) and stochastic gradient descentbased methods (Babenko et al., 2009b; Leistner et al.,2009; Grbovic & Vucetic, 2011).
Recently, Chen etal. (2012) formulated a smoothed boosting algorithm basedon the analysis of regret from offline benchmarks.
In this paper, we pose the online ensemble problem as
Proceedings of the 31 st International Conference on Machine
Learning, Beijing, China, 2014. JMLR: W&CP volume 32. Copyright 2014 by the author(s).

QINXUN @ CS . BU . EDU

KHLAM @ BU . EDU

SCLAROFF @ CS . BU . EDU

a loss minimization problem with respect to the ensemble weights, and propose an online ensemble classification
method that is not based on boosting or gradient descent.
The main idea is to recursively estimate a posterior distribution of the ensemble weights in a Bayesian manner. We
show that, for a given class of loss functions, we can definea likelihood function on the ensemble weights and, with anappropriately formulated prior distribution, we can generate a posterior mean that closely approximates the empirical loss minimizer.
Our proposed scheme is straightforward, but powerful in
two respects. First, it can approximate the global optimal
solution, in contrast with local methods such as stochastic gradient descent (SGD). Second, assuming the training
data is sampled from a stationary process, our Bayesian
scheme possesses a rate of convergence to the expected loss
minimizer that is at least as fast as standard SGD. In fact,
our rate is faster unless the SGD step size is chosen optimally, which cannot be done a priori in the online setting. We identify the class of loss functions where both of
the above properties are precisely satisfied. In experimentswith real-world datasets, our formulation often performs
better than state-of-the-art online boosting algorithms.

2. Related WorkA number of past works focus on online learning with concept drift (Wang et al., 2003; Kolter & Maloof, 2005; 2007;
Minku, 2011), which differs from stationary online settings. Given the technical difficulty, theoretical analysis forconcept drift seems to be underdeveloped. Kolter & Maloof (2005) proved error bounds for their proposed method,which appears to be the first such theoretical analysis, yetsuch analysis is not easily generalized to other methods
in this category. Other works, such as Schapire (2001)
and Cesa-Bianchi & Lugosi (2003), obtained performancebounds from the perspective of iterative games.

A Bayesian Framework for Online Classifier Ensemble

Our work is more closely related to methods that operate
in a stationary environment, most notably online boosting
methods. One of the first methods was proposed by Oza& Russell (2001), who showed asymptotic convergence tobatch boosting under certain conditions. However, the convergence result only holds for some simple “lossless” weaklearners (Oza, 2001), such as Naive Bayes. Other variantsof online boosting have been proposed, such as methods
that employ feature selection (Grabner & Bischof, 2006;
Liu & Yu, 2007), semi-supervised learning (Grabner et al.,2008), multiple instance learning (Babenko et al., 2009a),
and multi-class learning (Saffari et al., 2010). However,most of these works consider the design and update of
weak learners beyond that of (Oza, 2001) and, thus, donot bear the convergence guarantee therein. Other methods employ the gradient descent framework, such as Online
GradientBoost (Leistner et al., 2009), Online Stochastic
Boosting (Babenko et al., 2009b) and Incremental Boosting (Grbovic & Vucetic, 2011). Many of these methods
possess convergence results, which provide a basis forcomparison with our framework. In fact, we show that our
method compares favorably to gradient descent in terms ofasymptotic convergence rate. Lastly, Chen et al. (2012)
proposed an online boosting method with a theoreticalbound on the error rate, with the novel design of a smootherand more conservative update of the online weak classifiers.
Our idea is related to, yet differs from, simulated annealing (Laarhoven et al., 1987) and Bayesian model averaging (Hoeting et al., 1999). The former is a global optimization technique, typically conducted by defining a probability distribution that has the objective function that one
wants to minimize as an exponent, and running Monte
Carlo to estimate the peak of this distribution. Simulated
annealing, nevertheless, is primarily motivated for deterministic global optimization, and should be contrasted withthe stochastic and also the sequential nature of our framework. Next, conventional Bayesian model averaging aims
to combine several plausible models as a closer descriptionof the data. In contrast, our Bayesian framework does not
focus on the actual model that generates the data, but isinstead motivated as a loss minimization algorithm.

3. Bayesian Recursive Ensemble
We denote the input feature by x and its classification label by y (1 or −1). We assume that we are given m binary
weak classifiers {ci (x)}mi=1 , and our goal is to find the best
ensemble weights λ = (λ1 , . . . , λm ) where λi ≥ 0, to construct an ensemble classifier. For now, we do not impose
a particular form of ensemble method (wePdefer this until
Section 4), although one example form is i λi ci (x). We
focus on online learning, where training data (x, y) comesin sequentially, one at a time at t = 1, 2, 3, . . ..
3.1. Loss Specification
We first introduce a loss function at the weak classifier
level. Given a training pair (x, y) and an arbitrary weakclassifier h, we denote g := g(h(x), y) as a non-negativeloss function. Possible choices of g include the logistic
loss function, hinge loss, zero-one loss, etc. If h is one of
the given weak classifiers ci , we will denote g(ci (x), y) asgi (x, y), or simply gi for ease of notation. Furthermore,
we define git := g(cti (xt ), y t ) where (xt , y t ) is the training
sample and cti the updated i-th weak classifier at time t. To
simplify notation, we use g := (g1 , . . . , gm ) to denote thet)vector of losses for the weak classifiers, gt := (g1t , . . . , gm
1:T
1T
to denote the losses at time t, and g:= (g , . . . , g ) todenote the losses up to time T .
With the above notation, we let ℓt (λ; gt ) be some ensemble loss function at time t, which depends on the ensemble
weights and the individual loss of each weak classifier. We
then define our cumulative ensemble loss as follows:
LT (λ; g1:T ) = ℓ0 (λ) +TXℓt (λ; gt )

(1)

t=1

where ℓ0 (λ) can be regarded as an initial loss, which becomes negligible as T progresses.
We make two sets of assumptions on LT that are adaptedfrom Chen (1985): one on the regularity conditions on LT ,the other on the form of ℓt to ensure eligibility in applying
our Bayesian approach. We now specify these assumptions.
Assumption 1 (Regularity conditions). Assume that foreach T , there exists a λ∗T that minimizes (1), and1. “local optimality”: for each T , ∇LT (λ∗T ; g1:T ) = 0
and ∇2 LT (λ∗T ; g1:T ) is positive definite.
2. “steepness”:
the minimum eigenvalue∇2 LT (λ∗T ; g1:T ) diverges to ∞ as T → ∞.

of

3. “smoothness”: For any ǫ > 0, there exists a positive
integer N and δ > 0 such that for any T > N and θ ∈Hδ (λ∗T ) = {θ : kθ − λ∗T k2 ≤ δ}, ∇2 LT (θ; g1:T )exists and satisfies
−1≤ I+A(ǫ)
I−A(ǫ) ≤ ∇2 LT (θ; g1:T ) ∇2 LT (λ∗T ; g1:T )for some positive semidefinite symmetric matrix A
whose largest eigenvalue tends to 0 as ǫ → 0, andthe inequalities above are matrix inequalities.
4. “concentration”: for any δ > 0, there exists a positive
integer N and constants c, p > 0 such that for any
T > N and θ 6∈ Hδ (λ∗T ), we have
LT (θ; g1:T ) − LT (λ∗T ; g1:T ) <pc (θ − λ∗T )′ ∇2 LT (λ∗T ; g1:T )(θ − λ∗T )A Bayesian Framework for Online Classifier Ensemble

In the situation where ℓt is separable
terms of eachPinmcomponent
of
λ,
i.e.
ℓ
(λ;
g)
=
t
i=1 ri (λi ; g) andPmℓ0 (λ) = i=1 si (λi ) for some twice differentiable functions ri (·; g) and si (·), the assumptions above will dependPTtonly on fi (λ; g1:T ) :=t=1 ri (λ; g ) + si (λ) for eachi. For example, Condition 3 in Assumption 1 reduces tomerely checking uniform continuity of each fi′′ (·; g1:T ).
Condition 1 in Assumption 1 can be interpreted as the standard first and second order conditions for the optimality of
λ∗T , whereas Condition 3 in essence requires continuity of
the Hessian matrix. Conditions 2 and 4 are needed for theuse of Laplace method (Cox & Hinkley, 1974), which, as
we will show later, stipulates that the posterior distribution
peaks near the optimal solution λ∗T .
Assumption 2 (Density interpretation). The loss functionsℓt satisfyZe−ℓt (λ;z) dz = 1(2)

for t = 1, 2, . . ., and ℓ0 satisfiesZe−ℓ0 (w) dw = 1.

(3)

In view of (1), ℓ0 does not contribute significantly to the
cumulative loss as T increases, and it can be specified by
the user on the basis of convenience. The condition in (2)is more crucial, and requires that the exponent of the loss
function ℓt (λ; ·) behaves exactly as a probability density.
3.2. A Bayesian Framework
Loss functions ℓt that satisfy Assumptions 1 and 2 can beused to define pt (g|λ) = e−ℓt (λ;g) as a likelihood function
for g, parametrized by λ and p0 (λ) = e−ℓ0 (λ) , as a priorfor the parameter λ. Our update scheme for λ then hinges
on calculating the posterior mean for λ at each step. A
summary of this algorithm is given in Algorithm 1.
Algorithm 1 Bayesian Ensemble
Input: streaming samples {(xt , y t )}Tt=1
online weak learners {cti (x)}mi=1chosen likelihood p(g|λ) and prior p(λ)
Initialize: hyper-parameters for p(g|λ) and p(λ)
for t = 1 to T do∀i, compute git = g(cti (xt ), y t )update for the posterior distribution of λ :tQp(λ|g1:t ) ∝ p(gt |λ)p(λ|g1:t−1 ) ∝p(gs |λ)p(λ)
t

s=1
t

update the weak learners using (x , y )end for

Algorithm 1 offers the following desirable property.

Theorem 1. Under Assumptions 1 and 2, the Bayesian
scheme in Algorithm 1 produces a posterior distributionpT (λ|g1:T ) satisfying the asymptotic normality property
1/2d∇2 LT (λ∗T ; g1:T )(λT − λ∗T ) → N (0, 1)(4)where λT is interpreted as a random variable with distrid
bution pT (λ|g1:T ), and → denotes convergence in distribution. Furthermore, under the uniform integrability condition supT EλT |g1:T kλT − λ∗T k1+ǫ< ∞ for some ǫ > 0,1
we have!
1∗(5)|EλT |g1:T [λT ] − λT | = o
1/2
σTwhere EλT |g1:T [·] denotes the posterior expectation and σTis the minimum eigenvalue of the matrix ∇2 LT (λ∗T ; g1:T ).
The idea behind (4) comes from a classical techniquein Bayesian asymptotics known as the Laplace method(Cox & Hinkley, 1974). Theorem 1 states that given theloss structure satisfying Assumptions 1 and 2, the posterior distribution of λ under our Bayesian update scheme
provides an approximation to the minimizer λ∗T of the cumulative loss at time T , as T increases, by tending to a normal distribution peaked at λ∗T with shrinking variance. The
bound (5) states that this posterior distribution can be summarized using the posterior mean to give a point estimate of
λ∗T . Moreover, note that λ∗T is the global, not merely local,
minimizer of the cumulative loss. This approximation of
global optimum highlights a key advantage of the Bayesian
scheme over other methods such as stochastic gradient descent (SGD), which only find a local optimum.
The next theorem states another benefit of our Bayesian
scheme over standard SGD. Supposing that SGD does indeed converge to the global optimum. Even so, it turns outthat the Bayesian scheme converges faster than standard
SGD under the assumption of i.i.d. training samples.
Theorem 2. Suppose Assumptions 1 and 2 hold. Assume
also that ℓt (λ; g) = ℓ(λ; g) are identical across t and gt
are i.i.d., with E[ℓ(λ; g)] < ∞ and E[ℓ(λ; g)2 ] < ∞. The
Bayesian posterior mean produced by Alg. 1 converges toargminλ E[ℓ(λ; g)] strictly faster than standard SGD (supposing it converges to the global minimum), given by
λT +1 ← λT − ǫT K∇ℓ(λT ; gT )(6)

in terms of the asymptotic variance, except when the step
size ǫT and the matrix K is chosen optimally.
In Theorem 2, by asymptotic variance we mean the following: it turns out that both the posterior mean and the
update from SGD possess versions of the central limit the√dorem, in the form T (λT − λ∗ ) → N (0, Σ) where λ∗ =

A Bayesian Framework for Online Classifier Ensemble

argminλ E[ℓ(λ; g)]. Our comparison is on the asymptotic
variances Σ: the smaller Σ is, the smaller√ the multiplicative
constant in the rate of convergence 1/ T .
The result follows from first comparing central limit theorems for the minimizer of cumulative loss λ∗T and the standard SGD update in (6), and secondly, from the relation(5), which states that the difference between the posteriormean and λ∗T decreases at a rate faster than the central limit
theorem, and hence is asymptotically negligible.

4. Loss Functions, Likelihoods and Priors
We first discuss in depth a simple and natural choice ofloss function and its corresponding likelihood function andprior, which are also used in our experiments in Section 5.
Then we briefly give examples of other loss functions that
also fit into our framework.
4.1. Exponential Likelihood and Gamma Prior

m
X
i=1

λi gi −mX

log λi(7)

i=1

The motivation for (7) is straightforward: it is the sum of
individual loss each weighted by λi . The extra term log λiprevents λi from approaching zero, the trivial minimizer
for the first term. The parameter θ specifies the trade-off
between the importance of the first and the second term.
This loss function satisfies Assumptions 1 and 2. In particular, the Hessian of LT turns out to not depend on g 1:T ,therefore all conditions of Assumption 1 can be verified
easily. For Assumption 2, the exponent of the negation of
the loss function in (7), plus a constant term m log θ, which
does not affect the loss minimization, integrates to 1.
Using the discussion in Section 3.2, we choose the exponential likelihoodp(g|λ) =mY(θλi )e−θλi gip(λ|g1:t ) ∝mY(λi )α+t−1 e−(β+θPtss=1 gi )λi

i=1

Therefore the posterior mean for each λi is
α+tP
β + θ ts=1 gis

We use the following prediction rule at each step:mmP 1 if P
λi gi (x, −1)
λi gi (x, 1) ≤
y=
i=1
i=1

−1
otherwise

(10)

(11)

where each λi is the posterior mean given by (10). For thissetup, Algorithm 1 can be cast as Algorithm 2 below, whichis to be implemented in the numerical section.
Algorithm 2 Closed-form Bayesian Ensemble

For any t, considerℓt (λ; g) = θ

Now, under conjugacy of (8) and (9), the posterior distribution of λ after t steps is given by the Gamma distribution

(8)

i=1

Input: streaming samples {(xt , y t )}Tt=1
online weak learners {cti (x)}mi=1
Initialize: parameters θ for likelihood (8) and parameters α, β for prior (9)for t = 1 to T do∀i, compute git = g(cti (xt ), y t ), where g is logistic
loss function
update the posterior mean of λ by (10)update the weak learners according to the particular
choice of online weak learnermake prediction by (11) for next incoming sample
end for
The following bound provides further understanding of theloss function (7) and the prediction rule (11), by relating
their use with a guarantee on the prediction error:
Theorem 3. Suppose that gt are i.i.d., so that λ∗T converges to λ∗ := argminλ E[ℓ(λ; g)] for ℓ defined in (7).
The prediction error using rule (11) with λ∗ is bounded by
p−1

To facilitate computation, we employ the Gamma prior:p(λ) ∝

m
Y

λα−1
e−βλi
i

(9)

i=1

where α and β are the hyper shape andPrate parameters.
mCorrespondingly,
we pick ℓ0 (λ) = β i=1 λi − (α −Pm1) i=1 log λi . To be concrete, the cumulative loss in (1)(disregarding the constant terms) is
!
m
m
T
m
m
X
X
X
X
X
t
log λi
λi gi −
θlog λi +λi −(α−1)
β
i=1

i=1

t=1

i=1

i=1

−1  p
! p−1
1
g
(x,
−y)
i

P(x,y) (error) ≤ m p E(x,y) 
E[g
(x,
y)]
i
i=1





m
X

(12)

for any p > 1.
The proof, given in the Appendix, provides a bound forthe long-run prediction error under stationary environment. To make sense of this result, note that the quantity
1
E[gi (x,y)] gi (x, −y) can be interpreted as a performance indicator of each weak classifier, i.e. the larger it is, the better the weaker classifier is, since a good classifier should

A Bayesian Framework for Online Classifier Ensemble

have a small loss E[gi (x, y)] and correspondingly a largegi (x, −y). As long as there exists some good weak classiP
gi (x,−y)fiers among the m choices, m
i=1 E[gi (x,y)] will be large,
which leads to a small error bound in (12).

+i=1In Section 5 we will see that this simple choice of loss function and Bayesian update scheme lead to superior empiricalperformance compared with other methods.
4.2. Other Examples
Note that while our simple choice of (7) can be directly
minimized, this is not true in general. We now give a few
other examples of acceptable ensemble loss functions.
1. The loss functionℓt (λ; g) =
+

m
X

i=1
m
X

(1 − λi ) log gi + θ

i=1

m
X

gi

i=1
m
X

log Γ(λi ) − (log θ)

λi

i=1

where θ > 0 is a parameter, corresponds to the product of Gamma likelihood given byp(g|λ) =mY

θλi λi −1 −θgige
Γ(λi ) i
i=1

A conjugate prior for λ is available, in the formp(λ) ∼mY
aλi −1 θcλi

i=1

Γ(λi )b

where a, b, c > 0 are hyper parameters.
2. We can generalize the ensemble weights to include
two parameters λi = (αi , βi ). In this case, we may
define the loss function asmm
X
X(1 − αi ) log gi
βi g i +ℓt (α, β; g) =
i=1

i=1

log Γ(αi ) −mX

αi log βii=1with the following Gamma likelihood

Finally, in correspondence to Theorem 2, the SGD for (7)is written as


1
γ
t
t
θg
−
(13)
λt+1
=
λ
−
i
i
i
t
λti
where γ is a parameter that controls the step size. The following result is a consequence of Theorem 2 (a proof forthis particular case appears in the Appendix).
Theorem 4. Suppose that gt are i.i.d., and 0 <E(x,y) [gi (x, y)] < ∞ and V ar(x,y) (gi (x, y)) < ∞. For
each λi , the posterior mean given by (10) always has arate of convergence at least as fast as the SGD update (13)in terms of asymptotic variance. In fact, it is strictly betterin all situations except when the step size parameter γ in(13) is set optimally a priori.

mXp(g|α, β) =mYβiαi αi −1 −βi gi
ge
Γ(αi )
i=1

A conjugate prior is available for α and β jointlyp(α, β) ∼mYpαi −1 e−βi qi=1

Γ(αi )r βi−αi swhere p, q, r, s are hyper parameters.

5. Experiments
We report two sets of experiments on binary classification
benchmark datasets1 . In the first set of experiments, weevaulate our scheme’s performance vs. three baseline methods, given static pre-trained weak learners. In the second
set of experiments, we compare with leading online bosting
methods, following the setup of (Chen et al., 2012).
Following (Chen et al., 2012), we report experiments using
two different weak learners: Perceptron and Naive Bayes.
In every trial, each ensemble method is given 100 weaklearners and the average error rate is reported over 5 random trials of different orders of each dataset.
In all experiments, we have set the hyperparameters of our
method α = β = 1 and θ = 0.1. From the expressionof posterior mean (10), the prediction rule (11) is unrelated
to the values of α, β and θ in long term. In experiments,
we also find that our method achieves stable results with respect to settings of these parameters. However, the stochastic gradient descent baseline (SGD) (13) is sensitive to θ;
therefore, use the same value θ = 0.1 in our method.
5.1. Comparison with Baseline Methods
We compare our online ensemble method with three baseline methods, using two different weak learners: P ERCEP TRON and NAIVE BAYES . The first baseline is a single
Perceptron/Naive Bayes classifier. The second baseline(VOTING) is the uniform ensemble of weak learners. The
third baseline (SGD) is the ensemble method with ensemble weights estimated by stochastic gradient descent (13).
O URS is our proposed Bayesian ensemble method. The
same static weak learners are shared by all ensemble methods. Each data set is split into training and testing sets foreach random trial, where a training set contains no morethan 10% of the total amount of data. In order to makeweak learners divergent, a weak learner uses a randomly1

http://www.csie.ntu.edu.tw/˜cjlin/libsvmtools/datasets/

A Bayesian Framework for Online Classifier Ensemble

Table 1. Error rate for our method vs baselines, using online Perceptron/Naive Bayes weak learners.
P ERCEPTRON WEAK LEARNERDATA SETH EARTB REAST-C ANCER
AUSTRALIAN
D IABETESG ERMANS PLICEM USHROOMSI ONOSPHERES ONARSVM GUIDE 3# EXAMPLES
270
683
693
768
1000
3175
8124
351
208
1284

P ERCEPTRON
0.287
0.062
0.212
0.356
0.359
0.393
0.120
0.279
0.414
0.385

VOTING
0.275
0.052
0.209
0.339
0.337
0.371
0.104
0.260
0.400
0.437

sampled subset of data features as input for both training
and testing. The first baseline always uses all the features.
Classifier error rates for this experiment are shown in Table 1. Our proposed method consistently performs the best
for all datasets. Its superior performance against the voting
baseline is consistent with the asymptotic convergence result given by Theorem 1. Its superior performance against
the SGD baseline is consistent with the convergence rate
analysis given by Theorem 4. To better see this convergence rate difference, we produced plots of the error rate
between our method and the SGD baseline, as online learning progresses (see supplemental material).

SGD
0.261
0.051
0.167
0.321
0.334
0.331
0.102
0.257
0.392
0.414

NA ÏVE BAYES WEAK LEARNER
O URS
0.249
0.041
0.143
0.293
0.323
0.317
0.078
0.249
0.388
0.332

NA ÏVE BAYES
0.249
0.048
0.248
0.299
0.348
0.169
0.032
0.199
0.306
0.311

VOTING
0.214
0.044
0.241
0.284
0.327
0.174
0.049
0.207
0.305
0.299

SGD
0.216
0.043
0.240
0.283
0.315
0.169
0.047
0.201
0.304
0.281

O URS
0.210
0.039
0.225
0.278
0.312
0.160
0.026
0.190
0.300
0.240

given that our method only focuses on optimizing the ensemble weights, each incoming sample is treated equally inthe update of all weak learners, while all three online boosting methods adopt more sophisticated weighted update of
weak learners, where the sample weight is dynamically adjusted during each round of update. Secondly, in order tomake weak learners different from each other, our weaklearners use only a subset of input features, while weaklearners of competing methods use all features and updatethem differently. As a result, the weak learners used byour method are actually weaker than in competing methods. Nevertheless, our method often compares favorably.

5.2. Comparison with Online Boosting Methods

6. Future WorkWe further compare our method with three representative online boosting methods: O ZA B OOST (Oza & Russell,2001), OGB OOST is the online GradientBoost method proposed by (Leistner et al., 2009), and OSB OOST is the online Smooth-Boost proposed by Chen et al. (2012). Our
method is trained and compared following their setup.
However, we discard the “Ijcnn1” and “Web Page” datasetsfrom the tables of (Chen et al., 2012), because they arehighly biased with portions of positive samples around 0.09
and 0.03 respectively, and even a naive “always negative”
classifier achieves a comparable performance.

This work can be viewed as an initial attempt to explore the proposed Bayesian framework in the context
of online learning of classifier ensembles. Potential followup works include the analysis of sequential Monte
Carlo (Doucet & Johansen, 2009) for non-closed-form
Bayesian update, the extension of our analysis to nonstationary environments, the application of our framework
to more general ensemble rules, and comparison studies
between our method and some more sophisticated SGDbased schemes, such as Polyak-Ruppert averaging.

The error rates for this experiment are shown in Tables 2
and 3. Our method consistently outperforms competing
methods for the Perceptron weak learner and performs
among the best for the Naive Bayes weak learner. It is
worth noting that our method is the only one that outperforms the baseline in all data sets, which further confirms
the effectiveness of the proposed ensemble scheme.
We also note that despite our best efforts to align both the
weak learner construction and experiment setup with competing methods (Chen et al., 2012; Chen, 2013), there are
inevitably differences in weak learner construction. Firstly,

Acknowledgment: This work was supported in part by US
NSF Grants 0910908 and 0965579.

A. Appendix
A.1. Proof of Theorem 1
Proof. The convergence in (4) follows from Theorem 2.1
in (Chen, 1985). The first condition in Assumption 1 isequivalent to conditions (P1) and (P2) therein, while thesecond and third conditions correspond to (C1) and (C2).
The last condition is equivalent to (C3.1), which then implies (C3) there to invoke its Theorem 2.1 to conclude (4).

A Bayesian Framework for Online Classifier Ensemble

Table 2. Error rate using online Perceptron weak learner, for our method vs methods as reported in (Chen et al., 2012).
DATA SET# EXAMPLESP ERCEPTRONO ZA B OOSTOGB OOSTOSB OOST

O URS

270
683
693
768
1000
3175
8124
48842
4885655810120.24890.05920.20990.32160.3256
0.27170.01480.20930.2096
0.34370.23560.05010.20120.31690.33640.27590.00800.20450.21700.34490.22670.04450.19620.33130.31420.26250.00680.20800.2241
0.34820.2356
0.04660.18720.31850.31480.26050.00600.19940.20750.33340.21340.04190.16550.30980.31050.25840.00620.16820.19340.3115

H EARTB REAST-C ANCER
AUSTRALIAN
D IABETESG ERMANS PLICEM USHROOMSA DULTC OD -RNAC OVERTYPE

Table 3. Error rate using online Naive Bayes weak learner, for our method vs methods as reported in (Chen et al., 2012). For “Cod-RNA”
our implementation of the Naive Bayes baseline was unable to duplicate the reported result; ours gave 0.2555 instead.
DATA SET# EXAMPLES

NAIVE BAYESO ZA B OOSTOGB OOSTOSB OOST

O URS

270
683
693
768
1000
3175
8124
48842
4885655810120.19040.04740.17510.26640.29880.25200.00760.20010.2206∗
0.35180.25700.06350.21330.30910.3206
0.15630.00490.19120.07960.32930.30370.10040.28260.32920.35980.18630.02290.18780.05680.37320.20590.04890.18490.26220.27300.13700.00290.1581
0.05810.36340.17550.04080.16110.2467
0.26670.13440.00540.16580.25520.3269H EARTB REAST-C ANCER
AUSTRALIAN
D IABETESG ERMANS PLICEM USHROOMSA DULTC OD -RNAC OVERTYPE

To show the bound (5) we take expectation on (4) to get
1∇2 LT (λ∗T ; g1:T ) 2 (EλT |g1:T [λT ] − λ∗T ) → 0 (14)which is valid because of the uniform integrability condition supT EλT |g1:T kλT − λ∗T k1+ǫ< ∞ (Durrett, 2010).
1
− 1∗Therefore, EλT |g1:T [λT ]−λT = ∇2 L(λ∗T ; g1:T ) 2 wT
where wT = o(1) by (14). But then

≤
≤

− 1
∇2 LT (λ∗T ; g1:T ) 2 wT

C
1/2
σT

kwT k1 = o



1

1

−
∇ LT (λ∗T ; g1:T ) 2
2

1

1/2
σT

!1

kwT k1

where k·k1 when applied to matrix is the induced L1 -norm.
This shows (5).
A.2. Proof of Theorem 2
Proof. The proof follows by combining (5) with established central limit theorems for sample average approximation (Pasupathy & Kim, 2011) and stochastic gradientdescent (SGD) algorithms. First, let z(λ) := −E[ℓ(λ; g)],and λ∗ := argminλ z(λ). The quantity λ∗T can be viewed
PT
as the minimizer of T1 t=1 ℓ(λ; gt ) (the initial loss function can be argued to be negligible after dividing by T ).

Then Theorem 5.9 in (Pasupathy & Kim, 2011) stipulates√dthat T (λ∗T − λ∗ ) → N (0, Σ), whereΣ = (∇2 z(λ))−1 V ar(∇ℓ(λ; g))(∇2 z(λ))−1(15)

and V ar(·) denotes the covariance matrix.
PT2∗t
Now since ∇2 LT (λ∗T ; g1:T ) =t=1 (∇ ℓ(λT ; g )) and
P
T
1
2
∗
t
2
∗
t=1 (∇ ℓ(λT ; g )) → E[∇ ℓ(λ ; g)] by law of large
Tnumbers (Durrett, 2010), we have ∇2 LT (λ∗T ; g1:T ) =Θ(T ). Then the bound in (5) implies that |EλT |g1:T [λT ] − 
λ∗T | = o √1T . In other words, the difference between√
posterior mean and λ∗T is of smaller scale than 1/ T .
By Slutsky Theorem (Serfling, 2009), this implies that√d
T (EλT |g1:T [λT ] − λ∗ ) → N (0, Σ) also.
On the other hand, for SGD (6), it is known(e.g. (Asmussen & Glynn, 2007)) that the optimal step size
parameter value is ǫT = 1/T and K = ∇2 z(λ), in whichcase the central limit theorem for the update λT will be√dgiven by T (λT − λ∗ ) → N (0, Σ) where Σ is exactly(15). For other choices of step√ size, either the convergence
rate is slower than order 1/ T or the asymptotic variance,
denoted by Σ̃, is such that Σ̃− Σ is positive definite. Therefore, by comparing the asymptotic variance, the posteriormean always has a faster convergence unless the step sizein SGD is chosen optimally.

A Bayesian Framework for Online Classifier Ensemble
V ar(gi (x, y))−→ N 0, 2
θ (E[gi (x, y)])4

A.3. Proof of Theorem 3
Proof. Suppose λ is used in the strong classifier (11). Denote I(·) as the indicator function. Consider
# Z
"m
m
hX
X
λi gi (x, 1)
λi gi (x, y) =E(x,y)i=1

i=1

P (y = 1|x) +

m
X
i=1

≥

Z h

I

m
X

i
λi gi (x, −1)P (y = −1|x) dP (x)λi gi (x, 1) >i=1

gi (x, 1)P (y = 1|x) + ImX!

λi gi (x, −1)

i=1
m
X

λi gi (x, 1) <

·

≥

I

λi gi (x, 1) >

m
X
i=1

i=1

gi (x, −1)P (y = 1|x) + I!

λi gi (x, −1)

m
X

·

λi gi (x, 1) <

where

m
X

i=1
m
X

λi
λi

i=1

i=1

m
i
 X
λi gi (x, 1)P (y = −1|x) dP (x)gi (x, −1) ·
i=1

=

"

E(x,y) I(error)

m
X
i=1

i

λi

i=1
m
X

i=1

m
X

i

If the step size γ > 2z′′1(λ∗ ) , the update scheme (13) will

λi

m
X

m
i
 X
λi gi (x, −1)P (y = −1|x) dP (x)gi (x, −1) ·Z hFor the stochastic gradient descent scheme (13), it would be
useful to cast the objective function as zi (λi ) = E[θλi gi −log λi ]. Let λ∗i = argminλ zi (λ) which can be directly
1. Then zi′′ (λ∗i ) = λ1∗ 2 = θ2 (E[gi (x, y)])2 .
solved as θE[gi]generate λTi that satisfies the following central limit theorem (Asmussen & Glynn, 2007; Kushner & Yin, 2003)√d(17)
T (λTi − λ∗i ) → N (0, σi2 )

i=1

i=1

(16)

#

λi gi (x, −y)

Z ∞



1
e
γ V ar θgi (x, y) − ∗ ds
λi
0
(18)
and θgi (x, y) − λ1∗ is the unbiased estimate of the graσi2 =(1−2γzi′′ (λ∗i ))s 2idient at the point λ∗i . On the other hand, λTi − λ∗i =ωp ( √1T ) if γ ≤ 2z′′1(λ∗ ) , i.e. the convergence is slowerithan (17) asymptotically and so we can disregard thiscase (Asmussen & Glynn, 2007). Now substitute λ∗i =1
θE[gi ] into (18) to obtainZ ∞∗σi2 = θ2 γ 2 V ar(gi (x, y))e(1−2γ/λi )s ds
0=θ2 γ 2 V ar(gi (x, y))θ2 γ 2 V ar(gi (x, y))=2γ/λ∗i − 12γθ2 (E[gi (x, y)])2 − 1−1 −(p−1) and let γ = γ̃/θ 2 , we get! p−1≥ P (error)p E(x,y) 
λi gi (x, −y)γ̃ 2 V ar(gi (x, y))(19)
σi2 = 2i=1
θ (2γ̃(E[gi (x, y)])2 − 1)
the last inequality holds by reverse Holder inequality2
1
if γ̃ > 2z′′θ(λ∗ ) = 2(E[gi (x,y)])2.
(Hardy et al., 1952). So
i
#! p1
"m
We are now ready to compare the asymptotic variance inX
λi gi (x, y)P (error) ≤E(x,y)(16) and (19), and show that for all γ̃, the one in (16) is
i=1
smaller. Note that this is equivalent to showing thatp−1
−1  p
! p−1
mγ̃ 2 V ar(gi (x, y))V ar(gi (x, y))X≤· E(x,y) 
λi gi (x, −y)θ2 (E[gi (x, y)])4
θ2 (2γ̃(E[gi (x, y)])2 − 1)





m
X

i=1

and the result (12) follows by plugging in λi =1
θE(x,y) [gi (x,y)] for each i, the minimizer of E[ℓ(λ; g)],which can be solved directly when ℓ is in the form (7).
A.4. Proof of Theorem 4

Proof. Since for each i, git are i.i.d., the sample meanP
(1/T ) Tt=1 git follows a central limit theorem. It can beargued using the delta method (Serfling, 2009) that the posterior mean (10) satisfies
!
√
α+T
1
T
−
PT
θE[gi (x, y)]β + θ t=1 git

Eliminating the common factors, we have

1
γ̃ 2
≤
(E[gi (x, y)])22γ̃ − 1/(E[gi (x, y)])2
and by re-arranging the terms, we have
2

1
≥0
(E[gi (x, y)])2 γ̃ −(E[gi (x, y)])2
1
which is always true. Equality holds iff γ̃ = (E[gi (x,y)])2,
1which corresponds to γ = θ2 (E[gi (x,y)])2 .Therefore, theasymptotic variance in (16) is always smaller than (19), unless the step size γ is chosen optimally.

A Bayesian Framework for Online Classifier Ensemble

References
Asmussen, S. and Glynn, P. W. Stochastic simulation: Algorithms and analysis. Springer, 2007.
Babenko, B., Yang, M. H., and Belongie, S. Visual tracking
with online multiple instance learning. In CVPR, pp.
983–990, 2009a.
Babenko, B., Yang, M. H., and Belongie, S. A family of online boosting algorithms. In ICCV Workshops, pp. 1346–
1353, 2009b.
Cesa-Bianchi, N. and Lugosi, G. Potential-based algorithms in on-line prediction and game theory. Machine
Learning, pp. 239–261, 2003.
Chen, C. F. On asymptotic normality of limiting density
functions with bayesian implications. Journal of theRoyal Statistical Society, pp. 540–546, 1985.
Chen, S. T. personal communication, 2013.
Chen, S. T., Lin, H. T., and Lu, C. J. An online boostingalgorithm with theoretical justifications. In ICML, pp.
1007–1014, 2012.
Cox, D. R. and Hinkley, D. V. Theoretical Statistics. Chapman & Hall/CRC, 1974.

Kolter, J.Z. and Maloof, M.A. Using additive expert ensembles to cope with concept drift. In Proceedings ofthe 22nd international conference on Machine learning,pp. 449–456, 2005.
Kushner, H. J. and Yin, G. Stochastic approximation andrecursive algorithms and applications. Springer, 2003.
Laarhoven, V., JM, P., and Aarts, E. H. Simulated annealing. Springer, 1987.
Leistner, C., Saffari, A., Roth, P. M, and Bischof, H. On
robustness of on-line boosting-a competitive study. In
ICCV Workshops, pp. 1362–1369, 2009.
Liu, X. and Yu, T. Gradient feature selection for online
boosting. In ICCV, pp. 1–8, 2007.
Minku, L.L. Online ensemble learning in the presence ofconcept drift. PhD thesis, University of Birmingham,
2011.
Oza, N. C. Online ensemble learning. PhD thesis, University of California, Berkeley, 2001.
Oza, N. C. and Russell, S. Online bagging and boosting. In
AISTATS, pp. 105–112, 2001.

Doucet, A. and Johansen, A. M. A tutorial on particle filtering and smoothing: Fifteen years later. Handbook of
Nonlinear Filtering, pp. 656–704, 2009.

Pasupathy, R. and Kim, S. The stochastic root-finding
problem: overview, solutions, and open questions. ACM
Transactions on Modeling and Computer Simulation, 21(3):19, 2011.

Durrett, R. Probability Theory and Examples. Cambridge
Series in Statistical and Probabilistic Mathematics, 4thedition, 2010.

Pelossof, R., Jones, M., Vovsha, I., and Rudin, C. Online coordinate boosting. In ICCV Workshops, pp. 1354–
1361, 2009.

Grabner, H. and Bischof, H. On-line boosting and vision.
In CVPR, pp. 260–267, 2006.

Saffari, A., Godec, M., Pock, T., Leistner, C., and Bischof,
H. Online multi-class lpboost. In CVPR, pp. 3570–3577,
2010.

Grabner, H., Leistner, C., and Bischof, H. Semi-supervised
on-line boosting for robust tracking. In ECCV, pp. 234–
247. 2008.
Grbovic, M. and Vucetic, S. Tracking concept change withincremental boosting by minimization of the evolving
exponential loss. In Machine Learning and Knowledge
Discovery in Databases, pp. 516–532. 2011.
Hardy, G. H., Littlewood, J. E., and Pólya, G. Inequalities.
Cambridge university press, 1952.
Hoeting, J. A., Madigan, D., Raftery, A. E., and Volinsky,
C. T. Bayesian model averaging: a tutorial. Statisticalscience, pp. 382–401, 1999.
Kolter, J. Z. and Maloof, M. A. Dynamic weighted majority: An ensemble method for drifting concepts. The
Journal of Machine Learning Research, pp. 2755–2790,
2007.

Schapire, Robert E. Drifting games. Machine Learning,pp. 265–291, 2001.
Serfling, R. J. Approximation theorems of mathematicalstatistics. Wiley. com, 2009.
Wang, H., Fan, W., Yu, P.S., and Han, J. Mining conceptdrifting data streams using ensemble classifiers. In
SIGKDD, pp. 226–235, 2003.