CRII: RI: Inference for Probabilistic Programs: A Symbolic Approach

CRII：RI：概率程序的推理：符号方法

• 批准号: 1657613
• 负责人: Guy Van den Broeck
• 金额: $ 17.46万
• 依托单位: University of California-Los Angeles
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2017
• 资助国家: 美国
• 起止时间: 2017-03-01 至 2019-02-28
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1657613&HistoricalAwards=false
• 关键词: CRII; RI; Inference; Probabilistic; Programs

Probabilistic machine learning and artificial intelligence have revolutionized the world and are present in most aspects of our life. However, the tools used to develop probabilistic machine learning solutions are limited in what they can express. Moreover, they require significant expert knowledge, and are not accessible to scientists in each discipline, let alone everybody else. Probabilistic programming aims to make probabilistic machine learning accessible to all, and as easy to program as a phone application. To make this dream a reality, probabilistic program execution, making probabilistic predictions from observations, has to become as highly efficient and robust as our current non-probabilistic software tools. This project develops general-purpose algorithms to execute probabilistic programs efficiently, using advanced symbolic reasoning techniques from artificial intelligence. Moreover, it does so for probabilistic programs that are significantly more complex than the ones in use today, involving a wide range of programming language features that are both discrete and continuous. This increase in scalability and expressive power will foster novel, increasingly advanced machine learning applications. More specifically, probabilistic programs subsume classical probabilistic graphical models and are additionally able to capture complex probabilistic dependencies that include arbitrary pieces of executable code. While many expressive probabilistic programming languages have been proposed in recent years, the current bottleneck and barrier to success is the lack of general-purpose reasoning algorithms to perform inference with probabilistic programs efficiently. This research tackles two key problems in probabilistic program inference. First, current sampling-based algorithms have problems reasoning about dependencies between large numbers of discrete random variables and explaining low-probability observations. In one thrust, this project develops new inference algorithms based on knowledge compilation. This technique compiles the program into a symbolic structure that is efficient for probability computation. The algorithm does not compile the entire program, which is generally intractable, but uses importance sampling on partially compiled programs to sample efficient subprograms. This combines the best of approximate program evaluation by sampling with highly efficient compilation techniques for exact inference. Second, symbolic approaches to inference are fundamentally discrete and have problems dealing with continuous and integer variables, which frequently appear in real code. Conversely, algorithms for continuous distributions cannot efficiently handle discrete program structure. In another thrust, this project studies symbolic approaches to probabilistic reasoning in programs with both types of structure, using recent breakthroughs based on satisfiability modulo theories and hashing-based sampling. This project provides a scientific leap at a fundamental level. It also provides a context for training undergraduate and graduate students in subjects spanning machine learning, artificial intelligence, statistics, and programming languages, and targets the integration of probabilistic programming into computer science curricula.

概率机器学习和人工智能已经彻底改变了世界，并存在于我们生活的大多数方面。然而，用于开发概率机器学习解决方案的工具的表达能力有限。此外，它们需要大量的专业知识，并且每个学科的科学家都无法接触到它们，更不用说其他人了。概率编程旨在让所有人都能使用概率机器学习，并且像手机应用程序一样易于编程。为了使这个梦想成为现实，概率程序执行，根据观察进行概率预测，必须变得像我们当前的非概率软件工具一样高效和强大。该项目使用人工智能的先进符号推理技术，开发通用算法来高效执行概率程序。此外，它适用于比当今使用的程序复杂得多的概率程序，涉及广泛的离散和连续的编程语言功能。可扩展性和表达能力的增强将促进新颖、日益先进的机器学习应用程序。更具体地说，概率程序包含经典的概率图形模型，并且还能够捕获包括任意可执行代码片段的复杂概率依赖性。尽管近年来提出了许多表达性概率编程语言，但当前的瓶颈和成功的障碍是缺乏通用推理算法来有效地使用概率程序进行推理。这项研究解决了概率程序推理中的两个关键问题。首先，当前基于采样的算法在推理大量离散随机变量之间的依赖性和解释低概率观测值时存在问题。一方面，该项目开发了基于知识编译的新推理算法。该技术将程序编译成对概率计算有效的符号结构。该算法不会编译整个程序，这通常很难处理，而是对部分编译的程序使用重要性采样来采样有效的子程序。这结合了通过采样进行的最佳近似程序评估与用于精确推理的高效编译技术。其次，符号推理方法本质上是离散的，并且在处理连续变量和整数变量时存在问题，而这些变量经常出现在实际代码中。相反，连续分布算法无法有效处理离散程序结构。在另一个主旨中，该项目利用基于可满足性模理论和基于哈希的采样的最新突破，研究具有两种结构类型的程序中概率推理的符号方法。该项目实现了基础层面的科学飞跃。它还为本科生和研究生提供机器学习、人工智能、统计和编程语言等学科的培训环境，并致力于将概率编程整合到计算机科学课程中。

项目成果

Optimal Feature Selection for Decision Robustness in Bayesian Networks

• DOI: 10.24963/ijcai.2017/215
• 发表时间: 2017-08
• 作者: YooJung Choi;Adnan Darwiche;Guy Van den Broeck

What to Expect of Classifiers? Reasoning about Logistic Regression with Missing Features

• DOI: 10.24963/ijcai.2019/377
• 发表时间: 2019-03
• 期刊: ArXiv
• 作者: Pasha Khosravi;Yitao Liang;YooJung Choi;Guy Van den Broeck

Learning the Structure of Probabilistic Sentential Decision Diagrams

学习概率句子决策图的结构

• 发表时间: 2017
• 期刊: Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence (UAI
• 作者: Liang, Yitao;Bekker, Jessa;Van den Broeck, Guy
• 通讯作者: Van den Broeck, Guy

Sound Abstraction and Decomposition of Probabilistic Programs

概率程序的合理抽象和分解

• 发表时间: 2018
• 期刊: Proceedings of the 35th International Conference on Machine Learning (ICML
• 作者: Holtzen, S.;Van den Broeck, G.;Millstein, T.
• 通讯作者: Millstein, T.

Coded machine learning: Joint informed replication and learning for linear regression

编码机器学习：线性回归的联合知情复制和学习

• DOI: 10.1109/allerton.2017.8262880
• 发表时间: 2017
• 期刊: and Computing (Allerton
• 作者: Kabir, Shahroze;Sala, Frederic;Van den Broeck, Guy;Dolecek, Lara
• 通讯作者: Dolecek, Lara