AitF: Collaborative Research: Efficient High-Dimensional Integration using Error-Correcting Codes

AitF：协作研究：使用纠错码进行高效高维积分

• 批准号: 1733686
• 负责人: Stefano Ermon
• 金额: $ 36万
• 依托单位: Stanford University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2017
• 资助国家: 美国
• 起止时间: 2017-09-01 至 2021-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1733686&HistoricalAwards=false
• 关键词: AitF; Collaborative; Research; Efficient; Dimensional; AitF; Collaborative; Research; Efficient; Dimensional

Efficiently estimating integrals of high-dimensional functions is a fundamental and largely unsolved computational problem, manifesting in scientific areas from biology and physics to economics. In particular, in Artificial Intelligence and Machine Learning, a wide array of methods are computationally limited precisely because they require the computation of high-dimensional integrals. While computing such integrals exactly is highly intractable, approximations suffice for many applications. Currently, approximation is attempted using two main classes of algorithms: Markov Chain Monte Carlo (MCMC) sampling methods and variational inference techniques. The former are asymptotically accurate, but their computational budget is inflexible and often prohibitive. The latter have manageable computational budget, but typically come with no accuracy guarantees. This project will investigate a new family of computationally efficient approximation methods which reduce the task of integration to the much better studied task of optimization, thus leveraging decades of research and engineering in combinatorial optimization methods and technology. A key goal of the project is to develop an open-source software library of efficient tools for high-dimensional integration.The reduction of integration to optimization builds on the probabilistic reduction of decision problems to uniqueness promise problems developed in the mid-80s. Specifically, the idea is to use systems of random parity equations in order to specify random subsets of the function's domain, and relate integration to the task of optimization over these subsets. In general, the capacity for efficient optimization fundamentally stems from the capacity to summarily dispense large parts of the domain as uninteresting. The key question to be addressed by the project is whether it is possible to define random subsets over which optimization is both tractable and informative for integration. To that end, the project will employ random systems of linear equations corresponding to Low Density Parity Check (LDPC) matrices for error-correcting codes. The energy landscape, i.e., the number of violated equations, of such systems is far smoother than that of the generic (dense) random systems of linear equations that underlie the original mid-80s technique, thus being far more amenable to optimization. The project will also build upon the deep understanding gained in the last two decades for LDPC codes in the field of communications, with the goal of integrating a priori knowledge about the energy landscape in the optimization strategy. This will provide a fundamentally new use for error-correcting codes, creating a bridge between the areas of optimization and information theory.

有效地估算高维功能的积分是一个基本的，并且在很大程度上无法解决的计算问题，在从生物学和物理学到经济学的科学领域表现出来。特别是，在人工智能和机器学习中，各种各样的方法在计算上是限制的，因为它们需要计算高维积分。虽然计算此类积分非常棘手，但对于许多应用来说，近似值就足够了。当前，使用两种主要类别的算法类别尝试近似：马尔可夫链蒙特卡洛（MCMC）采样方法和变异推理技术。前者渐近准确，但是他们的计算预算僵化且通常是过于刺激的。后者具有可管理的计算预算，但通常没有准确的保证。该项目将调查一个新的计算高效近似方法，该方法将整合的任务降低到更好地研究的优化任务，从而利用组合优化方法和技术利用数十年的研究和工程。该项目的一个关键目标是开发一个开源软件库，以高维集成为有效的工具。将集成到优化的集成减少基于将决策问题降低到80年代中期开发的独特性问题的概率。具体而言，这个想法是使用随机平价方程的系统来指定函数域的随机子集，并将集成与对这些子集的优化任务相关联。通常，进行有效优化的能力从根本上源于将域的大部分分配给无趣的能力。该项目要解决的关键问题是是否可以在哪些优化既可以易于又有且有用的集成方式定义随机子集。为此，该项目将采用与低密度奇偶校验检查（LDPC）矩阵相对应的线性方程式的随机系统，以进行错误校正代码。这种系统的能量格局，即违反方程的数量，远比原始80年代中期技术的线性方程的通用（密集）随机系统的范围更加顺畅，因此可以优化得多。该项目还将建立在过去二十年来对通信领域的LDPC代码中获得的深刻理解的基础，其目的是将有关能源景观的先验知识纳入优化策略。这将提供从根本上为错误校正代码提供新的用途，从而在优化和信息理论领域之间建立桥梁。