David Williams Finds Solutions by Minding what's Missing

March 14, 2006

Solving many real-world problems -- from land mine detection to medical diagnosis -- requires careful consideration of what’s missing, according to Ph.D. candidate David Williams, who also completed his undergraduate work at Duke.

“My research falls at the intersection of computer science and statistics,” said the Shavertown, Pa. native, who works with William H. Younger professor Larry Carin in the electrical and computer engineering (ECE) department. “I focus on incomplete or missing data problems, where the main goal is improving classification.”

Land Mines and Medicine

Problems of classification – the process of systematically grouping items into categories based on common characteristics -- crop up all over, Williams said. In landmine detection, for example, people often deploy a single sensor to differentiate hidden explosives from clutter. Different types of radar or infrared sensors are flown over the land on aircraft to produce images of what is, from the surface, invisible.

The method has fundamental limitations, he said, because a single type of sensor cannot capture all the information needed. Even when multiple sensors gather data, each invariably winds up taking somewhat different flight paths due to their practical limitations.

Many of the sensors can only be mounted on certain types of planes, Williams explained. They can also be incredibly heavy -- a factor that also prevents the deployment of multiple sensors on a single aircraft. In any practical situation, some information is missing, said Williams.

The computer algorithms, built by Williams in collaboration with about a half dozen other graduate students and post-docs in the Carin lab, offer a unifying framework to optimally piece together the physical information drawn from different sensors, offering a more accurate picture of the location of land mines.

That initial line of inquiry led Williams to a different, but related problem: how best to deploy landmine sensors given limited resources – determining which sensors to use and where to send them, for instance. One such problem-solving method they developed for optimizing the search for unexploded ordnance (UXO) – military materials including ammunition and explosives -- won a Department of Defense Cleanup Project of the Year award in 2005, Williams said.

More than 1,400 military sites are suspected to contain explosives and propellants from munitions that have been armed and fired and remain unexploded through malfunction, making accurate, cost-effective UXO detection essential, according to the Department of Defense. The Carin team’s method is now being tested and is expected to be used in the cleanup of hundreds of UXO sites in the coming years.

The algorithms developed by the team are also wending their way into other arenas, including medicine, he added. “In medical diagnosis, physicians have to identify a patient’s illness after running tests – but they don’t administer every test available. Some information is missing.”

Such algorithms could also help physicians decide which medical tests to run in the first place. For example, their method could quantify the expected benefit to any given test, he said, potentially allowing doctors and their patients to better weigh the diagnostic advantages of a procedure against its costs.

Although the utility of the team’s methods have not yet been tested with patients’ real medical information, Williams said he hopes to tackle that soon.

A Passion for Math

Williams admits that his research preoccupies him constantly and, now in his final year at Duke, he finds little free time anymore for disc golf or bowling, two of his favorite pastimes.

“I like to challenge myself,” he said. “It can be stressful, but it’s also rewarding to develop something or solve a problem.”

Williams likes to keep his work focused on “real applications.” Still it’s the process of finding solutions for problems with no set answer that he most relishes. And one of his real passions has always been mathematics.

In high school, it was his talent for math and science that led others to suggest that he should try engineering. “It was the typical response,” he said, but he didn’t have a good idea of what exactly an engineering career would entail. He pursued it anyway, choosing Duke’s Pratt School over MIT because of its generally dynamic and interdisciplinary atmosphere.

A couple years in, he came close to switching to a math major. It was Carin and a class on electromagnetic fields that convinced him otherwise, he said.

“I decided for sure to stick with engineering after my junior year,” he said. “I took a class from my current advisor, Larry Carin. It was more his teaching than the subject. He really conveyed the ideas and concepts well and the elegance of the math was very appealing.”

On Track

When presented with the opportunity to continue working with Carin as a graduate student, Williams couldn’t pass it up. Now in his eighth year at Duke, he plans to complete his Ph.D. dissertation in spring 2006. He is applying for faculty positions and wants to continue on a similar research track.

“I have ideas for extending the work I’ve already done,” he said. “It has wide applicability, so there are lots of directions I can move in.”