TL;DR
This paper presents a system for dependency parsing that leverages k-best Maximum Spanning Tree (MST) parsing and a novel tree-based reranker. By generating multiple parse hypotheses and then reranking them with rich structural features, the system achieves improved accuracy, particularly for languages with non-projective dependency structures.
What Problem Does This Paper Address?
Traditional dependency parsers often rely on edge-factored models, which are limited in their ability to capture complex syntactic phenomena like non-projectivity. Non-projective dependencies occur when a word's dependent is not its immediate neighbor in the sentence, a common occurrence in many languages. While constituency parsers can handle these structures, they are often less efficient and accurate for dependency parsing. This paper addresses the challenge of building accurate dependency parsers that can effectively model non-projective structures by combining the efficiency of MST parsing with the expressive power of reranking.
Methods
The system comprises three main components, all utilizing log-linear models:
- k-best MST Parser: This component generates a set of k most likely dependency parse trees. The authors explore two training techniques for the MST parser: tree-normalized and graph-normalized conditional training. The core idea is to frame dependency parsing as finding a maximum spanning tree in a graph of possible dependencies.
- Tree Labeler: This component assigns dependency labels to the edges of the parsed trees. It uses a separate log-linear model trained on edge features, conjoined with potential labels.
- Tree-Reranker: This is the novel contribution. It takes the k parse trees from the MST parser and reorders them using a rich set of structural features. This reranker is crucial for improving accuracy by allowing the model to consider global syntactic phenomena that are difficult to capture in the initial parsing stage. The reranker is trained using a minimum-error approach, assuming the oracle-best parse is correct and others are incorrect.
Datasets
The system was evaluated on the CoNLL 2007 shared task data, which includes 10 languages: Arabic, Basque, Catalan, Chinese, Czech, English, Greek, Hungarian, Italian, and Turkish. The data originates from various dependency treebanks and transformed constituency-based treebanks. The authors also used a randomly sampled development set for parameter optimization.
Key Insights and Ideas
- k-best MST Parsing is Viable: The paper demonstrates that generating multiple parse hypotheses using k-best MST parsing significantly increases the "oracle accuracy" (the accuracy of the best hypothesis among the k options), even for relatively small values of k. This suggests that MST parsers, when allowed to produce multiple outputs, capture a good range of plausible parses.
- Reranking is Key for Non-Projectivity: The tree-based reranker, with its rich set of structural features, is essential for improving upon the base MST parser's performance. Features specifically designed to model non-projective configurations are highlighted as particularly important.
- Global Features Matter: The reranker's ability to incorporate global syntactic features (ancestors, subtree depth, word order interactions) is what allows it to overcome the limitations of edge-factored models used in the initial MST parsing.
- Tree Normalization Advantage: For MST training, tree normalization showed a slight advantage over graph normalization in terms of absolute dependency accuracy.
Key Results
- The oracle parsing accuracy of the k-best MST parser is considerably higher than the one-best score of the same parser. For example, Turkish showed a difference of 9.64% in accuracy between the one-best and 50-best oracle.
- The reranker improved upon the base MST parser's performance, though it did not always reach the oracle rates.
- The paper reports results for labeled and unlabeled dependency accuracy on the CoNLL 2007 evaluation set, showing improvements with increasing k and l (number of alternative labelings). For instance, for Arabic, the reranked accuracy for k=50, l=1 was 73.40% (83.45% unlabeled), compared to the 1-best score of 83.10% (85.56% unlabeled).
Limitations and Future Work
- Feature Set Limitations: The authors acknowledge that their reranker's feature set, while rich, was not able to achieve the oracle rates. They attribute this, in part, to the lack of lexicalized reranking models due to time constraints.
- Lexicalized Reranking: The introduction of lexicalized features in the reranker is suggested as a promising direction to improve the selection of better trees from the k-best hypothesis sets.
- Model Complexity: While the system achieves good results, the complexity of training and reranking multiple hypotheses can be computationally intensive. Future work might explore more efficient reranking strategies or feature selection.
Summary updated