Universal prediction of selected bits

DOI10.1007/978-3-642-24412-4_22MaRDI QIDQ3093957zbMATH OpenOpenAlexWikidataFDO

Authors Tor Lattimore, Marcus Hutter, Vaibhav Gavane

Publication date 19 October 2011

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1107.5531

zbMATH Keywords

algorithmic information theorydiscriminative learningonline classificationsequence predictionSolomonoff induction

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Inference from stochastic processes and prediction (62M20) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Learning and adaptive systems in artificial intelligence (68T05)

Abstract: Many learning tasks can be viewed as sequence prediction problems. For example, online classification can be converted to sequence prediction with the sequence being pairs of input/target data and where the goal is to correctly predict the target data given input data and previous input/target pairs. Solomonoff induction is known to solve the general sequence prediction problem, but only if the entire sequence is sampled from a computable distribution. In the case of classification and discriminative learning though, only the targets need be structured (given the inputs). We show that the normalised version of Solomonoff induction can still be used in this case, and more generally that it can detect any recursive sub-pattern (regularity) within an otherwise completely unstructured sequence. It is also shown that the unnormalised version can fail to predict very simple recursive sub-patterns.

Recommendations

• Theory and Applications of Models of Computation
• New error bounds for Solomonoff prediction
• Is There an Elegant Universal Theory of Prediction?
• Convergence and Error Bounds for Universal Prediction of Nonbinary Sequences
• On universal prediction and Bayesian confirmation

Cited in

(9)

• Does snooping help?
• On universal prediction and Bayesian confirmation
• On the computability of Solomonoff induction and knowledge-seeking
• Is There an Elegant Universal Theory of Prediction?
• Universal prediction
• Two Kinds of Probabilistic Induction
• On asymptotic and finite-time optimality of Bayesian predictors
• Theory and Applications of Models of Computation
• New error bounds for Solomonoff prediction

This page was built for publication: Universal prediction of selected bits

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3093957)