Sequential prediction of individual sequences under general loss functions

摘要: We consider adaptive sequential prediction of arbitrary binary sequences when the performance is evaluated using a general loss function. The goal to predict on each individual sequence nearly as well best strategy in given comparison class (possibly adaptive) strategies, called experts. By function, we generalize previous work universal prediction, forecasting, and data compression. However, here restrict ourselves case finite. For sequence, define regret total entire suffered by predictor, minus predictor that performs particular sequence. show for large functions, minimax either /spl theta/(log N) or Omega/(/spl radic//spl Lscr/log N), depending where N number predictors and/spl Lscr/ length be predicted. former was shown previously Vovk (1990); give simplified analysis with an explicit closed form constant formula, probabilistic argument shows this possible. Some weak regularity conditions are imposed function obtaining these results. also extend our predicting take real values interval [0,1].