Recurrent models and lower bounds for projective syntactic decoding

Proceedings of NAACL-HLT 2019, pages 251–260 Minneapolis, Minnesota, June 2 - June 7, 2019. c⃝2019 Association for Computational Linguistics 251 Recurrent Models and Lower Bounds for Projective Syntactic Decoding Natalie Schluter IT University of Copenhagen Copenhagen, Denmark natschluter@itu.dk Abstract The current state-of-the-art in neural graph- based parsing uses only approximate decoding at the training phase. In this paper aim to un- derstand this result better. We show how recur- rent models can carry out projective maximum spanning tree decoding. This result holds for both current state-of-the-art models for shift- reduce and graph-based parsers, projective or not. We also provide the first proof on the lower bounds of projective maximum span- ning tree, DAG, and digraph decoding. 1 Introduction For several years, the NLP field has seen widespread investigation into the application of Neural Networks to NLP tasks, and with this, much, rather inexplicable progress. A string of very recent work (for example, Chen et al. (2018); Weiss et al. (2018); Peng et al. (2018)), has at- tempted to delve into the formal properties of neu- ral network topology choices, in attempts to both motivate, predict, and explain associated research in the field. This paper aims to further contribute along this line of research. We present the results of our study into the ability of state-of-the-art first-order neural graph- based parsers, with seemingly simple architec- tures, to explicitly forego structured learning and prediction.1 In particular, this is not due to a significantly faster, simpler, algorithm for pro- jective maximum spanning tree (MST) decoding than Eisner (1996)’s algorithm, which we for- mally prove to be impossible, given the Exponen- tial Time Hypothesis. But rather, this is due to the capacity of recurrent components of these archi- tectures to implicitly discover a projective MST. We prove this formally by showing how these re- 1For the remainder of this paper, all decoding algorithms discussed are first-order. current components can intrinsically simulate ex- act projective decoding. The context. The current state-of-the-art for graph-based syntactic dependency parsing is a seemingly basic neural model by Dozat and Man- ning (2017). The parser’s performance is an improvement on the first, even simpler, rather engineering-free, neural graph-based parser by Kiperwasser and Goldberg (2016). This latter parser updates with respect to an output structure: projective decoding over a matrix of arc scores coupled with hinge loss between predicted and gold arcs, reporting parser performance of, for example, 93.32% UAS and 91.2% LAS on the converted Penn Treebank.2 Remarkably, the for- mer parser by Dozat and Manning (2017) forgoes entirely any structural learning, employing sim- ple cross-entropy at training time, and saving (un- constrained) maximum spanning tree decoding for test time. We further optimised Kiperwasser and Gold- berg (2016)’s parser (Varab and Schluter, 2018) and extended it for cross-entropy learning, as is done by Dozat and Manning (2017). At test time, instead of any explicit decoding algorithm over the arc score matrix, we simply take the maxi- mum weighted incoming arc for each word; that is, the parser is highly streamlined, …

Content truncated to 500 words