Non-projective Dependency Parsing using Spanning Tree Algorithms

2.2 Maximum Spanning Trees

1. How is a sentence turned into a graph for MST parsing?
   \(G_x\) has vertices \(x_0 = \text{root}, x_1, \ldots, x_n\) and a directed edge \((i, j)\) for every \(i \ne j\) with \(j \ge 1\): from the root to every word and between every pair of distinct words, weighted by \(s(i, j)\). Dependency trees for \(x\) are exactly the spanning trees of \(G_x\) rooted at the root (arborescences).
   • McDonald et al., 2005, Non-projective Dependency Parsing using Spanning Tree Algorithms (Proceedings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing (HLT/EMNLP 2005)), §2.2, p. 525