License
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-6327
URL: http://drops.dagstuhl.de/opus/volltexte/2006/632/

Chernov, Alexey ; Hutter, Marcus ; Schmidhuber, Jürgen

Complexity Monotone in Conditions and Future Prediction Errors

pdf-format:
Dokument 1.pdf (296 KB)


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 $mu$ by the algorithmic complexity of $mu$. Here we assume we are at a time $t>1$ and already observed $x=x_1...x_t$. We bound the future prediction performance on $x_{t+1}x_{t+2}...$ by a new variant of algorithmic complexity of $mu$ 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.

BibTeX - Entry

@InProceedings{chernov_et_al:DSP:2006:632,
  author =	{Alexey Chernov and Marcus Hutter and J{\"u}rgen Schmidhuber},
  title =	{Complexity Monotone in Conditions and Future Prediction Errors},
  booktitle =	{Kolmogorov Complexity and Applications},
  year =	{2006},
  editor =	{Marcus Hutter  and Wolfgang Merkle and Paul M.B. Vitanyi},
  number =	{06051},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Internationales Begegnungs- und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2006/632},
  annote =	{Keywords: Kolmogorov complexity, posterior bounds, online sequential prediction, Solomonoff prior, monotone conditional complexity, total error, future loss, ra}
}

Keywords: Kolmogorov complexity, posterior bounds, online sequential prediction, Solomonoff prior, monotone conditional complexity, total error, future loss, ra
Seminar: 06051 - Kolmogorov Complexity and Applications
Issue date: 2006
Date of publication: 31.07.2006


DROPS-Home | Fulltext Search | Imprint Published by LZI