Skip to main content
Log in

On Bayes Methods for On-Line Boolean Prediction

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract.

We examine a general Bayesian framework for constructing on-line prediction algorithms in the experts setting. These algorithms predict the bits of an unknown Boolean sequence using the advice of a finite set of experts. In this framework we use probabilistic assumptions on the unknown sequence to motivate prediction strategies. However, the relative bounds that we prove on the number of prediction mistakes made by these strategies hold for any sequence. The Bayesian framework provides a unified derivation and analysis of previously known prediction strategies, such as the Weighted Majority and Binomial Weighting algorithms. Furthermore, it provides a principled way of automatically adapting the parameters of Weighted Majority to the sequence, in contrast to previous ad hoc doubling techniques. Finally, we discuss the generalization of our methods to algorithms making randomized predictions.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Author information

Authors and Affiliations

Authors

Additional information

Received February 5, 1997; revised July 17, 1997.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Cesa-Bianchi, N., Helmbold, D. & Panizza, S. On Bayes Methods for On-Line Boolean Prediction . Algorithmica 22, 112–137 (1998). https://doi.org/10.1007/PL00013825

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/PL00013825

Navigation