Universal Convergence of Semimeasures on Individual Random Sequences
Download (246.63 kB)
-
Altmetric Citations
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.author | Hutter, Marcus | |
---|---|---|
dc.contributor.author | Muchnik, Andrej | |
dc.date.accessioned | 2015-09-01T05:37:58Z | |
dc.date.available | 2015-09-01T05:37:58Z | |
dc.identifier.isbn | 978-3-540-23356-5 | |
dc.identifier.issn | 0302-9743 | |
dc.identifier.uri | http://hdl.handle.net/1885/15054 | |
dc.description.abstract | 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 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.sponsorship | This 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.publisher | Springer Verlag | |
dc.relation.ispartof | Algorithmic 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.subject | Sequence prediction | |
dc.subject | Algorithmic Information Theory | |
dc.subject | universal enumerable semimeasure | |
dc.subject | mixture distributions | |
dc.subject | posterior convergence | |
dc.title | Universal Convergence of Semimeasures on Individual Random Sequences | |
dc.type | Conference paper | |
local.identifier.citationvolume | 3244 | |
dc.date.issued | 2004 | |
local.publisher.url | http://link.springer.com/ | |
local.type.status | Accepted Version | |
local.contributor.affiliation | Hutter, M., Research School of Computer Science, The Australian National University | |
local.bibliographicCitation.startpage | 234 | |
local.bibliographicCitation.lastpage | 248 | |
local.identifier.doi | 10.1007/978-3-540-30215-5_19 | |
Collections | ANU Research Publications |
Download
File | Description | Size | Format | Image |
---|---|---|---|---|
Hutter and Muchnik Universal Convergence of Semimeasures 2004.pdf | 246.63 kB | Adobe PDF |
Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.
Updated: 17 November 2022/ Responsible Officer: University Librarian/ Page Contact: Library Systems & Web Coordinator