Type-Driven Incremental Semantic Parsing with Polymorphism

Human Language Technologies: The 2015 Annual Conference of the North American Chapter of the ACL, pages 1416–1421, Denver, Colorado, May 31 – June 5, 2015. c⃝2015 Association for Computational Linguistics Type-Driven Incremental Semantic Parsing with Polymorphism∗ Kai Zhao Graduate Center City University of New York kzhao.hf@gmail.com Liang Huang Queens College and Graduate Center City University of New York liang.huang.sh@gmail.com Abstract Semantic parsing has made significant progress, but most current semantic parsers are extremely slow (CKY-based) and rather primitive in representation. We introduce three new techniques to tackle these problems. First, we design the first linear-time incremental shift-reduce-style semantic parsing al- gorithm which is more efficient than conventional cubic-time bottom-up semantic parsers. Second, our parser, being type-driven instead of syntax-driven, uses type-checking to decide the direction of reduc- tion, which eliminates the need for a syntactic gram- mar such as CCG. Third, to fully exploit the power of type-driven semantic parsing beyond simple types (such as entities and truth values), we borrow from programming language theory the concepts of sub- type polymorphism and parametric polymorphism to enrich the type system in order to better guide the parsing. Our system learns very accurate parses in GEOQUERY, JOBS and ATIS domains. 1 Introduction Most existing semantic parsing efforts employ a CKY- style bottom-up parsing strategy to generate a meaning representation in simply typed lambda calculus (Zettle- moyer and Collins, 2005; Lu and Ng, 2011) or its variants (Wong and Mooney, 2007; Liang et al., 2011). Although these works led to fairly accurate semantic parsers, there are two major drawbacks: efficiency and expressiveness. First, as many researches in syntactic parsing (Nivre, 2008; Zhang and Clark, 2011) have shown, compared to cubic-time CKY-style parsing, incremental parsing can achieve comparable accuracies while being linear-time, and orders of magnitude faster in practice. We therefore introduce the first incremental parsing algorithm for se- mantic parsing. More interestingly, unlike syntactic pars- ing, our incremental semantic parsing algorithm, being strictly type-driven, directly employs type checking to automatically determine the direction of function applica- tion on-the-fly, thus reducing the search space and elimi- ∗We thank the reviewers for helpful suggestions. We are also grate- ful to Luke Zettelmoyer, Yoav Artzi, and Tom Kwiatkowski for pro- viding data. This research is supported by DARPA FA8750-13-2-0041 (DEFT), NSF IIS-1449278, and a Google Faculty Research Award. nating the need for a syntactic grammar such as CCG to explicitly encode the direction of function application. However, to fully exploit the power of type-driven in- cremental parsing, we need a more sophisticated type system than simply typed lambda calculus. Compare the following two phrases: (1) the governor of New York (2) the mayor of New York If we know that governor is a function from state to per- son, then the first New York can only be of type state; sim- ilarly knowing mayor maps city to person disambiguates the second New York to be of type city. This can not be done using a simple type system with just entities and booleans. Now let us …

Content truncated to 500 words