Learning Programs: A Hierarchical Bayesian Approach

The authors' are interested in learning programs for multiple related tasks given only a few training examples per task. Since the program for a single task is underdetermined by its data, the paper introduces a nonparametric hierarchical Bayesian prior over programs which shares statistical strength across multiple tasks. The key challenge is to parametrize this multi-task sharing. For this, the paper introduces a new representation of programs based on combinatory logic and provide an MCMC algorithm that can perform safe program transformations on this representation to reveal shared inter-program substructures.