Program Synthesis with Pragmatic Communication

• URL: http://arxiv.org/abs/2007.05060v3
• Date: Wed, 21 Oct 2020 03:02:39 GMT
• Title: Program Synthesis with Pragmatic Communication
• Authors: Yewen Pu, Kevin Ellis, Marta Kryven, Josh Tenenbaum, Armando Solar-Lezama
• Abstract summary: 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.
• Score: 28.24612900419843
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Program synthesis techniques construct or infer programs from user-provided specifications, such as input-output examples. Yet most specifications, especially those given by end-users, leave the synthesis problem radically ill-posed, because many programs may simultaneously satisfy the specification. Prior work resolves this ambiguity by using various inductive biases, such as a preference for simpler programs. This work introduces a new inductive bias derived by modeling the program synthesis task as rational communication, drawing insights from recursive reasoning models of pragmatics. Given a specification, we score a candidate program both on its consistency with the specification, and also whether a rational speaker would chose this particular specification to communicate that program. We develop efficient algorithms for such an approach when learning from input-output examples, and build a pragmatic program synthesizer over a simple grid-like layout domain. A user study finds that end-user participants communicate more effectively with the pragmatic program synthesizer over a non-pragmatic one.

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)
• Efficient Pragmatic Program Synthesis with Informative Specifications [13.234975857626752]
  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.
  arXiv  Detail & Related papers  (2022-04-05T21:25:58Z)
• A Conversational Paradigm for Program Synthesis [110.94409515865867]
  We propose a conversational program synthesis approach via large language models. We train a family of large language models, called CodeGen, on natural language and programming language data. Our findings show the emergence of conversational capabilities and the effectiveness of the proposed conversational program synthesis paradigm.
  arXiv  Detail & Related papers  (2022-03-25T06:55:15Z)
• 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)

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.