Variants of Solomonoff induction: Difference between revisions

From Machinelearning
No edit summary
No edit summary
Line 17: Line 17:
| Sterkenburg (p. 22)<ref name="sterkenburg">Tom Florian Sterkenburg. "The Foundations of Solomonoff Prediction". February 2013.</ref> || <math>P_{\mathrm{I}}(\sigma) = \lim_{n\to\infty} \frac{|T_{\sigma,n}|}{|T_n|}</math> where <math>\sigma</math> is a finite string, <math>T_n</math> is the set of all halting (valid) inputs of length <math>n</math> to the reference machine <math>U</math>, <math>T_{\sigma,n}</math> is the set of all halting (valid) inputs of length <math>n</math> that output something starting with <math>\sigma</math> || deterministic || universal Turing machine (no restrictions on prefix-free-ness) || discrete?
| Sterkenburg (p. 22)<ref name="sterkenburg">Tom Florian Sterkenburg. "The Foundations of Solomonoff Prediction". February 2013.</ref> || <math>P_{\mathrm{I}}(\sigma) = \lim_{n\to\infty} \frac{|T_{\sigma,n}|}{|T_n|}</math> where <math>\sigma</math> is a finite string, <math>T_n</math> is the set of all halting (valid) inputs of length <math>n</math> to the reference machine <math>U</math>, <math>T_{\sigma,n}</math> is the set of all halting (valid) inputs of length <math>n</math> that output something starting with <math>\sigma</math> || deterministic || universal Turing machine (no restrictions on prefix-free-ness) || discrete?
|-
|-
| Sterkenburg (p. 24)<ref name="sterkenburg"/> || <math>P'_{\mathrm{II}}(\sigma) = 2^{-|\tau_\mathrm{min}|}</math> where <math>\tau_\mathrm{min}</math> is the shortest program <math>\tau</math> such that <math>U(\tau) = \sigma</math> (i.e. the shortest program that causes the reference machine to output <math>\sigma</math> and halt) || deterministic || universal Turing machine ||
| Sterkenburg (p. 24)<ref name="sterkenburg"/> || <math>P'_{\mathrm{II}}(\sigma) = 2^{-|\tau_\mathrm{min}|}</math> where <math>\tau_\mathrm{min}</math> is the shortest program <math>\tau</math> such that <math>U(\tau) = \sigma</math> (i.e. the shortest program that causes the reference machine to output <math>\sigma</math> and halt) || deterministic || universal Turing machine || discrete?
|}
|}



Revision as of 03:08, 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?
Sterkenburg (p. 24)[3] where is the shortest program such that (i.e. the shortest program that causes the reference machine to output and halt) deterministic universal Turing machine 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. 3.0 3.1 Tom Florian Sterkenburg. "The Foundations of Solomonoff Prediction". February 2013.