Synthesizing Programmatic Knowledge with Heuristic Search

通过启发式搜索综合程序化知识

• 批准号: RGPIN-2021-02886
• 负责人: SantanadeLelis, Levi
• 金额: $ 1.75万
• 依托单位: University of Alberta
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=750518
• 关键词: Synthesizing; Programmatic; Knowledge; Heuristic; Search

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.

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