Monotone conditional complexity bounds on future prediction errors

Alexey Chernov, Marcus Hutter

Research output: Chapter in Book/Conference proceeding with ISSN or ISBNConference contribution with ISSN or ISBN

Abstract

We bound the future loss when predicting any (computably) stochastic sequence online. Solomonoff finitely bounded the total deviation of his universal predictor M from the true distribution m by the algorithmic complexity of m. Here we assume we are at a time t>1 and already observed x=x 1...xt. We bound the future prediction performance on xt+1xt+2... by a new variant of algorithmic complexity of m given x, plus the complexity of the randomness deficiency of x. The new complexity is monotone in its condition in the sense that this complexity can only decrease if the condition is prolonged. We also briefly discuss potential generalizations to Bayesian model classes and to classification problems.
Original languageEnglish
Title of host publicationProceedings of the 16th International Conference Algorithmic Learning Theory 2005
Place of PublicationBerlin Heidelberg
PublisherSpringer
Pages414-428
Number of pages15
Volume3734
DOIs
Publication statusPublished - 31 Dec 2005
EventProceedings of the 16th International Conference Algorithmic Learning Theory 2005 - Singapore, October 8-11, 2005
Duration: 31 Dec 2005 → …

Publication series

NameLecture Notes in Computer Science

Conference

ConferenceProceedings of the 16th International Conference Algorithmic Learning Theory 2005
Period31/12/05 → …

Fingerprint Dive into the research topics of 'Monotone conditional complexity bounds on future prediction errors'. Together they form a unique fingerprint.

  • Cite this

    Chernov, A., & Hutter, M. (2005). Monotone conditional complexity bounds on future prediction errors. In Proceedings of the 16th International Conference Algorithmic Learning Theory 2005 (Vol. 3734, pp. 414-428). (Lecture Notes in Computer Science). Springer. https://doi.org/10.1007/11564089_32