Part of Advances in Neural Information Processing Systems 9 (NIPS 1996)
Nick Littlestone, Chris Mesterharm
We study a mistake-driven variant of an on-line Bayesian learn(cid:173) ing algorithm (similar to one studied by Cesa-Bianchi, Helmbold, and Panizza [CHP96]). This variant only updates its state (learns) on trials in which it makes a mistake. The algorithm makes binary classifications using a linear-threshold classifier and runs in time lin(cid:173) ear in the number of attributes seen by the learner. We have been able to show, theoretically and in simulations, that this algorithm performs well under assumptions quite different from those embod(cid:173) ied in the prior of the original Bayesian algorithm. It can handle situations that we do not know how to handle in linear time with Bayesian algorithms. We expect our techniques to be useful in deriving and analyzing other apobayesian algorithms.