Synthesizing Programmatic Knowledge with Heuristic Search

我们最近见证了机器学习系统在决策问题上取得的巨大成就。人工智能（AI）算法在围棋、国际象棋和棋棋上取得了超人的成绩，在《星际争霸》中也取得了不俗的成绩。虽然这些系统能够解决复杂的问题，但生成的解决方案是在黑盒模型（例如，神经网络）中编码的，这导致解决方案难以解释。缺乏可解释性阻碍了这些系统在信任和可靠性很重要的领域中的应用，因为很难预测这些系统在生产中的行为。与在黑箱模型中编码决策问题的解决方案不同，在本研究项目中，我们将开发在人类可读的计算机程序中编码解决方案的算法，因为后者更易于解释和验证，并且被证明可以更好地推广到训练期间未见过的问题。这里的挑战是，人们需要解决困难的组合搜索问题，以便能够在人类可读的程序中编码复杂决策问题的强大解决方案。我们将对决策问题的解决方案进行编码的程序称为程序化知识。我们的长期目标是开发算法来解决组合搜索问题，这些问题出现在可编程知识的合成中，作为获得可解释和健壮的智能系统的一种手段。我们寻求先进的系统来综合程序性知识，最终允许用类似强度的可解释模型取代现有的黑盒模型。在接下来的五年里，我们将重点关注以下目标，这将有助于综合更强的编程知识：开发搜索程序空间表示的算法（目标A）；制定行动抽象以加快综合过程（目标B）；开发用于综合可编程知识（Aim C）的指导搜索算法的评估函数。在这个研究计划中，我们将通过开发新的启发式搜索算法来减少不可解释和可解释的机器生成知识之间的差距。这项研究计划的结果将有助于开发能够与我们有效合作的系统。例如，我们将能够通过合成一个击败程序员编写的程序的程序来发现游戏ai程序员编写的程序中的缺陷。我们的综合程序可以用来指导程序员的弱点，他们的实现。我们开始与当地游戏公司合作，我们的目标是最终将这个项目开发的技术应用到商业产品中。

We have recently witnessed tremendous achievements of machine learning systems in decision-making problems. Artificial intelligence (AI) algorithms achieved superhuman performance on Go, Chess, and Shogi, and strong performance in StarCraft. While these systems are able to solve complex problems, the generated solution is encoded in black-box models (e.g., neural networks), which result in solutions that are hard to interpret. Lack of interpretability hinders the application of these systems in domains where trust and reliability are important, as it can be hard to predict how such systems will act in production. Instead of encoding solutions to decision-making problems in black-box models, in this research program we will develop algorithms for encoding solutions in human-readable computer programs, as the latter are more amenable to interpretation, verification, and were shown to generalize better to problems not seen during training. The challenge here is that one needs to solve hard combinatorial search problems to be able to encode strong solutions to complex decision-making problems in human-readable programs. We refer to programs encoding solutions to decision-making problems as programmatic knowledge. Our long-term objective is to develop algorithms for solving the combinatorial search problems that arise in the synthesis of programmatic knowledge as a means of attaining interpretable and robust intelligent systems. We seek to advance the state-of-the-art of systems for synthesizing programmatic knowledge to eventually allow for the replacement of existing black-box models with interpretable ones of similar strength. In the next five years we will focus the following objectives, which will contribute to the synthesis of stronger programmatic knowledge: develop algorithms that search for program space representations (Aim A); develop action abstractions for speeding up the synthesis process (Aim B); develop evaluation functions for guiding search algorithms for synthesizing programmatic knowledge (Aim C). In this research program we will reduce the gap between non-interpretable and interpretable machine-generated knowledge through the development of novel heuristic search algorithms. The results of this research program will contribute to the development of systems able to collaborate effectively with us. For example, we will be able to find flaws in programs written by game-AI programmers by synthesizing a program that defeats the program written by the programmer. Our synthesized programs could be used to instruct the programmer of the weaknesses of their implementation. We are starting to work with local games companies and our goal is to eventually have the technology developed in this project deployed in commercial products.