Does Solomonoff's theory of inductive inference justify Occam's razor?

Question

I was told to make a separate question on this to keep focus given the implications of this question. As a reminder, Occam's razor states that you should prefer the hypothesis that has fewer assumptions when comparing hypotheses that explain the same evidence.

In Solomonoff's theory of inductive inference, there is a concept of a universal prior that assigns a positive probability to any computable theory. Larger prior credences are assigned to theories that require a shorter algorithmic description.

The intuition behind this is that each non contradictory theory must be assigned a non zero positive prior (since you cannot epistemically rule any theory out). And the only way to assign a probability distribution over a potential infinite number of hypotheses where the sum adds up to 1 (as required by probability theory) is by assigning shorter hypotheses a higher prior.

Does this theory then give us reasons that are more than just aesthetic to adopt Occam's razor?

Note: A common complaint against this is the idea of language dependence. For algorithms, depending on the language, if a hypothesis can be represented by a program, a particular program may be shorter in one language than another. However, in Solomonoff's theory, the invariance theorem states that while different languages may produce different lengths for the same data, the relative complexity between different data strings remains consistent across different universal Turing machines (a model of a computing machine), making the choice of language less important.

Answer 1

The Wikipedia article explicitly states that it is a formalization that combines Occam's Razor and a couple other theories, so in a circular sense, yes it does. However, this is because it was developed as an attempt at finding a principled justification of Occam's Razor from more primitive principles.

Overall, I think he succeeded -- it's quite clever and coherent argument for why simplicity of a theory should be used as a balancing factor.

However, it is still required to accept the idea that simpler is more a priori probable -- we could suggest that Einstein's aphorism is more a priori plausible:

A theory should be as simple as possible, but no simpler.

Given that, we could argue we should expect neither overly simple nor overly complex a priori, so we have some kind of Gamma-like prior distribution over hypotheses. Maybe we'd then need a hyper-prior on this to integrate over the likely location of the "bump", and so the posterior is over the hyperprior's location param vs the actual "prior" we use -- somewhat similar to objective Bayes (but this isn't objective Bayes strictly).

From an infornation-theoretic perspective a nonmonotonic, unimodal prior would make sense (I think) in that extremely simple theories (per Solomonoff's metric) may not be informative enough to allow the metalanguage they are expressed in. The existence of a metalanguage to express hypotheses seems like a background requirement, and the fact that observers exist to ask the question presumably can be factored into our prior.

For example, if I have an extremely simple theory expressible by one bit of information, it would be very likely a priori to be true per Solomonoff, but one bit is not enough information to allow us to propose the hypothesis (i.e., our logical apparatus itself requires more than extremely simple theories can support).

This might be circular, but I think it depends on where you draw the line on what we are including in our prior.

---

One thing that bothers me a bit is that it seems that by using Bayesian theory, we are treating complexity and accuracy as epistemically fungible. For any given posterior probability, I can continuously shift between a highly compact but highly inaccurate model and a highly complex, highly accurate model. However, we usually think of Occam's razor as a secondary criterion to accuracy/correctness.

Case in point: The standard model is very complex and is needed to explain minute differences from particle accelerators. Yet the vast majority of our available evidence doesn't involve the phemonea that the standard model describes -- we could simply stick with 19th century physics and accept that some of the evidence is poorly explained/improbable.

The jury is out if the extra bump in the data likelihood for the Standard Model would overrule the big hit in prior probability due to its complexity.

This is why I think Solomonoff (or Wiki the article at least) make's this huge caveat:

All computable theories which perfectly describe previous observations are used to calculate the probability of the next observation, with more weight put on the shorter computable theories.

(emphasis mine).

The condition above would result in us defaulting to something like Occam's razor (although there may be several theories of equal complexity in which case we're back to square one).

Unfortunately, the set of such theories is empty :(

Answer 2

And the only way to assign a probability distribution over a potential infinite number of hypotheses where the sum adds up to 1 (as required by probability theory) is by assigning shorter hypotheses a higher prior.

No this is very obviously not the only way. You can take any such probability distribution and manually switch any two hypothesises having different probability and length, and you get a new distribution that does not assign all shorter hypotheses a higher prior than all longer ones.

Though some Occam's razor likeness remains, but it's not strict and depends on too much semantics anyway in the general.

Answer 3

In some sense, the answer is yes, because the universal prior can be seen as a consequence of feeding random inputs to a prefix-free Turing machine, instead of something you just assume as an hypothesis. Looking at Solomonoff's seminal paper from 1964 "A Formal Theory of Inductive Inference", this is what he does: in the initial hypotheses, there is nothing about the lengths of the programs, it appears later as a consequence.