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

Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics, pages 1051–1062 Vancouver, Canada, July 30 - August 4, 2017. c⃝2017 Association for Computational Linguistics https://doi.org/10.18653/v1/P17-1097 Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics, pages 1051–1062 Vancouver, Canada, July 30 - August 4, 2017. c⃝2017 Association for Computational Linguistics https://doi.org/10.18653/v1/P17-1097 From Language to Programs: Bridging Reinforcement Learning and Maximum Marginal Likelihood Kelvin Guu Statistics Stanford University kguu@stanford.edu Panupong Pasupat Computer Science Stanford University ppasupat@stanford.edu Evan Zheran Liu Computer Science Stanford University evanliu@stanford.edu Percy Liang Computer Science Stanford University pliang@cs.stanford.edu Abstract Our goal is to learn a semantic parser that maps natural language utterances into ex- ecutable programs when only indirect su- pervision is available: examples are la- beled 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 pro- grams: incorrect programs that coinci- dentally output the correct result. We connect two common learning paradigms, reinforcement learning (RL) and maxi- mum marginal likelihood (MML), and then present a new learning algorithm that combines the strengths of both. The new algorithm guards against spurious pro- grams by combining the systematic search traditionally employed in MML with the randomized exploration of RL, and by up- dating parameters such that probability is spread more evenly across consistent pro- grams. 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. 1 Introduction We are interested in learning a semantic parser that maps natural language utterances into executable programs (e.g., logical forms). For example, in Figure 1, a program corresponding to the utter- ance transforms an initial world state into a new world state. We would like to learn from indirect supervision, where each training example is only labeled with the correct output (e.g. a target world state), but not the program that produced that out- "The man in the yellow hat moves to the left of the woman in blue.” Spurious: move(hasShirt(red), 1) Correct: move(hasHat(yellow), leftOf(hasShirt(blue))) 1 2 3 1 2 3 BEFORE AFTER z* z' 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 p(z') = 10-4 p(z*) = 10-6 red yellow hasHat blue hasShirt leftOf move move 1 hasShirt Figure 1: The task is to map natural language ut- terances to a program that manipulates the world state. The correct program captures the true mean- ing of the utterances, while spurious programs ar- rive at the correct output for the wrong reasons. We develop methods to prevent the model from being drawn to spurious programs. put (Clarke et al., 2010; Liang et al., 2011; Kr- ishnamurthy and Mitchell, 2012; Artzi and Zettle- moyer, 2013; Liang et al., 2017). The process of constructing a program can be formulated as a sequential decision-making pro- cess, where feedback is only received at the end of the sequence when the completed …

Content truncated to 500 words