Paper: Structured Prediction Models via the Matrix-Tree Theorem

ACL ID D07-1015
Title Structured Prediction Models via the Matrix-Tree Theorem
Venue Conference on Empirical Methods in Natural Language Processing
Session Main Conference
Year 2007
Authors

This paper provides an algorithmic frame- work for learning statistical models involv- ing directed spanning trees, or equivalently non-projective dependency structures. We show how partition functions and marginals for directed spanning trees can be computed by an adaptation of Kirchhoff’s Matrix-Tree Theorem. To demonstrate an application of the method, we perform experiments which use the algorithm in training both log-linear and max-margin dependency parsers. The new training methods give improvements in accuracy over perceptron-trained models.