The Experts below are selected from a list of 309 Experts worldwide ranked by ideXlab platform
Armando Solar-lezama - One of the best experts on this subject based on the ideXlab platform.
-
NeurIPS - Program Synthesis with Pragmatic Communication
2020Co-Authors: Kevin Ellis, Marta Kryven, Josh Tenenbaum, Armando Solar-lezamaAbstract: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.
-
Program Synthesis with Pragmatic Communication
arXiv: Artificial Intelligence, 2020Co-Authors: Kevin Ellis, Marta Kryven, Josh Tenenbaum, Armando Solar-lezamaAbstract: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.
-
Program Synthesis with algebraic library specifications
Proceedings of the ACM on Programming Languages, 2019Co-Authors: Benjamin Mariano, Jeffrey S. Foster, Josh Reese, Thanhvu Nguyen, Xiaokang Qiu, Armando Solar-lezamaAbstract:A key challenge in Program Synthesis is synthesizing Programs that use libraries, which most real-world software does. The current state of the art is to model libraries with mock library implementations that perform the same function in a simpler way. However, mocks may still be large and complex, and must include many implementation details, both of which could limit Synthesis performance. To address this problem, we introduce JLibSketch, a Java Program Synthesis tool that allows library behavior to be described with algebraic specifications, which are rewrite rules for sequences of method calls, e.g., encryption followed by decryption (with the same key) is the identity. JLibSketch implements rewrite rules by compiling JLibSketch problems into problems for the Sketch Program Synthesis tool. More specifically, after compilation, library calls are represented by abstract data types (ADTs), and rewrite rules manipulate those ADTs. We formalize compilation and prove it sound and complete if the rewrite rules are ordered and non-unifiable. We evaluated JLibSketch by using it to synthesize nine Programs that use libraries from three domains: data structures, cryptography, and file systems. We found that algebraic specifications are, on average, about half the size of mocks. We also found that algebraic specifications perform better than mocks on seven of the nine Programs, sometimes significantly so, and perform equally well on the last two Programs. Thus, we believe that JLibSketch takes an important step toward Synthesis of Programs that use libraries.
-
Write, Execute, Assess: Program Synthesis with a REPL
arXiv: Programming Languages, 2019Co-Authors: Kevin Ellis, Josh Tenenbaum, Maxwell I. Nye, Felix Sosa, Armando Solar-lezamaAbstract:We present a neural Program Synthesis approach integrating components which write, execute, and assess code to navigate the search space of possible Programs. We equip the search process with an interpreter or a read-eval-print-loop (REPL), which immediately executes partially written Programs, exposing their semantics. The REPL addresses a basic challenge of Program Synthesis: tiny changes in syntax can lead to huge changes in semantics. We train a pair of models, a policy that proposes the new piece of code to write, and a value function that assesses the prospects of the code written so-far. At test time we can combine these models with a Sequential Monte Carlo algorithm. We apply our approach to two domains: synthesizing text editing Programs and inferring 2D and 3D graphics Programs.
-
ICML - Selecting Representative Examples for Program Synthesis
2018Co-Authors: Zachery Miranda, Armando Solar-lezama, Leslie Pack KaelblingAbstract: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.
Stefan Forstenlechner - One of the best experts on this subject based on the ideXlab platform.
-
PPSN (1) - Extending Program Synthesis Grammars for Grammar-Guided Genetic Programming
Parallel Problem Solving from Nature – PPSN XV, 2018Co-Authors: Stefan Forstenlechner, David Fagan, Miguel Nicolau, Michael O'neillAbstract:Program Synthesis is a problem domain that due to its importance is tackled by many different fields, one being Genetic Programming. Two variants, Grammar-Guided Genetic Programming (G3P) and PushGP, have been applied to a vast general Program Synthesis benchmark suite and solved a variety of problems although with varying success rates. While G3P achieved higher success rates on some problems, PushGP was able to find solutions to more problem instances. Reason why G3P fails at some problems might be missing functionality in the grammars or knowledge that has to discovered during the runs. In this paper the current shortcomings of G3P are analysed and the papers contributions include an example of extending grammars for Program Synthesis, a fairer comparison between PushGP and G3P with a more similar function set as well as new results on problems that have not been solved with G3P and one that has not been solved with PushGP.
-
GECCO - Towards effective semantic operators for Program Synthesis in genetic Programming
Proceedings of the Genetic and Evolutionary Computation Conference, 2018Co-Authors: Stefan Forstenlechner, David Fagan, Miguel Nicolau, Michael O'neillAbstract:The use of semantic information in genetic Programming operators has shown major improvements in recent years, especially in the regression and boolean domain. As semantic information is domain specific, using it in other areas poses certain problems. Semantic operators require being adapted for the problem domain they are applied to. An attempt to create a semantic crossover for Program Synthesis has been made with rather limited success, but the results have provided insights about using semantics in Program Synthesis. Based on this initial attempt, this paper presents an improved version of semantic operators for Program Synthesis, which contains a small but significant change to the overall functionality, as well as a novel measure for the comparison of the semantics of subtrees. The results show that the improved semantic crossover is superior to the previous semantic operator in the Program Synthesis domain.
-
towards understanding and refining the general Program Synthesis benchmark suite with genetic Programming
Congress on Evolutionary Computation, 2018Co-Authors: Stefan Forstenlechner, David Fagan, Miguel Nicolau, Michael OneillAbstract:Program Synthesis is a complex problem domain tackled by many communities via different methods. In the last few years, a lot of progress has been made with Genetic Programming (GP) on solving a variety of general Program Synthesis problems for which a benchmark suite has been introduced. While Genetic Programming is capable of finding correct solutions for many problems contained in a general Program Synthesis problems benchmark suite, the actual success rate per problem is low in most cases. In this paper, we analyse certain aspects of the benchmark suite and the computational effort required to solve its problems. A subset of problems on which GP performs poorly is identified. This subset is analysed to find measures to increase success rates for similar problems. The paper concludes with suggestions to refine performance on Program Synthesis problems.
-
CEC - Towards Understanding and Refining the General Program Synthesis Benchmark Suite with Genetic Programming
2018 IEEE Congress on Evolutionary Computation (CEC), 2018Co-Authors: Stefan Forstenlechner, David Fagan, Miguel Nicolau, Michael O'neillAbstract:Program Synthesis is a complex problem domain tackled by many communities via different methods. In the last few years, a lot of progress has been made with Genetic Programming (GP) on solving a variety of general Program Synthesis problems for which a benchmark suite has been introduced. While Genetic Programming is capable of finding correct solutions for many problems contained in a general Program Synthesis problems benchmark suite, the actual success rate per problem is low in most cases. In this paper, we analyse certain aspects of the benchmark suite and the computational effort required to solve its problems. A subset of problems on which GP performs poorly is identified. This subset is analysed to find measures to increase success rates for similar problems. The paper concludes with suggestions to refine performance on Program Synthesis problems.
Kevin Ellis - One of the best experts on this subject based on the ideXlab platform.
-
NeurIPS - Program Synthesis with Pragmatic Communication
2020Co-Authors: Kevin Ellis, Marta Kryven, Josh Tenenbaum, Armando Solar-lezamaAbstract: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.
-
Program Synthesis with Pragmatic Communication
arXiv: Artificial Intelligence, 2020Co-Authors: Kevin Ellis, Marta Kryven, Josh Tenenbaum, Armando Solar-lezamaAbstract: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.
-
Write, Execute, Assess: Program Synthesis with a REPL
arXiv: Programming Languages, 2019Co-Authors: Kevin Ellis, Josh Tenenbaum, Maxwell I. Nye, Felix Sosa, Armando Solar-lezamaAbstract:We present a neural Program Synthesis approach integrating components which write, execute, and assess code to navigate the search space of possible Programs. We equip the search process with an interpreter or a read-eval-print-loop (REPL), which immediately executes partially written Programs, exposing their semantics. The REPL addresses a basic challenge of Program Synthesis: tiny changes in syntax can lead to huge changes in semantics. We train a pair of models, a policy that proposes the new piece of code to write, and a value function that assesses the prospects of the code written so-far. At test time we can combine these models with a Sequential Monte Carlo algorithm. We apply our approach to two domains: synthesizing text editing Programs and inferring 2D and 3D graphics Programs.
-
unsupervised learning by Program Synthesis
Neural Information Processing Systems, 2015Co-Authors: Kevin Ellis, Armando Solarlezama, Joshua B TenenbaumAbstract:We introduce an unsupervised learning algorithm that combines probabilistic modeling with solver-based techniques for Program Synthesis. We apply our techniques to both a visual learning domain and a language learning problem, showing that our algorithm can learn many visual concepts from only a few examples and that it can recover some English inflectional morphology. Taken together, these results give both a new approach to unsupervised learning of symbolic compositional structures, and a technique for applying Program Synthesis tools to noisy data.
-
NIPS - Unsupervised learning by Program Synthesis
2015Co-Authors: Kevin Ellis, Armando Solar-lezama, Joshua B TenenbaumAbstract:We introduce an unsupervised learning algorithm that combines probabilistic modeling with solver-based techniques for Program Synthesis. We apply our techniques to both a visual learning domain and a language learning problem, showing that our algorithm can learn many visual concepts from only a few examples and that it can recover some English inflectional morphology. Taken together, these results give both a new approach to unsupervised learning of symbolic compositional structures, and a technique for applying Program Synthesis tools to noisy data.
Michael O'neill - One of the best experts on this subject based on the ideXlab platform.
-
PPSN (1) - Extending Program Synthesis Grammars for Grammar-Guided Genetic Programming
Parallel Problem Solving from Nature – PPSN XV, 2018Co-Authors: Stefan Forstenlechner, David Fagan, Miguel Nicolau, Michael O'neillAbstract:Program Synthesis is a problem domain that due to its importance is tackled by many different fields, one being Genetic Programming. Two variants, Grammar-Guided Genetic Programming (G3P) and PushGP, have been applied to a vast general Program Synthesis benchmark suite and solved a variety of problems although with varying success rates. While G3P achieved higher success rates on some problems, PushGP was able to find solutions to more problem instances. Reason why G3P fails at some problems might be missing functionality in the grammars or knowledge that has to discovered during the runs. In this paper the current shortcomings of G3P are analysed and the papers contributions include an example of extending grammars for Program Synthesis, a fairer comparison between PushGP and G3P with a more similar function set as well as new results on problems that have not been solved with G3P and one that has not been solved with PushGP.
-
GECCO - Towards effective semantic operators for Program Synthesis in genetic Programming
Proceedings of the Genetic and Evolutionary Computation Conference, 2018Co-Authors: Stefan Forstenlechner, David Fagan, Miguel Nicolau, Michael O'neillAbstract:The use of semantic information in genetic Programming operators has shown major improvements in recent years, especially in the regression and boolean domain. As semantic information is domain specific, using it in other areas poses certain problems. Semantic operators require being adapted for the problem domain they are applied to. An attempt to create a semantic crossover for Program Synthesis has been made with rather limited success, but the results have provided insights about using semantics in Program Synthesis. Based on this initial attempt, this paper presents an improved version of semantic operators for Program Synthesis, which contains a small but significant change to the overall functionality, as well as a novel measure for the comparison of the semantics of subtrees. The results show that the improved semantic crossover is superior to the previous semantic operator in the Program Synthesis domain.
-
CEC - Towards Understanding and Refining the General Program Synthesis Benchmark Suite with Genetic Programming
2018 IEEE Congress on Evolutionary Computation (CEC), 2018Co-Authors: Stefan Forstenlechner, David Fagan, Miguel Nicolau, Michael O'neillAbstract:Program Synthesis is a complex problem domain tackled by many communities via different methods. In the last few years, a lot of progress has been made with Genetic Programming (GP) on solving a variety of general Program Synthesis problems for which a benchmark suite has been introduced. While Genetic Programming is capable of finding correct solutions for many problems contained in a general Program Synthesis problems benchmark suite, the actual success rate per problem is low in most cases. In this paper, we analyse certain aspects of the benchmark suite and the computational effort required to solve its problems. A subset of problems on which GP performs poorly is identified. This subset is analysed to find measures to increase success rates for similar problems. The paper concludes with suggestions to refine performance on Program Synthesis problems.
Milan Petkovic - One of the best experts on this subject based on the ideXlab platform.
-
BF++: a language for general-purpose Program Synthesis.
arXiv: Artificial Intelligence, 2021Co-Authors: Vadim Liventsev, Aki Härmä, Milan PetkovicAbstract:Most state of the art decision systems based on Reinforcement Learning (RL) are data-driven black-box neural models, where it is often difficult to incorporate expert knowledge into the models or let experts review and validate the learned decision mechanisms. Knowledge-insertion and model review are important requirements in many applications involving human health and safety. One way to bridge the gap between data and knowledge driven systems is Program Synthesis: replacing a neural network that outputs decisions with a symbolic Program generated by a neural network or by means of genetic Programming. We propose a new Programming language, BF++, designed specifically for automatic Programming of agents in a Partially Observable Markov Decision Process (POMDP) setting and apply neural Program Synthesis to solve standard OpenAI Gym benchmarks.
-
BF++: a language for general-purpose neural Program Synthesis.
arXiv: Artificial Intelligence, 2021Co-Authors: Vadim Liventsev, Aki Härmä, Milan PetkovicAbstract:Most state of the art decision systems based on Reinforcement Learning (RL) are data-driven black-box neuralmodels, where it is often difficult to incorporate expert knowledge into the models or let experts review andvalidate the learned decision mechanisms. Knowledge-insertion and model review are important requirements inmany applications involving human health and safety. One way to bridge the gap between data and knowledgedriven systems is Program Synthesis: replacing a neural network that outputs decisions with one that generatesdecision-making code in some Programming language. We propose a new Programming language, BF++,designed specifically for neural Program Synthesis in a Partially Observable Markov Decision Process (POMDP)setting and generate Programs for a number of standard OpenAI Gym benchmarks.
