Abstract
Dependency parsing with high-order features results in a provably hard decoding problem. A lot of work has gone into developing powerful optimization methods for solving these combinatorial problems. In contrast, we explore, analyze, and demonstrate that a substantially simpler randomized greedy inference algorithm already suffices for near optimal parsing: a) we analytically quantify the number of local optima that the greedy method has to overcome in the context of first-order parsing; b) we show that, as a decoding algorithm, the greedy method surpasses dual decomposition in second-order parsing; c) we empirically demonstrate that our approach with up to third-order and global features outperforms the state-of-the-art dual decomposition and MCMC sampling methods when evaluated on 14 languages of non-projective CoNLL datasets.
Introduction
In natural language processing, dependency parsing is the task of mapping out the grammatical structure of a sentence—identifying "who did what to whom." To achieve high accuracy, modern parsers utilize "high-order features," which are rules that examine triplets or quadruplets of words rather than just simple pairs. While these features improve performance, they transform the decoding process into a notoriously difficult NP-hard combinatorial problem.
Historically, the field has relied on sophisticated optimization techniques such as Dual Decomposition or MCMC sampling to navigate this complexity. However, these methods are mathematically dense and often difficult to implement or scale. This paper investigates whether a significantly simpler "greedy" approach can achieve comparable or superior results.
Methodology: Randomized Greedy Inference
The authors propose a Randomized Greedy Inference algorithm that leverages multiple restarts to overcome the limitations of standard greedy search. The process follows four main steps:
- Random Initialization: The algorithm begins with a parse tree drawn either completely at random or from a simple first-order model.
- Hill-Climbing: It iteratively examines each word in the sentence. If changing a word's parent increases the overall tree score, the change is made. This continues until no single modification can further improve the score, reaching a local optimum.
- Random Restarts: To avoid getting trapped in mediocre local optima, the process is repeated many times from different random starting points.
- Selection: The highest-scoring tree found across all restarts is selected as the final parse.
Theoretical and Empirical Analysis
A common criticism of greedy algorithms is their tendency to get stuck in local optima. However, the authors demonstrate that the search space for dependency parsing is less "jagged" than previously assumed.
Local Optima Analysis
The authors analytically show that for real-world sentences, the number of local optima is surprisingly small. For instance, in English, 70% of sentences contain fewer than 121 local optima—a manageable number for modern computational power. This suggests that the "average case" for parsing is significantly easier than the theoretical "worst case."
Robustness of Initialization
Empirical tests revealed that starting from a completely random tree eventually yields the same high-quality results as starting from a "smart" guess, provided enough restarts are used. This highlights the robustness of the hill-climbing approach and suggests that the primary structure of a sentence is largely determined by simple, local word pairings that are easy for the algorithm to find.
Key Results
The model was evaluated on the CoNLL non-projective datasets across 14 languages, including Arabic, Chinese, English, German, Japanese, and Turkish.
- Superior Accuracy: The randomized greedy parser achieved an average Unlabeled Attachment Score (UAS) of 89.44%, outperforming the previous state-of-the-art TurboParser (88.72%).
- Optimization Performance: In second-order parsing, the greedy method found a tree with a score equal to or higher than that found by Dual Decomposition in 99.1% of cases.
- Efficiency: The algorithm is "embarrassingly parallel," allowing hundreds of independent restarts to run simultaneously on multi-core CPUs.
Conclusion and Future Work
Randomized hill-climbing proves to be a powerful alternative to complex optimization for dependency parsing. While highly accurate, the method's main bottleneck is the number of restarts (e.g., $K=300$) required for long, complex sentences, which may impact latency in real-time applications. Future research could explore the impact of even more complex global constraints on the search space and investigate the interaction between greedy inference and various training loss functions.
Summary updated