Learning Dependency-Based Compositional Semantics

Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics, pages 590–599, Portland, Oregon, June 19-24, 2011. c⃝2011 Association for Computational Linguistics Learning Dependency-Based Compositional Semantics Percy Liang UC Berkeley pliang@cs.berkeley.edu Michael I. Jordan UC Berkeley jordan@cs.berkeley.edu Dan Klein UC Berkeley klein@cs.berkeley.edu Abstract Compositional question answering begins by mapping questions to logical forms, but train- ing a semantic parser to perform this mapping typically requires the costly annotation of the target logical forms. In this paper, we learn to map questions to answers via latent log- ical forms, which are induced automatically from question-answer pairs. In tackling this challenging learning problem, we introduce a new semantic representation which highlights a parallel between dependency syntax and effi- cient evaluation of logical forms. On two stan- dard semantic parsing benchmarks (GEO and JOBS), our system obtains the highest pub- lished accuracies, despite requiring no anno- tated logical forms. 1 Introduction What is the total population of the ten largest cap- itals in the US? Answering these types of complex questions compositionally involves first mapping the questions into logical forms (semantic parsing). Su- pervised semantic parsers (Zelle and Mooney, 1996; Tang and Mooney, 2001; Ge and Mooney, 2005; Zettlemoyer and Collins, 2005; Kate and Mooney, 2007; Zettlemoyer and Collins, 2007; Wong and Mooney, 2007; Kwiatkowski et al., 2010) rely on manual annotation of logical forms, which is expen- sive. On the other hand, existing unsupervised se- mantic parsers (Poon and Domingos, 2009) do not handle deeper linguistic phenomena such as quan- tification, negation, and superlatives. As in Clarke et al. (2010), we obviate the need for annotated logical forms by considering the end- to-end problem of mapping questions to answers. However, we still model the logical form (now as a latent variable) to capture the complexities of lan- guage. Figure 1 shows our probabilistic model: (parameters) (world) θ w x z y (question) (logical form) (answer) state with the largest area x1 x1 1 1 c argmax area state ∗∗ Alaska z ∼ pθ(z | x) y = �z�w Semantic Parsing Evaluation Figure 1: Our probabilistic model: a question x is mapped to a latent logical form z, which is then evaluated with respect to a world w (database of facts), producing an answer y. We represent logical forms z as labeled trees, induced automatically from (x, y) pairs. We want to induce latent logical forms z (and pa- rameters θ) given only question-answer pairs (x, y), which is much cheaper to obtain than (x, z) pairs. The core problem that arises in this setting is pro- gram induction: finding a logical form z (over an exponentially large space of possibilities) that pro- duces the target answer y. Unlike standard semantic parsing, our end goal is only to generate the correct y, so we are free to choose the representation for z. Which one should we use? The dominant paradigm in compositional se- mantics is Montague semantics, which constructs lambda calculus forms in a bottom-up manner. CCG is one instantiation (Steedman, …

Content truncated to 500 words