A loss bound model for on-line stochastic prediction strategies
Kenji Yamanishi · Conference on Learning Theory · 1991
This paper proposes a performance criterion for on-line stochastic prediction strategies, which we call a loss bound model It has been developed by extending Littlestone's mistake bound model into the case where the target rule is stochastic. In the loss bound model, we assume that the label for an instance is stochastically assigned by a conditional probability distribution over a set of labels for any given an instance. At each stage, an on-line stochastic prediction strategy takes as input an instance and outputs a probability distribution over the set of labels for the input. It then receives a reinforcement and updates its prediction strategy for the next stage. In the loss bound model, the correctness of a stochastic prediction strategy is measured in terms of “loss,” a function of the predicted probability values and the observed correct label.