Tracking the Best Disjunction.
Littlestone developed a simple deterministic on-line learning algorithm for learning k-literal disjunctions. This algorithm (called {\sc Winnow}) keeps one weight for each of then variables and does multiplicative updates to its weights. We develop a randomized version of {\sc Winnow} and prove bounds for an adaptation of the algorithm for the case when the disjunction may change over time. In this case a possible target {\it disjunction schedule} &Tgr; is a sequence of disjunctions (one per trial) and the {\it shift size} is the total number of literals that are added/removed from the disjunctions as one progresses through the sequence.We develop an algorithm that predicts nearly as well as the best disjunction schedule for an arbitrary sequence of examples. This algorithm that allows us to track the predictions of the best disjunction is hardly more complex than the original version. However, the amortized analysis needed for obtaining worst-case mistake bounds requires new techniques. In some cases our lower bounds show that the upper bounds of our algorithm have the right constant in front of the leading term in the mistake bound and almost the right constant in front of the second leading term. Computer experiments support our theoretical findings.
Introduction
One of the most significant successes of the Computational Learning Theory community
has been Littlestone's formalization of an on-line model of learning and
the development of his algorithm Winnow for learning disjunctions (Littlestone,
1989, 1988). The key feature of Winnow is that when learning disjunctions of
constant size, the number of mistakes of the algorithm grows only logarithmically
with the input dimension. For many other standard algorithms such as the Perceptron
Algorithm (Rosenblatt, 1958), the number of mistakes can grow linearly in
the dimension (Kivinen, Warmuth, & Auer, 1997). In the meantime a number of
algorithms similar to Winnow have been developed that also show the logarithmic
growth of the loss bounds in the dimension (Littlestone & Warmuth, 1994; Vovk,
1990; Cesa-Bianchi et al., 1997; Haussler, Kivinen, & Warmuth, 1994).
* An extended abstract appeared in (Auer & Warmuth, 1995).
* M. K. Warmuth acknowledges the support of the NSF grant CCR 9700201.
In this paper we give a refined analysis of Winnow, develop a randomized version
of the algorithm, give lower bounds that show that both the deterministic and the
randomized version are close to optimal, and adapt both versions so that they can
be used to track the predictions of the best disjunction.
Consider the following by now standard on-line learning model (Littlestone, 1989,
1988; Vovk, 1990; Cesa-Bianchi et al., 1997). Learning proceeds in trials. In trial
the algorithm is presented with an instance x t (in our case an n-dimensional
binary vector) that is used to produce a binary prediction - y t . The algorithm then
receives a binary classification y t of the instance and incurs a mistake if -
The goal is to minimize the number of mistakes of the algorithm for an arbitrary
sequence of examples h(x This is of course a hopeless scenario: for any
deterministic algorithm an adversary can always choose the sequence so that the
algorithm makes a mistake in each trial. A more reasonable goal is to minimize the
number of mistakes of the algorithm compared to the minimum number of mistakes
made by any concept from a comparison class.
1.1. The (non-shifting) basic setup
In this paper we use monotone 1 k-literal disjunctions as the comparison class. If the
dimension (number of Boolean attributes/literals) is n then such disjunctions are
Boolean formulas of the form x
, where the (distinct) indices i j lie
in ng. The number of classification errors of such a disjunction with respect
to a sequence of examples is simply the total number of misclassifications that this
disjunction produces on the sequence. The goal is to develop algorithms whose
number of mistakes is not much larger than the number of classification errors of
the best disjunction, for any sequence of examples.
In this paper we consider the case where the mistakes of the best ("target") disjunction
are caused by attribute errors. The number of attribute errors of an example
with respect to a target disjunction u is the minimum
number of attributes/bits of x that have to be changed so that for the resulting x 0 ,
y. The number of attribute errors for a sequence of examples with respect
to a target concept is simply the total number of such errors for all examples of
the sequence. Note that if the target u is a k-literal monotone disjunction then the
number of attribute errors is at most k times the number of classification errors
with respect to u (i.e. k times the number of examples (x; y) in the sequence for
which u(x) 6= y).
Winnow can be tuned as a function of k so that it makes at most O(A+k ln(n=k))
mistakes on any sequence of examples where the best disjunction incurs at most
A attribute errors (Littlestone, 1988). We give a randomized version of Winnow
and give improved tunings of the original algorithm. The new algorithm can be
tuned based on k and A so that its expected mistake bound is at most A
any sequence of examples for which there
is a monotone k-literal disjunction with at most A attribute errors. We also show
how the original deterministic algorithm can be tuned so that its number of mistakes
is at most 2A
for the same set of sequences.
Our lower bounds show that these bounds are very close to optimal. We show
that for any algorithm the expected number of mistakes must be at least
our upper bound has the correct constant on the leading term
and almost the optimal constant on the second term. For deterministic algorithms
our lower bounds show that the constant on the leading term is optimal.
Our lower bounds for both the deterministic and the randomized case cannot be improved
significantly because there are essentially matching upper bounds achieved
by non-efficient algorithms with the correct factors on the first and the second term.
These algorithms use
experts (Cesa-Bianchi et al., 1997): each expert simply
computes the value of a particular k-literal disjunction and one weight is kept per
expert. This amounts to expanding the n-dimensional Boolean inputs into
Boolean inputs and then using single literals (=experts) (Littlestone & Warmuth,
1994; Vovk, 1990; Cesa-Bianchi et al., 1997) as the comparison class instead of k-
literal disjunctions. The expected number of mistakes of the randomized algorithm
is at most Q+
a bound on the number of
classification errors of the best k-literal disjunction. The mistake bound of the deterministic
algorithm is exactly twice as high. Observe that these algorithms have
to use about n k weights, and that they need that much time in each trial to calculate
their prediction and update the weights. Thus their run time is exponential in
k.
In contrast, our algorithm uses only n weights. On the other hand the noise in the
upper bounds of our efficient algorithm is measured in attribute errors rather than
classification errors. This arises since we are using just one weight per attribute.
Recall that a classification error with respect to a k-literal disjunction can equate to
up to k attribute errors. To capture errors that affect up to k attributes efficiently
the expansion to
experts seems to be unavoidable. Nevertheless, it is surprising
that our version of Winnow is able to get the right factor before the number of
attribute errors A and for the randomized version almost the right factor before the
square root term. In some sense Winnow compresses
\Delta weights to only n weights.
At this point we don't have a combinatorial interpretation of our weights. Such
an interpretation was only found for the single literal (expert) case (Cesa-Bianchi,
Freund, Helmbold, & Warmuth, 1996).
As Littlestone (Littlestone, 1991) we use an amortized analysis with an entropic
potential function to obtain our worst-case loss bounds. However besides the more
careful tuning of the bounds we take the amortized analysis method a significant
step further by proving mistake bounds of our algorithm as compared to the best
shifting disjunction.
1.2. Shifting disjunctions
Assume that a disjunction u is specified by a n-dimensional binary vector, where
the components with value 1 correspond to the monotone literals of the disjunction.
For two disjunctions u and u 0 the Hamming distance measures how many
literals have to be "shifted" to obtain u 0 from u. A disjunction schedule T for a
sequence of examples of length T is simply a sequence of T disjunctions u t . The
(shift) size of the schedule T is
is the all zero vector). In
the original non-shifting case all u are equal to some k-literal disjunction
u and accordingly to the above definition the "shift size" is k.
At trial t the schedule T predicts with disjunction u t . We define the number of
attribute errors of an example sequence h(x t ; y t )i with respect to a schedule T as
the total number of attributes that have to be changed in the sequence of examples
to make it consistent with the schedule T , i.e. for which the changed instances x 0
Note that the loss bounds for the non-shifting case can be written as cA+O(
\Delta is the number of bits it takes to describe a disjunction with
k literals, and where for the randomized and for the deterministic
algorithm. Surprisingly, we were able to prove bounds of the same form for the
shifting disjunction case. B is now the number of bits it takes to describe the best
schedule T and A is the number of attribute errors of this schedule. If Z is the shift
size of schedule T then it takes log 2
Z
bits to describe a schedule
T in respect to a given sequence of examples. 2
Our worst-case mistake bounds are similar to bounds obtained for "competitive
algorithms" in that we compare the number of mistakes of our algorithm against
the number of attribute errors of the best off-line algorithm that is given the whole
sequence ahead of time. The off-line algorithm still incurs A attribute errors and
here we bound the additional loss of the on-line algorithm over the number of
attribute errors of the best schedule (as opposed to the coarser method of bounding
the ratio of on-line over off-line).
Winnow does multiplicative updates to its weights. Whenever the algorithm makes
a mistake then the weights of all the literals for which the corresponding bit in the
current input instance is one are multiplied by a factor. In the case of Winnow2,
the version of Winnow this paper is based on (Littlestone, 1988), this factor is
either ff or 1=ff, where ff ? 1 is a parameter of the algorithm. The multiplicative
weight updates might cause the weights of the algorithm to decay rather rapidly.
Since any literal might become part of the disjunction schedule even when it was
misleading during the early part of the sequence of examples, any algorithm that is
to predict well as compared to the best disjunction schedule must be able to recover
weights quickly. Our extension of Winnow2 simply adds a step to the original
algorithm that resets a weight to fi=n whenever it drops below this boundary.
Similar methods for lower bounding the weights were used in the algorithm Wml
of (Littlestone & Warmuth, 1994) which was designed for predicting as well as the
best shifting single literal (which is called expert in (Cesa-Bianchi et al., 1997)).
In addition to generalizing the work of (Littlestone & Warmuth, 1994) to arbitrary
size disjunctions we were able to optimize the constant in the leading term of the
mistake bound of Winnow and develop a randomized version of the algorithm.
In (Herbster & Warmuth, 1998) the work of (Littlestone & Warmuth, 1994) was
generalized in a different direction. The focus there is to predict as well as the
best shifting expert, where "well" is measured in terms of other loss functions than
the discrete loss (counting mistakes) which is the loss function used in this paper.
Again the basic building block is a simple on-line algorithm that uses multiplicative
weight updates (Vovk, 1990; Haussler et al., 1994) but now the predictions and the
feedback in each trial are real-valued and lie in the interval [0; 1]. The class of loss
functions includes the natural loss functions of log loss, square loss and Hellinger
loss. Now the loss does not occur in "large" discrete units. Instead the loss in a
trial my be arbitrarily small and thus more sophisticated methods are needed for
recovering small weights quickly (Herbster & Warmuth, 1998) than simply lower
bounding the weights.
Why are disjunctions so important? Whenever a richer class is built by (small)
unions of a large number of simple basic concepts, our methods can be applied.
Simply expand the original input into as many inputs as there are basic concepts.
Since our mistake bounds only depend logarithmically on the number of basic con-
cepts, we can even allow exponentially many basic concepts and still have polynomial
mistake bounds. This method was previously used for developing noise robust
algorithms for predicting nearly as well as the best discretized d-dimensional axis-parallel
box (Maass & Warmuth, 1998; Auer, 1993) or as well as the best pruning
of a decision tree (Helmbold & Schapire, 1997). In these cases a multiplicative
algorithm maintains one weight for each of the exponentially many basic concepts.
However for the above examples, the multiplicative algorithms with the exponentially
many weights can still be simulated efficiently. Now, for example, the methods
of this paper immediately lead to an efficient algorithm for predicting as well as the
best shifting d-dimensional box. Thus by combining our methods with existing al-
gorithms, we can design efficient learning algorithms with provably good worst-case
loss bounds for more general shifting concepts than disjunctions.
Besides doing experiments on practical data that exemplify the merits of our worst-case
mistake bounds, this research also leaves a number of theoretical open prob-
lems. Winnow is an algorithm for learning arbitrary linear threshold functions
and our methods for tracking the best disjunction still need to be generalized to
learning this more general class of concepts.
We believe that the techniques developed here for learning how to predict as well
as the best shifting disjunction will be useful in other settings such as developing
algorithms that predict nearly as well as the best shifting linear combination. Now
the discrete loss has to be replaced by a continuous loss function such as the square
loss, which makes this problem more challenging.
1.3. Related work
There is a natural competitor to Winnow which is the well known Perceptron
algorithm (Rosenblatt, 1958) for learning linear threshold functions. This algorithm
does additive instead of multiplicative updates. The classical Perceptron
Convergence Theorem gives a mistake bound for this algorithm (Duda & Hart,
1973; Haykin, 1994), but this bound is linear in the number of attributes (Kivinen
et al., 1997) whereas the bounds for the Winnow-like algorithms are logarithmic
in the number of attributes. The proof of the Perceptron Convergence Theorem
can also be seen as an amortized analysis. However the potential function needed
for the perceptron algorithm is quite different from the potential function used for
the analysis of Winnow. If w t is the weight vector of the algorithm in trial t and
u is a target weight vector, then for the perceptron algorithm
2 is the
potential function where jj:jj 2 is the Euclidean length of a vector. In contrast the
potential function used for the analysis of Winnow (Littlestone, 1988, 1989) that
is also used in this paper is the following generalization 3 of relative entropy (Cover,
In the case of linear regression a framework was developed (Kivinen & Warmuth,
1997) for deriving updates from the potential function used in the amortized anal-
ysis. The same framework can be adapted to derive both the Perceptron algorithm
and Winnow. The different potential functions for the algorithms lead to the
additive and multiplicative algorithms, respectively. The Perceptron algorithm is
seeking a weight vector that is consistent with the examples but otherwise minimizes
some Euclidean length. Winnow instead minimizes a relative entropy and
is thus rooted in the Minimum Relative Entropy Principle of Kullback (Kapur &
Kesavan, 1992; Jumarie, 1990).
1.4. Organization of the paper
In the next section we formally define the notation we will use throughout the
paper. Most of them have already been discussed in the introduction. Section 3
presents our algorithm and Section 4 gives the theoretical results for this algorithm.
In Section 5 we consider some more practical aspects, namely how the parameters
of the algorithm can be tuned to achieve good performance. Section 6 reports some
experimental results. The analysis of our algorithm and the proofs for Section 4
are given in Section 7. Lower bounds on the number of mistakes made by any
algorithm are shown in Section 8 and we conclude in Section 9.
2. Notation
A target schedule a sequence of disjunctions represented by n-ary
bit vectors u . The size of the shift from disjunction
u to disjunction u t is z
j. The total
shift size of schedule T is
z t where we assume that u
To get more precise bounds
for the case when there are shifts in the target schedule we will distinguish between
shifts where a literal is added to the disjunction and shifts where a literal is removed
from the disjunction. Thus we define z
t as the
number of times a literal is switched on, and
t as the number of
times a literal is switched off.
A sequence of examples consists of attribute vectors
classifications y t 2 f0; 1g. The prediction of
disjunction u t for attribute vector x t is u t
The number of attribute errors a t at trial t with respect to
a target schedule T is the minimal number of attributes that have to be changed,
resulting in x 0
t , such that u t
That is a
g. The total number of attribute errors of sequence S with respect to
schedule T is
a t . We denote by S(Z; A; n) the class of example sequences
S with n attributes which are consistent with some target schedule T with shift
size Z and with at most A attribute errors. If we wish to distinguish between
positive and negative shifts we denote the corresponding class by S(Z
are the numbers of literals added and removed, respectively,
in the target schedule. By S 0 (k; A; n) we denote the class of example sequences
S with n attributes which are consistent with some non-shifting target schedule
(i.e.
and with at most A attribute errors.
For the case that only upper bounds on Z, Z are known we denote
the corresponding classes by S - (Z; A;
z-Z
-k
The loss of a learning algorithm L on an example sequence S is the number of
misclassifications
is the binary prediction of the learning algorithm L in trial t.
3. The algorithm
We present algorithm Swin ("Shifting Winnow"), see Table 1, an extension of
Littlestone's Winnow2 algorithm (Littlestone, 1991). Our extension incorporates
a randomization of the algorithm, and it guarantees a lower bound on the weights
used by the algorithm. The algorithm maintains a vector of n weights for the n
attributes. By w we denote the weights at the end of trial t,
Table

1. Algorithm Swin
Parameters:
The algorithm uses parameters ff ?
Initialization:
Set the weights to initial values
In each trial t - 1 set r predict
ae
Receive the binary classification y t .
If y
Update:
If y t 6= p(r t ) then for all
1. w 0
2. w
and w 0 denotes the initial value of the weight vector. In trial t the algorithm
predicts using the weight vector w . The prediction of the algorithm depends
on r
1]. The algorithm
predicts 1 with probability p(r t ), and it predicts 0 with probability
obtain a deterministic algorithm one has to choose a function p
predicting the algorithm receives the classification y t . If y
i.e. the weight vector is not modified. Since y t 2 f0; 1g and p(r t ) 2 [0; 1] this can
only occur when the prediction was deterministic, i.e. p(r t correct.
An update occurs in all other cases when the prediction was wrong or p(r t
The updates of the weights are performed in two steps. The first step is the original
Winnow update, and the second step guarantees that no weight is smaller than fi
for some parameter fi (a similar approach was taken in (Littlestone & Warmuth,
1994)). Observe that the weights are changed only if the probability of making a
mistake was non-zero. For the deterministic algorithm this means that the weights
are changed only if the algorithm made a mistake. Furthermore the i-th weight is
modified only if x 1. The weight is increased (multiplied by ff) if y
it is decreased (divided by ff) if y The parameters ff, fi, w 0 , and the function
p(\Delta), have to be set appropriately. A good choice for function p(\Delta) is the following:
for a randomized prediction let
if
(RAND)
and for a deterministic version of the algorithm let
(DET)
For the randomized version one has to choose fi ! ln ff
. Observe that (DET)
is obtained from (RAND) by choosing the threshold
in (RAND). This corresponds to the straightforward conversion from
a randomized prediction algorithm into a deterministic prediction algorithm.
Theoretically good choices of the parameters ff, fi, and w 0 are given in the next
section and practical issues for tuning the parameters are discussed in Section 5.
4. Results
In this section we give rigorous bounds on the (expected) number of mistakes of
Swin, first in general and then for specific choices of ff, fi, and w 0 , all with p(\Delta)
chosen from (RAND) or (DET). These bounds can be shown to be close to optimal
for adversarial example sequences, for details see Section 8.
Theorem 1 (randomized version) Let ff ? 1,
n , and p(\Delta)
as in (RAND). Then for all S
A
If fi - n
e then the bound holds for all S
Theorem 2 (deterministic version) Let ff ? 1,
n , and
p(\Delta) as in (DET). Then for all S
A
If fi - n
e then the bound holds for all S
Theorem 3 (non-shifting case) Let ff ? 1,
if Swin uses the function p(\Delta) given by (RAND), and
if Swin uses the function p(\Delta) given by (DET).
e then the bounds hold for all S 2 S -
Remark. The usual conversion of a bound M for the randomized algorithm into a
bound for the deterministic algorithm would give 2M as the deterministic bound. 4
But observe that our deterministic bound is just 1 times the randomized
bound.
Since at any time a disjunction cannot contain more than n literals we have Z
which gives the following corollary.
, and w
. If p(\Delta) as in
(RAND) then for all S 2 S - (Z; A; n)
A
j.
j.
If p(\Delta) as in (DET) then for all S 2 S - (Z; A; n)
A
ffn
j.
j.
At first we give results on the number of mistakes of Swin, if no information besides
n, the total number of attributes, is given.
Theorem 4 Let
n , and p(\Delta) be as in (RAND). Then
for all S 2 S - (Z; A; n)
n , and p(\Delta) be as in (DET). Then for all S 2
n , and p(\Delta) be as in (RAND). Then for all S 2
then the above bound holds for all S 2 S -
n). For n - 2 we have
, and p(\Delta) be as in (DET). Then for all S 2 S 0 (k; A; n)
then the above bound holds for all S 2 S -
n). For n - 2 we have
In Section 8 we will show that these bounds are optimal up to constants. If A
and Z are known in advance then the parameters of the algorithm can be tuned to
obtain even better results. If for example in the non-shifting case the number k of
attributes in the target concept is known we get
Theorem 5 Let
n , and p(\Delta) be as in (RAND). Then for
e
then the above bound holds for all S 2 S -
n). For k - n
e
we set
e
and get EM(Swin;S) - 1:44
e
for all S 2 S -
, and p(\Delta) be as in (DET). Then for all S 2 S 0 (k; A; n)
e then the above bound holds for all S 2 S -
n). For k - n
e we set
e and get M(Swin;S) - 2:75
e for all S 2 S -
Of particular interest is the case when A is the dominant term, i.e. A AE k ln n
Theorem 6 Let A - k ln n
A
n , and p(\Delta) be as in
(RAND). Then for all S 2 S 0 (k; A; n)
r
e then the above bound holds for all S 2 S -
n). For k - n
e , A - n
e ,
e , we have EM(Swin;S) - A
e for all
If A - 2k
A
, and p(\Delta) be as in (DET), then
for all S 2 S 0 (k; A; n)
r
e
then the above bound holds for all S 2 S -
n). For k - n
e
e
e , we have M(Swin;S) - 2A
e for all
In the shifting case we get for dominant A AE Z ln n
Theorem 7 Let
Z+minfn;Zg
Z
, and A and Zsuch that ffl - 1
. Then for
n , and p(\Delta) as in (RAND), and for all S 2 S - (Z; A; n),
r
An
Z
Z+minfn;Zg
A
An
Z
n , and p(\Delta) as in
(DET), then for all S 2 S - (Z; A; n),
r
An
Z
In Section 8 we will show that in Theorems 6 and 7 the constants on A are optimal.
Furthermore we can show for the randomized algorithm that also the magnitude of
the second order term in Theorem 6 is optimal.
5. Practical tuning of the algorithm
In this section we give some thoughts on how the parameters ff, fi, and w 0 of
Swin should be chosen for particular target schedules and sequences of examples.
Our recommendations are based on our mistake bounds which hold for any target
schedule and for any sequence of examples with appropriate bounds on the number
of shifts and attribute errors. Thus it has to be mentioned that, since many target
schedules and many example sequences are not worst case, our bounds usually
overestimate the number of mistakes made by Swin. Therefore parameter settings
different from our recommendations might result in a smaller number of errors for
a specific target schedule and example sequence. On the other hand Swin is quite
insensitive to small changes in the parameters (see Section 6) and the effect of such
changes should be benign.
If little is known about the target schedule or the example sequence than the parameter
settings of Theorems 4 or 5 are advisable since they balance well between
the effect of target shifts and attribute errors. If good estimates for the number of
target shifts and the number of attribute errors are known than good parameters
can be calculated by numerically minimizing the bounds in Theorems 1, 2, 3 or
Corollary 1, respectively.
If the average rate of target shifts and attribute errors is known such that Z -
r Z T and A - r AT with r Z ? 0; r A - 0 then for large T the error rate r
M(Swin;S)=T is by Corollary 1 approximately upper bounded by
r A
for randomized predictions and by
r A
ffn
for deterministic predictions. Again, optimal choices for ff and fi can be obtained
by numerical minimization.
6. Experimental results
The experiment reported in this section is not meant to give a rigorous empirical
evaluation of algorithm Swin. Instead, it is intended as an illustration of the typical
behavior of Swin, compared with the theoretical bound and also with a version of
Winnow which was not modified to adapt to shifts in the target schedule.
In our experiment we used attributes and a target schedule T of
length which starts with 4 active literals. After 1000 trials one of the
literals is switched off and after another 1000 trials another literal is switched on.
This switching on and switching off of literals continues as depicted in Figure 1.
Thus there are initially 4 active literals).
The example sequence h(x t ; y t )i was chosen such that for half of the examples y
and for the other half y The values of attributes not appearing in the target
schedule were chosen at random such that x probability 1/2. For examples
with y exactly one of the active attributes (chosen at random) was set to
number of trials
number
of
active
literals

Figure

1. Shifts in the target schedule used in the experiment.
1. For examples with attribute errors all relevant attributes were either set to 1 (for
the case y
set to 0 (for the case y
Attribute errors occurred at trials
with y 1 and at trials
a

Figure

2 shows the performance of Swin compared with the theoretical bound
where the parameters were set by numerically minimizing the bound of Corollary 1
as described in the previous section, which yielded
The theoretical bound at trial t is calculated from the actual number of shifts and
attribute errors up to this trial. Thus an increase of the bound is due to a shift
in the target schedule or an attribute error at this trial. In Figure 2 the reasons
for these increases are indicated by z + for a literal switched on, z \Gamma for a literal
switched off, and a for attribute errors.

Figure

2 shows that the theoretical bound very accurately depicts the behavior of
Swin, although it overestimates the actual number of mistakes by some amount.
It can be seen that switching off a literal causes far less mistakes than switching on
a literal, as predicted by the bound. Also the relation between attribute errors and
mistakes can be seen.
The performance of Swin for the whole sequence of examples is shown in Figure 3
and it is compared with the performance of a version of Winnow which was not
modified for target shifts. As can be seen Swin adapts very quickly to shifts in
the target schedule. On the other hand, the unmodified version of Winnow makes
more and more mistakes for each shift.
The unmodified version of Winnow we used is just Swin with Thus the
weights are not lower bounded and can become arbitrarily small which causes a
large number of mistakes if the corresponding literal becomes active. We used the
z - a
a=4
z
number of trials
number
of
mistakes theoretical bound
performance of SWIN

Figure

2. Comparison of Swin with the theoretical bound for a particular target schedule and
sequence of examples. Shifts and attribute errors are indicated by z
number of trials
number
of
mistakes
theoretical bound
performance of SWIN
performance of Winnow

Figure

3. A version of Winnow which does not lower bound the weights makes many more
mistakes than Swin.
same ff for the unmodified version but we set w which is optimal for the
initial part of the target schedule. Therefore the unmodified Winnow adapts very
quickly to this initial part, but then it makes an increasing number of mistakes
for each shift in the target schedule. For each shift the number of mistakes made
approximately doubles.
In the last plot, Figure 4, we compare the performance of Swin with tuned parameters
to the performance of Swin with the generic parameter setting given by
Theorem 4. Although the tuned parameters do perform better the difference is
number of trials
number
of
mistakes
theoretical bound
performance of SWIN

Figure

4. Tuned parameters of Swin versus the generic parameters
relatively small.
The overall conclusion of our experiment is that, first, the theoretical bounds capture
the actual performance of the algorithm quite well, second, that some mechanism
of lower bounding the weights of Winnow is necessary to make the algorithm
adaptive to target shifts, and third, that moderate changes in the parameters do
not change the qualitative behavior of the algorithm.
7. Amortized analysis
In this section we first prove the general bounds given in Theorems 1 and 2 for the
randomized and for the deterministic version of Swin. Then from these bounds we
calculate the bounds given in Theorems 4-7 for specific choices of the parameters.
The analysis of the algorithm proceeds by showing that the distance between the
weight vector of the algorithm w t , and vector u t representing the disjunction at trial
t, decreases, if the algorithm makes a mistake. The potential/distance function used
for the previous analysis of Winnow (Littlestone, 1988, 1989, 1991) is the following
generalization of relative entropy to arbitrary non-negative weight vectors:
(This distance function was also used for the analysis of the Egu regression algorithm
(Kivinen & Warmuth, 1997), which shows that Winnow is related to the
algorithm.) By taking derivatives it is easy to see that the distance is minimal
and equal to 0 if and only if w . With the convention that 0 and the
assumption that u 2 f0; 1g n the distance function simplifies to
We start with the analysis of the randomized algorithm with shifting target dis-
junctions. The other cases will be derived easily from this analysis. At first we
calculate how much the distance D(u t ; w t ) changes between trials:
Observe that term (1) might be non-zero in any trial, but that terms (2) and (3)
are non-zero only if the weights are updated in trial t. For any fl, ffi with
can lower bound term (1) by
If the weights are updated in trial t, term (2) is bounded by
The third equality holds since each x t;i 2 f0; 1g. Remember that x 0 t is obtained
from x t by removing the attribute errors from x t . The last inequality follows from
the fact that
At last observe that w t;i 6= w 0
only if y
. In this case w 0
ffn
and we get for term (3)
Summing over all trials we have to consider the trials where the weights are updated
and we have to distinguish between trials with y
denote these trials. Then by the above bounds on terms (1), (2), and (3) we have

\Theta r t
Now we want to lower bound the sum over M 0 and M 1 by the expected (or total)
number of mistakes of the algorithm. We can do this by choosing an appropriate
function p(\Delta; w t ). We denote by p t the probability that the algorithm makes a
mistake in trial t. Then the expected number of mistakes is
. Observe that
since in this case y
Thus it is sufficient to find a function p(\Delta)
and a constant C with
and
For such a function p(\Delta) satisfying (4) and (5) we get
assuming that S 2 S(Z
we can upper bound the expected number of mistakes by
Hence we want to choose p(\Delta) and C such that C is as big as possible. For that
fix p(\Delta) and let r   be a value where p(r   ) becomes 1. 5 Since the left hand sides of
equations (4) and (5) are continuous we get (r
combining these two we have
ff
This can be achieved by choosing p(\Delta) as in (RAND) which satisfies (4) and (5) for
course we have to choose fi ! ln ff
. Putting everything
together we have the following lemma.
and assume that
are the weights used by algorithm
Swin. Then for all S
if Swin uses the function p(\Delta) given by (RAND).
For the deterministic variant of our algorithm the function p(\Delta) has to take values in
f0; 1g. Thus we get from (4) and (5) that (r\Gammafi)(1\Gamma1=ff) - C and r(1\Gammaff)+ln ff - C
which yields
This we get by choosing p(\Delta) as in (DET) which satisfies (4) and (5) for
and assume that
are the weights used by algorithm
Swin. Then for all S
if Swin uses the function p(\Delta) given by (DET).
Now we are going to calculate bounds fl; ffi on 1 We get these bounds by
lower and upper bounding w t;i . Obviously w t;i - fi
for all t and i. The upper
bound on w t;i is derived from the observation that w t;i ? w t\Gamma1;i only if y
with the p(\Delta) as in (RAND) or
(DET), and r t - w t\Gamma1;i x t;i we find that w t;i - ff. Thus ln efi
Lemma 3 If fi
the weights w t;i
of algorithm Swin with function p(\Delta) as in (RAND) or (DET) satisfy
and
Proof of Theorems 1 and 2. By Lemmas 1, 2, and 3. 2
Proof of Theorem 3 In the non-shifting case where u
and it is
is the number of attributes in the target disjunction
u. Thus in the non-shifting case the term in the upper bounds of
Lemmas 1 and 2 can be replaced by k
, which gives the theorem. 2
7.1. Proofs for specific choices of the parameters
Proofs of Theorems 4 and 5. By Theorem 3 and Corollary 1 and simple calcu-
lations. 2
Proof of Theorem 6. For we get from Theorem 3 that
with
with 2. Then
In the second inequality we used that ffl - 1. Substituting the values for c and ffl
gives the statements of the theorem. 2
Proof of Theorem 7. For
we get from
Corollary 1 that
j.
j.
with
j.
j.
with 2. Then for ffl - 1=10
j.
j.
c
c
for
r
A
An
Z
This gives the bounds of the theorem. 2
8. Lower bounds
We start by proving a lower bound for the shifting case. We show that for any
learning algorithm L there are example sequences S for which the learning algorithm
makes "many" mistakes. Although not expressed explicitly in the following
theorems we will show that these sequences S can be generated by target schedules
each disjunction u t consists of exactly one literal, i.e.
is the jth unit vector.
Our first lower bound shows that for any deterministic algorithm there is an adversarial
example sequence in S(Z; A; n) such that it makes at least 2A
many mistakes. Related upper bounds are given in Theorems 4 and 7.
Theorem 8 For any deterministic learning algorithm L, any n - 2, any Z - 1,
and any A - 0, there is an example sequence S 2 S(Z; A; n) such that
Proof. For notational convenience we assume that
R - 1. We construct the example sequence S depending on the predictions of
the learning algorithm such that the learning algorithm makes a mistake in each
trial. We partition the trials into R rounds. The first R \Gamma 1 rounds have length -,
the last round has length - errors will occur only within the last
trials. We choose the target schedule such that during each round the target
disjunction does not change and is equal to some e j .
At the beginning of each round there are disjunctions consistent with the
examples of this round. After l trials in this round there are still 2 - \Gammal consistent
disjunctions: we construct the attribute vector by setting half of the attributes
which correspond to consistent disjunctions to 1, and the other attributes to 0.
Furthermore we set y
y t is the prediction of the algorithm for
this attribute vector. Obviously half of the disjunctions are consistent with this
example, and thus the number of consistent disjunctions is divided by 2 in each
trial. Thus in each of the first R \Gamma 1 rounds there is a disjunction consistent with
all - examples of this round.
After in the last round there are two disjunctions consistent with the
examples of this round. For the remaining 2A+1 trials we fix some attribute vector
for which these two disjunctions predict differently, and again we set y
y t .
Thus one of these disjunctions disagrees at most A times with the classifications in
these This disagreement can be seen as caused by A attribute errors,
so that the disjunction is consistent with all the examples in the last round up to
A attribute errors. 2
Remark. Observe that a lower bound for deterministic algorithms like
implies the following lower bound on randomized algorithms:
This follows from the fact that any randomized learning algorithm can be turned
into a deterministic learning algorithm which makes at most twice as many mistakes
as the randomized algorithm makes in the average. This means that Theorem 8
implies for any randomized algorithm L that there are sequences S 2 S(Z; A; n)
with
Remark. As an open problem it remains to show lower bounds that have the same
form as the upper bounds of Theorem 7 with the square root term.
Now we turn to the non-shifting case. For are already lower bounds
known.
Lemma 4 (Littlestone & Warmuth, 1994) For any deterministic learning algorithm
L, any n - 2, and any A - 0, there is an example sequence S 2 S 0 (1; A; n) such
that
A slight modification of results in (Cesa-Bianchi et al., 1997) gives
Lemma 5 (Cesa-Bianchi et al., 1997) There are functions n(j) and A(n; j) such
that for any j ? 0, any randomized learning algorithm L, any n - n(j), and any
A - A(n; j), there is an example sequence S 2 S 0 (1; A; n) such that
A ln n:
We extend these results and obtain the following theorems. The corresponding
upper bounds are given in Theorems 5 and 6.
Theorem 9 For any deterministic learning algorithm L, any k - 1, any n - 2k,
and any A - 0, there is an example sequence S 2 S 0 (k; A; n) such that
Theorem 10 There are functions n(j) and A(n; j) such that for any j ? 0, any
randomized learning algorithm L, any k - 1, any n - kn(j), and any A - kA(n; j),
there is an example sequence S 2 S 0 (k; A; n) such that
r
Proof of Theorems 9 and 10. The proof is by a reduction to the case 1. The
n attributes are divided into k groups G i , such that each group consists
of
attributes. Furthermore we choose numbers a i -
\Xi A
with
A. For each group G i we choose a sequence S i
accordingly to Lemmas 4 and 5, respectively, such that for any learning algorithm
and
a
These sequences S i can be extended to sequences S 0
i with n attributes by setting
all the attributes not in group i to 0. Concatenating the expanded sequences S 0
we get a sequence S. It is easy to see that S 2 S(k; A; n). On the other hand
any learning algorithm for sequences with n attributes can be transformed into a
learning algorithm for sequences with a smaller number of attributes by setting the
missing attributes to 0. Thus on each subsequence S 0
of S learning algorithm L
makes at least as many mistakes as given in (6) and (7), respectively. Hence
and
r
s
A
r
if the function A(n; j) is chosen appropriately. 2
The last theorem shows that for randomized algorithms the constant of 1 before A
in Theorem 6 is optimal and that the best constant before the square root term is
in [1; 2].
9. Conclusion
We developed algorithm Swin which is a variant of Winnow for on-line learning
of disjunctions subject to target shift. We proved worst case mistake bounds for
Swin which hold for any sequence of examples and any kind of target drift (where
the amount of error in the examples and the amount of shifts is bounded). There
is a deterministic and a randomized version of Swin where the analysis of the randomized
version is more involved and interesting in its own right. Lower bounds
show that our worst case mistake bounds are close to optimal in some cases. Computer
experiments highlight that an explicit mechanism is necessary to make the
algorithm adaptive to target shifts.

Acknowledgments

We would like to thank Mark Herbster and Nick Littlestone for valuable discussions.
We also thank the anonymous referees for their helpful comments.
Notes
1. By expanding the dimension to 2n, learning non-monotone disjunctions reduces to the monotone
case.
2. Essentially one has to describe when a shift occurs and which literal is shifted. Obviously there
is no necessity to shift if the current disjunction is correct on the current example. Thus only
in some of the trials in which the current disjunction would make a mistake the disjunction is
shifted. Since the target schedule might make up to A mistakes due to attribute errors and
there are up to Z shifts, we get up to A + Z trials which are candidates for shifts. Choosing
Z of them and choosing one literal for each shift gives
Z
possibilities.
3. For this potential function the weights must be positive. Negative weights are handled via a
reduction (Littlestone, 1988, 1989; Haussler et al., 1994).
4. In the worst case the randomized algorithm makes a mistake with probability 1/2 in each trial
and the deterministic algorithm always breaks the tie in the wrong way such that it makes a
mistake in each trial. Thus the number of mistakes of the deterministic algorithm is twice the
expected number of mistakes of the randomized algorithm.
5. Formally let r Such a sequence hr j i exists if p(\Delta)
is not equal to 1 everywhere and if there is a value r with 1. For functions p(\Delta) not
satisfying these conditions algorithm Swin can be forced to make an unbounded number of
mistakes even in the absence of attribute errors.



--R


Tracking the best disjunction.
How to use expert advice.
Pattern classification and scene analysis.
Tight worst-case loss bounds for predicting with expert advice (Tech
Predicting nearly as well as the best pruning of a decision tree.
Tracking the best expert.

Entropy optimization principles with applications.
Additive versus exponentiated gradient updates for linear prediction.
The perceptron algorithm vs.
linear vs. logarithmic mistake bounds when few input variables are relevant.
Mistake bounds and logarithmic linear-threshold learning algorithms
Redundant noisy attributes
learning theory (pp.
The weighted majority algorithm.
Information and Computation
Efficient learning with virtual threshold gates.
learning theory (pp.
--TR

--CTR
Mark Herbster , Manfred K. Warmuth, Tracking the Best Expert, Machine Learning, v.32 n.2, p.151-178, Aug. 1998
D. P. Helmbold , S. Panizza , M. K. Warmuth, Direct and indirect algorithms for on-line learning of disjunctions, Theoretical Computer Science, v.284 n.1, p.109-142, 6 July 2002
Chris Mesterharm, Tracking linear-threshold concepts with Winnow, The Journal of Machine Learning Research, 4, 12/1/2003
Mark Herbster , Manfred K. Warmuth, Tracking the best regressor, Proceedings of the eleventh annual conference on Computational learning theory, p.24-31, July 24-26, 1998, Madison, Wisconsin, United States
Manfred K. Warmuth, Winnowing subspaces, Proceedings of the 24th international conference on Machine learning, p.999-1006, June 20-24, 2007, Corvalis, Oregon
Gentile , Nick Littlestone, The robustness of the
Olivier Bousquet , Manfred K. Warmuth, Tracking a small set of experts by mixing past posteriors, The Journal of Machine Learning Research, 3, 3/1/2003
Claudio Gentile, The Robustness of the p-Norm Algorithms, Machine Learning, v.53 n.3, p.265-299, December
Giovanni Cavallanti , Nicol Cesa-Bianchi , Claudio Gentile, Tracking the best hyperplane with a simple budget Perceptron, Machine Learning, v.69 n.2-3, p.143-167, December  2007
Mark Herbster , Manfred K. Warmuth, Tracking the best linear predictor, The Journal of Machine Learning Research, 1, p.281-309, 9/1/2001
S. B. Kotsiantis , I. D. Zaharakis , P. E. Pintelas, Machine learning: a review of classification and combining techniques, Artificial Intelligence Review, v.26 n.3, p.159-190, November  2006
Peter Auer, Using confidence bounds for exploitation-exploration trade-offs, The Journal of Machine Learning Research, 3, 3/1/2003
concept drift;prediction;computational learning theory;amortized analysis;on-line learning