6
$\begingroup$

My motivations for asking this question are philosophical in nature. I'm by no means a computer scientist though, and I feel as though this question should be answered by someone who is since it's one thing to read about a subject second hand and another to understand it first hand. I'm an A-level student of philosophy, physics and mathematics (UK qualification) if that helps you formulate an answer at all.

The question relates to the problem of induction in that, we have little reason to believe the universe is uniform and apply that expectation to science and inference. However, I've seen the claim made that this guy Solomonoff created a theory of induction that uses a Bayesian framework as well as something called 'Kolomogrov complexity' as an objective measure of 'complexity' in a model or hypothesis. For example, if we observe over and over again that all A's are B's, we might be tempted to formulate the hypothesis:

"All A's are B's",

This would be afforded the maximum credence from a bayesian framework since it predicts that A's are B's with a probability of 1 and we're attaching ourselves to the likelihood lover's principle. However, you could also formulate the hypothesis:

"All A's are B's until a time t where they are C."

And there are infinitely many of these hypothesis since the 'C' can represent literally anything. This has a bayesian multiplier equal to the previous hypothesis so technically have an equal credence if we don't prefer one of these in our priors. And the only way (it would seem) to decide between the two is to see if hypothesis 2 shows it's prediction at time t. So we would otherwise have to always wait until time t to see if hypothesis 1 is correct.

My question can be split up into three parts:

1) Is "Kolmogrov complexity" generally considered a genuine formulation of an objective definition for complexity/simplicity?

2) Would the former hypothesis, with such an understanding of complexity be considered more 'simple'?

3) How would this understanding of complexity be used practically when distinguishing between hypotheses? Or is it just obvious that the former type of hypothesis is more simple?

Although this is really a philosophical question, I suppose I would also like to know if anyone here has any ideas about why we should prefer more simple hypotheses. And perhaps, how would you increase your bayesian prior probability given some measure of complexity for a hypothesis?

Thank you in advance for any answers.

Improve this question
$\endgroup$
10
  • $\begingroup$ A paper of Legg seems to be a good introduction. A thesis of Vallinder could also be useful, and has several other pointers. $\endgroup$ – Yuval Filmus May 21 '18 at 11:22
  • $\begingroup$ What's the likelihood lover's principle? $\endgroup$ – D.W.♦ May 21 '18 at 17:59
  • $\begingroup$ Why do you think that "All A's are B's until a time t where they are C." has the same bayesian multiplier as "All A's are B's"? By "bayesian multiplier" are you referring to the prior on hypotheses? Why would you choose a prior where those two have equal probability? That seems unreasonable. Normally I'd expect a prior where the simpler hypothesis has higher probability than the more complicated one (Occam's razor). For instance, one could choose a prior that is a function of the Kolmogorov complexity of the prior. $\endgroup$ – D.W.♦ May 21 '18 at 18:03
  • $\begingroup$ What would it mean to "increase your bayesian prior probability"? I don't follow you. Can you edit the question to clarify? $\endgroup$ – D.W.♦ May 21 '18 at 18:05
  • $\begingroup$ @D.W. That is how you choose a prior. The bayesian multiplier is the P(E|H) term (E=evidence and H=your hypothesis). The likelihood lover's principle states that we prefer a hypothesis that makes the evidence more probable. I.e. we prefer a hypothesis who's P(E|H) term is higher. The problem is that the hypotheses "All A's are B's" and "All A's are B's until time t" have the same P(E|H) until time t so it seems like we can't say we prefer one over the other unless we have some objective standard of simplicity that says the former hypothesis is more simple than the latter. $\endgroup$ – Joe Lee-Doktor May 21 '18 at 19:37
3
$\begingroup$

Mathematics and computer science doesn't have anything to say about whether simpler hypotheses are more likely. That's a question about reality, not about math / computer science.

What computer science can provide is the notion of Kolmogorov complexity. Kolmogorov complexity is one reasonable notion of simplicity: bit-strings with lower Kolmogorov complexity are "simpler" in some sense.

Now we could start with a model of reality, which says that nature randomly picks a process for generating data; the process is obtained by picking a Turing machine at random, with smaller (simpler) Turing machines more likely to be chosen than complex ones; and then nature runs the Turing machine and the data you observe is the output of that Turing machine. That's a sketch of a possible model of reality; basically, it's an assumption about how nature works.

That assumption then implies (if we fill in some details) a particular prior on hypotheses. A hypothesis amounts to a Turing machine. There will be multiple Turing machines that are all consistent with the observations (that could have produced those observations), and Bayes theorem + the prior will let you infer the posterior distribution on which of those hypotheses are most likely.

This is a possible way to obtain a prior, and it seems reasonable to me. Computer science can't tell you whether that model (that assumption) is a good model of reality. But it can help you work out the consequences of making that assumption.

Finally, you seem to be asking why simpler explanations are more often correct. Basically, why is Occam's razor useful? I don't know if there is any completely convincing answer to that.

One possible answer is the empirical answer: it seems to work well in practice. In other words, we often find in nature that very simple processes/models suffice to explain a wide range of natural observations. See, e.g., the unreasonable effectiveness of mathematics.

There's lots more that one can say about Occam's razor. See, e.g., https://en.wikipedia.org/wiki/Occam%27s_razor#Justifications and https://philosophy.stackexchange.com/questions/tagged/occams-razor?sort=votes. I think that gets beyond the scope of this site.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.