Correlation, Information, and Compression

ASIDE: CORRELATION, INFORMATION, COMPRESSION, BEETHOVEN

In the Bertillon system, each physical characteristic was recorded as small, medium, or large rather than as an exact numerical value. When you measure the length of the finger, you divide the criminals into three groups: small-fingered, medium-fingered, large-fingered. And then when you measure the cubit, you divide each of these three groups into three subgroups, so that the criminals are divided ninefold in all. Making all five measurements in the basic Bertillon system divides the criminals into

3 × 3 × 3 × 3 × 3 = 3⁵ = 243

groups; and for each of these 243, there are seven options for eye and hair color. So, in the end, Bertillon classified suspects into 3⁵ × 7 = 1,701 tiny categories. Once you’ve arrested more than 1,701 people, some categories will inevitably contain more than one suspect; but the number of people in any one category is likely to be rather small, small enough that a gendarme can easily flip through the cards to find a photograph matching the man in chains before him. And if you cared to add more measurements, tripling the number of categories each time you did so, you could easily make categories so small that no two criminals—for that matter, no two Frenchmen of any kind—would share the same Bertillon code.

It’s a neat trick, keeping track of something complicated like the shape of a human being with a short string of symbols. And the trick isn’t limited to human physiognomy. A similar system, called the Parsons code,* is used to classify musical melodies. Here’s how it goes. Take a melody—one we all know, like Beethoven’s “Ode to Joy,” the glorious finale of the Ninth Symphony. We mark the first note with a *. And for each note thereafter, you mark down one of three symbols: u if the note at hand goes up from the previous note, d if it goes down, or r if it repeats the note that came before. The first two notes of Ode to Joy are the same, so you start out with *r. Then a higher note followed by a still higher one: *ruu. Next you repeat the top note, and then follow with a string of four descents: so the code for the whole opening segment is *ruurdddd.

You can’t reproduce the sound of Beethoven’s masterpiece from the Parsons code, any more than you can sketch a picture of a bank robber from his Bertillon measurements. But if you have a cabinet full of music categorized by Parsons code, the string of symbols does a pretty good job of identifying any given tune. If, for instance, you have the “Ode to Joy” in your head but can’t remember what it’s called, you can go to a website like Musipedia and type in *ruurdddd. That short string is enough to cut the possibilities down to “Ode to Joy” or Mozart’s Piano Concerto No. 12. If you whistle to yourself a mere seventeen notes, there are

3¹⁶ = 3 × 3 × 3 × 3 × 3 × 3 × 3 × 3 × 3 × 3 × 3 × 3 × 3 × 3 × 3 × 3= 43,046,721

different Parsons codes; that’s surely greater than the number of melodies ever recorded, and makes it pretty rare for two songs to have the same code. Each time you add a new symbol, you’re multiplying the number of codes by three; and thanks to the miracle of exponential growth, a very short code gives you an astonishingly high capacity for discriminating between two songs.

But there’s a problem. Back to Bertillon: What if we found that the men who came into the police station always had cubits in the same size category as their fingers? Then what look like nine choices for the first two measurements are really only three: small finger/small cubit, medium finger/medium cubit, and long finger/long cubit; two-thirds of the drawers in our Bertillon cabinet sit empty. The total number of categories is not really 1,701, but a mere 567, with a corresponding diminution of our ability to distinguish one criminal from another. Another way to think of this: we thought that we were taking five measurements, but given that the cubit conveys exactly the same information as the finger, we were effectively taking only four. That’s why the number of possible cards is cut down from 7 × 3⁵ = 1,701 to 7 × 3⁴ = 567. (The 7 is counting the possibilities for eye and hair color.) More relationships between the measurements would make the effective number of categories still smaller and the Bertillon system still less powerful.

Galton’s great insight was that the same thing applies even if finger length and cubit length aren’t identical, but only correlated. Correlations between the measurements make the Bertillon code less informative. Once again, Galton’s keen wisdom provided him a kind of intellectual prescience. What he’d captured was, in embryonic form, a way of thinking that would become fully formalized only a half-century later, by Claude Shannon in his theory of information. As discussed in chapter 13 of How Not to Be Wrong, Shannon’s formal measure of information was able to provide bounds on how quickly bits could flow through a noisy channel; in much the same way, Shannon’s theory provides a way of capturing the extent to which correlation between variables reduces the informativeness of a card. In modern terms we would say that the more strongly correlated the measurements, the less information, in Shannon’s precise sense, a Bertillon card conveys.

Nowadays, though Bertillonage is gone, the idea that the best way to keep track of identity is by a sequence of numbers has achieved total dominance; we live in a world of digital information. And the insight that correlation reduces the effective amount of information has emerged as a central organizing principle. A photograph, which used to be a pattern of pigment on a sheet of chemically coated paper, is now a string of numbers, each one representing the brightness and color of a pixel. An image captured on a 4-megapixel camera is a list of 4 million numbers—no small commitment of memory for the device shooting the picture. But these numbers are highly correlated with one another. If one pixel is bright green, the next one over is likely to be as well. The actual information contained in the image is much less than 4 million numbers’ worth—and it’s precisely this fact that makes it possible * to have compression, the critical mathematical technology that allows images, videos, music, and text to be stored in much smaller spaces than you’d think. The presence of correlation makes compression possible; actually doing it involves much more modern ideas, like the theory of wavelets developed in the 1970s and ’80s by Jean Morlet, Stéphane Mallat, Yves Meyer, Ingrid Daubechies, and others; and the rapidly developing area of compressed sensing, which started with a 2005 paper by Emmanuel Candès, Justin Romberg, and Terry Tao, and has quickly become its own active subfield of applied math.