Collaborative Research: FMitF: Track I: Differentiable Probabilistic Programming with Recursive Structured Models

符号（如字母表中的字母）和结构（如由字母组成的单词）对人类来说是很自然的：它们在日常生活中无处不在，我们很容易理解，并且很容易编写与它们一起工作的程序。但目前的人工智能（AI）系统通过做出许多微小的改变来学习，看看哪些改变能提高系统的性能；因此，他们擅长处理允许微小变化的表征，比如数字，而不擅长处理符号和结构，比如字母和单词。这可能会成为构建AI系统和理解其工作原理的障碍。人工智能系统学习处理符号和结构的典型方法是考虑所有选择，并对其概率做出微小的改变。但如果不是26个选项，而是26万亿呢？例如，一个句子的语法结构可以用一个树来表示，一个树是大量甚至无限可能的树中的一个。在这种情况下——这是普遍现象，而不是例外——人们可以采取近似方法，比如随机选择几千种可能性，或者可以使用精心构建的算法来考虑所有可能性。但要做到后者并不容易，甚至不知道什么时候是可能的。这个项目的新颖之处在于开发了一种新的编程框架，使编写这样的算法变得容易，这样编写一个学习使用树的程序就可以像编写一个使用树的程序一样容易。如果成功，该项目的影响是帮助机器学习成为计算机编程的日常组成部分，不仅对研究人员，甚至对初学者也是如此。该项目借鉴并贡献了机器学习、编程语言和形式语言理论领域。在机器学习中，人们对神经网络越来越感兴趣，神经网络可以对离散结构（如代表句子可能语法结构的树）做出概率决策。在程序设计语言的研究中，有很多关于概率程序和精确保存意义的运算的工作。然而，在现有的神经网络和概率程序框架中，仍然难以准确地表示递归结构上的分布并有效地对其进行微分等操作。本项目使用了形式语言理论的思想来弥合这一差距，使在这些发行版上准确有效地工作变得容易。该项目有三个阶段：首先，扩展和向量化概率规划上的精确变换，使它们适用于由可微张量参数化的规划。其次，该项目使用超边缘替换图语法（hyperedge replacement graph grammars, hrg）来表示递归结构上的分布。hrg概括了图形模型和字符串/树自动机，为结构化模型提供了一种高度表达的形式。对hrg进行有效推断的方法也正在开发中。第三，团队正在将使用递归数据结构的概率代码自动转换为hrg。开发的技术正在一个开源的深度学习框架中实施。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Symbols (like the letters of the alphabet) and structures (like words formed out of letters) are natural for humans to work with: they are ubiquitous in daily life, they are easy for us to understand, and it is easy to write programs that work with them. But current artificial intelligence (AI) systems learn by making many small changes to see which ones improve the performance of the system; they are therefore good at working with representations that allow small changes, like numbers, and not so good with symbols and structures, like letters and words. This can be an obstacle both to building AI systems and to understanding why they work. A typical way for an AI system to learn to work with symbols and structures is to consider all choices and make small changes to their probabilities. But what if there are not 26 choices, but 26 trillion? For example, the grammatical structure of a sentence can be represented by a tree, one out of a large or even infinite number of possible trees. In such cases -- which are the rule rather than the exception -- one can resort to approximations, like randomly selecting a few thousand possibilities, or one can use carefully constructed algorithms to consider all of them. But it is not easy to do the latter or even to know when it is possible. This project's novelty is to develop a new programming framework to make it easy to code such algorithms, so that writing a program that learns to use trees can be as easy as writing a program that uses trees. If successful, the project's impact is to help make machine learning an everyday part of computer programming, not only for researchers but even for beginners.This project draws on and contributes to the fields of machine learning, programming languages, and formal language theory. In machine learning, there is growing interest in neural networks that make probabilistic decisions about discrete structures such as trees that represent the possible grammatical structures of a sentence. In programming language research, there has been much work on probabilistic programs and operations on them that preserve meaning exactly. However, in existing frameworks for both neural networks and probabilistic programs, it is still difficult to represent distributions over recursive structures exactly and to efficiently perform operations on them like differentiation. This project uses ideas from formal language theory to bridge this gap, making it easy to work on these distributions exactly and efficiently. The project has three stages: First, it is extending and vectorizing exact transformations on probabilistic programs so that they work on programs parameterized by differentiable tensors. Second, the project is using hyperedge replacement graph grammars (HRGs) to represent distributions over recursive structures. HRGs generalize both graphical models and string/tree automata, providing a single highly expressive formalism for structured models. Methods for efficient inference on HRGs are also being developed. Third, the team is automating the translation of probabilistic code that uses recursive data structures into HRGs. The techniques developed are being implemented in an open-source deep-learning framework.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.