Deep Contextualized Word Embeddings in Transition-Based and Graph-Based Dependency Parsing - A Tale of Two Parsers Revisited

Deep Contextualized Word Embeddings in Transition-Based and Graph-Based Dependency Parsing – A Tale of Two Parsers Revisited∗ Artur Kulmizev Miryam de Lhoneux Johannes Gontrum Elena Fano Joakim Nivre Department of Linguistics and Philology, Uppsala University {artur.kulmizev,miryam.de lhoneux,joakim.nivre}@lingfil.uu.se {johannes.gontrum.4608,elena.fano.3249}@student.uu.se Abstract Transition-based and graph-based dependency parsers have previously been shown to have complementary strengths and weaknesses: transition-based parsers exploit rich structural features but suffer from error propagation, while graph-based parsers benefit from global optimization but have restricted feature scope. In this paper, we show that, even though some details of the picture have changed after the switch to neural networks and continuous rep- resentations, the basic trade-off between rich features and global optimization remains es- sentially the same. Moreover, we show that deep contextualized word embeddings, which allow parsers to pack information about global sentence structure into local feature represen- tations, benefit transition-based parsers more than graph-based parsers, making the two ap- proaches virtually equivalent in terms of both accuracy and error profile. We argue that the reason is that these representations help pre- vent search errors and thereby allow transition- based parsers to better exploit their inherent strength of making accurate local decisions. We support this explanation by an error analy- sis of parsing experiments on 13 languages. 1 Introduction For more than a decade, research on data-driven dependency parsing has been dominated by two approaches: transition-based parsing and graph- based parsing (McDonald and Nivre, 2007, 2011). Transition-based parsing reduces the parsing task to scoring single parse actions and is often com- bined with local optimization and greedy search algorithms. Graph-based parsing decomposes parse trees into subgraphs and relies on global op- timization and exhaustive (or at least non-greedy) ∗We gratefully acknowledge the inspiration for our sub- title in the seminal paper by Zhang and Clark (2008). search to find the best tree. These radically differ- ent approaches often lead to comparable parsing accuracy, but with distinct error profiles indicative of their respective strengths and weaknesses, as shown by McDonald and Nivre (2007, 2011). In recent years, dependency parsing, like most of NLP, has shifted from linear models and dis- crete features to neural networks and continu- ous representations. This has led to substantial accuracy improvements for both transition-based and graph-based parsers and raises the question whether their complementary strengths and weak- nesses are still relevant. In this paper, we repli- cate the analysis of McDonald and Nivre (2007, 2011) for neural parsers. In addition, we investi- gate the impact of deep contextualized word repre- sentations (Peters et al., 2018; Devlin et al., 2019) for both types of parsers. Based on what we know about the strengths and weaknesses of the two approaches, we hypothe- size that deep contextualized word representations will benefit transition-based parsing more than graph-based parsing. The reason is that these rep- resentations make information about global sen- tence structure available locally, thereby helping to prevent search errors in greedy transition-based parsing. The hypothesis is corroborated in ex- periments on 13 languages, and the error analysis supports our …

Content truncated to 500 words