Variants of Solomonoff induction - Revision history

https://machinelearning.subwiki.org/w/index.php?action=history&feed=atom&title=Variants_of_Solomonoff_induction Variants of Solomonoff induction - Revision history 2026-05-18T01:48:38Z Revision history for this page on the wiki MediaWiki 1.41.2 https://machinelearning.subwiki.org/w/index.php?title=Variants_of_Solomonoff_induction&diff=2789&oldid=prev IssaRice at 04:48, 3 February 2020 2020-02-03T04:48:07Z

<p></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="en"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 04:48, 3 February 2020</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l36">Line 36:</td> <td colspan="2" class="diff-lineno">Line 36:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>| Solomonoff section 3.1, eq. 1<ref name="solomonoff">R. J. Solomonoff. [https://www.sciencedirect.com/science/article/pii/S0019995864902232 "A formal theory of inductive inference. Part I"]. 1964.</ref> || <math>\lim_{\epsilon\to0} \lim_{n\to\infty} \sum_{k=1}^{r^n} \sum_{i=1}^\infty ((1-\epsilon)/2)^{N_{(S_{TC_{n,k}})_i}}</math> (this might be incorrect). Solomonoff is using the notation <math>C_{n,k}</math> to mean that he doesn't care about what happens as long as the desired string <math>T</math> starts the output. In more modern notation we would say <math>M(p)=T*</math> or <math>T \preceq M(p)</math> rather than <math>M(p) = TC_{n,k}</math> (although note that with Solomonoff's notation, we are also restricting the length of the output, so in the modern notation we would have to also require that <math>|M(p)| = |T| + n</math>). || Deterministic; universal Turing machine || || Solomonoff originally gave the conditional probability of seeing <math>a</math> given we've already seen <math>T</math>, which he writes <math>P(a,T,M_1)</math> but which in more common notation would be something like <math>P_{M_1}(Ta\mid T)</math>.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>| Solomonoff section 3.1, eq. 1<ref name="solomonoff">R. J. Solomonoff. [https://www.sciencedirect.com/science/article/pii/S0019995864902232 "A formal theory of inductive inference. Part I"]. 1964.</ref> || <math>\lim_{\epsilon\to0} \lim_{n\to\infty} \sum_{k=1}^{r^n} \sum_{i=1}^\infty ((1-\epsilon)/2)^{N_{(S_{TC_{n,k}})_i}}</math> (this might be incorrect). Solomonoff is using the notation <math>C_{n,k}</math> to mean that he doesn't care about what happens as long as the desired string <math>T</math> starts the output. In more modern notation we would say <math>M(p)=T*</math> or <math>T \preceq M(p)</math> rather than <math>M(p) = TC_{n,k}</math> (although note that with Solomonoff's notation, we are also restricting the length of the output, so in the modern notation we would have to also require that <math>|M(p)| = |T| + n</math>). || Deterministic; universal Turing machine || || Solomonoff originally gave the conditional probability of seeing <math>a</math> given we've already seen <math>T</math>, which he writes <math>P(a,T,M_1)</math> but which in more common notation would be something like <math>P_{M_1}(Ta\mid T)</math>.</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|-</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|-</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>| Solomonoff section 3.2, eq. 7<ref name="solomonoff"/> || <math>\sum_{i=1}^\infty 2^{-N(T,i)}</math> where <math>N(T,i)</math> is the <math>i</math>th minimal program for <math>T</math> || Deterministic; universal monotone machine || ||</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>| Solomonoff section 3.2, eq. 7<ref name="solomonoff"/> || <math>\sum_{i=1}^\infty 2^{-N(T,i)}</math> where <math>N(T,i)</math> is <ins style="font-weight: bold; text-decoration: none;">the number of bits in </ins>the <math>i</math>th minimal program for <math>T</math> || Deterministic; universal monotone machine || ||</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|-</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|-</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>| Solomonoff section 3.3, eq. 9 and 11<ref name="solomonoff"/> || <math>\lim_{R\to\infty} N_T/N_R</math>, where <math>N_R</math> is the number of programs of length <math>R</math> that cause the machine to halt eventually, and <math>N_T</math> are the subset of those programs that cause the machine to output something starting with <math>T</math> || Deterministic; either a universal Turing machine or a universal monotone machine || ||</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>| Solomonoff section 3.3, eq. 9 and 11<ref name="solomonoff"/> || <math>\lim_{R\to\infty} N_T/N_R</math>, where <math>N_R</math> is the number of programs of length <math>R</math> that cause the machine to halt eventually, and <math>N_T</math> are the subset of those programs that cause the machine to output something starting with <math>T</math> || Deterministic; either a universal Turing machine or a universal monotone machine || ||</div></td></tr> </table>

IssaRice https://machinelearning.subwiki.org/w/index.php?title=Variants_of_Solomonoff_induction&diff=2788&oldid=prev IssaRice at 04:09, 3 February 2020 2020-02-03T04:09:26Z

<p></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="en"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 04:09, 3 February 2020</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l18">Line 18:</td> <td colspan="2" class="diff-lineno">Line 18:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>| Scholarpedia continuous universal a priori probability<ref name="scholarpedia"/> || <math>M(x) = \sum_{p : U(p) = x*} 2^{-\ell(p)}</math> where the sum is over minimal programs || Deterministic; monotone Turing machine || Continuous ||</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>| Scholarpedia continuous universal a priori probability<ref name="scholarpedia"/> || <math>M(x) = \sum_{p : U(p) = x*} 2^{-\ell(p)}</math> where the sum is over minimal programs || Deterministic; monotone Turing machine || Continuous ||</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|-</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|-</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>| 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; ordinary Turing machine || Discrete<del style="font-weight: bold; text-decoration: none;">? </del>|| this seems similar to solomonoff's section 3.3</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>| 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; ordinary Turing machine || Discrete <ins style="font-weight: bold; text-decoration: none;">(I think because we are only considering halting inputs, the sample space is the set of all finite strings, which is a countable/discrete set) </ins>|| this seems similar to solomonoff's section 3.3<ins style="font-weight: bold; text-decoration: none;">. also I think this is different from the scholarpedia <math>m(x)</math> because here we allow anything that outputs starting with x to count toward the probability, rather than exactly x.</ins></div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|-</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|-</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>| 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, universal prefix machine (to get a probability distribution; see remark on p. 27) || discrete? || this formula does not define a probability distribution over strings <math>\sigma</math> because the sum of probabilities does not converge</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>| 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, universal prefix machine (to get a probability distribution; see remark on p. 27) || discrete? || this formula does not define a probability distribution over strings <math>\sigma</math> because the sum of probabilities does not converge</div></td></tr> </table>

IssaRice https://machinelearning.subwiki.org/w/index.php?title=Variants_of_Solomonoff_induction&diff=2787&oldid=prev IssaRice at 03:47, 3 February 2020 2020-02-03T03:47:25Z

<p></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="en"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 03:47, 3 February 2020</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l18">Line 18:</td> <td colspan="2" class="diff-lineno">Line 18:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>| Scholarpedia continuous universal a priori probability<ref name="scholarpedia"/> || <math>M(x) = \sum_{p : U(p) = x*} 2^{-\ell(p)}</math> where the sum is over minimal programs || Deterministic; monotone Turing machine || Continuous ||</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>| Scholarpedia continuous universal a priori probability<ref name="scholarpedia"/> || <math>M(x) = \sum_{p : U(p) = x*} 2^{-\ell(p)}</math> where the sum is over minimal programs || Deterministic; monotone Turing machine || Continuous ||</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|-</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|-</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>| 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; ordinary Turing machine || Discrete || this seems similar to solomonoff's section 3.3</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>| 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; ordinary Turing machine || Discrete<ins style="font-weight: bold; text-decoration: none;">? </ins>|| this seems similar to solomonoff's section 3.3</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|-</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|-</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>| 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, universal prefix machine (to get a probability distribution; see remark on p. 27) || discrete? || this formula does not define a probability distribution over strings <math>\sigma</math> because the sum of probabilities does not converge</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>| 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, universal prefix machine (to get a probability distribution; see remark on p. 27) || discrete? || this formula does not define a probability distribution over strings <math>\sigma</math> because the sum of probabilities does not converge</div></td></tr> </table>

IssaRice https://machinelearning.subwiki.org/w/index.php?title=Variants_of_Solomonoff_induction&diff=2786&oldid=prev IssaRice at 03:45, 3 February 2020 2020-02-03T03:45:17Z

<p></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="en"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 03:45, 3 February 2020</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l18">Line 18:</td> <td colspan="2" class="diff-lineno">Line 18:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>| Scholarpedia continuous universal a priori probability<ref name="scholarpedia"/> || <math>M(x) = \sum_{p : U(p) = x*} 2^{-\ell(p)}</math> where the sum is over minimal programs || Deterministic; monotone Turing machine || Continuous ||</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>| Scholarpedia continuous universal a priori probability<ref name="scholarpedia"/> || <math>M(x) = \sum_{p : U(p) = x*} 2^{-\ell(p)}</math> where the sum is over minimal programs || Deterministic; monotone Turing machine || Continuous ||</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|-</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|-</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>| 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> || <del style="font-weight: bold; text-decoration: none;">deterministic</del>; <del style="font-weight: bold; text-decoration: none;">universal </del>Turing machine <del style="font-weight: bold; text-decoration: none;">(no restrictions on prefix-free-ness) </del>|| <del style="font-weight: bold; text-decoration: none;">discrete? </del>|| this seems similar to solomonoff's section 3.3</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>| 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> || <ins style="font-weight: bold; text-decoration: none;">Deterministic</ins>; <ins style="font-weight: bold; text-decoration: none;">ordinary </ins>Turing machine || <ins style="font-weight: bold; text-decoration: none;">Discrete </ins>|| this seems similar to solomonoff's section 3.3</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|-</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|-</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>| 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, universal prefix machine (to get a probability distribution; see remark on p. 27) || discrete? || this formula does not define a probability distribution over strings <math>\sigma</math> because the sum of probabilities does not converge</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>| 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, universal prefix machine (to get a probability distribution; see remark on p. 27) || discrete? || this formula does not define a probability distribution over strings <math>\sigma</math> because the sum of probabilities does not converge</div></td></tr> </table>

IssaRice https://machinelearning.subwiki.org/w/index.php?title=Variants_of_Solomonoff_induction&diff=2785&oldid=prev IssaRice at 03:44, 3 February 2020 2020-02-03T03:44:02Z

<p></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="en"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 03:44, 3 February 2020</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l16">Line 16:</td> <td colspan="2" class="diff-lineno">Line 16:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>| 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 (i.e. self-delimiting) programs || Deterministic; prefix Turing machine || Discrete || In this notation, <math>U(p) = x</math> means that <math>U</math>, when run with program <math>p</math>, halts having just read all of <math>p</math> (and not beyond <math>p</math>). This means that "halting program" is the same thing as "self-delimiting program".</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>| 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 (i.e. self-delimiting) programs || Deterministic; prefix Turing machine || Discrete || In this notation, <math>U(p) = x</math> means that <math>U</math>, when run with program <math>p</math>, halts having just read all of <math>p</math> (and not beyond <math>p</math>). This means that "halting program" is the same thing as "self-delimiting program".</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|-</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|-</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>| Scholarpedia continuous universal a priori probability<ref name="scholarpedia"/> || <math>M(x) = \sum_{p : U(p) = x*} 2^{-\ell(p)}</math> where the sum is over minimal programs || <del style="font-weight: bold; text-decoration: none;">deterministic? Monotone </del>Turing machine || Continuous</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>| Scholarpedia continuous universal a priori probability<ref name="scholarpedia"/> || <math>M(x) = \sum_{p : U(p) = x*} 2^{-\ell(p)}</math> where the sum is over minimal programs || <ins style="font-weight: bold; text-decoration: none;">Deterministic; monotone </ins>Turing machine || Continuous <ins style="font-weight: bold; text-decoration: none;">||</ins></div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|-</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|-</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>| 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? || this seems similar to solomonoff's section 3.3</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>| 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? || this seems similar to solomonoff's section 3.3</div></td></tr> </table>

IssaRice https://machinelearning.subwiki.org/w/index.php?title=Variants_of_Solomonoff_induction&diff=2784&oldid=prev IssaRice at 03:43, 3 February 2020 2020-02-03T03:43:11Z

<p></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="en"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 03:43, 3 February 2020</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l14">Line 14:</td> <td colspan="2" class="diff-lineno">Line 14:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>| 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; prefix Turing machine || Discrete ||</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>| 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; prefix Turing machine || Discrete ||</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|-</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|-</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>| 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 || <del style="font-weight: bold; text-decoration: none;">deterministic? </del>prefix Turing machine || <del style="font-weight: bold; text-decoration: none;">discrete</del></div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>| 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 <ins style="font-weight: bold; text-decoration: none;">(i.e. self-delimiting) </ins>programs || <ins style="font-weight: bold; text-decoration: none;">Deterministic; </ins>prefix Turing machine || <ins style="font-weight: bold; text-decoration: none;">Discrete || In this notation, <math>U(p) = x</math> means that <math>U</math>, when run with program <math>p</math>, halts having just read all of <math>p</math> (and not beyond <math>p</math>). This means that "halting program" is the same thing as "self-delimiting program".</ins></div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|-</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|-</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>| Scholarpedia continuous universal a priori probability<ref name="scholarpedia"/> || <math>M(x) = \sum_{p : U(p) = x*} 2^{-\ell(p)}</math> where the sum is over minimal programs || deterministic? Monotone Turing machine || Continuous</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>| Scholarpedia continuous universal a priori probability<ref name="scholarpedia"/> || <math>M(x) = \sum_{p : U(p) = x*} 2^{-\ell(p)}</math> where the sum is over minimal programs || deterministic? Monotone Turing machine || Continuous</div></td></tr> </table>

IssaRice https://machinelearning.subwiki.org/w/index.php?title=Variants_of_Solomonoff_induction&diff=2783&oldid=prev IssaRice at 03:37, 3 February 2020 2020-02-03T03:37:24Z

<p></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="en"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 03:37, 3 February 2020</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l12">Line 12:</td> <td colspan="2" class="diff-lineno">Line 12:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>! Source !! Formula !! Determinism !! Discrete vs continuous !! Notes</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>! Source !! Formula !! Determinism !! Discrete vs continuous !! Notes</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|-</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|-</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>| 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; <del style="font-weight: bold; text-decoration: none;">page doesn't say type of machine, but uses self-delimiting programs and it's discrete, so </del>prefix Turing machine<del style="font-weight: bold; text-decoration: none;">? </del>|| Discrete <del style="font-weight: bold; text-decoration: none;">because of the <math>U(p) = y_0</math> rather than <math>U(p) = y_0*</math>?</del></div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>| 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; prefix Turing machine || Discrete <ins style="font-weight: bold; text-decoration: none;">||</ins></div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|-</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|-</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>| 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</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>| 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</div></td></tr> </table>

IssaRice https://machinelearning.subwiki.org/w/index.php?title=Variants_of_Solomonoff_induction&diff=2777&oldid=prev IssaRice at 01:08, 3 February 2020 2020-02-03T01:08:21Z

<p></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="en"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 01:08, 3 February 2020</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l6">Line 6:</td> <td colspan="2" class="diff-lineno">Line 6:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>NOTE: as of july 2019 i'm no longer sure that discrete vs continuous is actually a distinction. i think all(?) versions of solomonoff induction use continuous semimeasures. i'm not sure why the discrete one can't be used though. e.g. "For applications such as the prediction of growing sequences it is necessary to define a similar distribution on infinite binary sequences" [http://www.scholarpedia.org/article/Algorithmic_probability] Solomonoff also says similar things in at least one of his papers.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>NOTE: as of july 2019 i'm no longer sure that discrete vs continuous is actually a distinction. i think all(?) versions of solomonoff induction use continuous semimeasures. i'm not sure why the discrete one can't be used though. e.g. "For applications such as the prediction of growing sequences it is necessary to define a similar distribution on infinite binary sequences" [http://www.scholarpedia.org/article/Algorithmic_probability] Solomonoff also says similar things in at least one of his papers.</div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">February 2020 update: there is a discrete vs continuous distinction after all. With a discrete semimeasure, <math>\mu(xy\mid x) = 0</math> for all non-empty strings y, since we are considering ordinary Turing machines that halt. if a TM halts with output x, then it can't also halt with output xy. So the universal discrete semimeasure can't be used for sequence prediction, since all conditional probabilities are zero, hence useless. To do sequence prediction, we need to switch to monotone TMs and allow partial outputs.</ins></div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{| class="sortable wikitable"</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{| class="sortable wikitable"</div></td></tr> </table>

IssaRice https://machinelearning.subwiki.org/w/index.php?title=Variants_of_Solomonoff_induction&diff=2242&oldid=prev IssaRice at 19:53, 22 July 2019 2019-07-22T19:53:54Z

<p></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="en"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 19:53, 22 July 2019</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l4">Line 4:</td> <td colspan="2" class="diff-lineno">Line 4:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>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). I'm not sure how to tell whether a given formula is discrete or continuous. One difference seems to be that with discrete semimeasures, we only require that the sum is at most 1, whereas with continuous semimeasures we also require that <math>\mu(x) \geq \mu(x0) + \mu(x1)</math>? (see e.g. p. 5 of [https://arxiv.org/pdf/1508.05733.pdf] and p. 294 of Li and Vitanyi) Apparently one way to think of the discrete version is to think of the sample space as the natural numbers, i.e. one-letter strings from a countably infinite alphabet (see p. 265 of Li and Vitanyi).</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>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). I'm not sure how to tell whether a given formula is discrete or continuous. One difference seems to be that with discrete semimeasures, we only require that the sum is at most 1, whereas with continuous semimeasures we also require that <math>\mu(x) \geq \mu(x0) + \mu(x1)</math>? (see e.g. p. 5 of [https://arxiv.org/pdf/1508.05733.pdf] and p. 294 of Li and Vitanyi) Apparently one way to think of the discrete version is to think of the sample space as the natural numbers, i.e. one-letter strings from a countably infinite alphabet (see p. 265 of Li and Vitanyi).</div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">NOTE: as of july 2019 i'm no longer sure that discrete vs continuous is actually a distinction. i think all(?) versions of solomonoff induction use continuous semimeasures. i'm not sure why the discrete one can't be used though. e.g. "For applications such as the prediction of growing sequences it is necessary to define a similar distribution on infinite binary sequences" [http://www.scholarpedia.org/article/Algorithmic_probability] Solomonoff also says similar things in at least one of his papers.</ins></div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{| class="sortable wikitable"</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{| class="sortable wikitable"</div></td></tr> </table>

IssaRice https://machinelearning.subwiki.org/w/index.php?title=Variants_of_Solomonoff_induction&diff=1888&oldid=prev IssaRice at 04:14, 1 April 2019 2019-04-01T04:14:17Z

<p></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="en"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 04:14, 1 April 2019</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l25">Line 25:</td> <td colspan="2" class="diff-lineno">Line 25:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>| Sterkenburg (p. 29)<ref name="sterkenburg"/> || <math>Q_U(\sigma) = \sum_{\tau \in T_\sigma} 2^{-|\tau|}</math> where <math>T_\sigma</math> is the set of minimal descriptions of <math>\sigma</math> (i.e. set of programs that output something starting with <math>\sigma</math> such that if one removes one bit from the end of the program, it no longer outputs something starting with <math>\sigma</math>) || deterministic; universal monotone machine || continuous? ||</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>| Sterkenburg (p. 29)<ref name="sterkenburg"/> || <math>Q_U(\sigma) = \sum_{\tau \in T_\sigma} 2^{-|\tau|}</math> where <math>T_\sigma</math> is the set of minimal descriptions of <math>\sigma</math> (i.e. set of programs that output something starting with <math>\sigma</math> such that if one removes one bit from the end of the program, it no longer outputs something starting with <math>\sigma</math>) || deterministic; universal monotone machine || continuous? ||</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|-</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|-</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>| Sterkenburg (p. 31)<ref name="sterkenburg"/> || <math>P_{\mathrm{IV}}(\sigma) = \lim_{n\to\infty} \sum_i f_{i,n}P_i(\sigma)</math> || Stochastic; || || <del style="font-weight: bold; text-decoration: none;">i </del>think this is the same as <del style="font-weight: bold; text-decoration: none;">solomonoff</del>'s section 3.4, eq. 13</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>| Sterkenburg (p. 31)<ref name="sterkenburg"/> || <math>P_{\mathrm{IV}}(\sigma) = \lim_{n\to\infty} \sum_i f_{i,n}P_i(\sigma)</math> || Stochastic; || || <ins style="font-weight: bold; text-decoration: none;">I </ins>think this is the same as <ins style="font-weight: bold; text-decoration: none;">Solomonoff</ins>'s section 3.4, eq. 13<ins style="font-weight: bold; text-decoration: none;">, except that Solomonoff takes the limit of the <math>f_{i,n}</math> separately and then plugs it into the formula, rather than taking the limit of the sum.</ins></div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|-</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|-</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>| Sterkenburg (p. 33)<ref name="sterkenburg"/> || <math>\xi_w(\sigma) = \sum_i w(\mu_i)\mu_i(\sigma)</math> || Stochastic; weighting unspecified, except for the requirement that <math>w(\mu_i)>0</math> for all <math>i</math> and that <math>\sum_i w(\mu_i) \leq 1</math>; the model class is all semicomputable semimeasures ||</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>| Sterkenburg (p. 33)<ref name="sterkenburg"/> || <math>\xi_w(\sigma) = \sum_i w(\mu_i)\mu_i(\sigma)</math> || Stochastic; weighting unspecified, except for the requirement that <math>w(\mu_i)>0</math> for all <math>i</math> and that <math>\sum_i w(\mu_i) \leq 1</math>; the model class is all semicomputable semimeasures ||</div></td></tr> </table>

IssaRice