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

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

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.