Sequential predictions based on algorithmic complexity

DOI10.1016/J.JCSS.2005.07.001MaRDI QIDQ2581758zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Marcus Hutter

Publication date 10 January 2006

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

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

zbMATH Keywords

Algorithmic information theoryConvergenceMinimal description lengthMonotone Kolmogorov complexitySelf-optimizationSequence predictionSolomonoff's prior

Mathematics Subject Classification ID

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

Abstract: This paper studies sequence prediction based on the monotone Kolmogorov complexity Km=-log m, i.e. based on universal deterministic/one-part MDL. m is extremely close to Solomonoff's universal prior M, the latter being an excellent predictor in deterministic as well as probabilistic environments, where performance is measured in terms of convergence of posteriors or losses. Despite this closeness to M, it is difficult to assess the prediction quality of m, since little is known about the closeness of their posteriors, which are the important quantities for prediction. We show that for deterministic computable environments, the "posterior" and losses of m converge, but rapid convergence could only be shown on-sequence; the off-sequence convergence can be slow. In probabilistic environments, neither the posterior nor the losses converge, in general.

Recommendations

• Sequence prediction based on monotone complexity.
• Algorithmic Learning Theory
• Algorithmic complexity bounds on future prediction errors
• Learning Theory
• The complexity and effectiveness of prediction algorithms

Cites work

• A formal theory of inductive inference. Part I
• A Theory of Program Size Formally Identical to Information Theory
• A variant of the Kolmogorov concept of complexity
• Algorithmic Learning Theory
• Complexity-based induction systems: Comparisons and convergence theorems
• Convergence and Error Bounds for Universal Prediction of Nonbinary Sequences
• Convergence and loss bounds for bayesian sequence prediction
• HIERARCHIES OF GENERALIZED KOLMOGOROV COMPLEXITIES AND NONENUMERABLE UNIVERSAL MEASURES COMPUTABLE IN THE LIMIT
• scientific article; zbMATH DE number 2089364 (Why is no real title available?)
• scientific article; zbMATH DE number 3427210 (Why is no real title available?)
• scientific article; zbMATH DE number 4160608 (Why is no real title available?)
• scientific article; zbMATH DE number 3489016 (Why is no real title available?)
• scientific article; zbMATH DE number 3492569 (Why is no real title available?)
• scientific article; zbMATH DE number 3560492 (Why is no real title available?)
• scientific article; zbMATH DE number 1010621 (Why is no real title available?)
• scientific article; zbMATH DE number 3271180 (Why is no real title available?)
• scientific article; zbMATH DE number 3085434 (Why is no real title available?)
• Learning Theory
• Minimum complexity density estimation
• Minimum description length induction, Bayesianism, and Kolmogorov complexity
• New error bounds for Solomonoff prediction
• On minimal-program complexity measures
• On the relation between descriptional complexity and algorithmic probability
• Process complexity and effective random tests
• Randomness conservation inequalities; information and independence in mathematical theories
• Sequence prediction based on monotone complexity.
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
• Universal artificial intelligence. Sequential decisions based on algorithmic probability.

Cited in

(13)

• Prediction of stochastic sequences
• Discrete sequence prediction and its applications
• Open problems in universal induction \& intelligence
• A complete theory of everything (will be subjective)
• Predictions and algorithmic statistics for infinite sequences
• Simulation complexity
• Series prediction based on algebraic approximants
• Convergence and Error Bounds for Universal Prediction of Nonbinary Sequences
• Algorithms with Predictions
• Sequence prediction based on monotone complexity.
• Learning Theory
• Prediction and MDL for infinite sequences
• Algorithmic complexity bounds on future prediction errors

This page was built for publication: Sequential predictions based on algorithmic complexity

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