A decision-theoretic extension of stochastic complexity and its applications to learning

摘要: Rissanen (1978) has introduced stochastic complexity to define the amount of information in a given data sequence relative hypothesis class probability densities, where is measured terms logarithmic loss associated with universal compression. This paper introduces notion extended (ESC) and demonstrates its effectiveness design analysis learning algorithms on-line prediction batch-learning scenarios. ESC can be thought as an extension Rissanen's decision-theoretic setting general real-valued function used distortion measure. As application prediction, this shows that sequential realization produces algorithm called Vovk's aggregating strategy, which Bayes algorithm. We derive upper bounds on cumulative for strategy both expected form worst case continuous. batch-learning, batch-approximation induces minimum L-complexity (MLC), description length (MDL) principle. statistical risk MLC, are least date. Through we give unifying view most effective have been explored computational theory.