Solomonoff induction

Solomonoff induction is an idealized method of sequence prediction.

Variants

There are many variants of Solomonoff induction that seem to all turn out essentially the same, but most resources on Solomonoff induction only talk about one or two of the variants, which makes it pretty confusing for someone trying to learn about it. It's also not obvious that all of these variants are essentially the same, so showing that would be nice.

Comparison dimensions:

• Determinism: are your programs probabilistic or deterministic? If deterministic, I think the programs require random coinflips as input.
• Kind of Turing machine used: ordinary, prefix, monotone
• Prediction length: finite vs infinite sequences
• Input (to UTM) length: finite vs infinite
• Solomonoff prior vs universal mixture; for universal mixture, you need to also specify the class over which you're mixing
• Discrete vs continuous? (is this the same as finite vs infinite?)

List of variants considered in various resources:

• Solomonoff's original paper:
  • (section 3.1)
  • (section 3.2)
  • (section 3.3)
  • (section 3.4) this uses a universal mixture, but i think solomonoff is using all computable measures (rather than enumerable semimeasures)
• Eliezer's Solomonoff induction dialogue:
• Li and Vitanyi:
  • $\mathbf{m}$ (defined in theorem 4.3.1 and example 4.3.3) seems like a discrete universal mixture. Input is finite. The "programs" (lower semicomputable discrete semimeasures $P_j$) are probabilistic.
  • universal a priori probability $Q_U$ (definition 4.3.5): deterministic prefix machine, random coinflips as input, finite input (program), finite output
  • $\mathbf{M}$
  • universal a priori probability ${\lambda }_{\psi }(x)$ (definition 4.5.6, p. 302)
  • ${\mathbf{M}}_{\mathrm{n}\mathrm{o}\mathrm{r}\mathrm{m}}$ (a version of $\mathbf{M}$ that is a measure)
• LessWrong Wiki:
• Scholarpedia article:
  • $m$: discrete, deterministic UTM (with random input), finite output, finite input (however, the "arises in three different ways" part gives other ways to view $m$)
  • $M$: continuous, infinite output, finite input (but maybe only because we consider minimal programs), deterministic UTM (with random coinflips)
• Shane Legg's introduction:
  • $P^U(\mu )$
• Sterkenburg's "The Foundations of Solomonoff Prediction":
  • $P_{\mathrm{I}}$ -- this seems similar to solomonoff's section 3.3
  • $P{\text{'}}_{\mathrm{I}\mathrm{I}}$
  • $P^{\prime }{\text{'}}_{\mathrm{I}\mathrm{I}}$
  • $P_{\mathrm{I}\mathrm{I}}$
  • algorithmic probability $Q_U(\sigma )$ (p. 29): monotone machine
  • $P_{\mathrm{I}\mathrm{V}}$ -- i think this is the same as solomonoff's section 3.4, eq. 13
  • ${\xi }_w(\sigma )$ (p. 33): universal mixture of semicomputable semimeasures
• Marcus Hutter's papers...
• Herrmann's "An Introduction to Solomonoff Induction With an Application to Scientific Confirmation Theory":
• Logical Induction Arbital page:
  • deterministic, regular (rather than prefix-free) Turing machines

Type of hypothesis

What is the type of a hypothesis? The type varies by formalization. For example:

• In classical statistical inference, a hypothesis is a constant that happens to be unknown, so e.g. it is a real number. This hypothesis then induces a probability distribution (called a "model").
• In Bayesian statistical inference, a hypothesis is an event (i.e. a subset of the sample space). There is a random variable representing the hypothesis (e.g. $\mathrm{\Theta }$), and you can get each individual hypothesis (e.g. $H_1\subseteq \mathrm{\Omega }$) by setting it to different values (e.g. $H_1=(\mathrm{\Theta }={\theta }_1)$).
• In Solomonoff induction a hypothesis is a program (?) whose type depends on the variant of Solomonoff induction being used.

Significance of random coin flips

(p. 4)

"""The prior AIXI is based on is the Solomonoff prior. It is defined as the output of a universal Turing machine (UTM) whose inputs are coin-flips.

In other words, feed a UTM a random program. Normally, you’d think of a UTM as only being able to simulate deterministic machines. Here, however, the initial inputs can instruct the UTM to use the rest of the infinite input tape as a source of randomness to simulate a stochastic Turing machine.

Combining this with the previous idea about viewing Bayesian learning as a way of allocating “trust” to “experts” which meets a bounded loss condition, we can see the Solomonoff prior as a kind of ideal machine learning algorithm which can learn to act like any algorithm you might come up with, no matter how clever."""

Measures vs semimeasures

Multiple ways to think about semimeasures:

• "defective" measures
• probability distribution over finite and infinite strings

Turing machines, prefix machines, monotone machines

Kraft's inequality

Applications

• there are some standard applications you can find standard references
• AIXI
• carl's analogy to psychophysical laws
• malign prior stuff
• comparison to logical induction