Reading between the Lines: Learning to Map High-Level Instructions to Commands

Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, pages 1268–1277, Uppsala, Sweden, 11-16 July 2010. c⃝2010 Association for Computational Linguistics Reading Between the Lines: Learning to Map High-level Instructions to Commands S.R.K. Branavan, Luke S. Zettlemoyer, Regina Barzilay Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology {branavan, lsz, regina}@csail.mit.edu Abstract In this paper, we address the task of mapping high-level instructions to se- quences of commands in an external en- vironment. Processing these instructions is challenging—they posit goals to be achieved without specifying the steps re- quired to complete them. We describe a method that fills in missing informa- tion using an automatically derived envi- ronment model that encodes states, tran- sitions, and commands that cause these transitions to happen. We present an ef- ficient approximate approach for learning this environment model as part of a policy- gradient reinforcement learning algorithm for text interpretation. This design enables learning for mapping high-level instruc- tions, which previous statistical methods cannot handle.1 1 Introduction In this paper, we introduce a novel method for mapping high-level instructions to commands in an external environment. These instructions spec- ify goals to be achieved without explicitly stat- ing all the required steps. For example, consider the first instruction in Figure 1 — “open control panel.” The three GUI commands required for its successful execution are not explicitly described in the text, and need to be inferred by the user. This dependence on domain knowledge makes the automatic interpretation of high-level instructions particularly challenging. The standard approach to this task is to start with both a manually-developed model of the en- vironment, and rules for interpreting high-level in- structions in the context of this model (Agre and 1Code, data, and annotations used in this work are avail- able at http://groups.csail.mit.edu/rbg/code/rl-hli/ Chapman, 1988; Di Eugenio and White, 1992; Di Eugenio, 1992; Webber et al., 1995). Given both the model and the rules, logic-based infer- ence is used to automatically fill in the intermedi- ate steps missing from the original instructions. Our approach, in contrast, operates directly on the textual instructions in the context of the in- teractive environment, while requiring no addi- tional information. By interacting with the en- vironment and observing the resulting feedback, our method automatically learns both the mapping between the text and the commands, and the un- derlying model of the environment. One partic- ularly noteworthy aspect of our solution is the in- terplay between the evolving mapping and the pro- gressively acquired environment model as the sys- tem learns how to interpret the text. Recording the state transitions observed during interpretation al- lows the algorithm to construct a relevant model of the environment. At the same time, the envi- ronment model enables the algorithm to consider the consequences of commands before they are ex- ecuted, thereby improving the accuracy of inter- pretation. Our method efficiently achieves both of these goals as part of a policy-gradient reinforce- ment learning algorithm. We apply our method to the task of mapping …

Content truncated to 500 words