Source-linked AI summary
A Minimal Span-Based Neural Constituency Parser
Mitchell Stern, Jacob Andreas, Dan Klein
TL;DR
Constituency parsing needs models that produce well-formed trees while retaining efficient inference. This paper introduces an independent span-and-label scoring model supporting chart-based and greedy top-down decoding, achieving state-of-the-art Penn Treebank performance and strong French Treebank performance.
Problem
Existing neural parsers often require explicit structural constraints, while transition-based models lack fast dynamic programs and recurrent-state models need complex training for non-greedy inference.
Method
The paper scores constituent spans and labels independently, then uses the resulting model with exact chart decoding or greedy top-down recursive partitioning.
Results
91.79 F1 on the Penn Treebank and 82.23 F1 on the French Treebank demonstrate state-of-the-art and strong performance, respectively.
Takeaways & Limitations
Both chart-based and top-down inference achieve strong parsing performance, with the best models reaching state-of-the-art results on the Penn Treebank.
Takeaways & Limitations
Top-down training can expose the model only to gold-tree decisions, leaving it unexposed to mistakes and potentially causing poor test-time calibration and performance.
Abstract
from arXiv · showhide
In this work, we present a minimal neural model for constituency parsing based on independent scoring of labels and spans. We show that this model is not only compatible with classical dynamic programming techniques, but also admits a novel greedy top-down inference algorithm based on recursive partitioning of the input. We demonstrate empirically that both prediction schemes are competitive with recent work, and when combined with basic extensions to the scoring model are capable of achieving state-of-the-art single-model performance on the Penn Treebank (91.79 F1) and strong performance on the French Treebank (82.23 F1).
1 Introduction
The paper seeks a simple neural constituency parser that preserves structural validity without the drawbacks of transition-based or heavily scaffolded chart-based systems. It introduces a span-based chart model with greedy top-down inference and reports strong English and French results.
- Prior approaches: Transition-based parsers enforce well-formedness through incremental operations but lack fast dynamic programs and may require careful feature engineering for exact search.Recurrent-state models also face complex training procedures beyond greedy decoding.
- Prior approaches: Chart parsers support exact inference and structured losses but have required substantial scaffolding beyond a simple well-formedness potential.Examples include specifying a complete context-free grammar and initially pruning structures.
- Contribution: The model scores spans and labels independently, supporting both chart-based and greedy top-down parsing.The top-down procedure recursively partitions the input while retaining span-oriented representations.
- Results: 91.79 F1 on the Penn Treebank outperforms several recent chart-based and transition-based models, including the cited state-of-the-art systems.The approach also obtains 82.23 F1 on the French Treebank.
2 Model
The parser represents constituency trees as labeled spans and uses recurrent contextual representations to score both span labels and span existence. It accommodates unary chains, empty labels, and structured label composition within this minimal framework.
- Span representation: A constituency tree is modeled as labeled spans, with one component scoring labels and another scoring whether spans exist.Label scores determine output labeling, while span scores provide structure.
- Span representation: Bidirectional LSTM encodings represent span (i, j) using differences between forward and backward endpoint representations.This is a bidirectional version of LSTM-Minus features.
- Scoring: One-layer feedforward networks map each span representation to either a vector of label scores or a single span score.The label and span scoring functions share the same span representation as input.
- Label inventory: Unary chains are treated as atomic labels, and a special empty label supports spans arising from implicit binarization of n-ary trees.The empty label is included alongside elementary nonterminals and unary-chain labels.
3 Chart Parsing
The chart parser sums independent label and span potentials over labeled spans and finds the highest-scoring tree with a modified CKY dynamic program. Margin-based training and loss augmentation exploit the separation between labeling and structural decisions.
- Tree scoring: The score of a constituency tree is the sum of independent label and span scores over its constituent spans.This decomposed objective represents the tree through labeled spans.
- Dynamic programming: The modified CKY recursion performs exact chart inference in O(n3) time for a sentence of length n.It combines subspan scores over candidate split points.
- Dynamic programming: Because label and span scores are independent, each joint decision decomposes into separate label and split maximizations, reducing the state space.Span scores can be precomputed once, yielding a quadratic number of span-score computations.
- Margin training: Margin-based training compares the best predicted tree with the gold tree and penalizes violations of a margin of at least 1.The total objective sums hinge penalties across training examples.
- Structured loss: Loss-augmented decoding incorporates a Hamming loss on labeled spans by modifying label scores during dynamic programming.Since label decisions are isolated from structural decisions, the loss can be added directly to label scoring.
- Structured loss: The structured loss requires larger margins for predictions containing more mistakes, offering greater robustness and better generalization.The loss compares predicted and reference labels at spans.
4 Top-Down Parsing
The parser constructs trees greedily from the top down by independently labeling spans and selecting split points, recursively stopping at singleton spans. Training uses margin-based local decisions, while dynamic-oracle exploration addresses exposure to model mistakes.
- Top-Down Inference: Top-down inference independently assigns each span a label and split point, then recursively processes the left and right subspans.Recursion terminates at singleton spans, which cannot be split.
- Top-Down Inference: O(n^2) runtime follows from one label evaluation and at most n −1 split-point evaluations during recursive parsing.
- Top-Down Inference: The top-down procedure selects splits using only top-level span evaluations, unlike chart parsing, which can use scores of already-computed subtrees.
- Top-Down Inference: Despite this difference, the authors report no performance loss when replacing globally optimal chart inference with greedy top-down inference.
- Training: Margin training accumulates local hinge penalties for incorrect labels and split points at gold-tree decision points.
- Training: A dynamic oracle supplies valid labels and split points after deviations from the gold tree, enabling exploration during training.For nongold spans, split decisions use boundaries from the smallest enclosing gold constituent; multiple binarizations may be valid.
- Training: Training with exploration follows model-predicted decisions rather than always tracing the gold tree, exposing supervision to states likely at test time.
5 Scoring and Loss Alternatives
The paper explores structured label representations and several split-scoring alternatives while retaining a minimal span-based neural architecture. These extensions introduce parameter sharing and richer structural scoring choices, but exposing additional label structure can reduce performance.
- Top-Middle-Bottom Label Scoring: The model can decompose labels into top nonterminal, middle unary chain, and bottom nonterminal components, each possibly empty.The final label concatenates the three components while omitting empty ones.
- Top-Middle-Bottom Label Scoring: Structured label decomposition shares parameters across labels with common subcomponents and permits novel unary chains at test time.
- Split Scoring: Distinct left and right feedforward networks can replace the shared span scorer when assigning scores to a split's child spans.
- Split Scoring: A concatenation-based network can directly score a split from the representations of its left and right subspans.The implementation omits outside-span features because they did not improve performance.
- Split Scoring: A deep biaffine alternative scores splits using transformed left and right span representations, combining a bilinear form with two inner products.
- Label Loss: Structured Hamming loss compares labels as multisets of nonterminals and penalizes their asymmetric differences.
6 Experiments
Experiments evaluate the parser across datasets, label losses, labeling schemes, and split-scoring functions. The model achieves strong Penn Treebank results and competitive French Treebank performance, while top-down decoding is substantially faster than chart decoding.
- Scoring functions: Left-right and concatenation split scoring outperform minimal and deep biaffine scoring across label-loss settings.The left-right scheme slightly outperforms concatenation in all but one case and is stronger than deep biaffine throughout.
- Label losses: 0-1 and structured Hamming label losses produce scores within 0.1 of each other across all eight tested cases.The 0-1 loss is slightly higher in four cases and slightly lower in the other four.
- Labeling schemes: Top-middle-bottom label scoring generally performs worse than atomic label scoring, although minimal scoring can exceed left-right scoring in one chart-parser setting.Similar trends hold across split-scoring functions, with minimal scoring closer to left-right under the structured labeling scheme.
- Final test results: 91.79 F1 is achieved on the Penn Treebank, while French Treebank performance is competitive with a neural CRF parser but below Cross and Huang (2016).The final Penn Treebank comparison includes single-model parsers trained without external parse data.
- Efficiency: 75.5 sentences per second for top-down parsing exceeds the chart parser's 20.3 sentences per second on the test set.Both speeds were measured one sentence at a time on a c4.4xlarge Amazon EC2 instance.
7 Related Work
The paper contrasts earlier output-space modeling with its direct input-space approach, which uses rich representations to parameterize local potentials in a comparatively unconstrained structured decoder.
- Output- and input-space modeling: Earlier constituency parsers modeled output correlations through enriched probabilistic context-free grammars capturing long-distance dependencies and lexical phenomena.The paper instead follows recent work that models correlations in the input space.
- Output- and input-space modeling: The described approach uses rich input feature representations to parameterize local potentials while leaving the structured output comparatively unconstrained.
8 Conclusion
The paper presents a minimal span-oriented parser with independent span and label potentials, supporting both exact chart decoding and novel top-down inference. Both approaches perform strongly on English, and the best model is competitive on French.
- Model: The parser scores trees as sums of independent potentials over constituent spans and labels using recurrent input representations.
- Inference and results: Both exact chart-based decoding and novel top-down inference achieve state-of-the-art performance on the Penn Treebank.
- Inference and results: The best model achieves competitive performance on the French Treebank.
- Implication: The experiments show that insights from neural transition-based parsing can transfer to chart parsing while retaining extremely simple models.