MSTParser

The core algorithm treats parsing as finding the highest-scoring directed spanning tree over all possible words. It uses the Chu-Liu/Edmonds algorithm to efficiently find the global optimum in O(n²) time, considering all possible arcs simultaneously rather than making local greedy decisions. This global view allows it to naturally handle non-projective dependencies, such as those found in languages with free word order like German or Dutch, without special extensions.

MSTParser uses a first-order factorization where the score of a complete dependency tree is the sum of the scores of its individual arcs. This assumes independence between edges for computational tractability.

• Feature Templates: Scores are computed using a linear model over hand-crafted features extracted from the words, part-of-speech tags, and positional context of the head and dependent.
• Training: The model is trained using the Margin Infused Relaxed Algorithm (MIRA), an online large-margin learning method that updates weights to ensure the gold tree outscores all incorrect trees by a margin.

MSTParser offers two distinct decoding modes, making it versatile across language typologies:

• Projective Mode: Restricts the search to trees without crossing arcs, using an efficient Eisner-style dynamic programming algorithm. This is faster and suitable for English.
• Non-Projective Mode: Applies the full Chu-Liu/Edmonds algorithm to find the maximum spanning tree without projectivity constraints. This is essential for accurately parsing languages with long-distance dependencies and free constituent order.

To improve accuracy beyond first-order independence assumptions, MSTParser supports higher-order features that score pairs of adjacent arcs:

• Sibling Features: Capture the relationship between a head and two of its dependents, modeling coordination structures more accurately.
• Grandparent Features: Model the relationship between a head, its dependent, and the head's own parent, capturing richer syntactic context. These extensions move the model closer to capturing global tree structure while maintaining tractable decoding.

MSTParser is trained using the Margin Infused Relaxed Algorithm (MIRA), an online learning method that processes one sentence at a time. For each sentence, it finds the highest-scoring incorrect tree and updates the feature weights to increase the margin between the gold tree and the competitor. This approach is:

• Memory efficient: No need to store the entire training set in memory.
• Fast to converge: Typically requires only a few passes over the data.
• Robust: The margin criterion helps prevent overfitting to noisy annotations.

Developed by Ryan McDonald and colleagues in the mid-2000s, MSTParser established the graph-based parsing paradigm as a viable alternative to transition-based methods. Its key contributions include:

• Proving that global inference over all possible arcs was computationally feasible.
• Demonstrating that non-projective parsing could be done without loss of accuracy on projective languages.
• Inspiring the development of modern neural graph-based parsers, including the Deep Biaffine Parser, which replaced linear feature templates with BiLSTM-encoded representations while retaining the same maximum spanning tree decoding logic.