The Speed Prior: A New Simplicity Measure Yielding Near-Optimal Computable Predictions

Abstract

Solomonoff’s optimal but non computable method for inductive inference assumes that observation sequences x are drawn from an recursive prior distribution μ ( x ). Instead of using the unknown μ ( x ) he predicts using the celebrated universal enumerable prior M ( x ) which for all x exceeds any recursive μ ( x ), save for a constant factor independent of x . The simplicity measure M ( x ) naturally implements “Occam’s razor” and is closely related to the Kolmogorov complexity of x . However, M assigns high probability to certain data x that are extremely hard to compute. This does not match our intuitive notion of simplicity. Here we suggest a more plausible measure derived from the fastest way of computing data. In absence of contrarian evidence, we assume that the physical world is generated by a computational process, and that any possibly infinite sequence of observations is therefore computable in the limit (this assumption is more radical and stronger than Solomonoff’s). Then we replace M by the novel Speed Prior S , under which the cumulative a priori probability of all data whose computation through an optimal algorithm requires more than O ( n ) resources is 1/ n . We show that the Speed Prior allows for deriving a computable strategy for optimal prediction of future y , given past x . Then we consider the case that the data actually stem from a non optimal, unknown computational process, and use Hutter’s recent results to derive excellent expected loss bounds for S -based inductive inference. We conclude with several nontraditional predictions concerning the future of our universe.