The speed prior: A new simplicity measure yielding near-optimal computable predictions

Research output: Chapter in Book/Report/Conference proceedingConference contribution

55 Scopus citations


Solomonoff's optimal but noncomputable 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 p ast x. Then we consider the case that the data actually stem from a nonoptimal, 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.
Original languageEnglish (US)
Title of host publicationLecture Notes in Artificial Intelligence (Subseries of Lecture Notes in Computer Science)
Number of pages13
ISBN (Print)354043836X
StatePublished - Jan 1 2002
Externally publishedYes

Bibliographical note

Generated from Scopus record by KAUST IRTS on 2022-09-14

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'The speed prior: A new simplicity measure yielding near-optimal computable predictions'. Together they form a unique fingerprint.

Cite this