Comment by d_burfoot | Hacker News Reader

Comment by d_burfoot | Hacker News Reader

Yes, compression is definitely a rabbit hole - essentially an infinite rabbit hole. Optimal compression requires perfect understanding of the underlying material. So to compress English text well, you need to understand English very well - it's grammar, morphology, semantics, etc.

I crawled very deep into this particular rabbit hole. I built text compressors that exploited linguistic structure. I was able to quantify improvements in my understanding of text by observing improvements in the compression rate. The beautiful aspect of this project is its rigor: lossless compression is such a demanding challenge that you cannot possibly deceive yourself. If you have a bug in your code, you will either decode the wrong result or fail to get a codelength reduction. Using this methodology I was able to build a statistical parser without using any labeled training data.

Unfortunately for me, the advent of GPT and other DNN-based LLMs made this research obsolete. It may still be interesting for humans to build theories of syntax and grammar, but GPT has this information encoded implicitly in its neural weights in a much more sophisticated way than linguistic theories can achieve.

> GPT has this information encoded implicitly in its neural weights in a much more sophisticated way than linguistic theories can achieve

"More data beats clever algorithms" strikes again.

Isn't gpt like 800gb big? I can compress a 1gb file to 0 bytes if i am allowed 1gb of additional data.

You can't if you have to pick the 1gb of additional data before you see the 1gb file you're supposed to compress (which is the situation gpt is in)

Although in this case, we know the data comes from wikipedia and i assume gpt was trained on wikipedia, so it really does seem unfair.

But the parent was talking about lossless, GPT presumably is anything but.

Sure it is, just use a probability distribution over the entire vocabulary of possible tokens to do arithmetic/range coding of the original text.

Uh? GPT is an neural net, right?Which is a bunch of weights, surely, so how can you get lossless compression from that?

(Complete newbie here BTW)

The model can either generate probable outputs or score the likelihood of given inputs.

How does one produce 'lossless' from 'probable' or 'likelihood'?

By running the decoder during encoding. If the decoder already produces the right output, which it will most of the time, then you don’t need to store anything in the file. If it produces the wrong output, store a correction, then continue from there. The final file only needs to include the corrections.

Arithmetic coding is one of the classic information theory methods that produce essentially-optimal results. Like everywhere else in information theory, the eminence of the probability distribution is fully recognised, and given it, arithmetic coding gives you an information-theoretically optimal lossless compression (to the degree that the probability distribution describes the data well) (by treating the objects in question as numbers and intuitively, like the other post says, only keeping diffs).

See https://en.wikipedia.org/wiki/Arithmetic_coding

Let's say your text is "I like red cats", your current token input is at "I like red". Let's say the model thinks "cats" is 25% likely. It also thinks "dogs" is eg 50% likely for the next token. So rather than storing 1 bit (= log p) to encode dog in the output encoded code, it can use 2 bits to store "cats". Totally lossless. At decode time, you're reading the code, so it's going to just pick the "cats" token anyway, even though it's not the likeliest, because it's not randomly sampling here, it's just using the underlying probabilistic model to do entropy coding. It's not lossy here, since we're not letting the model/sampling process freely choose what the text is made of.

GPT, and probably any LLM, can be hooked up to an encoder to produce a lossless data compressor. Patrice Bellard has done this, HN discussion here:

https://news.ycombinator.com/item?id=23618465

Compression is, ultimately, AI.

https://news.ycombinator.com/item?id=38399753

https://news.ycombinator.com/item?id=31923231

Not really. Your task might be to compress random weather data or historical stock info or historical lottery results.

They are not random (e.g. weather data should have a daily or seasonal pattern). And the fact that there does exist a random-looking data doesn't refute the original claim because AI can conclude that the data has a close-to-maximal entropy (i.e. "incompressible") instead.

In those datasets you could improve compression by adding apriori knowledge about their context in the real world - if the compression program knows about historical S&P500 prices, it will be pretty good at compressing all historical stock info. Kolmogorov complexity is indistinguishable from AI

Reply on news.ycombinator.com