TL;DR
This paper introduces a novel approach to dependency parsing by using reinforcement learning (RL) to create "approximate dynamic oracles" (ADOs). These ADOs help parsers overcome the error propagation problem inherent in greedy parsing, leading to improved accuracy across various transition systems.
What Problem Does This Paper Address?
Dependency parsing aims to determine the grammatical relationships between words in a sentence. Greedy transition-based parsers are efficient but suffer from error propagation: an incorrect decision early on can cascade and lead to a cascade of further errors. Traditional "dynamic oracles" help mitigate this by providing guidance on the best action at each step, but they are often complex to design and only work for specific, usually projective, parsing systems. This paper tackles the challenge of creating a more general and efficient dynamic oracle that can handle non-projective structures and be more easily implemented.
Methods
The core contribution is the development of an Approximate Dynamic Oracle (ADO) trained using Deep Q-Learning (DQN). Instead of trying to perfectly mimic a human-designed oracle, the ADO learns to approximate the "cost" of actions by treating parsing as a Markov Decision Process.
Here's a breakdown of the approach:
- Reinforcement Learning for Oracles: The authors frame the problem of finding the best parsing action as an RL task. The ADO learns a policy to select actions that minimize future errors.
- Reward Function: The reward function is designed to approximate the concept of "arc reachability." It penalizes actions that introduce immediate unreachable gold arcs (arcs that should exist in the correct parse tree but are now impossible to form) and provides a small positive reward for correct, projective attachments. This reward function is inspired by classical dynamic oracles but is designed to be more general.
- Deep Q-Learning (DQN): DQN is used to train the ADO. The state representation for the DQN includes binary features indicating the positions of gold heads in the stack and buffer, information about pending dependents, and previous actions. The DQN outputs estimated values for each possible action.
- Cost-Sensitive Parser Training: The ADO's learned action costs are then used to train the dependency parser itself using a cost-sensitive training approach. This encourages the parser to learn to avoid actions that the ADO deems costly.
- Separation of Concerns: A key insight is separating the exploration for the oracle and the parser. The oracle explores action space to learn costs, while the parser explores state space to learn from the oracle's guidance.
Datasets
The experiments were conducted on the 55 big treebanks from the CoNLL 2017 shared task. This dataset is standard for Universal Dependencies parsing and includes a wide variety of languages and treebank characteristics, including varying degrees of projectivity.
Key Insights and Ideas
- RL as a General Oracle Design Tool: The paper demonstrates that RL can be a powerful tool for approximating complex oracles, especially when exact dynamic oracles are difficult or impossible to derive.
- Approximate Oracles are Sufficient: The ADO, while not an "exact" dynamic oracle, provides sufficient guidance to significantly improve parser performance, often matching or exceeding the performance of exact dynamic oracles where available.
- Generalizability of the ADO: A single ADO trained on all treebanks can be used to train parsers across different transition systems and treebanks, making the approach highly efficient and reusable.
- Error Propagation Mitigation: The ADO effectively helps parsers learn to recover from or avoid cascading errors by providing a more nuanced cost signal than static oracles.
- Simpler Oracle Features: The ADO uses simpler, gold-tree-based features for its decision-making, contrasting with the more complex lexical features typically used by parsers.
Key Results
- Improved Parsing Accuracy: Parsers trained with the ADO consistently outperform parsers trained with static oracles across multiple transition systems (STANDARD, ATTARDI, SWAP, HYBRID).
- Comparable to Exact Dynamic Oracles: For the HYBRID system, where an exact dynamic oracle (EDO) was available, the ADO achieved very close performance, outperforming the static baseline by a similar margin.
- Significant Gains on Non-Projective Systems: The ADO showed particular benefit in non-projective systems, bridging the performance gap between projective and non-projective parsing.
- Robustness to Errors: The oracle recovery test showed that the ADO is robust to errors, introducing only a small percentage of additional errors even in challenging non-projective scenarios.
- Efficiency: Training a single ADO for all treebanks is more efficient than designing system-specific oracles.
Limitations and Future Work
- Suboptimal Actions: The paper acknowledges that the ADO can make suboptimal actions in certain complex scenarios (illustrated in Figure 3), particularly when a "harmless" shift might lead to future lost tokens. This suggests that further refinement of the reward function or state representation might be beneficial.
- Future Directions: The authors suggest that this approach can be extended to other structured prediction tasks beyond dependency parsing, such as graph parsing, by adapting the concept of learning structure costs from incremental rewards. Further investigation into eliminating the specific types of mistakes identified in the comparison with EDO is also a clear avenue for future work.
Summary updated