21.1 Online Classification in the Realizable Case 289tional aspect of learning, and do not restrict the algorithms to be efficient. In
Section 21.3 and Section 21.4 we study efficient online learning algorithms.
To simplify the presentation, we start with the case of a finite hypothesis class,
namely,|H|<∞.
In PAC learning, we identified ERM as a good learning algorithm, in the sense
that ifHis learnable then it is learnable by the rule ERMH. A natural learning
rule for online learning is to use (at any online round) any ERM hypothesis,
namely, any hypothesis which is consistent with all past examples.
Consistentinput:A finite hypothesis classH
initialize:V 1 =H
fort= 1, 2 ,...
receivext
choose anyh∈Vt
predictpt=h(xt)
receive true labelyt=h?(xt)
updateVt+1={h∈Vt:h(xt) =yt}TheConsistentalgorithm maintains a set,Vt, of all the hypotheses which
are consistent with (x 1 ,y 1 ),...,(xt− 1 ,yt− 1 ). This set is often called the version
space. It then picks any hypothesis fromVtand predicts according to this hy-
pothesis.
Obviously, wheneverConsistentmakes a prediction mistake, at least one
hypothesis is removed fromVt. Therefore, after makingMmistakes we have
|Vt|≤|H|−M. SinceVtis always nonempty (by the realizability assumption it
containsh?) we have 1≤|Vt|≤|H|−M. Rearranging, we obtain the following:
corollary21.2 LetHbe a finite hypothesis class. TheConsistentalgorithm
enjoys the mistake boundMConsistent(H)≤|H|− 1.
It is rather easy to construct a hypothesis class and a sequence of examples on
whichConsistentwill indeed make|H|−1 mistakes (see Exercise 1). Therefore,
we present a better algorithm in which we chooseh∈Vtin a smarter way. We
shall see that this algorithm is guaranteed to make exponentially fewer mistakes.
Halving
input:A finite hypothesis classH
initialize:V 1 =H
fort= 1, 2 ,...
receivext
predictpt= argmaxr∈{ 0 , 1 }|{h∈Vt:h(xt) =r}|
(in case of a tie predictpt= 1)
receive true labelyt=h?(xt)
updateVt+1={h∈Vt:h(xt) =yt}