Epistemic status: Not peer reviewed, high chance of typos and small chance of errors. Written entirely by me, checked by Fable.
In this post I prove the existence of an anytime computable Bayesian mixture of all computable measures called , and briefly argue that this is a reasonable alternative to Solomonoff induction's universal distribution for general sequence prediction.
I believe that Tom Sterkenburg told me that this is possible, but I could not find it written down anywhere (though I may have missed it!). Indeed, has been conjectured not to be limit=anytime computable by Hutter and Muchnik: https://arxiv.org/abs/cs/0407057. I worked out the anytime algorithm with @Aram Ebtekar and @Marcus Hutter, though any mistakes are mine.
Anytime computable (or limit computable): A function f is anytime computable if where is finitely computable.
Lower semicomputable (or l.s.c.): A function f is l.s.c. if where is non-decreasing in t.
Computable (or estimable): A function f is computable if where .
A sequence predictor is a function from the binary strings to [0,1] which we interpret as the probability of seeing the prefix. Assuming "superadditivity" , specifies a (unique) distribution on possibly infinite sequences. The function is also called a semimeasure. Measures satisfy superadditivity with equality, which is called additivity.
Solomonoff induction predicts with the universal distribution , which is lower semicomputable but (only) has anytime computable posteriors.
is a universal l.s.c. semimeasure. This means that is an l.s.c. semimeasure such that for any l.s.c. semimeasure , there is a fixed such that for all . In log loss, does not predict much worse than any l.s.c. , which in particular means that it (nearly) beats all computable predictors over the long run. However, it does NOT beat all anytime computable predictors, and indeed no anytime computable predictor is can do so by a simple diagonalization.
There are other anytime computable predictors that dominate all computable predictors. One example is , defined by where is the (countable) set of computable normalized probability measures and . We will (implicitly) describe weights such that is anytime computable, which is achieved by constructing a computable (but in a sense ineffective) enumeration of with repetition.
The trick is that we can convert each Turing machine into a computable measure, in such a way that if already computes a computable measure, that measure is unchanged. The conversion, however, is only anytime computable. Naming the resulting measure , we obtain .
Then we simply take , where or any other anytime computable sequence of positive reals summing to exactly 1. Then (our)
is an anytime computable Bayesian mixture of the computable measures.
Now to construct , we simply treat as if is an estimate of to precision , equivalently an open interval of length containing . We can assume w.l.o.g. that these intervals are strictly decreasing, and for later convenience we also take their closures without effecting the resulting measure. We do not know how long needs to run, or (if it does not compute a computable measure) whether it will ever halt. I believe that the natural idea of dovetailing on all does not produce a computable measure. However, we can add constraints in stages, as follows.
Let run for up to steps, producing if the computation has not finished. Enumerating as we will at stage run:
If at any point the result is , the computation ends.
We can computably check as we go that all intervals for each are strictly decreasing, of the correct length, and do not violate superadditivity. For simplicity, we also require that so that our measures are normalized. If one of these constraints ever fails for , the computation ends (and indeed will not continue past that point for any ).
This entire process is finitely computable. It results in a constraint set of closed intervals for each which is satisfiable by a measure, and indeed we can easily map a constraint set to a fixed measure . For example, we can pick the "leftmost" point of the polyhedron, allocating the maximum possible measure to strings in lexicographic order.[1] This choice takes the empty constraint set to the atom corresponding to for all . Finite computability on each is obvious, though I have not written the constraint-selection algorithm down explicitly.
Take .
Clearly is anytime computable (uniformly in from with .
I claim that is also a computable measure, though NOT uniformly in . In fact, this is fairly easy to see. If computes a computable measure, that measure is clearly . Otherwise fails to compute a computable measure, either because there is a conflict in the constraints or because some has . In either case only finitely many constraints are added, which can be hardcoded into a single machine that computes on each .
QED.
Implications. and both have (only) anytime computable posteriors. Because the posteriors of a predictor are needed for learning + prediction, the lower semicomputability of (a priori) may not be a significant advantage over . Both choices beat all computable predictors, but only is a proper probability measure. As a basis for Solomonoff induction or AIXI, would simplify some of the measure theory by doing away with finite sequences. Arguably, this also undermines the uniqueness of as a universal/canonical choice of prior. Indeed, even carries the additional distinction of converging to along all -M.L. random sequences (which fails for at least some ).[2] However, it follows from a the selected bits negative result that beats in log loss along some infinite sequences ( does not dominate ).
- ^
We took the closure of interval constraints above because Fable reminds me that there is no leftmost point in an open set.
- ^
For the version of that converges, Hutter and Muchnik use weights and renormalize. Because they do not assume an enumeration without repetition, modifying our anytime algorithm to take should work; checking carefully would be a nice exercise for someone (otherwise) interested in reading the paper.
Discuss