Nope; there is a bit more nuance and the distinction is important.
Compression is functionally equivalent to prediction when the data distribution is exactly representative of all future problems. The story changes drastically if you want generalization -- because the test distribution could be arbitrarily different, even if it had the same support! Eg: you observe a rare edge case in your training data and (lossy) compression could simply ignore it. But if you wanted generalization in that particular part of the space -- either because an adversary was testing you, or for design freedom where you choose to build in that specific corner -- then you don't just want data compression, but good prediction performance on a test distribution which peaks in that corner.
Assuming that the training data distribution is exactly the distribution you will ever care for is implicitly doing a lot of the heavy lifting in the claim that compression = prediction, and I'm peeved at how much this statement is unthinkingly repeated like a manifesto.
There is nothing natural about the training data distribution, especially if the data generation process is exploratory while the downstream usage will be exploitative.
How does that invalidate the "compression is prediction"? If the future data is different and you failed to generalize, then the failure to predict means you got worse at compressing and have to spend more bits storing the new information. Conversely, if the future data is the same as that you've seen previously, you could predict it very well, and compress better as a result.
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.
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.
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.
I’m not exactly sure what distinction you are trying to make, but a compressor that generalizes from currently observed day to potential future data _is_ a better compressor, as it will have better predictions as it observes more of the source data distribution. Maybe you are making a point about whether compressors can “learn” after compressing the input data, but this also isn’t a fundamental property of compressors. Also compressors do have to deal with non-stationary data sources, so it also isn’t correct to say a compressor only models stationary distributions.
But your definition of compression as prediction is tautological. How would you operationalize that into a measurable metric of compression?
The crucial idea is that once you do that and start optimizing for compression, at some point more compression on the training dataset can lead to worse predictions on the futures you care for. Which is very incompatible with the poster statement.
I agree it is tautological in some sense. It is more precise to say compression requires prediction, and rather than sampling (as in a generative model), we use the probability distribution to efficiently encode observations. A better predictive model of the space you want to compress gives you a better compressor.
To your second point, it depends on what you mean by “futures you care for”. In my view, if you optimize your compressor for a set of particular inputs at the expense of all other inputs, you are explicitly making a judgement about what future data you expect to see (and in some sense what data you care about). If the space of data you want to compress well includes all truthful, valid English sentences, then in the limit you need a model of the world to make accurate predictions to compress well.
If you want further evidence of the predictive ability of compression, Marcus Hutter has a talk [0] where he presents a few papers that used a compressor (gzip) to approximate the Kolmogorov complexity of a string. Using this computable approximation you can construct the algorithmic information distance between two string by compressing the concatenation of two strings (pieces of text, DNA sequences, etc.) and measuring how well they compress together vs. their independent compressed sizes. The idea is that the Kolmogorov complexity of the concatenation of two similar strings is lower than the complexity of two dissimilar strings, since you can learn the structure of the data from a portion of the data, and use the learned predictive model to better compress other parts of the input data. Using this idea, the paper’s authors were able to perfectly reconstruct phylogenetic trees and linguistic family trees _simply by measuring the compressed size of concatenations_ of DNA sequences and a piece of text available translated to many languages.
You're just assuming a flawed implementation of a predictor and complain that it's flawed. That doesn't invalidate the general premise that predictors are compressors.
Predictors don't have to give you some corpus-average probability. They can give probabilities adjusted per symbol. The probability could even be exactly 1 for some symbol when the predictor is absolutely certain (and then it costs 0 bits to encode).
If you had a magic oracle predictor that already knew all the data you wanted to send, you'd have perfect compression.
The record setting file compressors are all very generalizable. This comes about because you score compression by adding the program size (including any training data or dictionary) to the compressed data. If they didn't score it this way you could just ship a dictionary of the test data and your program just prints that. So of course they combine it and effectively measure the Kolmorogov complexity.
This means that training data isn't that helpful to top of the line compressors. eg. Fabrice Bellards nncp that's currently the record holding compressor for enwik9 is an LLM that learns on the fly. It's 628KB as shipped (LLM code complexity is high) and it wins on data sets gigabytes in size due to it's ability to create the training data on the fly. No pre-trained LLM comes close when you measure it as above (program size + compressed result).
So it's really not worth that much concern. There's a reason we all say AI is compression and we dismiss comments like the above. They don't pan out. No one's shipping significant dictionaries or pre-trained data. You want to win competitive compression? You'd better have raw code that learns on the fly and is naturally generalizable.
Statistical compression works by learning statistics about the data as compression progresses. This is a(n admittedly very good) implementation of that, but the idea of learning about the data is as old as time (or computers, whichever came last). Pretty much all compressors do this, wither by building a huffmann tree on blocks and shipping the tree allowing the data to be decoded, or by incrementally updating statistics after each token, and using the updated statistics for the next one.
> because the test distribution could be arbitrarily different,
In that case all bets are off for all machine learning algorithms anyway. If the changes are not arbitrarily different then some of the lost performance can be recovered.
You talk about generalization a lot, but perhaps you are not aware that the technical term is defined under the assumption that test and train distribution are the same.
I'd approach this distinction differently. Prediction from compression is valid within the distribution of the compressed data. Which brings it much closer to LLMs in this case (can an LLM talk about a topic it has never seen in training? unlikely if it cannot be derived from other training data)
> Which brings it much closer to LLMs in this case (can an LLM talk about a topic it has never seen in training? unlikely if it cannot be derived from other training data)
This is a great experiment. Do some world building offline about Smergle the Keen finding the Hoopla of Kynashiusous. Then ask ChatGPT what reagents would have been more effective in breaking through the borantiastic door than squeeble stomach juices.
Of course we know the answer - it will either drop into a 'I have only been trained on data before blah blah blah' or 'I cannot talk about current world leaders' or 'I have not been trained on your hackneyed and unpublished romantasy saga, why don't you tell me about it?'
On the other hand, if it is aware of the general concepts of your concept, and has bridging concepts for related topics it has been trained upon, it might try to apply the general concepts to a specific but different scenario.
The point you make is observed in compression too, though, once you start optimizing for certain use cases. When LAME encodes sound into an mp3 it doesn't give equal weight to all frequencies. It throws away data outside the range of human hearing to leave more room for what's in-range.
If your compression algrotihm is deep enough (think LLM), it will capture a lot of abstraction, making it compress well even in future cases that differ from the passed but fit the scheme in some other way.
But not cases that don't fit the scheme, and the future always has some of those. We are continually surprised by what comes next, and have been notoriously bad at predictions that aren't clear trends (until those trends change).
Compression is functionally equivalent to prediction when the data distribution is exactly representative of all future problems. The story changes drastically if you want generalization -- because the test distribution could be arbitrarily different, even if it had the same support! Eg: you observe a rare edge case in your training data and (lossy) compression could simply ignore it. But if you wanted generalization in that particular part of the space -- either because an adversary was testing you, or for design freedom where you choose to build in that specific corner -- then you don't just want data compression, but good prediction performance on a test distribution which peaks in that corner.
Assuming that the training data distribution is exactly the distribution you will ever care for is implicitly doing a lot of the heavy lifting in the claim that compression = prediction, and I'm peeved at how much this statement is unthinkingly repeated like a manifesto.
There is nothing natural about the training data distribution, especially if the data generation process is exploratory while the downstream usage will be exploitative.