📄 Parser Combination by Reparsing

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

• I1. 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.
• I2. 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.
• I3. 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.
• I4. 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.
• I5. 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.