On-Line Maximum Likelihood Prediction with Respect to General Loss Functions

AbstractThis paper introduces a new family of deterministic and stochastic on-line prediction algorithms which work with respect to general loss functions and analyzes their behavior in terms of expected loss bounds. The algorithms useparametric probabilistic modelsregardless of the kind of loss function used. The key ideas of the algorithms are to iteratively estimate the probabilistic model using the maximum likelihood method and then to construct an optimal prediction function that minimizes the average of the loss taken with respect to the estimated probabilistic model. A future outcome is predicted using this optimal prediction function. We analyze the algorithms in the cases where the target distribution is (1)k-dimensional parametric andkis known, (2)k-dimensional parametric butkis unknown, and (3) nonparametric. For all the cases, we derive upper bounds on the expected instantaneous or cumulative losses for the algorithms with respect to a large family of loss functions satisfying the constraint introduced by Merhav and Feder. These loss bounds show new universal relations among the expected prediction accuracy, the indexes of the loss function, the complexity of the target rule, and the number of training examples