Yielding Near-Optimal Computable Predictions

**Jürgen Schmidhuber
juergen@idsia.ch - http://www.idsia.ch/~ juergen
**

IDSIA, Galleria 2, 6928 Manno (Lugano), Switzerland

In J. Kivinen and R. H. Sloan, editors, *Proceedings of the 15th
Annual Conference on Computational Learning Theory (COLT 2002), Sydney, Australia,*
Lecture Notes in Artificial Intelligence, pages 216-228. Springer, 2002.

Solomonoff's optimal but *non*computable method for inductive
inference assumes that observation sequences are drawn from an
recursive prior distribution . Instead of using the unknown
he predicts using the celebrated universal enumerable prior
which for all exceeds any recursive , save for a
constant factor independent of . The simplicity measure
naturally implements ``Occam's razor'' and is closely related to the
Kolmogorov complexity of . However, assigns high probability to
certain data 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 by the
novel Speed Prior , under which the cumulative a priori probability
of all data whose computation through an optimal algorithm requires more
than resources is . We show that the Speed Prior allows for
deriving a *computable* strategy for optimal prediction of future
, given past . 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
-based inductive inference. We conclude with several nontraditional
predictions concerning the future of our universe.

*This paper is based on section 6 of TR IDSIA-20-00, Version 2.0:
http://www.idsia.ch/~ juergen/toesv2/
http://arXiv.org/abs/quant-ph/0011122 (public physics archive)
*

- Introduction
- Speed Prior
- Speed Prior-Based Inductive Inference

- Machine Dependence / Suboptimal Computation of the Data:
Expected Loss Bounds

- Physics
- Conclusion
- Bibliography
- About this document ...

Back to Speed Prior page