End-to-End Graph-Based TAG Parsing with Neural Networks

Proceedings of NAACL-HLT 2018, pages 1181–1194 New Orleans, Louisiana, June 1 - 6, 2018. c⃝2018 Association for Computational Linguistics End-to-end Graph-based TAG Parsing with Neural Networks Jungo Kasai♣ Robert Frank♣ Pauli Xu♣ William Merrill♣ Owen Rambow♥ ♣Department of Linguistics, Yale University ♥Elemental Cognition, LLP {jungo.kasai,bob.frank,pauli.xu,william.merrill}@yale.edu owenr@elementalcognition.com Abstract We present a graph-based Tree Adjoin- ing Grammar (TAG) parser that uses BiL- STMs, highway connections, and character- level CNNs. Our best end-to-end parser, which jointly performs supertagging, POS tag- ging, and parsing, outperforms the previously reported best results by more than 2.2 LAS and UAS points. The graph-based parsing architecture allows for global inference and rich feature representations for TAG parsing, alleviating the fundamental trade-off between transition-based and graph-based parsing sys- tems. We also demonstrate that the proposed parser achieves state-of-the-art performance in the downstream tasks of Parsing Evaluation using Textual Entailments (PETE) and Un- bounded Dependency Recovery. This provides further support for the claim that TAG is a vi- able formalism for problems that require rich structural analysis of sentences. 1 Introduction Tree Adjoining Grammar (TAG, Joshi and Sch- abes (1997)) and Combinatory Categorial Gram- mar (CCG, Steedman and Baldridge (2011)) are both mildly context-sensitive grammar formalisms that are lexicalized: every elementary structure (elementary tree for TAG and category for CCG) is associated with exactly one lexical item, and ev- ery lexical item of the language is associated with a finite set of elementary structures in the gram- mar (Rambow and Joshi, 1994). In TAG and CCG, the task of parsing can be decomposed into two phases (e.g. TAG: Bangalore and Joshi (1999); CCG: Clark and Curran (2007)): supertagging, where elementary units or supertags are assigned to each lexical item and parsing where these su- pertags are combined together. The first phase of supertagging can be considered as “almost pars- ing” because supertags for a sentence almost al- ways determine a unique parse (Bangalore and Joshi, 1999). This near uniqueness of a parse given a gold sequence of supertags has been con- firmed empirically (TAG: Bangalore et al. (2009); Chung et al. (2016); Kasai et al. (2017); CCG: Lewis et al. (2016)). We focus on TAG parsing in this work. TAG differs from CCG in having a more varied set of supertags. Concretely, the TAG-annotated version of the WSJ Penn Treebank (Marcus et al., 1993) that we use (Chen et al., 2005) includes 4727 dis- tinct supertags (2165 occur once) while the CCG- annotated version (Hockenmaier and Steedman, 2007) only includes 1286 distinct supertags (439 occur once). This large set of supertags in TAG presents a severe challenge in supertagging and causes a large discrepancy in parsing performance with gold supertags and predicted supertags (Ban- galore et al., 2009; Chung et al., 2016; Kasai et al., 2017). In this work, we present a supertagger and a parser that substantially improve upon previously reported results. We propose crucial modifications to the bidirectional LSTM (BiLSTM) supertagger in Kasai et al. (2017). First, we use character-level Convolutional Neural Networks (CNNs) for en- coding morphological …

Content truncated to 500 words