Skip navigation
Skip navigation

Universal Convergence of Semimeasures on Individual Random Sequences

Hutter, Marcus; Muchnik, Andrej

Description

Solomonoff’s central result on induction is that the posterior of a universal semimeasure M converges rapidly and with probability 1 to the true sequence generating posterior μ, if the latter is computable. Hence, M is eligible as a universal sequence predictor in case of unknown μ. Despite some nearby results and proofs in the literature, the stronger result of convergence for all (Martin-Löf) random sequences remained open. Such a convergence result would be particularly interesting and...[Show more]

dc.contributor.authorHutter, Marcus
dc.contributor.authorMuchnik, Andrej
dc.date.accessioned2015-09-01T05:37:58Z
dc.date.available2015-09-01T05:37:58Z
dc.identifier.isbn978-3-540-23356-5
dc.identifier.issn0302-9743
dc.identifier.urihttp://hdl.handle.net/1885/15054
dc.description.abstractSolomonoff’s central result on induction is that the posterior of a universal semimeasure M converges rapidly and with probability 1 to the true sequence generating posterior μ, if the latter is computable. Hence, M is eligible as a universal sequence predictor in case of unknown μ. Despite some nearby results and proofs in the literature, the stronger result of convergence for all (Martin-Löf) random sequences remained open. Such a convergence result would be particularly interesting and natural, since randomness can be defined in terms of M itself. We show that there are universal semimeasures M which do not converge for all random sequences, i.e. we give a partial negative answer to the open problem. We also provide a positive answer for some non-universal semimeasures. We define the incomputable measure D as a mixture over all computable measures and the enumerable semimeasure W as a mixture over all enumerable nearly-measures. We show that W converges to D and D to μ on all random sequences. The Hellinger distance measuring closeness of two distributions plays a central role.
dc.description.sponsorshipThis work was partially supported by the Swiss National Science Foundation (SNF grant 2100-67712.02) and the Russian Foundation for Basic Research (RFBR grants N04-01-00427 and N02-01-22001).
dc.publisherSpringer Verlag
dc.relation.ispartofAlgorithmic Learning Theory: 15th International Conference, ALT 2004, Padova, Italy, October 2-5, 2004. Proceedings (Lecture Notes in Computer Science / Lecture Notes in Artificial Intelligence)
dc.rights© Springer-Verlag Berlin Heidelberg 2004. 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 1/09/15).
dc.subjectSequence prediction
dc.subjectAlgorithmic Information Theory
dc.subjectuniversal enumerable semimeasure
dc.subjectmixture distributions
dc.subjectposterior convergence
dc.titleUniversal Convergence of Semimeasures on Individual Random Sequences
dc.typeConference paper
local.identifier.citationvolume3244
dc.date.issued2004
local.publisher.urlhttp://link.springer.com/
local.type.statusAccepted Version
local.contributor.affiliationHutter, M., Research School of Computer Science, The Australian National University
local.bibliographicCitation.startpage234
local.bibliographicCitation.lastpage248
local.identifier.doi10.1007/978-3-540-30215-5_19
CollectionsANU Research Publications

Download

File Description SizeFormat Image
Hutter and Muchnik Universal Convergence of Semimeasures 2004.pdf246.63 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