2026-07-20T05:46:26Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:632 2024-03-06T11:06:41Z ddc:004 open_access

Complexity Monotone in Conditions and Future Prediction Errors Chernov, Alexey Hutter, Marcus Schmidhuber, Jürgen Kolmogorov complexity posterior bounds online sequential prediction Solomonoff prior monotone conditional complexity total error future loss ra 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Alexey Chernov and Marcus Hutter and Jürgen Schmidhuber 2006 Is Part Of Dagstuhl Seminar Proceedings, Volume 6051, Kolmogorov Complexity and Applications (2006) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DagSemProc.06051.6 urn:nbn:de:0030-drops-6327 https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06051.6 eng https://creativecommons.org/licenses/by/4.0/legalcode