Source-linked AI summary
Globally Normalized Transition-Based Neural Networks
Daniel Andor, Chris Alberti, David Weiss, Aliaksei Severyn, Alessandro Presta, Kuzman Ganchev, Slav Petrov, Michael Collins
TL;DR
The paper addresses whether feed-forward transition-based networks can match recurrent models and overcome weaknesses of local normalization. It introduces global normalization with beam search and a CRF objective, then demonstrates state-of-the-art performance across three tasks, supported by a proof concerning label bias. The authors also identify limits of local normalization with finite lookahead and the costs of increasing context.
Problem
The paper examines whether recurrence is necessary for strong NLP performance and whether local normalization's label bias limits a model's ability to revise earlier decisions.
Method
The model is a feed-forward transition-based neural network using beam search and global CRF normalization, with approximate partition functions and early updates.
Results
State-of-the-art performance is achieved on part-of-speech tagging, dependency parsing, and sentence compression, matching or outperforming LSTMs; Wall Street Journal parsing reaches 94.61% unlabeled attachment score.
Takeaways & Limitations
Global normalization makes feed-forward networks strictly more expressive than locally normalized models and helps overcome the label bias problem.
Takeaways & Limitations
Finite lookahead cannot in general eliminate local normalization's limitation, while broader context requires more powerful learning algorithms and potentially more training data.
Abstract
from arXiv · showhide
We introduce a globally normalized transition-based neural network model that achieves state-of-the-art part-of-speech tagging, dependency parsing and sentence compression results. Our model is a simple feed-forward neural network that operates on a task-specific transition system, yet achieves comparable or better accuracies than recurrent models. We discuss the importance of global as opposed to local normalization: a key insight is that the label bias problem implies that globally normalized models can be strictly more expressive than locally normalized models.
1 Introduction
The paper presents a globally normalized, feed-forward transition-based neural network that matches or exceeds recurrent models across several NLP tasks. It reports state-of-the-art results, including a 94.61% unlabeled attachment score for Wall Street Journal dependency parsing, while emphasizing speed and global training.
- 1 Introduction: Globally normalized feed-forward networks achieve comparable or better accuracies than LSTMs without recurrence.The model uses a transition system and feature embeddings, with beam search and a CRF objective for global normalization.
- 1 Introduction: State-of-the-art accuracy is reported on part-of-speech tagging, dependency parsing, and sentence compression, while the model is significantly faster than LSTMs.The paper evaluates the same modeling approach across all three tasks.
- 1 Introduction: Global backpropagation training of all model parameters outperforms previous structured training approaches for neural transition-based parsing.The comparison identifies fixed neural parameters during global training as a distinction from the earlier approaches.
- 1 Introduction: The method also outperforms Zhou et al. (2015) despite using a smaller beam.A sentence-compression example illustrates a case where the local model completely fails.
- 1 Introduction: The authors provide an open-source implementation, SyntaxNet, integrated into TensorFlow, alongside a pretrained English dependency parser.The parser, Parsey McParseface, was tuned for a balance of speed, simplicity, and accuracy.
2 Model
The model is an incremental transition-based parser whose differentiable decision scores support local or global normalization. Global training uses beam search and early updates to approximate otherwise intractable normalization.
- The model uses an incremental transition-based parser, adapting only the transition system and input features across tasks.
- A complete structure is a sequence of valid decision/state pairs beginning at a special start state and following the transition function.
- Each state is assumed to encode the entire decision history, allowing states and decision prefixes to be used interchangeably.
- The feed-forward neural network scores decisions by combining a state representation with decision-specific final-layer parameters.
- Local normalization assigns probabilities using a context-specific partition function, whereas global normalization scores complete valid decision sequences with one global partition function.
- Because the global partition function can be intractable, training uses beam search, early updates, and gradients back-propagated through all neural-network scoring parameters.
3 The Label Bias Problem
The section shows that global normalization is strictly more expressive than local normalization under the same prefix-restricted scoring, because local models cannot revise early decisions when later evidence resolves ambiguity.
- Expressiveness theorem: Theorem 3.1 states that the locally normalized distributions form a strict subset of the globally normalized distributions: PL ⊊ PG.The result is established for conditional sequence models whose decision scores access only the input prefix x1:i.
- Label bias example: At input symbol b, the ambiguity between tags B and D is resolved only after observing the next symbol, c or e.The constructed examples use the sequences a b c and a b e to expose this delayed resolution.
- Label bias example: A locally normalized model must satisfy pL(A B C|a b c) + pL(A D E|a b e) ≤1 because both alternatives share the same local decision point.The shared prefix forces the probabilities of choosing B and D after A, a b to sum to at most one.
- Expressiveness theorem: For sufficiently large α, the globally normalized model assigns probabilities whose corresponding sum exceeds 1, making any matching local model impossible.This constructs a distribution in PG that is not in PL and proves strict expressiveness.
- Limits of lookahead: Lookahead can repair the specific example, but every finite lookahead k has analogous failures created by repeating the ambiguous input k + 1 times.Capturing every conditional distribution with local normalization requires scores that inspect the entire input sequence.
- Limits of lookahead: Using more context can require more powerful learning algorithms and potentially more training data, although global normalization can be combined with richer scoring functions.The paper’s experiments use both global normalization and scoring functions with broader context.
4 Experiments
The experiments apply the transition-based model across POS tagging, dependency parsing, and sentence compression, using task-specific data and transition systems. Global normalization consistently delivers strong results, including state-of-the-art parsing and compression performance, while matching recurrent models on compression with substantially greater speed.
- Experimental scope: The approach is evaluated on POS tagging, syntactic dependency parsing, and extractive sentence compression.
- Experimental setup: The experiments use task-specific transition systems and features, with pretraining and global-objective training tuned separately for each task.
- Part of Speech Tagging: Global normalization reduces relative error by 7% for POS tagging when combined with beam search, whereas beam search does not help the local model.
- Dependency Parsing: The parser obtains the best ever published results on almost all datasets, and reaches 94.08% UAS and 92.15% LAS using only WSJ training data with beam 32.
- Sentence Compression: The globally normalized compression model significantly outperforms the local model and performs on par with the LSTM on automatic and human evaluations.
- Sentence Compression: The global compression model is roughly 100× faster than the compared LSTM, while all models retain approximately 42% of tokens on average.
5 Discussion
The discussion compares globally normalized transition-based models with prior approaches and illustrates how global normalization addresses label bias in practice. Results across parsing and compression show benefits from global training and broader model expressivity.
- 5.2 Related Transition-Based Parsing Work: Full backpropagation with the CRF objective reaches 93.20% accuracy and converges more than 4× faster than the hinge-loss alternative in the reported experiment.When backpropagation is limited to the top layer, the CRF and hinge-loss accuracies are 93.20% and 93.28%, respectively; with full backpropagation, CRF accuracy is 0.2% higher.
- 5.2 Related Transition-Based Parsing Work: The approach differs from recurrent or specialized-training alternatives by using neither recurrence nor specialized training, while also evaluating two additional tasks beyond dependency parsing.Zhou et al. (2015) used a larger beam but achieved significantly lower performance and evaluated only dependency parsing.
- 5.3 Label Bias in Practice: Global normalization avoids a sentence-compression failure in which local beam search sometimes selects empty compressions with higher local probability than the greedy prediction.The global model assigns the empty compression almost zero probability, whereas the local model can represent it incorrectly.
- 5.3 Label Bias in Practice: With no lookahead, the globally normalized parser reaches 93.60% UAS, compared with 81.35% for locally normalized beam search and 76.96% for greedy inference.The globally normalized model approaches the performance of a full-lookahead model under the restricted-information setting.
6 Conclusions
The paper concludes that a simple globally normalized transition-based feed-forward network achieves state-of-the-art results across three tasks without recurrence. A proof and empirical results support global normalization as a way to overcome label bias.
- 6 Conclusions: The model achieves state-of-the-art results on part-of-speech tagging, dependency parsing, and sentence compression.It combines transition-based algorithms with neural-network modeling.
- 6 Conclusions: Feed-forward networks without recurrence can outperform recurrent models such as LSTMs when trained with global normalization.The conclusion attributes the result to global normalization rather than recurrence.
- 6 Conclusions: A proof supports the claim that global normalization helps overcome the label bias problem affecting locally normalized models.The theoretical result complements the empirical performance findings.