Stochastic Covering Under Noisy Outcomes

噪声结果下的随机覆盖

基本信息

批准号：
1940766
负责人：
Viswanath Nagarajan
金额：
$ 37.09万
依托单位：
Regents of the University of Michigan - Ann Arbor
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2020
资助国家：
美国
起止时间：
2020-01-01 至 2023-12-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1940766&HistoricalAwards=false
关键词：
Stochastic Covering Under Noisy Outcomes

项目摘要

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.

该项目将根据通过一系列测试揭示的结果研究有效的方法，用于对系统进行分类。医疗决策中的一个常见任务是执行一系列诊断测试，以便尽快确定潜在的状况。测试将揭示有关潜在条件的部分信息，但也可能出现错误。目的是优化测试顺序，以最大程度地减少成本和分类时间。在检测复杂系统和威胁检测中的故障检测中会出现类似的问题。在这些应用程序中，嘈杂或缺失的数据是一个主要问题，这通常使传统模型无法实现。这些示例可以建模为顺序决策树，该项目将开发出研究具有嘈杂结果的最佳顺序决策树的方法。该项目中研究的具体问题对多个研究社区感兴趣，包括运营研究，工业工程，计算机科学和机器学习。该项目的教育组成部分涉及培训毕业生和本科生从事研究职业，增强研究生课程的课程，并向旨在扩大STEM参与的高中学生提供外展课程。该项目将研究在存在嘈杂结果的情况下涵盖问题的随机性模型和算法。这些问题的经典模型假设观察到随机结果而没有任何噪音。该项目将考虑以以下方式结合噪声的新模型。在随机噪声模型中，某些测试的结果与已知概率分布不确定。随机噪声可能是非持久的或持久性的，具体取决于观察相同结果是否反复导致独立样本。在对抗性噪声模型中，每个嘈杂的结果实例化成导致最差目标的值。该项目中的中央范式是最佳决策树，其中需要使用自适应测试序列来识别未知的随机假设。除了嘈杂的最佳决策树问题外，该项目还将研究随机下覆盖和顺序测试问题的嘈杂版本。该项目将使用数学上严格的性能保证设计算法。它还将测试由合成以及公开可用数据集的由此产生的算法的经验性能。该奖项反映了NSF的法定任务，并且使用基金会的智力优点和更广泛的影响评估标准，认为值得通过评估来支持。