Occam's razor justification, missing page number

[Gabriel Leuenberger]

I searched for the state-of-the-art justification of Occam's razor. So in Hutter's 2024 book, I read the section on justifying Occam's razor, which says that more details can be found in Hutter's paper titled 'A Complete Theory of Everything (will be subjective)'.

This paper then says:

"It is a deep theorem in algorithmic information theory [LV08] that there are also not
significantly more than 2^{L−l} programs q equivalent to q_min. The proof idea is as
follows: One can show that if there are many long equivalent programs, then there
must also be a short one. In our case the shortest one is q_min, which upper bounds
the number of long programs. Together this shows that |Q_L| ≈ 2^{L−l}."

The mentioned reference [LV08] is Li and Vitanyi's Introduction to Kolmogorov Complexity, however, no page number is provided in Hutter's reference. I can attest to the correctness of the result that he refers to, as I can prove it thanks to its resemblance to Levin's coding theorem. I also know where the coding theorem is in the book, but where exactly has the similar theorem been written up?

Best regards

[Marcus Hutter]

Hi Gabriel,

Thanks for your interest in my work 🙂
It 's Example 4.3.5 and Exercise 4.3.6 in [LV08].

Cheers,

Marcus

More information: http://www.hutter1.net/ait.htm
---
You received this message because you are subscribed to the Google Groups "Algorithmic Information Theory" group.
To unsubscribe from this group and stop receiving emails from it, send an email to ait0+uns...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/ait0/fe3e19c7-d628-42e5-90c7-2562cdbf8343n%40googlegroups.com.

[Ming Li]

Dear Gabriel,

In our book first edition, page 296, section 5.5.2, we gave a proof of
an Occam's razor theorem. The earlier version of Occam's razor
theorem was in the context of Valiant's pac-learning paradigm, first
proved by Blumer, Ehrenfeucht, Hausssler, Warmuth, later improved
by us (Li-Tromp-Vitanyi). I think this is what Marcus was referring to.

Hope this answers your question.

Best regards,
Ming Li

> More information: http://www.hutter1.net/ait.htm
> ---
> You received this message because you are subscribed to the Google
> Groups "Algorithmic Information Theory" group.
> To unsubscribe from this group and stop receiving emails from it, send
> an email to ait0+uns...@googlegroups.com.
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/ait0/fe3e19c7-d628-42e5-90c7-2562cdbf8343n%40googlegroups.com

> <https://groups.google.com/d/msgid/ait0/fe3e19c7-d628-42e5-90c7-2562cdbf8343n%40googlegroups.com?utm_medium=email&utm_source=footer>.

[Gabriel Leuenberger]

Thank you both very much for providing the information.

Ming Li, I have one more question. Although I did not know about this improved Occam's razor theorem, I have met a serious scholar who wrote a paper titled 'PAC Learning and Occam’s Razor: Probably Approximately Incorrect' which apparently debunked Blumer's argument for Occam's razor. Here is part of the abstract:

"I argue that the standard interpretation of the result in the literature is misguided and that a better reading does not, in fact, support Occam’s Razor at all. To this end, I state and prove a very similar theorem that, if interpreted the same way, would justify the contradictory Anti-Occam’s Razor—the principle that we should favor more complex hypotheses."

And his paper also mentioned your paper:

"Although there are subtly different ways to try to prove Occam’s Razor in the PAC learning framework (e.g., Wolf 1997;
Ming, Tromp, and Vitányi 2003), they all follow a pattern similar to the PAC LEARNING AND OCCAM’S RAZOR 689
original proof given by Blumer et al. For the purposes of this article, the proof I include follows closely the presentation of the original Blumer et al.
paper (1987)."

So my question to you is whether your improvement to the Occam's razor theorem has made it immune to his criticism.

Best regards,

Gabriel Leuenberger

[Ard Louis]

Dear Gabriel,

 

My student Zaman (cc’d above) and I are finishing a rebuttal to the paper in Philosophy of Science by Hermann. We agree with Hermann’s conclusion that Blumer et al. don’t provide an epistemic justification for Occam’s razor; however, this is not a novel claim. Our disagreement with Hermann lies in the arguments he presents to support that conclusion, including the anti-Occam construction.

.

 

Should have something out soon.

 

Best wishes,

Ard

 

To view this discussion on the web visit https://groups.google.com/d/msgid/ait0/fb0ee544-1f13-4b11-a6d9-5bd167c0ed2fn%40googlegroups.com.

[Ming Li]

Dear Gabriel,

I am not sure what the argument is. But if it favors a few "complex"
hypotheses, then the Kolmogorov complexity
of these hypotheses must be low (since there are not too many of them --
this is the essential idea of the BEHW proof
in the first place). Hence everything converges back to the same idea of
BEHW proof.

I guess we should switch to private channel not to overwhelm people's
mail boxes.

Cheers,
Ming

> <https://groups.google.com/d/msgid/ait0/fe3e19c7-d628-42e5-90c7-2562cdbf8343n%40googlegroups.com?utm_medium=email&utm_source=footer>>.

>
>
>
> More information: http://www.hutter1.net/ait.htm
> ---
> You received this message because you are subscribed to the Google
> Groups "Algorithmic Information Theory" group.
> To unsubscribe from this group and stop receiving emails from it, send
> an email to ait0+uns...@googlegroups.com.
> To view this discussion on the web visit

> https://groups.google.com/d/msgid/ait0/fb0ee544-1f13-4b11-a6d9-5bd167c0ed2fn%40googlegroups.com
> <https://groups.google.com/d/msgid/ait0/fb0ee544-1f13-4b11-a6d9-5bd167c0ed2fn%40googlegroups.com?utm_medium=email&utm_source=footer>.

[Ard Louis]

Dear Gabriel,

 

This is from a while ago – you mentioned the interesting paper by Daniel Herrmann entitled PAC Learning and Occam’s Razor: Probably Approximately Incorrect;  We have now deposited a response entitled The Uses and Limitations of Occam Algorithms: a response to Herrmann on the Phil-Sci archive – I am cc:’ing my student Zaman who did most of the work.  

 

Very briefly, while we agree with Herrmann that Occam algorithms don’t provide an epistemic justification of Occam’s razor, our reasons for this conclusion are subtly different. We also don’t think his anti-Occam algorithm argument works, but this is not fatal to his main arguments.

 

Hope you find it helpful

 

Best wishes,

Ard