A Two-Stage Parser for Multilingual Dependency Parsing

Wenliang Chen, Yujie Zhang, Hitoshi IsaharaEMNLP 2007

TL;DR

This paper introduces a two-stage dependency parsing system that first identifies grammatical relationships (arcs) and then assigns specific labels to these relationships. This approach achieved competitive results on the CoNLL-2007 shared task, demonstrating its effectiveness across multiple languages.

What Problem Does This Paper Address?

Dependency parsing aims to represent the grammatical structure of a sentence by identifying the head-dependent relationships between words. A key challenge in multilingual dependency parsing is handling the diversity of linguistic structures and annotation schemes across different languages. Specifically, this paper tackles the problem of accurately assigning dependency labels (e.g., subject, object, modifier) to the identified grammatical arcs, which can be complex and language-specific. The authors also address the challenge of languages with varying conventions for marking the root of a sentence.

Methods

The proposed system employs a two-stage approach:

  1. Unlabeled Parser: This stage uses a deterministic dependency parsing algorithm, specifically based on Nivre's (2003) work, to identify the grammatical arcs between words. This algorithm operates in a left-to-right pass, utilizing a stack to manage tokens and making decisions based on four elementary actions: Left-Arc, Right-Arc, Reduce, and Shift. The system uses MaltParser (Nivre et al., 2006) with an SVM classifier and a quadratic kernel for this stage. Features used include word forms (FORM), lemmas, coarse-grained part-of-speech tags (CPOSTAG), fine-grained part-of-speech tags (POSTAG), and morphological features (FEATS).
  2. Sequence Labeler: The second stage treats the task of assigning dependency labels to the arcs as a sequence labeling problem. An SVM-based approach, implemented using YamCha (Kudo and Matsumoto, 2001), is employed. Features for this stage include information about the parent and child nodes (FORM, LEMMA, CPOSTAG, POSTAG, FEATS), relationships between them (direction, combined features), verb information, and neighbor information. Special features are designed for the ROOT labeler to handle languages with different root conventions (Arabic, Basque, Czech, and Greek).

Datasets

The system was evaluated on the ten languages provided by the CoNLL-2007 shared task organizers for the Multilingual Track. Specific details about the individual language datasets are not provided beyond their inclusion in the shared task.

Key Insights and Ideas

  • Decomposition of the problem: Separating the identification of grammatical arcs from the labeling of those arcs into two distinct stages simplifies the overall parsing task and allows for specialized models and features for each sub-problem.
  • Sequence labeling for dependency labels: Treating dependency label assignment as a sequence labeling problem is an effective way to leverage powerful sequence modeling techniques (like SVMs) and capture dependencies between labels.
  • Importance of language-specific features: The need for special features for the ROOT labeler highlights that linguistic variations, even at a high level like sentence root marking, require tailored handling for optimal performance.
  • Projective parsing limitations: The authors acknowledge that using only projective parsing algorithms might be a reason for slightly lower performance on languages that naturally exhibit non-projective structures.

Key Results

The proposed two-stage system achieved good performance across all ten languages in the CoNLL-2007 Multilingual Track. The system provided better results than the average performance of all participating systems for both labeled accuracy (LA) and unlabeled accuracy (UA). For Chinese, the system achieved 81.24% labeled accuracy and 85.91% unlabeled accuracy, outperforming the MaltParser alone by 0.4% labeled accuracy. The paper also identifies specific words in Chinese (like "的/DE", "/C") that are prone to errors, suggesting areas for future improvement.

Limitations and Future Work

  • Projective Parsing: The system exclusively uses projective parsing algorithms. For languages with significant non-projective structures, this can lead to suboptimal results. The authors suggest exploring pseudo-projective approaches for future work.
  • Parameter Tuning: The authors mention that they did not tune parameters extensively due to time constraints, implying that further optimization could improve performance.
  • Handling Ambiguity: For Chinese, the paper highlights the difficulty in distinguishing between "property" and "predication" labels for the particle "的/DE". Future work could involve incorporating background knowledge or more sophisticated features to resolve such ambiguities.
  • Specific Word Categories: The authors note that conjunctions, prepositions, and the particle "DE" attached to their head words were parsed with lower accuracy. They plan to define special features for these word categories in the future.

Summary updated

BibTeX
@inproceedings{chen2007two,
  author = {Wenliang Chen and Yujie Zhang and Hitoshi Isahara},
  title = {{A Two-Stage Parser for Multilingual Dependency Parsing}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2007},
}
Figure