Transforming Dependency Structures to Logical Forms for Semantic Parsing

Transforming Dependency Structures to Logical Forms for Semantic Parsing Siva Reddy†a Oscar T¨ackstr¨om‡ Michael Collins‡b Tom Kwiatkowski‡ Dipanjan Das‡ Mark Steedman† Mirella Lapata† †ILCC, School of Informatics, University of Edinburgh ‡ Google, New York siva.reddy@ed.ac.uk {oscart, mjcollins, tomkwiat, dipanjand}@google.com {steedman, mlap}@inf.ed.ac.uk Abstract The strongly typed syntax of grammar for- malisms such as CCG, TAG, LFG and HPSG offers a synchronous framework for deriving syntactic structures and semantic logical forms. In contrast—partly due to the lack of a strong type system—dependency structures are easy to annotate and have become a widely used form of syntactic analysis for many languages. However, the lack of a type system makes a formal mechanism for deriving logical forms from dependency structures challenging. We address this by introducing a robust system based on the lambda calculus for deriving neo- Davidsonian logical forms from dependency trees. These logical forms are then used for semantic parsing of natural language to Free- base. Experiments on the Free917 and Web- Questions datasets show that our representation is superior to the original dependency trees and that it outperforms a CCG-based representa- tion on this task. Compared to prior work, we obtain the strongest result to date on Free917 and competitive results on WebQuestions. 1 Introduction Semantic parsers map sentences onto logical forms that can be used to query databases (Zettlemoyer and Collins, 2005; Wong and Mooney, 2006), instruct robots (Chen and Mooney, 2011), extract information (Krishnamurthy and Mitchell, 2012), or describe vi- sual scenes (Matuszek et al., 2012). Current systems accomplish this by learning task-specific grammars (Berant et al., 2013), by using strongly-typed CCG grammars (Reddy et al., 2014), or by eschewing the use of a grammar entirely (Yih et al., 2015). aWork carried out during an internship at Google. bOn leave from Columbia University. Disney acquired Pixar nnp vbd nnp nsubj dobj root (a) The dependency tree for Disney acquired Pixar. (nsubj (dobj acquired Pixar) Disney) (b) The s-expression for the dependency tree. λx. ∃yz. acquired(xe) ∧ Disney(ya) ∧ Pixar(za) ∧ arg1(xe, ya) ∧ arg2(xe, za) (c) The composed lambda-calculus expression. Figure 1: The dependency tree is binarized into its s-expression, which is then composed into the lambda expression representing the sentence logical form. In recent years, there have been significant ad- vances in developing fast and accurate dependency parsers for many languages (McDonald et al., 2005; Nivre et al., 2007; Martins et al., 2013, inter alia). Motivated by the desire to carry these advances over to semantic parsing tasks, we present a robust method for mapping dependency trees to logical forms that represent underlying predicate-argument structures.1 We empirically validate the utility of these logical forms for question answering from databases. Since our approach uses dependency trees as input, we hy- pothesize that it will generalize better to domains that are well covered by dependency parsers than methods that induce semantic grammars from scratch. The system that maps a dependency tree to its log- ical form (henceforth DEPLAMBDA) is illustrated in Figure 1. First, the dependency tree is binarized via …

Content truncated to 500 words