TerpreT: A Probabilistic Programming Language for Program Induction
Alexander L. Gaunt, Marc Brockschmidt, Rishabh Kumar Singh et al. · arXiv (Cornell University) · 2016
We study machine learning formulations of inductive program synthesis; given input-output examples, we try to synthesize source code that maps inputs to corresponding outputs. Our aims are to develop new machine learning approaches based on neural networks and graphical models, and to understand the capabilities of machine learning techniques relative to traditional alternatives, such as those based on constraint solving from the programming languages community. Our key contribution is the proposal of TerpreT, a domain-specific language for expressing program synthesis problems. TerpreT is similar to a probabilistic programming language: a model is composed of a specification of a program representation (declarations of random variables) and an interpreter describing how programs map inputs to outputs (a model connecting unknowns to observations). The inference task is to observe a set of input-output examples and infer the underlying program. TerpreT has two main benefits. First, it enables rapid exploration of a range of domains, program representations, and interpreter models. Second, it separates the model specification from the inference algorithm, allowing like-to-like comparisons between different approaches to inference. From a single TerpreT specification we automatically perform inference using four different back-ends. These are based on gradient descent, linear program (LP) relaxations for graphical models, discrete satisfiability solving, and the Sketch program synthesis system. We illustrate the value of TerpreT by developing several interpreter models and performing an empirical comparison between alternative inference algorithms. Our key empirical finding is that constraint solvers dominate the gradient descent and LP-based formulations. We conclude with suggestions for the machine learning community to make progress on program synthesis.
Cited by 74 works. doi:10.48550/arxiv.1608.04428 Open-access PDF
Authors
References
- Long Short-Term Memory
- Learning long-term dependencies with gradient descent is difficult
- Generating Sequences With Recurrent Neural Networks
- Graphical Models, Exponential Families, and Variational Inference
- Human-level concept learning through probabilistic program induction
- Neural GPUs Learn Algorithms
- Higher Order Recurrent Networks and Grammatical Inference
- A Clockwork RNN
- On the naturalness of software
- Adding Gradient Noise Improves Learning for Very Deep Networks