Skip navigation
Skip navigation

Universal prediction of selected bits

Lattimore, Tor; Hutter, Marcus; Gavane, Vaibhav

Description

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...[Show more]

dc.contributor.authorLattimore, Tor
dc.contributor.authorHutter, Marcus
dc.contributor.authorGavane, Vaibhav
dc.date.accessioned2015-08-20T00:31:52Z
dc.date.available2015-08-20T00:31:52Z
dc.identifier.isbn978-3-642-24411-7
dc.identifier.issn0302-9743
dc.identifier.urihttp://hdl.handle.net/1885/14809
dc.description.abstractMany 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.
dc.publisherSpringer Verlag
dc.relation.ispartofAlgorithmic Learning Theory: 22nd International Conference, ALT 2011, Espoo, Finland, October 5-7, 2011, Proceedings
dc.rights© Springer-Verlag Berlin Heidelberg 2011. http://www.sherpa.ac.uk/romeo/issn/0302-9743/..."Author's post-print on any open access repository after 12 months after publication" from SHERPA/RoMEO site (as at 20/08/15)
dc.subjectSequence prediction
dc.subjectSolomonoff induction
dc.subjectonline classification
dc.subjectdiscriminative learning
dc.subjectalgorithmic information theory
dc.titleUniversal prediction of selected bits
dc.typeConference paper
local.identifier.citationvolume6925
dc.date.issued2011-10
local.type.statusAccepted Version
local.contributor.affiliationLattimore, T., Research School of Computer Science, The Australian National University
local.contributor.affiliationHutter, M., Research School of Computer Science, The Australian National University
dc.relationhttp://purl.org/au-research/grants/arc/DP0988049
local.bibliographicCitation.startpage262
local.bibliographicCitation.lastpage276
local.identifier.doi10.1007/978-3-642-24412-4_22
CollectionsANU Research Publications

Download

File Description SizeFormat Image
Lattimore et al Universal Prediction of Selected Bits 2011.pdf131.38 kBAdobe PDFThumbnail


Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.

Updated:  19 May 2020/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator