Tuesday, August 28, 2012

Advances in Long-term Prediction

From IEEE Spectrum:
Where Will You Be December 18th at 6 P.M.?
Long-term prediction is hard, but researchers are on the case 
Steven Cherry: Hi, this is Steven Cherry for IEEE Spectrum’s “Techwise Conversations.”
Where will you be tomorrow at 6 p.m.? You probably know, right? Short-term predictions are easy. Where will you be five months from now at 6 p.m.? Well, if it’s Christmas Day, you might know, but what if it’s the week before? You probably don’t, and probably neither do your friends and family and coworkers.
Long-term prediction is hard.

In fact, it turns out to be very hard. The usual prediction models break down entirely, and new mathematical techniques are needed.

And needed they are, because there’s a lot of utility to being able to make those predictions, whether you’re a credit card company trying to detect fraud in an individual account or a highway-traffic engineer deciding when to schedule a road repair.

My guest today is Adam Sadilek. He’s a postdoctoral fellow with the University of Rochester’s Department of Computer Science, and he recently did a stint with Microsoft Research, where he looked into long-range prediction and came out of it with a paper entitled “Far Out: Predicting Long-Term Human Mobility.” It’s coauthored with John Krumm, who’s a researcher in Microsoft [Research]’s Adaptive Systems & Interaction Group, and it’s being presented this month [July] at the annual conference of the Association for the Advancement of Artificial Intelligence, or AAAI, in Toronto.
Adam, welcome to the podcast.

Adam Sadilek: Thank you for having me.

Steven Cherry: First of all, what is the use of long-term prediction, and were those good examples that I gave?
Adam Sadilek: Yeah, you alluded to a lot of those examples already. Like one is infrastructure planning. If we have a good idea where everybody is going to be two years from now, we can plan building roads better, for example. Another application is peer-to-peer package delivery system, where instead of having dedicated mail carriers, you can actually use the general population to deliver packages, and then you can use a system like Far Out to see where are these people most likely to meet so they can exchange these packages and then route them to the final destination. Another component that actually my colleague at Microsoft already explored is to use long-term prediction to have an intelligent thermostat in your home. So if the thermostats understand your location, it can either preheat or cool down the house based on how likely you are to get home.

Steven Cherry: Very good. So how good are short-term predictions? And why can’t those same methods be used for long-term predictions?
Adam Sadilek: Short-term predictions are myopic, so they look at a very specific localized context. They usually take your past few locations plus some real-time aspect of your current context, and they evolve that one or two steps into the future, and that gives you prediction for the next hour, the next day. But as you force these systems to evolve further and further into the future, they become less and less precise. They diverge and eventually become worse than even a random predictor, because they’re not designed for that purpose. With Far Out, we take a more global view of people’s location data, and for each person we learn a library of prototypical days which we call eigendays, and these eigendays have the property that they capture the dependable repeating components of people’s location signal, and they filter out the transient and undependable aspects of human mobility....MORE