Efficient Pragmatic Program Synthesis with Informative Specifications
- URL: http://arxiv.org/abs/2204.02495v1
- Date: Tue, 5 Apr 2022 21:25:58 GMT
- Title: Efficient Pragmatic Program Synthesis with Informative Specifications
- Authors: Saujas Vaduguru, Kevin Ellis, Yewen Pu
- Abstract summary: We show that it is possible to build a program synthesizer that is both pragmatic and efficient by approximating the joint distribution of programs with a product of independent factors.
We find that the synthesizer assuming a factored approximation performs better than a synthesizer assuming an exact joint distribution when evaluated on natural human inputs.
- Score: 13.234975857626752
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Providing examples is one of the most common way for end-users to interact
with program synthesizers. However, program synthesis systems assume that
examples consistent with the program are chosen at random, and do not exploit
the fact that users choose examples pragmatically. Prior work modeled program
synthesis as pragmatic communication, but required an inefficient enumeration
of the entire program space. In this paper, we show that it is possible to
build a program synthesizer that is both pragmatic and efficient by
approximating the joint distribution of programs with a product of independent
factors, and performing pragmatic inference on each factor separately. This
factored distribution approximates the exact joint distribution well when the
examples are given pragmatically, and is compatible with a basic neuro-symbolic
program synthesis algorithm. Surprisingly, we find that the synthesizer
assuming a factored approximation performs better than a synthesizer assuming
an exact joint distribution when evaluated on natural human inputs. This
suggests that humans may be assuming a factored distribution while
communicating programs.
Related papers
- Generating Pragmatic Examples to Train Neural Program Synthesizers [20.819451354452085]
A good synthesizer must choose the intended program from the many that are consistent with the given set of examples.
We propose a novel way to amortize this search with neural networks.
arXiv Detail & Related papers (2023-11-09T20:53:00Z) - Amortizing Pragmatic Program Synthesis with Rankings [19.070549715732483]
In program synthesis, an intelligent system takes in a set of user-generated examples and returns a program that is logically consistent with these examples.
The usage of Rational Speech Acts (RSA) framework has been successful in building emphpragmatic program synthesizers.
This work presents a novel method of amortizing the RSA algorithm by leveraging a emphglobal pragmatic ranking -- a single, total ordering of all the hypotheses.
arXiv Detail & Related papers (2023-09-01T20:12:01Z) - Latent Execution for Neural Program Synthesis Beyond Domain-Specific
Languages [97.58968222942173]
We take the first step to synthesize C programs from input-output examples.
In particular, we propose La Synth, which learns the latent representation to approximate the execution of partially generated programs.
We show that training on these synthesized programs further improves the prediction performance for both Karel and C program synthesis.
arXiv Detail & Related papers (2021-06-29T02:21:32Z) - Representing Partial Programs with Blended Abstract Semantics [62.20775388513027]
We introduce a technique for representing partially written programs in a program synthesis engine.
We learn an approximate execution model implemented as a modular neural network.
We show that these hybrid neuro-symbolic representations enable execution-guided synthesizers to use more powerful language constructs.
arXiv Detail & Related papers (2020-12-23T20:40:18Z) - Latent Programmer: Discrete Latent Codes for Program Synthesis [56.37993487589351]
In many sequence learning tasks, such as program synthesis and document summarization, a key problem is searching over a large space of possible output sequences.
We propose to learn representations of the outputs that are specifically meant for search: rich enough to specify the desired output but compact enough to make search more efficient.
We introduce the emphLatent Programmer, a program synthesis method that first predicts a discrete latent code from input/output examples, and then generates the program in the target language.
arXiv Detail & Related papers (2020-12-01T10:11:35Z) - Optimal Neural Program Synthesis from Multimodal Specifications [45.35689345004124]
Multimodal program synthesis is an attractive way to scale program synthesis to challenging settings.
This paper proposes an optimal neural synthesis approach where the goal is to find a program that satisfies user-provided constraints.
arXiv Detail & Related papers (2020-10-04T20:51:21Z) - Synthesize, Execute and Debug: Learning to Repair for Neural Program
Synthesis [81.54148730967394]
We propose SED, a neural program generation framework that incorporates synthesis, execution, and debug stages.
SED first produces initial programs using the neural program synthesizer component, then utilizes a neural program debugger to iteratively repair the generated programs.
On Karel, a challenging input-output program synthesis benchmark, SED reduces the error rate of the neural program synthesizer itself by a considerable margin, and outperforms the standard beam search for decoding.
arXiv Detail & Related papers (2020-07-16T04:15:47Z) - Program Synthesis with Pragmatic Communication [28.24612900419843]
This work introduces a new inductive bias derived by modeling the program synthesis task as rational communication.
A user study finds that end-user participants communicate more effectively with the pragmatic program synthesizer over a non-pragmatic one.
arXiv Detail & Related papers (2020-07-09T20:55:44Z) - Creating Synthetic Datasets via Evolution for Neural Program Synthesis [77.34726150561087]
We show that some program synthesis approaches generalize poorly to data distributions different from that of the randomly generated examples.
We propose a new, adversarial approach to control the bias of synthetic data distributions and show that it outperforms current approaches.
arXiv Detail & Related papers (2020-03-23T18:34:15Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.