upvote

points

by porphyra14 hours ago |
comments
upvoteby gr_norm14 hours ago|
next
[-]
A maximally efficient compressor for the existing data distribution is not in general (and often will not be) maximally efficient for future data. The former may only be enabled by convenient local optima of the input distribution that a compressor accounting for the latter could not take advantage of.

For instance, consider the distribution of strings drawn from the language '0+'. Now consider the same for the language '[01]+'. A compressor looking at only the strings of the first language within those of the second can do a much better job if it does not have to account for future data.

This also relates distantly to the idea of overfitting in machine learning.

reply
upvoteby AlotOfReading14 hours ago|
parent|
next
[-]
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.
reply
upvoteby versteegen10 hours ago|
parent|
next
[-]
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.

reply
upvoteby AlotOfReading10 hours ago|
parent|
[-]
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.
reply
upvoteby blobbers4 hours ago|
parent|
[-]
The winner generalize really well. They're just incredibly slow.

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

reply
upvoteby vatsachak6 hours ago|
parent|
prev|
[-]
In a world where we see 0+ strings more often the first compressor would be better
reply
upvoteby tcgv14 hours ago|
prev|
next
[-]
"Compression can be prediction" would be more accurate.
reply
upvoteby GornRok14 hours ago|
prev|
[-]
[dead]
reply