Non-projective Dependency Parsing using Spanning Tree Algorithms

2.2.1 Non-projective Trees

1. Describe the Chu-Liu-Edmonds algorithm informally.
   Each vertex greedily picks its highest-scoring incoming edge. If the result is a tree, it is the MST. Otherwise contract a cycle into a single node, recompute the weights of edges into and out of it, recursively find the MST of the contracted graph, and expand the cycle, breaking it at the vertex where the chosen incoming edge enters.
   • 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.1, pp. 525–526
2. In Chu-Liu-Edmonds, how are edge weights recomputed when a cycle \(C\) is contracted into node \(c\)?
   Edges out: \(s(c, x) = \max_{x' \in C} s(x', x)\). Edges in: \(s(x, c) = \max_{x' \in C} [s(x, x') - s(a(x'), x') + s(C)]\), where \(a(x')\) is the predecessor of \(x'\) in the cycle and \(s(C)\) the cycle’s total weight: entering at \(x'\) means dropping the cycle edge into \(x'\).
   • 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.1, pp. 525–526
3. Run Chu-Liu-Edmonds on “John saw Mary” with root→saw 10, root→John 9, root→Mary 9, saw→John 30, saw→Mary 30, John→saw 20, Mary→saw 0, John→Mary 3, Mary→John 11.
   Best incoming edges: saw→John, John→saw, saw→Mary, giving the cycle John⇄saw (\(s(C) = 50\)). Contract to \(c\): root→\(c\) = max(10 − 20, 9 − 30) + 50 = 40; Mary→\(c\) = max(0 − 20, 11 − 30) + 50 = 31; \(c\)→Mary = 30. Now root→\(c\) and \(c\)→Mary form a tree. Expanding gives root→saw, saw→John, saw→Mary (score 70).
   • 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.1, pp. 525–526
4. What is the time complexity of Chu-Liu-Edmonds for dependency parsing?
   Naively \(O(n^3)\): each recursive call takes \(O(n^2)\) to pick incoming edges and contract, and there are at most \(O(n)\) contractions. Tarjan’s (1977) implementation runs in \(O(n^2)\) on dense graphs, which is the dependency parsing case.
   • 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.1, pp. 525–526