Chu-Liu/Edmonds Algorithm

A parsing paradigm that scores all possible dependency arcs in a sentence simultaneously to find the highest-scoring maximum spanning tree. Unlike transition-based methods, graph-based parsing performs global optimization over the entire sentence. The Chu-Liu/Edmonds algorithm is the standard decoder for non-projective graph-based parsing, guaranteeing the optimal tree in O(n²) time. This approach excels at capturing long-distance dependencies and is the foundation for modern deep biaffine parsers.

A dependency tree structure containing crossing arcs that cannot be drawn without lines intersecting when the sentence is written linearly. Non-projectivity is essential for accurately representing:

• Wh-movement in English (e.g., 'What did you see?')
• Free word order in morphologically rich languages like Czech, Turkish, and Latin
• Long-distance dependencies across clause boundaries

The Chu-Liu/Edmonds algorithm is specifically required to decode non-projective trees, as projective constraints like the Eisner algorithm cannot handle crossing arcs.

A first-order parsing model where the score of a complete dependency tree is the sum of the scores of its individual arcs, assuming independence between edges. This factorization makes the global optimization problem tractable:

• Each arc (head, dependent) receives an independent score
• The total tree score = Σ score(head_i, dependent_i)
• The Chu-Liu/Edmonds algorithm finds the maximum spanning tree over these arc scores

Higher-order models incorporate sibling or grandparent features but require approximate decoding, making arc-factored models the standard for exact non-projective inference.

An early and influential graph-based dependency parser developed by Ryan McDonald that uses the maximum spanning tree algorithm to find the globally optimal dependency tree. Key characteristics:

• Supports both projective (Eisner algorithm) and non-projective (Chu-Liu/Edmonds) decoding
• Uses online large-margin learning (MIRA) for training
• Demonstrated that global inference outperforms greedy transition-based methods on non-projective languages

MSTParser established the graph-based paradigm and directly motivated the integration of the Chu-Liu/Edmonds algorithm into neural parsing architectures.

A neural dependency parser architecture introduced by Dozat and Manning (2017) that uses deep biaffine attention over BiLSTM-encoded word representations. The biaffine layer computes scores for all O(n²) possible head-dependent pairs simultaneously:

• A feedforward network produces head and dependent representations for each token
• A biaffine transformation scores every possible arc
• The Chu-Liu/Edmonds algorithm decodes the maximum spanning tree from the scored complete graph

This architecture achieves state-of-the-art accuracy and is the standard graph-based neural parser.

A deterministic parsing paradigm that processes a sentence left-to-right using a stack and buffer, applying shift-reduce actions to incrementally build a dependency tree. Contrasts with graph-based parsing:

• Greedy or beam search decoding vs. global maximum spanning tree
• Linear O(n) time complexity vs. O(n²) for Chu-Liu/Edmonds
• Susceptible to error propagation but faster for production
• Cannot naturally handle non-projective structures without swap operations

Modern libraries like spaCy use transition-based parsing for speed, while graph-based methods using Chu-Liu/Edmonds prioritize accuracy.