previous home search |
LaTeX (30kb)
PostScript (230kb)
PDF (233kb)
Html/Gif
| contact up next |

## New Error Bounds for Solomonoff Prediction

Author:Marcus Hutter (1999-2001) Comments:13 LaTeX pages Subj-class:Artificial Intelligence; Learning; ACM-class:I.2.6; F.1.3; E.4; F.2 Reference:Journal of Computer and System Science, 62:4 (2001) 653-667 Report-no:IDSIA-11-00 and cs.AI/9912008 Paper:LaTeX (30kb) - PostScript (230kb) - PDF (233kb) - Html/Gif Slides:PostScript - PDF

Keywords:Induction; Solomonoff, Bayesian, deterministic prediction; algorithmic probability; Kolmogorov complexity.

Abstract:Several new relations between Solomonoff prediction and Bayesian prediction and general probabilistic prediction schemes will be proved. Among others they show that the number of errors in Solomonoff prediction is finite for computable prior probability, if finite in the Bayesian case. Deterministic variants will also be studied. The most interesting result is that the deterministic variant of Solomonoff prediction is optimal compared to any other probabilistic or deterministic prediction scheme apart from additive square root corrections only. This makes it well suited even for difficult prediction problems, where it does not suffice when the number of errors is minimal to within some factor greater than one. Solomonoff's original bound and the ones presented here complement each other in a useful way.

Contents:

- Introduction
- Preliminaries
- Probabilistic Sequence Prediction
- Deterministic Sequence Prediction
- Conclusions

previous home search |
LaTeX (30kb)
PostScript (230kb)
PDF (233kb)
Html/Gif
| contact up next |

@Article{Hutter:99, author = "Marcus Hutter", institution = "Istituto Dalle Molle di Studi sull'Intelligenza Artificiale", title = "New Error Bounds for {Solomonoff} Prediction", month = jun, year = "2001", volume = "62", number = "4", pages = "653--667", journal = "Journal of Computer and System Science", address = "Manno(Lugano), CH", keywords = "Kolmogorov Complexity, Solomonoff Prediction, Error Bound, Induction, Learning, Algorithmic Information Theory, Bayes", url = "http://arxiv.org/abs/cs.AI/9912008", url2 = "http://www.hutter1.net/ai/perrbnd.htm", ftp = "ftp://ftp.idsia.ch/pub/techrep/IDSIA-11-00.ps.gz", abstract = "Several new relations between Solomonoff prediction and Bayesian prediction and general probabilistic prediction schemes will be proved. Among others they show that the number of errors in Solomonoff prediction is finite for computable prior probability, if finite in the Bayesian case. Deterministic variants will also be studied. The most interesting result is that the deterministic variant of Solomonoff prediction is optimal compared to any other probabilistic or deterministic prediction scheme apart from additive square root corrections only. This makes it well suited even for difficult prediction problems, where it does not suffice when the number of errors is minimal to within some factor greater than one. Solomonoff's original bound and the ones presented here complement each other in a useful way.", note = "Submitted December 1999, revised December 2000", }

previous home search |
LaTeX (30kb)
PostScript (230kb)
PDF (233kb)
Html/Gif
| contact up next |