4 ms·
Even though the implementation details are far from trivial, the general idea is fairly typical. Most advanced compression algorithms work the same way. - Usin
by GuB-42 7y ago
Even though the implementation details are far from trivial, the general idea is fairly typical. Most advanced compression algorithms work the same way.
- Using the previously decoded data, try to predict what's next, and the probability or being right
- Using an entropy coder, encode the difference between what is predicted and the actual data. The predicted probability will be used to define how many bits to assign to each possible value. The higher the probability, the less bits will be used for a "right" answer and the more bits will be used for a "wrong" answer.
Decoding works by "replaying" what the encoder did.
The most interesting part is the prediction. So much that some people think of compression as a better test for AIs that the Turing test. You are basically asking the computer to solve one of these sequence-based IQ tests.
And of course neural networks are one of the first thing we tend to think of when we want to implement an AI, and unsurprising it is not an uncommon approach for compression. For instance, the latest PAQ compressors use neural networks.
Of course, all that is a general idea. How to do it in practice is where the real challenge is. Here, the clever part is to "grow" the image from low to high resolution. Which kinds of reminds me of wavelet compression.
- remcob 7y ago> encode the difference between what is predicted and the actual data Minor nitpick: In the idealized model there is no single prediction that you can take the difference with. There is just a probability distribution and you encode the actual data using this distribution. Taking the difference between the most likely prediction and the actual data is just a very common implementation strategy.
- anamexis 7y agoHow is "the most likely prediction" not a "single prediction that you can take the difference with"?
- derf_ 7y agoWhat if there are two (nearly) equally likely predictions? What if there are N, and they are not close together? "A single prediction that you can take the difference with" makes some assumptions about the shape of your distribution, at least under any reasonable model of "code the difference" where, e.g., probability decreases as the difference gets larger. These are often very good assumptions, to be fair.
- ithinkso 7y agoAnyone interested in this approach to lossless compression should visit (and try to win!) Hutter Prize website[1][2]. The goal is to compress 1GB of english wikipedia [1] http://prize.hutter1.net/ http://prize.hutter1.net/ [2] https://en.wikipedia.org/wiki/Hutter_Prize https://en.wikipedia.org/wiki/Hutter_Prize
- londons_explore 7y agoI don't think anyone has yet applied neural net approaches to the hutter prize with success. The trained neural network weights tend to be very large, and hard to compress, and the hutter prize requires the size of them to be counted too. To win the hutter prize, you'd probably need some kind of training-during-inference system.
- sbierwagen 7y agocmix uses a LTSM net: http://www.byronknoll.com/cmix.html http://www.byronknoll.com/cmix.html
- m463 7y agoI wonder if a larger initial dataset (say 5G or 10G) might lead to better overall % compression.
- pieterk 7y agoThe actual difference here is the encoding, into a representation of a dataset annotated by thousands of people. Sounds like a basis of knowledge or even understanding. I bet this scales way better than any other method on large datasets