CIF: Medium: Collaborative Research: Learning in Networks: Performance Limits and Algorithms

CIF：媒介：协作研究：网络学习：性能限制和算法

基本信息

批准号：
1900636
负责人：
Bruce Hajek
金额：
$ 54.64万
依托单位：
University of Illinois at Urbana-Champaign
依托单位国家：
美国
项目类别：
Continuing Grant
财政年份：
2019
资助国家：
美国
起止时间：
2019-07-01 至 2025-06-30
项目状态：
未结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1900636&HistoricalAwards=false
关键词：
CIF Medium Collaborative Research Learning

项目摘要

Many machine learning problems deal with networks that encode similarities or relationships among different objects, for which observational data may be limited in extent and noisy. Learning the desired information requires highly efficient algorithms that can process large-scale network data and detect tenuous statistical signatures. This project involves modeling large-scale networks and observations, devising learning algorithms, analyzing the performance of the algorithms, deriving bounds on the possible performance of best algorithms, and deploying theoretically-grounded algorithms to real network data. The research aims to significantly advance the theoretical and algorithmic understanding of graphical inference and provide key enabling technologies for high-impact applications such as ordering of short DNA sub-sequences for genetic sequencing. Improvements in the ability to sequence DNA can accelerate the use of genomics with applications in health care. The associated mechanisms for broadening participation in computing include: (a) Explorations in computing and statistics for K-12 with broad participation; (b) Career and life skills guidance for graduate students at the Annual Allerton Conference on Communications, Control, and Computing; and (c) Mentoring female and minority students in research.The research is grouped into four interrelated areas, ranging from inference problems for single graphs, to inference involving two graphs, in order to study classification of graphs from general families: (a) learning community structure in dynamic graphs with heavy-tailed degree distribution, specifically, in a new variation of the Barabasi-Albert preferential attachment model; (b) recovering graphical structures beyond communities, including but not limited to recovery of hidden Hamiltonian cycles arising in a genetic sequencing problem and hidden matchings in bipartite graphs arising in a particle tracking problem; (c) matching two graphs to each other by identifying vertex correspondences, in particular, matching of perturbed versions of Erdos-Renyi random graphs and Barabasi-Albert preferential attachment graphs; and (d) learning properties of graphs using sampling, including sampling along random walks on graphs. Computationally efficient algorithms that estimate the number of both local structures (e.g., edges and triangles) and global structures are designed. Network dynamics and subsampling, as well as inference of network structures that are not necessarily low rank or static, are addressed by employing techniques ranging from information theory, message passing, spectral and non-convex methods, and convex methods including linear, quadratic, and semi-definite relaxations.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.

许多机器学习问题涉及对不同对象之间的相似性或关系进行编码的网络，而这些对象的观测数据可能在范围上受到限制并且存在噪声。学习所需的信息需要高效的算法，该算法可以处理大规模网络数据并检测脆弱的统计特征。该项目涉及对大规模网络和观测进行建模、设计学习算法、分析算法的性能、推导最佳算法可能性能的界限，以及将基于理论的算法部署到真实的网络数据。该研究旨在显着推进对图形推理的理论和算法理解，并为高影响力的应用提供关键的支持技术，例如用于基因测序的短 DNA 子序列的排序。 DNA 测序能力的提高可以加速基因组学在医疗保健领域的应用。扩大计算参与的相关机制包括： (a) 广泛参与的 K-12 计算和统计探索； (b) 在年度阿勒顿通信、控制和计算会议上为研究生提供职业和生活技能指导； (c) 指导女性和少数族裔学生进行研究。该研究分为四个相互关联的领域，从单个图的推理问题到涉及两个图的推理，以研究一般家庭的图的分类： (a) 学习具有重尾度分布的动态图中的群落结构，特别是 Barabasi-Albert 优先依恋模型的新变体； (b) 恢复群落之外的图形结构，包括但不限于恢复基因测序问题中出现的隐藏哈密顿循环以及粒子跟踪问题中出现的二分图中的隐藏匹配； (c) 通过识别顶点对应关系将两个图相互匹配，特别是 Erdos-Renyi 随机图和 Barabasi-Albert 优先附着图的扰动版本的匹配； (d) 使用采样来学习图的属性，包括沿图上的随机游走进行采样。设计了估计局部结构（例如边和三角形）和全局结构的数量的计算有效的算法。网络动态和子采样，以及不一定是低秩或静态的网络结构的推理，通过采用信息论、消息传递、谱和非凸方法以及包括线性、二次和等式在内的凸方法等技术来解决。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。