5 ms·
Nope; there is a bit more nuance and the distinction is important. Compression is functionally equivalent to prediction when the data distribution is exactly r
by ssivark 2mo ago
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.
- usernametaken29 2mo agoI think Hutter would vehemently disagree with you on that one ;)
- schopra909 2mo ago100% agreed.
- jbs789 2mo agoThat’s interesting. Also sparked the thought that the assumption only holds if the future looks like the present.
- vanviegen 2mo agoIf 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.
- goatlover 2mo agoBut 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).
- porphyra 2mo agoHow 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.
- gr_norm 2mo agoA 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 2mo agoIt 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.
- iwontberude 2mo ago[dead]
- versteegen 2mo agoThere 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.
- variadix 2mo agoI’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.
- ssivark 2mo agoBut 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.
- variadix 2mo agoI 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. [0]: https://youtu.be/8Q2G2OGHm1c?t=2483 https://youtu.be/8Q2G2OGHm1c?t=2483
- canjobear 2mo agoCompression is still prediction, the predictions just might not be good.
- pornel 2mo agoYou'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.
- deleted 2mo ago[deleted]
- altcognito 2mo ago> Compression is functionally equivalent to prediction when the data distribution is exactly representative of all future problems. At some level, nothing is representative of all future "problems". I think as far as corner cases is concerned, people can optimize for what they think matters. Larger models, higher sensitivities, better filtering. Beyond this, I don't know what you're peeved by. There's no manifesto, there's no claiming that any particular method to prediction is perfect yet.
- omneity 2mo agoI'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)
- monkeydreams 2mo ago> 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.
- bjt 2mo agoThe 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.
- AnotherGoodName 2mo agoThe 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.
- vrighter 2mo agoStatistical 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.
- srean 2mo ago> 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.