K-best Spanning Tree Parsing
Keith Hall · 2007
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