Using Additive Expert Ensembles to Cope with Concept Drift

Jeremy Z. Kolter and Marcus A. Maloof{jzk, maloof}@cs.georgetown.edu
Department of Computer Science, Georgetown University, Washington, DC 20057-1232, USA

Abstract
We consider online learning where the target concept can change over time. Previous work on expert prediction algorithms hasbounded the worst-case performance on any
subsequence of the training data relative tothe performance of the best expert. However,
because these “experts” may be difficult toimplement, we take a more general approachand bound performance relative to the actual performance of any online learner on thissingle subsequence. We present the additive
expert ensemble algorithm AddExp, a new,general method for using any online learnerfor drifting concepts. We adapt techniques
for analyzing expert prediction algorithms toprove mistake and loss bounds for a discrete
and a continuous version of AddExp. Finally, we present pruning methods and empirical results for data sets with concept drift.

1. Introduction
We consider the online learning scenario where an algorithm is presented with a series of labeled examples,
S = {xt , yt }, for t = 1, 2, . . . , T . At each time step, thealgorithm outputs a class prediction, ŷt , for the givenfeature vector xt , then updates its hypothesis based on
the true class yt . In the discrete case, yt and ŷt are ina finite set of classes Y , and under the mistake boundmodel (Littlestone, 1988), one bounds the number of
mistakes an algorithm makes on some target concept.
In the continuous case, yt , ŷt ∈ [0, 1], and one bounds
the maximum loss suffered by the algorithm – we focus on the absolute loss function L(ŷt , yt ) = |ŷt − yt |.
In addition, we allow for the target concept to changeover time.
Certain expert prediction algorithms (Littlestone &Warmuth, 1994; Herbster & Warmuth, 1998) proAppearing in Proceedings of the 22 nd International Conference on Machine Learning, Bonn, Germany, 2005. Copyright 2005 by the author(s)/owner(s).

vide theoretical performance guarantees under concept
drift. These algorithms predict based on the adviceof several prediction strategies, called experts. Whentrained on a series of different concepts, these algorithms perform “almost as well” as the best expert
on each concept – the assumption being that different
experts perform best on different concepts. In practice, however, such algorithms can be difficult to implement. If the experts are fixed prediction strategies,
then they are limited to those that one can delineate
prior to any training. Alternatively, if the experts arelearning algorithms, then they must be able to adapt
to concept drift individually, since all are trained overthe entire example series.
In this paper, we take a different, more adaptive approach: we bound our algorithm’s performance overchanging concepts, not relative to the performance of
any abstract expert, but relative to the actual performance of an online learner trained on each concept
individually. Our algorithm, called Additive Expert(AddExp), maintains what we call an additive expert
ensemble. It is similar to expert prediction algorithms,
except that new experts can be added during the online learning process. We adapt techniques from Littlestone and Warmuth (1994) and Freund and Schapire(1997) to prove performance bounds under the mistake bound and online loss models. The primary result of the paper is, when trained on a series of changing concepts, AddExp makes O(m) mistakes on any
concept, where m is the number of mistakes that thebase learner makes when trained only on this single
concept. Similarly for the continuous case, AddExp
will suffer a loss of O(`) on any concept, where ` isthe loss of the base learner when trained only on thissingle concept. We present pruning methods so the algorithm can be efficient on complex data sets. Finally,
we present empirical results.

2. Background and Related Work
Much work on expert prediction can be traced back to
the Weighted Majority (WM) algorithm (Littlestone& Warmuth, 1994) and Vovk’s (1990) work on aggre-

Using Additive Expert Ensembles to Cope with Concept Drift

gating strategies. Cesa-Bianchi et al. (1997) propose
a general algorithm for randomized predictions andprove lower bounds on the net loss of any expert prediction algorithm. Freund and Schapire (1997) propose the Hedge algorithm, which uses these methods for an online-allocation problem. Haussler et al.
(1998) and Vovk (1998) generalize previous results togeneral-case loss functions. Separately, several algorithms have been proposed to deal with concept drift(e.g., Kolter & Maloof, 2003; Schlimmer & Granger,
1986; Street & Kim, 2001; Widmer & Kubat, 1996).
There has also been theoretical analysis (e.g., Helmbold & Long, 1994).
Expert prediction algorithms have been applied specifically to the problem of concept drift. A variant of
the original WM algorithm, WML (Littlestone & Warmuth, 1994) adds mechanisms that allow new experts
to become dominant in constant time. Blum (1997)
implemented a version of WM for a calendar scheduling task that exhibits concept drift. Herbster and Warmuth (1998) generalize the loss bounds of such expert
predictions algorithms to general-case loss functions,and Monteleoni and Jaakkola (2004) have recently extended this work by allowing the algorithm to adjust
parameters during online learning to improve performance. Bousquet and Warmuth (2003) analyze a special case where the best experts come from a small
subset of the ensemble.
Additive expert ensembles were introduced by Kolter
and Maloof (2003) with the Dynamic Weighted Majority (DWM) algorithm, which shares many similarities
with the AddExp algorithm we present in this paper.
DWM was shown to perform well in situations withconcept drift, but the evidence for this performancewas entirely empirical, and in fact DWM’s weighting
scheme makes it impossible to bound performance inthe worst case. DWM handles only discrete classes,
can become unstable in noisy settings, and has a pruning mechanism that provides no guarantee as to thenumber of experts created. The AddExp algorithm,
as we will describe, allows for theoretical analysis, generalizes to regression tasks, provides pruning mechanisms that cap the number of experts, and achieves
better empirical results than DWM.

3. AddExp for Discrete Classes
In this section, we present the AddExp.D algorithm(see Figure 1) for handling discrete class predictions.
As its concept description, AddExp.D maintains an
ensemble of predictive models, referred to as experts,
each with an associated weight. Experts use the samealgorithm for training and prediction, but are created

Algorithm AddExp.D({x, y}T , β, γ)Parameters:{x, y}T : training data with class y ∈ Y
β ∈ [0, 1]: factor for decreasing weightsγ ∈ [0, 1]: factor for new expert weight
Initialization:
1. Set the initial number of experts N1 = 1.
2. Set the initial expert weight w1,1 = 1.
For t = 1, 2, . . . , T :1. Get expert predictions ξt,1 , ..., ξt,Nt ∈ Y
2. Output prediction:NtXŷt = argmaxc∈Ywt,i [c = ξt,i ]i=13. Update expert weights:

wt+1,i = wt,i β [yt 6=ξt,i ]4. If ŷt 6= yt then add a new expert:
Nt+1 = Nt + 1
Nt
X
wt,i
wt+1,Nt+1 = γ
i=15. Train each expert on example xt , yt .

Figure 1. AddExp for discrete class predictions.

at different time steps. The performance element of
the algorithm uses a weighted vote of all the experts.
For each possible classification, the algorithm sums theweights of all the experts predicting that classification,and predicts the classification with the greatest weight.
The learning element of the algorithm first predicts
the classification of the training example. The weights
of all the experts that misclassified the example aredecreased by a multiplicative constant β. If the overall
prediction was incorrect, a new expert is added to theensemble with weight equal to the total weight of theensemble times some constant γ. Finally, all experts
are trained on the example.
If trained on a large amount of data, AddExp.D has
the potential to create a large number of experts. However, since this does not affect the theoretical mistakeor loss bounds of the algorithm, we will not deal withthis issue until Section 5, where we discuss pruning.
3.1. Analysis
Here we analyze the performance of AddExp.D
within the mistake bound model (Littlestone, 1988) byadapting the methods used by Littlestone and Warmuth (1994) to analyze the WM algorithm. As thisis a worst-case analysis, we allow for an adversary tochoose, at any time step, whether any given expert
is going to make a mistake. This may seem odd because, after all, not only do these experts all employ

Using Additive Expert Ensembles to Cope with Concept Driftthe same learning algorithm, they are also all trained
from the same data stream – the only difference being that some experts are trained on a larger subsetof the stream than other experts. However, if we consider training noise and the sampling effects present inreal-world problems, it becomes difficult to conclude
anything about the performance of the different experts. Therefore we perform this analysis in the mostgeneral case.
We denote the total P
weight of the ensemble at timeNt
step t to be Wt =i=0 wt,i . We also let Mt be
the number of mistakes that AddExp.D has madethrough time steps 1, 2, . . . , t − 1. The bound rests on
the fact that the total weight of the ensemble decreases
exponentially with the number of mistakes.
Theorem 3.1 For any time steps t1 < t2 , if we stipulate that β + 2γ < 1, then the number of mistakesthat AddExp.D will make between time steps t1 andt2 can be bounded by
M t2 − M t1 ≤log(Wt1 /Wt2 ).
log(2/(1 + β + 2γ))

Proof AddExp.D operates by multiplying theweights of the experts that predicted incorrectly by
β. If we assume that a mistake is made at time stept then we know that at least 1/2 of the weight in theensemble predicted incorrectly. In addition, a new expert will be added with weight γWt . So we can boundthe weight with
Wt+1 ≤β
1 + β + 2γ
1
Wt + Wt + γWt =
Wt .
2
2
2

Applying this function recursively leads to:Wt2 ≤1 + β + 2γ Mt2 −Mt1
Wt1 .
2

Taking the logarithm and rearranging terms gives thedesired bound, which will hold since the requirementthat β + 2γ < 1 ensures that (1 + β + 2γ)/2 < 1. ¤Now suppose that the algorithm makes a mistake attime t1 , and so a new expert is added. The initial
weight of this expert will be γWt1 . Let m be the number of mistakes made by the new expert by time stept2 . The weight of the expert is multiplied by β foreach mistake it makes, so its weight at time t2 will be
γWt1 β m . Since the total weight of the ensemble must
be greater than that of any individual member,
Wt2 ≥ γWt1 β m .

(1)Corollary 3.2 For any time steps, t1 < t2 , if AddExp.D makes a mistake at time t1 – and therefore

adds a new expert to the pool – then the number of
mistakes that AddExp.D makes between time steps
t1 and t2 can be bounded by
M t2 − M t1 ≤m log(1/β) + log(1/γ),
log(2/(1 + β + 2γ))

where m is the number of mistakes that the new expert
makes in this time frame.
Proof The bound is obtained by substituting (1) into
the result of Theorem 3.1.
¤
Finally, we show how this analysis applies to concept
drift.
Corollary 3.3 Let S1 , S2 , . . . , Sk be any arbitrary
partitioning of the input sequence S into k subsequences, such that AddExp.D makes a mistake on thefirst example of each subsequence. Then for each Si ,AddExp.D makes no more than½¾
mi log(1/β) + log(1/γ)
min |Si |,log(2/(1 + β + 2γ))
mistakes, where mi is the number of mistakes made by
the base learner when trained only on Si .
Proof The follows follows by applying Corollary 3.2 toeach subsequence Si .
¤It is important to note that the requirement that AddExp.D makes a mistake on the first example of eachsubsequence is not a practical limitation, since subsequences need not correspond directly to concepts.
Consider the subsequence that begins whenever AddExp.D makes its first mistake on some concept, andends at the last example of this concept. We can boundthe performance of AddExp.D on this subsequence
relative to the performance of the base learner. And
since we know that AddExp.D made no mistakes on
the concept before the subsequence begins, this also
serves as a bound for the performance of AddExp.D
over the entire concept. Additionally, while this boundis most applicable to scenarios of sudden drift, it is by
no means limited to these situations. It only requiresthat at some point during online training, a new expert will perform better than experts trained on “old”
data, which can also happen in situations of gradualdrift.
However, there is another difficulty when considering
the theoretical performance of AddExp.D. It can beshown that the coefficient on the m term in Corollary
3.2 can never be reduced lower than 2, which can bea significant problem if, for example, the base learnermakes a mistake 20% of the time.

Using Additive Expert Ensembles to Cope with Concept Drift

Theorem 3.4 For any β, γ ∈ [0, 1],
m log(1/β) + log(1/γ)≥ 2m .
log(2/(1 + β + 2γ))
Proof (Sketch) The coefficient of m is minimized as
γ → 0, so it will always be greater thanlog(1/β).
log(2/(1 + β))
It can be shown that ln(1/x) ≥ 2(1 − x)/(1 + x) forx ∈ [0, 1]. Using this inequality to bound the numerator, and the inequality ln(1 + x) ≤ x to bound thedenominator gives the desired result. This can also beverified by plotting the function for β ∈ [0, 1].
¤
A similar situation occurs in the analysis of the original
WM algorithm. The problem is that since only half theweight of the ensemble needs to predict incorrectly inorder to make a mistake, an adversary will be able
to let the experts conspire to drive up the number ofglobal mistakes. For this reason, we shift our focus toa continuous version of the algorithm analyzed under
the online loss model. In the case of binary classes,
it is possible to use randomized prediction to obtain abound on the expected number of mistakes equivalent
to the loss bound.

4. AddExp for Continuous Classes

wt+1,i = wt,i β |ξt,i −yt |5. If |ŷt − yt | ≥ τ add a new expert:
Nt+1 = Nt + 1
NtX
wt+1,Nt+1 = γ
wt,i |ξt,i − yt |i=1

6. Train each expert on example xt , yt .

Figure 2. AddExp for continuous class predictions.

this new expert is calculated by:
wt+1,Nt+1 = γ

In this section, we present and analyze the AddExp.C
algorithm (see Figure 2) for predicting values in the interval [0,1]. The general operation of the AddExp.C
algorithm is the same as that of AddExp.D exceptthat class predictions – both the overall prediction of
AddExp.C and the predictions of each expert – are in[0, 1] rather than in a discrete set of classes Y . This necessitates other changes to the algorithm. Rather than
predicting with a weighted majority vote, AddExp.C
predicts the sum of all expert predictions, weighted bytheir relative expert weight. When updating weights,
the algorithm uses the rule
wt+1,i = wt,i β |ξt,i −yt | .

Algorithm AddExp.C({x, y}T , β, γ, τ )Parameters:{x, y}T : training data with class y ∈ [0, 1]
β ∈ [0, 1]: factor for decreasing weightsγ ∈ [0, 1]: factor for new expert weightτ ∈ [0, 1]: loss required to add a new expert
Initialization:
1. Set the initial number of experts N1 = 1.
2. Set the initial expert weight w1,1 = 1.
For t = 1, 2, . . . , T :1. Get expert predictions ξt,1 , . . . , ξt,Nt ∈ [0, 1]
2. Output prediction:
P Nt
i=1 wt,i ξt,iŷt = PNt
i=1 wt,i
3. Suffer loss |ŷt − yt |4. Update expert weights:(2)

As with other expert prediction algorithms, the following analysis also holds for a more general update function wt+1,i = wt,i Uβ (|ξt,i − yt |), for any Uβ : [0, 1] →[0, 1], where β r ≤ Uβ (r) ≤ 1 − (1 − β)r for β ≥ 0 andr ∈ [0, 1]. Whereas we previously added a new member to the ensemble whenever the global prediction
was incorrect, we now add a new member whenever
the global loss of the algorithm on that time step isgreater than some threshold τ ∈ [0, 1]. The weight ofNtX

wt,i |ξt,i − yt | .

(3)

i=1

4.1. Analysis
We adapt techniques from Littlestone and Warmuth(1994) and Freund and Schapire (1997) to analyze
AddExp.C. Again we use the notation Wt to denotethe total weight of the expert pool at time t. We let
Lt refer to the total absolute lossby the algoPsufferedt−1rithm before time t, with Lt = i=1 |ŷi − yi |.

Theorem 4.1 For any time steps t1 < t2 , if we stipulate that β + γ < 1, then the absolute loss of AddExp.C between time steps t1 and t2 can be boundedbyln(Wt1 /Wt2 )L t2 − L t1 ≤.
1−β−γProof It can be shown by a convexity argument (e.g.,
Littlestone & Warmuth, 1994, Lemma 5.1) thatβ r ≤ 1 − (1 − β)r(4)

for β ≥ 0 and r ∈ [0, 1]. At each time step AddExp.C
updates the weights according to (2) and may add a

Using Additive Expert Ensembles to Cope with Concept Driftnew expert with weight determined by (3). Combining
these equations with (4) gives
Wt+1

Nt
X

≤

Nt
X

wt,i β |ξt,i −yt | + γ

≤

Nt
X

wt,i (1 − (1 − β − γ)|ξt,i − yt |)wt,i |ξt,i − yt |

i=1

i=0

i=0

≤

Wt (1 − (1 − β − γ)|ŷ − y|) .

Applying repeatedly for t = t1 , . . . , t2 − 1 gives
Wt2 ≤ W t1

tY
2 −1

(1 − (1 − β − γ)|ŷt − yt |) .

The theorem follows by taking the natural logarithm
and using the inequality ln(1 + x) ≤ x.
¤
Now suppose that the loss at time step t1 is greaterthan
PNτt , so a new expert is added with initial weight
γ i=1
wt,i |ξt,i − yt | = γ|ŷt − yt |Wt . Let ` be the loss
that the new expert has suffered by time t2 . At time
step t2 the weight of this expert will be β ` γ|ŷt − yt |Wt .
And since the total weight of the ensemble must be
greater than any individual member, we have(5)

We use this to prove corollaries corresponding to 3.2
and 3.3 for the continuous case.
Corollary 4.2 For any time steps, t1 < t2 , if AddExp.C suffers a loss greater than τ at time t1 – andtherefore adds a new expert to the pool – then the loss
suffered by AddExp.C between time steps t1 and t2
can be bounded by
L t2 − L t1 ≤As with the discrete case, the requirement that AddExp.C suffer loss greater than τ at the first example of each subsequence is not a significant practicallimitation. It is slightly more difficult in the continuous case, since AddExp.C may continuously suffer
loss less than τ , and never add a new expert. However, since τ can be made arbitrary small, with only
a log(1/τ ) penalty, this “extra” loss suffered can be
reduced arbitrarily close to zero.
4.2. Optimizing Parameters

t=t1

Wt2 ≥ β ` γ|ŷt1 − ytt |Wt1 .

Proof The bound is obtained by applying Corollary
4.2 to each partition Si .
¤` ln(1/β) + ln(1/γ) + ln(1/τ ),1−β−γ

where ` is the loss suffered by the new expert in thistime frame.

In this section, we present methods for choosing parameters β and γ based on previous knowledge of the
problem. Specifically, if we have an upper bound `˜ on
the loss of a given expert, then we can choose β andγ so as to minimize the loss bound for AddExp.C.
However, due to the nature of the bound, it is very
difficult to optimize the parameters precisely, and so
approximations are used. Well-chosen values for β andγ result in analysis that is remarkably similar to theanalysis of WM-style algorithms.
We make use of the following lemma from Freund andSchapire (1997), slightly rewritten:
Lemma 4.4 (Freund & Schapire, 1997) q
Suppose0 ≤ A ≤ Ã and 0 ≤ B ≤ B̃. Let α = 1 +Thenp
A ln α + B≤ A + B + 2ÃB̃ .
1 − (1/α)Empirical optimization of the loss bound suggests thatthe bound reaches a minimum when γ = β/`. Using
this conjecture we can choose values for β and γ suchthat the resulting equation is an instance of Lemma
4.4. Specifically, we choose the valuesβ=

Proof The bound is obtained immediately by substituting (5) into the result of Theorem 4.1 and noticing¤that |ŷt1 − yt1 | ≥ τ .
Corollary 4.3 Let S1 , S2 , . . . , Sk be any arbitrary
partitioning of the input sequence S such that at thefirst example in each subsequence, AddExp.C suffers
loss greater than τ . Then for each subsequence Si ,AddExp.C suffers loss no greater than½¾
`i ln(1/β) + ln(1/γ) + ln(1/τ )min |Si |,,1−β−γ
where `i is the loss suffered by the base learner whentrained only on Si .

2B̃/Ã.

`˜
1and γ =,˜˜˜˜(` + 1)g(`)(` + 1)g(`)

(6)

where
˜ =1+
g(`)

q

2(ln∗ (`˜ + 1) + ln(1/τ ))/(`˜ + 1) .1(7)

Substituting these values into the bound from Corollary 4.2 satisfies the conditions of Lemma 4.4 with
1

Here we define the functionln∗ (x) = x ln x − (x − 1) ln(x − 1).

We use the name ln∗ since this function is asymptoticallysimilar to the ln function, and can be bounded by ln∗ x ≤ln x + 1 for x > 1. The difference is that ln∗ x approaches
0 as x approaches 1, so the bound is stronger.

Using Additive Expert Ensembles to Cope with Concept Drift˜Ã = `˜ + 1, B̃ = ln∗ (`˜ + 1) + ln(1/τ ) and α = g(`).
So we can obtain the new loss bound,L t2 − L t1≤

` + 1 + ln∗ (` + 1) + ln(1/τ ) +q2(`˜ + 1)(ln∗ (`˜ + 1) + ln(1/τ )) .

If we choose `˜ and τ such that `˜ ≥ 1/τ , then the net
lossof AddExp.C
over this interval, Lt2 − Lt1 − `, is´³p˜˜` ln ` . This bears a strong resemblance to theObound proven by Cesa-Bianchi et al. (1997) and others
for³p
the worst-case
net loss of WM-style algorithms:´
˜l ln n , where n in the number of experts.
O

5. Pruning
Until now, we have ignored issues of efficiency. AddExp can potentially add a new expert every time step,leading to inefficiency as the length of the input grows.
In this section, we present two pruning techniques, onethat has theoretical guarantees but which may be impractical, and one that performs well in practice but
which has no theoretical guarantees.
Ideally, pruning removes unnecessary experts from theensemble while keeping the best experts. If done correctly, it will not affect the mistake or loss bounds
proven in Sections 3 and 4. These bounds depended
only on the fact that the weight of the ensemble decreases over time, and pruning does not interfere withthis. If we are concerned with the bound between time
steps t1 and t2 , the only requirement is that we do notremove the best expert during this time period.
Pruning Method 1 (Oldest First) When a new expert is added to the ensemble, if the number of experts
is greater than some constant K, remove the oldest expert before adding the new member.
Theorem 5.1 Let S1 , S2 , . . . , Sk be a partitioning of
the input series as discussed in Corollaries 3.3 and4.3. Suppose that we have an upper bound m̃ or `˜ on
the maximum mistakes or loss of the base learner on
any partition. Then AddExp trained on S, using theOldest First pruning method with suitably chosen K,
will have the same mistake or loss bound as AddExp
without pruning.
Proof For the discrete case, letK=m̃ log(1/β) + log(1/γ).
log(2/(1 + β + 2γ))

By Corollary 3.3, AddExp.D will make no more than
K mistakes when trained on any partition Si . Since
a new expert is added only when a mistake is made,this also serves as a bound for the number of expertsthat can be created when trained on one partition.
Therefore, if more experts than K are created, theoldest expert must span more than one partition, andwe can remove it, since the bound depends only on theexpert added at the beginning of each partition.
In the continuous case we selectK=`˜ln(1/β) + ln(1/γ) + ln(1/τ ) 1
· ,
1−β−γ
τ

as this is a worst-case bound on the number of new
experts that can be created. After this, the proof parallels that of the discrete case.
¤
Unfortunately, this method may be difficult to use inpractice since we may not be able to obtain `˜ or m̃.
Even if we could, the number of experts required might
still be prohibitively large. Additionally, if we select a
K that is too small, Oldest First may seriously degrade
the performance of AddExp since, when trained on a
static concept, it is precisely the oldest expert that is
usually the most valuable. For this reason, we introduce a more practical pruning method.
Pruning Method 2 (Weakest First) When a newexpert is added to the ensemble, if the number of experts is greater than a constant K, remove the expert
with the lowest weight before adding the new member.
Weakest First performs well in practice, because it removes the worst performing experts. However, it isdifficult to determine performance in the worst casesince an adversary can always degrade the initial performance of the optimal expert, such that its weight
falls below other experts. We must also be carefulin choosing K in conjunction with γ, as we do notwant new experts to be pruned before they are given achance to learn. However, as we show in the next section, Weakest First works well in practice, even withsmall values of K.

6. Empirical Results
To provide empirical support for AddExp, we evaluated it on the STAGGER Concepts (Schlimmer &Granger, 1986), a standard benchmark for concept
drift, and on classification and regression tasks involving a drifting hyperplane. For the STAGGER Concepts, each example consists of three attributes, color∈ {green, blue, red}, shape ∈ {triangle, circle, rectangle}, and size ∈ {small, medium, large}, and a classlabel y ∈ {+, −}. Training lasts for 120 time steps,
and consists of three target concepts that last 40 time
steps each: (1) color = red ∧ size = small, (2) color= green ∨ shape = circle, and (3) size = medium ∨Using Additive Expert Ensembles to Cope with Concept Drift100

100
Predictive Accuracy on Test Set (%)

Predictive Accuracy (%)

90
80
70
60
50
40
30

AddExp.D w/ Naive Bayes
Naive Bayes on each concept
Naive Bayes
DWM w/ Naive Bayes

20
10

90
80
70
60
50

AddExp.D w/ Naive Bayes
Naive Bayes on each concept
Naive Bayes
DWM w/ Naive Bayes

40
30

0

20

40

60

80

100

120

0

500

Time Step (t)size = large. At each time step, the learner is trainedon one example, and tested on 100 examples generated
randomly according to the current concept.
To test performance on a larger problem involving
noise and more gradual drift, and to evaluate AddExp on a regression task, we created a synthetic problem using a drifting hyperplane. Feature vectors consist of ten variables, x ∈ [0, 1]10 , each with a uniform distribution over this range. Training lasts for2000 time steps, with 4 target concepts lasting for 500
examples each. At every time step, the learners aretrained on one example and tested on 100. For theclassification task, y ∈ {+, −}, and the general target concept is (xi + xi+1 + xi+2 )/3 > 0.5, with i = 1,
2, 4, and 7 for each of the 4 concepts, respectively.
We also introduced 10% random class noise into thetraining data. The regression task is identical exceptthat y ∈ [0, 1] and we eliminated the threshold, i.e.,y = (xi + xi+1 + xi+2 )/3 with i = 1, 2, 4, and 7 foreach of the 4 concepts. Instead of class noise, we introduced a ±0.1 random variate to y, clipping y if it
was not in [0, 1].
We evaluated AddExp.D on the STAGGER and hyperplane classification tasks, and AddExp.C on thehyperplane regression task. Based on pilot studies, wechose parameters of β = 0.5, γ = 0.1 for STAGGER,
β = 0.5, γ = 0.01 for the hyperplane classification task,
and β = 0.5, γ = 0.1, τ = 0.05 for hyperplane regression. We used an incremental version of naive Bayes as
the base learner for AddExp.D and an online batch
version of least squares regression as the base learnerfor AddExp.C. For the sake of comparison, we evaluated the performance of the base learner over the entire data set, and on each concept individually. These
serve as worst-case and best-case comparisons, respectively, since the base learners have no mechanisms foradjusting to concept drift, and conversely, the baselearners trained on each concept individually are not

1500

2000

Figure 4. Predictive accuracy on the hyperplane problem.
0.6
Average Absolute Loss on Test Set

Figure 3. Predictive accuracy on the STAGGER concepts.

1000
Time Step (t)AddExp.C w/ Linear Regression
Linear Regression on each concept
Linear Regression

0.5
0.4
0.3
0.2
0.1
0
0

500

1000

1500

2000

Time Step (t)Figure 5. Average absolute loss on a continuous version of
the hyperplane problem.

hindered by previous data. We also evaluated DWM
on the classification tasks – using naive Bayes as abase learner, β = 0.5, and allowing new experts to be
added every time step, mirroring AddExp.D. For all
simulations, we averaged accuracies over 50 runs, andcalculated 95% confidence intervals.
Figure 3 shows the performance of AddExp.D on the
STAGGER data set. All algorithms except DWM perform virtually the same on the first concept, since nodrift takes place. Once the target concept changes,
naive Bayes cannot adapt quickly to the new concept,
but AddExp.D is able to quickly converge to performance similar to naive Bayes trained only on the newtarget concept. Figure 4 shows a similar result for thehyperplane classification task. AddExp.D converges
quickly to all concepts. However, it converges slowest
to the second concept, the most gradual of the threedrifts since only one relevant variable changes, and x2
and x3 are relevant for both concepts. After the drift
occurs, AddExp.D’s performance is initially better
than naive Bayes’, because of the “old” experts andthe overlap of the two concepts. Convergence is slower
because it takes longer for the new experts to “out-Using Additive Expert Ensembles to Cope with Concept Driftweigh” the old ones. This shows AddExp.D balancing the predictions of its old and new experts, which
is important for real-world applications, since it is notknown in advance whether drift will be gradual or sudden. Finally, Figure 5 shows similar behavior for AddExp.C on the hyperplane regression task.
DWM performs slightly worse than AddExp.D on
the first STAGGER concept (Figure 3), but outperforms it on the last. This is because DWM gives moreweight to a new expert – set initially to the highest
weight in the ensemble – which can accelerate convergence, but it can also let new experts become dominant
too quickly, thereby decreasing performance. This isparticularly harmful in noisy scenarios, as shown by
Figure 4. To deal with this problem, DWM uses a
parameter such that new experts can only be added
periodically. However, this prevents DWM from recognizing drift during this period, and does not alleviate the problem entirely. Therefore, we argue that
AddExp is a more robust solution to this problem,since the γ parameter allows one to precisely dictate
the weight of new experts, and the bounds we have
proven show that new experts can never dominate entirely if an older expert performs better.
By the end of the 2000 training examples on the hyperplane classification task, AddExp.D created an average of 385 experts, causing the algorithm to be muchslower than naive Bayes. This is especially a problem
in noisy domains, since new experts will continually becreated when the algorithm misclassifies noisy examples. Fortunately, the Weakest First method of pruning works remarkably well on this task. The learning curves for AddExp.D with a maximum of 10
or 20 experts are virtually indistinguishable from theunpruned learning curve. The average accuracy over
all time steps for unpruned AddExp.D is 87.34% ±0.06, while Weakest First achieves average accuraciesof 87.27±0.06 for K = 20 and 87.08±0.06 for K = 10.

7. Concluding Remarks
We presented the additive expert ensemble algorithm
AddExp, a general method for using any online
learner to handle concept drift. We proved mistakeand loss bounds on a subsequence of the training data
relative to the actual performance of the base learner,
the first theoretical analysis of this type. We proposed
two pruning methods that limit the number of experts
in the ensemble, and evaluated the performance of
the algorithm on two synthetic data sets. In future
work, we would like to conduct more empirical analysis, analyze additive expert ensembles under other loss
functions, and investigate methods for dynamically ad-justing the parameters of the algorithm during online
learning to maximize performance.
Acknowledgements. The authors thank the Georgetown
Undergraduate Research Opportunities Program for funding, and thank Lisa Singh and the anonymous reviewers
for helpful comments on earlier drafts of this article.

References
Blum, A. (1997). Empirical support for Winnow andWeighted-Majority algorithms. Machine Learning, 26,
5–23.
Bousquet, O., & Warmuth, M. K. (2003). Tracking a small
set of experts by mixing past posteriors. Journal of Machine Learning Research, 3, 363–396.
Cesa-Bianchi, N., Freund, Y., Haussler, D., Helmbold,
D. P., Schapire, R. E., & Warmuth, M. K. (1997). How
to use expert advice. Journal of the ACM, 44, 427–485.
Freund, Y., & Schapire, R. (1997). A decision-theoretic
generalization of on-line learning and an application to
boosting. J. Computer and Sys. Sciences, 55, 119–139.
Haussler, D., Kivinen, J., & Warmuth, M. (1998). Sequential predictions of individual sequences under general loss functions. IEEE Transactions on Information
Theory, 44, 1906–1925.
Helmbold, D. P., & Long, P. M. (1994). Tracking drifting
concepts by minimising disagreements. Machine Learning, 14, 27–45.
Herbster, M., & Warmuth, M. K. (1998). Tracking the bestexpert. Machine Learning, 32, 151–178.
Kolter, J. Z., & Maloof, M. A. (2003). Dynamic weighted
majority. Proceedings of the 3rd IEEE ICDM Conference(pp. 123–130). IEEE Press.
Littlestone, N. (1988). Learning quickly when irrelevant
attributes abound: A new linear-threshold algorithm.
Machine Learning, 2, 285–318.
Littlestone, N., & Warmuth, M. K. (1994). The weighted
majority algorithm. Information and Computation, 108,
212–261.
Monteleoni, C., & Jaakkola, T. S. (2004). Online learning of non-stationary sequences. Proceedings of the 16th
NIPS Conference. MIT Press.
Schlimmer, J., & Granger, R. (1986). Beyond incremental
processing: Tracking concept drift. Proceedings of the
5th AAAI Conference (pp. 502–507). AAAI Press.
Street, W., & Kim, Y. (2001). A streaming ensemble algorithm (SEA) for large-scale classification. Proceedings ofthe 7th SIGKDD Conference (pp. 377–382). ACM Press.
Vovk, V. (1990). Aggregating strategies. Proceedings of the
3rd COLT Workshop (pp. 371–386). Morgan Kaufmann.
Vovk, V. (1998). A game of prediction with expert advice.
J. of Computer and System Sciences, 56, 153–173.
Widmer, G., & Kubat, M. (1996). Learning in the presenceof concept drift and hidden contexts. Machine Learning,23, 69–101.