Online Learning of Relaxed CCG Grammars for Parsing to Logical Form

Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, pp. 678–687, Prague, June 2007. c⃝2007 Association for Computational Linguistics Online Learning of Relaxed CCG Grammars for Parsing to Logical Form Luke S. Zettlemoyer and Michael Collins MIT CSAIL lsz@csail.mit.edu,mcollins@csail.mit.edu Abstract We consider the problem of learning to parse sentences to lambda-calculus repre- sentations of their underlying semantics and present an algorithm that learns a weighted combinatory categorial grammar (CCG). A key idea is to introduce non-standard CCG combinators that relax certain parts of the grammar—for example allowing flexible word order, or insertion of lexical items— with learned costs. We also present a new, online algorithm for inducing a weighted CCG. Results for the approach on ATIS data show 86% F-measure in recovering fully correct semantic analyses and 95.9% F-measure by a partial-match criterion, a more than 5% improvement over the 90.3% partial-match figure reported by He and Young (2006). 1 Introduction Recent work (Mooney, 2007; He and Young, 2006; Zettlemoyer and Collins, 2005) has developed learn- ing algorithms for the problem of mapping sentences to underlying semantic representations. In one such approach (Zettlemoyer and Collins, 2005) (ZC05), the input to the learning algorithm is a training set consisting of sentences paired with lambda-calculus expressions. For instance, the training data might contain the following example: Sentence: list flights to boston Logical Form: λx.flight(x) ∧ to(x, boston) In this case the lambda-calculus expression denotes the set of all flights that land in Boston. In ZC05 it is assumed that training examples do not include additional information, for example parse trees or a) on may four atlanta to denver delta flight 257 λx.month(x, may) ∧ day number(x, fourth)∧ from(x, atlanta) ∧ to(x, denver)∧ airline(x, delta air lines) ∧ flight(x)∧ flight number(x, 257) b) show me information on american airlines from fort worth texas to philadelphia λx.airline(x, american airlines)∧ from(x, fort worth) ∧ to(x, philadelphia) c) okay that one’s great too now we’re going to go on april twenty second dallas to washington the latest nighttime departure one way argmax(λx.flight(x) ∧ from(x, dallas)∧ to(x, washington) ∧ month(x, april)∧ day number(x, 22) ∧ during(x, night)∧ one way(x), λy.depart time(y)) Figure 1: Three sentences from the ATIS domain. other derivations. The output from the learning algo- rithm is a combinatory categorial grammar (CCG), together with parameters that define a log-linear dis- tribution over parses under the grammar. Experi- ments show that the approach gives high accuracy on two database-query problems, introduced by Zelle and Mooney (1996) and Tang and Mooney (2000). The use of a detailed grammatical formalism such as CCG has the advantage that it allows a system to handle quite complex semantic effects, such as co- ordination or scoping phenomena. In particular, it allows us to leverage the considerable body of work on semantics within these formalisms, for example see Carpenter (1997). However, a grammar based on a formalism such as CCG can be somewhat rigid, and this can cause problems when a system is …

Content truncated to 500 words