|
NeuroCOLT
Technical Report NC-TR-96-018
Tracking
the best disjunction
Peter
Auer
Institute for Theoretical Computer Science
Technische Universitaet Graz
Austria
Manfred
Warmuth
University of California at Santa Cruz
USA
Abstract
Littlestone developed a simple deterministic on-line learning
algorithm for learning $k$-literal disjunctions. This algorithm (called
Winnow) keeps one weight for each of the $n$ variables and does multiplicative
updates to its weights. We develop a randomized version of 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
disjunction schedule $\Tau$ is a sequence of disjunctions
(one per trial) and the 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. By combining the tracking
capability with existing applications of Winnow we are able to enhance
these applications to the shifting case as well.
Download Compressed
Postscript
|