Higher-Order Parsing

Incorporates information about previously attached dependents of the same head when scoring a new arc. This captures coordination structures and modifier ordering constraints.

• Resolves prepositional phrase attachment ambiguities by modeling modifier sequences
• Identifies coordination structures where multiple dependents share the same head
• Example: In "the man with the telescope," sibling features help determine whether "with the telescope" modifies "man" or a verb
• Computationally more expensive than arc-factored models but significantly improves Labeled Attachment Score (LAS)

Models the relationship between a dependent and its head's own head, capturing three-node vertical contexts essential for resolving clause-level dependencies.

• Critical for parsing embedded clauses and long-distance dependencies
• Helps distinguish between clausal complements and adverbial modifiers
• Example: In "She said he left," grandparent features link "left" back to "said" through the intermediate head "he"
• Enables parsers to learn constraints on verb chain structures across clause boundaries

Extends sibling modeling to consider three dependents simultaneously, capturing ternary relationships that pairwise sibling features miss.

• Models appositive constructions where multiple noun phrases modify the same head
• Handles complex coordination with shared modifiers across conjuncts
• Example: In "apples, oranges, and bananas," tri-sibling features capture the full list structure
• Increases feature space quadratically, requiring careful regularization to prevent overfitting

Higher-order parsing introduces significant computational overhead compared to first-order arc-factored models, requiring optimization strategies for practical deployment.

• First-order: O(n²) arc scoring complexity
• Second-order with siblings: O(n³) in naive implementations
• Third-order: O(n⁴) worst-case, often reduced via cube pruning or coarse-to-fine inference
• Modern neural approaches use biaffine attention with higher-order feature concatenation to approximate these dependencies efficiently
• Production systems often use beam search with higher-order features applied only to top-k candidates

Higher-order models jointly predict both the dependency arc and its relation label using contextual features from surrounding arcs.

• Labels like nsubj, dobj, and iobj benefit from knowing sibling labels
• Prevents impossible label combinations: a verb cannot have two nsubj dependents
• Uses conditional random fields or structured perceptrons to enforce global label consistency
• Improves Labeled Attachment Score (LAS) by 1-3 percentage points over first-order labeling

Adapts transition-based architectures to incorporate higher-order features by enriching the parser state representation with previously constructed arcs.

• Arc-standard and arc-eager algorithms extended with history-based features
• Feature templates include: head of top-of-stack, leftmost/rightmost dependents of stack items
• Dynamic oracles enable training on non-gold states while preserving higher-order feature validity
• Implemented in systems like MaltParser with polynomial feature combinations
• Achieves near-graph-based accuracy with linear-time decoding speed

The first-order baseline that higher-order parsing extends. In an arc-factored model, the score of a complete dependency tree is simply the sum of the scores of its individual arcs, assuming independence between edges. This factorization makes decoding computationally efficient using maximum spanning tree algorithms but ignores crucial syntactic contexts like sibling or grandparent relations, which higher-order models explicitly capture.

A neural architecture introduced by Dozat and Manning that serves as the modern backbone for high-accuracy parsing. It uses deep biaffine attention over BiLSTM-encoded word representations to score all possible head-dependent pairs. While originally a first-order model, its architecture is routinely extended with higher-order components to capture richer syntactic contexts, achieving state-of-the-art results on benchmark treebanks.

The primary evaluation metric for measuring the impact of higher-order features. LAS calculates the percentage of tokens that are assigned both the correct syntactic head and the correct dependency relation label. Higher-order models typically demonstrate a measurable improvement in LAS over arc-factored baselines, particularly on complex constructions like prepositional phrase attachment and coordination, where sibling context is critical.

A dependency tree structure containing crossing arcs, common in languages with free word order. Higher-order parsing becomes significantly more complex for non-projective trees because the decoding algorithm must consider crossing constraints while scoring sibling or grandparent features. The Chu-Liu/Edmonds algorithm used for non-projective parsing does not naturally extend to higher-order factors, requiring approximate inference techniques.

A combinatorial optimization algorithm for finding the maximum spanning tree in a directed graph. It is the standard decoder for first-order graph-based dependency parsing. Extending this algorithm to handle higher-order features—where the score of an arc depends on its siblings or grandparents—is NP-hard, forcing researchers to use approximate decoding methods like belief propagation or cube pruning in higher-order models.