Saturday, April 21, 2007

Math and Patterns

I mentioned earlier in the week that math is all about patterns, and that as humans we are naturally good at pattern matching. It's true that we're good at pattern matching. It is an excellent tool for survival. In the past, the person who was able to spot the predator behind the bushes first (i.e. compile the image of the predator from the bits and pieces in the field of vision) didn't get eaten. Even today, it comes in handy by helping us avoid danger.

Our pattern matching skills are really amazing. We can recognize a person from a tiny, two-dimensional blob of color known as a photograph. We can slap the right place when we hear a sound we recognize as a mosquito landing on the arm. We can open the fridge and know that something is rotten thanks to a scent we recognize as "week-old chicken."

And even more amazingly, this pattern recognition can trigger memories of our experiences. If the government investigator asks us about a high school classmate, we may not immediately recognize the name, but upon seeing a yearbook photo, all the memories come rushing back. The sound of a certain breed of dog barking could be enough to spook someone who was once bitten by a dog. The scent of a certain cologne may remind someone of her ex-boyfriend, and depending on the nature of that relationship, may induce feelings of nostalgia or of fear.

Our pattern matching skills are so fine-tuned that we sometimes find patterns in cases where there really are none. Man-in-the-moon, anyone? How about inkblot tests? How about hitting streaks in baseball? We are made to look for patterns, and we find them in the most unlikely places. Because of the clustering illusion, if something doesn't fit our expectations of what randomness looks like, we assign it a significance it does not deserve.

Mathematicians look for patterns, but good mathematicians look for ways to invalidate the patterns they find. The work I do with algorithms is all about finding patterns and making sure that they are really patterns.

How does a person design an algorithm? Here's what I do:

1. Do a simple case of the thing for which you're trying to find an algorithm. Look for pieces of it that can be broken down into individual steps. Look for paths of dependence (e.g. I have to do X before I can do Y).

2. Try your algorithm on a more complicated case. Look for errors and inconsistencies, and alter your algorithm accordingly.

3. Pretend that you know absolutely nothing and have no preconceived notions beyond the consistency of the basic laws of physics and arithmetic (i.e. pretend you are a computer). Follow the algorithm literally. Does it work? If not, refine the algorithm using steps 1 and 2. If so, try it on a few more cases. If it still works, you probably have a good algorithm.

I love patterns. But, I love them so much that it's important to me that the patterns I see are valid patterns, rather than statistically probable outcomes to which I artificially assign meaning.

For example, there is no significant meaning to coincidences that don't feel coincidental, tarot card readings, or psychics. Greta Christina explains it well but I will summarize and then augment her argument a bit. Basically, the likelihood of any single outcome at one moment in time is very low. But, the aggregate probability of one of multiple unlikely outcomes occurring over the course of time is fairly significant.

Let me explain with an example. There is a 1/365 chance that anyone I meet will share a birthday with me (ignoring leap year). Yet if I'm in a room with 22 other people, the chance that two of us share a birthday exceeds 50%, and if I'm one of 57 people, the chance grows to more than 99%. How can this be?

This is because the so-called birthday paradox takes the aggregate probabilities of any one person's birthday matching another's and adds them all together. So yes, it is unlikely that one of these other 56 people shares my birthday, but it is quite likely that a pair with the same birthday exists.

Putting this into a real-life perspective, it's unlikely that tomorrow morning at 7:13 a.m. EDT, a person I know will die in a plane crash. However, it's much more likely that over the course of my lifetime, someone I know will die in a plane crash. This is because a) I meet more people as life goes on, and b) more and more plane crashes occur as time marches on (not necessarily more frequently, I'm just saying that they keep happening and each one makes it more likely that I'll know a victim).

Understanding how to distinguish between true patterns and the clustering illusion is certainly important beyond just work as a mathematician. It will make you resistant to false claims by psychics, snake-oil salesmen, and even your own mind.

Rachel said...

But your systematic attempts to ruin my life... that's a real pattern, isn't it? ;-)

Tony said...

It's often useful to look at the "common sense" pattern recognition the leads to the clustering illusion from an evolutionary perspective. In the land of the blind, the one-eyed man is king. More scientifically, a variation the leads to the addition of a single photo-receptive cell gives a creature the ability to separate light from dark. This in turn allows orientation toward the sun in the day and will certainly be marginally helpful in evading predators. It doesn't have to be perfect, just good enough to give a leg up on the competition. Paley's "irreducibly complex" eye can come later.

Genetically inherited algorithms for pattern recognition work the same way. They don't have to be accurate 100% of the time; they only have to keep you from getting eaten more than your peers. Fortunately for us, we have developed the science of mathematics and no longer have to rely on gut instinct. Unfortunately for us, a lot of people still do.

Rebecca said...