Thursday, September 07, 2006

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.

1 comment:

Anonymous said...

I wonder if this would get better compression and performance than simply compressing a file.

An interesting idea, though; reminds me of some ducks I saw on a lake. I was slowly catching up to them, and after about 15 minutes of chasing them, they all simulataneously leapt into the air and flew away, as if they were synchronized and just counting down the seconds until it was time.

I wonder if a system similar to the one you propose could yield similar results.