Universal prediction of selected bits

Tor Lattimore*, Marcus Hutter, Vaibhav Gavane

*Corresponding author for this work

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    5 Citations (Scopus)


    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.

    Original languageEnglish
    Title of host publicationAlgorithmic Learning Theory - 22nd International Conference, ALT 2011, Proceedings
    Number of pages15
    Publication statusPublished - 2011
    Event22nd International Conference on Algorithmic Learning Theory, ALT 2011 - Espoo, Finland
    Duration: 5 Oct 20117 Oct 2011

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    Volume6925 LNAI
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349


    Conference22nd International Conference on Algorithmic Learning Theory, ALT 2011


    Dive into the research topics of 'Universal prediction of selected bits'. Together they form a unique fingerprint.

    Cite this