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:

  1. Introduction
  2. Preliminaries
  3. Probabilistic Sequence Prediction
  4. Deterministic Sequence Prediction
  5. Conclusions
 previous  home  search  LaTeX (30kb)   PostScript (230kb)   PDF (233kb)   Html/Gif   contact    up    next  

BibTeX Entry

@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