The Best of Both Worlds – A Graph-based Completion Model for Transition-based Parsers

Proceedings of the 13th Conference of the European Chapter of the Association for Computational Linguistics, pages 77–87, Avignon, France, April 23 - 27 2012. c⃝2012 Association for Computational Linguistics The Best of Both Worlds – A Graph-based Completion Model for Transition-based Parsers Bernd Bohnet and Jonas Kuhn University of Stuttgart Institute for Natural Language Processing {bohnet,jonas}@ims.uni-stuttgart.de Abstract Transition-based dependency parsers are often forced to make attachment deci- sions at a point when only partial infor- mation about the relevant graph configu- ration is available. In this paper, we de- scribe a model that takes into account com- plete structures as they become available to rescore the elements of a beam, com- bining the advantages of transition-based and graph-based approaches. We also pro- pose an efficient implementation that al- lows for the use of sophisticated features and show that the completion model leads to a substantial increase in accuracy. We apply the new transition-based parser on ty- pologically different languages such as En- glish, Chinese, Czech, and German and re- port competitive labeled and unlabeled at- tachment scores. 1 Introduction Background. A considerable amount of recent research has gone into data-driven dependency parsing, and interestingly throughout the continu- ous process of improvements, two classes of pars- ing algorithms have stayed at the centre of at- tention, the transition-based (Nivre, 2003) vs. the graph-based approach (Eisner, 1996; McDonald et al., 2005).1 The two approaches apply funda- mentally different strategies to solve the task of finding the optimal labeled dependency tree over the words of an input sentence (where supervised machine learning is used to estimate the scoring parameters on a treebank). The transition-based approach is based on the conceptually (and cognitively) compelling idea 1More references will be provided in sec. 2. that machine learning, i.e., a model of linguis- tic experience, is used in exactly those situations when there is an attachment choice in an other- wise deterministic incremental left-to-right pars- ing process. As a new word is processed, the parser has to decide on one out of a small num- ber of possible transitions (adding a dependency arc pointing to the left or right and/or pushing or popping a word on/from a stack representation). Obviously, the learning can be based on the fea- ture information available at a particular snapshot in incremental processing, i.e., only surface in- formation for the unparsed material to the right, but full structural information for the parts of the string already processed. For the completely pro- cessed parts, there are no principled limitations as regards the types of structural configurations that can be checked in feature functions. The graph-based approach in contrast empha- sizes the objective of exhaustive search over all possible trees spanning the input words. Com- monly, dynamic programming techniques are used to decide on the optimal tree for each par- ticular word span, considering all candidate splits into subspans, successively building longer spans in a bottom-up fashion (similar to chart-based constituent parsing). Machine learning drives the process of deciding among alternative can- didate …

Content truncated to 500 words