An on-line prediction algorithm combining several prediction strategies inthe shared bet model

One of the most important problems in machine learning is to predict a bina ry value by observing a sequence of outcomes, up to the present time step, generated from some unknown source. Vovk and Cesa-Bianchi ct al. independen tly proposed an on-line prediction model where prediction algorithms are as sumed to be given a collection of prediction strategies called experts and hence be allowed to use the predictions they make. In this model, no assump tion is made about the way the sequence of bits to be predicted is generate d, and the performance of the algorithm is measured by the difference betwe en the number of mistakes it makes on the bit sequence and the number of mi stakes made by the best expert, on the same sequence. In this paper we exte nd the model by introducing a notion of investment. That is, both the predi ction algorithm and the experts are required to make bets on their predicti ons 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 impractic al, and we also give an efficient prediction algorithm that turns out to be nearly optimal.