TL;DR
This paper introduces two novel probabilistic models for dependency parsing that address the limitations of greedy, deterministic parsers. By modeling the probability of entire dependency trees rather than just individual parsing actions, these models achieve improved performance across 10 languages, demonstrating a more robust approach to capturing complex linguistic structures.
What Problem Does This Paper Address?
Traditional deterministic dependency parsers, while efficient, operate greedily. They make locally optimal decisions at each step without considering the overall structure of the resulting dependency tree. This "myopic" approach can lead to suboptimal parses because a decision that seems best at one moment might prevent a better overall parse later on. The paper aims to overcome this limitation by developing models that can assign a probability to an entire dependency tree, allowing for the selection of the most probable parse globally. This is particularly challenging for multi-lingual parsing, where diverse linguistic structures and the potential for non-projective dependencies add complexity.
Methods
The authors propose two probabilistic parsing action models:
- Parsing Action Chain Model (PACM): This model views the parsing process as a Markov Chain. It assumes that the probability of the current parsing state depends only on the previous state. PACM calculates the probability of a sequence of parsing actions and uses this to determine the probability of the entire dependency tree. They employ a Support Vector Machine (SVM) classifier trained to predict parsing actions with probability outputs. Beam search is used for decoding to explore multiple promising parsing paths.
- Parsing Action Phrase Model (PAPM): This model refines PACM by dividing parsing actions into "constructing actions" (which build dependencies) and "shifting actions" (which move the parsing focus). It introduces the concept of a "parsing action phrase," which is a sequence of actions that constructs a syntactic phrase. PAPM models the probability of these phrases, aiming to capture how phrases are built. Similar to PACM, it uses beam search for decoding, but it keeps track of states corresponding to the best current parsing action phrases.
Both models extend the original Yamada and Matsumoto's deterministic parsing algorithm by incorporating labeled dependency relations.
Datasets
The experiments were conducted on data from the CoNLL 2007 shared task on dependency parsing. This dataset includes treebanks for 10 languages. For languages with non-projective relations, the data was projected to a projective format for training and then deprojectivized after parsing.
Key Insights and Ideas
- Moving beyond greedy parsing: The core insight is that by modeling the probability of the entire dependency tree, we can avoid the pitfalls of greedy, step-by-step decision-making inherent in deterministic parsers.
- Probabilistic action sequences matter: The success of PACM and PAPM highlights that the sequence of actions, not just individual optimal actions, is crucial for building accurate dependency structures.
- Phrase-level modeling (PAPM): The idea of grouping actions into "parsing action phrases" offers a more structured way to think about dependency construction, potentially capturing more complex linguistic phenomena.
- Universal applicability: The models demonstrate improved performance across a diverse set of 10 languages, suggesting their generalizability.
- Long-distance dependencies remain a challenge: Despite improvements, the paper identifies long-distance dependencies as a persistent difficulty in dependency parsing, even for their probabilistic models.
Key Results
- Outperformance of deterministic parsers: Both PACM and PAPM consistently outperform the original Yamada and Matsumoto deterministic dependency parser across all 10 languages tested.
- LAS improvements: PACM shows improvements in Labeled Attachment Score (LAS) ranging from 0.60 to 1.71 percentage points over the baseline.
- PAPM's mixed results: PAPM shows further improvements over PACM for Catalan and English (2.31% and 0.86% LAS respectively), but a marginal improvement for Chinese and a slight decrease for Hungarian. This is attributed to Hungarian's high percentage of non-projective relations.
- Error analysis: The paper notes that long-distance dependencies and root node precision are key areas where errors occur, and that error propagation from short-distance dependencies can impact the final parse.
Limitations and Future Work
- Unary root languages for PAPM: PAPM is noted to be most suitable for languages with a single root node per sentence (unary root languages), limiting its direct application to all languages without adaptation.
- Long-distance dependencies: The paper explicitly states that long-distance dependencies remain a significant challenge. Future work should focus on guiding research directions and exploring more informative features to tackle this.
- Feature exploration: The authors suggest that feature exploration is necessary to improve performance on difficult parsing problems.
- Error propagation: While the probabilistic models mitigate greedy error propagation, the underlying deterministic nature of the parsing actions still means errors can occur. Further research could explore more fundamentally different approaches to error handling.
Summary updated