Algorithmic complexity bounds on future prediction errors

Alexey Chernov; Marcus Hutter; Jürgen Schmidhuber

doi:10.1016/j.ic.2006.10.004

Algorithmic complexity bounds on future prediction errors

Alexey Chernov^*, Marcus Hutter, Jürgen Schmidhuber

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

7 Citations (Scopus)

Abstract

We bound the future loss when predicting any (computably) stochastic sequence online. Solomonoff finitely bounded the total deviation of his universal predictor M from the true distribution μ by the algorithmic complexity of μ. Here we assume that we are at a time t> 1 and have already observed x=x₁···x_t. We bound the future prediction performance onx_t+1x _t+2··· by a new variant of algorithmic complexity of μ given x, plus the complexity of the randomness deficiency of x. The new complexity is monotone in its condition in the sense that this complexity can only decrease if the condition is prolonged. We also briefly discuss potential generalizations to Bayesian model classes and to classification problems.

Original language	English
Pages (from-to)	242-261
Number of pages	20
Journal	Information and Computation
Volume	205
Issue number	2
DOIs	https://doi.org/10.1016/j.ic.2006.10.004
Publication status	Published - 2007

Access to Document

10.1016/j.ic.2006.10.004

Cite this

@article{52996fd4154c48e59962078a5c44d6d5,

title = "Algorithmic complexity bounds on future prediction errors",

abstract = "We bound the future loss when predicting any (computably) stochastic sequence online. Solomonoff finitely bounded the total deviation of his universal predictor M from the true distribution μ by the algorithmic complexity of μ. Here we assume that we are at a time t> 1 and have already observed x=x1···xt. We bound the future prediction performance onxt+1x t+2··· by a new variant of algorithmic complexity of μ given x, plus the complexity of the randomness deficiency of x. The new complexity is monotone in its condition in the sense that this complexity can only decrease if the condition is prolonged. We also briefly discuss potential generalizations to Bayesian model classes and to classification problems.",

keywords = "Future loss, Kolmogorov complexity, Monotone conditional complexity, Online sequential prediction, Posterior bounds, Randomness deficiency, Solomonoff prior, Total error",

author = "Alexey Chernov and Marcus Hutter and J{\"u}rgen Schmidhuber",

year = "2007",

doi = "10.1016/j.ic.2006.10.004",

language = "English",

volume = "205",

pages = "242--261",

journal = "Information and Computation",

issn = "0890-5401",

publisher = "Elsevier Inc.",

number = "2",

}

TY - JOUR

T1 - Algorithmic complexity bounds on future prediction errors

AU - Chernov, Alexey

AU - Hutter, Marcus

AU - Schmidhuber, Jürgen

PY - 2007

Y1 - 2007

N2 - We bound the future loss when predicting any (computably) stochastic sequence online. Solomonoff finitely bounded the total deviation of his universal predictor M from the true distribution μ by the algorithmic complexity of μ. Here we assume that we are at a time t> 1 and have already observed x=x1···xt. We bound the future prediction performance onxt+1x t+2··· by a new variant of algorithmic complexity of μ given x, plus the complexity of the randomness deficiency of x. The new complexity is monotone in its condition in the sense that this complexity can only decrease if the condition is prolonged. We also briefly discuss potential generalizations to Bayesian model classes and to classification problems.

AB - We bound the future loss when predicting any (computably) stochastic sequence online. Solomonoff finitely bounded the total deviation of his universal predictor M from the true distribution μ by the algorithmic complexity of μ. Here we assume that we are at a time t> 1 and have already observed x=x1···xt. We bound the future prediction performance onxt+1x t+2··· by a new variant of algorithmic complexity of μ given x, plus the complexity of the randomness deficiency of x. The new complexity is monotone in its condition in the sense that this complexity can only decrease if the condition is prolonged. We also briefly discuss potential generalizations to Bayesian model classes and to classification problems.

KW - Future loss

KW - Kolmogorov complexity

KW - Monotone conditional complexity

KW - Online sequential prediction

KW - Posterior bounds

KW - Randomness deficiency

KW - Solomonoff prior

KW - Total error

UR - http://www.scopus.com/inward/record.url?scp=84855201017&partnerID=8YFLogxK

U2 - 10.1016/j.ic.2006.10.004

DO - 10.1016/j.ic.2006.10.004

M3 - Article

SN - 0890-5401

VL - 205

SP - 242

EP - 261

JO - Information and Computation

JF - Information and Computation

IS - 2

ER -

Algorithmic complexity bounds on future prediction errors

Abstract

Access to Document

Other files and links

Fingerprint

Cite this