Analyzing the Effect of Global Learning and Beam-Search on Transition-Based Dependency Parsing
Yue Zhang, Joakim Nivre · International Conference on Computational Linguistics · 2012
Beam-search and global models have been applied to transition-based dependency parsing, leading to state-of-the-art accuracies that are comparable to the best graph-based parsers. In this paper, we analyze the effects of global learning and beam-search on the overall accuracy and error distribution of a transition-based dependency parser. First, we show that global learning and beam-search must be jointly applied to give improvements over greedy, locally trained parsing. We then show that in addition to the reduction of error propagation, an important advantage of the combination of global learning and beam-search is that it accommodates more powerful parsing models without overfitting. Finally, we characterize the errors of a global, beam-search, transition-based parser, relating it to the classic contrast between “local, greedy, transition-based parsing” and “global, exhaustive, graph-based parsing”.