IBM Research       


IBM Research - Finding a model for ill-posed problems

Open Collaborative Research

An IBM Research collaboration with the University of British Columbia homes in on solving problems based on scant but reasonable information.

lior horesh The doorbell rings. You peer through the peephole, but all you can see is a section of porch and the street behind it. This scenario -- and any other where you have limited ability to “see around the corners” -- is familiar to computer scientists and mathematicians who want to solve “ill-posed problems.”

Such problems have long presented a challenge to oil drillers, for example, who can see into a subsurface reservoir wherever a well has been drilled, but can only infer what’s going on between wells. A neurosurgeon experiences a comparable problem when she tries to locate some unusual activity or lesion in an individual’s brain -- and cannot, for obvious reasons, slice through the brain to establish where exactly the surgery must be done.

In all types of partially observable cases, researchers are beginning to consider incorporating design into this process of inference, or “inversion.” This can mean defining an optimal paradigm for data collection or it can mean designing a methodology that factors in prior known information. The goal in either case is to obtain more reasonable inferred but concrete knowledge about the object under consideration – before taking action.

Developing optimal experimental design for ill-posed problems

Lior Horesh (pictured above), a mathematician in the optimization and numerical analysis group at IBM Research, is among a relatively small number of researchers who are developing methodologies for solving design inversion problems. Such designs allow for making informed decisions about a broad variety of drilling and tomographic (x-ray-related) activities, and generally offer improved procedures for collecting information that is not directly observable. Under the auspices of IBM Open Collaborative Research (OCR), an open source project between IBM Research and universities around the world, Horesh is working with Eldad Haber at the University of British Columbia to develop optimal experimental design for a swath of ill-posed problems in biomedical and geophysical imaging.

As it turns out, these problems may not be as insurmountable as they appeared to be in 2006, when experts in experimental design believed that design inversion was not possible. Indeed, before Horesh and his collaborators began their work, few published papers addressed design for ill-posed problems. And none offered an approach that could be scaled up to solve complex real-life problems.

“We proved them wrong,” Horesh says. “And we did that counter-intuitively by complying with some restrictions and preferences.”

The restrictions in design inversion might involve safety or speed of data acquisition, to name just two. Moreover, the design would be circumscribed by taking into account a priori information about the specific model or environment under study.

“I know, for example, that the ground surrounding an oil field might contain oil or water or rocks, and that each of these has a specific physical and chemical make-up,” Horesh says. “I know it won’t look like a Mickey Mouse face. So imposing restrictions on the experiment helps me eliminate incorrect and even absurd solutions.”

Learning to quantify uncertainty

Gradually, researchers can introduce more and more constraining information so they ideally will arrive at a single best solution -- or at least quantify uncertainty more rigorously. Ultimately, depending on how and how much data is collected, and depending on financial, operational and safety-related considerations, researchers can start to prescribe optimal data acquisition procedures. Of course, no single design can accommodate all preferences -- a limitation that actually gives decision-markers and designers greater control over the desired output.

Horesh observes that the OCR has provided a generous framework for conducting research into ill posed problems. He has been able to work formally with Eldad Haber, whom he met in 2005 at a Cirencester, U.K. conference on applied inverse problems. The program also lets him focus on the research itself and entrust the intellectual property issues to the lawyers. Best of all, he was able to attract a matching grant from Mathematics of Information Technology and Complex Systems (MITACS), a Canadian not-for-profit that connects companies with top Canadian and international researchers.

Horesh says that design inversion will become increasingly applicable to many ill posed real-world problems. In addition to oil drilling and brain tomography, weather forecasting lends itself to this kind of research. Through the Smarter Planet Initiative, researchers already can collect some data from satellites, some from ground stations. Additional sources of information continue to proliferate.

“But all of the data are sparse,” Horesh says. “Where should you be collecting more information to get a better weather forecast? And how do you knit all this information together?”

Horesh and his OCR colleagues will continue to “peer through the peephole,” incorporate meaningful a priori information, gather data in an optimal way -- and find the most reliable solutions for problems that beset us in our everyday lives.

For more information about Open Collaborative Research, contact Steve Lavenberg, associate director, computer science, IBM Research.

Last updated on September 8, 2011.