Graduate Student Refines Formulas to Optimize How Computers “Think”

When you use computers and devices, chances are algorithms are driving your experience with every click and choice.

But how do these mathematical steps to solve problems actually translate into computing, and how can research make them better?

That remains the goal of Kevin Jamieson, a graduate student in the UW–Madison College of Engineering who studies in WID’s Optimization research group. Recently, Jamieson hit the whiteboard in efforts to make computer algorithms more quick and efficient.

Let’s say you’re participating in a computer survey designed to learn your tastes and preferences in food choices. Rather than asking everyone taking the survey the same exhaustive list of questions about food, each new question is tailored by your answers to previous questions, skipping over those questions whose answers can be inferred using the information you already provided.

Jamieson’s Ph.D. advisor Robert Nowak, Discovery Fellow and Professor of Electrical and Computer Engineering, has developed a mathematical theory for selecting the best questions. The problem, Jamieson explains, is that the theory requires an exhaustive search over all possible questions, which is extremely computationally intensive.

So much so that it lags even by human standards, especially if the range of choices is expansive (think of data sets that could include all songs or movies in the world). In typical cases, the algorithm can take several seconds to prompt the next question or piece of information. In response, Jamieson developed a new algorithm that is both computationally efficient and proven optimal, fully realizing the potential suggested by Nowak’s theory.

“You don’t want people to be waiting. They need to be able to receive the next question in less than 100 milliseconds,” says Jamieson. “With this algorithm, you are still guaranteed to ask the fewest possible number of questions, but the time it takes to ask the next question is consistent, regardless of data set size.”

Jamieson’s algorithm, with implications for social science experiments and applications that predict preferences in users, has succeeded in solving problems with the fewest number of questions and in the least amount of time.

The research has already proven to be a powerful tool in a pilot psychology experiment as well as in a fun, side project that maps beer preferences.

— Marianne Spoon