Source-linked AI summary
Transition-Based Dependency Parsing with Stack Long Short-Term Memory
Chris Dyer, Miguel Ballesteros, Wang Ling, Austin Matthews, Noah A. Smith
TL;DR
Transition-based dependency parsers need representations of unbounded parser states, including the buffer, action history, and partially built stack. The paper introduces stack LSTMs with push and pop operations, uses them to encode these state components, and reports state-of-the-art parsing performance.
Problem
Transition-based dependency parsing must model action choices across unbounded parser states while previous representations used only narrow views of the buffer, stack, or action history.
Method
The model uses stack LSTMs to represent the input, partial-tree stack, and action history, with compositional neural representations for tree fragments and backpropagation training.
Results
The parser achieves state-of-the-art dependency-parsing results and substantially outperforms the baseline neural parser, with one Chinese −POS exception against a gold-POS baseline.
Takeaways & Limitations
Stack memory offers a mechanism for learning representations of complete parser states while retaining linear-time incremental parsing and training.
Takeaways & Limitations
Preliminary experiments found ReLU only slightly better than other nonlinearities, limiting the reported architectural conclusion about this choice.
Abstract
from arXiv · showhide
We propose a technique for learning representations of parser states in transition-based dependency parsers. Our primary innovation is a new control structure for sequence-to-sequence neural networks---the stack LSTM. Like the conventional stack data structures used in transition-based parsing, elements can be pushed to or popped from the top of the stack in constant time, but, in addition, an LSTM maintains a continuous space embedding of the stack contents. This lets us formulate an efficient parsing model that captures three facets of a parser's state: (i) unbounded look-ahead into the buffer of incoming words, (ii) the complete history of actions taken by the parser, and (iii) the complete contents of the stack of partially built tree fragments, including their internal structures. Standard backpropagation techniques are used for training and yield state-of-the-art parsing performance.
1 Introduction
Transition-based dependency parsing is computationally efficient but must choose actions across an unbounded number of parser states. The paper addresses this by learning incremental representations sensitive to the complete buffer, action history, and stack contents.
- Transition-based parsing reads words sequentially from a buffer and incrementally combines them into syntactic structures.Building projective parse trees requires a number of operations linear in sentence length.
- The central challenge is modeling which action to take in each of the unboundedly many states encountered during parsing.
- Prior work addressed this challenge through alternative transition sets, feature engineering, and neural-network models.
- The proposed model represents the complete input buffer, action history, and stack of partially constructed syntactic structures rather than only a narrow local view.
- Stack LSTMs support pushing and popping while constructing parser-state representations incrementally, keeping parsing and training time linear in sentence length.
2 Stack LSTMs
Stack LSTMs augment recurrent networks with a stack pointer, enabling push and pop operations while maintaining a continuous summary of stack contents. The design preserves access to earlier stack states and can represent complete stack contents rather than only the top element.
- 2.1 Long Short-Term Memories: The underlying LSTM uses multiplicative gates to control input incorporation, forgetting, and output, and stacked layers can increase representational capacity.
- 2.2 Stack Long Short-Term Memories: Stack LSTMs augment conventional left-to-right LSTMs with a stack pointer that determines which previous cell supplies recurrent state.
- 2.2 Stack Long Short-Term Memories: A push appends a new entry with a back-pointer, while a pop moves the pointer to the previously extended element without overwriting stack contents.
- 2.2 Stack Long Short-Term Memories: The output at the pointer, h_TOP, provides a continuous-space summary of the current stack configuration.
- 2.2 Stack Long Short-Term Memories: Unlike an external-stack architecture that exposes only the top element, the stack LSTM provides an embedding of the complete stack contents.
3 Dependency Parser
The parser represents its complete configuration with stack LSTMs for the buffer, partial syntactic trees, and action history, then predicts valid transitions from this state. Token and subtree representations are composed neural representations that support parsing decisions and out-of-vocabulary words.
- Parser state representation: Three stack LSTMs encode the input buffer, partial syntactic trees, and history of parser actions.The action-history stack is only pushed to, while the other structures reflect the parser’s changing configuration.
- Parser operation: The parser initializes the buffer in reverse sentence order, then repeatedly predicts actions that update the buffer, tree stack, and action history.Processing ends when the buffer is empty, the tree stack contains the complete ROOT-headed tree, and the action history records the operations.
- Parser state representation: The parser state embedding combines the three stack encodings through a learned linear transformation and ReLU before predicting a valid action distribution.The valid-action set depends on the current stack and buffer contents; when the stack is empty while words remain, SHIFT is obligatory.
- Token embeddings and OOVs: Each token representation combines learned word, pretrained language-model, and POS-tag vectors before a linear map and ReLU transformation.The model uses structured skip n-gram embeddings because order-discarding approaches perform less well for syntax modeling.
- Token embeddings and OOVs: Singleton words are stochastically replaced with UNK during training to provide estimates for out-of-vocabulary words in parsing data.The token architecture also supports words absent from parser training data but present in the language-model data.
- Tree composition: Dependency subtrees are represented compositionally by combining head, dependent, and relation vectors in the order imposed by parser reductions.The composition function computes c = tanh(U[h; d; r] + e), with relation embeddings derived from the parser action that constructs the attachment.
4 Training Procedure
The parser is trained by differentiating a sentence-level conditional log-likelihood through a computation graph. Optimization uses stochastic gradient descent with gradient clipping and regularization, while model dimensions are selected using development data.
- Objective and optimization: Training maximizes the conditional log-likelihood of treebank parses given sentences using forward- and backpropagation through a sentence-specific computation graph.A single-threaded CPU implementation required 8–12 hours to converge on a held-out development set.
- Objective and optimization: Stochastic gradient descent starts with learning rate η0 = 0.1 and decays it as ηt = η0/(1 + ρt), with ρ = 0.1 and no momentum.The gradient's ℓ2 norm is clipped to 5, and an ℓ2 penalty of 1 × 10^-6 is applied.
- Model dimensions: The full model uses 100-dimensional LSTM hidden states with two layers per stack, alongside task-specific dimensions for actions, outputs, words, and POS tags.English and Chinese pretrained word embeddings use 100 and 80 dimensions, respectively; learned word embeddings use 32 dimensions and POS embeddings use 12.
- Model dimensions: The reported architecture balances computational expense and solution quality, with dimensions chosen from reasonable values and checked on development data.The authors note that future work could optimize these parameters more carefully.
5 Experiments
The experiments evaluate the stack LSTM parser on English and Chinese dependency parsing across full, ablated, and recurrent-network configurations. The model outperforms the Chen and Manning baseline in both languages and reveals effects of POS tags, pretrained embeddings, composition, and beam size.
- Data and setup: The evaluation uses English Stanford Dependencies and Chinese CTB5, matching Chen and Manning’s neural arc-standard setup.English uses predicted POS tags, while Chinese uses gold POS tags.
- Configurations: Five configurations test the full stack LSTM model, POS tags, pretrained embeddings, composed representations, and replacing the LSTM with a classical RNN.The reported variants are S-LSTM, −POS, −pretraining, −composition, and S-RNN, alongside the Chen and Manning baseline.
- Results: The stack LSTM model is better than Chen and Manning’s model on both development and test sets under comparable evaluation.Punctuation symbols are excluded from evaluation.
- Results: The parser substantially outperforms the baseline across full and ablated conditions, except for −POS on Chinese, where it underperforms the gold-POS baseline.The Chinese −POS condition still achieves reasonable parsing performance in this limited case.
- Analysis: Composed dependency-fragment representations outperform head-word-only representations, while LSTMs outperform classical RNNs that nevertheless learn good representations.Predicted English POS tags add very little value.
- Decoding: Beam search yields at most 0.3% absolute improvement with small beams, so all reported results use greedy decoding.This matches the decoding strategy reported by Chen and Manning.
6 Related Work
The related work connects stack LSTMs to neural stack memories, neural transition-based parsers, LSTM parsing, and methods for incorporating larger contexts. The paper’s distinction is conditioning on a global parser state rather than manually selected state properties.
- Neural stack memories: Earlier neural stack memories augmented recurrent networks, but the cited NNPDA exposed only the stack top while this work summarizes the complete stack.The comparison highlights the different visibility of stack contents to the recurrent network.
- Neural dependency parsing: Neural transition-based parsers predict shift-reduce actions, but prior systems used manually crafted conditioning structures sensitive to selected state properties.Stenetorp’s work also used recursively composed tree-fragment representations.
- LSTM parsing: The cited phrase-structure LSTM parser reads the entire sentence before generating bracketing structures, whereas the present work addresses dependency parsing with stack operations.The paper characterizes adapting that approach to dependency parsing as nontrivial.
- Larger contexts: The work is situated in a progression toward larger parsing contexts, including nonlocal features, higher-order factors, and approximate decoding methods.The cited examples include cube pruning, LP-relaxation decoding, and randomized hill-climbing.
7 Conclusion
The paper presents stack LSTMs with push and pop operations and applies them to a state-of-the-art transition-based dependency parser. It also identifies extensions toward unsupervised parsing and general information-processing systems, while noting the computational difficulty of latent stack operations.
- Contribution: Stack LSTMs are recurrent sequence models with push and pop operations used to implement a state-of-the-art transition-based dependency parser.The conclusion frames stack memory as a possible mechanism for broader information-processing problems.
- Scope and extensions: The parser learns from observable stack manipulations supervised by a treebank, and its final parser-state embeddings are not used for further prediction.The conclusion contrasts this setup with a possible reversal in which the device learns to construct context-free programs from observed outputs.
- Limitations and future work: Unsupervised parsing would require learning latent stack operations, creating computational challenges such as marginalizing over all possible operation sequences.Sampling and reinforcement-learning techniques are identified as promising approaches.