Algorithmic Complexity Bounds on Future Prediction Errors

Details Algorithmic Complexity Bounds on Future Prediction Errors Algorithmic Complexity Bounds on Future Prediction Errors

2007-01-19

arxiv.org/abs/cs/0701120v1

Information and Computation, Vol.205,Nr.2 (2007) 242-261

Computer Science

Learning

21 pages

Scientific paper

10.1016/j.ic.2006.10.004

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_1...x_t$. We bound the future prediction performance on $x_{t+1}x_{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.

Affiliated with

Also associated with

No associations

Rating

Algorithmic Complexity Bounds on Future Prediction Errors does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Algorithmic Complexity Bounds on Future Prediction Errors, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Algorithmic Complexity Bounds on Future Prediction Errors will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-70541