Online Learning versus Offline Learning.
We present an off-line variant of the mistake-bound model of learning. This is an intermediate model between the on-line learning model (Littlestone, 1988, Littlestone, 1989) and the self-directed learning model (Goldman, Rivest Schapire, 1993, Goldman & Sloan, 1994). Just like in the other two models, a learner in the off-line model has to learn an unknown concept from a sequence of elements of the instance space on which it makes guess and test trials. In all models, the aim of the learner is to make as few mistakes as possible. The difference between the models is that, while in the on-line model only the set of possible elements is known, in the off-line model the sequence of elements (i.e., the identity of the elements as well as the order in which they are to be presented) is known to the learner in advance. On the other hand, the learner is weaker than the self-directed learner, which is allowed to choose adaptively the sequence of elements presented to him.We study some of the fundamental properties of the off-line model. In particular, we compare the number of mistakes made by the off-line learner on certain concept classes to those made by the on-line and self-directed learners. We give bounds on the possible gaps between the various models and show examples that prove that our bounds are tight.Another contribution of this paper is the extension of the combinatorial tool of labeled trees to a unified approach that captures the various mistake bound measures of all the models discussed. We believe that this tool will prove to be useful for further study of models of incremental learning.
Introduction
The mistake-bound model of learning, introduced by Littlestone [L88, L89], has attracted a considerable
amount of attention (e.g., [L88, L89, LW89, B90a, B90b, M91, CM92, HLL92, GRS93, GS94])
and is recognized as one of the central models of computational learning theory. Basically it models
a process of incremental learning, where the learner discovers the 'labels' of instances one by one.
At any given stage of the learning process, the learner has to predict the label of the next instance
based on his current knowledge, i.e. the labels of the previous instances that it has already seen.
The quantity that the learner would like to minimize is the number of mistakes it makes along
this process. Two variants of this model were considered, allowing the learner different degrees of
freedom in choosing the instances presented to him:
ffl The on-line model [L88, L89], in which the sequence of instances is chosen by an adversary
and the instances are presented to the learner one-by-one.
ffl The self-directed model [GRS93, GS94], in which the learner is the one who chooses the
sequence of instances; moreover, it may make his choices adaptively; i.e., each instance is
chosen only after seeing the labels of all previous instances.
In the on-line model, the learner is faced with two kinds of uncertainties. The first is which function
is the target function, out of all functions in the concept class which are consistent with the data.
The second is what are the instances that it would be challenged on in the future. While the
first uncertainty is common to almost any learning model, the second is particular to the on-line
learning model.
A central aim of this research is to focus on the uncertainty regarding the target function by
trying to "neutralize" the uncertainty that is involved in not knowing the future elements, and to
understand the effect that this uncertainty has on the mistake-bound learning model. One way
of doing this, is to allow the learner a full control of the sequence of instances, as is done in the
self-directed model. Our approach is different: we define the off-line learning model as a one in
which the learner knows the sequence of elements in advance. Since the difference between the
on-line learner and the off-line learner is the uncertainty regarding the order of the instances, this
comparison gives insight into the "information" that is in knowing the sequence.
Once we define the off-line cost of a sequence of elements, we can also define a best sequence
(a sequence in which the optimal learner, knowing the sequence, makes the fewest mistakes) and
a worst sequence (a sequence in which the optimal learner, knowing the sequence, makes the most
mistakes). These are best compared to the on-line and self-directed models if we think of them in
the following way:
ffl The worst sequence (off-line) model is a one in which the sequence of instances is chosen by
an adversary but the whole sequence (without the labels) is presented to the learner before
the prediction process starts.
ffl The best sequence (off-line) model is a one in which the whole sequence of instances is chosen
by the learner before the prediction process starts.
Denote by M on\Gammaline (C); Mworst (C); M best (C) and M sd (C) the number of mistakes made by the best
learning algorithm in the online, worst sequence, best sequence and self-directed model (respec-
tively) on the worst target concept in a concept class C. Obviously, for all C,
Mworst best
The main issue we consider is to what degree these measures can differ from one another. We
emphasize that the only complexity measure is the number of mistakes and that other complexity
measures, such as the computational complexity of the learning algorithms, are ignored. It is known
that in certain cases M sd can be strictly smaller than M on\Gammaline . For example, consider the class
of monotone monomials over n variables. It can be seen that this class has M
In addition, we give examples that show, for certain concept classes,
that M sd may be smaller than M best by a multiplicative factor of O(log n); hence, showing the
power of adaptiveness. The following example shows that there are also gaps between M best and
Mworst . Given n points in the interval [0; 1], consider the class of functions which are a suffix of
this interval (i.e., the functions f a (x) that are 1 for x - a and 0 otherwise). As there are n points,
there are only n+1 possible concepts, and therefore the Halving algorithm [L88, L89] is guaranteed
to make at most O(log n) mistakes, i.e. M on\Gammaline = O(log n). For this class, a best sequence would
be receiving the points in increasing order, in which case the learner makes at most one mistake
(i.e., M best = 1). On the other hand, we show that the worst sequence forces Mworst = \Theta(log n)
mistakes. An interesting question is what is the optimal strategy for a given sequence. We show
a simple optimal strategy and prove that the number of mistakes is exactly the rank of a search
tree (into which we insert the points in the order they appear in the sequence). We generalize
this example, and show that for any concept class, the exact number of mistakes is the rank of a
certain tree corresponding to the concept class and the particular sequence (this tree is based on the
consistent extensions). This formalization of the number of mistakes, in the spirit of Littlestone's
formalization for the on-line case [L88, L89], provides a powerful combinatorial characterization.
All the above examples raise the question of how large can these gaps be. We prove that the
gaps demonstrated by the above mentioned examples are essentially the largest possible; more
precisely, we show that M on\Gammaline can be greater than M sd by at most a factor of log jX j, where X
is the instance space (e.g., in the monomials example X is the set of 2 n boolean assignments).
The above result implies, in particular, that the ratio between the number of mistakes for
the best sequence and the worst sequence is O(log n), where n is the length of the sequence. 1
We also show that Mworst = \Omega\Gamma
log M on\Gammaline ), which implies that either both are constant or
both are non-constant. Finally we show examples in which M on\Gammaline = 3
Mworst , showing that
Mworst 6= M on\Gammaline . In a few cases we are able to derive better bounds: for the cases that Mworst
and Mworst = 2 we show simple on-line algorithms that have at most 1 and 3 mistakes, respectively.
One way to view the relationships among the above models is through the model of "experts"
[CFHHSW93, FMG92, MF93]. For each sequence oe there is an expert, E oe , that makes its predictions
under the assumption that the sequence is oe. Let oe   be the sequence chosen by the adversary,
related result by [B90a] implies that if efficiency constraints are imposed on the model, then there are cases in
which some orders are "easy" and others are computationally "hard".
then the expert E oe   makes at most Mworst mistakes. The on-line learner does not know the sequence
oe   in advance, so the question is how close can it get to the best expert, E oe   . The problem
is that the number of experts is overwhelming; initially there are n! experts (although the number
of experts consistent with the elements of the sequence oe   seen so far decreases with each element
presented). Therefore, previous results about experts do not apply here.
The rest of this paper is organized as follows: In Section 2, we give formal definitions of the
model and the measures of performance that are discussed in this paper, followed by some simple
properties of these definitions. In Section 3, we give the definition of the rank of a tree (as well as
some other related definitions) and prove some properties of it. In Section 4, we present the various
gaps. Then, we characterize the off-line complexity (for completeness, we present in Section 4.2.1
a characterization of the same nature, based on [L88, L89], for the on-line complexity and for the
self-directed complexity [GS94]) and we use these characterizations to obtain some basic results.
Finally, in Section 5, we use these characterizations to study the gap between the on-line complexity
and off-line complexity.
2 The Model
2.1 Basic Definitions
In this section we formally present our versions of the mistake bound learning model which is the
subject of this work. The general framework is similar to the on-line learning model defined by
Littlestone [L88, L89].
Let X be any set, and let C be a collection of boolean functions defined over the set X (i.e.
We refer to X as the instance space and to C as the concept class.
Let S be a finite subset of X . An on-line learning algorithm with respect to S (and a concept
class C) is an algorithm A that is given (in advance) S as an input; Then, it works in steps as
follows: In the i-th step the algorithm is presented with a new element s i 2 S. It then outputs
its prediction p i 2 f0; 1g and in response it gets the true value c t (s i ), where c t 2 C denotes the
target function. The prediction p i may depend on the set S, the values it has seen so far (and of
course the concept class C). The process continues until all the elements of S have been presented.
denote the order according to which the elements of S are presented to the
learning algorithm. Denote by M(A[S]; oe; c t ) the number of mistakes made by the algorithm on a
sequence oe as above and target function c t 2 C, when the algorithm is given S in advance (i.e., the
number of elements for which p i the mistake bound of the algorithm, for a fixed
S, as M(A[S]) 4
Finally, let
The original definitions of [L88, L89] are obtained (at least for finite X ) by considering
An off-line learning algorithm is an algorithm A that is given (in advance) not only the set S,
but also the actual sequence oe as an input. The learning process remains unchanged (except that
each prediction p i can now depend on the actual sequence, oe, and not only on the set of elements,
S). Denote by M(A[oe]; c t ) the number of mistakes made by an off-line algorithm, A, on a sequence
oe and a target c t . Define M(A[oe]) sequence oe, define
A
A
For a given S, we are interested in the best and worst sequences. Denote by M best (S; C) the smallest
value of M(oe; C) over all oe, an ordering of S, and let oe best be a sequence that achieves this minimum
(if there are several such sequences pick one of them arbitrarily). Similarly, M worst (S; C) is the
maximal value of M(oe; C) and oe worst is a sequence such that M(oe worst ; worst (S; C).
A self-directed learning algorithm A is a one that chooses its sequence adaptively; hence the
sequence may depend on the classifications of previous instances (i.e., on the target function).
Denote by M sd (A[S]; c t ) the number of mistakes made by a self-directed algorithm A on a target
function c t 2 C, when the algorithm is given in advance S (the set from which it is allowed to pick
its queries). Define M sd (A[S]) 4
A
A
The following is a simple consequence of the definitions:
Lemma 1: For any X ; C, and a finite S ' X ,
best (S; C) - M worst (S; C) - M on-line (S; C):
2.2 Relations to Equivalence Query Models
It is well known that the on-line learning model is, basically, equivalent to the Equivalence Query
model [L89]. It is not hard to realize that our versions of the on-line scenario give rise to
corresponding variants of the EQ model. For this we need the following definitions:
ffl An equivalence-query learning algorithm with respect to S (and a concept class C) is an algorithm
A that is given in advance S as an input; Then, it works in steps as follows: In the i-th
step the algorithm outputs its hypothesis, h i ' S, and in response it gets a counterexample;
i.e., an element x denotes the target function. The process goes
on until
ffl Let F denote the function that chooses the counterexamples x i . We denote by EQ(A[S]; F; c t )
the number of counterexamples, x i , presented by F to the algorithm, A, in the course of a
learning process on the target, c t , when A knows S in advance (but does not know F ).
Finally, let EQ(S; C)
Note that the original definitions of Angluin [A89] are obtained by considering . The following
is a well known (and easy to prove) fact:
1: For every
One aspect of the last definition above is that it considers the worst case performance of the
learner over all possible choices, F , of counterexamples to its hypotheses. It turns out that by
relaxing the definition so that the learner is only confronted with F 's of a certain type, one gets
EQ models that match the various offline learning measures presented in the previous subsection.
ffl Let oe denote an ordering of the set S. Let F oe be the following strategy for choosing coun-
terexamples. Given a hypothesis h, the counterexample, F oe (h), is the minimal element of
according to the ordering oe.
ffl Let EQ(oe; C) 4
ffl Let EQ best (S; C) 4
worst (S; C) 4
This variant of the equivalence query model in which the minimal counterexample is provided to
the algorithm is studied, e.g., in [PF88].
2: For every X ; C and S ' X as above, for every ordering oe of S, EQ(oe;
Proof: Given an EQ algorithm for (S; C; oe) construct an off-line algorithm by predicting, on each
element s i , the value that the current hypothesis of the EQ algorithm, h k i
, assigns to s i . Whenever
the teacher's response indicates a prediction was wrong, present that element as a counterexample
to the EQ algorithm (and replace the current hypothesis by its revised hypothesis).
For the other direction, given an offline algorithm, define at each stage of its learning process a
hypothesis by assigning to each unseen element, s 2 S, the value the algorithm would have guessed
for s if it got responses indicating it made no mistakes along the sequence, oe, from the current
stage up to that element. Whenever a counterexample is being presented, pass on to the offline
algorithm the fact that it has erred on that element (and update the hypothesis according to its
new guesses).
Corollary 1: For every
1. EQ best (S; best (S; C).
2. EQ worst (S; worst (S; C).
3 Labeled Trees
A central tool that we employ in the quantitative analysis in this work is the notion of ranks of trees.
We shall consider certain classes of labeled trees, depending upon the classes to be learned and the
type of learning we wish to analyze. The following section introduces these technical notions and
their basic combinatorial properties.
3.1 Rank of Trees
In this subsection we define the notion of the rank of a binary tree (see, e.g., [CLR90, EH89, B92]),
which plays a central role in this paper. We then prove some simple properties of this definition.
For a tree T , if T is empty then rank(T its left subtree and TR be
its right subtree. Then,
For example, the rank of a leaf is 0.
Let
-r
. The following lemma is a standard fact about the rank:
Lemma 2: A depth d rank r tree has at most
-r
leaves.
Proof: By induction on d and r. If there is exactly one leaf (if there were two or
more, then their least common ancestor is of rank 1). If there is one leaf (which is a
special case of r = 0) or two leaves, in which case r must be 1. In all these cases the claim holds.
For the induction step, let T be a depth d rank r tree. Each of and TR are of depth at most
by the definition of rank, in the worst case one of them is of rank r and the other of
Hence, by the induction hypothesis, the number of leaves is bounded by
r
d!
r
r
d
which completes the proof.
If r is small relative to d then it may be convenient to use the weaker d r (-
-r
on the
number of leaves.
A subtree of a tree T is a subset of the nodes of T ordered by the order induced by T .
Lemma 3: The rank of a binary tree T is at least k iff it has a subtree T 0 which is a complete
binary tree of depth k.
Proof: Mark in T the nodes where the rank increases. Those are the nodes of T 0 . For a marked
node with rank i, each of its children in T has rank hence it has a marked descendant with
binary tree. For the other direction, note that the rank of a
tree is at least the rank of any of its subtrees, and that a complete binary tree of depth k has rank
k.
Lemma 4: Let T be a complete binary tree of depth k. Let L be a partition of the leaves
of T into t disjoint subsets. For to be the subtree induced by the leaves in L i
(that is, T i is the tree of all the nodes of T that have a member of L i below them). Then, there
exists such that
Proof: The proof is by induction on t. For hence the claim is obvious.
For consider the nodes in depth bk=tc in T . There are two cases: (a) if all these nodes
belong to all trees T i then each of these trees contains a complete subtree of depth bk=tc and by
Lemma 3 each of them has rank of at least bk=tc. (b) if there exists a node v in depth bk=tc which
does not belong to all the trees T i then we consider the subtree T 0 whose root is v and consists of
all the nodes below v. By the definition of v, the leaves of the tree T 0 belong to at most t \Gamma 1 of
the sets L i . In addition the depth of T 0 is at least (t\Gamma1)k
. Hence, by induction hypothesis, one of
the subtrees T 0
of T 0 is of rank at least
Finally note that T 0
i is a subtree of T i hence T i has the desired rank.
Let us just mention that the above lower bound, on the rank of the induced subtrees, is essentially
the best possible. For example, take T to be a complete binary tree. Each leaf corresponds
to a path from the root to this leaf. Call an edge of such a path a left (right) edge if it goes from
a node to its left (right) son. Let L 0 (L 1 ) be the set of leaves with more left (right) edges. Then,
it can be verified that rank(T 0
3.2 Labeled Trees
Let X denote some domain set, S ' X and C ' f0; 1g X as above.
-labeled tree is a pair, (T ; F ), where T is a binary tree and F a function mapping the
internal nodes of T into X . Furthermore, we impose the following restriction on F :
is an ancestor of t then F
ffl A branch in a tree is a path from the root to a leaf. It follows that the above mapping F is
one to one on branches of T .
ffl A branch realizes a function
if for all 1 son of t i if and only if h(F (t i 1. Note that a branch
can realize more than one function. On the other hand, if then the
branch realizes a single function.
-labeled tree is an (S; C)-tree if the set of functions realized by its branches is exactly
S denote the set of all (S; C)-trees.
ffl For a sequence of elements of X , let T C
oe denote the maximal tree in T C
S for
which every node v in the k-th level is labeled F
Note, that using this notation, a class C shatters the set of elements of a sequence, oe, if and
only if T C
oe is a complete binary tree (recall that a class C shatters a set fs if for every
there exists a function f 2 C that for all
can therefore conclude that, for any class C,
oe is a complete binary treeg:
(We shall usually omit the superscript C when it is clear from the context.)
4 Gaps between the Complexity Measures
Lemma 1 provides the basic inequalities concerning the learning complexity of the different models.
In this section we turn to a quantitative analysis of the sizes of possible gaps between these measures.
We begin by presenting, in Section 4.1, some examples of concept classes for which there exist large
gaps between the learning complexity in different models. In Section 4.3, we prove upper bounds
on the possible sizes of these gaps, bounds that show that the examples of Section 4.1 obtain
the maximal possible gap sizes. A useful tool in our analysis is a characterization of the various
complexity measures as the ranks of certain trees. This characterization is given in section 4.2.
Let us begin our quantitative analysis by stating a basic upper bound on the learning complexity
in the most demanding model (from the student's point of view), namely, M on-line (S; C). Given an
instance space X , a concept class C and a set S we define C S to be the projection of the functions
in C on the set S (note that several functions in C may collide into a single function in C S ). Using
the Halving algorithm [L88, L89] we get,
Theorem 2: For all X ; C and S as above M on-line (S; C) - log jC S j.
4.1 Some Examples
The first example demonstrates that M best (S; C) may be much smaller than M worst (S; C) and
on-line (S; C). This example was already mentioned in the introduction and appears here in more
details.
Example 1: Let X be the unit interval [0; 1]. For, 0 - a - 1 define the function f a (x) to be 0 if
x - a and 1 if x ? a. Let C 4
1g. In other words, the concept class C consists of all
intervals of the form [a; 1] for 0 - a - 1. Let
g. By Theorem 2, it is
easy to see that in this example M on-line (S; C) - log(n 1). We would like to understand how an
off-line algorithm performs in this case.
Clearly, for every sequence oe, an adversary can always force a mistake on the first element of
the sequence. Hence, M best (S; C) - 1. To see that M best (S;
this sequence the following strategy makes at most 1 mistake: predict "0" until a mistake is made.
Then, all the other elements are "1"s of the function. For a worst sequence consider

Figure

1: The concept class of Example 2
It may be seen that the adversary can force the learning algorithm to make one mistake on each of
the sets
, and hence a total of mistakes.
This is the worst possible, as this performance is already granted for an on-line algorithm as
discussed above (and, by Lemma 1 an off-line algorithm can always match the on-line performance).
The next example shows that for all n there exist sets class C,
such that M sd (S; C) - 2 and M best (S; C)
n).
loss of generality, assume that for some value d,
dg. The concept class C (see Figure 1) consists of 2 \Delta 2 d functions
d. Each function f i is defined as follows: f i
all there is a single x i which is assigned 1 and hence can be viewed as an indicator for
the corresponding function f i ). The elements are partitioned into 2 d =d "blocks" each of
size d. In each of these blocks the 2 d functions f get all the 2 d possible combinations of
values (as in Figure 1). The functions are defined similarly by switching the roles of x's
and y's. More precisely, g i serves as an
indicator for the corresponding function g i ). Again, the elements are partitioned into
blocks each of size d. In each of these blocks the 2 d functions get all the 2 d possible
combinations of values.
To see that M sd (S; C) - 2 we describe a self-directed learner for this concept class. The learner
first asks about z and predicts in an arbitrary way. Whether it is right or wrong the answer
indicates whether the target functions is one of the f i 's or one of the g i 's. In each case the learner
looks for the corresponding indicator. That is, if c t asks the x's one by one, predicting 0
on each. A mistake on some x i (i.e., c t immediately implies that the target function is f i
and no mistakes are made anymore. Symmetrically, if c t the learner asks the y's one by one,
predicting 0 on each. A mistake on some y i (i.e., c t (y implies that the target function is g i
and again no mistakes are made anymore. In any case, the total number of mistakes is at most 2.
We now prove that M best (S; C)
n). 2 The idea is that a learner must choose its sequence
in advance, but does not know whether it looks for one of the f i 's or one of the g i 's. Formally, let oe
be the (best) sequence chosen by the learner. We describe a strategy for the adversary to choose a
target function in a way that forces the learner at least d=4
=\Omega\Gamma363 n) mistakes. Let oe 0 be a prefix
of oe of length 2 d . The adversary considers the number of x i 's queried in oe 0 versus the number of
's. Assume, without loss of generality, that the number of x i 's in oe 0 is smaller than the number
of y i 's in oe 0 . The adversary then restricts itself to choosing one of the f i 's. Moreover, it eliminates
all those functions f i whose corresponding element x i appears in oe 0 . Still, there are at least 2 d =2
possible functions to choose from. Now, consider the y's queried in oe 0 . By the construction of C
we can partition the elements "groups" of size 2 d =d such that every function f j
gives the same value for all elements in each group. There are at least 2 d =2 elements y's that are
queried in oe 0 and they belong to ' groups. By simple counting, d- d. We estimate the number
of possible behaviors on these ' groups as follows: originally all 2 d behaviors on the d groups were
possible. Hence, to eliminate one of the behaviors on the ' elements one needs to eliminate 2 d\Gamma'
functions. As we eliminated at most 2 d =2 functions, the number of eliminated behaviors is at most2
In other words, there are at least 12 ' behaviors on these ' elements. On the other
hand, if we are guaranteed to make at most r mistakes it follows from Theorem 6 and Lemma 2
that the number of functions is at most
-r
must be at least '=2 - d=4
n).
4.2 Characterizing M(oe; C) Using the Rank
The main goal of this section is to characterize the measure M(oe; C). As a by-product, we present
an optimal offline prediction algorithm. I.e., an algorithm, A, such that for every sequence oe,
The next theorem provides a characterization of M(oe; C) in terms of the rank of the tree T C
oe (for
any concept class C and any sequence oe). A similar characterization was proved by Littlestone [L88,
L89] for the on-line case (see section 4.2.1 below).
Theorem 3: For all
Proof: To show that M(oe; C) - rank(T oe ) we present an appropriate algorithm. For predicting
on s 1 , the algorithm considers the tree T oe , defined above, whose root is s 1 . Denote by its
left subtree and by TR its right subtree. If rank(T predicts "0", if
predicts "1", otherwise (rank(T L
can predict arbitrarily. Again, recall that in the case that rank(T L by the definition of
rank, both rank(T L ) and rank(T R ) are smaller than rank(T oe ). Therefore, at each step the algorithm
uses for the prediction a subtree of T oe which is consistent with all the values it has seen so far. To
conclude, at each step where the algorithm made a mistake, the rank decreased by (at least) 1, so
no more than rank(T oe ) mistakes are made.
To show that no algorithm can do better, we present a strategy for the adversary for choosing
a target in C so as to guarantee that a given algorithm A makes at least rank(T oe ) mistakes. The
adversary constructs for itself the tree T oe . At step i, it holds a subtree T whose root is a node
Again, by the Halving algorithm, M on-line (S; C) and therefore also M best (S; C) are O(log n).
marked s i which is consistent with the values it already gave to A as the classification of s
After getting A's prediction on s i the adversary decides about the true values as follows: If one
of the subtrees, either TR , has the same rank as the rank of T then it chooses the value
according to this subtree. Note that, by definition of rank, at most one of the subtrees may have
this property, so this is well defined. In this case, it is possible that A guessed the correct value (for
example, the algorithm we described above does this) but the rank of the subtree that will be used
by the adversary in the i 1-th step is not decreased. The second possible case, by the definition
of rank, is that the rank of both and TR is smaller by 1 than the rank of T . In this case, the
adversary chooses the negation of A's prediction; hence, in such a step A makes a mistake and the
rank is decreased by 1. Therefore, the adversary can force a total of rank(T oe ) mistakes.
The above theorem immediately implies:
Corollary 4: For all
worst (S;
oe is an ordering of S
best (S;
oe is an ordering of S
Remark 1: It is worth noting that, by Sauer's Lemma [S72], if the concept class C has V C
dimension d then the size of T C
oe is bounded by n d (where n, as usual, is the length of oe). It follows
that, for C with small V C, the tree is small and therefore, if consistency can be checked efficiently
then the construction of the tree is efficient. This, in turn, implies the efficiency of the generic
(optimal) off-line algorithm of the above proof, for classes with "small" VC dimension.
Example 3: Consider again the concept class of Example 1. Note that in this case, the tree
T oe is exactly the binary search tree corresponding to the sequence Namely, T oe is
the tree constructed by starting with an empty tree and performing the sequence of operations
e.g. [CLR90]). Hence, M(oe; C) is exactly the
rank of this search tree.
4.2.1 Characterizing the On-line and Self-Directed Learning
To complete the picture one would certainly like to have a combinatorial characterization of
on-line (S; C) as well. Such a characterization was given by Littlestone [L88, L89]. We reformulate
this characterization in terms of ranks of trees. The proof remains similar to the one given
by Littlestone [L88, L89] and we provide it here for completeness.
Theorem 5: For all
Proof: To show that M on-line (S; C) - max
we use an adversary argument
similar to the one used in the proof of Theorem 3. The adversary uses the tree that gives the
maximum in the above expression to choose both the sequence and the classification of its elements,
so that at each time that the rank is decreased by 1 the prediction algorithm makes a mistake.
To show that M on-line (S; C) is at most
we present an appropriate
algorithm, which is again similar to the one presented in the proof of Theorem 3. For predicting
on s 2 S, we first define C 0
S to be all the functions in C S consistent with
S to be all
the functions in C S consistent with 1. The algorithm compares max
and
and predicts according to the larger one. The crucial point is that at
least one of these two values must be strictly smaller than m otherwise there is a tree in T C
whose
rank is more than m. The prediction continues in this way, so that the maximal rank is decreased
with each mistake.
Finally, the following characterization is implicit in [GS94]:
Theorem
Proof: Consider the tree T whose rank is the minimal one in T C
S . We will show that M sd (S; C)
is at most the rank of T . For this, we present an appropriate algorithm that makes use of this tree.
At each point, the learner asks for the instance which is the current node in the tree. In addition,
it predicts according to the subtree of the current node whose rank is higher (arbitrarily, if the
ranks of the two subtrees are equal). The true classification determines the child of the current
node from which the learner needs to proceed. It follows from the definition of rank that whenever
the algorithm makes a mistake the remaining subtree has rank which is strictly smaller than the
previous one.
For the other direction, given a strategy for the learner that makes at most M sd (S; C) mistakes
we can construct a tree T that describes this strategy. Namely, at each point the instances that the
learner will ask at the next stage, given the possible classifications of the current instance, determine
the two children of the current node. Now, if the rank of T was more than M sd (S; C) then this gives
the adversary a strategy to fool the learner: at each node classify the current instance according
to the subtree with higher rank. If the ranks of both subtrees are equal then on any answer by the
algorithm the adversary says the opposite. By the definition of rank, this gives rank(T ) mistakes.
Hence, rank(T ) is at most M sd (S; C) and certainly the minimum over all trees can only be smaller.
4.3 A Bound on the Size of the Gap
A natural question is how large can be the gaps between the various complexity measures. For
example, what is the maximum ratio between M worst (S; C) and M best (S; C). In Example 1 the
best is 1 and the worst is log n, which can be easily generalized to k versus \Theta(k log n). The following
theorem shows that the gap between the smallest measure, M sd (S; C), and the largest measure,
the on-line cost, cannot exceed O(log n). This, in particular, implies a similar bound for the gap
between oe best and oe worst . By Example 1, the bound is tight; i.e., there are cases which achieve
this gap. Similarly, the gap between M sd (S; C) and M best (S; C) exhibited by Example 2 is also
optimal.
Theorem 7: For of size n as above,
on-line (S; C) - M sd (S; C) \Delta log n:
We shall present two quite simple but very different proofs for this theorem. The first proof
employs the tool of labeled trees (but gives a slightly weaker result) while the second is by an
information - theoretic argument.
Proof: [using labeled trees] Consider the tree T that gives the minimum in Theorem 6. Its depth
is n and its rank, by Theorem 6, is C). By Lemma 2, this tree contains at most
-m
leaves. That is, jC
-m
. By Theorem 2, M on-line (S; C) - log
-m
Proof: [information theoretic argument] Let C S be the projection of the functions in C on the set
S (note that several functions in C may collide into a single function in C S ). Consider the number
of bits required to specify a function in C S . On one hand, at least log jC S j bits are required. On
the other hand, any self-directed learning algorithm that learns this class yields a natural coding
scheme: answer the queries asked by the algorithm according to the function c 2 C S ; the coding
consists of the list of names of elements of S on which the prediction of the algorithm is wrong.
This information is enough to uniquely identify c. It follows that M sd (S; C) \Delta log n bits are enough.
Hence,
log
Finally, by the Halving algorithm [L88, L89], it is known that
on-line (S; C) - log jC S j:
The theorem follows.
Corollary 8: For worst (S; best (S; C) \Delta log n).
Proof: Combine Theorem 7 with Lemma 1.
worst (S; C) vs. M on-line (S; C)
In this section we further discuss the question of how much can a learner benefit from knowing
the learning sequence in advance. In the terminology of our model this is the issue of determining
the possible values of the gap between M on-line (S; C) and M worst (S; C). We show (in Section 5.2)
that if one of these two measures is non-constant then so is the other. Quantitatively, if the on-line
algorithm makes k mistakes, then any off-line algorithm makes \Omega\Gamma
log mistakes on oe. For the
special cases where M worst (S; C) is either 1 or 2, we prove (in Section 5.1) that M on-line (S; C) is
at most 1 or 3 (respectively).
5.1 Simple Algorithms
In this section we present two simple on-line algorithms, E1 and E2, for the case that the off-line
algorithm is bounded by one and two mistakes (respectively) for any sequence.
Let S be a set of elements of X . If for every sequence oe, which is a permutation of S, the off-line
learning algorithm makes at most one mistake, then we show that there is an on-line algorithm E1
that makes at most one mistake on S, without knowing the actual order in advance. The algorithm
E1 uses the guaranteed off-line algorithm A and works as follows:
ffl Given an element x 2 S, choose any sequence oe that starts with x, and predict according
to A's prediction on oe, i.e. A[oe]. If a mistake is made on x, then A[oe] made a mistake and
it will not make any more mistakes on this sequence oe. Hence, we can use A[oe](c t (x)) to
get the true values for all the elements of the sequence (where by A[oe](c t (x)) we denote the
predictions that A makes on the sequence oe after getting the value c t (x)). In other words,
for any y 2 S there is a unique value that is consistent with the value c t (x) 6= A[oe] (otherwise
A[oe] can make another mistake). Therefore, E1 will make at most one mistake.
In the case that for any sequence the off-line learning algorithm makes at most two mistakes,
we present an on-line algorithm E2 that makes at most three mistakes (which is optimal due to
Call an element x bivalent with respect to y if there exist sequences oe 0 and oe 1 that both start
with xy and for oe 0 the on-line algorithm predicts "c t the on-line algorithm
predicts "c t 1). Otherwise x is univalent with respect to y
(we say that x is 1-univalent with respect to y if the prediction is always 1 and 0-univalent if the
prediction is always 0). Our on-line procedure E2, on input x, works as follows.
ffl So far we made no mistakes:
If there is no y such that x is 1-univalent with respect to y, predict "c t predict
ffl So far we made one mistake on a positive w:
If we made such a mistake then we predicted "c t which implies that there is no y such
that w is 1-univalent with respect to y. In particular, with respect to x, w is either 0-univalent
or bivalent. In both cases there is a sequence oe = wxoe 0 such that A[oe] predicts "c t
and makes a mistake. Use as the prediction on x (where again, A[oe](1) denotes
the prediction that A makes on sequence oe after getting the value c t In case of
another mistake, we have a sequence on which we already made two mistakes so it will not
make any more mistakes. Namely, we can use A[oe](1; - b) to get the value for all elements in
S.
ffl So far we made one mistake on a negative w:
If w is either 1-univalent with respect to x or bivalent with respect to x then this is similar to
the previous case. The difficulty is that this time there is also a possibility that w is 0-univalent
with respect to x. However, in this case, if we made a mistake this means that we predicted
which implies that there exists a y such that w is 1-univalent with respect to
y. Consider a sequence . By the definition of y, A[oe] predicts "c t
therefore makes its first mistake on w. Denote by the prediction on y. If this is
wrong again then all the other elements of the sequence are uniquely determined. Namely,
there is a unique function f 1 that is consistent with c t b. If, on the other hand,
b is indeed the true value of y, we denote by its prediction on x. Again, if this
is wrong, we have a unique function f 2 which is consistent with c t
Therefore, we predict c on x. In case we made a mistake (this is our second mistake) we know
for sure that the only possible functions are f 1 and f 2 (in fact, if we are lucky then f 1
and we are done). To know which of the two functions is the target we will need to make (at
one more mistake (3 in total).
5.2 A General Bound
In this section we further discuss the gap between the measures M on-line (S; C) and M worst (S; C).
We show that if the on-line makes k mistakes, then any off-line algorithm makes \Omega\Gamma
log
on oe. The proof makes use of the properties proved in Section 3.1 and the characterizations of both
the on-line and the off-line mistake bounds as ranks of trees, proved in Section 4. More precisely,
we will take a tree in T C
S with maximum rank (this rank by Theorem 5 exactly characterizes the
number of mistakes made by the on-line algorithm) and use it to construct a tree with rank which
is "not too small" and such that the nodes at each level are labeled by the same element of S. Such
a tree is of the form T oe , for some sequence oe.
Lemma 5: Given a complete labeled binary tree of depth k, (T ; F
S , there is a sequence, oe,
of elements of S, such that the tree T C
oe has
log k).
Proof: We will construct an appropriate sequence oe in phases. At phase i (starting with
we add (at most 2 i ) new elements to oe, so that the rank of T C
oe is increased by at least one (hence,
at the beginning of the ith phase the rank is at least i). At the beginning of the ith phase, we
have a collection of 2 i subtrees of T , each is of rank at least k=2 O(i 2 (in particular, at the
beginning of phase 0 there is a single subtree, T itself, whose rank is k). Each of these subtrees is
consistent with one of the leaves of the tree T C
oe we already built in previous phases (i.e., the subtree
is consistent with some assignment to the elements included in oe in all previous phases). Moreover,
the corresponding 2 i leaves induce a complete binary subtree of depth i.
In the ith phase, we consider each of the 2 i subtrees in our collection. From each such subtree T 0
we add to the sequence oe, an element r such that the rank of the subtree of T 0 rooted at r is rank(T 0 )
and the rank in each of the subtrees TR corresponding to the sons of r is rank(T
remark that the order in which we treat the subtrees within the ith phase is arbitrary and that if
some of the elements r already appear in oe we do not need to add them again. After adding all
the new elements of oe we examine again the trees TR corresponding to each subtree
. For each of them the other partitions the leaves of the tree into 2
according to the possible values for the other Hence, by Lemma 4, there exists
subtrees
R of respectively which have rank at least
and each of them is consistent with one of the leaves of the extended T C
oe . The 2 i+1 subtrees that
we get in this way form the collection of trees for phase i + 1. Finally note that by the choice of
elements r added to oe, we now get in T C
oe a complete binary subtree of depth i + 1.
If before the ith phase the rank of the subtrees in our collection is at least k i then after the ith
phase the rank of the subtrees in our collection is at least k i =2 i . Hence, a simple induction implies
that
Therefore, we can repeat this process
log phases hence obtaining a tree T C
oe of rank
log k).
Theorem 9: Let C be a concept class, X an instance space and S ' X the set of elements. Then
worst (S;
log M on-line (S; C)).
Proof: Assume that M on-line (S; k. By Theorem 5, there is a rank k tree in T C
S , and by
Lemma 3 it contains a complete binary subtree T of depth k. By Lemma 5, there is a sequence oe
for which the tree T C
oe has
log k). Hence, by Theorem 3, M(oe; C) -
log k.
A major open problem is what is the exact relationship between the on-line and the off-line
mistake bounds. The largest gap we could show is a multiplicative factor of 3=2.
worst (S;
Proof: We first give an example for the case be a space of 4 elements,
C 1 be the following 8 functions on the 4 elements: f0000; 0011; 0010; 0111; 1000; 1010; 1100; 1111g.
It can be verified (by inspection) that M on-line (S; worst (S; 2.
For a general k, we just take k independent copies of X 1 and C 1 . That is, let X k be a space of
4k elements partitioned into k sets of 4 elements. Let C k be the 8 k functions obtained by applying
one of the 8 functions in C 1 to each of the k sets of elements. Let . Due to the independence
of the k functions, it follows that M on-line (S; worst (S;
6 Discussion
In this work we analyze the effect of having various degrees of knowledge on the order of elements
in the mistake bound model of learning on the performance (i.e., the number of mistakes) of the
learner. We remark that in our setting the learner is deterministic. The corresponding questions
in the case of randomized learners remain for future research.
We can also analyze quantitatively the advantage that an online algorithm may gain from
knowing just the set of elements, S, in advance (without knowing the order, oe, of their presentation).
That is, we wish to compare the situation where the online algorithm knows nothing a-priori about
the sequence (other than that it consists of elements of X ) and the case that the algorithm knows
the set S from which the elements of the sequence are taken (but has no additional information as
for their order). The following example shows that the knowledge of S gives an advantage to the
learning algorithm:
Consider the intervals concept class of Example 1, with the instance space X
restricted to f 1
g. As proven, M on-line (X 1). On the other hand, for every
set S of size ', we showed that M on-line (S; 1). Therefore, if S is small compared to
(i.e., ' is small compared to n) the number of mistakes can be significantly improved by the
knowledge of S.

Acknowledgment

We wish to thank Moti Frances and Nati Linial for helpful discussions.



--R

"Equivalence Queries and Approximate Fingerprints"
"Separating Distribution-Free and Mistake-Bound Learning Models over the Boolean Domain"
"Learning Boolean Functions in an Infinite Attribute Space"
"Rank-r Decision Trees are a Subclass of r-Decision Lists"
"How to Use Expert Advice"
"On-line Learning of Rectangles"

"Learning Decision Trees from Random Examples"
"Universal Prediction of Individual Sequences"
"Learning Binary Relations and Total Orders"
"The Power of Self-Directed Learning"
"Apple Tasting and Nearly One-Sided Learning"
"Learning when Irrelevant Attributes Abound: A New Linear-Threshold Algo- rithm"
"Mistake Bounds and Logarithmic Linear-Threshold Learning Algorithms"
"The Weighted Majority Algorithm"
"On-line Learning with an Oblivious Environment and the Power of Randomization"
"Universal Sequential Decision Schemes from Individual Sequences"
"Learning Automata from Ordered Examples"
"On the Density of Families of Sets"
--TR
Learning decision trees from random examples needed for learning
Mistake bounds and logarithmic linear-threshold learning algorithms
Introduction to algorithms
Equivalence queries and approximate fingerprints
Learning boolean functions in an infinite attribute space
On-line learning with an oblivious environment and the power of randomization
Learning Automata from Ordered Examples
On-line learning of rectangles
Rank-<italic>r</italic> decision trees are a subclass of <italic>r</italic>-decision lists
Learning binary relations and total orders
How to use expert advice
The weighted majority algorithm
The Power of Self-Directed Learning
Learning Quickly When Irrelevant Attributes Abound

--CTR
Peter Damaschke, Adaptive Versus Nonadaptive Attribute-Efficient Learning, Machine Learning, v.41 n.2, p.197-215, November 2000
Paul Burke , Sue Nguyen , Pen-Fan Sun , Shelley Evenson , Jeong Kim , Laura Wright , Nabeel Ahmed , Arjun Patel, Writing the BoK: designing for the networked learning environment of college students, Proceedings of the 2005 conference on Designing for User eXperience, November 03-05, 2005, San Francisco, California
mistake-bound;On-Line Learning;rank of trees