Synthesizing Programmatic Knowledge with 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.