Memory Augmented Policy Optimization for Program Synthesis and Semantic Parsing

By Chen Liang, Mohammad Norouzi, Jonathan Berant, Quoc V. Le, Ni Lao. 2018

140 citations recorded by the source corpus.

We present Memory Augmented Policy Optimization (MAPO), a simple and novel way to leverage a memory buffer of promising trajectories to reduce the variance of policy gradient estimate. MAPO is applicable to deterministic environments with discrete actions, such as structured prediction and combinatorial optimization tasks. We express the expected return objective as a weighted sum of two terms: an expectation over the high-reward trajectories inside the memory buffer, and a separate expectation over trajectories outside the buffer. To make an efficient algorithm of MAPO, we propose: (1) memory weight clipping to accelerate and stabilize training; (2) systematic exploration to discover high-reward trajectories; (3) distributed sampling from inside and outside of the memory buffer to scale up training. MAPO improves the sample efficiency and robustness of policy gradient, especially on tasks with sparse rewards. We evaluate MAPO on weakly supervised program synthesis from natural language (semantic parsing). On the WikiTableQuestions benchmark, we improve the state-of-the-art by 2.6%, achieving an accuracy of 46.3%. On the WikiSQL benchmark, MAPO achieves an accuracy of 74.9% with only weak supervision, outperforming several strong baselines with full supervision. Our source code is available at https://goo.gl/TXBp4e

Subfields: Computer Vision and Pattern Recognition, Electrical and Electronic Engineering, Hardware and Architecture, Prompting & Reasoning, Reinforcement Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Vision and Pattern Recognition

In Electrical and Electronic Engineering

In Hardware and Architecture

In Prompting & Reasoning

In Reinforcement Learning

Citations in the corpus

A Discrete Hard EM Approach for Weakly Supervised Question Answering (2019, methodology): “We compare with both traditional and recently-developed reward-based algorithms for weak supervision, including beam-based MML (MML which keeps a beam during training), conventional hard EM 8 , REINFORCE (Williams, 1992), iterative ML (Liang et al., 2017; Abolaﬁa et al., 2018) and a family of MAPO (”
Unsupervised Question Decomposition for Question Answering (2020, background): “Weakly supervised question generation often uses reinforcement learning (Nogueira & Cho, 2017; Wang & Lake, 2019; Strub et al., 2017; Das et al., 2017; Liang et al., 2018), where an unsupervised initialization can greatly mitigate the issues of exploring from scratch (Jaderberg et al., 2017).”
AutoML-Zero: Evolving Machine Learning Algorithms From Scratch (2020, neutral): “The synthesized programs—or algorithms—solve problems like sorting, addition, counting [74, 27, 70, 85], string manipulations [64, 61, 19], character recognition [38], competitionstyle programming [5], structured data QA [56, 45, 46],”
TabFact: A Large-scale Dataset for Table-based Fact Verification (2019, methodology): “They aim to retrieve answers by synthesizing programs and executing them on the tables, such as in Neural Programmer (Neelakan-tan et al., 2016; 2017) and Neural Symbolic Machines (Liang et al., 2017; 2018; Agarwal et al., 2019).”
TABBIE: Pretrained Representations of Tabular Data (2021, background): “Note that we do not investigate TABBIE ’s performance on table-and-text tasks such as WikiTable-Questions (Pasupat and Liang, 2015), as our focus is not on integrating TABBIE into complex task-speciﬁc pipelines (Liang et al., 2018), although this is an interesting avenue for future work.”
TaBERT: Pretraining for Joint Understanding of Textual and Tabular Data (2020, methodology): “MAPO uses a domain-speciﬁc query language tailored to answer compositional questions on a single table.”
Large Language Models are few(1)-shot Table Reasoners (2022, methodology): “This line of work includes Logic-FactChecker (Zhong et al., 2020), Neural-Symbolic Machine (Liang et al., 2018), etc.”
LEGO: Latent Execution-Guided Reasoning for Multi-Hop Question Answering on Knowledge Graphs (2021, methodology): “…more easily than the noisy ones (Arpit et al., 2017; Zhang et al., 2017; Liu et al., 2020), we propose stochastic hard EM (Min et al., 2019; Chen et al., 2020b; Liang et al., 2018), i.e. , for each question, we only optimize the model with the candidate query with the lowest loss in a minibatch.”
CodeRL: Mastering Code Generation through Pretrained Models and Deep Reinforcement Learning (2022, methodology): “More related to our work are RL-based program synthesis [Guu et al., 2017, Bunel et al., 2018, Liang et al., 2018, Zhong et al., 2018] and execution-guided synthesis approaches [Ellis et al., 2019, Chen et al., 2021b].”
SpreadsheetCoder: Formula Prediction from Semi-structured Context (2021, unknown): “…2017; Bunel et al., 2018; Bavishi et al., 2019; Shin et al., 2018; Chen et al., 2019), natural language descriptions (Gulwani & Marron, 2014; Yu et al., 2018; Yin et al., 2018; Lin et al., 2018; Liang et al., 2018; Wang et al., 2020), and images (Wu et al., 2017; Liu & Wu, 2019; Sun et al., 2018).”
Learning Semantic Parsers from Denotations with Latent Structured Alignments and Abstract Programs (2019, background): “Interestingly, its performance surpasses previously reported weakly-supervised models (Liang et al., 2018; Agarwal et al., 2019) and is on par even with fully supervised ones (Dong and Lapata, 2018).”
Learning to Generalize from Sparse and Underspecified Rewards (2019, methodology): “…variants of our technique with the current state-of-the-art in weakly supervised semantic parsing, Memory Augmented Policy Optimization ( MAPO ) (Liang et al., 2018): MAPOX : Combining the exploration ability of IML with generalization ability of MAPO, MAPOX runs MAPO starting from a memory…”
StructGPT: A General Framework for Large Language Model to Reason over Structured Data (2023, methodology): “For TableQA, we select MAPO (Liang et al., 2018), TAPAS (Herzig et al., 2020; Eisensch-los et al., 2020), UnifiedSKG (T5-3B) (Xie et al., 2022), TAPEX (Liu et al., 2022), and DATER (Ye et al., 2023).”
Learning by Fixing: Solving Math Word Problems with Weak Supervision (2020, methodology): “Both the REINFORCE and MAPO take a long time to start improving, which indicates the policy gradient methods suffer from the cold-start and need time to accumulate rewarding samples.”
Neural Symbolic Reader: Scalable Integration of Distributed and Symbolic Representations for Reading Comprehension (2020, methodology): “To filter out spurious programs, we adopt hard EM (Liang et al., 2018; Min et al., 2019) due to its simplicity and efficiency.”
Deep symbolic regression: Recovering mathematical expressions from data via risk-seeking policy gradients (2019, background): “Similarly, Liang et al. (2018) use a memory buffer to augment a policy gradient with off-policy training.”
Benchmarking Meaning Representations in Neural Semantic Parsing (2020, background): “…applied to weakly supervised semantic parsing, which receives wide attention because parsers are only supervised with execution results and annotated logical forms are no longer required (Berant et al., 2013; Pasupat and Liang, 2015; Goldman et al., 2018; Liang et al., 2018; Mueller et al., 2019).”