Computer Science Department
School of Computer Science, Carnegie Mellon University
On-Line Algorithms in Machine Learning
Avrim L. Blum
This paper is based on a survey talk presented at the June 1996 Dagstuhl Workshop on On-Line Algorithms.
Keywords: On-line algorithms, computational learning theory, on-line
prediction, competitive analysis, machine learning
The areas of On-Line Algorithms and Machine Learning are both
concerned with problems of making decisions about the present
based only on knowledge of the past. Although these areas differ in
terms of their emphasis and the problems typically studied, there are a
collection of results in Computational Learning Theory that fit nicely
into the "on-line algorithms" framework. This survey article
discusses some of the results, models, and open problems from
Computational Learning Theory that seem particularly interesting from
the point of view of on-line algorithms research.
The emphasis in this article is on describing some of the simpler,
more intuitive results, whose proofs can be given in their entirety.
Pointers to the literature are given for more sophisticated versions
of these algorithms.