March/April 2008

TR10: Modeling Surprise

Combining massive quantities of data, insights into human psychology, and machine learning can help manage surprising events, says Eric Horvitz.

By M. Mitchell Waldrop

Credit: Photo: Bettman/Corbis; Graphics: John Hersey

Multimedia •  Eric Horvitz talks about surprise modeling.

Who: Eric Horvitz, Microsoft Research Definition: Surprise modeling combines data mining and machine learning to help people do a better job of anticipating and coping with unusual events. Impact: Although research in the field is preliminary, surprise modeling could aid decision makers in a wide range of domains, such as traffic management, preventive medicine, military planning, politics, business, and finance. Context: A prototype that alerts users to surprises in Seattle traffic patterns has proved effective in field tests involving thousands of Microsoft employees. Studies investigating broader applications are now under way.

Much of modern life depends on forecasts: where the next hurricane will make landfall, how the stock market will react to falling home prices, who will win the next primary. While existing computer models predict many things fairly accurately, surprises still crop up, and we probably can't eliminate them. But Eric Horvitz, head of the Adaptive Systems and Interaction group at Microsoft Research, thinks we can at least minimize them, using a technique he calls "surprise modeling."

Horvitz stresses that surprise modeling is not about building a technological crystal ball to predict what the stock market will do tomorrow, or what al-Qaeda might do next month. But, he says, "We think we can apply these methodologies to look at the kinds of things that have surprised us in the past and then model the kinds of things that may surprise us in the future." The result could be enormously useful for decision makers in fields that range from health care to military strategy, politics to financial markets.

Granted, says Horvitz, it's a far-out vision. But it's given rise to a real-world application: SmartPhlow, a traffic-forecasting­ service that Horvitz's group has been developing and testing at Microsoft since 2003.

SmartPhlow works on both desktop computers and Microsoft PocketPC devices. It depicts traffic conditions in Seattle, using a city map on which backed-up highways appear red and those with smoothly flowing traffic appear green. But that's just the beginning. After all, Horvit­z says, "most people in Seattle already know that such-and-such a highway is a bad idea in rush hour." And a machine that constantly tells you what you already know is just irritating. So Horvitz and his team added software that alerts users only to surprises--the times when the traffic develops a bottleneck that most people wouldn't expect, say, or when a chronic choke point becomes magically unclogged.

But how? To monitor surprises effectively, says Horvitz, the machine has to have both knowledge--a good cognitive model of what humans find surprising--and foresight: some way to predict a surprising event in time for the user to do something about it.

Horvitz's group began with several years of data on the dynamics and status of traffic all through Seattle and added information about anything that could affect such patterns: accidents, weather, holidays, sporting events, even visits by high-profile officials. Then, he says, for dozens of sections of a given road, "we divided the day into 15-minute segments and used the data to compute a probability distribution for the traffic in each situation."

That distribution provided a pretty good model of what knowledgeable drivers expect from the region's traffic, he says. "So then we went back through the data looking for things that people wouldn't expect--the places where the data shows a significant deviation from the averaged model." The result was a large database of surprising traffic fluctuations.

Once the researchers spotted a statistical anomaly, they backtracked 30 minutes, to where the traffic seemed to be moving as expected, and ran machine-­learning algorithms to find subtleties in the pattern that would allow them to predict the surprise. The algorithms are based on ­Bayesian modeling techniques, which calculate the probability, based on prior experience, that something will happen and allow researchers to subjectively weight the relevance of contributing events (see TR10: "Bayesian Machine Learning," February 2004).