TL;DR
This paper introduces a two-stage dependency parser that leverages "global" features, which consider the entire sentence's structure, to improve accuracy in multilingual dependency parsing. By combining an unlabeled dependency parser using Gibbs sampling with a Support Vector Machine (SVM) for relation labeling, the system achieved competitive results on the CoNLL 2007 shared task, demonstrating the effectiveness of global features across various languages.
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. Traditional dependency parsers often rely on "local" features, which consider only a few words at a time. However, linguistic phenomena can span longer distances within a sentence, and capturing these "global" dependencies can be challenging for purely local models. This paper addresses the difficulty of incorporating these global features into dependency parsers, especially in a multilingual setting where language-specific complexities abound. The authors aim to improve parsing accuracy by effectively integrating sentence-level (global) features alongside token-level (local) features.
Methods
The proposed system is a two-stage pipeline:
- Unlabeled Dependency Parsing (Gibbs Sampling): This component focuses on determining the dependency structure (which word is the head of which) without assigning specific relation labels. It uses a probabilistic model based on exponential language models, similar to those used for whole-sentence modeling. The key innovation here is the ability to incorporate arbitrary sentence-level (global) features alongside token-level (local) features. Due to the complexity introduced by global features, exact inference is intractable, so the system employs Gibbs sampling to approximate the posterior distribution of dependency structures. The output of this stage is a set of approximate dependency structures.
- Dependency Relation Labeling (SVM): Once the unlabeled dependency structure is determined, a separate module assigns the specific dependency relation labels (e.g., subject, object, modifier) to each dependency arc. This is framed as a multi-class classification problem, and the authors use Support Vector Machines (SVMs) with a second-order polynomial kernel. To handle the computational cost of multi-class SVMs, they employ a "revision learning" method, which combines a probabilistic model (Maximum Entropy) with a binary classifier (SVM) to improve accuracy and efficiency.
The system also incorporates a maximum spanning tree (MST) framework for finding the best dependency tree based on edge scores derived from the probabilistic model. Parameter estimation for both the global and local models is performed using maximum a posteriori estimation with Gaussian priors and quasi-Newton methods.
Datasets
The system was evaluated on data sets from the CoNLL 2007 Shared Task on Dependency Parsing, which included 10 languages: Basque, Catalan, Chinese, Czech, English, Greek, Hungarian, Italian, Turkish, and Arabic. The paper does not mention the creation of any new datasets.
Key Insights and Ideas
- Global Features are Crucial: The paper strongly advocates for the use of global features in dependency parsing, demonstrating their positive impact on accuracy across most languages. This challenges the notion that only local information is sufficient for accurate parsing.
- Gibbs Sampling for Global Features: The use of Gibbs sampling is a practical approach to handle the computational complexity of incorporating global features, which makes exact inference difficult.
- Two-Stage Approach Effectiveness: Separating unlabeled parsing from relation labeling, and then using SVMs for the latter, proves to be an effective strategy, especially for multilingual tasks.
- Feature Engineering Matters: The specific global features designed (e.g., "Parent+All Children," "Child+Ancestor") capture important long-range dependencies, such as those involving conjunctions, which significantly improve parsing accuracy.
- Multilingual Challenges: The results highlight that the effectiveness of different parsing algorithms (Eisner vs. CLE) and the impact of global features can vary across languages, likely due to differences in their syntactic structures and the prevalence of non-projective dependencies.
Key Results
- The system achieved the second best average accuracy in terms of Labeled Attachment Score (LAS) and the best average accuracy in terms of Unlabeled Attachment Score (UAS) among participating systems in the CoNLL 2007 shared task.
- Using global features improved accuracy in all languages except Turkish when using the Eisner algorithm.
- Significant improvements were observed in Chinese and Czech when global features were introduced. For example, in Chinese (Eisner), accuracy for tokens with conjunctions as parts-of-speech improved from 80.5% to 86.0%.
- The CLE algorithm generally performed better than the Eisner algorithm for languages with a higher percentage of non-projective sentences (Basque, Czech, Hungarian, Italian, Turkish).
Limitations and Future Work
- Labeled Attachment Score Improvement: The authors note that the gap between their labeled and unlabeled scores is relatively large. They suggest that improving the labeled attachment score could be achieved by performing the parsing and labeling processes simultaneously, rather than as a post-processing step, and by taking dependencies among labels into account.
- Parameter Estimation Efficiency: The paper mentions that static Monte Carlo methods for parameter estimation can become inefficient for high-dimensional distributions, suggesting that more sophisticated methods might be needed for accurate parameter estimation.
- Future Work: The authors explicitly state that improving dependency relation labeling is left for future work.
Summary updated