Variants of Solomonoff induction: Difference between revisions
No edit summary |
No edit summary |
||
| Line 11: | Line 11: | ||
| 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 the output string <math>y_0</math> is finite | ||
|- | |- | ||
| 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"]. 2007.</ref> || <math>m(x) = \sum_{p:U(p)=x} 2^{-\ell(p)}</math> || 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> || deterministic? || prefix Turing machine || discrete | ||
|- | |- | ||
| Scholarpedia continuous universal a priori probability<ref name="scholarpedia"/> || <math>M(x) = \sum_{p : U(p) = x*} 2^{-\ell(p)}</math> || deterministic? || Monotone Turing machine || Continuous | | Scholarpedia continuous universal a priori probability<ref name="scholarpedia"/> || <math>M(x) = \sum_{p : U(p) = x*} 2^{-\ell(p)}</math> || deterministic? || Monotone Turing machine || Continuous | ||
Revision as of 02:47, 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 the output string is finite |
| Scholarpedia discrete universal a priori probability[2] | deterministic? | prefix Turing machine | discrete | |
| Scholarpedia continuous universal a priori probability[2] | deterministic? | Monotone Turing machine | Continuous |
References
- ↑ https://wiki.lesswrong.com/wiki/Solomonoff_induction
- ↑ 2.0 2.1 Marcus Hutter; Shane Legg; Paul M.B. Vitanyi. "Algorithmic probability". Scholarpedia. 2007.