BIGDATA: F: Collaborative Research: Mining for Patterns in Graphs and High-Dimensional Data: Achieving the Limits

大数据：F：协作研究：挖掘图形和高维数据中的模式：实现极限

基本信息

批准号：
1838124
负责人：
Jiaming Xu
金额：
$ 34.52万
依托单位：
Purdue University
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2018
资助国家：
美国
起止时间：
2018-10-01 至 2019-08-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1838124&HistoricalAwards=false
关键词：
BIGDATA Collaborative Research Mining Patterns

项目摘要

While modern datasets are very large, the amount of information per variable is often relatively small. This includes datasets from genomics, social networks, and many applications in machine learning and artificial intelligence. For instance, in genomics we often track hundreds of thousands of genes, but only have a few hundred independent samples for each one. Similarly, online social networks are massive, but the structure of friendships only gives us a relatively small amount of data per individual. This kind of data is called "high-dimensional", and poses new challenges for mathematics, statistics, and computer science, especially when (as with all real data) they are noisy or incomplete. This project will identify exactly when and how it is mathematically possible to find patterns in these massive but noisy datasets, giving scientists across many fields a useful guide to how much data they need to draw reliable conclusions, and to develop new algorithms that will solve modern data science problems efficiently and optimally.Through the study of community detection, noisy graph isomorphism, and matrix/tensor factorization, this project will develop a general framework to 1) locate the information-theoretic limit below which the observation is too noisy to detect the underlying pattern, or even to tell if a pattern exists; 2) devise efficient algorithms that succeed all the way down to the lowest possible signal-to-noise ratio; 3) prove that important classes of algorithms need super-polynomial time in certain hard regimes.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.

尽管现代数据集很大，但每个变量的信息量通常相对较小。这包括来自基因组学，社交网络以及机器学习和人工智能中许多应用的数据集。例如，在基因组学中，我们经常跟踪数十万个基因，但每个基因只有几百个独立样本。同样，在线社交网络是巨大的，但是友谊的结构只为我们每个人提供了相对较少的数据。这种数据称为“高维”，并对数学，统计和计算机科学提出了新的挑战，尤其是在（与所有真实数据一样）它们嘈杂或不完整时。该项目将确切地确定在数学上何时以及如何在这些庞大但嘈杂的数据集中找到模式，为许多领域的科学家提供了一个有用的指南，以指出他们需要多少数据来得出可靠的结论，并开发新的算法，以有效地和最佳地解决现代数据科学问题。 1）找到信息理论极限，在该限制下观察到太嘈杂，无法检测到基本模式，甚至可以判断是否存在模式； 2）设计有效的算法，这些算法一直成功地至最低的信噪比； 3）证明，重要的类算法需要在某些硬性制度中进行超级顺序的时间。该奖项反映了NSF的法定任务，并且使用基金会的知识分子优点和更广泛的审查标准，认为值得通过评估来获得支持。