Algorithmic complexity bounds on future prediction errors

DOI10.1016/J.IC.2006.10.004zbMATH Open1107.68044arXivcs/0701120OpenAlexW2139750407WikidataQ58012403 ScholiaQ58012403MaRDI QIDQ865627FDOQ865627

Jürgen Schmidhuber, Marcus Hutter, Alexey Chernov

Publication date: 20 February 2007

Published in: Information and Computation (Search for Journal in Brave)

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\mathrm{...}{x}_t$. We bound the future prediction performance on $x_{t+1}{x}_{t+2}\mathrm{...}$ 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.

Full work available at URL: https://arxiv.org/abs/cs/0701120

Recommendations

• Algorithmic Learning Theory
• scientific article; zbMATH DE number 3951668
• Sequential predictions based on algorithmic complexity
• scientific article; zbMATH DE number 2086606
• The complexity and effectiveness of prediction algorithms
• scientific article; zbMATH DE number 218676
• Algorithmic statistics and prediction for polynomial time-bounded algorithms
• Learning Theory
• Complexity and effective prediction
• scientific article; zbMATH DE number 3967748

zbMATH Keywords

Kolmogorov complexityrandomness deficiencySolomonoff priortotal errorfuture lossmonotone conditional complexityonline sequential predictionposterior bounds

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Cites Work

• Title not available (Why is that?)
• A formal theory of inductive inference. Part I
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
• Clustering by Compression
• Complexity-based induction systems: Comparisons and convergence theorems
• Universal artificial intelligence. Sequential decisions based on algorithmic probability.
• Relations between varieties of kolmogorov complexities
• Convergence and loss bounds for bayesian sequence prediction
• 10.1162/1532443041827952
• Sequential predictions based on algorithmic complexity
• HIERARCHIES OF GENERALIZED KOLMOGOROV COMPLEXITIES AND NONENUMERABLE UNIVERSAL MEASURES COMPUTABLE IN THE LIMIT
• Algorithmic Learning Theory
• Convergence and Error Bounds for Universal Prediction of Nonbinary Sequences
• Title not available (Why is that?)
• Learning Theory
• Sequence prediction based on monotone complexity.
• Algorithmic Learning Theory
• New error bounds for Solomonoff prediction

Cited In (13)

• Most sequences are stochastic
• A philosophical treatise of universal induction
• Does snooping help?
• Unresolved computation and optimal predictions
• Improving and benchmarking of algorithms for decision making with lower previsions
• New error bounds for Solomonoff prediction
• Open problems in universal induction \& intelligence
• Title not available (Why is that?)
• On universal prediction and Bayesian confirmation
• Algorithmic Learning Theory
• On calibration error of randomized forecasting algorithms
• Sequential predictions based on algorithmic complexity
• Why it is computationally harder to reconstruct the past than to predict the future

This page was built for publication: Algorithmic complexity bounds on future prediction errors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q865627)