A Three-Step Deterministic Parser for Chinese Dependency Parsing

Kun Yu, Sadao Kurohashi, Hao LiuNAACL 2007

TL;DR

This paper introduces a novel three-step deterministic dependency parser for Chinese that significantly improves accuracy by breaking down sentences into smaller, independently parsable sub-sentences. This approach effectively mitigates the error propagation inherent in traditional greedy deterministic parsers, leading to substantial gains in dependency accuracy.

What Problem Does This Paper Address?

Deterministic dependency parsing offers efficiency and simplicity, but its greedy nature leads to error propagation. When a parser makes a locally optimal choice that's globally incorrect, this mistake can cascade, leading to further errors down the line. This is particularly problematic for languages like Chinese, which can have complex sentence structures. Previous attempts to address this, like dividing sentences into just two parts, proved insufficient for more complex constructions. This paper tackles the challenge of reducing error propagation in Chinese dependency parsing by proposing a more robust, multi-stage parsing strategy.

Methods

The core innovation is a three-step approach:

  1. Sentence Segmentation: The parser first identifies and segments sentences into smaller "sub-sentences" using punctuation marks that are identified as common separators. A Support Vector Machine (SVM) classifier is trained to distinguish "good" punctuation separators from "bad" ones, using a rich set of binary features related to word context, part-of-speech tags, and punctuation types.
  2. Sub-sentence Parsing: Each segmented sub-sentence is then parsed independently using a standard shift-reduce parser. This parser is trained using SVMs and a comprehensive set of local and global features, including word/POS tags, child word/POS tags, distance, and baseNP chunking information.
  3. Parsing Combination: Finally, the dependency structures of the sub-sentences are combined. The "main-root" (the head of the entire sentence) is identified, and the sub-sentence structures are attached to it, along with the punctuation marks used for segmentation.

Datasets

The paper uses the Penn Chinese Treebank 5.1 for both training and testing. Head rules from Xia's head percolation table are used to convert phrase structures to dependency structures.

Key Insights and Ideas

  • Punctuation as a Structural Cue: The paper highlights that specific punctuation marks, when dependent on the main-root, can serve as reliable separators for sub-sentences. This observation is key to the sentence segmentation step.
  • Decomposition for Robustness: Breaking down a complex sentence into smaller, more manageable sub-sentences significantly reduces the impact of individual parsing errors. Each sub-sentence is parsed in isolation, preventing errors from cascading across the entire sentence.
  • Independent Sub-sentences: The segmentation strategy aims to create sub-sentences that are largely independent, making them easier to parse accurately.
  • Mitigating Error Propagation: The primary benefit of this multi-step approach is its effectiveness in combating the error propagation problem inherent in greedy deterministic parsers.

Key Results

  • The proposed three-step parser achieved a 2.14% increase in dependency accuracy and a 1.01% increase in root accuracy compared to a standard one-step deterministic parser. This improvement was statistically significant (p<0.0001).
  • The parser also demonstrated strong performance on complex sentences (those with two or more sub-sentences), outperforming the one-step parser by 2.38% in dependency accuracy.
  • While the parsing time increased slightly (by 2.14 seconds on average per sentence), the authors deemed this acceptable given the significant accuracy gains.
  • Evaluation of individual modules showed that the sentence root finder had the lowest accuracy, suggesting it as a key area for future improvement.

Limitations and Future Work

  • Language Specificity: The current parser is designed specifically for Chinese. The authors believe it can be adapted to other languages, as it doesn't rely on language-specific information, but this remains a future research direction.
  • Module Accuracy: The accuracy of the individual modules (sentence segmenter, sub-sentence root finder, baseNP chunker, sub-sentence parser, sentence root finder) directly impacts the overall performance. Improving the accuracy of the sentence root finder and sub-sentence root finder is identified as a crucial area for future work.
  • Root Finding: The paper notes that improving the root finders (both for sub-sentences and the main sentence) is essential for further advancements.

Summary updated

BibTeX
@inproceedings{yu2007three,
  author = {Kun Yu and Sadao Kurohashi and Hao Liu},
  title = {{A Three-Step Deterministic Parser for Chinese Dependency Parsing}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2007},
}
Figure