Source-linked AI summary
Span-Based Constituency Parsing with a Structure-Label System and Provably Optimal Dynamic Oracles
James Cross, Liang Huang
TL;DR
Neural constituency parsers have lagged behind state-of-the-art systems despite advances in neural dependency parsing. This paper introduces a span-based factored transition parser with minimal LSTM features and a provably optimal amortized O(1) dynamic oracle. It reports state-of-the-art accuracy for Penn Treebank parsing without reranking, using strictly greedy inference, and the best F1 results for English and French under the stated closed-training-set conditions.
Problem
Neural approaches have improved dependency parsing but remain behind state-of-the-art constituency parsers, which are also generally harder to parse accurately and efficiently.
Source: §1 · p. 1Method
Results
The parser achieves the best reported F1 scores for English and French among parsers without reranking or external data, while retaining strictly greedy inference.
Source: §1 · pp. 1–2, §7 · p. 9Takeaways & Limitations
A span-centered greedy transition design can deliver state-of-the-art constituency accuracy with a fast optimal training oracle.
Source: §1 · p. 1, §7 · p. 9The experiments used very little hyperparameter tuning, and the authors state that performance could improve with larger models, external embeddings, random restarts, or grid search.
Source: §6.4 · p. 9
Abstract
from arXiv · showhide
Parsing accuracy using efficient greedy transition systems has improved dramatically in recent years thanks to neural networks. Despite striking results in dependency parsing, however, neural models have not surpassed state-of-the-art approaches in constituency parsing. To remedy this, we introduce a new shift-reduce system whose stack contains merely sentence spans, represented by a bare minimum of LSTM features. We also design the first provably optimal dynamic oracle for constituency parsing, which runs in amortized O(1) time, compared to O(n^3) oracles for standard dependency parsing. Training with this oracle, we achieve the best F1 scores on both English and French of any parser that does not use reranking or external data.
1 Introduction
Neural approaches have advanced dependency parsing but remain behind state-of-the-art constituency parsers, motivating a span-focused neural transition system. The paper combines factored span actions, minimal LSTM representations, and an efficient optimal dynamic oracle, achieving the best reported F1 scores for English and French under its stated training constraints.
Motivation
- Constituency parsing remains harder than dependency parsing, while neural models have not surpassed constituency state of the art.The difficulty concerns both parsing accuracy and runtime, and prior neural approaches remain behind established constituency systems.Source: §1 · p. 1
Parsing system
- The parser uses a factored shift-reduce system whose stack contains sentence spans rather than partial trees, alternating structural and label actions.Structural actions simplify shift-reduce operations, while label actions assign nonterminal symbols to spans.Source: §1 · p. 1
Neural model
- A neural model represents spans with differences of multilayer bidirectional LSTM outputs and uses only a few span features.The model processes each sentence once per parse, with four features for structural actions and three for label actions; pretrained embeddings are unnecessary.Source: §1 · p. 1
Dynamic oracle
- The paper introduces the first provably optimal constituency dynamic oracle with amortized O(1) computation.The oracle is optimal for F1, precision, and recall, extending dynamic-oracle methods from dependency parsing.Source: §1 · pp. 1–2
Results
- Best F1 scores were achieved for English and French by a single-model parser trained without reranking or external data.The result is reported for parsers trained only on the Penn Treebank and French Treebank.Source: §1 · pp. 1–2
Availability
- The work releases source code for one implementation of the parser.This implementation is publicly released alongside the paper.Source: §1 · p. 2
2 Parsing System
The parser builds constituency trees around sentence spans, using alternating structural and label actions on a stack that need not contain partial trees.
Parsing System
- The stack contains sentence spans rather than partial trees, making spans the parser’s fundamental unit of computation.Stack elements need not correspond to tree structures during parsing.Source: §2 · p. 2
- Structural actions alternate with label actions: shift or nondirectional combine constructs spans, while labels optionally assign nonterminals or unary chains.Nolabel leaves a span unlabeled and returns control to a structural step.Source: §2 · p. 2
- Because stack elements are not tree-structured, the system supports arbitrary-arity productions without binarization and removes shift-reduce directionality.This span-based design is presented as a better fit for constituency parsing.Source: §2 · p. 2
- The formal system represents the stack as increasing word boundaries, whose consecutive pairs define spans that can be labeled into a complete tree.Figure 1’s labeled-span set t contains entries of the form iXj.Source: §2 · p. 2, Figure 1 · p. 2
- The running example handles ternary branching by delaying labeling and creates a unary production with one label-S-VP action.The static oracle uses a short-stack heuristic that combines whenever combine and shift are both possible.Source: §2 · p. 3, Figure 2 · p. 3
3 LSTM Span Features
The model represents arbitrary sentence spans with bidirectional LSTM output differences, reusing one sentence encoding while consulting only a few span features for each action type.
LSTM Span Features
- Each span is represented by concatenated forward and backward LSTM differences, (f_j − f_i) and (b_i − b_j), at its word boundaries.This extends LSTM-Minus features to bidirectional recurrent outputs.Source: §3 · p. 3, Figure 3 · p. 4
- Difference features perform nearly the same as concatenated endpoint vectors in initial experiments but are almost twice as fast.The comparison concerns span representation choices rather than parsing accuracy across datasets.Source: §3 · pp. 3–4
- The sentence is processed once, allowing recurrent outputs to generate span features throughout the parse while modeling spans in sentence context.The implementation uses a two-layer bidirectional LSTM.Source: §3 · p. 4
- The parser uses four span features for structural actions and three for label actions, partitioning the sentence exactly.Structural decisions inspect the top two spans; label decisions inspect the top span, with the remaining prefix and suffix included.Source: §3 · p. 4
- The model uses learned word embeddings and separate one-hidden-layer ReLU perceptrons for structural and label actions.Embeddings are randomly initialized rather than pretrained, and training uses per-action negative log softmax loss.Source: §3 · p. 4
4 Dynamic Oracle
The paper defines reachable gold brackets for arbitrary configurations and uses them to construct a provably optimal dynamic oracle for constituency parsing. The oracle preserves exactly the actions that retain maximum achievable F1 and can be computed in amortized O(1) time.
4.4 Efficiency
- The oracle is computed in amortized O(1) time by updating next(c) only when structural crossing or mislabeled actions invalidate the current next bracket.Updates trace parent links until finding the smallest gold bracket that encompasses the current span.Source: §4 · p. 5, §4.4 · p. 7
- The dynamic oracle selects exactly the actions that preserve the maximum achievable F1 from any parser configuration.It is formally defined as the set of actions whose resulting configurations retain the configuration’s optimal F1.Source: §4.1 · p. 5, §4.3 · p. 7
4.1 Preliminaries and Notations
- Reachable brackets are gold brackets that can still be added without crossing stack spans or duplicating brackets already recognized.They combine left-reachable brackets that encompass the current span with right-reachable brackets on the queue; reach(c) is disjoint from the current tree.Source: §4.1 · p. 5
4.2 Structural and Label Oracles
- The next reachable bracket determines the structural oracle’s permitted actions: shift, combine, or both depending on how it encompasses the current stack span.Following the policy preserves the reachable set, whereas any excluded structural action strictly reduces it.Source: §4.2 · p. 6
- Label actions simply assign the gold label when the top stack span is a gold span, and otherwise take no-label.The structural and label policies together preserve t∗(c) exactly when followed.Source: §4.2 · p. 6, §4.3 · p. 7
- The optimal tree t∗(c) contains the current tree plus every reachable gold bracket and no other brackets.This tree is attainable and achieves the best possible F1 because it maximizes recall without adding incorrect brackets.Source: §4.3 · pp. 6–7
5 Related Work
Prior work applies neural, recursive, sequence-to-sequence, and Stack-LSTM methods to constituency parsing, while other systems combine neural and sparse features or use beam search. Dynamic-oracle research includes bottom-up constituency formulations and more expensive dependency-parsing oracles, alongside concurrent constituency work.
Neural constituency parsing
- Earlier constituency parsers used recursive networks, sequence-to-sequence generation, recursive shift-reduce models with beam search, Stack-LSTM adaptations, and CKY systems with neural and sparse features.The authors also contrast their approach with a prior greedy recurrent transition system that did not achieve state-of-the-art results.Source: §5 · p. 7
Dynamic oracles
- Huang (2008) first defined and solved constituency-parsing oracles as trees most similar to the gold tree among possible trees.The paper places its dynamic oracle in this broader oracle tradition.Source: §5 · p. 7
- Dynamic oracles for shift-reduce dependency parsing had worst-case O(n^3) time, whereas concurrent work proposed a dynamic oracle for another incremental constituency parser.The cited concurrent work is identified as Coavoux and Crabbé (2016).Source: §5 · p. 7
6 Experiments
Experiments show that dynamic-oracle training makes the greedy parser highly competitive on English and French constituency parsing, while stochastic exploration improves validation performance at a precision–recall trade-off.
6.1 Oracle Training
- Stochastic action sampling during training produces higher F1 scores than straightforward training with exploration, but sacrifices recall in favor of precision.Source: §6.1 · p. 8
6.1 English Experiments
- The reported experiments use standard Penn Treebank splits, jackknifed Stanford POS tags, ten training epochs, minibatches of ten sentences, dropout, and ADADELTA.Source: §6 · pp. 7–8, §6.2 · p. 8
6 Experiments
- The greedy parser achieves the best F1 score among closed-set single-model parsers on the Penn Treebank when trained with dynamic-oracle exploration.Source: §6.2 · p. 8
6.3 French Treebank
- The French experiments add morphological features and use predicted morphological features, part-of-speech tags, and lemmas supplied by the SPMRL 2014 dataset.Source: §6.3 · p. 8
- The French results could improve with an integrated or more accurate predictor for the supplied morphological features, tags, and lemmas.Source: §6.3 · p. 9
- On the French Treebank, the parser achieves state-of-the-art results even against a system using external data and reranking.Source: §6.3 · p. 9, Table 5 · p. 9
7 Conclusion and Future Work
The paper concludes that its span-based factored parser and fast optimal dynamic oracle deliver state-of-the-art greedy Penn Treebank accuracy. Future work centers on beam search and dynamic programming, enabled by the system’s fixed action structure and simple features.