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)

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

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)