4 ms·
Ziplm: Gzip-Backed Language Model
- jll29 3y agoThis is a nice application of the idea that understanding and compression are equivalent, which is the inspiration behind the Hutter prize (500 K€ for whoever can compress Wikipedia best, see http://prize.hutter1.net/ http://prize.hutter1.net/ - the current state of the art is about 15 MB). Compression can also be used as "machine learning method": but all data vectors with the same class label into a separate bucket; any new, unseen and unlabeled data item can be added to each bucket. The most likely class is the one the bucket of which grows the least when compressed after adding it. The University of Waikato group (Ian Witten and co-workers) did a fair amount of that kind of work, perhaps first, e.g. Frank, Eibe, Chang Chui and Ian H. Witten (2000) "Text categorization using compression models", https://www.cs.waikato.ac.nz/~eibe/pubs/Frank_categorization.full.pdf https://www.cs.waikato.ac.nz/~eibe/pubs/Frank_categorization... - yes, published 23 years ago!).
- puttycat 3y agoFor anyone interested in the idea of compression as learning combined with neural nets, a random list of interesting work: 1. Schmidhuber's classical work applying a time-based Kolmogorov complexity to neural nets https://pubmed.ncbi.nlm.nih.gov/12662875/ https://pubmed.ncbi.nlm.nih.gov/12662875/ 2. Applying a form of Kolmogorov complexity to learn formal languages using RNNs https://direct.mit.edu/tacl/article/doi/10.1162/tacl_a_00489/112499/Minimum-Description-Length-Recurrent-Neural https://direct.mit.edu/tacl/article/doi/10.1162/tacl_a_00489... 3. Hinton and Van Camp - Keeping the neural networks simple by minimizing the description length of the weights https://dl.acm.org/doi/10.1145/168304.168306 https://dl.acm.org/doi/10.1145/168304.168306
- canjobear 3y agoOh crud, I made the front page. It should be obvious that this is junk quality as a language model. But it's a cool example of the equivalence between compression codes and probability distributions, so I hope people find it interesting for that reason. You can also get a bit of an intuitive sense for the patterns that gzip and bzip2 pick up on in text (they like repetitive strings).
- gr0m 3y agoHave you tried beam search as well?
- ronsor 3y agoI think you would get slightly better generations from the model if the input data were tokenized and token IDs were sampled instead.
- canjobear 3y agoPossibly. It would definitely make it even slower though. To sample from the model, if you have a prompt/training data c, you have to compute the compressed length of all strings cx for tokens x in your vocabulary. If you have a long prompt c (like 1 million lines of wikipedia) and a big vocabulary of tokens (like 100,000 different words), you're going to have a bad time.
- vintermann 3y agoIt should be possible to save and reuse the state of the compressor right before the final byte.
- dleeftink 3y agoI think it is a cool 'tangible' demo of how non-human readable data remains learnable for ML purposes. I've recently tried using Nilsimsa and sdeep hashes to reduce the input dimensionality of natural text, with some loss in accuracy on similarity tasks. A combination of byte-pair encoding and local-sensitive hashing might prove a more stable combination. Throw some gzip function that way and we may be able to reduce input corpus file sizes immensely.
- westurner 3y ago> Transformers (GPT-3, Copilot ,) are built upon an expensive self-attention network. Instead or also FFT looks to be 7x GPU-cheaper. "Google Replaces BERT Self-Attention with Fourier Transform: 92% Accuracy, 7 Times Faster on GPUs" (2021) https://syncedreview.com/2021/05/14/deepmind-podracer-tpu-based-rl-frameworks-deliver-exceptional-performance-at-low-cost-19/ https://syncedreview.com/2021/05/14/deepmind-podracer-tpu-ba... The next step of Conway's Game can be calculated with FFT and also 2D Convolution. Convolution > Visual explanation: https://en.wikipedia.org/wiki/Convolution https://en.wikipedia.org/wiki/Convolution
- westurner 3y ago"Convolutions / Why X+Y in probability is a beautiful mess" by 3blue1brown https://youtu.be/IaSGqQa5O-M https://youtu.be/IaSGqQa5O-M
- p-e-w 3y agoIt should be noted that Moby Dick is (in)famous for its very large and unusual vocabulary. Some lighter reading might yield better results for demonstration purposes. Also, while fairly long for a single novel, the number of words is still minuscule compared to what other LMs are trained on. Using the entire Gutenberg library, or a Wikipedia dump, could improve the quality dramatically. Of course, it doesn't really matter, as the whole thing is obviously just a toy, but I still think that this approach should be able to produce much better output than the garbled Moby Dick example.
- boberoni 3y ago"An early version of a new project will sometimes be dismissed as a toy. It's a good sign when people do this. That means it has everything a new idea needs except scale, and that tends to follow." [1] [1] http://www.paulgraham.com/greatwork.html http://www.paulgraham.com/greatwork.html
- optimalsolver 3y agoStrong disagree. In AI, many cool ideas blow up when meeting anything close to real world inputs.
- pseg134 3y agoThat is the perfect attitude for you then. Please ignore this toy and use only the Webscale tech blessed by google.
- jdiff 3y agoThis is a horribly disingenuous and dismissive response. Sometimes good ideas fundamentally just don't work, they miss foundational issues that make them incompatible with reality. That just happens sometimes. Not everything can be polished up and made into something useful.
- usgroup 3y agoHey author, would you mind explaining the conversion from compression length to probability please? Namely this line: scipy.special.log_softmax(-code_lengthsself.conversion(1/temperature)) Your codes are K-ary but this doesn't look like its taken into account ala the README. What is the log(256) conversion factor? What is 1/temperature for?
- canjobear 3y agoI’m measuring the length of the gzipped string in bytes, so K=256. The temperature parameter is there in case anyone wants to play around with it.
- usgroup 3y agoFor anyone else wondering how this works out: 1. You want: p(x) ~ K^(-|x|), where K=256. 2. log p(x) ~ log K^(-|x|) = -|x|log K 3. he is using log(softmax) ~ log(e^x) 4. and log(e^(-|x|log(K))) = -|x|*log K as required.
- idbfs 3y agoCool! I had been thinking about trying this as well, after reading about the idea in one of Cosma Shalizi's notebooks [0]. I'd love to see how something like this performs when "trained" on a corpus the size of the web when given the same kind of computational resources used to train modern LLMs. [0] http://bactra.org/notebooks/nn-attention-and-transformers.html#gllz http://bactra.org/notebooks/nn-attention-and-transformers.ht...
- asim 3y agoI was curious as to whether this would work. Good to see people trying new things. Because the next is to feed it PGP or AES-256 encrypted data and hand it a symmetric key. Just sort of an attempt to secure what lives in the model itself.
- isoprophlex 3y agoBetter write a pull request to have this added to LangChain :^) Eternal, VC money backed, fame awaits!
- giuscri 3y agoCan someone explain?
- mynonameaccount 3y ago[dead]
- djxfade 3y agoPerhaps a stupid question, but is this kinda thing related to how Markov chains work?
- OriPekelman 3y agoBasically "Information theoretically" compression is a measure of informational distance. So basically if text A and Text B contactenated together, compress better than text A and text C it means A and B repeat more patterns. and are closer. All we need are some distance functions .. in a way you can think about it like Levenhstein distance but that can take into account inputs with very different sizes, repetitions, changes in order big inserts etc... Reminds me of a mostly joke ruby project I did a decade ago https://github.com/oripekelman/simple_similarity https://github.com/oripekelman/simple_similarity
- th0ma5 3y agoPreviously, a similar work with great performance: https://news.ycombinator.com/item?id=36707193 https://news.ycombinator.com/item?id=36707193
- diagramist 3y agoThis can be improved by changing the alphabet and the corresponding codes for the text. If the alphabet consisted of digrams then the output would be much more coherent.
- Vetch 3y agoidbfs has posted this link already but did not explain that Shalizi provides a deep theoretical explanation for why universal source coding (does not require information about symbol distribution or statistics) such as Lempel ziv derived compression algorithms can serve as powerful language models if practical restrictions on them such as dictionary and input corpus size are lifted. This is a good example of how old methods can be pushed quite far if similar resources were devoted to them. Who knows, they might even posses advantages hitherto unmet due to a lack of exploring at larger scales. That said, Transformers have a number of practical advantages. The learned projection matrices in attention lend Transformers a dynamic adaptability with respect to learned patterns that help make them programmable by their context, able to work out patterns present in context zero shot and on the fly. gzip based language models will be limited to their dictionary of patterns. The underlying vector space of neural language models also makes semantics more readily learnable (driving novel synthesis such as neologisms and more) while feed forward layers can learn a large range of computations. http://bactra.org/notebooks/nn-attention-and-transformers.html#gllz http://bactra.org/notebooks/nn-attention-and-transformers.ht...
- erostrate 3y agoFabrice Bellard did the converse, using a language model as a compressor: https://bellard.org/nncp/ https://bellard.org/nncp/
- bionhoward 3y agoThe author implies this is a useless toy but looking at the formula shows the one for Solomonoff’s Universal Prior. That makes this a bit beyond a useless toy. Great idea!
- the8472 3y agohttps://gwern.net/scaling-hypothesis#why-does-pretraining-work https://gwern.net/scaling-hypothesis#why-does-pretraining-wo...
- nialv7 3y agoConversely, language models can also be used for compression. For example, https://bellard.org/nncp/ https://bellard.org/nncp/
- 29athrowaway 3y agoWhat about zstd?
- dkatz23238 3y agoWhat would happen if each word in "tokenized" to an integer and then you generate tokens instead of characters to produce a string of coherent words instead of random strings? Maybe the answer is obvious but not to me without diving into it at a deeper level. Would be interested to hear anyones thoughts on this.
- bravura 3y agoCompression based ML approaches and hacks are fascinating. My colleague recently sent me this: https://arxiv.org/abs/2212.09410 https://arxiv.org/abs/2212.09410 "Less is More: Parameter-Free Text Classification with Gzip "...We propose a non-parametric alternative to DNNs that's easy, light-weight and universal in text classification: a combination of a simple compressor like gzip with a k-nearest-neighbor classifier. Without any training, pre-training or fine-tuning, our method achieves results that are competitive with non-pretrained deep learning methods on six in-distributed datasets. It even outperforms BERT on all five OOD datasets, including four low-resource languages. Our method also performs particularly well in few-shot settings where labeled data are too scarce for DNNs to achieve a satisfying accuracy."