Algorithmic complexity bounds on future prediction errors

Alexey Chernov, Marcus Hutter, Jürgen Schmidhuber

Research output: Contribution to journalArticlepeer-review

6 Scopus citations

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 μ by the algorithmic complexity of μ. Here we assume that we are at a time t> 1 and have already observed x=x1···xt. We bound the future prediction performance onxt+1x t+2··· by a new variant of algorithmic complexity of μ 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. © 2006 Elsevier Inc. All rights reserved.
Original languageEnglish (US)
Pages (from-to)242-261
Number of pages20
JournalInformation and Computation
Volume205
Issue number2
DOIs
StatePublished - Jan 1 2007
Externally publishedYes

ASJC Scopus subject areas

  • Computational Theory and Mathematics
  • Theoretical Computer Science
  • Information Systems
  • Computer Science Applications

Fingerprint

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

Cite this