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

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

基本信息

批准号：
1838251
负责人：
Cristopher Moore
金额：
$ 73.76万
依托单位：
Santa Fe Institute
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2018
资助国家：
美国
起止时间：
2018-10-01 至 2023-09-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1838251&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 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。