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.