Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Compression is prediction

ngrok.com

Post reply on HN
Print view View original

261–270 of 324 posts

Re: Compression is prediction

#261

Post by vrighter »

tgv wrote: post #236
vrighter wrote: post #189

Earlier quoted context omitted.

there are dictionary compressors (decent compression, most common, fast), and statistical compressors (better compression, slower). Statistical compressors are much closer to LLMs in that an llm is learning statistics about the data too. And yes, compression is history, that's what statistics are all about. Statistics can only measure the past to make a prediction about the future. And LLMs work in the same way. The…

Anything can only represent past measurements. Statistics is not an exception. But they don't make a prediction about the future. That comes from a model you have, and it often is implicit: "the linear trend from the last 12 months will hold in the next month" or whatever. So compression isn't by definition prediction. The other way around doesn't have to hold either, but in the case of LLMs it does.

a prediction is not necessarily correct. What compressors actually store is how wrong the prediction was, in fact, a guess takes exactly 0 bits to encode. It builds a st atistical model at runtime based on past encountered data. Exactly the same as llms, with the exception that llms remain fixed at runtime, instead of adapting to the data it is currently processing, so they can't adapt at runtime if the model does not suit the data

Re: Compression is prediction

#262

Post by variadix »

ssivark wrote: post #170
variadix wrote: post #59

Earlier quoted context omitted.

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 compressor…

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.

[0]: https://youtu.be/8Q2G2OGHm1c?t=2483

Re: Compression is prediction

#263

Post by MSkill1 »

I sometimes wonder if compression is a key that can unlock human potential to access higher dimensions of thought.

We talk about the elegance of e=mc2. What we're really talking about is the ability to compress all of the ideas contained in relativity down into such a elegant equation.

The same thing is true for symbolism. We compress enormous amounts of information into a symbol like a crucifix, or in language, the amount of weight a word like Hitler can contain represents a level of compression used to convey meaning which we don't fully understand. Utilizing extreme levels of compression seems to allow the human mind, or perhaps consciousness, to grapple with more difficult and esoteric concepts.

Re: Compression is prediction

#264

Post by Xmd5a »

Lerc wrote: post #138

Prediction is compression, but I am not sure if it is true the other way around. It's obvious that an accurate predictor enables encoding only the data that the predictor gets wrong. But a compressor can encode patterns that defy prediction by looking at the data as a whole. It doesn't have to look at everything in sequence as it arrives. Applying transformations prior to entropy encoding often isn't just 'rearrangin…

https://arxiv.org/abs/2311.08768

>Three Conjectures on Unexpectedeness

>Unexpectedness is a central concept in Simplicity Theory, a theory of cognition relating various inferential processes to the computation of Kolmogorov complexities, rather than probabilities. Its predictive power has been confirmed by several experiments with human subjects, yet its theoretical basis remains largely unexplored: why does it work? This paper lays the groundwork for three theoretical conjectures. First, unexpectedness can be seen as a generalization of Bayes' rule. Second, the frequentist core of unexpectedness can be connected to the function of tracking ergodic properties of the world. Third, unexpectedness can be seen as constituent of various measures of divergence between the entropy of the world (environment) and the variety of the observer (system).

Re: Compression is prediction

#266

Post by Xmd5a »

woliveirajr wrote: post #33

There is Compression done by Prediction by partial matching [0] There is the Kolmogorov Complexity [1], Normalized Information Distance [2] and Normalized compression distance [3] that correlates those. Finally, there's the Pre-Big Bang Informational Compression and the Delayed Release of Antimatter [4] All big {rabbit/black} holes to lose some time, if you have any. [0] https://en.wikipedia.org/wiki/Prediction_by_pa…

https://philarchive.org/rec/GRETIO-35

https://quantum-journal.org/papers/q-2020-07-20-301/

Re: Compression is prediction

#267

Post by wpietri »

detourdog wrote: post #258
wpietri wrote: post #249

Earlier quoted context omitted.

If only there were some sort of way for a reader to dig deeper on a topic without a writer having to spoon-feed them the entire history of everything! It's wild to me what people here expect out of something they got for free and that was offered as a gift.

Mentioning any idea disconnected from its roots may not provide the terms needed to search. Snarky replies always appreciated

Your theory is that anybody who writes anything is obligated to make sure you can find any related information with one Google search? Again, to me that looks like wanting to be spoon fed.

I have no idea why you think the world owes you endless 101-level discourse, but I hope you recognize you're setting yourself up for equally endless disappointment. If you take a little responsibility for your own education, you'll be happier.

Re: Compression is prediction

#268

Post by [deleted] »

qarl2 wrote: post #259

Consider: If you want to record the motion of the planets, naively you have large tables of positions. To compress that, you may smoothly interpolate sparse positions. To compress that, you encode the laws of gravity and simulate from a starting state. Compression is literally understanding.

[deleted]

Re: Compression is prediction

#270

Post by elendilm »

ChuckMcM wrote: post #160
farfatched wrote: post #36

This is the thesis behind the "Information Theory, Inference, and Learning Algorithms" course that was taught at Cambridge University. > Why unify information theory and machine learning? Because they are two sides of the same coin. In the 1960s, a single field, cybernetics, was populated by information theorists, computer scientists, and neuroscientists, all studying common problems. Information theory and machine l…

It also helps explain to people that LLMs are as likely as bzip to develop "consciousness".

Your take helps to ground oneself and not be swept away by the hype.

But never forget, there is nothing in information science that rules out that bzip cannot develop consciousness.

Sounding silly doesn't mean false. It just sounds silly is all.

Post reply on HN