EAGER: Algorithms for Analyzing Faulty Data Using Domain Information

这个项目的重点是建立一个数学理论，通过利用关于创建数据的过程以及错误模型的领域知识来分析包含错误的大型数据。该项目包含三个推力，从定义最明确到最具探索性。第一个推力涉及分析基因组数据，以调查导致癌症发展的肿瘤进化树。第二种方法是分析计算机网络产生的故障数据，同时利用网络的拓扑结构和延迟模式等信息。第三是探索前两次推力开发的技术适用的其他领域，朝着开发通用技术的目标取得进展，以便在缺乏已知地面真相的情况下使用域信息来分析错误数据。在本项目假设的模型中，输入包含根据未知位置的已知分布以概率方式生成的错误。研究人员想要探索的目标是创造采样技术，这种技术不会盲目地从令人望而却步的大空间中随机采样，而是使用有关限制可能导致噪声输入的空间的限制的知识，并分析这个小得多的空间。特别是，该项目的第一个重点是探索如何利用这些信息来生成有效的采样技术，以便推断肿瘤进展树的属性，并随后推断更一般的系统发育树。本项目的后续部分涉及将此知识应用于具有基础结构良好的图表的路由图表和其他数据。由于这些技术依赖于输入背后的图论假设，所有三项努力的目标都是开发广泛适用的概率技术，帮助人们分析噪声图形信息，推动现有的理论知识，并使更好地理解具有强大理论基础的应用领域。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

The focus of this project is the building of a mathematical theory for analyzing large data that contains errors by taking advantage of domain knowledge regarding the processes that have created the data, as well as the error model. The project contains three thrusts, listed from the most well-defined to the most exploratory. The first thrust involves analyzing genomic data in order to investigate tumor evolution trees that lead to the development of cancer. The second involves analyzing faulty data generated by computer networks while utilizing information about the network such as its topology and delay pattern. The third is exploring other areas for which the techniques developed for the first two thrusts apply, making progress towards the goal of developing general techniques for analyzing faulty data in the absence of a known ground truth using domain information.In the model that this project assumes, the input contains errors that have been probabilistically generated according to a known distribution in unknown locations. The goal that the investigator would like to explore is the creation of sampling techniques that do not blindly take random samples from the prohibitively large space for the ground truth; rather, it is to use the knowledge about restrictions that limit the possible space that could have led to the noisy input and analyze this much smaller space. In particular, the first focus of this project is to explore how such information can be used to generate efficient sampling techniques in order to infer properties of tumor progression trees, and, later on, more general phylogenetic trees. Later parts of this project involve applying this knowledge to routing graphs and other data with underlying well-structured graphs. Since such techniques rely on graph-theoretic assumptions underlying the inputs, the goal for all three thrusts is to develop widely applicable probabilistic techniques that will help one analyze noisy graph information in general, pushing existing theoretical knowledge forward, as well as bringing a better understanding to applied areas with strong theoretical underpinnings.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.