Structured Prediction Models via the Matrix-Tree Theorem

Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, pp. 141–150, Prague, June 2007. c⃝2007 Association for Computational Linguistics Structured Prediction Models via the Matrix-Tree Theorem Terry Koo, Amir Globerson, Xavier Carreras and Michael Collins MIT CSAIL, Cambridge, MA 02139, USA {maestro,gamir,carreras,mcollins}@csail.mit.edu Abstract 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. 1 Introduction Learning with structured data typically involves searching or summing over a set with an exponen- tial number of structured elements, for example the set of all parse trees for a given sentence. Meth- ods for summing over such structures include the inside-outside algorithm for probabilistic context- free grammars (Baker, 1979), the forward-backward algorithm for hidden Markov models (Baum et al., 1970), and the belief-propagation algorithm for graphical models (Pearl, 1988). These algorithms compute marginal probabilities and partition func- tions, quantities which are central to many meth- ods for the statistical modeling of complex struc- tures (e.g., the EM algorithm (Baker, 1979; Baum et al., 1970), contrastive estimation (Smith and Eis- ner, 2005), training algorithms for CRFs (Lafferty et al., 2001), and training algorithms for max-margin models (Bartlett et al., 2004; Taskar et al., 2004a)). This paper describes inside-outside-style algo- rithms for the case of directed spanning trees. These structures are equivalent to non-projective depen- dency parses (McDonald et al., 2005b), and more generally could be relevant to any task that involves learning a mapping from a graph to an underlying spanning tree. Unlike the case for projective depen- dency structures, partition functions and marginals for non-projective trees cannot be computed using dynamic-programming methods such as the inside- outside algorithm. In this paper we describe how these quantities can be computed by adapting a well- known result in graph theory: Kirchhoff’s Matrix- Tree Theorem (Tutte, 1984). A na¨ıve application of the theorem yields O(n4) and O(n6) algorithms for computation of the partition function and marginals, respectively. However, our adaptation finds the par- tition function and marginals in O(n3) time using simple matrix determinant and inversion operations. We demonstrate an application of the new infer- ence algorithm to non-projective dependency pars- ing. Specifically, we show how to implement two popular supervised learning approaches for this task: globally-normalized log-linear models and max-margin models. Log-linear estimation criti- cally depends on the calculation of partition func- tions and marginals, which can be computed by our algorithms. For max-margin models, Bartlett et al. (2004) have provided a simple training al- gorithm, based on exponentiated-gradient (EG) up- dates, that requires computation of marginals and can thus be implemented within our framework. Both of these methods explicitly minimize the …

Content truncated to 500 words