EAGER: Algorithms for Analyzing Faulty Data Using Domain Information

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

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.