Cool result, thanks. But this already smuggles in description length dependence (i.e. something in the direction of a simplicity prior) by requiring the prior to be uniform over programs of each length, no?
(This is a general confusion for me when it comes to the “we can derive Occam’s razor from nothing” slogan)
In this formulation, you only consider programs of exactly length . I don’t know what happens if you instead take uniform prior over programs with length up to. My guess is that this would converge to the Solomonoff simplicity prior as well. The shorter programs are just too few in number to make much of a difference. I can ask Sol.
One could still object that we are privileging length by taking any explicit limit in length at all. But I dunno, this seems pretty practically motivated to me.
EDIT: Sol says yes, indeed converges to the Solomonoff semimeasure as well.
Sol:
Yes — it converges to the same Solomonoff semimeasure. In the book’s notation, let , so Section 3.8.1 proves . If a program is sampled uniformly from all bitstrings of length at most , then . Since is increasing, . For any fixed , . Thus , while for every , hence . Therefore . The same conclusion also holds for the other possible interpretation—choose a length uniformly from , then a string uniformly at that length—by the ordinary Cesàro convergence theorem.
The relevant source is pp. 159–161 of the authors’ PDF: https://www.hutter1.net/publ/uaibook2.pdf. One caveat: this uses exactly the book’s model, where the candidates are all binary strings and ignores unread padding up to the point is printed. A restriction to an arbitrary set of “syntactically valid programs” would need separate assumptions on how their counts grow.
Cool! Thanks for checking that. Made me talk to Fable for a bit and understand it better too.
One could still object that we are privileging length by taking any explicit limit in length at all. But I dunno, this seems pretty practically motivated to me.
I would probably still have this objection, yeah (especially now that I understand better how it results in the simplicity prior, with shorter programs having exponentially more ways to be padded) - we are at a level of fundamental philosophy where IMO we are looking for theoretical principledness, not pragmatic appeal. But I agree that I probably undersold the UD a bit in the post. It’s quite natural, and there’s definitely a deep insight there about how natural a simplicity prior is.
Cool result, thanks. But this already smuggles in description length dependence (i.e. something in the direction of a simplicity prior) by requiring the prior to be uniform over programs of each length, no?
(This is a general confusion for me when it comes to the “we can derive Occam’s razor from nothing” slogan)
In this formulation, you only consider programs of exactly length
One could still object that we are privileging length by taking any explicit limit in length at all. But I dunno, this seems pretty practically motivated to me.
EDIT: Sol says yes,
Sol:
Cool! Thanks for checking that. Made me talk to Fable for a bit and understand it better too.
I would probably still have this objection, yeah (especially now that I understand better how it results in the simplicity prior, with shorter programs having exponentially more ways to be padded) - we are at a level of fundamental philosophy where IMO we are looking for theoretical principledness, not pragmatic appeal. But I agree that I probably undersold the UD a bit in the post. It’s quite natural, and there’s definitely a deep insight there about how natural a simplicity prior is.