Algorithmic complexity bounds on future prediction errors

2006/12/20 by A. Chernov, Alexey Chernov, Marcus Hütter +3 · 1 citation
Computer Science · Mathematics · #Algorithms and Data Compression #Benford’s Law and Fraud Detection #Computability, Logic, AI Algorithms #cs.AI #cs.IT #cs.LG #math.IT

paper · pdf · doi:10.1016/j.ic.2006.10.004

published as Information and Computation, Vol.205,Nr.2 (2007) 242-261 · 21 pages

openalex publication_date 2006/12/20 · arxiv created 2007/01/19 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/02

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

Citations

• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS

Cited by

• A Philosophical Treatise of Universal Induction