Collaborative Research: A Fast Hierarchical Algorithm for Computing High Dimensional Truncated Multivariate Gaussian Probabilities and Expectations

协作研究：计算高维截断多元高斯概率和期望的快速分层算法

• 批准号: 1821171
• 负责人: Yichao Wu
• 金额: $ 10万
• 依托单位: University of Illinois at Chicago
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2018
• 资助国家: 美国
• 起止时间: 2018-08-15 至 2022-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1821171&HistoricalAwards=false
• 关键词: Collaborative; Research; Fast; Hierarchical; Algorithm

The "curse of dimensionality" has severely limited human's capability of handling high-dimensional data in many application domains. However, most useful data in existing human knowledge database has certain compressible features. This project focuses on the mathematical description of these compressible features, and develops a novel hierarchical modeling technique to extract these features from high-dimensional datasets in science and engineering applications and process the compressed information efficiently on a hierarchical tree structure. The investigators will develop fast algorithms for high-dimensional integrations involving a truncated multivariate normal distribution that targets the analysis of medical datasets. The techniques developed from this project will provide the scientific community a very powerful tool to handle high-dimensional datasets and at the same time foster the training of researchers with interdisciplinary knowledge. Multivariate Gaussian distribution is one of the most important continuous distributions in statistics. If some components are restricted to an interval, either finite or semi-finite, it is referred to as the truncated multivariate normal (TMVN) distribution. Many statistical algorithms rely on the evaluations of the probabilities and expectations with respect to a TMVN, especially in the expectation-maximization (EM) type algorithms. Direct computation of the desired expectation is very challenging. A commonly used alternative approach is based on the Monte Carlo simulation by drawing random samples from the corresponding TMVN distribution. However, it is equally challenging to simulate from a TMVN distribution in high dimensional cases. This project will develop new hierarchical algorithms to efficiently compute very high dimensional TMVN probabilities and expectations. The core ideas include the hierarchical data clustering, low-rank and low-dimensional features extraction, and their efficient processing on the hierarchical tree structures. The resulting algorithm can compute the expectations with respect to a class of p-dimensional TMVN distributions in asymptotically optimal O(p) operations in high dimensional cases, which can also be used to tighten the likelihood ratio bound of the target TMVN distribution in the acceptance-rejection method to achieve the highest acceptance probability while avoiding the burn-in period of some competitive algorithms such as the Metropolis-Hastings algorithm. The hierarchical nature of the algorithm allows easy adoption of the recent progress in adaptive, dynamic, and asynchronous runtime systems to efficiently utilize the computing resources at scale. The project provides advanced numerical tools to accelerate the computations and improve the applicability of the EM algorithms to handle large and complex biomedical data, with target applications aimed at improving public health.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.

在许多应用领域，“维数灾难”严重限制了人类处理高维数据的能力。然而，现有的人类知识库中，大多数有用的数据都具有一定的可压缩性。本项目主要研究这些可压缩特征的数学描述，并开发了一种新的分层建模技术，以从科学和工程应用中的高维数据集中提取这些特征，并在分层树结构上有效地处理压缩信息。研究人员将开发涉及截断多元正态分布的高维积分的快速算法，以分析医学数据集。该项目开发的技术将为科学界提供一个非常强大的工具来处理高维数据集，同时促进对具有跨学科知识的研究人员的培训。多元高斯分布是统计学中最重要的连续分布之一。如果某些成分被限制在一个区间内，无论是有限的还是半有限的，它被称为截断多元正态（TMVN）分布。许多统计算法依赖于对TMVN的概率和期望的评估，特别是在期望最大化（EM）类型的算法中。直接计算期望值是非常具有挑战性的。一种常用的替代方法是基于蒙特卡罗模拟，从相应的TMVN分布中抽取随机样本。然而，在高维情况下从TMVN分布进行模拟同样具有挑战性。这个项目将开发新的分层算法来有效地计算非常高维的TMVN概率和期望。其核心思想包括层次数据聚类、低秩低维特征提取及其在层次树结构上的高效处理。该算法可以在高维情形下以渐近最优O（p）运算计算一类p维TMVN分布的期望值，也可以用于收紧接受-拒绝方法中目标TMVN分布的似然比界，以获得最高的接受概率，同时避免了Metropolis-Hastings算法等竞争算法的老化期.该算法的分层性质允许轻松采用自适应，动态和异步运行时系统的最新进展，以有效地利用大规模的计算资源。该项目提供了先进的数值工具，以加速计算并提高EM算法的适用性，以处理大型和复杂的生物医学数据，目标应用旨在改善公共健康。该奖项反映了NSF的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Variable Selection for Global Fréchet Regression

全局 Fréchet 回归的变量选择

• DOI: 10.1080/01621459.2021.1969240
• 发表时间: 2021
• 期刊: Journal of the American Statistical Association
• 影响因子: 3.7
• 作者: Tucker, Danielle C.;Wu, Yichao;Müller, Hans-Georg
• 通讯作者: Müller, Hans-Georg

Tuning parameter selection for penalised empirical likelihood with a diverging number of parameters

• DOI: 10.1080/10485252.2020.1717491
• 发表时间: 2020-01
• 期刊: Journal of Nonparametric Statistics
• 影响因子: 1.2
• 作者: Chaowen Zheng;Yichao Wu

Can’t Ridge Regression Perform Variable Selection?

• DOI: 10.1080/00401706.2020.1791254
• 发表时间: 2020-07
• 期刊: Technometrics
• 影响因子: 2.5
• 作者: Yichao Wu

A modified expectation‐maximization algorithm for latent Gaussian graphical model

潜在高斯图模型的改进期望最大化算法

• DOI: 10.1002/cjs.11643
• 发表时间: 2021
• 期刊: Canadian Journal of Statistics
• 作者: Zheng, Chaowen;Huang, Jingfang;Wood, Ian A.;Wu, Yichao
• 通讯作者: Wu, Yichao

Nonparametric Interaction Selection

非参数交互选择

• DOI: 10.5705/ss.202020.0463
• 发表时间: 2022
• 期刊: Statistica Sinica
• 影响因子: 1.4
• 作者: Dong, Yushen;Wu, Yichao
• 通讯作者: Wu, Yichao