« Back to Stories Archive

Graduate Student Refines Formulas to Optimize How Computers “Think”

Kevin Jamieson hits the whiteboard in efforts to make computer algorithms more quick and efficient.

Photo by M. Spoon / WID

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.

Photo by M. English / WID

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

 

 


Press Contact:

WID Media
608-316-4325

More articles in Archive:

badgerloop vr

Virtual Reality Goes Hyper-speed with Badgerloop

Two students from WID’s Living Environments Laboratory are a part of the Badgerloop team that recently won an innovation award at the SpaceX Hyperloop competition, thanks in part to their work on Badgerloop VR.

Caption This Cartoon

High-tech humor

UW program powers New Yorker contest featuring Rob Nowak and NEXT software

Jo Handelsman at WID

Handelsman Brings Expansive Vision to WID’s Future

Jo Handelsman began her tenure as Director of the Wisconsin Institute for Discovery on February 1. Shortly before her start date, we sat down with her to talk about the future of WID and the course she intends to set.