Computer Science – Learning
Scientific paper
2004-07-23
Proc. 15th International Conf. on Algorithmic Learning Theory (ALT-2004), pages 234-248
Computer Science
Learning
16 pages
Scientific paper
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 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.
Hutter Marcus
Muchnik Andrej
No associations
LandOfFree
Universal Convergence of Semimeasures on Individual Random Sequences does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Universal Convergence of Semimeasures on Individual Random Sequences, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Universal Convergence of Semimeasures on Individual Random Sequences will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-246178