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

概要

論文の詳細を見る
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.
社団法人電子情報通信学会の論文
1999-02-25