It might not be optimal, but it's not wrong to call it the best available guess. That's basically assuming Occam's razor / Solomonoff induction. Hutter published a bunch of work about what it means to have an "optimal" compressor and famously spent the past couple decades running a compression contest on the idea that it'd lead to insights in AI.
replyThere is a distinction between a compressor for a fixed dataset and one for an unknown population from which we have a sample. The optimal compressor for the sample may be the single best guess for the population, but that's not what Solomonoff induction does. It begins with a prior that allows all possible programs, and it never assigns all probability to the single optimal compressor, so it has no problem with the all-zeroes example.
replyBut the Hutter prize (of which I'm a big fan) is for ever-more-optimal compressors, and in fact many of the solutions don't generalise to other input data without stripping out various tricks.
I think it's better to think of the hutter prize as a challenge to see how close people can get to efficiently approximating AIXI without the exponential cost of AIXItl. The fact that winners don't generalize well is just that they're not great approximations, because the behavior is different in the limit.
replyThe winner generalize really well. They're just incredibly slow.
replyMost of the neural compressors are trying to squeeze every last bit out by sacrificing runtime. You can speed them up a fair bit and they're pretty good. fast-cmix with a small priming corpus will probably be about twice as compact as something like lzma or brotli.
[dead]
replyIn a world where we see 0+ strings more often the first compressor would be better
reply