K-best Spanning Tree Parsing

Proceedings of the 45th Annual Meeting of the Association of Computational Linguistics, pages 392–399, Prague, Czech Republic, June 2007. c⃝2007 Association for Computational Linguistics k-best Spanning Tree Parsing Keith Hall Center for Language and Speech Processing Johns Hopkins University Baltimore, MD 21218 keith hall@jhu.edu Abstract This paper introduces a Maximum Entropy dependency parser based on an efficient k- best Maximum Spanning Tree (MST) algo- rithm. Although recent work suggests that the edge-factored constraints of the MST al- gorithm significantly inhibit parsing accu- racy, we show that generating the 50-best parses according to an edge-factored model has an oracle performance well above the 1-best performance of the best dependency parsers. This motivates our parsing ap- proach, which is based on reranking the k- best parses generated by an edge-factored model. Oracle parse accuracy results are presented for the edge-factored model and 1-best results for the reranker on eight lan- guages (seven from CoNLL-X and English). 1 Introduction The Maximum Spanning Tree algorithm1 was re- cently introduced as a viable solution for non- projective dependency parsing (McDonald et al., 2005b). The dependency parsing problem is nat- urally a spanning tree problem; however, effi- cient spanning-tree optimization algorithms assume a cost function which assigns scores independently to edges of the graph. In dependency parsing, this effectively constrains the set of models to those which independently generate parent-child pairs; 1In this paper we deal only with MSTs on directed graphs. These are often referred to in the graph-theory literature as Max- imum Spanning Arborescences. these are known as edge-factored models. These models are limited to relatively simple features which exclude linguistic constructs such as verb sub-categorization/valency, lexical selectional pref- erences, etc.2 In order to explore a rich set of syntactic fea- tures in the MST framework, we can either approx- imate the optimal non-projective solution as in Mc- Donald and Pereira (2006), or we can use the con- strained MST model to select a subset of the set of dependency parses to which we then apply less- constrained models. An efficient algorithm for gen- erating the k-best parse trees for a constituency- based parser was presented in Huang and Chiang (2005); a variation of that algorithm was used for generating projective dependency trees for parsing in Dreyer et al. (2006) and for training in McDonald et al. (2005a). However, prior to this paper, an effi- cient non-projective k-best MST dependency parser has not been proposed.3 In this paper we show that the na¨ıve edge-factored models are effective at selecting sets of parses on which the oracle parse accuracy is high. The or- acle parse accuracy for a set of parse trees is the highest accuracy for any individual tree in the set. We show that the 1-best accuracy and oracle accu- racy can differ by as much as an absolute 9% when the oracle is computed over a small set generated by edge-factored models (k = 50). 2Labeled edge-factored models can capture selectional pref- erence; however, the unlabeled models presented here are lim- ited …

Content truncated to 500 words