Agent problem solving by inductive and deductive program synthesis

How do people learn abstract concepts unsupervised? Psychologists broadly recognize two types of concepts, declarative knowledge and procedural knowledge: know-what and know-how. While much work has focused on unsupervised learning of declara-tive concepts as clusters of features, there is much less clarity on the representation for procedural concepts and the methods for learning them. In this thesis, I claim that programs are a good representation for procedural knowledge, and that program synthesis is a promising mechanism for procedural learning. Prior attempts at AI pro-gram synthesis have taken a purely deductive approach to building provably corrent programs. This approach requires many axioms and non-trivial interaction with a human programmer. In contrast, this thesis introduces a new approach called SSGP (Sample Solve Generalize Prove), which combines inductive and deductive synthesis to autonomously synthesize programs with no extra knowledge outside of the program specification. The approach is to generate examples, solve the examples, generalize from the solutions, and then prove the generalization correct