6 ms·
This is just compression with a monster dictionary. It would be faster to just use a giant word and phrase file as such.
by api 6y ago
This is just compression with a monster dictionary. It would be faster to just use a giant word and phrase file as such.
- nullc 6y agoGPT-2 is not just a dictionary, it's enormous non-linear function. This compressor gets compression levels which are unachievable with a dictionary. Alas, its arithmetic coder isn't bijective-- so you can't just decompress encrypted input back into english.
- blackbear_ 6y ago> GPT-2 is not just a dictionary, it's enormous non-linear function. Dictionaries are non-linear functions. > This compressor gets compression levels which are unachievable with a dictionary. I don't see why this is the case, care to elaborate?
- croddin 6y agoA dictionary doesn’t give a prediction about what the next word in string will be. GPT-2 does and those predictions can be used so save space.
- cma 6y agoA dictionary of n-grams does, which I think is what he is describing.
- sidarape 6y agoGPT is way better at next-word predictions than n-grams. However, I agree with OP that the resulting compression scheme is probably not very practical all things considered.
- TheRealPomax 6y agoA dictionary of n-grams does not change its probabilities based on "text seen so far", so you'd need an unbounded n. In practice, n-gram dictionaries don't encode for more than very low values of n, so while yes, abstractly we can say that GPT-2 is equivalent to an n-gram dictionary with some high n, those dictionary cannot be constructed, let alone used, leaving the equivalency is purely theoretical. GPT-2 is not a dictionary.
- cma 6y ago>GPT-2 is not a dictionary. I was only responding to the statement that dictionary methods don't give a prediction of the next word in a string will be. I wasn't in any way saying GPT-2 is a dictionary.
- rahimnathwani 6y ago"Alas, its arithmetic coder isn't bijective-- so you can't just decompress encrypted input back into english." OP calls it a lossless encoder. What makes you say it's not bijective?
- djbtkvehvf 6y agoIf it was bijective, any possible string of bytes could be decoded, even a random string. Here's an example of a bijective compression system—one of the first AFAIK: http://www3.sympatico.ca/mt0000/bicom/ http://www3.sympatico.ca/mt0000/bicom/
- nicoburns 6y ago> If it was bijective, any possible string of bytes could be decoded Is that true? Couldn't it is also just have a different output domain. For example the function: f: non-zero positive integers -> even non-zero positive integers f(x) = 2x is bijective.
- snakeboy 6y agoI believe here "bijective" is being used with the implicit assumption that we're talking about the same finite sets, "byte-strings up to a fixed length". From the link on BiCom: > compression with bicom is completely bijective -- any file is a possible bicom output that can be decompressed, and then recompressed back to its original form.
- nicoburns 6y ago"any possible string of bytes could be decoded" still doesn't seem like the right criteria though. Gzipping is lossless/bijective, but an arbitrary byte stream won't necessarily be a valid gzip archive.
- lidjfsljbn 6y agoLossless is not equivalent to bijective. Gzip is not bijective. The definition of bijective compression is that an arbitrary bytestream is valid for decompression. To put it another way: because there are some output files that gzip compression can never create (whatever the input), it's a not surjective function from the set of possible inputs to the set of possible outputs. For this reason it is not bijective.
- jkhdigital 6y agoYes, you can decompress a random string. Might be garbage, but arithmetic coding won’t “fail”.
- nullc 6y agoNot all random strings decompress, also termination is an explicit symbol that can only happen once, so for most random inputs it only consumes a tiny amount of the input.
- seanwilson 6y ago> This is just compression with a monster dictionary. Are there any compression methods based on this? E.g. a browser or OS that ships with huge lists of common words and sentence fragments?
- blackbear_ 6y agoHuffman coding [1] and all derived algorithms do. They find the most common "words" and assign them shorter codes. Language models, among which GPT-2, do essentially the same: they learn what is likely to appear in the text, albeit in a much more elaborated way. [1] https://en.wikipedia.org/wiki/Huffman_coding https://en.wikipedia.org/wiki/Huffman_coding
- seanwilson 6y agoYep, but you have to send the created dictionary to the client. I'm asking if there's compression setups that rely on the client already having a massive dictionary downloaded that's reused to decompress downloads from different sources.
- jhardy54 6y agoBrotli! A few months ago I was looking for strings in random binaries and was very confused when I found that my Node.js binary came with tons of fragments of English and HTML. I looked through the Node.js source on GitHub and was horrified when I didn't see any of the text, so I compiled it from scratch and breathed a sigh of relief when my new binary included the text fragments. Turns out Brotli was included as a dependency, and it ships with a list of common fragments that are frequent enough that they justify hardcoding.
- seanwilson 6y ago> Turns out Brotli was included as a dependency, and it ships with a list of common fragments that are frequent enough that they justify hardcoding. How big? I know from coding word games that typical English word dictionaries only take up around 3MB example.
- Veedrac 6y agoNo it isn't. The encoding is conditional on all previously generated characters in the context window.
- rijoja 6y agoWhat would the size be of the equivalent dictionary to GPT-2?
- liuliu 6y agoThe training data is around 40GiB: https://d4mucfpksywv.cloudfront.net/better-language-models/language_models_are_unsupervised_multitask_learners.pdf https://d4mucfpksywv.cloudfront.net/better-language-models/l... Consider the compression ratio for such text, and you need 2-word / 3-word to 1000-word dictionary, and at 1000-word length, it will be very sparse. I would guess an accelerated structure for such lookup would take around 60GiB. It would require quite a bit of engineering to get it right otherwise can easily blow-up pass that.