Title: Automatic Generation of Procedural Knowledge Using Program Synthesis
Advisors: Zoran Popovic and Emina Torlak
Supervisory Committee: Zoran Popovic (Co-Chair), Emina Torlak (Co-Chair), Amy Ko (GSR, iSchool), Steve Tanimoto
Abstract: Computer-aided tools have revolutionized the way people approach design problems, such as computer-aided drafting for industrial design. Computers help designers by taking care of rote tasks and computation, freeing designers' time and brainpower to focus on the challenging aspects of problems that cannot be automated. This thesis focuses on using computers to aid in design tasks involving models of human expertise and learning in problem domains such as high school mathematics or puzzles.
Educational technology that models the problem-solving process of a learning domain—called the domain model—powers many promising and proven-effective applications such as generating problems, providing student feedback, or estimating student understanding. Creating domain models is an integral part of such applications and is a challenging and time-consuming process, requiring expertise in both the learning domain and artificial intelligence. Domain models also have applications in fields such as game design: for example, understanding how puzzles and problems must be solved enables automatic game generation or analysis. All of these applications require first completing the challenging design task of creating a domain model.
To aid in this process, we turn to computers, and in particular formal methods, to help automatically learn domain models. Unlike typical machine learning tasks, the primary goal of this endeavor is not to solve domain problems automatically, but to get an interpretable description of how to solve problems. To support this goal, we use program synthesis. For the domains on which we focus, the domain model takes the form of a set of procedural rules for problem solving, such as the rules used to solve algebra equations. We model procedural knowledge as programs in a domain-specific language (DSL) of rules. Then we use program synthesis to automatically generate these programs. Our approach of using program synthesis for automated rule learning turns the typical use of programming languages on its head; rather than using a programming language as a vehicle for a human to give formal instruction to a computer, we're using a programming language as a vehicle for a computer to give formal instruction to humans.
In this thesis, we present a framework, RuleSy, for automatically learning domain models, instantiated for two separate domains. We present results showing that the rules generated by RuleSy are comparable to or better than human-designed rules. We additionally present two novel applications built on top of domain models: first, a mixed-initiative interface for generating puzzle progressions in an educational game, and second, an algorithm for automatically generating entire game progressions. Lastly, we present results from a case study in which participants design the DSL for use in RuleSy. We describe the challenges and difficulties participants encounter in this process, suggesting future avenues of research to make creating program synthesis tools such as RuleSy easier and accessible to a broad range of programmers.