--- title: "Parser Combination by Reparsing — Sagae 2006" description: "The paper addresses how to merge the outputs of several strong parsers into one analysis that beats each of them, while still producing a valid syntactic…" authors: ["Kenji Sagae", "Alon Lavie"] year: 2006 venue: "Proceedings of the Human Language Technology Conference of the NAACL, Companion Volume: Short Papers" source: "https://aclanthology.org/N06-2033/" licence: "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)" licence_url: "https://creativecommons.org/licenses/by-nc-sa/3.0/" summary_licence: "Elamur Cosmic License" canonical: "https://research.elamur.ai/free/en/papers/sagae-2006-parser-combination-reparsing/" --- [Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/sagae-2006-parser-combination-reparsing/) [home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2006](https://md.research.elamur.ai/free/en/papers/2006/) / Parser Combination by Reparsing # Parser Combination by Reparsing **Authors:** [Kenji Sagae](https://md.research.elamur.ai/free/en/authors/kenji-sagae/), [Alon Lavie](https://md.research.elamur.ai/free/en/authors/alon-lavie/) · **Year:** 2006 · **Venue:** Proceedings of the Human Language Technology Conference of the NAACL, Companion Volume: Short Papers · **Licence:** [CC BY-NC-SA 3.0 (ACL Anthology, before 2016)](https://creativecommons.org/licenses/by-nc-sa/3.0/) **Links:** [Publisher's page](https://aclanthology.org/N06-2033/) · [PDF](https://aclanthology.org/N06-2033.pdf) · [OpenAlex](https://openalex.org/W2128092251) **Citations:** 180 citations (openalex-snapshot · 2026-10-14) · [96](#cited-by) in our library, of the 140884 papers whose bibliographies we read ## Summary The paper addresses how to merge the outputs of several strong parsers into one analysis that beats each of them, while still producing a valid syntactic structure. Simple voting has a flaw. Word-level voting on heads can yield a graph that is not a tree, and constituent-level majority voting tends to favor precision at the cost of recall. Sagae and Lavie propose reparsing instead. The sentence is parsed a second time, but the search space and scores come only from the candidate analyses proposed by the first-stage parsers. For unlabeled dependencies, weighted edges from all parsers are pooled into a graph, and a maximum spanning tree is extracted. For Penn Treebank constituents, weighted constituents are merged into a chart, and a bottom-up search finds the heaviest well-formed tree. A weight threshold tuned on held-out data controls the precision/recall balance. On WSJ section 23, the combinations outperform every input parser: 92.7 unlabeled dependency accuracy and 92.1 constituent f-score. This shows that ensembles can respect structural constraints and still gain accuracy. ## Key points - Data: Penn Treebank WSJ, with sections 02–21 for training and section 23 for testing. For dependencies, section 00 was held out and section 22 used for development. Section 22 also served as held-out data for constituent tuning. Dependencies were converted using the Yamada & Matsumoto head-table. - Dependency ensemble: six parsers in total, including Nivre & Scholz–style shift-reduce parsers run left-to-right (LR) and right-to-left (RL), an alternating-direction Yamada & Matsumoto variant (LRRL), and McDonald et al.'s large-margin MST parser. The best single parser reached 91.0 accuracy (LR). - Dependency reparsing results by weighting scheme: - Equal weights: 91.8 - Per-parser accuracy weights: 92.1 - Per-parser, per-POS-of-dependent weights: 92.7, with root accuracy of 96.6 - Constituent ensemble: Charniak/Johnson reranker, Henderson's neural network parser, Bikel's Collins model 2, and two Sagae/Lavie shift-reduce parsers (MaxEnt and SVM). Individual f-scores ranged from 86.7 to 91.0. Reparsing tuned for maximum f-score reached 92.1 (93.2 precision, 91.0 recall). - The earlier Henderson & Brill majority vote is a special case of the method: all weights set to 1 and threshold t = (m+1)/2. Tuning t gives better results. Note that the extracted Table 2 row for this setting is garbled, so its exact numbers are unreliable. ## Interesting ideas - **Combine at the decoder level, not by voting on outputs.** Pooling candidate parts into a scored graph or chart and running a structured search guarantees well-formed output. The same idea applies to other structured tasks, such as merging NER spans or alignments from several systems. - **Reuse the base algorithm's own decoder.** The MST algorithm (Chu-Liu/Edmonds) handles non-projective trees, and Eisner's algorithm handles projective ones. The choice of structural constraint becomes a simple switch rather than a redesign. - **Get diversity cheaply.** Running the same deterministic parser in the opposite direction produces errors different enough to help the ensemble. This is useful when only one model architecture is available, for example for a low-resource language like Ukrainian. - **Weight votes by fine-grained reliability.** Measuring each system's accuracy per POS tag or per label on held-out data lets the ensemble exploit each component's specific strengths. This gave the largest dependency gain. - **Expose a threshold as a precision/recall dial.** A single cutoff on accumulated weight, tuned by hill-climbing on development data, lets the ensemble target either balanced precision and recall or maximum f-score. *Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.* Fields: [Natural language processing](https://md.research.elamur.ai/free/en/shelves/nlp/) ## Cited by Cited by 96 papers of our library cite it (of the 140884 whose bibliographies we read); 13 of them have a page here, 83 not yet. - [Evaluation of Dependency Parsers on Unbounded Dependencies](https://md.research.elamur.ai/free/en/papers/aclbulk-2010-nivre-evaluation-dependency-parsers-unbounded-dependencies/) - [It Depends: Dependency Parser Comparison Using A Web-based Evaluation Tool](https://md.research.elamur.ai/free/en/papers/aclbulk-2015-choi-it-depends-dependency-parser-comparison/) - [Multilingual Projection for Parsing Truly Low-Resource Languages](https://md.research.elamur.ai/free/en/papers/agic-2016-multilingual-projection-parsing-truly-low/) - [Cross-Lingual Parser Selection for Low-Resource Languages](https://md.research.elamur.ai/free/en/papers/agic-2017-cross-lingual-parser-selection-low/) - [Characterizing the Errors of Data-Driven Dependency Parsing Models](https://md.research.elamur.ai/free/en/papers/missing4-2007-mcdonald-characterizing-errors-data-driven-dependency/) - [The CoNLL 2007 Shared Task on Dependency Parsing](https://md.research.elamur.ai/free/en/papers/nivre-2007-conll-2007-shared-task-dependency/) - [Integrating Graph-Based and Transition-Based Dependency Parsers](https://md.research.elamur.ai/free/en/papers/nivre-2008-integrating-graph-based-transition-based/) - [Dependency Parsing and Domain Adaptation with LR Models and Parser Ensembles](https://md.research.elamur.ai/free/en/papers/sagae-2007-dependency-parsing-domain-adaptation-lr/) - [Overview of the SPMRL 2013 Shared Task: A Cross-Framework Evaluation of Parsing Morphologically Rich Languages](https://md.research.elamur.ai/free/en/papers/seddah-2013-overview-spmrl-2013-shared-task/) - ['IMS at the CoNLL 2017 UD Shared Task: CRFs and Perceptrons Meet Neural Networks'](https://md.research.elamur.ai/free/en/papers/ud-2017-bjorkelund-ims-conll-2017-ud-shared/) - [Integrating Graph-Based and Transition-Based Dependency Parsers in the Deep Contextualized Era](https://md.research.elamur.ai/free/en/papers/ud-2020-falenska-integrating-graph-based-transition-based/) - [A Tale of Two Parsers: Investigating and Combining Graph-based and Transition-based Dependency Parsing](https://md.research.elamur.ai/free/en/papers/zhang-2008-tale-two-parsers-investigating-combining/) - [Fast and Accurate Shift-Reduce Constituent Parsing](https://md.research.elamur.ai/free/en/papers/zhu-2013-fast-accurate-shift-reduce-constituent/) ## Cite The paper itself, not this page. BibTeX from the library's record of the work. ```bibtex @inproceedings{sagae2006parser, title = {{Parser Combination by Reparsing}}, author = {Sagae, Kenji and Lavie, Alon}, booktitle = {Proceedings of the Human Language Technology Conference of the NAACL, Companion Volume: Short Papers}, year = {2006}, doi = {10.3115/1614049.1614082}, url = {https://doi.org/10.3115/1614049.1614082} } ``` - [← previous Paraphrasing for Automatic Evaluation](https://md.research.elamur.ai/free/en/papers/kauchak-2006-paraphrasing-automatic-evaluation/) - [next → Parsing Arabic Dialects](https://md.research.elamur.ai/free/en/papers/aclbulk-2006-chiang-parsing-arabic-dialects/) - [↑ back to papers of 2006](https://md.research.elamur.ai/free/en/papers/2006/) ## References 14 references, 5 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet. 1. Allen, J. (1995). Natural Language Understanding (2nd ed.). Redwood City, CA: The Benjamin/Cummings Publishing Company, Inc. [find](https://scholar.google.com/scholar?q=Allen%2C+J%2E+%281995%29%2E+Natural+Language+Understanding+%282nd+ed%2E%29%2E+Redwood+City%2C+CA%3A+The+Benjamin%2FCummings+Publishing+Company%2C+Inc%2E) 2. Bikel, D. (2002). Design of a multi-lingual, parallel-processing statistical parsing engine. In Proceedings of HLT2002. San Diego, CA. [find](https://scholar.google.com/scholar?q=Bikel%2C+D%2E+%282002%29%2E+Design+of+a+multi%2Dlingual%2C+parallel%2Dprocessing+statistical+parsing+engine%2E+In+Proceedings+of+HLT2002%2E+San+Diego%2C+CA%2E) 3. Charniak, E., & Johnson, M. (2005). Coarse-to-fine nbest parsing and MaxEnt discriminative reranking. In Proceedings of the 43rd meeting of the Association for Computational Linguistics. Ann Arbor, MI. [find](https://scholar.google.com/scholar?q=Charniak%2C+E%2E%2C+%26+Johnson%2C+M%2E+%282005%29%2E+Coarse%2Dto%2Dfine+nbest+parsing+and+MaxEnt+discriminative+reranking%2E+In+Proceedings+of+the+43rd+meeting+of+the+Association+for+Computational+Linguistics%2E+Ann+Arbor%2C+MI) 4. Chu, Y. J., & Liu, T. H. (1965). On the shortest arborescence of a directed graph. Science Sinica(14), 1396-1400. [find](https://scholar.google.com/scholar?q=Chu%2C+Y%2E+J%2E%2C+%26+Liu%2C+T%2E+H%2E+%281965%29%2E+On+the+shortest+arborescence+of+a+directed+graph%2E+Science+Sinica%2814%29%2C+1396%2D1400%2E) 5. Edmonds, J. (1967). Optimum branchings. Journal of Research of the National Bureau of Standards(71B), 233-240. [find](https://scholar.google.com/scholar?q=Edmonds%2C+J%2E+%281967%29%2E+Optimum+branchings%2E+Journal+of+Research+of+the+National+Bureau+of+Standards%2871B%29%2C+233%2D240%2E) 6. Eisner, J. (1996). Three new probabilistic models for dependency parsing: An exploration. In Proceedings of the International Conference on Computational Linguistics (COLING'96). Copenhagen, Denmark. [find](https://scholar.google.com/scholar?q=Eisner%2C+J%2E+%281996%29%2E+Three+new+probabilistic+models+for+dependency+parsing%3A+An+exploration%2E+In+Proceedings+of+the+International+Conference+on+Computational+Linguistics+%28COLING%2796%29%2E+Copenhagen%2C+Denmark%2E) [our card](https://md.research.elamur.ai/free/en/papers/ast-1996-eisner-three-new-probabilistic-models-dependency/) 7. Henderson, J. (2004). Discriminative training of a neural network statistical parser. In Proceedings of the 42nd Meeting of the Association for Computational Linguistics. Barcelona, Spain. [find](https://scholar.google.com/scholar?q=Henderson%2C+J%2E+%282004%29%2E+Discriminative+training+of+a+neural+network+statistical+parser%2E+In+Proceedings+of+the+42nd+Meeting+of+the+Association+for+Computational+Linguistics%2E+Barcelona%2C+Spain%2E) 8. Henderson, J., & Brill, E. (1999). Exploiting diversity in natural language processing: combining parsers. In Proceedings of the Fourth Conference on Empirical Methods in Natural Language Processing (EMNLP). [find](https://scholar.google.com/scholar?q=Henderson%2C+J%2E%2C+%26+Brill%2C+E%2E+%281999%29%2E+Exploiting+diversity+in+natural+language+processing%3A+combining+parsers%2E+In+Proceedings+of+the+Fourth+Conference+on+Empirical+Methods+in+Natural+Language+Processing+%28) 9. Marcus, M. P., Santorini, B., & Marcinkiewics, M. A. (1993). Building a large annotated corpus of English: The Penn Treebank. Computational Linguistics, 19. [find](https://scholar.google.com/scholar?q=Marcus%2C+M%2E+P%2E%2C+Santorini%2C+B%2E%2C+%26+Marcinkiewics%2C+M%2E+A%2E+%281993%29%2E+Building+a+large+annotated+corpus+of+English%3A+The+Penn+Treebank%2E+Computational+Linguistics%2C+19%2E) [our card](https://md.research.elamur.ai/free/en/papers/bank-1993-marcus-building-large-annotated-corpus-english/) 10. McDonald, R., Pereira, F., Ribarov, K., & Hajic, J. (2005). Non-Projective Dependency Parsing using Spanning Tree Algorithms. In Proceedings of the Conference on Human Language Technologies/Empirical Methods in Natural Language Processing (HLT-EMNLP). Vancouver, Canada. [find](https://scholar.google.com/scholar?q=McDonald%2C+R%2E%2C+Pereira%2C+F%2E%2C+Ribarov%2C+K%2E%2C+%26+Hajic%2C+J%2E+%282005%29%2E+Non%2DProjective+Dependency+Parsing+using+Spanning+Tree+Algorithms%2E+In+Proceedings+of+the+Conference+on+Human+Language+Technologies%2FEmpirical+) [our card](https://md.research.elamur.ai/free/en/papers/narrative-2005-mcdonald-non-projective-dependency-parsing-spanning/) 11. Nivre, J., & Scholz, M. (2004). Deterministic dependency parsing of English text. In Proceedings of the 20th International Conference on Computational Linguistics (pp. 64-70). Geneva, Switzerland. [find](https://scholar.google.com/scholar?q=Nivre%2C+J%2E%2C+%26+Scholz%2C+M%2E+%282004%29%2E+Deterministic+dependency+parsing+of+English+text%2E+In+Proceedings+of+the+20th+International+Conference+on+Computational+Linguistics+%28pp%2E+64%2D70%29%2E+Geneva%2C+Switzerland%2E) [our card](https://md.research.elamur.ai/free/en/papers/aclbulk-2004-nivre-deterministic-dependency-parsing-english-text/) 12. Sagae, K., & Lavie, A. (2005). A classifier-based parser with linear run-time complexity. In Proceedings of the Ninth International Workshop on Parsing Technologies. Vancouver, Canada. [find](https://scholar.google.com/scholar?q=Sagae%2C+K%2E%2C+%26+Lavie%2C+A%2E+%282005%29%2E+A+classifier%2Dbased+parser+with+linear+run%2Dtime+complexity%2E+In+Proceedings+of+the+Ninth+International+Workshop+on+Parsing+Technologies%2E+Vancouver%2C+Canada%2E) [our card](https://md.research.elamur.ai/free/en/papers/sagae-2005-classifier-based-parser-linear-run/) 13. Yamada, H., & Matsumoto, Y. (2003). Statistical dependency analysis using support vector machines. In Proceedings of the Eighth International Workshop on Parsing Technologies. Nancy, France. [find](https://scholar.google.com/scholar?q=Yamada%2C+H%2E%2C+%26+Matsumoto%2C+Y%2E+%282003%29%2E+Statistical+dependency+analysis+using+support+vector+machines%2E+In+Proceedings+of+the+Eighth+International+Workshop+on+Parsing+Technologies%2E+Nancy%2C+France%2E) 14. Zeman, D., & Žabokrtský, Z. (2005). Improving Parsing Accuracy by Combining Diverse Dependency Parsers. In Proceedings of the International Workshop on Parsing Technologies. Vancouver, Canada. [find](https://scholar.google.com/scholar?q=Zeman%2C+D%2E%2C+%26+%C5%BDabokrtsk%C3%BD%2C+Z%2E+%282005%29%2E+Improving+Parsing+Accuracy+by+Combining+Diverse+Dependency+Parsers%2E+In+Proceedings+of+the+International+Workshop+on+Parsing+Technologies%2E+Vancouver%2C+Canada%2E)