Selecting Representative Examples for Program Synthesis

Yewen Pu, Zachery Miranda, Armando Solar-Lezama, Leslie Kaelbling
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:4161-4170, 2018.

Abstract

Program synthesis is a class of regression problems where one seeks a solution, in the form of a source-code program, mapping the inputs to their corresponding outputs exactly. Due to its precise and combinatorial nature, program synthesis is commonly formulated as a constraint satisfaction problem, where input-output examples are encoded as constraints and solved with a constraint solver. A key challenge of this formulation is scalability: while constraint solvers work well with a few well-chosen examples, a large set of examples can incur significant overhead in both time and memory. We describe a method to discover a subset of examples that is both small and representative: the subset is constructed iteratively, using a neural network to predict the probability of unchosen examples conditioned on the chosen examples in the subset, and greedily adding the least probable example. We empirically evaluate the representativeness of the subsets constructed by our method, and demonstrate such subsets can significantly improve synthesis time and stability.

Cite this Paper

BibTeX
@InProceedings{pmlr-v80-pu18b, title = {Selecting Representative Examples for Program Synthesis}, author = {Pu, Yewen and Miranda, Zachery and Solar-Lezama, Armando and Kaelbling, Leslie}, booktitle = {Proceedings of the 35th International Conference on Machine Learning}, pages = {4161--4170}, year = {2018}, editor = {Dy, Jennifer and Krause, Andreas}, volume = {80}, series = {Proceedings of Machine Learning Research}, month = {10--15 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v80/pu18b/pu18b.pdf}, url = {https://proceedings.mlr.press/v80/pu18b.html}, abstract = {Program synthesis is a class of regression problems where one seeks a solution, in the form of a source-code program, mapping the inputs to their corresponding outputs exactly. Due to its precise and combinatorial nature, program synthesis is commonly formulated as a constraint satisfaction problem, where input-output examples are encoded as constraints and solved with a constraint solver. A key challenge of this formulation is scalability: while constraint solvers work well with a few well-chosen examples, a large set of examples can incur significant overhead in both time and memory. We describe a method to discover a subset of examples that is both small and representative: the subset is constructed iteratively, using a neural network to predict the probability of unchosen examples conditioned on the chosen examples in the subset, and greedily adding the least probable example. We empirically evaluate the representativeness of the subsets constructed by our method, and demonstrate such subsets can significantly improve synthesis time and stability.} }
Endnote
%0 Conference Paper %T Selecting Representative Examples for Program Synthesis %A Yewen Pu %A Zachery Miranda %A Armando Solar-Lezama %A Leslie Kaelbling %B Proceedings of the 35th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2018 %E Jennifer Dy %E Andreas Krause %F pmlr-v80-pu18b %I PMLR %P 4161--4170 %U https://proceedings.mlr.press/v80/pu18b.html %V 80 %X Program synthesis is a class of regression problems where one seeks a solution, in the form of a source-code program, mapping the inputs to their corresponding outputs exactly. Due to its precise and combinatorial nature, program synthesis is commonly formulated as a constraint satisfaction problem, where input-output examples are encoded as constraints and solved with a constraint solver. A key challenge of this formulation is scalability: while constraint solvers work well with a few well-chosen examples, a large set of examples can incur significant overhead in both time and memory. We describe a method to discover a subset of examples that is both small and representative: the subset is constructed iteratively, using a neural network to predict the probability of unchosen examples conditioned on the chosen examples in the subset, and greedily adding the least probable example. We empirically evaluate the representativeness of the subsets constructed by our method, and demonstrate such subsets can significantly improve synthesis time and stability.
APA
Pu, Y., Miranda, Z., Solar-Lezama, A. & Kaelbling, L.. (2018). Selecting Representative Examples for Program Synthesis. Proceedings of the 35th International Conference on Machine Learning, in Proceedings of Machine Learning Research 80:4161-4170 Available from https://proceedings.mlr.press/v80/pu18b.html.

Related Material