Graph Algebraic Combinatory Categorial Grammar

Proceedings of the 7th Joint Conference on Lexical and Computational Semantics (*SEM), pages 54–64 New Orleans, June 5-6, 2018. c⃝2018 Association for Computational Linguistics Graph Algebraic Combinatory Categorial Grammar Sebastian Beschke Wolfgang Menzel Department of Informatics University of Hamburg Vogt-Kölln-Straße 30, 22527 Hamburg, Germany {beschke,menzel}@informatik.uni-hamburg.de Abstract This paper describes CCG/AMR, a novel grammar for semantic parsing of Abstract Meaning Representations. CCG/AMR equips Combinatory Categorial Grammar derivations with graph semantics by assigning each CCG combinator an interpretation in terms of a graph algebra. We provide an algorithm that induces a CCG/AMR from a corpus and show that it cre- ates a compact lexicon with low ambiguity and achieves a robust coverage of 78% of the ex- amined sentences under ideal conditions. We also identify several phenomena that affect any approach relying either on CCG or graph algebraic approaches for AMR parsing. This includes differences of representation between CCG and AMR, as well as non-compositional constructions that are not expressible through a monotonic construction process. To our knowledge, this paper provides the first anal- ysis of these corpus issues. 1 Introduction With the release of the Abstract Meaning Rep- resentation (AMR) corpus (Knight et al., 2014), graph representations of meaning have taken cen- tre stage in research on semantic parsing. Se- mantic parsing systems have to address the prob- lem of lexicon induction: extracting reusable lexi- cal items from the sentential meaning representa- tions annotated in the AMR corpus. Since the cor- pus contains sentential meaning representations, but no indication of their compositional structure, derivations of the meaning representation cannot be observed. Common approaches enumerate all conceivable lexical items that may have con- tributed to the derivation of the meaning represen- tation at hand (Artzi et al., 2015; Groschwitz et al., 2017). This may produce very large lexicons with high degrees of ambiguity, and therefore require large amounts of computational resources during parsing. One central contribution of this paper is a lexicon induction algorithm that produces a rel- atively compact lexicon. Combinatory Categorial Grammar (CCG) uses a transparent syntax-semantic interface that con- structs meaning representations using λ-calculus. This makes lexicon induction challenging, as in- ducing λ-calculus terms essentially requires solv- ing higher-order unification (Kwiatkowski et al., 2010). In practice, heuristics are employed to manage the search space, but it would be prefer- able to make use of a less powerful mechanism which better fits the problem domain. Graph alge- bras such as the HR algebra (Courcelle and Engel- friet, 2012) constitute such a constrained mecha- nism. By combining CCG with the HR algebra, we are able to leverage the availability of syntac- tic parsers for CCG while making use of tailored semantic construction operations. 1.1 Related Work There is an extensive body of work on seman- tic parsing of AMRs, using a range of techniques including maximum spanning tree-based parsing (Flanigan et al., 2014), transition-based parsing (Wang et al., 2015; Ballesteros and Al-Onaizan, 2017; Peng et al., 2018), machine translation (van Noord and Bos, 2017), graph grammars (Peng et al., 2015; Groschwitz …

Content truncated to 500 words