3 ms·

Could someone explain how these are guaranteed to be lossless?

• gwern 8y ago
  Arithmetic encoding https://en.wikipedia.org/wiki/Arithmetic_encoding https://en.wikipedia.org/wiki/Arithmetic_encoding . The way I would put it is: the statistical model does its best to predict the next bits, assigning short bit strings to what it thinks is likely to come next and long bit strings to less likely next bits, and if it is indeed right, only the short bitstrings need to be emitted; if it's wrong, more long bit strings must be spent to correct it and emit the exact right bitstring. (Like using shorthand with lots of convenient shortcuts, and then falling back to painfully writing everything out explicitly.) So, you can use imperfect lossy probabilistic models, while still getting lossless compression.
• sreekotay 8y ago
  The NN is used for the probability model for the compression - it's not the compression itself. In simplest terms, think of it as being used to predict the next bit.
• ychen306 8y ago
  Arithmetic coding is a standard compression technique. It uses less bits for more frequent characters (think Huffman code, even though they are not the same). This one makes arithmetic coding "adaptive". Consider this. The rough frequency of `e' in English is about 50%. But if you just seen this partial sentence "I am going to th", the probability/frequency of `e' skyrockets to, say, 98%. In standard arithmetic coding scheme, you would still parametrize you encoder with 50% to encode the next "e" despite it's very likely (~98%) that "e" is the next character (you are using more bits than you need in this case), while with the help of a neural network, the frequency becomes adaptive.