New Error Bounds for Solomonoff Prediction
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
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",
}