Monotone Conditional Complexity Bounds on Future Prediction Errors

Simple item page
dc.creatorChernov, Alexey
dc.creatorHutter, Marcus
dc.date2005-07-18
dc.date.accessioned2026-07-07T08:17:48Z
dc.date.available2026-07-07T08:17:48Z
dc.descriptionWe 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...x_t. We bound the future prediction performance on x_{t+1}x_{t+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.
dc.description16 LaTeX pages
dc.identifierhttps://arxiv.org/abs/cs/0507041
dc.identifierhttp://arxiv.org/abs/cs/0507041
dc.identifierProc. 16th International Conf. on Algorithmic Learning Theory (ALT 2005) 414-428
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/134222
dc.subjectMachine Learning
dc.subjectArtificial Intelligence
dc.subjectInformation Theory
dc.subjectI.2.6; E.4; G.3; F.1.3
dc.titleMonotone Conditional Complexity Bounds on Future Prediction Errors
dc.typetext

Files

Collections

arXiv