4 ms·
Yes, compression is definitely a rabbit hole - essentially an infinite rabbit hole. Optimal compression requires perfect understanding of the underlying materia
by d_burfoot 3y ago
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.
- xnx 3y ago> 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.
- bawolff 3y agoIsn't gpt like 800gb big? I can compress a 1gb file to 0 bytes if i am allowed 1gb of additional data.
- ChadNauseam 3y agoYou 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)
- bawolff 3y agoAlthough in this case, we know the data comes from wikipedia and i assume gpt was trained on wikipedia, so it really does seem unfair.
- _a_a_a_ 3y agoBut the parent was talking about lossless, GPT presumably is anything but.
- d_burfoot 3y agoGPT, 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 https://news.ycombinator.com/item?id=23618465
- pizza 3y agoSure it is, just use a probability distribution over the entire vocabulary of possible tokens to do arithmetic/range coding of the original text.
- _a_a_a_ 3y agoUh? 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)
- pizza 3y agoThe model can either generate probable outputs or score the likelihood of given inputs.
- _a_a_a_ 3y agoHow does one produce 'lossless' from 'probable' or 'likelihood'?
- sp332 3y agoBy 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.
- refset 3y agoCompression is, ultimately, AI. https://news.ycombinator.com/item?id=38399753 https://news.ycombinator.com/item?id=38399753 https://news.ycombinator.com/item?id=31923231 https://news.ycombinator.com/item?id=31923231
- DeathArrow 3y agoNot really. Your task might be to compress random weather data or historical stock info or historical lottery results.
- lifthrasiir 3y agoThey 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.
- ivancho 3y agoIn 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