4 ms·

Oh 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 compress

Oh 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 ago
Have you tried beam search as well?
ronsor 3y ago
I think you would get slightly better generations from the model if the input data were tokenized and token IDs were sampled instead.
- canjobear 3y ago
  Possibly. 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 ago
    It should be possible to save and reuse the state of the compressor right before the final byte.
dleeftink 3y ago
I 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.
- up2isomorphism 3y ago
  Why does this needs to be "demoed"? The weights for ML inference is obviously "binary".
DarmokJalad1701 3y ago
I am not sure if it was intentional, but in your "Moby Dick" example, the "alphabet" vocab is missing the letter 'f'.
- canjobear 3y ago
  Ha, yeah. I was just running my finger along the keyboard to type out the string. I just regenerated it, btw, and got a better looking result.
  - Twirrim 3y ago
    Python can give you all the characters via the constants on the string stdlib: https://docs.python.org/3/library/string.html?highlight=string#string-constants https://docs.python.org/3/library/string.html?highlight=stri..., e.g.: Python 3.10.6 (main, May 29 2023, 11:10:38) [GCC 11.3.0] on linux Type "help", "copyright", "credits" or "license" for more information. >>> import string >>> string.printable '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!"#$%&\'()*+,-./:;<=>?@[\\]^_`{|}~ \t\n\r\x0b\x0c'
  - usgroup 3y ago
    i suggest you get all the unique characters from the moby dick text and use it as the alphabet if you're generating from it, or truncate the text to just your hand selected characters else gzip cannot even approximate an optimal code if the alphabets don't match.
hedgehog 3y ago
Maybe this was the inspiration for your project but I just saw a paper that applied compressors as part of a text classification system getting accuracy competitive with BERT. 14 lines of Python. https://aclanthology.org/2023.findings-acl.426/ https://aclanthology.org/2023.findings-acl.426/
- canjobear 3y ago
  Yeah, that paper made me wonder how well gzip would work as a language model so I typed up this thing in a coffee shop
  - sam_lowry_ 3y ago
    Reminds immediately this famous article by Ted Chiang "ChatGPT Is a Blurry JPEG of the Web " https://www.newyorker.com/tech/annals-of-technology/chatgpt-is-a-blurry-jpeg-of-the-web https://www.newyorker.com/tech/annals-of-technology/chatgpt-...
    - DonHopkins 3y ago
      I'm looking forward to Progressive ChatGPT, that immediately answers your question with an thoughtfully chosen emoji, that expands into an irresistible clickbait title, that expands into a viral tweet, that expands into a fascinating forum comment, that expands into a ranting and raving blog post, that expands into a ponderous wikipedia page, that expands into a voluminous e-book, that expands into ...
    - dleeftink 3y ago
      Thank you for posting, I enjoyed the article. In true cybernetics fashion, the maximum compression ratio of information seems to be the current grail of our machine learning efforts, whether that is through inferring heuristics or gradually incorporating knowledge about the world. I'm interested to see where on the information density gradient various organisms exists in their ability to do so..DNA seems awfully wordy, but has proven to be a very dense storage medium.
userbinator 3y ago
Repeating this experiment with a more optimal compression algorithm might be interesting too.
- canjobear 3y ago
  It doesn't look qualitatively any better with bzip2 or lzma.
- nerdponx 3y ago
  In some sense, the feature space learned by a NN is a compression algorithm.
- versteegen 3y ago
  Sure! The current best achieved compression for English text (well, specifically, Wikipedia articles) is Fabrice Bellard's nncp, which uses... transformers. http://mattmahoney.net/dc/text.html#1085 http://mattmahoney.net/dc/text.html#1085 Unfortunately I don't think anyone has posted any trained models after running any inputs through it, which could be used to repeat the experiment. I would try it, but I don't have a AVX2 CPU. However, most research into reducing the model perplexity of text (increasing the compression ratio when the model is used for encoding) uses fixed language models which are learnt offline. Obviously, they use transformers too. You can see some of them here: https://paperswithcode.com/sota/language-modelling-on-wikitext-103 https://paperswithcode.com/sota/language-modelling-on-wikite... However (token) perplexity is only comparable across models if the same tokenizer is used. The above page seems to compare papers using the GPT-2 tokenizer. I would assume that if you controlled for differences in tokenizers by just measuring bits-per-word/byte, GPT-4 without RLHF would achieve the highest compression. It should be obvious that RLHF increases perplexity because it changes the training objective to something other than predicting text.
- vintermann 3y ago
  If I understand it correctly, this implementation re-compresses the prefix 256 times, once for each possible byte continuation. It should be possible to save a lot of work by saving the state of the compressor just before the predicted byte, and reusing it. Also, since gzip works on a limited sliding context window, it's probably pointless to give it a prefix much longer than the window... unless there's something about the algorithm that I'm missing. Same with bzip2 and its block size.
fnordpiglet 3y ago
I think this would work better if you used a fixed compression dictionary trained over the corpus and used to compress the prompt. Unless you do that? I wouldn’t expect this to work well for such a small training set. But I do wonder if this is an excellent way to improve token resolution; especially in poorly represented languages like southeast Asian.
manmal 3y ago
A maybe dumb question for understanding: does a longer output imply lower probability of the input?
- usgroup 3y ago
  its not a dumb question -- optimal coding in theory assigns codes of shorter length to more frequently occurring tokens hence by design longer codes imply lower probabilities: that's how compression is achieved.

gr0m 3y ago

Have you tried beam search as well?

ronsor 3y ago

I think you would get slightly better generations from the model if the input data were tokenized and token IDs were sampled instead.

canjobear 3y ago
Possibly. 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 ago
  It should be possible to save and reuse the state of the compressor right before the final byte.

dleeftink 3y ago

I 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.

up2isomorphism 3y ago
Why does this needs to be "demoed"? The weights for ML inference is obviously "binary".

DarmokJalad1701 3y ago

I am not sure if it was intentional, but in your "Moby Dick" example, the "alphabet" vocab is missing the letter 'f'.

canjobear 3y ago
Ha, yeah. I was just running my finger along the keyboard to type out the string. I just regenerated it, btw, and got a better looking result.
- Twirrim 3y ago
  Python can give you all the characters via the constants on the string stdlib: https://docs.python.org/3/library/string.html?highlight=string#string-constants https://docs.python.org/3/library/string.html?highlight=stri..., e.g.: Python 3.10.6 (main, May 29 2023, 11:10:38) [GCC 11.3.0] on linux Type "help", "copyright", "credits" or "license" for more information. >>> import string >>> string.printable '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!"#$%&\'()*+,-./:;<=>?@[\\]^_`{|}~ \t\n\r\x0b\x0c'
- usgroup 3y ago
  i suggest you get all the unique characters from the moby dick text and use it as the alphabet if you're generating from it, or truncate the text to just your hand selected characters else gzip cannot even approximate an optimal code if the alphabets don't match.

hedgehog 3y ago

Maybe this was the inspiration for your project but I just saw a paper that applied compressors as part of a text classification system getting accuracy competitive with BERT. 14 lines of Python. https://aclanthology.org/2023.findings-acl.426/ https://aclanthology.org/2023.findings-acl.426/

canjobear 3y ago
Yeah, that paper made me wonder how well gzip would work as a language model so I typed up this thing in a coffee shop
- sam_lowry_ 3y ago
  Reminds immediately this famous article by Ted Chiang "ChatGPT Is a Blurry JPEG of the Web " https://www.newyorker.com/tech/annals-of-technology/chatgpt-is-a-blurry-jpeg-of-the-web https://www.newyorker.com/tech/annals-of-technology/chatgpt-...
  - DonHopkins 3y ago
    I'm looking forward to Progressive ChatGPT, that immediately answers your question with an thoughtfully chosen emoji, that expands into an irresistible clickbait title, that expands into a viral tweet, that expands into a fascinating forum comment, that expands into a ranting and raving blog post, that expands into a ponderous wikipedia page, that expands into a voluminous e-book, that expands into ...
  - dleeftink 3y ago
    Thank you for posting, I enjoyed the article. In true cybernetics fashion, the maximum compression ratio of information seems to be the current grail of our machine learning efforts, whether that is through inferring heuristics or gradually incorporating knowledge about the world. I'm interested to see where on the information density gradient various organisms exists in their ability to do so..DNA seems awfully wordy, but has proven to be a very dense storage medium.

userbinator 3y ago

Repeating this experiment with a more optimal compression algorithm might be interesting too.

canjobear 3y ago
It doesn't look qualitatively any better with bzip2 or lzma.
nerdponx 3y ago
In some sense, the feature space learned by a NN is a compression algorithm.
versteegen 3y ago
Sure! The current best achieved compression for English text (well, specifically, Wikipedia articles) is Fabrice Bellard's nncp, which uses... transformers. http://mattmahoney.net/dc/text.html#1085 http://mattmahoney.net/dc/text.html#1085 Unfortunately I don't think anyone has posted any trained models after running any inputs through it, which could be used to repeat the experiment. I would try it, but I don't have a AVX2 CPU. However, most research into reducing the model perplexity of text (increasing the compression ratio when the model is used for encoding) uses fixed language models which are learnt offline. Obviously, they use transformers too. You can see some of them here: https://paperswithcode.com/sota/language-modelling-on-wikitext-103 https://paperswithcode.com/sota/language-modelling-on-wikite... However (token) perplexity is only comparable across models if the same tokenizer is used. The above page seems to compare papers using the GPT-2 tokenizer. I would assume that if you controlled for differences in tokenizers by just measuring bits-per-word/byte, GPT-4 without RLHF would achieve the highest compression. It should be obvious that RLHF increases perplexity because it changes the training objective to something other than predicting text.
vintermann 3y ago
If I understand it correctly, this implementation re-compresses the prefix 256 times, once for each possible byte continuation. It should be possible to save a lot of work by saving the state of the compressor just before the predicted byte, and reusing it. Also, since gzip works on a limited sliding context window, it's probably pointless to give it a prefix much longer than the window... unless there's something about the algorithm that I'm missing. Same with bzip2 and its block size.

fnordpiglet 3y ago

I think this would work better if you used a fixed compression dictionary trained over the corpus and used to compress the prompt. Unless you do that? I wouldn’t expect this to work well for such a small training set. But I do wonder if this is an excellent way to improve token resolution; especially in poorly represented languages like southeast Asian.

manmal 3y ago

A maybe dumb question for understanding: does a longer output imply lower probability of the input?

usgroup 3y ago
its not a dumb question -- optimal coding in theory assigns codes of shorter length to more frequently occurring tokens hence by design longer codes imply lower probabilities: that's how compression is achieved.