Source-linked AI summary
Structured Training for Neural Network Transition-Based Parsing
David Weiss, Chris Alberti, Michael Collins, Slav Petrov
TL;DR
Dependency parsing needs accurate transition decisions without relying on extensive manual feature engineering. The paper combines a neural network representation with structured perceptron training and beam-search decoding, then augments training with automatically parsed data; on the Penn Treebank, it reaches 94.26% UAS and 92.41% LAS. The study also analyzes which architectural and modeling choices contribute most to accuracy.
Problem
Transition-based parsers can require significant manual feature engineering, motivating neural representations combined with stronger structured search and training.
Method
The paper pre-trains a feedforward neural network representation, trains a final layer with the structured perceptron and beam search, and augments training with tri-trained automatically parsed sentences.
Results
94.26% UAS / 92.41% LAS is achieved on the Penn Treebank after incorporating unlabeled data.
Takeaways & Limitations
The paper presents a transition-based neural parser that combines learned representations, structured prediction, and unlabeled-data training to improve dependency parsing accuracy.
Takeaways & Limitations
The representation is pre-trained rather than learned jointly during perceptron training because joint backpropagation was left for future investigation.
Abstract
from arXiv · showhide
We present structured perceptron training for neural network transition-based dependency parsing. We learn the neural network representation using a gold corpus augmented by a large number of automatically parsed sentences. Given this fixed network representation, we learn a final layer using the structured perceptron with beam-search decoding. On the Penn Treebank, our parser reaches 94.26% unlabeled and 92.41% labeled attachment accuracy, which to our knowledge is the best accuracy on Stanford Dependencies to date. We also provide in-depth ablative analysis to determine which aspects of our model provide the largest gains in accuracy.
1 Introduction
The paper combines neural representations with structured training and beam-search inference for transition-based dependency parsing, while using automatically parsed data to improve performance. On the Penn Treebank, the parser reaches 94.26% UAS and 92.41% LAS after incorporating unlabeled data.
- Neural representations: The neural network eliminates hand-engineered features by learning combinations of atomic inputs and distributed lexical, POS-tag, and arc-label representations.Its feedforward design avoids recurrent structure to keep inference fast and permit simple backpropagation.
- Results: 94.26% UAS / 92.41% LAS is achieved on the Penn Treebank after incorporating unlabeled data.The supervised parser reaches 93.99% UAS / 92.05% LAS before unlabeled-data augmentation.
- Structured training: Structured perceptron training with beam search uses neural network representations rather than action probabilities directly, improving Penn Treebank parsing accuracy by 0.8%.The representation is learned before the final structured perceptron layer is trained with beam search and early updates.
- Unlabeled data: 10 million automatically parsed tokens improve parser accuracy by almost ∼1.0% on web domain data.The method selects sentences whose parses agree under two different parsers, an approach called tri-training.
- Analysis: Ablative analysis examines which architectural and modeling choices produce the largest accuracy gains and guides future refinements.The paper presents this exploration as one of its goals.
2 Neural Network Model
The parser uses a feedforward neural network that embeds configuration features, processes them through ReLU hidden layers, and supplies the resulting representation to structured prediction. Its design extends Chen and Manning’s model with smaller tag and label embeddings, ReLU units, and two hidden layers.
- Input layer: The model extracts words, POS tags, and arc labels from an arc-standard parse configuration and represents each group as a sparse feature matrix.It uses 20 word features, 20 tag features, and 12 label features.
- Embedding layer: The embedding layer transforms sparse discrete features into a dense continuous representation by applying learned group-specific embedding matrices and concatenating the outputs.Embedding dimensions can differ across groups, with smaller dimensions possible for POS tags and arc labels.
- Hidden layers: The hidden layers use fully connected ReLU units, with each layer’s weights mapping the preceding representation to the next layer.The first hidden-layer matrix is M1 × E, while subsequent matrices are Mi × Mi−1.
- Model differences: Compared with Chen and Manning (2014), the model uses smaller POS-tag and label embeddings, ReLU units, and a deeper two-hidden-layer architecture.Combined with SGD pre-training, these changes produced an almost 1% accuracy gain over that model.
- Structured prediction: The structured perceptron learns the final layer from the neural network representation in a structured prediction setting.This training procedure is the paper’s main algorithmic contribution.
3 Semi-Supervised Structured Learning
The approach combines neural representations with structured perceptron training and beam-search inference, then augments gold data with high-quality automatic parses. Pretraining supplies the representation, while structured learning and semi-supervised data improve parsing accuracy.
- Structured learning: The network is pretrained on individual parsing actions, after which a structured perceptron learns a final output layer over its fixed hidden representations.The perceptron uses beam search and early updates rather than directly using the neural action probabilities for prediction.
- Structured learning: Structured perceptron training improves accuracy by approximately 0.6% absolute over the pretrained neural representation.The hidden representation is fixed while the additional final output layer is learned with structured perceptron training.
- Structured learning: Beam-search early updates compare the gold decision prefix with the highest-scoring incorrect beam member when the gold tree falls out of the beam.If the gold tree remains in the beam until sentence end, conventional perceptron updates are used.
- Structured learning: The feature representation concatenates outputs from both hidden layers with probabilities for all decisions possible in the current configuration.This representation achieved the best development accuracy among the variants tested.
- Semi-supervised learning: Tri-training supplements gold data with automatic parses, retaining only sentences receiving the same tree from two parsers.The method is motivated by the higher expected correctness of parser-agreement cases and is reported to improve accuracy by as much as 1% absolute.
- Semi-supervised learning: The two baseline parsers agree on 36% of tune-set sentences, whose accuracy is 97.26% UAS.These agreement-selected sentences approach the reported inter-annotator agreement rate.
4 Experiments
Experiments evaluate the parser on WSJ and a multi-domain Treebank Union, including semi-supervised tri-training and comparisons with prior systems. The parser performs strongly across these evaluations, while beam size and cross-parser comparability affect interpretation.
- WSJ setup: Experiments use WSJ sections 2–21 for training, section 22 for development, section 24 for tuning, and section 23 for final testing.
- Treebank Union setup: The Treebank Union combines WSJ, OntoNotes 5, the English Web Treebank, and the Question Treebank, training on their union and testing each domain separately.
- Semi-supervised setup: 107 agreeing parses from BerkeleyParser and ZPar were selected as additional training data in the semi-supervised experiments.
- Results: 97.57% accuracy was reached on the WSJ after incorporating unlabeled data.
- Results: On WSJ and Web tasks, the parser outperformed all compared dependency parsers by a substantial margin, while QTB was more sensitive to the smaller training beam.
- Results: Tri-training produced 0.4–1.0% absolute LAS gains for the most accurate model on the diverse Treebank Union setup, whereas the reimplemented baseline did not improve significantly on test data.
5 Discussion
The ablations examine architecture, embeddings, structured training, representations, and semi-supervised data. They find benefits from pre-training, larger hidden layers, structured perceptron training, all-layer representations, and tri-training, while embedding-size gains diminish.
- Network initialization and depth: Pre-trained embeddings improve generalization across data, whereas adding a second hidden layer helps tune performance but not dev performance without pre-training.Tune and dev UAS correlate strongly overall (ρ = 0.64, p < 10^-10) but not without pre-trained embeddings (ρ = 0.12, p > 0.3).
- Embedding dimensions: 92.33% UAS is achieved by a tri-trained compact model with 8× fewer parameters, comparable to the full model without tri-training.The result suggests additional training data can compensate for fewer parameters.
- Hidden-layer size: Increasing hidden units continues improving accuracy, although training becomes too slow beyond M = 2048.Improvements did not appear to saturate even after increasing hidden units by an order of magnitude.
- Structured perceptron: Structured perceptron training yields much larger gains than beam search with direct softmax probabilities, especially for the tri-trained neural network.The comparison evaluates softmax scoring versus hidden-layer representations in the structured perceptron across beam sizes.
- Structured perceptron: Using all intermediate hidden representations is the most effective feature representation for the structured perceptron.The intermediate layers collectively contain information that reduces model bias, whereas filtering through the softmax layer does not.
- Semi-supervised training: Tri-training benefits the neural network more than up-training, with the greedy neural network surpassing the BerkeleyParser after tri-training.Up-training improves the baseline more than tri-training, but the neural network shows the opposite pattern.
- Error analysis: Structured perceptron training improves error rates by more than 1% for ROOT, ccomp, cc, conj, and nsubj.The learned perceptron weights reweight softmax probabilities according to common confusions, but this does not work using probabilities alone as features.
6 Conclusion
The paper presents a state-of-the-art transition-based neural dependency parser trained with structured perceptron and ASGD. Combining the approach with unlabeled data and tri-training further advances semi-supervised parsing, while scaling representations remains a promising direction.
- Conclusion: The parser establishes a new state of the art using structured perceptron and ASGD for transition-based neural dependency parsing.The authors identify larger representations, other languages, end-to-end structured learning, and larger datasets as future directions.