From Language to Programs: Bridging Reinforcement Learning and Maximum Marginal Likelihood

By Kelvin Guu, Panupong Pasupat, Evan Zheran Liu, Percy Liang. 2017

199 citations recorded by the source corpus.

Our goal is to learn a semantic parser that maps natural language utterances into executable programs when only indirect supervision is available: examples are labeled with the correct execution result, but not the program itself. Consequently, we must search the space of programs for those that output the correct result, while not being misled by spurious programs: incorrect programs that coincidentally output the correct result. We connect two common learning paradigms, reinforcement learning (RL) and maximum marginal likelihood (MML), and then present a new learning algorithm that combines the strengths of both. The new algorithm guards against spurious programs by combining the systematic search traditionally employed in MML with the randomized exploration of RL, and by updating parameters such that probability is spread more evenly across consistent programs. We apply our learning algorithm to a new neural semantic parser and show significant gains over existing state-of-the-art results on a recent context-dependent semantic parsing task.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Natural Language Processing, 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 Artificial Intelligence

In Computer Vision and Pattern Recognition

In Natural Language Processing

In Reinforcement Learning

Citations in the corpus

Break-It-Fix-It: Unsupervised Learning for Program Repair (2021, methodology): “This is commonly used in structured generation problems such as semantic parsing, program synthesis and molecule generation (Liang et al., 2013; Berant et al., 2013; Guu et al., 2017; Min et al., 2019; Zhong et al., 2020; Yang et al., 2020).”
STaR: Bootstrapping Reasoning With Reasoning (2022, background): “The idea of alternating between filtering steps and training steps more broadly is also well-grounded in prior work in NLP such as [23] and in other weak supervision contexts [24, 25].”
The Web as a Knowledge-Base for Answering Complex Questions (2018, methodology): “However, this requires training from denotations using methods such as maximum marginal likelihood or reinforcement learning (Guu et al., 2017) that are dif-ﬁcult to optimize.”
Neural-Symbolic VQA: Disentangling Reasoning from Vision and Language Understanding (2018, methodology): “For sentences, semantic parsing methods map them to logical forms via a knowledge base or a program [Berant et al., 2013, Liang et al., 2013, Vinyals et al., 2015, Guu et al., 2017].”
Speaker-Follower Models for Vision-and-Language Navigation (2018, background): “Systems that learn to carry out natural language instructions in an interactive environment include approaches based on intermediate structured and executable representations of language [50, 9, 4, 28, 20] and approaches that map directly from language and world state observations to actions [7, 2, ”
Neural Semantic Parsing with Type Constraints for Semi-Structured Tables (2017, background): “This approach is known to be difficult to apply when the space of outputs is large and the reward signal is sparse, and recent work has found that maximizing marginal loglikelihood is more effective in these circumstances (Guu et al., 2017).”
Coupling Retrieval and Meta-Learning for Context-Dependent Semantic Parsing (2019, background): “However, some of action sequences are spurious (Guu et al., 2017), in the sense they do not represent the meaning of questions but get the correct answers.”
Neural Program Synthesis with Priority Queue Training (2018, background): “…Schaechtle et al., 2016; Zaremba et al., 2016; Barone & Sennrich, 2017; Beltramelli, 2017; Cai et al., 2017; Devlin et al., 2017; Hu et al., 2017; Guu et al., 2017; Johnson et al.; Liang et al., 2017; Murali et al., 2017; Parisotto et al., 2016; Rabinovich et al., 2017; Vigueras et al., 2017;…”
Memory Augmented Policy Optimization for Program Synthesis and Semantic Parsing (2018, background): “More discussion of these two objectives can be found in [17, 36, 48].”
Dynamic Hybrid Relation Network for Cross-Domain Context-Dependent Semantic Parsing (2021, methodology): “…encode the current utterance and effectively integrate information from conversation history, at each turn i, we employ an utterance-level Bi-LSTM (Hochreiter and Schmidhuber 1997) to produce embedding from a contextual hidden state: hUi,k = Bi-LSTM U ( xi,k,h U i,k−1 ) , (2) We use the…”
LEVER: Learning to Verify Language-to-Code Generation with Execution (2023, background): “Weakly-supervised learning approaches (Berant et al., 2013; Pasupat & Liang, 2015; Guu et al., 2017) model programs as latent variables and use execution results to derive the supervision signal.”
CONVERSATIONAL MACHINE COMPREHENSION (2019, result): “We compare our approaches with previous semantic parsing approaches (Long et al., 2016; Guu et al., 2017), which map each instruction into a logical form, and then execute the logical form to update the world state, and (Fried et al., 2018; Suhr & Artzi, 2018), which maps each instruction into…”
Inferring Rewards from Language in Context (2022, background): “…2016; Fried et al., 2018a; Arumugam et al., 2017; Suhr et al., 2018) or map directly to primitive actions (Branavan et al., 2009; Andreas and Klein, 2015; Mei et al., 2016; Bisk et al., 2016; Misra et al., 2017; Guu et al., 2017; Suhr and Artzi, 2018; Anderson et al., 2018; Shridhar et al., 2020).”
Learning by Fixing: Solving Math Word Problems with Weak Supervision (2020, methodology): “Neural-Symbolic Learning for NLP Neural-symbolic learning has been applied to solve NLP tasks with weak supervision, such as semantic parsing and program synthesis (Liang et al. 2016a; Guu et al. 2017; Liang et al. 2018; Agarwal et al. 2019; Li et al. 2020b).”
TaPas: Weakly Supervised Table Parsing via Pre-training (2020, background): “Although appealing, training semantic parsers from this input is often difficult due to the abundance of spurious logical forms (Berant et al., 2013; Guu et al., 2017) and reward sparsity (Agarwal et al., 2019; Muhlgay et al., 2019).”
Can we generate shellcodes via natural language? An empirical study (2021, background): “, 2020), has been previously addressed to generate executable snippets in domain-specific languages (Guu et al., 2017; Long et al., 2016), and several programming languages, including Python (Yin and Neubig, 2017) and Java (Ling et al.”