The search functionality is under construction.

The search functionality is under construction.

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

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

Copy

Ichiro TAJIKA, Eiji TAKIMOTO, Akira MARUOKA, "An On-Line Prediction Algorithm Combining Several Prediction Strategies in the Shared Bet Model" in IEICE TRANSACTIONS on Information,
vol. E82-D, no. 2, pp. 348-355, February 1999, doi: .

Abstract: 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.

URL: https://global.ieice.org/en_transactions/information/10.1587/e82-d_2_348/_p

Copy

@ARTICLE{e82-d_2_348,

author={Ichiro TAJIKA, Eiji TAKIMOTO, Akira MARUOKA, },

journal={IEICE TRANSACTIONS on Information},

title={An On-Line Prediction Algorithm Combining Several Prediction Strategies in the Shared Bet Model},

year={1999},

volume={E82-D},

number={2},

pages={348-355},

abstract={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.},

keywords={},

doi={},

ISSN={},

month={February},}

Copy

TY - JOUR

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

T2 - IEICE TRANSACTIONS on Information

SP - 348

EP - 355

AU - Ichiro TAJIKA

AU - Eiji TAKIMOTO

AU - Akira MARUOKA

PY - 1999

DO -

JO - IEICE TRANSACTIONS on Information

SN -

VL - E82-D

IS - 2

JA - IEICE TRANSACTIONS on Information

Y1 - February 1999

AB - 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.

ER -