Does the Solomonoff Prior Double-Count Simplicity?
Question: I've noticed what seems like a feature of the Solomonoff prior that I haven't seen discussed in any intros I've read. The prior is usually described as favoring simple programs through its exponential weighting term, but aren't simpler programs already exponentially favored in it just through multiplicity alone, before we even apply that weighting?
Consider Solomonoff induction applied to forecasting e.g. a video feed of a whirlpool, represented as a bit string x. The prior probability for any such string is given by: P(x)=∑p:U(p)=x12|p| where p ranges over programs for a prefix-free Universal Turing Machine.
Observation: If we have a simple one kilobit program p1 that outputs prediction x1, we can construct nearly 21000 different two kilobit programs that also output x1 by appending arbitrary "dead code" that never executes.
For example: DEADCODE="[arbitrary 1 kilobit string]" [original 1 kilobit program p1] EOF Where programs aren't allowed to have anything follow EOF, to ensure we satisfy the prefix free requirement.
If we compare p1 against another two kilobit program p2 outputting a different prediction x2, the prediction x1 from p1 would get 21000−|G| more contributions in the sum, where |G| is the very small number of bits we need to delimit the DEADCODE garbage string. So we're automatically giving x1 ca. 21000 higher probability – even before applying the length penalty 12|p|. p1 has less 'burdensome details', so it has more functionally equivalent implementations. Its predictions seem to be exponentially favored in proportion to its length |p1| already due to this multiplicity alone.
So, if we chose a different prior than the Solomonoff prior which just assigned uniform probability to all programs below some very large cutoff, say 1090 bytes: P(x)=∑p:U(p)=x,|p|≤1090121090
and then followed the exponential decay of the Solomonoff prior for programs longer than 1090 bytes, wouldn't that prior act barely differently than the Solomonoff prior in practice? It’s still exponentially preferring predictions with shorter minimum message length.[1]
Context for the question: Multiplicity of implementation is how simpler hypotheses are favored in Singular Learning Theory despite the prior over neural network weights usually being uniform. I'm trying to understand how those SLT statements about neural networks generalising relate to algorithmic information theory statements about Turing machines, and Jaynes-style pictures of probability theory.
Sure. But what’s interesting to me here is the implication that, if you restrict yourself to programs below some maximum length, weighing them uniformly apparently works perfectly fine and barely differs from Solomonoff induction at all.
This resolves a remaining confusion I had about the connection between old school information theory and SLT. It apparently shows that a uniform prior over parameters (programs) of some fixed size parameter space is basically fine, actually, in that it fits together with what algorithmic information theory says about inductive inference.