Sparse and structured networks: Statistical theory and algorithms

稀疏和结构化网络：统计理论和算法

• 批准号: 1107000
• 负责人: Martin Wainwright
• 金额: $ 42万
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2011
• 资助国家: 美国
• 起止时间: 2011-07-01 至 2015-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1107000&HistoricalAwards=false
• 关键词: Sparse; structured; networks; Statistical; theory

The proposal focuses on Markov random fields and directed graphicalmodels, classes of statistical models that are based on a marriagebetween graph theory and probability theory, and allow for flexiblemodeling of network-structured data. The core of the proposalconsists of multiple research thrusts, all centered around the goal ofdeveloping practical algorithms and theory for statistical estimationwith network-structured data. One research thrust concerns variousissues associated with model selection in undirected graphical models,also known as Gibbs distributions or Markov random fields. Problemsinclude determining the information-theoretic limitations of graphicalmodel selection in high dimensions (where the number of vertices maybe larger than the sample size), not only for i.i.d. data but alsodependent data; developing methods for tracking sequences of networksthat evolve over time; and developing methods for data with hiddenvariables. Another research thrust concerns various statisticalproblems associated with directed acyclic graphical structures (DAGs),including estimating equivalence classes of DAGs in thehigh-dimensional setting; estimating causal relationships via designedinterventions; and efficient computational methods for DAG selectionusing the Lasso and related methods. Overall, the proposed researchis inter-disciplinary in nature, drawing on techniques frommathematical statistics, convex optimization, information theory,concentration of measure, and graph theory.Science and engineering abounds with different types of networks.Examples include social networks such as FaceBook and Twitter,networks of genes and proteins in molecular biology, network modelsfor economic and market dynamics, neural networks in brain imaging,networks of disease transmission in epidemiology, and informationnetworks in law enforcement. In the real-world, the structure of theunderlying network is not known, but instead one observes samples ofthe network behavior (e.g., packet counts in a computer network;instances of infection at given time instances of an epidemic; emailsor text messages sent among a group of people), and the goal is toinfer the network structure. Methods for solving this networkinference problem have a broad range of applications. Examplesinclude inferring brain connectivity and disease etiology inneuroimaging studies, detecting terrorist cells in social networks,monitoring intrusions in computer networks, and understanding thebasis of gene-protein interactions in systems biology.

该提案侧重于马尔可夫随机场和有向图模型，这是基于图论和概率论之间的结合的统计模型的类别，并允许灵活的网络结构化数据建模。该提案的核心由多个研究重点组成，所有研究重点都围绕着开发具有网络结构数据的统计估计的实用算法和理论的目标。一个研究重点涉及与无向图形模型中模型选择相关的各种问题，也称为吉布斯分布或马尔可夫随机场。问题包括确定高维图模型选择的信息论限制（其中顶点的数量可能大于样本量），不仅适用于id数据，也适用于依赖数据；开发跟踪随时间演变的网络序列的方法；开发具有隐藏变量的数据的方法。另一个研究重点是与有向无环图结构（dag）相关的各种统计问题，包括估计高维环境下dag的等价类；通过设计干预评估因果关系；利用Lasso及相关方法进行DAG选择的高效计算方法。总的来说，拟议的研究本质上是跨学科的，利用了数理统计、凸优化、信息论、测度集中和图论等技术。科学和工程中充斥着不同类型的网络。例子包括FaceBook和Twitter等社交网络、分子生物学中的基因和蛋白质网络、经济和市场动态网络模型、脑成像中的神经网络、流行病学中的疾病传播网络以及执法中的信息网络。在现实世界中，底层网络的结构是未知的，而是观察网络行为的样本（例如，计算机网络中的数据包计数；给定时间的感染实例；一群人之间发送的电子邮件或文本消息），目标是推断网络结构。解决这种网络推理问题的方法具有广泛的应用前景。例子包括在神经成像研究中推断大脑连接和疾病病因，在社会网络中检测恐怖分子细胞，监测计算机网络中的入侵，以及在系统生物学中理解基因-蛋白质相互作用的基础。