Source-linked AI summary
Stack-Pointer Networks for Dependency Parsing
Xuezhe Ma, Zecong Hu, Jingzhou Liu, Nanyun Peng, Graham Neubig, Eduard Hovy
TL;DR
Dependency parsers must balance transition-based efficiency against limited local context and graph-based accuracy against slower decoding. STACKPTR combines pointer networks with an internal stack for top-down, depth-first tree construction while retaining whole-sentence information and linear parsing steps. Across 29 treebanks in 20 languages, it achieves state-of-the-art performance on 21 corpora.
Problem
Transition-based parsers are efficient but rely on local decisions that can propagate errors, while accurate graph-based parsers usually decode more slowly.
Method
STACKPTR combines pointer networks with an internal stack to construct dependency trees top-down and depth-first using whole-sentence and previously derived subtree information.
Results
STACKPTR achieves state-of-the-art performance on 21 of 29 treebanks spanning 20 languages and different dependency annotation schemas.
Takeaways & Limitations
The architecture removes the classical left-to-right restriction while maintaining linear parsing steps and O(n^2) decoding complexity.
Takeaways & Limitations
The experiments use the same hyper-parameters across models, treebanks, and languages because of time constraints.
Abstract
from arXiv · showhide
We introduce a novel architecture for dependency parsing: \emph{stack-pointer networks} (\textbf{\textsc{StackPtr}}). Combining pointer networks~\citep{vinyals2015pointer} with an internal stack, the proposed model first reads and encodes the whole sentence, then builds the dependency tree top-down (from root-to-leaf) in a depth-first fashion. The stack tracks the status of the depth-first search and the pointer networks select one child for the word at the top of the stack at each step. The \textsc{StackPtr} parser benefits from the information of the whole sentence and all previously derived subtree structures, and removes the left-to-right restriction in classical transition-based parsers. Yet, the number of steps for building any (including non-projective) parse tree is linear in the length of the sentence just as other transition-based parsers, yielding an efficient decoding algorithm with $O(n^2)$ time complexity. We evaluate our model on 29 treebanks spanning 20 languages and different dependency annotation schemas, and achieve state-of-the-art performance on 21 of them.
1 Introduction
Dependency parsing supports deep language understanding but faces a trade-off between transition-based efficiency and graph-based global accuracy. STACKPTR addresses this trade-off with a top-down neural architecture that retains global sentence information while achieving strong benchmark performance.
- Motivation: Dependency parsing predicts labeled dependencies between words and supports downstream NLP applications.It is described as a first step toward deep language understanding.
- Motivation: Transition-based parsers use linearly many operations but rely on local decisions that can propagate errors, especially for root and long dependencies.Their sequential construction commonly proceeds left-to-right.
- Motivation: Graph-based parsers optimize globally and achieve strong accuracy, but their decoding commonly requires O(n^3) time or higher.The cited complexity applies to first-order and higher-order graph-based models, respectively.
- Proposed approach: STACKPTR combines pointer networks with an internal stack to build dependency trees top-down and depth-first.The stack tracks head-word order while the pointer mechanism selects each child.
- Proposed approach: STACKPTR captures whole-sentence and previously derived subtree information while maintaining a linear number of parsing steps.This removes the left-to-right restriction associated with classical transition-based parsing.
- Evaluation: 21 treebanks achieved state-of-the-art performance across an evaluation spanning 29 treebanks and 20 languages.The experiments also compare the proposed method with a strong biaffine graph-based baseline.
2 Background
Dependency parsing represents syntactic relations as directed links between words, while pointer networks provide a mechanism for selecting input positions as outputs. The paper uses these foundations to describe sentence, tree, stack, and attention representations for STACKPTR.
- Dependency parsing and notation: Dependency trees represent syntactic relationships through labeled directed edges from heads to dependents.The notation treats a dependency tree as root-to-leaf paths beginning at a virtual root.
- Dependency parsing and notation: The input sentence is represented as x = {w_1, ..., w_n}, and the output tree may be non-projective.Each path is a sequence of words from the virtual root to a leaf.
- Dependency parsing and notation: A stack configuration σ is a sequence of words, while ch(w_i) denotes the list of children or modifiers of w_i.The notation σ|w represents pushing word w onto stack σ.
- Pointer Networks: Pointer Networks use attention as a pointer to select discrete input positions when the output sequence length varies with the input.The encoder produces word representations and the decoder uses attention scores over source words.
- Pointer Networks: Figure 1 combines the STACKPTR neural architecture with an example decoding procedure, including sibling and grandparent vectors in decoder inputs.The figure omits the encoder BiRNN for brevity.
3 Stack-Pointer Networks
STACKPTR combines a pointer network with an internal stack to construct dependency trees top-down and depth-first while preserving access to encoded sentence context.
- STACKPTR encodes the whole sentence before decoding, then selects each head’s children using attention over encoder representations.
- The stack records depth-first parsing status by pushing selected children and popping a head when it selects itself.
- At test time, available-word tracking ensures every input word is included exactly once in the dependency tree.
- Children are decoded in inside-out order, which supports sibling information and outperformed left-to-right ordering in the reported experiments.
- The decoder uses encoder hidden states from the stack top, providing contextual inputs rather than previous-word embeddings.
- Biaffine attention scores candidate children, with learned bilinear, linear, and bias parameters; MLPs transform encoder and decoder states beforehand.
3.4 Higher-order Information
The parser incorporates higher-order grandparent and sibling structures into decoder inputs while jointly training arc and dependency-label predictions.
- The model represents sibling structures as a head with two successive modifiers and grandparent structures as connected head-to-tail dependencies.
- At each decoding step, the input combines encoder states for the head, its grandparent, and its sibling.
- Element-wise summation incorporates these three states without increasing decoder-input dimensionality or adding model parameters.
- The parser models tree probability autoregressively over top-down paths and previously generated paths, rather than a left-to-right chain.
- Arc prediction optimizes conditional likelihood through cross-entropy, while a separate classifier jointly predicts dependency labels from head and child features.
3.7 Discussion
STACKPTR requires linear decoding steps and achieves quadratic decoding time, while following a whole-sentence, recursively structured parsing strategy.
- 2n−1 decoding steps build a sentence-length-n parse tree, making the number of steps linear in n.
- O(n^2) decoding follows because attention costs O(n) at each step, improving on graph-based parsers with O(n^3) or worse decoding.
- The parser’s top-down strategy mirrors annotation behavior that begins with the whole sentence, identifies predicates, and recursively processes governed subtrees.
- Experiments use pretrained word embeddings across languages, Adam optimization, gradient clipping, and dropout training.
4 Experiments
Experiments compare STACKPTR variants with BIAF across multiple treebanks, languages, metrics, and structural conditions. STACKPTR achieves strong parsing performance, while error patterns vary with sentence length, dependency length, root distance, and POS-tag quality.
- Experimental setup: STACKPTR is evaluated on PTB, CTB, German CoNLL, 14 CoNLL treebanks, and 12 Universal Dependency treebanks using UAS, LAS, UCM, LCM, and RA.Results are reported as means with standard deviations over 5 repetitions.
- Main results: The Full STACKPTR model with beam size 10 outperforms BIAF on Chinese UAS and LAS and achieves competitive English and German performance.It is strongest on English and Chinese, while +sib performs slightly better than Full on German.
- Comparison with previous work: STACKPTR significantly outperforms transition-based parsers on all three evaluated languages and achieves state-of-the-art UAS and LAS on Chinese, plus best UAS on English.On German, it is competitive with BIAF and significantly better than other models.
- Error analysis: STACKPTR performs better on shorter sentences and shorter dependencies, while BIAF retains an advantage on longer arcs with only a marginal gap.STACKPTR shows no obvious precision advantage for arcs farther from the root and does not over-predict root modifiers.
- CoNLL treebanks: On 14 CoNLL treebanks, STACKPTR achieves state-of-the-art UAS and LAS on eight languages and best UAS on Bulgarian and Dutch.Japanese is the only listed exception, where NeuroMST obtains the best scores.
- UD treebanks: On 12 UD treebanks, STACKPTR outperforms BIAF on both UAS and LAS in nine languages, with mixed or marginal differences on the remaining three.All 12 languages obtain UAS above 90%; Bulgarian has slightly better UAS but worse LAS, while BIAF is marginally better on Italian and Romanian.
5 Conclusion
STACKPTR combines pointer networks with an internal stack to support top-down, depth-first dependency parsing while retaining global sentence and subtree information. Across 29 treebanks and 20 languages, it achieved state-of-the-art performance on 21 corpora, with future work targeting error analysis and child-order learning.
- 5 Conclusion: STACKPTR combines pointer networks with an internal stack to track top-down, depth-first decoding.The architecture captures information from the whole sentence and previously derived subtrees.
- 5 Conclusion: STACKPTR removes the classical left-to-right restriction while maintaining a number of parsing steps linear in sentence length.
- 5 Conclusion: 21 of 29 treebanks achieved state-of-the-art performance across 20 languages.
- 5 Conclusion: Future work includes improving qualitative and quantitative parsing-error analysis and learning an optimal child order with reinforcement learning.
Appendix A: Hyper-Parameters
The appendix summarizes hyper-parameters used across the experiments. The same hyper-parameters were applied across models, treebanks, and languages because of time constraints.
- Appendix A: Hyper-Parameters: The experiments use the same hyper-parameters across models, treebanks, and languages due to time constraints.
- Appendix A: Hyper-Parameters: Table 5 summarizes the hyper-parameters used for all experiments.
Appendix B: UD Treebanks
The appendix reports corpus statistics for UD treebanks covering 12 languages and specifies how punctuation is handled during evaluation.
- Appendix B: UD Treebanks: Evaluation excludes tokens whose POS tags are “PUNCT” or “SYM”.
- Appendix B: UD Treebanks: Table 6 reports corpus statistics for UD treebanks covering 12 languages.The table includes sentence and word counts, with word counts reported with and without punctuation.
Appendix C: Main Results
The appendix presents parsing results for model variations across development and test sets in three languages. Experiments vary decoding beam size and report means with standard deviations over five runs.
- Appendix C: Main Results: Experiments use decoding beam sizes of 1, 5, and 10, reporting means and standard deviations over 5 runs.
- Appendix C: Main Results: Table 7 compares model variations on development and test sets for three languages against the BIAF parser baseline.