Groups keyboard shortcuts have been updated
Dismiss
See shortcuts

Occam's razor justification, missing page number

70 views
Skip to first unread message

Gabriel Leuenberger

unread,
Jul 6, 2024, 3:48:34 PM7/6/24
to Algorithmic Information Theory
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

unread,
Jul 6, 2024, 4:39:03 PM7/6/24
to Gabriel Leuenberger, Algorithmic Information Theory

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

unread,
Jul 6, 2024, 8:54:29 PM7/6/24
to ai...@googlegroups.com

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>.


Message has been deleted

Gabriel Leuenberger

unread,
Jul 9, 2024, 5:49:23 PM7/9/24
to Algorithmic Information Theory
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

unread,
Jul 9, 2024, 7:08:02 PM7/9/24
to Gabriel Leuenberger, Algorithmic Information Theory, Zaman Keinath-Esmail

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

 

Ming Li

unread,
Jul 10, 2024, 12:22:19 AM7/10/24
to ai...@googlegroups.com

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>.


Reply all
Reply to author
Forward
0 new messages