权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。