Dependency Parsing

20.3 Graph-based parsing

1. Why can graph-based dependency parsers be more accurate than transition-based ones?
   They score entire trees rather than making greedy local decisions, which helps especially with long sentences and distant heads, and they can produce non-projective trees.
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 20, §20.3, p. 463
2. What does an edge-factored model assume?
   That the score of a tree is the sum of the scores of its edges.
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 20, §20.3, p. 464
3. How is dependency parsing cast as a maximum spanning tree problem?
   Build a fully connected weighted directed graph over the words plus ROOT (edges = all possible head–dependent pairs, weights = scores); the best parse is the maximum spanning tree rooted at ROOT.
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 20, §20.3, p. 464
4. What two intuitions underlie the Chu-Liu-Edmonds algorithm?
   Every vertex (and every connected component) of a spanning tree has exactly one incoming edge; and only the relative weights of edges entering a vertex matter, so subtracting a constant from all of them doesn’t change the best tree.
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 20, §20.3, pp. 464–465
5. Describe the Chu-Liu-Edmonds maximum spanning tree algorithm.
   Greedily pick the highest-scoring incoming edge for each vertex; if this forms a tree, done. Otherwise subtract each vertex’s best incoming score from its incoming edges, collapse a cycle into one node, recursively find the MST of the contracted graph, then expand the node, dropping the one cycle edge the chosen entering edge replaces.

   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 20, §20.3, p. 465
6. What is the running time of Chu-Liu-Edmonds for parsing?
   \(O(mn)\) for \(m\) edges and \(n\) nodes, so \(O(n^3)\) on a fully connected graph; faster implementations reach \(O(m + n\log n)\).
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 20, §20.3, p. 466
7. What features does a feature-based edge scorer use, and how is it trained?
   Forms, lemmas and POS of head and dependent, context features before/after/between them, the relation, its direction and the distance. Weights are learned with inference-based learning and the perceptron rule: parse a training sentence; if wrong, lower the weights of features in the wrong parse not present in the reference.
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 20, §20.3, pp. 466–467
8. How does the biaffine parser score a dependency edge?
   Encode the sentence; pass each token’s encoding through two feedforward networks to get a head representation and a dependent representation; score edge \(i \to j\) with \(\text{Biaff}(h^{head}_i, h^{dep}_j) = x^\top Uy + W(x \oplus y) + b\), which captures multiplicative interactions.
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 20, §20.3, p. 468
9. How does the biaffine parser turn edge scores into a labeled tree?
   A softmax over each word’s possible heads gives \(p(i \to j)\) (trained with cross-entropy); maximum spanning tree finds the best tree; then a second classifier of the same form picks the best label for each chosen edge.
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 20, §20.3, p. 469