The search functionality is under construction.
The search functionality is under construction.

An On-Line Prediction Algorithm Combining Several Prediction Strategies in the Shared Bet Model

Ichiro TAJIKA, Eiji TAKIMOTO, Akira MARUOKA

  • Full Text Views

    0

  • Cite this

Summary :

One of the most important problems in machine learning is to predict a binary value by observing a sequence of outcomes, up to the present time step, generated from some unknown source. Vovk and Cesa-Bianchi et al. independently proposed an on-line prediction model where prediction algorithms are assumed to be given a collection of prediction strategies called experts and hence be allowed to use the predictions they make. In this model, no assumption is made about the way the sequence of bits to be predicted is generated, and the performance of the algorithm is measured by the difference between the number of mistakes it makes on the bit sequence and the number of mistakes made by the best expert on the same sequence. In this paper we extend the model by introducing a notion of investment. That is, both the prediction algorithm and the experts are required to make bets on their predictions at each time step, and the performance of the algorithm is now measured with respect to the total money lost, rather than the number of mistakes. We analyze our algorithms in the particular situation where all the experts share the same amount of bets at each time step. In this shared bet model, we give a prediction algorithm that is in some sense optimal but impractical, and we also give an efficient prediction algorithm that turns out to be nearly optimal.

Publication
IEICE TRANSACTIONS on Information Vol.E82-D No.2 pp.348-355
Publication Date
1999/02/25
Publicized
Online ISSN
DOI
Type of Manuscript
PAPER
Category
Algorithm and Computational Complexity

Authors

Keyword