Structured Prediction Models via the Matrix-Tree Theorem

By Terry Koo, Amir Globerson, Xavier Carreras, Michael Collins. 2007

170 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Natural Language Processing

Citations in the corpus

Barrier Frank-Wolfe for Marginal Inference (2015, methodology): “This is an encouraging and non-intuitive result since it indicates that one can achieve high quality marginals through the use of relatively cheaper approximate MAP oracles.”
Inside-Outside and Forward-Backward Algorithms Are Just Backprop (tutorial paper) (2016, background): “Smith and Smith (2007) and Koo et al. (2007) handle non-projective dependency grammars, using an inside algorithm with a different structure (not a dynamic programming algorithm).”
Neural Probabilistic Model for Non-projective MST Parsing (2017, methodology): “Matrix-Tree Theorem.”
Gradient Estimation with Stochastic Softmax Tricks (2020, methodology): “X can be computed with Kruskal’s algorithm [45], X t with Kirchoff’s matrix-tree theorem [42, Sec.”
SparseMAP: Differentiable Sparse Structured Inference (2018, methodology): “, 2005), and the MatrixTree theorem (Kirchhoff, 1847) provides a way to perform marginal inference (Koo et al., 2007; Smith & Smith, 2007).”
Reasoning with Latent Structure Refinement for Document-Level Relation Extraction (2020, methodology): “Using a variant of Matrix-Tree Theorem (Tutte, 1984; Koo et al., 2007), our model is able to generate task-specific dependency structures for”
Iterative parameter mixing for distributed large-margin training of structured predictors for natural language processing (2015, background): “Practical experience has shown that, for many NLP tasks, especially parsing, maximum-margin training will outperform perceptron training (McDonald et al., 2005; Tsochantaridis et al., 2005; Koo et al., 2007).”
Unsupervised Neural Single-Document Summarization of Reviews via Learning Latent Discourse Structure and its Ranking (2019, methodology): “We normalize fij into aij based on (Koo et al., 2007).”
Convergent Propagation Algorithms via Oriented Trees (2007, background): “The function F ( µ ; ρ, θ ) can now be written as where the edge set ¯ E contains edges in both directions.”
Dependency Parsing by Belief Propagation (2008, background): “A slower but potentially more stable alternative is deterministic annealing.”
Exponentiated Gradient Algorithms for Conditional Random Fields and Max-Margin Markov Networks (2008, methodology): “In the experiments below we use a feature set f(x,h,m) similar to that in McDonald et al. (2005) and Koo et al. (2007), resulting in 2,500,554 features.”
Tractable Bayesian Inference of Time-Series Dependence Structure (2009, methodology): “However, as pointed out in (Koo et al., 2007), using the invariance of Cofi,j ( Q̄(β) ) allows for O(N3) time computation of Z(β).”