Paper: K-best Spanning Tree Parsing

ACL ID P07-1050
Title K-best Spanning Tree Parsing
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 2007
  • Keith Hall (Johns Hopkins University, Baltimore MD)

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).