Stochastic Covering Under Noisy Outcomes

Regents Of The University Of Michigan - Ann Arbor, Ann Arbor MI

Investigators

Abstract

This project will study efficient methods for classifying a system based on outcomes revealed through a series of tests. A common task in medical decision-making is to perform a sequence of diagnostic tests in order to determine an underlying condition as quickly as possible. Tests will reveal partial information about the underlying condition, but may also be subject to error. The goal is to optimize the sequence of tests to minimize cost and time to classification. Similar problems arise in fault detection of complex systems and in threat detection. Noisy or missing data is a major issue in these applications, which often renders traditional models inapplicable. These examples can be modeled as sequential decision trees, and this project will develop methods to study optimal sequential decision trees with noisy outcomes. The specific questions studied in this project are of interest to multiple research communities including operations research, industrial engineering, computer science and machine learning. The educational component of this project involves training graduate and undergraduate students for a career in research, enhancing the curriculum of graduate courses, and outreach programs to high school students designed to broaden participation in STEM. This project will study models and algorithms for stochastic covering problems in the presence of noisy outcomes. Classical models for these problems assume that random outcomes are observed without any noise. This project will consider new models that incorporate noise in the following ways. In the stochastic noise model, the outcomes of certain tests are uncertain with known probability distributions. The stochastic noise can be either non-persistent or persistent, depending on whether observing the same outcome repeatedly results in independent samples. In the adversarial noise model, each noisy outcome instantiates to a value that results in the worst-case objective. A central paradigm in this project is the optimal decision tree, where one needs to identify an unknown random hypothesis using an adaptive sequence of tests. Apart from the noisy optimal decision tree problem, this project will also study noisy versions of stochastic submodular-cover and sequential testing problems. The project will design algorithms with mathematically rigorous performance guarantees. It will also test the empirical performance of the resulting algorithms on synthetic as well as publicly available datasets. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.