Skip navigation
Skip navigation

Algorithmic complexity bounds on future prediction errors

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

Description

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
URI: http://hdl.handle.net/1885/15014
Source: Information and Computation
DOI: 10.1016/j.ic.2006.10.004

Download

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:  12 November 2018/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator