Alexander L. Gaunt, Marc Brockschmidt, Rishabh Singh
Nate Kushman, Pushmeet Kohli, Jonathan Taylor, Daniel Tarlow
2016 · arXiv
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.
Metadata: arXiv. Abstracts retain their original authors’ rights.
Original HN comments, with labels from simple text rules. A label describes the whole comment and may miss context or irony. Read the discussion to make up your own mind. About the labels
4 selected excerpts · 4 total mentions
Thanks! You may find DeepProbLog by Manhaeve et al. interesting, which brings together logic programming, probabilistic programming and gradient descent/neural networks. Also, more generally, I believe in the field of program synthesis there is some research on deriving programs with gradient descent. However, as also pointed out in the comment below, gradient descent may not always be the best approach to such problems (e.g., https://arxiv.org/abs/1608.04428).
If you're interested in these kinds of things, many years ago we created TerpreT (https://arxiv.org/pdf/1608.04428.pdf and https://github.com/51alg/TerpreT) to look into generic program synthesis problems, using a set of very different techniques (gradient descent, ILP, SMT) on different problem settings (turing machines, boolean circuits, LLVM IR-style basic blocks, and straight assembly).
There is a vast chasm of computational complexity between Chess, Go, and protein folding, to program induction. Unlike problems where the configuration space grows exponentially, the space of valid programs is at least super-exponential and depending on the language family, (e.g. context free, context sensitive, recursively enumerable), can often be undecidable. Furthermore, many language induction problems do not have optimal substructure or overlapping subproblems, two important prerequisites for reinforcement learning to work. In these settings, gradient-based heuristics will only get you so far. If you are interested in learning more about the limits of gradient…
descent, you should look into the TerpreT problem [1]. There are surprisingly tiny Boolean circuits which can be found using constraint solving, but we have not yet been able to learn despite the success of reinforcement learning in other domains. I'm not saying that program induction is impossible, but it is extremely hard even for relative "simple" languages like source code. [1]: https://arxiv.org/pdf/1608.04428.pdf
> What sort of things have been achieved with machine-learning over algorithms, though? See also this paper for a comparison of programming by example using gradient descent versus more standard alternatives: https://arxiv.org/abs/1608.04428 The main takeaway is that gradient descent is not a silver bullet for searching over program space.
More from the same topics.
Tom B. Brown, Benjamin Mann, Nick Ryder +28
Recent work has demonstrated substantial gains on many NLP tasks and benchmarks by pre-training on a large corpus of text followed by fine-tuning on a specific task.
Chiyuan Zhang, Samy Bengio, Moritz Hardt +2
Despite their massive size, successful deep artificial neural networks can exhibit a remarkably small difference between training and test performance.
Haoran Xu, Fredrik Kjolstad
Fast compilation is important when compilation occurs at runtime, such as query compilers in modern database systems and WebAssembly virtual machines in modern browsers.
Mariusz Bojarski, Davide Del Testa, Daniel Dworakowski +10
We trained a convolutional neural network (CNN) to map raw pixels from a single front-facing camera directly to steering commands.