Program Synthesis: A Hierarchical Nonparametric Bayesian Approach
Speaker: Percy Liang , UC Berkeley
In this talk, we focus on the problem of inferring computer programs from their behavior on one or two training examples. A single program is likely to be undetermined by this data. Therefore, we introduce a nonparametric hierarchical Bayesian prior over programs which allows the sharing of statistical strength across multiple programs. The key challenge we address is how to parametrize this multi-task sharing. For this, we introduce a new representation of programs based on combinatory logic and provide an MCMC algorithm that can perform safe program transformations on this representation in order to reveal shared inter-program substructures. We show the benefits of our multi-task approach on learning macros in a text-editing domain.