Abstract
This paper introduces a Maximum Spanning Tree (MST) dependency parser that can be trained using only partially annotated sentences. By treating head-selection as an independent "pointwise" classification task rather than a global structural prediction, the authors achieve state-of-the-art accuracy while significantly reducing training time and enabling low-cost domain adaptation.
1. Introduction
Dependency parsing is a fundamental task in Natural Language Processing (NLP), identifying grammatical relationships between words. However, two primary challenges hinder its widespread application: the high cost of producing fully annotated corpora and the difficulty of domain adaptation. Traditional parsers, such as the Maximum Spanning Tree (MST) model by McDonald et al. (2005), rely on structural learning, requiring entire, perfectly annotated trees for training. This requirement makes it impossible to leverage "partial" data where only a subset of dependencies is labeled.
2. Methodology
The authors propose a Pointwise MST Parser designed to overcome these limitations.
2.1 Pointwise Estimation
Unlike global optimization models, the pointwise approach treats the selection of a head for each word as an independent $n$-class classification problem. A log-linear model (softmax) calculates the probability of word $i$ depending on word $j$ based on features such as distance, surface forms, and Part-of-Speech (POS) tags.
2.2 Maximum Spanning Tree Inference
During inference, the parser uses the MST algorithm (specifically Chu-Liu/Edmonds) to ensure the output is a valid tree. For Japanese, a "head-final" language, this process is simplified as heads always appear to the right of their dependents, allowing for a greedy selection of the highest-scoring candidate to the right for each word.
2.3 Rule-Based Conversion for Partial Annotation
To facilitate domain adaptation and utilize existing resources, the authors developed heuristic rules (e.g., "LAST", "PAREN", "INFLECT") to convert phrase-based (bunsetsu) Japanese corpora into partially annotated word-based corpora. This allows the model to learn from certain dependencies while ignoring ambiguous ones.
3. Experimental Evaluation
The method was evaluated on several Japanese datasets, including the general-domain EHJ (Example-based High-quality Japanese) and the NAIST Text Corpus (NTC) for domain adaptation. Testing was conducted on the Nikkei Newspaper (NKN) business news set.
3.1 Accuracy and Efficiency
The Pointwise (PW) model demonstrated competitive performance, achieving 96.83% accuracy on the EHJ test set, slightly exceeding the traditional MST parser (96.67%) and MaltParser (96.63%). Crucially, the PW model trained in just 125 seconds, a 15x speedup over the traditional MST parser's 1,901 seconds.
3.2 Domain Adaptation Results
By incorporating 5,000 partially annotated dependencies from the NTC corpus into the general training set, the authors achieved a 2.75% improvement in accuracy on the NKN business news test set. This demonstrates the effectiveness of using partial annotations to bridge domain shifts.
4. Discussion and Conclusion
The pointwise assumption, while theoretically ignoring some structural context, does not degrade accuracy for Japanese dependency parsing. Instead, it provides the flexibility to train on any subset of edges, significantly reducing the human effort required for corpus creation.
While the current implementation leverages specific properties of Japanese (head-final, projective), the framework is potentially extensible to other languages. Future work includes exploring active learning, where the model identifies uncertain edges for human annotation, further optimizing the data collection process.
Summary updated