Source-linked AI summary
Neural CRF Parsing
Greg Durrett, Dan Klein
TL;DR
Neural parsing often relies on sequential decisions or reranking, while recurrent structured models may not admit efficient dynamic programming. This paper scores anchored rules with feedforward neural potentials in a CRF that retains exact CKY inference, reporting 91.1 F1 on Penn Treebank section 23 and best single-parser results on nine other languages.
Problem
Neural parsing approaches often use sequential decisions or reranking, while recurrent structured models may not admit efficient dynamic programming.
Source: §1 · p. 1Method
A CRF constituency parser scores anchored rule productions with feedforward neural potentials while preserving factorization for exact CKY inference.
Source: §1 · p. 1, §2.1 · p. 3Results
91.1 F1 on section 23 of the Penn Treebank; the model also reports best single-parser results on nine other languages.
Source: §1 · p. 2Takeaways & Limitations
The modular neural component integrates into a preexisting learning and inference framework based on dynamic programming of a discrete parse chart.
Source: §8 · p. 9The experiments use no horizontal Markovization; English experiments use no vertical Markovization, and parent annotation is the only grammar refinement considered.
Source: §2.4 · p. 4
Abstract
from arXiv · showhide
This paper describes a parsing model that combines the exact dynamic programming of CRF parsing with the rich nonlinear featurization of neural net approaches. Our model is structurally a CRF that factors over anchored rule productions, but instead of linear potential functions based on sparse features, we use nonlinear potentials computed via a feedforward neural network. Because potentials are still local to anchored rules, structured inference (CKY) is unchanged from the sparse case. Computing gradients during learning involves backpropagating an error signal formed from standard CRF sufficient statistics (expected rule counts). Using only dense features, our neural CRF already exceeds a strong baseline CRF model (Hall et al., 2014). In combination with sparse features, our system achieves 91.1 F1 on section 23 of the Penn Treebank, and more generally outperforms the best prior single parser results on a range of languages.
1 Introduction
The paper combines feedforward neural scoring of anchored rule productions with CRF factorization, retaining exact CKY inference. It reports 91.1 F1 on Penn Treebank section 23 and best single-parser results on nine other languages.
1 Introduction
- Neural models learn nonlinear feature interactions, while recurrent architectures for structured outputs may not admit efficient dynamic programming; feedforward local scoring permits it.Source: §1 · p. 1
- The parser scores anchored rule productions with nonlinear feedforward-network features computed from word representations at span boundaries and split points.The resulting scores act as nonlinear potentials in the CRF.Source: §1 · p. 1
- Unlike prior parsers using sequential decisions or reranking, the framework permits exact CKY inference because its structured interactions are discrete rather than continuous hidden states.Source: §1 · p. 1
- Training uses conventional CRF gradient descent, backpropagating differences in expected anchored-rule counts through the network.Source: §1 · p. 2
- 91.1 F1 on section 23 of the Penn Treebank outperforms Socher et al. (2013) and Berkeley Parser, matches Carreras et al. (2008), and nine-language results are best single-parser results.The model also outperforms Hall et al. (2014) on nine other languages.Source: §1 · p. 2
- Dense learned features alone outperform the CRF parser of Hall et al. (2014).Source: §1 · p. 2
2 Model
The parser assigns scores to anchored rules using sparse features, nonlinear neural features, or both, while retaining CRF tree distributions and CKY inference. Its lexical inputs and grammar settings are chosen to balance feature richness, parameterization, and parsing efficiency.
2.1 Anchored Rules
- Trees are collections of anchored rules (rule identity plus span and split point), scored by potentials in a CRF distribution over trees conditioned on the sentence.Unary rules are omitted for exposition but can be supported by using a null split point.Source: §2.1 · pp. 2–3
2.2 Scoring Anchored Rules
- Neural scoring embeds word indicators from the anchoring, transforms them through a one-layer network into h, then combines h with rule indicators; sparse and neural scores can be jointly learned.Sparse scoring combines surface-feature vectors and rule indicators through W; the two scoring models can be combined without changing inference.Source: Figure 3 · p. 3, §2.2 · pp. 3–4
2.3 Features
- Neural features use 12 surrounding words around span boundaries and split points, represented by pretrained word vectors that remain fixed during training.The sparse model uses Hall et al. (2014) features; unlike the neural model, it did not benefit from the larger lexical neighborhood.Source: §2.3 · p. 4, §2.4 · p. 4
2.4 Grammar Refinements
- The English neural CRF uses no vertical Markovization (V = 0) or horizontal Markovization; parent annotation (V = 1) is useful on other languages.The authors use lightly annotated grammars to limit parameter growth and overfitting, and report that smaller state spaces make dynamic programming faster.Source: §2.4 · p. 4
3 Learning
Learning maximizes conditional log likelihood over training trees, with gradients for neural parameters obtained through expected-count signals and backpropagation. The objective is nonconvex and not everywhere differentiable, so optimization follows subgradients.
3 Learning
- The model maximizes conditional log likelihood over the training trees, using subgradients because the ReLU objective is not everywhere differentiable and is nonconvex.Adadelta worked better out of the box than Adagrad, although Adagrad performed equally well with tuned regularization and step size.Source: §3 · pp. 4–5
- The gradient for W has the standard log-linear form, while gradients for H and other neural parameters are computed by backpropagating through hidden activations.The gradient signal is expressed in terms of expected feature counts.Source: §3 · p. 4
- Training uses minibatches of 200 trees and stops after 10 passes through a treebank or 1,000 minibatches, whichever comes first.The system was not particularly sensitive to minibatch size; W is initialized to zero and H with small-variance Gaussian entries.Source: §3 · p. 5
4 Inference
Inference uses standard CKY over anchored-rule scores, with coarse pruning and sparse computation to reduce work. Training takes 24 hours for the combined model on the Penn Treebank.
4 Inference
- CKY computes expected anchored-rule counts or the Viterbi tree, and coarse pruning removes constituents with max marginal probability below e^-9.Pruning reduces the spans and split points that need consideration.Source: §4 · p. 5
- For each remaining span and split point, cached word contributions reduce hidden-layer computation to vector addition followed by the nonlinearity.The network may otherwise require activations for thousands of span/split-point combinations per sentence.Source: §4 · p. 5
- Because only a few rules apply to each span and split point, the model selectively computes the terms needed for the final bilinear product.This exploits the sparsity of the rule-indicator vector despite the large number of possible rules.Source: §4 · p. 5
- The combined sparse and neural model trains on the Penn Treebank in 24 hours, versus around 15 hours for the parent-annotated sparse model.Both timings are on the same machine; the combined model uses a parallelized CPU implementation.Source: §4 · p. 5
5 System Ablations
On Penn Treebank development data, neural and sparse features show complementary strengths, while word-representation and architecture choices also affect parsing results.
5 System Ablations
- The neural CRF alone outperforms the sparse CRF even with a more heavily annotated grammar, while the combined model substantially beats either alone.Table 1 reports the section 22 development results and compares sparse/neural features, grammar Markovization, and word representations.Source: §5 · p. 5, Table 1 · p. 6
- Wikipedia-trained embeddings do not outperform Bansal et al. (2014) vectors, while Penn Treebank-only vectors still improve the sparse-feature model when stacked on top.The Penn Treebank-only vectors are somewhat lower-performing on their own.Source: §5 · p. 6
- On sentences of length ≤40 from section 22, rectified linear units outperform tanh and cubic units, and one hidden layer performs best.The table also reports worse performance when the output feature vector is embedded.Source: Table 2 · p. 6
- Brown-cluster features provide no benefit to the baseline CRF, while the table reports gains from combining sparse and neural features.The authors suggest the embeddings may capture different regularities or be easier to use than sparse cluster features.Source: §5 · p. 6, Table 1 · p. 6
6 Design Choices
The design comparisons favor rectified linear units and one hidden layer over the tested alternatives. Output-feature embeddings performed poorly, and cubic-unit performance declined late in learning.
6 Design Choices
- Rectified linear units perform best, followed by tanh units and then cubic units.Tanh saturation can halt derivative backpropagation when inputs are far from zero.Source: §6 · p. 7
- A one-hidden-layer network outperforms both linear features and the tested two-layer network.The purely linear architecture performs surprisingly well but remains less effective than the one-layer architecture.Source: §6 · p. 7
- Multiplying the sparse output feature vector by K gives a low-rank approximation of the output-layer weights, so similar rule embeddings can make rules behave similarly.This avoids learning a separate output-weight row for every grammar rule.Source: §6 · p. 7
- Cubic-unit performance declined substantially late in learning, peaking at around 90.52; dropout did not help overall in these experiments.The authors suggest dropout may help alleviate this type of overfitting, though it was not beneficial overall in their experiments.Source: §6 · p. 7
- Embedding the output feature vector performs worse; learning that representation was unstable and required careful initialization.The authors hypothesize that blurring output-class distinctions may hurt parsing.Source: §6 · p. 7
7 Test Results
The test results cover the English Penn Treebank and nine SPMRL languages. The parser matches or surpasses strong single-parser comparisons on PTB section 23 and improves over the strongest single-parser results across the SPMRL languages.
7.1 Penn Treebank
- 91.1 F1 on PTB section 23 matches Shindo et al. (2012) and Carreras et al. (2008), while outperforming the Berkeley and CVG parsers.The comparison focuses on single parsers; the system also uses word vectors computed from unlabeled data, and the compared CVG and Vinyals systems use different training conditions.Source: §7.1 · pp. 7–8, Table 4 · p. 8
- The PTB comparison includes four parsers trained only on PTB without auxiliary data, while the neural CRF uses word vectors computed from unlabeled data.The authors also compare with parsers using different conditions, including a CVG reranker and a Vinyals parser trained on more parsed data.Source: §7.1 · p. 8
7.2 SPMRL
- Across nine SPMRL treebanks, the parser improves on Hall et al. (2014) and the top single parser, with robust improvements on all languages.The table reports F-scores for sentences of all lengths using the shared-task version of evalb.Source: Table 3 · p. 8, §7.2 · p. 9
8 Conclusion
The paper presents a CRF parser that scores anchored rule productions with dense features from a feedforward neural network. Its modular neural component integrates with dynamic-programming inference, and the combined neural and sparse model performs strongly on English and other languages.
8 Conclusion
- The parser scores anchored rule productions with dense input features computed by a feedforward neural network.The neural component is modularized for integration into an existing learning and inference framework based on dynamic programming over a discrete parse chart.Source: §8 · p. 9
- The combined neural and sparse model gives strong performance on English and other languages.Source: §8 · p. 9
- The system is publicly available at the Berkeley NLP website.Source: §8 · p. 9