TL;DR
This paper introduces a novel data-driven LR parsing framework for dependency parsing, extending it with best-first search for probabilistic parsing. The authors demonstrate its effectiveness in both multilingual parsing and domain adaptation tasks, achieving top results by leveraging parser ensembles and a clever co-training-like approach for domain adaptation.
What Problem Does This Paper Address?
Dependency parsing aims to determine the grammatical relationships between words in a sentence, often represented as a tree structure. While various sophisticated dependency parsers exist, this paper bridges the gap between current shift-reduce parsing methods and the well-established LR parsing algorithms. Furthermore, it tackles two significant challenges in natural language processing: building parsers that work across many languages (multilingual parsing) and adapting parsers trained on one domain of text to perform well on a different domain (domain adaptation). Existing approaches often require extensive language-specific engineering or large amounts of labeled data for new domains, making them less practical.
Methods
The core of the paper is a probabilistic, data-driven variant of the LR parsing algorithm. Instead of relying on a hand-crafted grammar and LR tables, this approach uses a classifier to predict parser actions (shift or reduce) based on features derived from the parser's current state (stack and lookahead). Key methodological contributions include:
- Probabilistic LR Parsing: Generalizing deterministic LR parsing to a probabilistic framework using a best-first search strategy, similar to techniques used in constituent parsing. This allows for exploring multiple parsing possibilities and selecting the most probable one.
- Parser Ensembles: Demonstrating that combining the outputs of multiple parsers, even those based on the same algorithm but trained with different learners or directions (forward/backward), can significantly improve accuracy. This is achieved using a maximum spanning tree voting scheme.
- Domain Adaptation: Proposing a straightforward method for domain adaptation that leverages unlabeled data in the target domain. This involves training initial parsers on out-of-domain data, using them to parse unlabeled in-domain data, and then selecting sentences where the parsers agree. These "agreed-upon" sentences are then added to the training set to retrain the parser, effectively adapting it to the new domain. This is described as a scheme similar to one iteration of co-training.
- Pseudo-Projectivity: Handling non-projective dependency structures (where arcs cross) using pseudo-projective transformations, specifically Nivre and Nilsson's PATH scheme.
Datasets
The paper evaluates its approach on the CoNLL 2007 shared task datasets, which included:
- Multilingual Track: Treebanks for ten languages: Arabic, Basque, Catalan, Chinese, Czech, English, Greek, Hungarian, Italian, and Turkish.
- Domain Adaptation Track: English training data from the Wall Street Journal (Penn Treebank) converted to dependencies, and evaluation data from the biological (development set) and chemical (test set) domains. Optionally, text from the CHILDES database was also available.
Key Insights and Ideas
- LR Parsing's Versatility: The paper shows that the well-established LR parsing framework, often associated with compiler construction, can be effectively adapted for modern statistical dependency parsing, connecting it to current research.
- Agreement as a Signal of Correctness: The domain adaptation approach hinges on the insight that when multiple parsers, trained differently, agree on an analysis, it's a strong indicator of correctness, even if their individual accuracies are moderate.
- Ensembles are Powerful, Even with Similar Parsers: The success of combining parsers trained with different learners (MaxEnt, SVM) and directions (forward, backward) highlights the benefit of diversity in parser ensembles, even within a single algorithmic family.
- Unlabeled Data is Valuable for Adaptation: The domain adaptation method effectively utilizes unlabeled data in the target domain, which is often more readily available than labeled data, to significantly boost parser performance.
Key Results
- Multilingual Parsing: The system achieved an average labeled attachment score of 79.90% across ten languages, placing it just 0.43% below the top-scoring system. For several languages, their results were among the top three.
- Domain Adaptation: The system achieved the highest labeled attachment score (81.06%) and unlabeled attachment score (83.42%) in the domain adaptation track. This was achieved without using additional resources (closed track) and surpassed the top score in the open track.
- Agreement Accuracy: In the domain adaptation experiments, sentences where the two initial parsers agreed had labeled attachment scores over 90%, demonstrating the power of their agreement-based selection.
Limitations and Future Work
- Feature Engineering: The authors note that the same set of features and meta-parameters were used for all languages in the multilingual track due to time constraints. Fine-tuning these could potentially improve accuracy further.
- Weighting Schemes: While a simple maximum spanning tree voting scheme was used for combining parsers, the authors suggest that more sophisticated weighting schemes proposed by Sagae and Lavie might yield even better results.
- Model Diversity: The paper primarily focuses on ensembles of LR-based parsers. The authors suggest that incorporating parsers based on fundamentally different approaches (e.g., MSTParser) could lead to greater improvements.
- Computational Cost: Training SVM parsers was noted as being significantly longer than MaxEnt parsers, and parsing with memory-based language processing models can be slower. This suggests a trade-off between accuracy and computational resources.
- Further Ensemble Exploration: The authors propose training more models with no other changes to the setup as a simple improvement, and exploring other learning approaches like memory-based language processing.
Summary updated