Hutter Prize: Compress a 100MB file to less than the current record of 16 MB
hutter1.net
hutter1.net
From the prize site:
This compression contest is motivated by the fact
that being able to compress well is closely
related to acting intelligently, thus reducing
the slippery concept of intelligence to hard file
size numbers.
Of course, maybe we can find a 15MB executable that outputs the specific Wikipedia file he’s asking for, and there might be clever ways to search for or construct that executable on a specific computer platform, but it doesn’t strike me as some particularly generalizable sense of compression requiring intelligence.
One of the best contenders is the open source cmix which, among other tricks, uses LSTM neural networks to predict the next character/bit: http://www.byronknoll.com/cmix.html
I wonder what the memory/speed/efficiency tradeoffs looks like for that kind of design.
Not just any chunk though. It (presumably) contains a lot of structure that encodes information about [English representations of] the real world.
It's not random, nor is it simple, nor is it an image of a fractal (maybe?) etc.
A system that is able to compress it well makes good predictions about what the data contain which indicates "intelligence" about the structure of the (encoded) world.
Unless the idea is that whatever methodology is required to build this particular program could then be adapted to do other things that seem intelligent. That seems possible, but not at all likely given my reading of the challenge requirements.
> But would you expect that program to itself be useful for anything else?
That exact program, no, but the process of creating that program would be educational, both the compressor that makes it and the process of making the compressor.
Another way of putting it is in terms of the "Twenty Questions" game. Which pre-selected twenty questions allows you to "cover" the most of the Universe of phenomenon? If one set of 20 allows you to distinguish more of the Universe than some other set, then the first set is somehow a better model of the Universe. Does that help?
Is Akinator’s 20q database available as a dataset for non-commercial research purposes? It’d be beat to attempt to compress it in a way where training with one half predicts the other half at the smallest trained model size.
The Kolmogorov complexity of a string is (loosely) the size of the smallest possible Turing machine that will output that string when run. So a string with 1000x "a" has a lower complexity than a random string of length 1000.
He sees GAI as a system that, given all its input up to now (from sensors and the like) and some value-function that defines the goal we're trying to reach, takes the action that has the highest expected value of the value-function. It's hard to give a better definition of intelligence in a completely general sense: given all input, choose the most likely best action.
That requires some guessing about the future: given all this input so far, for all possible next inputs in the next time step, what is the likelihood of each.
And his answer is: the likelihood is correlated with the Kolmogorov complexity of the sequence of all inputs so far, plus the possible future input we're currently considering. The idea is that there is information in the inputs so far, and the sequence that best uses that has the lowest Kolmogorov complexity and is most likely to occur. If we've, seen 999 "a" s, we expect another one. If we've seen a car-shaped object slide left to right on previous camera images, we expect it to continue its movement. If the input so far is completely random then every possible future is equally likely. Et cetera.
Given that, it becomes possible to calculate the value function for every combination of possible action and possible next sensor input, and the AI can know what to do.
Except of course for the detail that this is (wildly) incomputable.
But what is somewhat correlated to Kolmogorov complexity? Compressibility.
So that is why Hutter is interested in better compression algorithms.
All this is very loosely stated from memory, I was interested in this stuff over a decade ago...
I run an non-artificial GI in my brain and can't solve this challenge manually. So AGI doesn't seem sufficient.
If you studied the text and learned everything in it, you'd be able to generate a new text from scratch, from your internal representation of the information. It wouldn't be word-for-word identical, but that's actually evidence that there is a compressed representation in your head. If you got a good sense of Wikipedia's style out of it, your reconstruction would be even better. Now imagine that we let you take notes - little reminders of unusual turns of phrase, hard to remember dates, small outlines etc. You could probably do quite well indeed, perhaps even well enough that your output could be diffed with the original and result in a comparatively small file. I think it would be fair to count that as a win for you, since the computer program is deterministic and can store the diff along with its output. True, we can't measure the size of the data in your head, but compression is definitely occurring because you would certainly fail miserably if you tried to reconstruct 100 megabytes of random binary data in a similar way.
Still, to achieve that last little bit of the way to truly lossless reconstruction without the diff-storing trick will present you with a challenge, I agree. Lossless reproduction inherently requires encoding a lot of noise, to which no pattern can be matched. It's still a valid test because, although there is a hard floor on how much the data can be compressed, a better encoder will get closer and closer to that floor. And there's room for interesting optimizations all the way to the bottom - for example, with the help of a language parser and a thesaurus one could probably encode the difference between your lossy output and the original text rather better than 'diff'...
The Hutter dataset is included, incidentally, and the top is a Transformer-XL (277M parameters) at 0.94 BPC. Does all of that seem 'very much not AGI'?
https://slatestarcodex.com/2019/02/19/gpt-2-as-step-toward-g...
If you think of intelligence as distilling the essence of the universe around you and building on top of that, at least the former starts to sound like really really really sophisticated compression.
A decompressor with a high upfront cost (say a pretrained model) and otherwise higher compression ratio would be more interesting than tweaking yet another PAQ8 variant, but I'm not sure this contest's rules make that very viable.
Dictionaries are powerful tools when compressing small data. But once the data is large enough they stop mattering so much. See the dictionary compression section of https://engineering.fb.com/core-data/zstandard/.
Can you add text to a string of text to make the compressed string shorter?
I suppose you could call it “compressor hinting” and it would be specific to the compressing algorithm. The added text would be tagged through an escape sequence, so it could be removed after the decompressing stage.
My naive approach is to add randomly generated hints to at randomly chosen location and then gzip/ungzip. I haven’t had success yet. I think that the potential is limited by the expressiveness of the compressor’s “instruction set” - ie - can it understand generalized hints.
1. Predefined statistics based on the training data for literals (bytes we couldn't find matches for), literal lengths, match lengths, and offset codes. These allow us to use tuned statistics without the cost of putting the tables in the headers, which saves us 100-200 bytes. 2. Content. Unstructured excerpts from the training data that are very common. This gets "prefixed" the the data before compression and decompression, to seed the compressor with some common history.
Dictionaries are very powerful tools for small data, but they stop being effective once you get to 100KB or more.
1. Pre distributed dictionaries for commonly transmitted data types. Ie: web browsers could ship with a shared dictionary that is generally helpful for JavaScript, then servers could negotiate and send a specially compressed version for those that have the dictionary.
2. Streaming buffered data: eg before sending video, send a dictionary. This is useful because we are interested in compressing each chunk well, not just the overall file. Relatedly - a compression scheme where you need all bytes before you can decompress any is rather useless here.
[1] https://github.com/zelon88/xPress
[2] https://www.honestrepair.net/index.php/2019/03/08/xpress-an-...
I tried programming this idea very briefly a couple years ago but I got pulled away for something else.
julia> setprecision(BigFloat, 10_000) do
findfirst("123","$(BigFloat(pi)))")
end
1926:1928
On the other hand, this type of "encoding" always fun to think about. I would suggest reading "Permutation City" by Greg Egan if you are amused by this.
Assuming optimal conditions (i.e. optimal randomness), you can expect that as many pieces of data will have pointers smaller than them, as pointers bigger than them; you can't win that way necessarily, only in some cases.
But maybe if you can find two 'opposite' algorithms, such that for any data where the pointer is larger with the first, it's smaller in the second...
(From what I know of information theory, the extra bit you have to use to specify which algorithm to use will outweigh all savings, but it's still fun to think about.)
> After returning to Zenon (or wherever), the alien precisely measures the marked rod, obtains lengths A and B, and divides A/B to yield the original integer, which a computer decodes to print out the Encyclopedia.
- Dr Dobb's
E.g., "Because trees tend to have a low albedo, removing forests would tend to increase albedo and thereby cool the planet" is a sentence from the file that would need to be compressed. It should be acceptable for the decompressed text to read, "Eliminating large groups of trees would improve surface reflectivity and provide support for a planetary cooling trend," or to employ any number of similar phrasings.
Any form of AGI arrived at through Hutter's exercise would be more akin to the intelligence shown by an eidetic person when they recite the telephone book, and computers are already good at that.
That number will be much smaller than the text of the sentence.
> Although humans cannot compress losslessly, they are very good at lossy compression: remembering that which is most important and discarding the rest. Lossy compression algorithms like JPEG and MP3 mimic the lossy behavior of the human perceptual system by discarding the same information that we do. For example, JPEG codes the color signal of an image at a lower resolution than brightness because the eye is less sensitive to high spatial freqencies in color. But we clearly have a long way to go. We can now compress speech to about 8000 bits per second with reasonably good quality. In theory, we should be able to compress speech to about 20 bits per second by transcribing it to text and using standard text compression programs like zip.
> Humans do poorly at reading text and recalling it verbatim, but do very well at recalling the important ideas and conveying them in different words. It would be a powerful demonstration of AI if a lossy text compressor could do the same thing. But there are two problems with this approach.
> First, just like JPEG and MP3, it would require human judges to subjectively evaluate the quality of the restored data.
> Second, there is much less noise in text than in images and sound, so the savings would be much smaller. If there are 1000 different ways to write a sentence expressing the same idea, then lossy compression would only save log2 1000 = about 10 bits. Even if the effect was large, requiring compressors to code the explicit representation of ideas would still be fair to all competitors.
1) Needs to run in around 8hrs or less on a single CPU core
2) (I assume) it needs to be self-extracting (and size includes the compression logic).
Size includes decompression logic, which may be what you meant but it is important to distinguish between compression and decompression.
The fact that small compressors like gzip or zpaq do so well at small data/compute but then can't compete as you scale up to tens or hundreds of gigabytes of text (amortizing the cost of those fancy NN models) can be considered a version of the Bitter Lesson: http://www.incompleteideas.net/IncIdeas/BitterLesson.html
TBH I feel limiting RAM usage to 1GB is an unnecessary restriction in 2019.
For instance, DEFLATE has default variable width encoding tables built in based on letter frequency of the English language as measured some time ago. If you use an algorithm with any kind of defaults those count against the cost, but they don’t necessarily cost more to tune it for a solitary input.
For a competition like this, all simple approaches have probably been tried already. The current leader has been tuning their approach for 5 years: http://mattmahoney.net/dc/text.html#1159
The teacher had a hard time explaining shortcuts to her. The girl kept insisting that the PC at school was broken as the shortcut worked in her machine at home.