Convergence and Error Bounds for Universal Prediction of Nonbinary Sequences

MaRDI QIDQ4797063zbMATH OpenFDO

Authors Marcus Hutter

Publication date 12 March 2003

Full work available at URL https://arxiv.org/abs/cs/0106036, http://link.springer.de/link/service/series/0558/bibs/2167/21670239.htm

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Measures of information, entropy (94A17)

Abstract: Solomonoff's uncomputable universal prediction scheme $xi$ allows to predict the next symbol $x_k$ of a sequence $x_1\mathrm{...}{x}_{k-1}$ for any Turing computable, but otherwise unknown, probabilistic environment $mu$. This scheme will be generalized to arbitrary environmental classes, which, among others, allows the construction of computable universal prediction schemes $xi$. Convergence of $xi$ to $mu$ in a conditional mean squared sense and with $mu$ probability 1 is proven. It is shown that the average number of prediction errors made by the universal $xi$ scheme rapidly converges to those made by the best possible informed $mu$ scheme. The schemes, theorems and proofs are given for general finite alphabet, which results in additional complications as compared to the binary case. Several extensions of the presented theory and results are outlined. They include general loss functions and bounds, games of chance, infinite alphabet, partial and delayed prediction, classification, and more active systems.

Recommendations

• New error bounds for Solomonoff prediction
• 10.1162/1532443041827952
• Universal prediction of individual sequences
• Theory and Applications of Models of Computation
• Sequential predictions based on algorithmic complexity

Cited in

(20)

• Measuring the efficiency of the intraday Forex market with a universal data compression algorithm
• Prediction of random sequences and universal coding
• Universal prediction of random binary sequences in a noisy environment
• Open problems in universal induction \& intelligence
• Universal probability-free prediction
• Upper estimate of partial prediction degree for general regular superevents
• On universal prediction and Bayesian confirmation
• Sequential predictions based on algorithmic complexity
• Universal prediction of selected bits
• Is There an Elegant Universal Theory of Prediction?
• Convergence and loss bounds for bayesian sequence prediction
• Universal prediction of individual sequences
• scientific article; zbMATH DE number 1552327 (Why is no real title available?)
• A universal prediction lemma and applications to universal data compression and prediction
• 10.1162/1532443041827952
• Theory and Applications of Models of Computation
• New error bounds for Solomonoff prediction
• Robust inference of trees
• On generalized computable universal priors and their convergence
• Algorithmic complexity bounds on future prediction errors

This page was built for publication: Convergence and Error Bounds for Universal Prediction of Nonbinary Sequences

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