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

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