Open Problems 1 When Is Small Beautiful ?
Is the textbook result that Solomonoff’s universal posterior converges to the true posterior for all Martin-Löf random sequences true? Universal Induction Induction problems can be phrased as sequence prediction tasks. This is, for instance, obvious for time series prediction, but also includes classification tasks. Having observed data xt at times t < n, the task is to predict the t-th symbol xt from sequence x = x1...xt−1. The key concept to attack general induction problems is Occam’s razor and to a less extent Epicurus’ principle of multiple explanations. The former/latter may be interpreted as to keep the simplest/all theories consistent with the observations x1...xt−1 and to use these theories to predict xt. Solomonoff [4, 5] formalized and combined both principles in his universal prior M(x) which assigns high/low probability to simple/complex environments, hence implementing Occam and Epicurus. M(x) is defined as the probability that a universal Turing machine U outputs a string starting with x, when provided with fair coin flips on the input. Posterior Convergence Solomonoff’s [5] central result is that if the probability μ(xt|x1...xt−1) of observing xt at time t, given past observations x1...xt−1 is a computable function, then the universal posterior Mt := M(xt|x1...xt−1) converges (rapidly!) with μ-probability 1 (w.p.1) for t → ∞ to the true posterior μt := μ(xt|x1...xt−1), hence M represents a universal predictor in case of unknown μ. Convergence of Mt to μt w.p.1 tells us that Mt is close to μt for sufficiently large t for “almost all” sequences x1:∞ (we abbreviate x1:n := x1...xn). It says nothing about whether convergence is true for any particular sequence (of measure 0). Martin-Löf Randomness is the standard notion to capture convergence for individual sequences and is closely related to Solomonoff’s universal prior. Levin gave a characterization equivalent to Martin-Löf’s (M.L.) original definition [2]: A sequence x1:∞ is μ-random (in the sense of M.L.) iff there is a constant c such that M(x1:n) ≤ c · μ(x1:n) for all n. One can show that a μ-random sequence x1:∞ passes all thinkable effective randomness tests, e.g. the law of large numbers, the law of the iterated logarithm, etc. In particular, the set of all μ-random sequences has μ-measure 1. Open Problem An interesting open question is whether Mt converges to μt (in difference or ratio) individually for all Martin-Löf random sequences. Clearly, Solomonoff’s result shows that convergence may at most fail for a set of sequences with μ-measure zero. A convergence result for μ-random sequences is particularly interesting and natural in this context, since μ-randomness can be defined in terms of M itself (see above). 11 IDSIA, Galleria 2, CH-6928 Manno-Lugano, Switzerland marcus@idsia.ch http://www.idsia.ch/~marcus 12 A prize of 128 Euro for a solution of this problem is offered. Proof Attempts Attempts to convert the convergence results w.p.1 to effective μ-randomness tests fail, since Mt is not lower semi-computable. In [3, Th.5.2.2] and [6, Th.10] the following Theorem is stated: “Let μ be a positive recursive measure. If the length of y is fixed and the length of x grows to infinity, then M(y|x)/μ(y|x) → 1 with μ-probability one. The infinite sequences ω with prefixes x satisfying the displayed asymptotics are precisely [‘⇒’ and ‘⇐’] the μ-random sequences.” While convergence w.p.1 is correct if appropriately interpreted, the proof that convergence holds for μ-random sequences is incomplete: “M(x1:n) ≤ c ·μ(x1:n)∀n ⇒ limn→∞ M(x1:n)/μ(x1:n) exists” has been used, but not proven, and may indeed be wrong. Vovk [7] shows that for two finitely computable semi-measures μ and ρ, and x1:∞ being μand ρ-random that ρt/μt → 1. If M were recursive, then this would imply Mt/μt → 1 for every μ-random sequence x1:∞, since every sequence is M -random. Since M is not recursive Vovk’s theorem cannot be applied and it is not obvious how to generalize it. So the question of individual convergence remains open. Conclusions Contrary to what was believed before, the question of posterior convergence Mt/μt → 1 (also Mt → μt) for all μ-random sequences is still open. In [1] we introduce a new flexible notion of randomness which contains MartinLöf randomness as a special case. This notion is used to show that standard proof attempts of Mt/μt M.L. −→ 1 based on so called dominance only must fail, indicating that this problem may be a hard one.