Imitation Learning of Agenda-based Semantic Parsers

Imitation Learning of Agenda-based Semantic Parsers Jonathan Berant Stanford University yonatan@cs.stanford.edu Percy Liang Stanford University pliang@cs.stanford.edu Abstract Semantic parsers conventionally construct logical forms bottom-up in a fixed order, re- sulting in the generation of many extraneous partial logical forms. In this paper, we com- bine ideas from imitation learning and agenda- based parsing to train a semantic parser that searches partial logical forms in a more strate- gic order. Empirically, our parser reduces the number of constructed partial logical forms by an order of magnitude, and obtains a 6x-9x speedup over fixed-order parsing, while main- taining comparable accuracy. 1 Introduction Semantic parsing, the task of mapping natural language to semantic representations (e.g., log- ical forms), has emerged in recent years as a promising paradigm for developing question an- swering systems (Zelle and Mooney, 1996; Zettle- moyer and Collins, 2005; Wong and Mooney, 2007; Kwiatkowski et al., 2010; Liang et al., 2011) and other natural language interfaces (Zettlemoyer and Collins, 2007; Tellex et al., 2011; Matuszek et al., 2012). Recently, there have been two ma- jor trends: The first is to scale semantic parsing to large knowledge bases (KB) such as Freebase (Cai and Yates, 2013; Kwiatkowski et al., 2013; Berant and Liang, 2014). The second is to learn semantic parsers without relying on annotated logical forms, but instead on their denotations (answers) (Clarke et al., 2010; Liang et al., 2011); this lessens the anno- tation burden and has been instrumental in fueling the first trend (Berant et al., 2013). what city was abraham lincoln born in 391 508 362 20 20 >1M Type.City ⊓ PlaceOfBirthOf.AbeLincoln Type.Loc ⊓ ContainedBy.LincolnTown . . . AbeLincoln LincolnTown USSLincoln . . . Type.City Type.Loc . . . PlaceOfBirthOf PlacesLived . . . Figure 1: A parsing chart for the utterance “what city was abraham lincoln born in”. Numbers in chart cells indicate the number of possible semantic parses constructed over that span, and arrows point to some of the logical forms that were con- structed. There are more than one million possible semantic parses for this utterance. In this paper, we are interested in training seman- tic parsers from denotations on large KBs. The chal- lenge in this setting is that the vocabulary of the target logical language often contains thousands of logical predicates, and there is a mismatch between the structure of the natural language and the logical language. As a result, the space of possible seman- tic parses for even a short utterance grows quickly. For example, consider the utterance “what city was abraham lincoln born in”. Figure 1 illustrates the number of possible semantic parses that can be con- structed over some of the utterance spans. Just by combining semantic parses over the spans “city”, “lincoln” and “born” we already obtain 362·391·20 possible parses; at the root, we get over a million parses.1 The ambiguity of language thus results in a 1 Even when type constraints are used to prune parses, we still produce more than a million possible parses at the …

Content truncated to 500 words