8 ms·
Lossless compression of English messages using GPT-2
- starpilot 6y agoI compressed "I am going to work outside today," then put the compressed output in Google Translate. Google translated the Chinese characters back to English as "raccoon."
- dhosek 6y agoI think the Chinese text that comes out confuses Google translate. I took the whole first sentence of Hamlet's soliloquy which compressed to 䮛趁䌆뺜㞵蹧泔됛姞音逎贊 and plugged that into Google Translate. It came back with "Commendation." The reverse translation is 表彰
- dhosek 6y agoI hit the reverse button again, and got "recognition" which translated back to 承认 which finally got into a closed loop to recognition and back to the same Chinese text.
- james412 6y agoIt's not Chinese text, it's an arithmetic-coded stream of bits mapped so the bits fall within the range of some codepoints. It's basically a variant of base64 except for Unicode. (Side note: aren't these codepoints very expensive to encode in UTF-8? It seems there must be a lower-valued range more suited to it)
- willcipriano 6y agoIt's probably similar to this: https://pieroxy.net/blog/pages/lz-string/index.html https://pieroxy.net/blog/pages/lz-string/index.html Check the 'How does it look?' section.
- greenshackle2 6y agoYeah I don't understand why it's using CJK, the page claims: > each compressed character holds 15 data bits by using the CJK and the Hangul Syllables unicode ranges. In UTF-8 these characters take 3 bytes each. Which makes it less space efficient than base64 (60% overhead vs 33% overhead). The CJK/Hangul scheme has more information per character but I'm not sure where that matters.
- jkhdigital 6y agoIt's so that the output uses printable characters, that's all. The raw output would actually just be random bits, or at least something approximating random bits if GPT-2 is as good as we hope it is.
- greenshackle2 6y agoYes, I understand. But base64 is the bog standard solution for encoding arbitrary binary data as printable characters. So I'm just wondering why you would use something more obscure, less space efficient, and not ascii compatible.
- im3w1l 6y agoBecause it will impress uneducated people with how much smaller (in terms of screen real estate) the resulting message is. EDIT: Ohhh, I know, and because twitter cares about characters. So you can use this to put essays into tweets.
- toast0 6y agoThe page for base32768 has some efficiency charts for different binary to text encodings on top of different UTF encodings, as well as how many bytes you can use them to stuff in a tweet. Depends on where you're going to house the data, I guess. https://github.com/qntm/base32768 https://github.com/qntm/base32768
- infogulch 6y agoIn addition to being 94% efficient in UTF-16 (!), this reveals some additional reasons why one might want to optimize for number of characters: fitting as many bytes as possible into a tweet which is bounded in the number of characters not bytes.
- dheera 6y agoThis is Chinese characters mixed with Korean characters and this is pretty much never done by humans. It is analogous to mixing English and Heiroglyphics and typing out some gibberish with both. The author might as well have included the rest of the Unicode range including Arabic, Emoji, and math symbols.
- gHosts 6y agoFor more fun enter "I am going to work outside today" compress, delete the second character and decompress, the result is... "I know what you're thinking –"
- minimaxir 6y agoA neat trick I found while working with GPT-2 is that byte-pair encoding is, in itself a compression method. With Huggingface Transformers, encoding/decoding this way is very fast. I've implemented this approach in my aitextgen package (https://github.com/minimaxir/aitextgen/blob/master/aitextgen/TokenDataset.py#L238 https://github.com/minimaxir/aitextgen/blob/master/aitextgen...) to encode massive input datasets as a uint16 Numpy array; when gzipped on disk, it's about 1/10th of the original data set size. However, the technique in this submission gets about compression to 1/10 w/o the gzipping. Hmm.
- jkhdigital 6y agoThis is really just a way to show how good GPT-2 is at predicting text. If you know anything about information theory, you'll know that the entropy of the information source places a hard limit on how much it can be compressed. If GPT-2 is really good at predicting English text, then the entropy of its output should be very very close to the entropy of natural English text. Thus, using GPT-2 predictions as an adaptive source encoder will achieve compression ratios that approach the information content (entropy) of English text.
- The_rationalist 6y agoNot directly related but does anybody know where can I find lossless text simplification/ellipsis expansion? For example The cat like piano and violin. Would semantically losslessly expand to The cat like piano. The cat like violin. I'm working on AGI level text understanding and getting those lossless simplification passes would really help.
- speedgoose 6y agoI don't understand why it shows Chinese characters. Assuming utf-8, English characters are a lot more compact than Chinese characters. So we can't really compare. Otherwise it's a good idea and it works, but it's super slow, only working for English text, and the system requirements are huge. I like it.
- YetAnotherNick 6y agoI think base 64 would be a good option as it is easy to copy
- sp332 6y agoIt's counting characters, so it is comparable. This is useful for applications that limit the number of characters, e.g. Twitter.
- m4rtink 6y agoYep, as far as I can tell, you can cram about twice as much information to the same number of Japanese as you would cram into Latin characters. I wonder if Chinese is even more info dense, as it does not have the syllabic hiragana/katakana characters ?
- dheera 6y agoModern Chinese is typically more dense than modern Japanese (which is partially phoenetic), and ancient formal Chinese is even more compact than modern Chinese. However it's worth noting that Chinese characters are analogous to entire words in English, and are composed of components much like English characters are composed of letters. For example "thanks" is spelled "t h a n k s" "謝" is made up of "言 身 寸" (Of course, the components in Chinese have less correlation to their pronunciation, but the main point I'm making here is that there is a LOT of overlap in the common components used to assemble the entire Chinese lexicon.) It is really not a fair comparison to compare languages in terms of their number of characters needed to represent something. Better measures would be the fastest time (in seconds) needed to use speech to convey a concept intelligibly to an average native speaker, or the square centimeters of paper needed to convey an idea given the same level of eyesight.
- matthewfcarlson 6y agoJust for kicks and giggles, I threw in some rather obscure words to see what would happen. It's been compressing for a few minutes and showing no sign of progress. Cool project!
- knolax 6y agoThis should be top comment.
- jkhdigital 6y agoFor anyone who doesn't get why this would happen: GPT-2 basically outputs a probability distribution for its guess of the next word, and then the encoder uses these distributions to perform arithmetic coding adaptively. If the next word in the source text is not actually present anywhere in the output distribution, it cannot encode it.
- londons_explore 6y agoI may be wrong, but I thought GPT2 could also output partial words/syllables (for unknown words), or individual letters if they don't make a syllable. The simple way to achieve that is to have an encoding dictionary of words, but then add to the end of the dictionary "sh", etc., and then add to the end of that "a", "b", "c", etc. When tokenizing words, prefer to use a whole word, but if you can't do that, split to syllables, and failing that, individual letters. That has the benefit that any ascii string can go through the system.
- jkhdigital 6y agoYes, this is why I said "basically". The fact that GPT-2 tokens are not necessarily prefix-free can be a problem for arithmetic coding, but I've found that "greedy" parsing almost never fails in practice. So yes, there are ways to work around this but it seems like the simplest explanation for why unusual words break the encoder.
- Vvector 6y agoLooks like the work is done server-side. And we've hit a bottleneck
- lxe 6y ago> using the probability of the next word computed by the GPT-2 language model Can the same effect be achieved by looking at actual probability of the next word from a large corpus of existing text (a-la markov chains)?
- duskwuff 6y agoLess effectively. GPT-2 and a Markov chain are both predictive models; GPT-2 just happens to be a much more complex (and, in most cases, more accurate) model for English text, so fewer bits are required on average to encode the delta between its predictions and the actual text.
- vessenes 6y agoI am guessing that Fabrice is planning on some sort of commercialization here; this is a re-issue of something originally on his website. A fun game to play is to see how many characters a name takes: it’s an indication of your importance to the Internet. In answer to the why Chinese, it seems to me to be easier to read and more compact to display than hexlified bytes.
- dhosek 6y agoMy last name compressed to 3 characters. I tried my wife's last name and it was 3 characters, then I decided to add the accent to it that normally gets dropped in an English-language context and it compressed to 2. Adding first names, I was 4 characters and she was 5 with and without the accent. William Shatner went to 6 characters. Barack Obama went to 2. William Shakespeare also to 2.
- vessenes 6y agoRight, I guess your last name is the importance of all Hoseks worldwide, albeit vis-a-vis some chunking of the word, so it has to compete with the importance of other Hos es like hospitals and so on.
- kordlessagain 6y ago偖讇灥爕䒫뷕먓띑䴏㣅뒢佐氧糷䉻끟䕶揠豊
- fla 6y agoTry swapping a few characters in the compressed string before decompressing and get a totally unrelated, but somewhat plausible, sentence.
- adonovan 6y agooh this is so much fun! It's like tuning an old radio and suddenly hearing speech amid the static. A tiny nudge on the dial and it's a different accent/topic/language altogether.
- jmiller099 6y agoTried similar. Typed in 你好吗 and decompressed it. The decompression was an entertaining read.
- VMG 6y agoTry swapping a few characters in the compressed string before decompressing and get a totally unrelated, but somewhat plausible, sentence. --> 䔹䧹焫놉勏㦿顱㦽膑裚躈葊 Swapping last two: 䔹䧹焫놉勏㦿顱㦽膑裚葊躈 --> Try swapping a few characters in the compressed string before decompressing and get a totally unrelated, but somewhat applied tlh Swapping first two: 䧹䔹焫놉勏㦿顱㦽膑裚躈葊 --> Sexy Shania Twain acting as a sprite for sexy Hogan's Alley demo dude my site my favorite animal's name is camelid 2 my favorite artist is david maile my favorite movie's are Pretty wild!
- VMG 6y agoAfter some more tweaking it looks like the most-significant bits come first
- jkhdigital 6y agoIt's just adaptive arithmetic coding, with the distribution provided by GPT-2 instead of some other statistical analysis of the source. He uses CJK simply to make the output printable, but it's really just random bits. I mean, it's a neat idea, but certainly not novel.
- Erwin 6y agoI run this code in Python: for i in range(20): print ''.join(unichr(random.randrange(20000, 25000)) for x in range(4)) to generate some random text; one string like 劓惂儶宓 turns up this bizarre output: > Honeybees ( Apis mellifera ) are splendidly beautiful little creatures. They have shapely abdomens, amphistales and pedipalps, round chests, and square backs … all of them beautifully highly marketable. Exactly what has caused the popularity of bees I do not quite know; just what they do is a mystery to me. I beg to differ. The
- hint23 6y agoFYI, the corresponding standalone Linux command line version is available at https://bellard.org/nncp/gpt2tc.html https://bellard.org/nncp/gpt2tc.html . It also does text completion and file compression.
- cs702 6y ago...by the one and only Fabrice Bellard: "gpt2tc is a small program using the GPT-2 language model to complete and compress (English) texts. It has no external dependency, requires no GPU and is quite fast...The compression ratios are much higher than conventional compressors at the expense of speed and of a much larger decompressor. See the documentation to get results on text files from well known compression data sets." A natural question I've pondered from time to time is whether Fabrice is really a time traveler from a more advanced civilization in the future, sent back in time to show us, mere mortals, what humankind will be capable of in the future. If this sounds far-fetched, consider that he has created FFMPEG, QEMU, LibBF, SoftFP, BPG, TinyEMU, a software implementation of 4G/LTE, a PC emulator in Javascript, the TCC compiler, TinyGL, LZEXE, and a tiny program for computing the biggest known prime number. And that's just a partial list of his successful projects, which now of course also include software for lossless compression with Transformer neural networks. Any of these projects, on its own, would be considered a notable achievement for an ordinary human being. Source: https://bellard.org https://bellard.org -- Copied and edited some text from my post a year ago: https://news.ycombinator.com/item?id=19591308 https://news.ycombinator.com/item?id=19591308 -- I never cease to be amazed by the guy.
- timgilbert 6y agoI couldn't agree more, Fabrice Bellard's mom
- VMG 6y ago...and briefly held the record of having computed the precise approximation for Pi https://bellard.org/pi/pi2700e9/ https://bellard.org/pi/pi2700e9/
- londons_explore 6y agoThis particular project is noteworthy mostly for its completeness and 'it just works' functionality. Tens of researchers before him have used arithmetic coding on the outputs of various neural network models to do lossless compression of text or images. Bellards contributions are a packaged tool (as opposed to PoC code) and demo webpage, and the idea of using CJK characters rather than outputting binary data (in todays world of JSON, binary data has fallen out of fashion).
- aquajet 6y agoTitle should be renamed to "Language Models are Lossless Compressors"
- jkhdigital 6y agoExactly, along with a link to some basic information theory Wikipedia articles.
- knolax 6y agoYou boomers need to know that 먓띑뒢끟 are precomposed hangul characters. It's not hard to just say CJK.
- dmarchand90 6y agoI'm really impressed that this seems largely written by scratch in c. "This demo has no external dependency."
- goodside 6y agoNot to diminish what a cool idea this is, but isn’t it cheating to not count the size of the GPT2 parameters as part of the final compression ratio? Assuming the decompressor already has GPT2 weights is analogous to assuming it has a massive fixed dictionary of English words and phrases and doing code substitution — it’s likely the pragmatic answer in some scenario, but it’s not a fair basis for comparison. Real-world compressors use dictionary coders, but they build the dictionary specifically for the data when it’s compressed and then count that dictionary in the compressed size. For competitions like the Hutter Compression Prize (1GB of English Wikipedia) the reported size includes the complete binary of the decompressor program too. GPT2 model weights require over 5GB of storage, so you’d need a corpus orders of magnitude larger for it to be even close to competitive by that standard. And it appears it would lose anyway — the OP claims ~15% ratio even with “cheating”, and the current Hutter Prize winner for 1GB of enwiki is ~11% without “cheating”.
- jkhdigital 6y agoThis is exactly what I was thinking. It seems like he’s just taking advantage of the fact that CJK characters are a lot more information-dense than English letters, and has a turnkey encoder/decoder in the form of the pre-trained GPT-2 language model. I am, in fact, currently involved in research that uses GPT-2 for format-transforming encryption and we follow the exact same recipe but in reverse. Encrypt a message, then "decompress" the random bits into English text using GPT-2. Assuming the receiver has the same GPT-2 state (model parameters and prompt) then they will reproduce the same random bits by arithmetic compression, which can then be decrypted with the shared key.
- ethbro 6y agoAt some point, isn't this just Shannon coding that takes advantage of higher-order probabilities?
- AaronFriel 6y agoYes, but you can compress arbitrarily many texts of arbitrary size with that 5GB fixed cost. As the number of total bytes compressed goes to infinity, that vanishes in the numerator.
- aapeli 6y agoSo if you end up being famous and talked about a lot on Wikipedia, your name will compress better? The impact of bias in training data is interesting in general here. What's the impact on Wikipedia's article biases? That's probably one of the main corpuses used.
- nmca 6y agoThis guy should enter the Hutter Prize - http://prize.hutter1.net/ http://prize.hutter1.net/ This won't win, but it seems he cares and has some talent :)
- deleted 6y ago[deleted]
- jkhdigital 6y agoPaste encrypted bits (mapped to the CJK range he uses) in the "decompress" box and you've got format-transforming encryption.
- maest 6y agoI'm not at all familiar with arithmetic encoding (or adaptive version tehreof), but, after reading some guides, it seems to me that the novel thing here is using GPT2 to somehow generate a character probability distribution? The theory being that GPT2 should have a distribution closely matching "reality" and thus minimizing the output size?
- d_burfoot 6y agoA fun game is to compress some text, then look up some random Chinese words, cut-and-paste them into the compressed output, and then decompress again.
- nmstoker 6y agoYes or even just swap the compressed character order and it still results in interesting somewhat similar texts.