Skip navigation
Skip navigation

Algorithmic complexity bounds on future prediction errors

Chernov, Alexey; Hutter, Marcus; Schmidhuber, Jürgen


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 on x(t+1)x(t+2) ⋯ by a new variant of algorithmic complexity of μ given x, plus the complexity of the randomness deficiency of x. The new...[Show more]

CollectionsANU Research Publications
Date published: 2007-02
Type: Journal article
Source: Information and Computation
DOI: 10.1016/j.ic.2006.10.004


File Description SizeFormat Image
Chernov et al Algorithmic Complexity Bounds 2007.pdf239.52 kBAdobe PDFThumbnail

Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.

Updated:  19 May 2020/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator