Variants of Solomonoff induction: Difference between revisions

From Machinelearning
No edit summary
No edit summary
Line 9: Line 9:
! Source !! Formula !! Determinism !! Type of machine used !! Discrete vs continuous
! Source !! Formula !! Determinism !! Type of machine used !! Discrete vs continuous
|-
|-
| LessWrong Wiki<ref>https://wiki.lesswrong.com/wiki/Solomonoff_induction</ref> || <math>m(y_0) = \sum_{p \in \mathcal P : U(p) = y_0} 2^{-\ell(p)}</math> where <math>\mathcal P</math> is the set of self-delimiting programs || Deterministic || Page doesn't say, but uses self-delimiting programs and it's discrete, so prefix Turing machine? || Discrete because the output string <math>y_0</math> is finite
| LessWrong Wiki<ref>https://wiki.lesswrong.com/wiki/Solomonoff_induction</ref> || <math>m(y_0) = \sum_{p \in \mathcal P : U(p) = y_0} 2^{-\ell(p)}</math> where <math>\mathcal P</math> is the set of self-delimiting programs || Deterministic || Page doesn't say, but uses self-delimiting programs and it's discrete, so prefix Turing machine? || Discrete because of the <math>U(p) = y_0</math> rather than <math>U(p) = y_0*</math>
|-
|-
| Scholarpedia discrete universal a priori probability<ref name="scholarpedia">Marcus Hutter; Shane Legg; Paul M.B. Vitanyi. [http://www.scholarpedia.org/article/Algorithmic_probability "Algorithmic probability"]. ''Scholarpedia''. 2007.</ref> || <math>m(x) = \sum_{p:U(p)=x} 2^{-\ell(p)}</math> where the sum is over halting programs || deterministic? || prefix Turing machine || discrete
| Scholarpedia discrete universal a priori probability<ref name="scholarpedia">Marcus Hutter; Shane Legg; Paul M.B. Vitanyi. [http://www.scholarpedia.org/article/Algorithmic_probability "Algorithmic probability"]. ''Scholarpedia''. 2007.</ref> || <math>m(x) = \sum_{p:U(p)=x} 2^{-\ell(p)}</math> where the sum is over halting programs || deterministic? || prefix Turing machine || discrete

Revision as of 03:02, 31 March 2019

This page lists some variants of Solomonoff induction.

For determinism, I think "deterministic" is the same as "Solomonoff prior" and "stochastic" is the same as "universal mixture".

For discrete vs continuous, I think this just means whether the prior we define is over finite strings or over infinite sequences (where we want to know the probability of an infinite sequence starting with a given finite string).

Source Formula Determinism Type of machine used Discrete vs continuous
LessWrong Wiki[1] where is the set of self-delimiting programs Deterministic Page doesn't say, but uses self-delimiting programs and it's discrete, so prefix Turing machine? Discrete because of the rather than
Scholarpedia discrete universal a priori probability[2] where the sum is over halting programs deterministic? prefix Turing machine discrete
Scholarpedia continuous universal a priori probability[2] where the sum is over minimal programs deterministic? Monotone Turing machine Continuous
Sterkenburg (p. 22)[3] where is a finite string, is the set of all halting (valid) inputs of length to the reference machine , is the set of all halting (valid) inputs of length that output something starting with deterministic universal Turing machine (no restrictions on prefix-free-ness) discrete?

References

  1. https://wiki.lesswrong.com/wiki/Solomonoff_induction
  2. 2.0 2.1 Marcus Hutter; Shane Legg; Paul M.B. Vitanyi. "Algorithmic probability". Scholarpedia. 2007.
  3. Tom Florian Sterkenburg. "The Foundations of Solomonoff Prediction". February 2013.