Compression as a Learning Problem

Humans are pretty good at efficiently communicating information to each other. One of the reasons for this is that we can model the listener's expectations (their interpretation) of what we are saying. If I say "Can I have that?", pointing towards the table, you will hand me the pen because you can see I just pulled out my checkbook. We have long-term expectations, a learned pragmatics to conversation (like you knowing I want to write a check), and short-term expectations, like learning the meaning of pronouns.

If we apply this to a computational context, we get an interesting compression algorithm. Imagine computer A trying to send a file to computer B. It's a binary file, and because it's not noise, there are short patterns here and there. A and B both have the same predictive capabilities — let's say they're both using Markov models — so they can guess what the next bit is with a certain confidence. So here's what happens: A starts sending B bits, and B starts learning patterns in the bits being sent. A is modeling B's mind, so it knows what B is expecting. Now if A knows that B is very confident about the next bit, A doesn't even bother to send it, it just moves on. Thus you only transfer a portion of the information, and the rest is implied.

The problem, of course, is how expensive it is for A to correct B if it makes a wrong prediction. Bit-by-bit would have a lot of overhead, so it would probably be best for A to send a long sequence at a time, coupled with a note about any bits B guessed wrong.