Value-based Search in Execution Space for Mapping Instructions to Programs

Proceedings of NAACL-HLT 2019, pages 1942–1954 Minneapolis, Minnesota, June 2 - June 7, 2019. c⃝2019 Association for Computational Linguistics 1942 Value-based Search in Execution Space for Mapping Instructions to Programs Dor Muhlgay1 Jonathan Herzig1 Jonathan Berant1,2 1School of Computer Science, Tel-Aviv University 2Allen Institute for Artificial Intelligence {dormuhlg@mail,jonathan.herzig@cs,joberant@cs}.tau.ac.il Abstract Training models to map natural language in- structions to programs, given target world su- pervision only, requires searching for good programs at training time. Search is com- monly done using beam search in the space of partial programs or program trees, but as the length of the instructions grows finding a good program becomes difficult. In this work, we propose a search algorithm that uses the target world state, known at training time, to train a critic network that predicts the expected reward of every search state. We then score search states on the beam by interpolating their expected reward with the likelihood of pro- grams represented by the search state. More- over, we search not in the space of programs but in a more compressed state of program ex- ecutions, augmented with recent entities and actions. On the SCONE dataset, we show that our algorithm dramatically improves perfor- mance on all three domains compared to stan- dard beam search and other baselines. 1 Introduction Training models that can understand natural lan- guage instructions and execute them in a real- world environment is of paramount importance for communicating with virtual assistants and robots, and therefore has attracted considerable atten- tion (Branavan et al., 2009; Vogel and Jurafsky, 2010; Chen and Mooney, 2011). A prominent ap- proach is to cast the problem as semantic parsing, where instructions are mapped to a high-level pro- gramming language (Artzi and Zettlemoyer, 2013; Long et al., 2016; Guu et al., 2017). Because anno- tating programs at scale is impractical, it is desir- able to train a model from instructions, an initial world state, and a target world state only, letting the program itself be a latent variable. Learning from such weak supervision results in a difficult search problem at training time. The model must search for a program that when ex- ecuted leads to the correct target state. Early work employed lexicons and grammars to con- strain the search space (Clarke et al., 2010; Liang et al., 2011; Krishnamurthy and Mitchell, 2012; Berant et al., 2013; Artzi and Zettlemoyer, 2013), but recent success of sequence-to-sequence mod- els (Sutskever et al., 2014) shifted most of the bur- den to learning. Search is often performed sim- ply using beam search, where program tokens are emitted from left-to-right, or program trees are generated top-down (Krishnamurthy et al., 2017; Yin and Neubig, 2017; Cheng et al., 2017; Ra- binovich et al., 2017) or bottom-up (Liang et al., 2017; Guu et al., 2017; Goldman et al., 2018). Nevertheless, when instructions are long and com- plex and reward is sparse, the model may never find enough correct programs, and training will fail. In this paper, we propose a novel search algo- rithm …

Content truncated to 500 words