News for hackers. Stuff that matters.
Re:Gzip and KNN Outperforms Transformers on Text Classification by willvarfar on Thursday July 13, 2023 @07:25AM (#36707545)
For anyone interested in the equivalence between AI and compression, take a look at the Hutter Prize :) http://prize.hutter1.net/

Also worth a look is the Large Text Compression Benchmark http://mattmahoney.net/dc/text.html - currently the world's best compressor is a neural network made by ... the renowned Fabrice Bellard, creator of ffmpeg and QEMU!

And I really dig these pages' refreshingly appropriate text-only style!

Re:Gzip and KNN Outperforms Transformers on Text Classification by ramraj07 on Thursday July 13, 2023 @07:30AM (#36707577)
When you dive deep into the math, many things are fundamentally the same. Superresolution is just glorified deconvolution. A single layer perceptron is a linear kernel SVM is a logistic regression. FFT is just factorisation.
Re:Gzip and KNN Outperforms Transformers on Text Classification by iJesus on Thursday July 13, 2023 @09:46AM (#36709041)
What does it take to learn math at such a deep level?
Re:Gzip and KNN Outperforms Transformers on Text Classification by lmeyerov on Thursday July 13, 2023 @10:34AM (#36709776)
Even just undergraduate linear algebra & calc + real analysis & prob/stats... With good teachers to draw the connections

Stuff like info theory are amazing bc of this... But easy to miss if you are just working through a drier text

The crazier version for me is we have a physics professor on our team whose grounding intuitions are use ideas like black holes for mental intuition... Which does not work as well for the rest of the team

(And a lot of modern ML/AI feels very engineered and interchangeable after that, like 'metric function of the month')

Re:Gzip and KNN Outperforms Transformers on Text Classification by TheDong on Thursday July 13, 2023 @11:14AM (#36710535)
Either a year in college, or your entire lifetime. Not that it really matters since mathematically, they're both fundamentally the same, they're both just numbers.
Re:Gzip and KNN Outperforms Transformers on Text Classification by nico on Thursday July 13, 2023 @11:52AM (#36711222)
You don’t really need to go that deep, just broad

You can get a lot just by reading Wikipedia and following links in each article

It’s hard to grasp the formulas and proofs sometimes, but if you only care about understanding the concepts, there are a lot of dots to connect

Re:Gzip and KNN Outperforms Transformers on Text Classification by inimino on Friday July 14, 2023 @01:25AM (#36719816)
Reading textbooks is wildly more effective than trying to pick up new math from Wikipedia.
Re:Gzip and KNN Outperforms Transformers on Text Classification by dekhn on Sunday July 16, 2023 @01:00PM (#36749153)
decades of trying, in my case. and I still only understand a little. I focused a lot on linear algebra, graphs, and probability- most of abstract math is completely outside my understanding.

other folks pick it up quickly in college.

Re:Gzip and KNN Outperforms Transformers on Text Classification by romusha on Thursday July 13, 2023 @11:42AM (#36711045)
Numerical methods are Ax=B
Re:Gzip and KNN Outperforms Transformers on Text Classification by goombacloud on Thursday July 13, 2023 @07:43AM (#36707699)
Specially compression algos that use arithmetic coding with interval weights adjusted based on the prediction of what is likely coming next are very similar. They adjust the arithmetic coding (https://en.wikipedia.org/wiki/Arithmetic_coding) based on the context of the byte/bit to predict, so the more accurate the predicted continuation is, the more efficient is the encoding. The task is very similar to that of the transformers like GPT. A perfect prediction will almost have no additional storage cost because the arithmetic interval doesn't get smaller, and thus no bit gets stored - but anyway, you have to count the size of the decompressor to get a fair benchmark.
Re:Gzip and KNN Outperforms Transformers on Text Classification by gcr on Thursday July 13, 2023 @08:10AM (#36707940)
How is it similar?

There’s been a lot of study going the other direction - using neural networks to aid the entropy prediction in classical compression algorithms - but I’m not seeing the conceptual link between how transformer/attention models work internally and how gzip works internally beyond “similar words are easy to compress”

I’m not seeing it because GPT representations are just vectors of fixed, not varying, size

Re:Gzip and KNN Outperforms Transformers on Text Classification by willvarfar on Thursday July 13, 2023 @10:34AM (#36709774)
An LLM or, well, any statistical model, is about prediction. As in, given some preceding input, what comes next?

One way to measure the accuracy of the model, as in it's "intelligence", is to use the predictions to turn input into all the differences from the prediction; if it's good at predicting then there will be fewer differences and it will compress it.

So seeing how well your model can compress some really big chunk of text is a very good objective measure of it's strength and compare it to the strength of others?

So a competition is born! :)

Re:Gzip and KNN Outperforms Transformers on Text Classification by sumtechguy on Thursday July 13, 2023 @11:26AM (#36710706)
Good summary.

The LLM vs a static tree has some interesting oppositions. With a static tree as emitted by a compression alg will probably many times beat an LLM. As it has full knowledge of the whole stream (or in gzips version that window). So it can do things where it can look back and say 'hm the tree I spit out was not that good let me build a better one'. Where as an LLM does not really have that before hand knowledge. Using a pre-cooked LZW tree for all inputs would be more akin to using an LLM.

Re:Gzip and KNN Outperforms Transformers on Text Classification by willvarfar on Thursday July 13, 2023 @12:04PM (#36711451)
I would envisage the LLM is allowed to train on each and every input token. So, to begin with, it knows nothing; but to predict the very last token, it has internalised the whole preceding stream.

Now I wouldn't expect it to be particularly competitive in enwik8 or enwik9, but the question would be: is there any max-model-size and input-length for which it would right now pull ahead and become the best known or at least competitive predictor?

Re:Gzip and KNN Outperforms Transformers on Text Classification by sumtechguy on Thursday July 13, 2023 @01:56PM (#36713367)
I would expect it to be 'ok'. Basically as if you used a pre-trained LZW table only and shipped that along with each stream but the results would be mixed. A compressor has the advantage of foresight and hindsight whereas a LLM would only have hindsight. As any input stream would be basically at the mercy of the previous streams fed into it. Those may or may not be optimal.

It is an interesting hypothesis. But my gut feeling is I would expect a LLM to perform on average worse. Competitive? Yes, but still worse. But it is something I am sure someone will test.

From the hundreds of different compressor models I have made for myself over the years. Usually believe it or not the compressed data is usually the best part. It is the decode tree/table/key/whatever that usually ends up crowding out the savings on the compressed data. In this case it would be the LLM weights or whatever the LLM spits out for the tree/decode.

Re:Gzip and KNN Outperforms Transformers on Text Classification by goombacloud on Thursday July 13, 2023 @02:07PM (#36713566)
gzip uses LZ and Huffman coding and not arithmetic coding with a predictor, so yes, these are not similar.
Re:Gzip and KNN Outperforms Transformers on Text Classification by BSEdlMMldESB on Thursday July 13, 2023 @09:09AM (#36708553)
yes, absolutely!

this kind of "compression" is essentially "understanding through theories" where theories are like those from physics

which are a lot like stories that explain many things with just the same "characters". in this context a 'character' is more like a concept. for example an atom would fit this bill.

Re:Gzip and KNN Outperforms Transformers on Text Classification by nextos on Thursday July 13, 2023 @10:43AM (#36709941)
Something important to note is that the authors use normalized compression distance (NCD). NCD is a way to approximate Kolmogorov complexity.

This is a pretty old idea, see [1,2]. Old but still very useful, like perceptrons.

[1] Li and Vitanyi. An Introduction to Kolmogorov Complexity and Its Applications.

[2] Clustering by compression. https://arxiv.org/pdf/cs/0312044

Re:Gzip and KNN Outperforms Transformers on Text Classification by klaussilveira on Thursday July 13, 2023 @12:15PM (#36711628)
Fabrice Bellard is such a living legend. Add to that list QuickJS, jslinux, tcc and TinyGL.