Source-linked AI summary
A Fundamental Algorithm for Dependency Parsing (With Corrections)
Michael A. Covington
TL;DR
The paper addresses how to parse natural-language sentences into dependency trees in a systematic, incremental way. It develops a word-at-a-time algorithm that attaches words as soon as possible, with worst-case complexity O(n^3); the paper notes that such worst cases occur only for small n in human language.
Problem
Dependency parsing had been implemented for decades, but a fundamental algorithm had not been presented systematically in the extant literature.
Method
The paper develops variations of a dependency parser that processes words incrementally using Wordlist and Headlist while attaching each word as soon as it can be attached.
Results
The algorithm’s worst-case complexity is O(n^3), matching recursive-descent constituency parsing, while the initial deterministic brute-force search is O(n^2).
Takeaways & Limitations
Dependency parsing offers a formalism for connecting words incrementally, and the paper argues that worst-case complexity is not generally encountered in human language.
Takeaways & Limitations
The complexity bounds are worst-case results, and human language is constrained in ways that remain incompletely discovered.
Abstract
from arXiv · showhide
This paper presents a fundamental algorithm for parsing natural language sentences into dependency trees. Unlike phrase-structure (constituency) parsers, this algorithm operates one word at a time, attaching each word as soon as it can be attached, corresponding to properties claimed for the parser in the human brain. Like phrase-structure parsing, its worst-case complexity is $O(n^3)$, but in human language, the worst case occurs only for small $n$.
1 Overview.
The paper develops a fundamental dependency-parsing algorithm systematically from first principles. It processes sentences one word at a time, attaching words as soon as they can be attached.
- The paper develops several variations of a fundamental algorithm for parsing natural language into dependency trees.The algorithm had appeared in some form since the 1960s but had not been presented systematically in the extant literature.
- Unlike phrase-structure parsers, the algorithm operates one word at a time and attaches each word as soon as it can be attached.These properties are claimed to correspond to evidence about parsing in the human mind.
- Figure 1 presents a constituency tree, the phrase-structure representation contrasted with the paper’s dependency representation.
2 Dependency grammar.
Dependency grammar represents sentence structure through links between words rather than constituent groupings. The paper motivates this representation as direct, word-based, and compatible with incremental parsing while noting its formal equivalence to restricted constituency grammar.
- 2 Dependency grammar.: Dependency grammar represents sentence structure by drawing links connecting individual words, whereas constituency grammar breaks sentences into nested phrases.
- 2.1 The key concept.: A dependency relation connects a head to a dependent, with the dependent generally functioning as modifier, object, or complement.The head plays the larger role in determining the pair’s behavior; the dependent presupposes the head, while the head may require the dependent.
- 2.2 Dependency trees.: Dependency trees preserve word order while displaying tree structure directly; dependents preceding their heads are predependents, and following dependents are postdependents.The paper’s diagrammatic guide is to move downhill from a head to its dependents.
- 2.3 Generative power.: Dependency and constituency grammar are strongly equivalent when constituency grammar designates a head in each phrase and imposes the stated restriction.The paper therefore does not claim a significant difference in generative power between the formalisms.
- 2.4 The appeal of dependency parsing.: Dependency links are close to semantic relationships needed for interpretation because head–modifier and head–complement relations are shown directly.
- 2.4 The appeal of dependency parsing.: A dependency tree has one node per word, so parsing connects existing words instead of postulating additional nodes.The paper says this makes the task more straightforward to manage, although not lower in actual complexity.
- 2.4 The appeal of dependency parsing.: Dependency parsing supports word-at-a-time operation by accepting and attaching words incrementally rather than waiting for complete phrases.The paper relates this property to evidence that human parsing avoids certain local ambiguities and begins understanding phrases before they are complete.
3 The parsing task.
The parsing task is to impose dependency links on a word string while producing a unified, unique, and often projective tree in a single left-to-right, word-at-a-time pass. The initial investigation simplifies this task by assuming instant grammar, no ambiguity, no inaudibilia, and atomic words.
- A dependency parser imposes the appropriate set of links on a string of words.
- Unity requires one tree with a unique root comprising every input word.
- Uniqueness gives each word only one head, so dependency links form a tree rather than another graph.
- Projectivity requires every word between a dependent and its head to be subordinate to that head.
- The parser examines words one at a time and attaches them during a single left-to-right pass unless ambiguity forces backtracking.
- The initial investigation assumes constant-time grammar judgments, no ambiguity, no inaudible elements, and unanalyzable words.
4 The obvious parsing strategy.
The obvious strategy accepts words from left to right and tests possible links with earlier words. Exhaustive search requires choosing comparison order and whether to seek heads or dependents first.
- Strategy 1 examines every pair of words and links them in either direction when the grammar permits.
- For n words, brute-force search tries n(n −1) pairs and has O(n^2) complexity without backtracking.
- With backtracking, exhaustive brute-force parsing can reach O(n^3), because the whole O(n) process may restart after each accepted word.
- Strategy 2 accepts words one by one and tests each as head or dependent of every previous word.
- Backward comparison is favored when projective structures predominate because nearby heads and dependents are found earlier.
- ESH searches heads first, whereas ESD swaps the relevant steps to search dependents first.
5 Refining the algorithms.
The algorithms are refined by enforcing uniqueness and by replacing unrestricted pair testing with lists that exclude ineligible words. The list-based LSU algorithm tracks encountered words and words lacking heads.
- A better parser avoids links that violate unity, uniqueness, or required projectivity.
- Enforcing uniqueness: Uniqueness means a word with a head cannot receive another head, while an existing dependent cannot be assigned elsewhere.
- Enforcing uniqueness: ESHU enforces uniqueness while searching heads first; ESDU uses the same constraints but searches dependents first.
- LSU uses Headlist for words lacking heads and Wordlist for all words encountered so far.
- The lists are built by prepending elements, so scanning from the beginning examines the most recently encountered words first.
- LSU first attaches eligible Headlist elements as dependents of the current word, then searches Wordlist for its single possible head.
6 Projectivity.
Projectivity means dependency structures have continuous constituents, equivalently no crossing branches. LSUP builds this property into list-based parsing by restricting dependent and head searches.
- A projective tree is one in which every word comprises a continuous substring.
- A continuous substring contains every word between any two words it comprises.
- When finding W’s head, it considers the most recent eligible predecessor and climbs through that word’s heads toward the root.
- The corrected algorithm replaces an erroneous previous-word-only rule, which could fail on postdependents with multiple obstacles.
- LSUP adds projectivity to list-based search while retaining uniqueness.
- When finding dependents of W, the parser may attach only consecutive independent Headlist elements beginning with the most recently added.
7 Complexity.
The paper analyzes dependency-parsing complexity under deterministic and locally ambiguous conditions. Deterministic brute-force search is O(n^2), while backtracking raises worst-case complexity to O(n^3), and lexical ambiguity with agreement features yields NP-completeness.
- O(n^2) complexity arises for brute-force parsing with a completely deterministic grammar.The search examines n(n−1) word pairs, which approaches n^2 as n grows.
- Backtracking makes brute-force-search parsing O(n^3) because the full O(n) process may restart after each accepted word.This is also the complexity of recursive-descent constituency parsing.
- Unity and projectivity constraints do not reduce these complexity results in cases where successive local ambiguities still force backtracking.In “the green house paint,” each successive word can require reconsidering the prior structure.
- With lexical ambiguity and agreement features, natural-language parsing is NP-complete.This statement is made under the paper’s assumption of atomicity before those features are introduced.
- These are worst-case bounds, and the paper states that human language generally avoids sentences producing worst-case behavior.The language’s relevant constraints are described as still being discovered.