Is There an Elegant Universal Theory of Prediction?

DOI10.1007/11894841_23MaRDI QIDQ3522992zbMATH OpenOpenAlexFDO

Authors Shane Legg

Publication date 4 September 2008

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Inference from stochastic processes and prediction (62M20) Computational learning theory (68Q32)

Abstract: Solomonoff's inductive learning model is a powerful, universal and highly elegant theory of sequence prediction. Its critical flaw is that it is incomputable and thus cannot be used in practice. It is sometimes suggested that it may still be useful to help guide the development of very general and powerful theories of prediction which are computable. In this paper it is shown that although powerful algorithms exist, they are necessarily highly complex. This alone makes their theoretical analysis problematic, however it is further shown that beyond a moderate level of complexity the analysis runs into the deeper problem of Goedel incompleteness. This limits the power of mathematics to analyse and study prediction algorithms, and indeed intelligent systems in general.

Recommendations

• Theory and Applications of Models of Computation
• Universal prediction of selected bits
• New error bounds for Solomonoff prediction
• Convergence and Error Bounds for Universal Prediction of Nonbinary Sequences
• Algorithmic Probability: Theory and Applications

Cited in

(9)

• Algorithmic Probability: Theory and Applications
• Genetic Programming for Inductive Inference of Chaotic Series
• scientific article; zbMATH DE number 2089364 (Why is no real title available?)
• Natural descriptions and anthropic bias: extant problems in Solomonoff induction
• Open problems in universal induction \& intelligence
• Universal prediction of selected bits
• Physical limits of inference
• Making Solomonoff induction effective. Or: you can learn what you can bound
• On the computability of Solomonoff induction and knowledge-seeking

This page was built for publication: Is There an Elegant Universal Theory of Prediction?

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