Inferring Logical Forms From Denotations

Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics, pages 23–32, Berlin, Germany, August 7-12, 2016. c⃝2016 Association for Computational Linguistics Inferring Logical Forms From Denotations Panupong Pasupat Computer Science Department Stanford University ppasupat@cs.stanford.edu Percy Liang Computer Science Department Stanford University pliang@cs.stanford.edu Abstract A core problem in learning semantic parsers from denotations is picking out consistent logical forms—those that yield the correct denotation—from a combina- torially large space. To control the search space, previous work relied on restricted set of rules, which limits expressivity. In this paper, we consider a much more ex- pressive class of logical forms, and show how to use dynamic programming to effi- ciently represent the complete set of con- sistent logical forms. Expressivity also introduces many more spurious logical forms which are consistent with the cor- rect denotation but do not represent the meaning of the utterance. To address this, we generate fictitious worlds and use crowdsourced denotations on these worlds to filter out spurious logical forms. On the WIKITABLEQUESTIONS dataset, we increase the coverage of answerable ques- tions from 53.5% to 76%, and the ad- ditional crowdsourced supervision lets us rule out 92.1% of spurious logical forms. 1 Introduction Consider the task of learning to answer com- plex natural language questions (e.g., “Where did the last 1st place finish occur?”) using only question-answer pairs as supervision (Clarke et al., 2010; Liang et al., 2011; Berant et al., 2013; Artzi and Zettlemoyer, 2013). Seman- tic parsers map the question into a logical form (e.g., R[Venue].argmax(Position.1st, Index)) that can be executed on a knowledge source to ob- tain the answer (denotation). Logical forms are very expressive since they can be recursively com- posed, but this very expressivity makes it more difficult to search over the space of logical forms. Previous work sidesteps this obstacle by restrict- ing the set of possible logical form compositions, but this is limiting. For instance, for the system in Pasupat and Liang (2015), in only 53.5% of the examples was the correct logical form even in the set of generated logical forms. The goal of this paper is to solve two main chal- lenges that prevent us from generating more ex- pressive logical forms. The first challenge is com- putational: the number of logical forms grows ex- ponentially as their size increases. Directly enu- merating over all logical forms becomes infeasi- ble, and pruning techniques such as beam search can inadvertently prune out correct logical forms. The second challenge is the large increase in spurious logical forms—those that do not reflect the semantics of the question but coincidentally execute to the correct denotation. For example, while logical forms z1, . . . , z5 in Figure 1 are all consistent (they execute to the correct answer y), the logical forms z4 and z5 are spurious and would give incorrect answers if the table were to change. We address these two challenges by solving two interconnected tasks. The first task, which ad- dresses the computational challenge, is to enumer- …

Content truncated to 500 words