TL;DR
This paper introduces a novel multi-stage dependency parsing framework that offers a flexible compromise between purely deterministic and globally optimal parsing approaches. By leveraging Maximum Entropy Markov Models (MEMMs) in a sequential, stage-wise manner, it achieves competitive performance while allowing fine-tuning of the trade-off between feature richness and search optimality.
What Problem Does This Paper Address?
Dependency parsing aims to uncover the grammatical structure of a sentence by identifying relationships between words. However, finding the absolute best dependency tree is computationally intractable due to the exponential number of possible structures. Traditional approaches fall into two camps: maximum spanning tree (MST) methods that explore the entire search space but often use simpler features, and transition-based parsers that make locally optimal decisions with rich features but don't guarantee global optimality. This paper addresses the need for a parsing framework that can fluidly navigate the spectrum between these two extremes, offering a tunable balance of global feature exploitation and efficient, deterministic decision-making.
Methods
The core of the proposed framework is a multi-stage parsing process built upon Maximum Entropy Markov Models (MEMMs). Instead of parsing a sentence in a single pass, the process is broken down into multiple stages. In each stage, the MEMM takes a sequence of partial dependency trees and links them together, effectively reducing the number of trees until only one remains.
The MEMM's state transitions allow for three basic actions: linking the current tree to the next tree (RAx), linking to the previous tree (LAx), or doing nothing (NA). The key innovation lies in the tunable automaton topology that defines the possible transitions. By modifying this topology, the authors can control the "rank" of the parser, influencing the compromise between local and global optimization. For instance, a rank-1 automaton approximates a deterministic, easiest-first parser, while higher ranks allow for more complex tree structures to be formed within a single stage.
Crucially, the MEMM is trained using the Generalized Iterative Scaling algorithm, and parsing employs the Viterbi algorithm within each stage. This is enabled by ensuring that MEMM features depend only on previously created arcs, respecting the first-order Markov constraint necessary for Viterbi decoding.
Datasets
The proposed parser was evaluated on the French Ester Treebank (ETB), a corpus of French broadcast news annotated with dependencies. The training set comprised 50,000 words, and the test set contained 4,807 words. Part-of-speech tags were automatically computed using the Tree Tagger.
Key Insights and Ideas
- Tunable Compromise: The framework's most significant contribution is its ability to act as a knob, allowing researchers to dial in the desired balance between local, feature-rich decisions and global, structure-aware optimization. This is achieved by adjusting the automaton's rank.
- Stage-wise Global Optimization: By performing Viterbi decoding within each stage, the parser finds a globally optimal solution for that stage, given the constraints. This is a departure from purely deterministic parsers that only optimize locally at each step.
- Probabilistic Foundation: The use of MEMMs provides a probabilistic model, opening doors to advanced techniques like marginalization and Bayesian inference for handling missing or corrupted data, which is not possible with purely deterministic parsers.
- Projectivity Constraint: The automaton design inherently enforces projectivity, a common constraint in dependency parsing, by forbidding certain transitions between left and right linking actions.
Key Results
On the French Ester Treebank, the rank-1 MEMM parser achieved a Labeled Attachment Score (LAS) comparable to the state-of-the-art Malt parser. It performed moderately lower than the MATE parser, which is attributed to MATE's more exhaustive search space exploration at the cost of higher complexity.
In terms of efficiency, the proposed MEMM parser demonstrated significantly faster training and testing times and lower memory consumption compared to Malt (especially the libSVM version) and MATE. Specifically, the MEMM parser achieved a practical running time of 3 seconds for testing, comparable to the fastest Malt configuration, while maintaining competitive accuracy.
Limitations and Future Work
The authors acknowledge that the Ester Treebank is relatively small and consists of speech data, which is generally more challenging to parse than written text. They suggest several avenues for future work:
- Exploring other models: Investigating Conditional Random Fields (CRFs) or higher-order Markovian models could potentially incorporate richer features and improve performance.
- Extending deterministic processes: Incorporating mechanisms like backtracking or graphs of alternative solutions across stages could mitigate the impact of errors from previous stages.
- Leveraging probabilistic algorithms: Further exploration of marginalization and Bayesian inference for handling partial or missing observations is a promising direction.
- Higher-rank automata: While higher ranks offer more global optimization, they lead to exponentially increasing states, posing a challenge for practical implementation. The authors suggest that the goal is not to replace MST parsers but to explore the intermediate space.
Summary updated