Hacker News Reader

Comment by gr_norm | Hacker News Reader

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.

View on HN

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.

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.

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.

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.

In a world where we see 0+ strings more often the first compressor would be better

But what does it mean to say "in a world where 0+ strings occur more often"? Typically that's not some immutable fact of nature. It might be merely an artifact of the current state of the world, that could change next year.

Eg: cigarette smoking was extremely common and a recommended social activity in the past, but now it's not.

If you asked someone would they still smoke if cigarettes were harmful, and they tell you that it's an out of distribution question because they don't know a world were cigarettes are harmful, you'd question their intelligence.

We want predictive models to be able to estimate the consequences of different (counter-factual) actions to then pick the best one.

Reply on news.ycombinator.com