A Loss Bound Model for On-Line Stochastic Prediction Strategies

Abstract

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. Also proposed here is a new stochastic prediction strategy developed by extending Desantis, Markowsky, & Wegman's Bayesian weighted average type stochastic prediction strategy into the case where the weighted average is taken over a parametric countable hypothesis space. Here a parametric countable hypothesis space refers to a pool of stochastic prediction functions specified by real-valued parameters as well as a countable model. Derived are upper bounds on the cumulative log loss, expected cumulative log loss, and expected cumulative quadratic loss for the proposed strategy. Specifically, it is proven that the cumulative log loss is bounded by the description length for any countable model itself plus Rissanen's predictive stochastic complexity relative to the model. This suggests that the cumulative loss bound may be approximated by the total description length relative to a single countable model selected by Rissanen's Minimum Description Length(MDL) principle. Further, on the assumption that examples are independently drawn according to the target rule which belongs to the hypothesis space in question, it may be shown that the proposed strategy is optimal in the sense that the upper bound on the expected cumulative loss asymptotically matches Rissanen's lower bound, which is derived from the viewpoint of source coding theory. Also derived is an upper bound on the smallest sample size for which, for any arbitrary target rule, the mean per log loss for the proposed strategy will lie within of that for the target rule itself. The proposed strategy is applied to on-line prediction using stochastic decision lists and Boltzmann perceptron networks, and loss bounds are calculated for these classes.