TL;DR
This paper presents a novel incremental dependency parser that trains to optimize sentence-level parsing costs rather than individual parsing decisions. By adapting an online learning approach, they achieve competitive performance while offering a more unified framework that bridges the gap between different parsing strategies.
What Problem Does This Paper Address?
Dependency parsing aims to determine the grammatical relationships between words in a sentence, often represented as a directed graph. Two dominant approaches in dependency parsing training exist: one that optimizes the overall sentence parse (like CKY-style parsers) and another that focuses on making optimal decisions at each step of an incremental parsing process (like shift-reduce parsers). These two approaches, while achieving similar top scores in shared tasks, are fundamentally different in their training objectives. This paper seeks to bridge this gap by developing an incremental parser that is trained to optimize sentence-level costs, thereby combining the strengths of both paradigms.
Methods
The authors adapt Nivre's shift-reduce parser, an incremental algorithm that builds dependency trees using a stack and a list of input words. To handle non-projective dependency trees (where arcs can cross), they employ a projectivization step during training and a de-projectivization step after parsing, using a "Head+Path" encoding to recover the original non-projective arcs.
A key innovation is the training methodology. Instead of optimizing individual parsing actions, they train the parser to minimize sentence-level costs. They achieve this by using the Online Passive-Aggressive (OPA) algorithm, a cost-sensitive online learning method. This allows them to incrementally update the model's weights based on sentence-level errors. To improve robustness, they also employ beam search during parsing, exploring multiple parsing paths to find a better overall score. Furthermore, they investigate bidirectional parsing, running the parser from both left-to-right and right-to-left and combining the results using a voting strategy.
Datasets
The paper evaluates the parser on the CoNLL-X shared task data, which includes treebanks for multiple languages: Arabic, Basque, Catalan, Chinese, Czech, English, Greek, Hungarian, Italian, and Turkish. Specific experiments on the Basque treebank are highlighted for beam width and directionality analysis.
Key Insights and Ideas
- Unifying Training Objectives: The core idea of training an incremental parser on sentence-level costs is a significant step towards unifying different parsing paradigms. This allows for the benefits of incremental parsing (efficiency) with the robustness of global optimization.
- Online Learning for Dependency Parsing: The successful application of the Online Passive-Aggressive algorithm demonstrates its viability for dependency parsing, offering a scalable alternative to computationally expensive batch methods like SVMstruct for large datasets.
- Bidirectional Parsing Benefits: The study shows that bidirectional parsing generally outperforms unidirectional parsing, especially on smaller treebanks, suggesting that leveraging information from both directions is crucial for robust parsing.
- Beam Search Effectiveness: Widening the beam search significantly improves parsing accuracy, indicating that exploring a larger set of candidate parses is beneficial, even for an incremental parser.
Key Results
The system achieved competitive results in the CoNLL-X multilingual task, with an average labeled attachment score of 75.78%. For the Basque test set, the OPA-trained parser achieved an accuracy of 75.08%, slightly lower than a local SVM-based classifier (75.53%), but the authors attribute this to the trade-off between global optimization and local classification accuracy. Beam search experiments on Basque showed that increasing the beam width from 2 to 12 improved accuracy from 72.01% to 75.49%. Bidirectional parsing on Basque also yielded better results (74.48%) compared to left-to-right (72.01%) or right-to-left (71.02%) parsing.
Limitations and Future Work
The authors acknowledge that their parser is outperformed by some local classifier-based systems, suggesting that further improvements could be made by optimizing learning parameters and feature sets. They also note that the optimal number of iterations was determined for Basque and applied to all languages, which might not be ideal for other treebanks. Future work could involve exploring more sophisticated feature engineering, investigating different online learning algorithms, and further optimizing the bidirectional parsing combination strategy. The paper also hints at the potential for combining this approach with other parsing techniques for further performance gains.
Summary updated