Collaborative Research: CDS&E: Scalable Inference for Spatio-Temporal Markov Random Fields

众所周知，现代系统是大规模的，具有复杂、动态和未知的拓扑层次结构。例如，在基因组学中，可以通过跨越不同细胞的时空基因调控网络来模拟基因之间的相互作用。时间和空间重新连接的基因表达网络的推断对动态的疾病过程具有巨大的影响，为相互作用的生物过程在空间和时间上的动态变化提供了关键的机械学见解。这种相互关联的系统的行为可以通过时空图形模型来捕获。现有的推断这些模型的方法存在一些统计和计算上的缺陷，这使得它们在现实环境中不切实际。为了弥合这一知识鸿沟，该项目旨在开发有效的计算工具来推断时空图形模型，这些模型不仅可以证明是最优的，而且是自适应的、可并行化的和可在有意义的规模上实现的。本提案中开发的方法将在推断肿瘤发生的基因网络的背景下进行研究。通过这些努力产生的数据集将伴随着发展良好的分析工具，以获得对生物过程背后的基因网络本质的机械性见解。更广泛地说，提出的机制将产生领域专家可以解释的模型，并将产生丰富的公开可用的数据集，这些数据集可以用作不同推理方法的试验台，从而导致更广泛的人工智能(AI)和人类合作。图形模型的推理的大部分进展是基于松弛正则化的最大似然估计(MLE)，这既不能产生理想的统计特性，也不会产生时空环境中遇到的维度的尺度。这个项目将通过背离正则化的MLE范式来解决这些挑战，并求助于一类新的具有组合性质的约束优化问题，该问题可以系统地捕获时空图形模型的隐藏但有用的结构。由于基于最大似然估计的方法极其复杂，它们的实际实现不能同时保证计算效率和良好的统计性能。因此，所提出的方法将是第一个能够以统一的方式实现两全其美的系统推理框架。这类新的估计方法将对统计学习产生深远影响：它将重新引起人们对使用易处理的离散方法及其统计性质的兴趣，并将为发现适用于大维度和时空环境的新推理方法铺平道路。此外，拟议的项目将是对一类目前鲜为人知的离散优化问题的首次系统研究，从而也有助于组合和混合整数社区。鉴于其跨学科性质，该项目还将在很大程度上有助于培养未来几代数据科学研究人员。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Modern systems are known to be massive-scale, with a hierarchy of complex, dynamic, and unknown topologies. For example, in genomics, the interactions among genes can be modeled via spatio-temporal gene regulatory networks across different cells. The inference of temporal and spatially-rewired gene expression networks carries enormous implications for dynamic disease processes, offering key mechanistic insights into the dynamic variations of interacting biological processes in space and time. The behavior of such interconnected systems can be captured via spatio-temporal graphical models. The existing methods for inferring these models suffer from several statistical and computational drawbacks which render them impractical in realistic settings. With the goal of bridging this knowledge gap, this project aims at developing efficient computational tools for the inference of spatio-temporal graphical models that are not only provably optimal, but also adaptive, parallelizable, and implementable in meaningful scales. The methods developed in this proposal will be studied in the context of inferring gene networks underlying oncogenesis. The datasets generated through these efforts will be accompanied with well-developed analytics tools to derive mechanistic insights into the nature of gene-networks underlying biological processes. More broadly, the proposed machinery will give rise to models that are interpretable by domain experts, and will lead to a rich set of publicly-available datasets that can be used as test-bed for different inference methods, resulting in broader artificial intelligence (AI)-human collaborations.Much of the progress in the inference of graphical models is based on the maximum likelihood estimation (MLE) with relaxed regularization, which neither result in ideal statistical properties nor scale to dimensions encountered in spatio-temporal settings. This project will address these challenges by departing from the regularized MLE paradigm, and resorting to a new class of constrained optimization problems with combinatorial nature that can systematically capture the hidden-but-useful structure of the spatio-temporal graphical models. Due to the prohibitively complex nature of the MLE-based methods, their practical implementations cannot simultaneously guarantee computational efficiency and favorable statistical performance. Therefore, the proposed approach will be the first systematic inference framework that can achieve the best of both worlds in a unified fashion. The new class of estimation methods will have a profound impact in statistical learning: it will lead to a renewed interest in the use of tractable discrete approaches and their statistical properties, and will pave the way towards the discovery of new inference methods suitable for the large-dimensional and spatio-temporal settings. In addition, the proposed project will be the first systematic study of a class of discrete optimization problems that are currently poorly understood, thus contributing to the combinatorial and mixed-integer communities as well. Given its interdisciplinary nature, the project will also largely contribute to training of future generations of researchers in data science.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.