On semimeasures predicting Martin-Löf random sequences |
| |
Authors: | Marcus Hutter Andrej Muchnik |
| |
Affiliation: | 1. IDSIA, Galleria 2, CH-6928 Manno-Lugano, Switzerland;2. RSISE/ANU/NICTA, Canberra, ACT, 0200, Australia;3. Institute of New Technologies, 10 Nizhnyaya Radischewskaya, Moscow 109004, Russia |
| |
Abstract: | Solomonoff’s central result on induction is that the prediction of a universal semimeasure M converges rapidly and with probability 1 to the true sequence generating predictor μ, if the latter is computable. Hence, M is eligible as a universal sequence predictor in the 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 to μ on 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. |
| |
Keywords: | Sequence prediction Algorithmic information theory Universal enumerable semimeasure Mixture distributions Predictive convergence Martin-Lö f randomness Supermartingales Quasimeasures |
本文献已被 ScienceDirect 等数据库收录! |
|