Occam's Razor

The Vapnik Chernovenkis Dimension also offers a way of filling in the detail of the the concept of "simple" appropriate to Occam's Razor. I've read about it in the context of statistical learning theory, specifically "probably approximately correct learning".

Having successfully tuned the parameters of your model to fit the data, how likely is it to fit new data, that is, how well does it generalise. The VC dimension comes with formulae that tell you. I've not been able to follow the field, but I suspect that VC dimension leads to worst case estimates whose usefulness is harmed by their pessimism.

Great post!

"Your accusation of witchcraft wouldn't let you shorten the rest of the message; you would still have to describe, in full detail, the data which her witchery caused."

My model of witches, if I had one, would produce a given simple sequence like 01010101 with greater probability than a given random sequence like 00011011. Wouldn't yours? I might agree if you said "in nearly full detail".

Steven, that means you have to transmit the accusation of witchcraft, followed by a computer program, followed by the coded data. Why not just transmit the computer program followed by the coded data? I don't expect my own environment to be random noise, but that has nothing to do with witchcraft...

Alan, I agree that VC dimension is an important conceptually different way of thinking about "complexity". One of its primary selling points is that, for example, it doesn't attach infinite complexity to a model class that contains one real-valued parameter, if that model class isn't very flexible (i.e., it says only "the data points are greater than R"). But VC complexity doesn't plug into standard probability theory as easily as Solomonoff induction.

In Solomonoff induction it is important to use a two-tape Turing machine where one tape is for the program and one is for the input and work space. The program tape is an infinite random string, but the program length is defined to be the number of bits that the Turing machine actually reads during its execution. This way the set of possible programs becomes a prefix free set. It follows that the prior probabilities will add up to one when you weight by 2^(-l) where l is program length. (I believe this was realized by Leonid Levin. In Solomonoff's original scheme the prior probabilities did not add to one.) This also allows the beautiful interpretation that the program tape is assigned by independent coin flips for each bit, and the 2^-l weighting arises naturally rather than as an artificial assumption. I believe this is discussed in the information theory book by Cover and Thomas.

Eliezer,

"I don't expect my own environment to be random noise, but that has nothing to do with witchcraft..."

I think I misinterpreted the math and now see what you're getting at. Would it be an accurate translation to human language to say, "a sequence like 10101010 may favor witchcraft over the hypothesis that nothing weird is going on (i.e. the coinflips are random), but it will never favor witchcraft over the simpler hypothesis that something weird is going on that isn't witchcraft"?

I find it awkward to think of "witchcraft" as just a content-free word; what "witchcraft" means to me is something like the possibility that reality includes human-mind-like things with personalities and with preferences that they achieve through unknown nonstandard causal means. If you coded that up, it would probably no longer be content-free; it would allow shortening the rest of the program generating the sequences in some cases and require lengthening it in some other cases. In all realistic cases the resulting program would still be longer than necessary.

Good comments, all!

Steven, yes. Stephen, also yes.

Eli, you said:

An enormous bolt of electricity comes out of the sky and hits something, and the Norse tribesfolk say, "Maybe a really powerful agent was angry and threw a lightning bolt." The human brain is the most complex artifact in the known universe. If anger seems simple, it's because we don't see all the neural circuitry that's implementing the emotion. (Imagine trying to explain why Saturday Night Live is funny, to an alien species with no sense of humor. But don't feel superior; you yourself have no sense of fnord.) The complexity of anger, and indeed the complexity of intelligence, was glossed over by the humans who hypothesized Thor the thunder-agent.

I think it's worth noting that Norse tribesfolk already knew about human beings, so whatever model of the universe they made had to include angry agents in it somewhere.

What you are talking about in terms of Solmonoff induction is usually called algorithmic information theory and the shortest-program-to-produce-a-bit-string is usually called Kolmogorov-Chaitin information. I am sure you know this. Which begs the question, why didn't you mention this? I agree, it is the neatest way to think about Occam's razor. I am not sure why some are raising PAC theory and VC-dimension. I don't quite see how they illuminate Occam. Minimalist inductive learning is hardly the simplest "explanation" in the Occam sense, and is actually closer to Shannon entropy in spirit, in being more of a raw measure. Gregory Chaitin's 'Meta Math: The Search for Omega', which I did a review summary of is a pretty neat look at this stuff.

Venkat: I think there is a very good reason to mention PAC learning. Namely, Kolmogorov complexity is uncomputable, so Solomonoff induction is not possible even in principle. Thus one must use approximate methods instead such as PAC learning.

Occam’s razor is not conclusive and it’s not science. It is not unscientific but I would say that it fits into the category of philosophy. In science you do not get two theories, take the facts you know, and then conclude based on the simplest theory. If you’re doing this, you need to do better experiments to determine the facts. Occam’s razor can be a useful heuristic to suggest what experiments should be done. Just like mathematical elegance, Occam’s razor suggests that something is on the right track but it is not decisive. To look back at the facts and then interpret it through Occam’s razor is just an exercise in hindsight bias.

Your analogy with Norse tribesfolk reminds me of the NRA slogan, “Guns don’t kill people, people kill people”. There are many different levels of causation. The gun can be said to be the secondary cause of why someone died. The person pulling the trigger would be the primary cause. The secondary cause of thunder is nature but the first cause that brought things into existence and created the system is God. Nature cannot be its own cause.

The rest of what you wrote sounds like you're pulling numbers out of your arse. The last sentence should be read in your best Norse tribesfolk accent.

In science you do not get two theories

You're right - there are an infinite number of theories consistent with any set of observations. Any set. All observed facts are technically consistent with the prediction that gravity will reverse in one hour, but nobody believes that because of... Occam's Razor!

The rest of what you wrote sounds like you're pulling numbers out of your arse.

Cure of Ars, I should prefer it if you no longer commented on my posts. There may be a place on Overcoming Bias for Catholics; but none for those who despise math they don't understand.

MIT Press has just published Peter Grünwald's The Minimum Description Length Principle. His Preface, Chapter 1, and Chapter 17 are available at that link. Chapter 17 is a comparison of different conceptions of induction.

I don't know this area well enough to judge Peter's wok, but it is certainly informative. Many of his points echo Eliezer's. If you find this topic interesting, Peter's book is definitely worth checking out.

"Different inductive formalisms are penalized by a worst-case constant factor relative to each other"

You mean a constant term; it's additive, not multiplicative.

Occam's razor actually suggest that entities are not to be multiplied without necessity.

Unfortunately, most people happily bastardize Occam's Razor, abusing it to suggest the simpler explanation is usually the better one.

First off, define simple. Simple how? Can you objectively define simplicity? (It's not easily done.) Second, explanations must fit the facts. Third, this is a heuristic-based argument, not a logical proof of something. (This same argument was used against Boltzman and his idea of the atom, but Boltzman was right.) Fourth, what does "usually" mean anyway? Define that objectively. Black swans events are seemingly impossible, yet they happen much more regularly than people imagine (because they are based on power laws/fractal statistics, not the Bell Curve reality we often think in terms of where the past gives us some sense of what to expect).

Consequently, I don't consider an offhand mention of Occam's razor as a compelling argument. I would stop shaking your head and reconsider what it is you think you know.

There is: It's enormously easier (as it turns out) to write a computer program that simulates Maxwell's Equations, compared to a computer program that simulates an intelligent emotional mind like Thor.

Coming back to this post, I finally noticed that "emotional" is a necessary word in the quoted sentence. If we leave it out, the sentence might just become false! That is, if you believe there's some sort of simple mathematical "key" to intelligence (my impression is that you do believe that), then you also ought to believe that the Solomonoff prior makes an intelligent god quite probable apriori. Maybe even more probable than the currently most elegant known formulations of physical laws, which include a whole zoo of elementary particles etc. Of course, if we take into account the evidence we've seen so far, it looks like our universe is based on physics rather than a "god".

Occam's Razor is "entities must not be multiplied beyond necessity" (entia non sunt multiplicanda praeter necessitatem)

NOT "The simplest explanation that fits the facts."

Now thats just purely definition. I think both are true. I think there are problems with both. The problem with Occams razor, is that yes its true, however, it doesn't cover all the bases. There is a deeper underlying principle that makes Occams razor true, which is the one you described in the article. However summing up your article as "The simplest explanation that fits the facts" is also misleading as in, while it does seem to cover all the bases, it only does so if you use a very specific definition of simple which really doesnt fit with everyday language.

Example: Stonehenge, let me suggest two theories, 1. it was built by ancient humans, 2. it fell together through purely random geological process. Both theories fit with the facts, we know that both are physically possible (yes 2. is vastly less probable, ill get to that in a second). Occams razor suggest 2. as the answer, and "The simplest explanation" appears to be 2. also. Both seem to be failing. The real underlying principle as to why Occams razor is true, is statistics, not simplicity. Now dont get me wrong, I understand why "The simplest explanation that fit the facts" actually points to 1., but then you have to go through this long process of what you actually mean by simplest, which basically just ends up being a long explanation of how "simple" actually means "probable".

Anyways, I'm just arguing over semantics, I do in fact agree with everything you said. I just wish there was no Occams razor, it should just be "The theory which is the most statistically probable, is usually the right one." This is what people actually mean to say when they say "The simplest explanation that fits the facts."

NOT "The simplest explanation that fits the facts."

Witchcraft may fit our observations in the sense of qualitatively permitting them; but this is because witchcraft permits everything

I think replacing witchcraft with godhood is also a common mistake

What I don't understand is so much insistence that Occam's Razor applies only to explanations you address to God. Or else how do you avoid the observation that the simplicity of an explanation is a function of whom you are explaining to ? In the post, you actually touch on the issue, only to observe that there are difficulties interpreting Occam's Razor in the frame of explaining things to humans (in their own natural language), so let's transpose to a situation where humans are completely removed from the picture. Curiously enough, where the same issue occurs in the context of machine languages it is quickly "solved". Makes one wonder what Occam - who had no access to Turing machines - himself had in might.

Also, if you deal in practice with shortening code length of actual programs, at some point you have exploited all the low lying fruit; further progress can come after a moment of contemplation made you observe that distinct paths of control through the code have "something in common" that you may try to enhance to the point where you can factor it out. This "enhancing" follows from the quest for minimal "complexity", but it drives you to do locally, on the code, just the contrary of what you did during the "low-lying fruit" phase, you "complexify" rather than "simplify" two distinct areas of the code to make them resemble each other (and the target result emerges during the process, fun). What I mean to say, I guess, is that even the frame proposed by Chaitin-Kolmogorov complexity gives only fake reasons to neglect bias (from shared background or the equivalent).

"each program is further weighted by its fit to all data observed so far. This gives you a weighted mixture of experts that can predict future bits."

I don't see it explained anywhere what algorithm is used to weight the experts for this measure. Does it matter? And how are the "fit" probabilities and "complexity" probabilities combined? Multiply and normalize?

What I find fascinating is that Solomonoff Induction (and the related concepts from Kolmogorov complexity) very elegantly solves the classical philosophical problem of induction, as well as resolving a lot of other problems:

1. What is the correct "prior" in Bayesian inference, and isn't the choice of prior all subjective?
2. What does Occam's razor really mean, and what is a "simple" theory?
3. Why do physicists insist that their theories are "simple" when only they can understand them?

Despite this, it is almost unheard of in the general philosophical (analytic philosophy) community. I've read literally dozens of top-grade philosophers discussing these topics, with the implication that these are still big unsolved problems, and in complete ignorance that there is a very rich mathematical theory in this area. And the theory's not exactly new either... dates back to the 1960s.

Anyone got an explanation for the disconnect?

If you let a program store one more binary bit of information, it will be able to cut down a space of possibilities by half, and hence assign twice as much probability to all the points in the remaining space. This suggests that one bit of program complexity should cost at least a "factor of two gain" in the fit. If you try to design a computer program that explicitly stores an outcome like "HTTHHT", the six bits that you lose in complexity must destroy all plausibility gained by a 64-fold improvement in fit. Otherwise, you will sooner or later decide that all fair coins are fixed.

I found this paragraph confusing. How about

If you let a program store one more binary bit of information, it will be able to cut down a space of possibilities by half, and hence assign twice as much probability to all the points in the remaining space. This suggests that one bit of program complexity should always buy at least a "factor of two gain" in the fit. If you try to design a computer program that explicitly stores an outcome like "HTTHHT", the six bits that you pay in complexity must get you at least a 64-fold improvement in fit. Otherwise, you will sooner or later decide that all fair coins are fixed.

Does that mean the same thing?

Upcoming formal philosophy conference on the foundations of Occam's razor here. Abstracts included.

I don't think it's quite necessary for people to even be consciously aware of Occam's Razor. The right predictions will eventually win out because there will exist an economic profit somewhere which will be exploited. If you can think of an area which is overrun with market inefficiencies due to something related to this post, please let me know and I will be sure to grab whatever I can of the economic profits while they last.

Hello,

I need some help understanding the article after Unless your program is being smart, and compressing the data, it should do no good just to move one bit from the data into the program description.

How is the connection being made from complexity and fit to data and program description?

Thanks in advance! :)

I found a reference to a very nice overview for the mathematical motivations of Occam's Razor on wikipedia.

It's Chapter 28: Model Comparison and Occam's Razor; from (page 355 of) Information Theory, Inference, and Learning Algorithms (legally free to read pdf) by David J. C. MacKay.

The Solomonoff Induction stuff went over my head, but this overview's talk of trade-offs between communicating increasing numbers of model parameters vs having to communicate less residuals (ie. offsets from real data); was very informative.

My own way of thinking of Occam's Razor is through model selection. Suppose you have two competing statements $H_1$ (the which did it) and $H_2$ (it was chance or possibly something other than a which caused it ($H_2=\neg H_1$)) and some observations $D$ (the sequence came up 0101010101). Then the preferred statement is whichever is more probable calculated as

this is simply Bayes rule where

and the model is parametrized by some parameters $\theta$.

Now all this is just the mathematical way of writing that a hypothesis that has more parameters (or more specifically more possible values that it predicts), will not be as strong a statement that predicts a smaller state of outcomes.

In the witch example this would be:

• $H_1=$ There exist an advanced intelligent being (at least not much less than human intelligence) that can do things beyond what has ever been reproduced in a scientific way that for some reason chooses to live on our street and act mostly as a human that will choose to influence my sequence coin tosses to end up in some seemingly looking pattern
• $H_2=$ The coin toss is ruled by chance and might end up in the set of possible outcomes that seem to form a pattern ($\{0101010101,1111100000,1100110011,\dots \}$)
• $D=$The coin toss ended up as $0101010101$
• The way I stated the hypotheses $p\left(D|H_1\right)=p\left(D|H_2\right)\cdot \text{Fraction of outcomes that look like a pattern}$

Now what remains is to estimate the priors and the the fraction of outcomes that look like a pattern. We can skip $p\left(D\right)$ as we are interested in $p\left(H_1|D\right):p\left(H_2|D\right)$.

Now comparing the amount of conditionals in the hypotheses and how surprised I am by them I would roughly estimate a ratio of the priors as something like $2^{100}$ in favor to chance, as the witch hypothesis goes against many of my formed beliefs of the world collected over many years, it includes weird choices of living for this hypothetical alien entity, it picks out me as a possible agent of many in the neighborhood, it singles out an arbitrary action of mine and an arbitrary set of outcomes.

For the sake of completeness. The fraction of outcomes that look like a pattern is kind of hard to estimate exactly. However, my way of thinking about it is how soon in the sequence would I postulate the specific sequence that it ended up in. After 0101, I think that the sequence 0101010101 is the most obvious pattern to continue it in. So roughly this is six bits of evidence.

In conclusion, I would say that the probability of the witch hypothesis is lacking around 94 bits of evidence for me to believe it as much as the chance hypothesis.

The downside of this approach to the Solomonoff induction and the minimum message length is that it is clunkier to use and it might be easy to forget to include conditionals or complexity in the priors the same way they can be lost in the English language. The upside is that as a model it is simpler, less ad hoc and builds directly on the product rule in probability and that probabilities sum to one and should thus be preferred by Occam's Razor ;).