Universal Convergence of Semimeasures on Individual Random Sequences

Simple item page
dc.creatorHutter, Marcus
dc.creatorMuchnik, Andrej
dc.date2004-07-23
dc.date.accessioned2026-07-07T08:17:42Z
dc.date.available2026-07-07T08:17:42Z
dc.descriptionSolomonoff'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 mu, if the latter is computable. Hence, M is eligible as a universal sequence predictor in case of unknown mu. Despite some nearby results and proofs in the literature, the stronger result of convergence for all (Martin-Loef) 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 mu on all random sequences. The Hellinger distance measuring closeness of two distributions plays a central role.
dc.description16 pages
dc.identifierhttps://arxiv.org/abs/cs/0407057
dc.identifierhttp://arxiv.org/abs/cs/0407057
dc.identifierProc. 15th International Conf. on Algorithmic Learning Theory (ALT-2004), pages 234-248
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/134181
dc.subjectMachine Learning
dc.subjectArtificial Intelligence
dc.subjectComputational Complexity
dc.subjectInformation Theory
dc.subjectProbability
dc.subjectI.2.6; E.4; G.3; F.1.3
dc.titleUniversal Convergence of Semimeasures on Individual Random Sequences
dc.typetext

Files

Collections

arXiv