Characterizing the Errors of Data-Driven Dependency Parsing Models

Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, pp. 122–131, Prague, June 2007. c⃝2007 Association for Computational Linguistics Characterizing the Errors of Data-Driven Dependency Parsing Models Ryan McDonald Google Inc. 76 Ninth Avenue New York, NY 10011 ryanmcd@google.com Joakim Nivre V¨axj¨o University Uppsala University 35195 V¨axj¨o 75126 Uppsala Sweden Sweden nivre@msi.vxu.se Abstract We present a comparative error analysis of the two dominant approaches in data- driven dependency parsing: global, exhaus- tive, graph-based models, and local, greedy, transition-based models. We show that, in spite of similar performance overall, the two models produce different types of errors, in a way that can be explained by theoretical properties of the two models. This analysis leads to new directions for parser develop- ment. 1 Introduction Syntactic dependency representations have a long history in descriptive and theoretical linguistics and many formal models have been advanced (Hudson, 1984; Mel’ˇcuk, 1988; Sgall et al., 1986; Maruyama, 1990). A dependency graph of a sentence repre- sents each word and its syntactic modifiers through labeled directed arcs, as shown in Figure 1, taken from the Prague Dependency Treebank (B¨ohmov´a et al., 2003). A primary advantage of dependency rep- resentations is that they have a natural mechanism for representing discontinuous constructions, aris- ing from long distance dependencies or free word order, through non-projective dependency arcs, ex- emplified by the arc from jedna to Z in Figure 1. Syntactic dependency graphs have recently gained a wide interest in the computational lin- guistics community and have been successfully em- ployed for many problems ranging from machine translation (Ding and Palmer, 2004) to ontology Figure 1: Example dependency graph. construction (Snow et al., 2004). In this work we focus on a common parsing paradigm called data- driven dependency parsing. Unlike grammar-based parsing, data-driven approaches learn to produce de- pendency graphs for sentences solely from an anno- tated corpus. The advantage of such models is that they are easily ported to any domain or language in which annotated resources exist. As evident from the CoNLL-X shared task on de- pendency parsing (Buchholz and Marsi, 2006), there are currently two dominant models for data-driven dependency parsing. The first is what Buchholz and Marsi (2006) call the “all-pairs” approach, where ev- ery possible arc is considered in the construction of the optimal parse. The second is the “stepwise” ap- proach, where the optimal parse is built stepwise and where the subset of possible arcs considered depend on previous decisions. Theoretically, these models are extremely different. The all-pairs models are globally trained, use exact (or near exact) inference algorithms, and define features over a limited history of parsing decisions. The stepwise models use local training and greedy inference algorithms, but define features over a rich history of parse decisions. How- ever, both models obtain similar parsing accuracies 122 McDonald Nivre Arabic 66.91 66.71 Bulgarian 87.57 87.41 Chinese 85.90 86.92 Czech 80.18 78.42 Danish 84.79 84.77 Dutch 79.19 78.59 German 87.34 85.82 Japanese 90.71 91.65 Portuguese 86.82 87.60 …

Content truncated to 500 words