Inspecting the Structural Biases of Dependency Parsing Algorithms

Proceedings of the Fourteenth Conference on Computational Natural Language Learning, pages 234–242, Uppsala, Sweden, 15-16 July 2010. c⃝2010 Association for Computational Linguistics Inspecting the Structural Biases of Dependency Parsing Algorithms ∗ Yoav Goldberg and Michael Elhadad Ben Gurion University of the Negev Department of Computer Science POB 653 Be’er Sheva, 84105, Israel yoavg|elhadad@cs.bgu.ac.il Abstract We propose the notion of a structural bias inherent in a parsing system with respect to the language it is aiming to parse. This structural bias characterizes the behaviour of a parsing system in terms of structures it tends to under- and over- produce. We propose a Boosting-based method for un- covering some of the structural bias inher- ent in parsing systems. We then apply our method to four English dependency parsers (an Arc-Eager and Arc-Standard transition-based parsers, and first- and second-order graph-based parsers). We show that all four parsers are biased with respect to the kind of annotation they are trained to parse. We present a detailed analysis of the biases that highlights spe- cific differences and commonalities be- tween the parsing systems, and improves our understanding of their strengths and weaknesses. 1 Introduction Dependency Parsing, the task of inferring a depen- dency structure over an input sentence, has gained a lot of research attention in the last couple of years, due in part to to the two CoNLL shared tasks (Nivre et al., 2007; Buchholz and Marsi, 2006) in which various dependency parsing algo- rithms were compared on various data sets. As a result of this research effort, we have a choice of several robust, efficient and accurate parsing algo- rithms. ∗We would like to thank Reut Tsarfaty for comments and discussions that helped us improve this paper. This work is supported in part by the Lynn and William Frankel Center for Computer Science. These different parsing systems achieve com- parable scores, yet produce qualitatively different parses. Sagae and Lavie (2006) demonstrated that a simple combination scheme of the outputs of dif- ferent parsers can obtain substantially improved accuracies. Nivre and McDonald (2008) explore a parser stacking approach in which the output of one parser is fed as an input to a different kind of parser. The stacking approach also produces more accurate parses. However, while we know how to produce accu- rate parsers and how to blend and stack their out- puts, little effort was directed toward understand- ing the behavior of different parsing systems in terms of structures they produce and errors they make. Question such as which linguistic phenom- ena are hard for parser Y? and what kinds of er- rors are common for parser Z?, as well as the more ambitious which parsing approach is most suitable to parse language X?, remain largely unanswered. The current work aims to fill this gap by propos- ing a methodology to identify systematic biases in various parsing models and proposing and initial analysis of such biases. McDonald and Nivre (2007) analyze the dif- ference between graph-based and transition-based parsers (specifically the MALT and …

Content truncated to 500 words