Remix.run Logo
gr_norm an hour ago

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.

AlotOfReading an hour ago | parent [-]

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.