# Halving Algorithm

The Halving Algorithm is perhaps the simplest algorithm for On-line Prediction. Barzdin and Freivald (1972), Angluin (1988), and Littlestone (1988) are credited with its introduction; the name was suggested by Littlestone (1988).

Suppose the sequence of observations is known to belong to a finite class consisting of {$K$} sequences, which will be called *experts*. The following algorithm (the *Halving Algorithm*) makes at most {$\log K$} errors when predicting this sequence. Predict with the majority of the {$K$} experts in the class until you make a mistake. At least half of the experts will also make a mistake; remove them from the class. Predict with the majority of the remaining experts until you make a mistake. Etc.

The Halving Algorithm assumes that one of the experts is perfect ("knows" the sequence to be observed). The Weighted Majority Algorithm extends the Halving Algorithm beyond this case.

### Bibliography

- Dana Angluin. Queries and concept learning.
*Machine Learning*2:319 - 342, 1988. - J. Barzdin and R. Freivald. On the prediction of general recursive functions.
*Soviet Mathematics Doklady*, 13:1224 - 1228, 1972. - Nick Littlestone. Learning quickly when irrelevant attributes abound: a new linear-threshold algorithm.
*Machine Learning*2:285 - 318, 1988.