Reinforcement Learning and Data-Generation for Syntax-Guided Synthesis
- URL: http://arxiv.org/abs/2307.09564v2
- Date: Fri, 5 Jan 2024 13:07:10 GMT
- Title: Reinforcement Learning and Data-Generation for Syntax-Guided Synthesis
- Authors: Julian Parsert and Elizabeth Polgreen
- Abstract summary: We present a reinforcement-learning algorithm for SyGuS which uses Monte-Carlo Tree Search (MCTS) to search the space of candidate solutions.
Our algorithm learns policy and value functions which, combined with the upper confidence bound for trees, allow it to balance exploration and exploitation.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Program synthesis is the task of automatically generating code based on a
specification. In Syntax-Guided Synthesis (SyGuS) this specification is a
combination of a syntactic template and a logical formula, and the result is
guaranteed to satisfy both.
We present a reinforcement-learning guided algorithm for SyGuS which uses
Monte-Carlo Tree Search (MCTS) to search the space of candidate solutions. Our
algorithm learns policy and value functions which, combined with the upper
confidence bound for trees, allow it to balance exploration and exploitation. A
common challenge in applying machine learning approaches to syntax-guided
synthesis is the scarcity of training data. To address this, we present a
method for automatically generating training data for SyGuS based on
anti-unification of existing first-order satisfiability problems, which we use
to train our MCTS policy. We implement and evaluate this setup and demonstrate
that learned policy and value improve the synthesis performance over a baseline
by over 26 percentage points in the training and testing sets. Our tool
outperforms state-of-the-art tool cvc5 on the training set and performs
comparably in terms of the total number of problems solved on the testing set
(solving 23% of the benchmarks on which cvc5 fails). We make our data set
publicly available, to enable further application of machine learning methods
to the SyGuS problem.
Related papers
- ToolACE: Winning the Points of LLM Function Calling [139.07157814653638]
ToolACE is an automatic agentic pipeline designed to generate accurate, complex, and diverse tool-learning data.
We demonstrate that models trained on our synthesized data, even with only 8B parameters, achieve state-of-the-art performance on the Berkeley Function-Calling Leaderboard.
arXiv Detail & Related papers (2024-09-02T03:19:56Z) - IPSynth: Interprocedural Program Synthesis for Software Security Implementation [3.1119394814248253]
We introduce IP Synth, a novel inter-procedural program synthesis approach that automatically learns the specification of the tactic.
Our results show that our approach can accurately locate corresponding spots in the program, synthesize needed code snippets, add them to the program, and outperform ChatGPT in inter-procedural tactic synthesis tasks.
arXiv Detail & Related papers (2024-03-16T07:12:24Z) - Topological Guided Actor-Critic Modular Learning of Continuous Systems
with Temporal Objectives [2.398608007786179]
This work investigates the formal policy synthesis of continuous-state dynamic systems given high-level specifications in linear temporal logic.
We use neural networks to approximate the value function and policy function for hybrid product state space.
arXiv Detail & Related papers (2023-04-20T01:36:05Z) - Towards Automated Imbalanced Learning with Deep Hierarchical
Reinforcement Learning [57.163525407022966]
Imbalanced learning is a fundamental challenge in data mining, where there is a disproportionate ratio of training samples in each class.
Over-sampling is an effective technique to tackle imbalanced learning through generating synthetic samples for the minority class.
We propose AutoSMOTE, an automated over-sampling algorithm that can jointly optimize different levels of decisions.
arXiv Detail & Related papers (2022-08-26T04:28:01Z) - Learning Connectivity-Maximizing Network Configurations [123.01665966032014]
We propose a supervised learning approach with a convolutional neural network (CNN) that learns to place communication agents from an expert.
We demonstrate the performance of our CNN on canonical line and ring topologies, 105k randomly generated test cases, and larger teams not seen during training.
After training, our system produces connected configurations 2 orders of magnitude faster than the optimization-based scheme for teams of 10-20 agents.
arXiv Detail & Related papers (2021-12-14T18:59:01Z) - Network Support for High-performance Distributed Machine Learning [17.919773898228716]
We propose a system model that captures both learning nodes (that perform computations) and information nodes (that provide data)
We then formulate the problem of selecting (i) which learning and information nodes should cooperate to complete the learning task, and (ii) the number of iterations to perform.
We devise an algorithm, named DoubleClimb, that can find a 1+1/|I|-competitive solution with cubic worst-case complexity.
arXiv Detail & Related papers (2021-02-05T19:38:57Z) - Fast Few-Shot Classification by Few-Iteration Meta-Learning [173.32497326674775]
We introduce a fast optimization-based meta-learning method for few-shot classification.
Our strategy enables important aspects of the base learner objective to be learned during meta-training.
We perform a comprehensive experimental analysis, demonstrating the speed and effectiveness of our approach.
arXiv Detail & Related papers (2020-10-01T15:59:31Z) - BUSTLE: Bottom-Up Program Synthesis Through Learning-Guided Exploration [72.88493072196094]
We present a new synthesis approach that leverages learning to guide a bottom-up search over programs.
In particular, we train a model to prioritize compositions of intermediate values during search conditioned on a set of input-output examples.
We show that the combination of learning and bottom-up search is remarkably effective, even with simple supervised learning approaches.
arXiv Detail & Related papers (2020-07-28T17:46:18Z) - Generating Diverse and Consistent QA pairs from Contexts with
Information-Maximizing Hierarchical Conditional VAEs [62.71505254770827]
We propose a conditional variational autoencoder (HCVAE) for generating QA pairs given unstructured texts as contexts.
Our model obtains impressive performance gains over all baselines on both tasks, using only a fraction of data for training.
arXiv Detail & Related papers (2020-05-28T08:26:06Z) - Grammar Filtering For Syntax-Guided Synthesis [6.298766745228328]
We propose a system for using machine learning in tandem with automated reasoning techniques to solve PBE problems.
By preprocessing SyGuS PBE problems with a neural network, we can use a data driven approach to reduce the size of the search space.
Our system is able to run atop existing SyGuS PBE synthesis tools, decreasing the runtime of the winner of the 2019 SyGuS Competition for the PBE track by 47.65%.
arXiv Detail & Related papers (2020-02-07T16:35:50Z)
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.