Macro Grammars and Holistic Triggering for Efficient Semantic Parsing

Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pages 1214–1223 Copenhagen, Denmark, September 7–11, 2017. c⃝2017 Association for Computational Linguistics Macro Grammars and Holistic Triggering for Efficient Semantic Parsing Yuchen Zhang and Panupong Pasupat and Percy Liang {zhangyuc,ppasupat,pliang}@cs.stanford.edu Computer Science Department, Stanford University Abstract To learn a semantic parser from denota- tions, a learning algorithm must search over a combinatorially large space of log- ical forms for ones consistent with the an- notated denotations. We propose a new online learning algorithm that searches faster as training progresses. The two key ideas are using macro grammars to cache the abstract patterns of useful log- ical forms found thus far, and holistic trig- gering to efficiently retrieve the most rele- vant patterns based on sentence similarity. On the WIKITABLEQUESTIONS dataset, we first expand the search space of an ex- isting model to improve the state-of-the- art accuracy from 38.7% to 42.7%, and then use macro grammars and holistic trig- gering to achieve an 11x speedup and an accuracy of 43.7%. 1 Introduction We consider the task of learning a semantic parser for question answering from question- answer pairs (Clarke et al., 2010; Liang et al., 2011; Berant et al., 2013; Artzi and Zettlemoyer, 2013; Pasupat and Liang, 2015). To train such a parser, the learning algorithm must somehow search for consistent logical forms (i.e., logical forms that execute to the correct answer denota- tion). Typically, the search space is defined by a compositional grammar over logical forms (e.g., a context-free grammar), which we will refer to as the base grammar. To cover logical forms that answer complex questions, the base grammar must be quite general and compositional, leading to a huge search space that contains many useless logical forms. For ex- ample, the parser of Pasupat and Liang (2015) on Rank Nation Gold Silver Bronze r1 : 1 France 3 1 1 r2 : 2 Ukraine 2 1 2 r3 : 3 Turkey 2 0 1 r4 : 4 Sweden 2 0 0 r5 : 5 Iran 1 2 1 Table 1: A knowledge base for the question x = “Who ranked right after Turkey?”. The target de- notation is y = {Sweden}. Wikipedia table questions (with beam size 100) generates and featurizes an average of 8,400 par- tial logical forms per example. Searching for con- sistent logical forms is thus a major computational bottleneck. In this paper, we propose macro grammars to bias the search towards structurally sensible logi- cal forms. To illustrate the key idea, suppose we managed to parse the utterance “Who ranked right after Turkey?” in the context of Table 1 into the following consistent logical form (in lambda DCS) (Section 2.1): R[Nation].R[Next].Nation.Turkey, which identifies the cell under the Nation column in the row after Turkey. From this logical form, we can abstract out all relations and entities to pro- duce the following macro: R[{Rel#1}].R[Next].{Rel#1}.{Ent#2}, which represents the abstract computation: “iden- tify the cell under the {Rel#1} column in the row after {Ent#2}.” More …

Content truncated to 500 words