Multilingual Deterministic Dependency Parsing Framework using Modified Finite Newton Method Support Vector Machines

Yu-Chieh Wu, Jie-Chi Yang, Yue-Shi LeeEMNLP 2007

TL;DR

This paper introduces a novel three-stage framework for multilingual dependency parsing, combining specialized "neighbor" and "root" parsers with a modified finite Newton method Support Vector Machine (MFN-SVM) for the main parsing task. This approach significantly improves parsing accuracy by leveraging richer features derived from the initial stages, achieving competitive results in the CoNLL-2007 shared task.

What Problem Does This Paper Address?

Dependency parsing aims to uncover the grammatical relationships between words in a sentence, representing them as a directed graph. While significant progress has been made, building robust parsers that work across many languages (multilingual parsing) and adapt to different domains remains a challenge. Existing methods often rely on language-specific knowledge or struggle with the complexity of diverse linguistic structures. This paper tackles the problem of creating a more general and effective multilingual dependency parser by enhancing the feature set available to a deterministic shift-reduce parser through specialized pre-processing steps.

Methods

The core of the proposed system is a three-pass pipeline:

  1. Neighbor Parser: This stage identifies head-modifier relationships between adjacent words. It treats this as a sequential tagging problem, using Conditional Random Fields (CRFs) as learners. The key innovation here is to simplify the problem by focusing on just three relation types (left head, right head, out-of-neighbor) for efficiency, especially for languages with complex root structures.
  2. Root Parser: Following the neighbor parser, this stage identifies the root word of each sentence. This is also framed as a sequential tagging task. The output of the neighbor parser is used as a feature for the root parser.
  3. Shift-Reduce Parser: This is the main parsing engine, employing a modified deterministic shift-reduce algorithm (based on Yamada and Matsumoto, 2003). Crucially, the outputs from the neighbor and root parsers are incorporated as additional features for this stage. To speed up training, the authors use a Modified Finite Newton method Support Vector Machine (MFN-SVM), which offers linear time complexity for learning. The system also incorporates pseudo-projective encoding/decoding to handle non-projective structures common in real-world treebanks.

Datasets

The paper evaluates its system on the CoNLL-2007 shared task dataset, which includes treebanks for 10 different languages. Specific mention is made of the "pchemtb_closed" and "CHILDES closed" datasets, with notes on how their data was handled due to format issues or missing relation tags.

Key Insights and Ideas

  • Leveraging Neighbor and Root Information: The most significant insight is that explicitly modeling neighbor and root relationships as separate, preceding steps provides valuable features that substantially boost the performance of the main shift-reduce parser. This is more effective than directly using the outputs of these parsers as the final parse.
  • Efficiency through Simplification: For the neighbor and root parsers, simplifying the task to a few key relation types (e.g., left/right head) dramatically reduces training time without sacrificing overall performance, making the system more practical for multilingual applications.
  • MFN-SVM for Scalability: The adoption of MFN-SVM is a key enabler for training on large datasets and for multilingual settings, as it provides linear time complexity for learning, a significant advantage over traditional SVMs.
  • Pseudo-Projectivity as a Standard: The use of pseudo-projective encoding/decoding is highlighted as a standard technique to handle non-projective treebanks, allowing deterministic parsers to achieve good performance on such data.

Key Results

  • The proposed system achieved a middle rank among 23 teams in the CoNLL-2007 shared task.
  • For languages like English and Chinese, substantial benefits were observed from the neighbor and root parsers, with labeled attachment scores (LAS) improving significantly. For instance, English LAS increased from 79.49 to 84.27.
  • However, for some languages like Basque and Turkish, the neighbor and root parsers had a marginally negative or even detrimental effect on performance. The authors attribute this to the weak performance of the neighbor parser on these specific languages.
  • The MFN-SVM learner allowed for linear time training, which is crucial for efficiency.

Limitations and Future Work

  • Feature Set Uniformity: The paper acknowledges that using a single, unified feature set for all 10 languages might not be optimal. They suggest that parameter tuning and feature selection specific to each language could further improve performance. This is identified as a key area for future work.
  • Neighbor Parser Improvement: The negative impact on some languages is linked to the neighbor parser's performance. Improving this component is seen as a direct path to better overall results.
  • Alternative Learners: The authors plan to explore replacing the MFN-SVM with a polynomial kernel SVM, as preliminary studies showed it outperformed linear kernels on some languages.
  • Approximate N-Best Parsing: Investigating how to convert the deterministic parser into an approximate N-best parser is another future direction, which could enable parse reranking for further accuracy gains.

Summary updated

BibTeX
@inproceedings{wu2007multilingual,
  author = {Yu-Chieh Wu and Jie-Chi Yang and Yue-Shi Lee},
  title = {{Multilingual Deterministic Dependency Parsing Framework using Modified Finite Newton Method Support Vector Machines}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2007},
}
Figure