alt Hacker NewsIt 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.
Replies
iwontberude • yesterday at 11:22 PM
[dead]
There 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.
But 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.