Stochastic Covering Under Noisy Outcomes

该项目将研究基于一系列测试结果对系统进行分类的有效方法。医疗决策中的一项常见任务是执行一系列诊断测试，以便尽快确定潜在的疾病。测试将揭示有关潜在状况的部分信息，但也可能出现错误。目标是优化测试的顺序，以最小化分类的成本和时间。在复杂系统的故障检测和威胁检测中也会出现类似的问题。噪声或丢失数据是这些应用程序中的主要问题，这通常使传统模型不适用。这些例子可以建模为顺序决策树，本项目将开发具有噪声结果的最优顺序决策树的研究方法。该项目研究的具体问题引起了多个研究界的兴趣，包括运筹学、工业工程、计算机科学和机器学习。该项目的教育部分包括培训研究生和本科生从事研究工作，加强研究生课程的课程设置，以及旨在扩大STEM参与的高中生外展计划。本项目将研究存在噪声结果的随机覆盖问题的模型和算法。这些问题的经典模型假设在没有任何噪声的情况下观察到随机结果。本项目将考虑以以下方式纳入噪声的新模型。在随机噪声模型中，某些试验的结果在已知的概率分布下是不确定的。随机噪声可以是非持续的，也可以是持续的，这取决于是否在独立的样本中反复观察相同的结果。在对抗噪声模型中，每个噪声结果实例化到一个最坏情况目标的值。这个项目的中心范例是最优决策树，其中需要使用自适应测试序列来识别未知的随机假设。除了有噪声的最优决策树问题外，本项目还将研究随机子模覆盖和序列测试问题的有噪声版本。该项目将设计具有数学上严格性能保证的算法。它还将测试结果算法在合成和公开可用数据集上的经验性能。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.