Monotone conditional complexity bounds on future prediction errors

Alexey Chernov; Marcus Hutter

doi:10.1007/11564089_32

Monotone conditional complexity bounds on future prediction errors

University of Brighton

Research output: Chapter in Book/Conference proceeding with ISSN or ISBN › Conference contribution with ISSN or ISBN › peer-review

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 m by the algorithmic complexity of m. Here we assume we are at a time t>1 and already observed x=x 1...xt. We bound the future prediction performance on xt+1xt+2... by a new variant of algorithmic complexity of m 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
Title of host publication	Proceedings of the 16th International Conference Algorithmic Learning Theory 2005
Place of Publication	Berlin Heidelberg
Publisher	Springer
Pages	414-428
Number of pages	15
Volume	3734
DOIs	https://doi.org/10.1007/11564089_32
Publication status	Published - 31 Dec 2005
Event	Proceedings of the 16th International Conference Algorithmic Learning Theory 2005 - Singapore, October 8-11, 2005 Duration: 31 Dec 2005 → …

Publication series

Name	Lecture Notes in Computer Science

Conference

Conference	Proceedings of the 16th International Conference Algorithmic Learning Theory 2005
Period	31/12/05 → …

Access to Document

10.1007/11564089_32Licence: Unspecified

PostBnd_v2-alt.pdfAccepted author manuscript, 323 KBLicence: Unspecified

Cite this

@inproceedings{250a8ef1da1144f08c6ac46ae730bcfa,

title = "Monotone conditional 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 m by the algorithmic complexity of m. Here we assume we are at a time t>1 and already observed x=x 1...xt. We bound the future prediction performance on xt+1xt+2... by a new variant of algorithmic complexity of m 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.",

author = "Alexey Chernov and Marcus Hutter",

year = "2005",

month = dec,

day = "31",

doi = "10.1007/11564089_32",

language = "English",

volume = "3734",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "414--428",

booktitle = "Proceedings of the 16th International Conference Algorithmic Learning Theory 2005",

note = "Proceedings of the 16th International Conference Algorithmic Learning Theory 2005 ; Conference date: 31-12-2005",

}

Chernov, A & Hutter, M 2005, Monotone conditional complexity bounds on future prediction errors. in Proceedings of the 16th International Conference Algorithmic Learning Theory 2005. vol. 3734, Lecture Notes in Computer Science, Springer, Berlin Heidelberg, pp. 414-428, Proceedings of the 16th International Conference Algorithmic Learning Theory 2005, 31/12/05. https://doi.org/10.1007/11564089_32

Monotone conditional complexity bounds on future prediction errors. / Chernov, Alexey; Hutter, Marcus.
Proceedings of the 16th International Conference Algorithmic Learning Theory 2005. Vol. 3734 Berlin Heidelberg: Springer, 2005. p. 414-428 (Lecture Notes in Computer Science).

Research output: Chapter in Book/Conference proceeding with ISSN or ISBN › Conference contribution with ISSN or ISBN › peer-review

TY - GEN

T1 - Monotone conditional complexity bounds on future prediction errors

AU - Chernov, Alexey

AU - Hutter, Marcus

PY - 2005/12/31

Y1 - 2005/12/31

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 m by the algorithmic complexity of m. Here we assume we are at a time t>1 and already observed x=x 1...xt. We bound the future prediction performance on xt+1xt+2... by a new variant of algorithmic complexity of m 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 m by the algorithmic complexity of m. Here we assume we are at a time t>1 and already observed x=x 1...xt. We bound the future prediction performance on xt+1xt+2... by a new variant of algorithmic complexity of m 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.

U2 - 10.1007/11564089_32

DO - 10.1007/11564089_32

M3 - Conference contribution with ISSN or ISBN

VL - 3734

T3 - Lecture Notes in Computer Science

SP - 414

EP - 428

BT - Proceedings of the 16th International Conference Algorithmic Learning Theory 2005

PB - Springer

CY - Berlin Heidelberg

T2 - Proceedings of the 16th International Conference Algorithmic Learning Theory 2005

Y2 - 31 December 2005

ER -

Monotone conditional complexity bounds on future prediction errors

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this