TL;DR
This paper introduces a novel "reparsing" approach to combine the outputs of multiple syntactic parsers. By treating the initial parse trees as weighted suggestions, they build a new, more accurate parse tree that outperforms individual parsers on both dependency and constituent parsing tasks.
What Problem Does This Paper Address?
Syntactic parsing, the process of analyzing the grammatical structure of a sentence, is a fundamental task in Natural Language Processing (NLP). While significant progress has been made, achieving state-of-the-art accuracy with a single parser remains challenging. Individual parsers often have different strengths and weaknesses, leading to errors. The problem this paper addresses is how to effectively leverage the diverse outputs of multiple accurate parsers to create a single, superior parse tree, thereby improving overall parsing accuracy.
Methods
The core innovation is a two-stage "reparsing" framework.
- Initial Parsing: Several different parsers analyze the input sentence, each producing its own syntactic structure (either a dependency tree or a constituent tree).
- Reparsing: A new parsing algorithm is applied to the original sentence, but this time it's guided by the analyses from the initial parsers.
For dependency parsing, the initial dependency sets are used to build a directed graph where words are nodes and potential dependencies are weighted edges. The weight of an edge is determined by how many initial parsers suggest that specific dependency. A maximum spanning tree algorithm (like Chu-Liu/Edmonds) is then used to find the highest-weighted, well-formed dependency tree within this graph.
For constituent parsing, the initial constituent trees are decomposed into their constituent elements (defined by label, start/end words, and weight). These constituents are then merged if they are identical across multiple parsers, with their weights summed. This collection of weighted constituents is used to build a weighted parse chart. A bottom-up chart parsing algorithm is then employed to find the highest-weighted, well-formed constituent tree that can be constructed from these weighted constituents. A key aspect here is the introduction of a threshold parameter (t) to control the precision-recall tradeoff, allowing for the exclusion of less confident constituents.
Datasets
The experiments were conducted using the standard Penn Treebank dataset, specifically the Wall Street Journal (WSJ) corpus.
- Training Data: Sections 02-21 of the WSJ corpus.
- Test Data: Section 23 of the WSJ corpus.
- Held-out Data: Section 00 of the WSJ corpus was used for determining dependency weights.
- Development Data: Section 22 of the WSJ corpus was used for setting parameters in constituent parsing.
Key Insights and Ideas
- Leveraging Diversity: The paper demonstrates that combining diverse parsers, even those that are already highly accurate individually, can lead to significant improvements.
- Reparsing as a Unifying Framework: The "reparsing" approach provides a flexible way to integrate information from multiple parsers, moving beyond simple voting schemes.
- Weighted Graph/Chart Construction: The core idea of building a weighted graph (for dependencies) or chart (for constituents) from the outputs of initial parsers is a powerful way to represent the collective "opinion" of the parsers.
- Controlling Precision/Recall: The introduction of a threshold parameter (
t) in constituent parsing is crucial for balancing precision and recall, allowing fine-tuning of the combination strategy. - Well-formedness Constraint: The reparsing approach explicitly enforces the constraint that the final output must be a well-formed syntactic structure, which is a significant advantage over simpler combination methods.
Key Results
- Dependency Parsing: The "Reparse dep 3" setting achieved a dependency accuracy of 92.7% and a root accuracy of 96.6%, surpassing the best individual parsers (which had accuracies around 90-91% and root accuracies around 86-94%).
- Constituent Parsing: The "Reparse 3" setting achieved a precision of 93.2%, recall of 91.0%, and an f-score of 92.1%. This is a notable improvement over the best individual constituent parser, which had an f-score of 88.2% (or 91.0% for Charniak/Johnson). The paper highlights that combining parsers with f-scores ranging from 86.7% to 91.0% yielded a combined result with a 92.1% f-score.
Limitations and Future Work
- Computational Cost: The reparsing approach involves running multiple parsers initially and then running another parsing algorithm, which inherently increases computational cost compared to using a single parser.
- Parameter Tuning: For constituent parsing, setting the threshold parameter
trequires held-out data and a procedure (like hill-climbing) to find the optimal balance between precision and recall. - Future Work: The paper suggests exploring different weighting schemes and further investigating how to best balance precision and recall for optimal performance. The authors also imply that this framework could be extended to other NLP tasks where combining multiple models is beneficial.
Summary updated