A Fast and Accurate Dependency Parser using Neural Networks

Danqi ChenChristopher D. Manning

article2014EMNLP1,916 citations

Presents a greedy transition-based dependency parser powered by a neural network that replaces millions of sparse indicator features with compact dense representations, achieving high parsing accuracy while processing over 1,000 sentences per second.

Listen

Automated sentence analysis, known as dependency parsing, is essential for language-driven technology applications such as search, translation, and information extraction. Traditional transition-based parsers rely on millions of hand-crafted, sparse indicator features. This legacy design creates significant bottlenecks: extracting and querying these complex features consumes over 95% of total runtime, manual templates fail to capture all necessary word combinations, and models generalize poorly on unseen data.

The article evaluates whether replacing manual, sparse features with a compact neural network utilizing dense vector representations can simultaneously improve parsing accuracy and execution speed.

To demonstrate this, the researchers built a greedy transition-based parser powered by a single-hidden-layer neural network. The model maps words, grammatical tags (part-of-speech tags), and relationship labels into compact, continuous vector representations (embeddings). It employs a novel cubic activation function to naturally capture multi-word interactions and utilizes a pre-computation caching technique during runtime to eliminate repetitive mathematical calculations. The system was evaluated across standard English (Penn Treebank) and Chinese (Chinese Treebank) benchmarks covering tens of thousands of sentences.

The evaluation yielded several key findings. First, the neural parser achieved a parsing throughput of 654 to 1,013 sentences per second on English text, processing sentences roughly 20 times faster than standard baseline transition parsers and up to 100 times faster than graph-based alternatives like MSTParser. Second, it delivered an approximate 2% improvement in attachment accuracy across both English and Chinese benchmarks compared to standard greedy parsers, reaching 92.0% unlabeled accuracy on standard English tests. Third, the novel cubic activation function alone contributed a 0.8% to 1.2% accuracy improvement over standard neural activation functions such as tanh and sigmoid. Finally, incorporating part-of-speech tag embeddings drove substantial performance gains, boosting accuracy by 1.7% in English and nearly 10% in Chinese.

These findings prove that natural language processing pipelines do not need to trade accuracy for processing speed. By slashing feature computation overhead and learning rich compact features automatically, this neural approach delivers substantial operational cost and latency savings for high-volume text processing systems while outperforming manual feature engineering.

Organizations deploying large-scale text parsing systems should consider transitioning from sparse, template-based architectures to compact neural classifiers using dense representations. Engineering teams should also adopt runtime pre-computation caching for frequent vocabulary words to unlock maximum throughput. As an immediate next step, developers can explore integrating this neural classifier with search-based decoding methods (such as beam search) or incorporating additional positional features to further improve parsing quality.

Confidence in these findings is high given the rigorous evaluation across multiple languages, dependency frameworks, and standard benchmarks. However, leaders should note that greedy parsing can be vulnerable to early decision errors propagating down the sentence, and the study was conducted within controlled, standard treebank benchmarks where sentences are largely well-formed.

Chen et al (2014).pdf
  • Paper: Natural Language Processing (almost) from Scratch, Ronan Collobert et al. (2011). Read this account of neural NLP replacing hand-crafted features with learned dense representations first; it establishes the feature-learning approach that this parser adapts to dependency parsing.
  • Paper: Deep Biaffine Attention for Neural Dependency Parsing, Timothy Dozat et al. (2016). This later dependency parser advances the neural parsing approach with deep biaffine attention, making it a direct next step from the source’s transition-based neural model.
Cover for A Fast and Accurate Dependency Parser using Neural Networks

Abstract

Almost all current dependency parsers classify based on millions of sparse indicator features. Not only do these features generalize poorly, but the cost of feature computation restricts parsing speed significantly. In this work, we propose a novel way of learning a neural network classifier for use in a greedy, transition-based dependency parser. Because this classifier learns and uses just a small number of dense features, it can work very fast, while achieving an about 2% improvement in unlabeled and labeled attachment scores on both English and Chinese datasets. Concretely, our parser is able to parse more than 1000 sentences per second at 92.2% unlabeled attachment score on the English Penn Treebank.

Table of Contents

  • 1 Introduction
  • 2 Transition-based Dependency Parsing
  • 3 Neural Network Based Parser
  • 3.1 Model
  • 3.2 Training
  • 3.3 Parsing
  • 4 Experiments
  • 4.1 Datasets
  • 4.2 Results
  • 4.3 Effects of Parser Components
  • 4.4 Model Analysis
  • 5 Related Work
  • 6 Conclusion
  • Acknowledgments
  • References

Knowls

  1. Knowl 1 — Neural Network Architecture for Greedy Transition-Based Dependency Parsing

    model/method

    The dependency parser uses a single-hidden-layer feedforward neural network classifier to make greedy transition decisions in an arc-standard dependency transition system.

    Let dd be the embedding dimension, NwN_w the dictionary size, NtN_t the number of part-of-speech (POS) tags, and NlN_l the number of dependency arc labels. The model maintains dense embedding matrices Ew∈Rd×NwE^w \in \mathbb{R}^{d \times N_w}, Et∈Rd×NtE^t \in \mathbb{R}^{d \times N_t}, and El∈Rd×NlE^l \in \mathbb{R}^{d \times N_l}. From a given configuration c=(s,b,A)c = (s, b, A), sets of nwn_w words, ntn_t POS tags, and nln_l arc labels are extracted and mapped to their respective dense vectors, forming concatenated input vectors xw∈Rd⋅nwx^w \in \mathbb{R}^{d \cdot n_w}, xt∈Rd⋅ntx^t \in \mathbb{R}^{d \cdot n_t}, and xl∈Rd⋅nlx^l \in \mathbb{R}^{d \cdot n_l}.

    The input is mapped to a hidden layer h∈Rdhh \in \mathbb{R}^{d_h} using a component-wise cube activation function:

    h=(W1wxw+W1txt+W1lxl+b1)3h = \left(W_1^w x^w + W_1^t x^t + W_1^l x^l + b_1\right)^3

    where W1w∈Rdh×(d⋅nw)W_1^w \in \mathbb{R}^{d_h \times (d \cdot n_w)}, W1t∈Rdh×(d⋅nt)W_1^t \in \mathbb{R}^{d_h \times (d \cdot n_t)}, W1l∈Rdh×(d⋅nl)W_1^l \in \mathbb{R}^{d_h \times (d \cdot n_l)}, and b1∈Rdhb_1 \in \mathbb{R}^{d_h} is a bias vector.

    A softmax output layer calculates probabilities over the set of possible transitions T\mathcal{T} (∣T∣=2Nl+1|\mathcal{T}| = 2N_l + 1):

    p=softmax(W2h)p = \text{softmax}\left(W_2 h\right)

    where W2∈R∣T∣×dhW_2 \in \mathbb{R}^{|\mathcal{T}| \times d_h}. At each parsing step, the transition with the highest score among all legally feasible transitions is executed greedily: t∗=arg⁡max⁡t∈TfeasibleW2(t,⋅)h(c)t^* = \arg\max_{t \in \mathcal{T}_{\text{feasible}}} W_2(t, \cdot) h(c).

  2. Knowl 2 — Context Element Feature Selection for Neural Dependency Parsing

    model/method

    For any parsing configuration c=(s,b,A)c = (s, b, A) in the arc-standard system, three sets of contextual elements are selected:

    1. Word element set SwS^w (nw=18n_w = 18 elements):

      • The top 3 words on the stack: s1,s2,s3s_1, s_2, s_3.
      • The top 3 words on the buffer: b1,b2,b3b_1, b_2, b_3.
      • The first and second leftmost and rightmost children of the top two stack words: lc1(si),rc1(si),lc2(si),rc2(si)lc_1(s_i), rc_1(s_i), lc_2(s_i), rc_2(s_i) for i∈{1,2}i \in \{1, 2\}.
      • The leftmost-of-leftmost and rightmost-of-rightmost children of the top two stack words: lc1(lc1(si)),rc1(rc1(si))lc_1(lc_1(s_i)), rc_1(rc_1(s_i)) for i∈{1,2}i \in \{1, 2\}.
    2. Part-of-speech (POS) tag set StS^t (nt=18n_t = 18 elements):

      • The POS tags corresponding to all 18 elements chosen in SwS^w.
    3. Dependency label set SlS^l (nl=12n_l = 12 elements):

      • The arc labels of the 12 modifier/children elements selected in SwS^w, excluding the 6 primary stack and buffer heads (s1,s2,s3,b1,b2,b3s_1, s_2, s_3, b_1, b_2, b_3).

    If an element does not exist in the current configuration (such as a missing child or stack element), a dedicated NULL token embedding is used in its place.

  3. Knowl 3 — Cube Activation Function for Third-Order Feature Interactions

    model/method

    The neural parser employs the element-wise cube activation function g(x)=x3g(x) = x^3 in its hidden layer instead of standard activation functions such as tanh⁡\tanh or sigmoid. When applied to an affine transformation of the concatenated input vector ∑m=1Mwmxm+b\sum_{m=1}^M w_m x_m + b, the cube function directly expands to:

    g(∑m=1Mwmxm+b)=∑i,j,k(wiwjwk)xixjxk+∑i,jb(wiwj)xixj+…g\left(\sum_{m=1}^M w_m x_m + b\right) = \sum_{i,j,k} (w_i w_j w_k) x_i x_j x_k + \sum_{i,j} b (w_i w_j) x_i x_j + \dots

    Because input dimensions xi,xj,xkx_i, x_j, x_k originate from distinct dimensions of word, POS tag, and arc label embeddings, the cubic mapping inherently models third-order product interaction terms (conjunctions of three distinct input features) without requiring manually designed conjunction feature templates.

  4. Knowl 4 — Pre-computation Optimization for Fast Neural Parser Inference

    algorithm

    During greedy parsing, computing the hidden layer activations at every step dominates runtime. Because the number of distinct positions and categorical elements is small, linear embedding projections can be pre-computed before parsing begins.

    Input: Trained weight matrices W1w,W1t,W1lW_1^w, W_1^t, W_1^l, embedding matrices Ew,Et,ElE^w, E^t, E^l, vocabulary of top frequent words VfreqV_{\text{freq}} (size 10,000), set of all POS tags P\mathcal{P}, set of all arc labels L\mathcal{L}, configuration positions Sw,St,SlS^w, S^t, S^l
    Output: Pre-computed lookup tables Tw,Tt,TlT^w, T^t, T^l
    for each position index i∈{1,…,∣Sw∣}i \in \{1, \dots, |S^w|\} do
        for each word w∈Vfreqw \in V_{\text{freq}} do
            Tw[i,w]←W1w[⋅,(i−1)d+1:id]⋅Ew[⋅,w]T^w[i, w] \leftarrow W_1^w[\cdot, (i-1)d+1 : id] \cdot E^w[\cdot, w]
    for each position index i∈{1,…,∣St∣}i \in \{1, \dots, |S^t|\} do
        for each POS tag t∈Pt \in \mathcal{P} do
            Tt[i,t]←W1t[⋅,(i−1)d+1:id]⋅Et[⋅,t]T^t[i, t] \leftarrow W_1^t[\cdot, (i-1)d+1 : id] \cdot E^t[\cdot, t]
    for each position index i∈{1,…,∣Sl∣}i \in \{1, \dots, |S^l|\} do
        for each arc label l∈Ll \in \mathcal{L} do
            Tl[i,l]←W1l[⋅,(i−1)d+1:id]⋅El[⋅,l]T^l[i, l] \leftarrow W_1^l[\cdot, (i-1)d+1 : id] \cdot E^l[\cdot, l]

    During parsing of a configuration cc, the hidden layer pre-activation is computed by retrieving pre-computed vectors from Tw,Tt,TlT^w, T^t, T^l (or computing matrix-vector products on-the-fly for out-of-vocabulary words not in VfreqV_{\text{freq}}), summing them together with bias b1b_1, and applying the cube activation h(c)=(∑v)3h(c) = (\sum v)^3. This lookup optimization delivers an 8×8\times to 10×10\times inference speedup.

  5. Knowl 5 — Training Objective and Oracle Strategy for Neural Dependency Parsing

    model/method

    Training configurations and oracle transitions {(ci,ti)}i=1m\{(c_i, t_i)\}_{i=1}^m are generated from gold dependency trees using a shortest-stack oracle that prioritizes LEFT-ARC(l)\text{LEFT-ARC}(l) over SHIFT\text{SHIFT}.

    The model parameters θ={W1w,W1t,W1l,b1,W2,Ew,Et,El}\theta = \{W_1^w, W_1^t, W_1^l, b_1, W_2, E^w, E^t, E^l\} are trained by minimizing the cross-entropy loss over oracle transitions regularized by L2L_2 weight decay:

    L(θ)=−∑i=1mlog⁡pti+λ2∥θ∥2L(\theta) = -\sum_{i=1}^m \log p_{t_i} + \frac{\lambda}{2} \|\theta\|^2

    where softmax probabilities ptip_{t_i} are normalized only over feasible transitions for configuration cic_i. Optimization uses mini-batched AdaGrad with initial learning rate α=0.01\alpha = 0.01, dropout rate 0.50.5, regularization parameter λ=10−8\lambda = 10^{-8}, hidden dimension dh=200d_h = 200, and embedding dimension d=50d = 50. Word embeddings EwE^w are initialized with pre-trained vectors and fine-tuned during backpropagation, whereas POS and label embeddings are randomly initialized uniformly in (−0.01,0.01)(-0.01, 0.01).

  6. Knowl 6 — Parsing Accuracy and Speed on English PTB and Chinese CTB Benchmarks

    data/table

    The neural dependency parser was evaluated on the English Penn Treebank with CoNLL dependencies (PTB: CD), Stanford Dependencies (PTB: SD), and the Chinese Penn Treebank (CTB5). Unlabeled attachment score (UAS) and labeled attachment score (LAS) exclude punctuation. Speeds are measured in sentences per second (sent/s) on an Intel Core i7 2.7GHz CPU.

    Parser Dev Test Speed
    UAS LAS UAS LAS (sent/s)
    PTB: CoNLL Dependencies
    standard baseline 89.9 88.7 89.7 88.3 51
    eager baseline 90.3 89.2 89.9 88.6 63
    MaltParser (stackproj) 90.0 88.8 89.9 88.5 560
    MaltParser (nivreeager) 90.1 88.9 90.1 88.7 535
    MSTParser 92.1 90.8 92.0 90.5 12
    Neural Parser 92.2 91.0 92.0 90.7 1013
    PTB: Stanford Dependencies
    standard baseline 90.2 87.8 89.4 87.3 26
    eager baseline 89.8 87.4 89.6 87.4 34
    MaltParser (stackproj) 89.8 87.2 89.3 86.9 469
    MaltParser (nivreeager) 89.6 86.9 89.4 86.8 448
    MSTParser 91.4 88.1 90.7 87.6 10
    Neural Parser 92.0 89.7 91.8 89.6 654
    CTB
    standard baseline 82.4 80.9 82.7 81.2 72
    eager baseline 81.1 79.7 80.3 78.7 80
    MaltParser (stackproj) 82.4 80.5 82.4 80.6 420
    MaltParser (nivreeager) 81.2 79.3 80.2 78.4 393
    MSTParser 84.0 82.1 83.0 81.2 6
    Neural Parser 84.0 82.4 83.9 82.4 936

    The neural parser outperforms standard greedy transition baselines by approximately 2%2\% in UAS and LAS across all datasets while operating 10×10\times to 20×20\times faster than standard greedy baselines and nearly 100×100\times faster than the graph-based MSTParser.

  7. Knowl 7 — Empirical Superiority of Cube Activation Over Standard Non-Linearities

    empirical result

    When comparing different activation functions in the neural hidden layer while keeping all other hyperparameters constant (d=50,dh=200d=50, d_h=200):

    • The cube activation function g(x)=x3g(x) = x^3 outperforms tanh⁡\tanh, sigmoid\text{sigmoid}, and identity (g(x)=xg(x) = x) activations across all tested datasets.
    • Cube achieves an improvement of 0.8%0.8\% to 1.2%1.2\% in unlabeled attachment score (UAS) over tanh⁡\tanh on PTB: CD, PTB: SD, and CTB.
    • The identity activation function consistently produces the lowest parsing accuracy, demonstrating the necessity of non-linear interaction modeling.
  8. Knowl 8 — Impact of POS Tag and Dependency Label Embeddings

    empirical result

    Ablation experiments on embedding input components demonstrate:

    1. Incorporating learned dense part-of-speech (POS) tag embeddings yields substantial accuracy gains: approximately 1.7%1.7\% UAS improvement on English PTB and nearly 10%10\% UAS improvement on Chinese CTB compared to using word embeddings alone.
    2. When POS embeddings are absent, arc label embeddings provide a modest gain (0.3%0.3\% on PTB and 1.4%1.4\% on CTB).
    3. When POS embeddings are already present, adding arc label embeddings provides minimal incremental accuracy gain, indicating that the POS tags of two tokens already encode most of the relational arc label information between them.
  9. Knowl 9 — Effect of Pre-trained Word Vector Initialization on Parsing Accuracy

    empirical result

    Initializing word embeddings with pre-trained vectors (Collobert et al. 50-dimensional vectors for English, and 50-dimensional word2vec vectors for Chinese) improves performance compared to random uniform initialization within (−0.01,0.01)(-0.01, 0.01):

    • On English PTB, pre-trained initialization yields an improvement of approximately 0.7%0.7\% in UAS.
    • On Chinese CTB, pre-trained initialization yields an improvement of approximately 1.7%1.7\% in UAS.
    • Even when initialized purely from random weights, the dense neural parser remains competitive, demonstrating that the architecture can learn effective representations directly from treebank annotations.

Coverage note — None was omitted; all contributed models, equations, algorithms, empirical results, and ablation findings from the paper have been converted into self-contained knowls.

References

  1. 1.Bernd Bohnet. 2010. Very high accuracy and fast dependency parsing is not a contradiction. In Coling.
  2. 2.Ronan Collobert, Jason Weston, Leon Bottou, Michael Karlen, Koray Kavukcuoglu, and Pavel Kuksa. 2011. Natural language processing (almost) from scratch. Journal of Machine Learning Research.
  3. 3.Ronan Collobert. 2011. Deep learning for efficient discriminative parsing. In AISTATS.
  4. 4.Marie-Catherine de Marneffe, Bill MacCartney, and Christopher D. Manning. 2006. Generating typed dependency parses from phrase structure parses. In LREC.
  5. 5.Jacob Devlin, Rabih Zbib, Zhongqiang Huang, Thomas Lamar, Richard Schwartz, and John Makhoul. 2014. Fast and robust neural network joint models for statistical machine translation. In ACL.
  6. 6.John Duchi, Elad Hazan, and Yoram Singer. 2011. Adaptive subgradient methods for online learning and stochastic optimization. The Journal of Machine Learning Research.
  7. 7.Rong-En Fan, Kai-Wei Chang, Cho-Jui Hsieh, Xiang-Rui Wang, and Chih-Jen Lin. 2008. Liblinear: A library for large linear classification. The Journal of Machine Learning Research.
  8. 8.Nikhil Garg and James Henderson. 2011. Temporal restricted boltzmann machines for dependency parsing. In ACL-HLT.
  9. 9.He He, Hal Daume III, and Jason Eisner. 2013. Dynamic feature selection for dependency parsing. In EMNLP.
  10. 10.James Henderson. 2004. Discriminative training of a neural network statistical parser. In ACL.
  11. 11.Geoffrey E. Hinton, Nitish Srivastava, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. 2012. Improving neural networks by preventing co-adaptation of feature detectors. CoRR, abs/1207.0580.
  12. 12.Liang Huang, Wenbin Jiang, and Qun Liu. 2009. Bilingually-constrained (monolingual) shift-reduce parsing. In EMNLP.
  13. 13.Richard Johansson and Pierre Nugues. 2007. Extended constituent-to-dependency conversion for english. In Proceedings of NODALIDA, Tartu, Estonia.
  14. 14.Lingpeng Kong and Noah A. Smith. 2014. An empirical comparison of parsing methods for Stanford dependencies. CoRR, abs/1404.4314.
  15. 15.Terry Koo, Xavier Carreras, and Michael Collins. 2008. Simple semi-supervised dependency parsing. In ACL.
  16. 16.Sandra Kubler, Ryan McDonald, and Joakim Nivre. 2009. Dependency Parsing. Synthesis Lectures on Human Language Technologies. Morgan & Claypool.
  17. 17.Marshall R. Mayberry III and Risto Miikkulainen. 1999. Sardsrn: A neural network shift-reduce parser. In IJCAI.
  18. 18.Marshall R. Mayberry III and Risto Miikkulainen. 2005. Broad-coverage parsing with neural networks. Neural Processing Letters.
  19. 19.Ryan McDonald and Fernando Pereira. 2006. Online learning of approximate dependency parsing algorithms. In EACL.
  20. 20.Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. 2013. Distributed representations of words and phrases and their compositionality. In NIPS.
  21. 21.Joakim Nivre, Johan Hall, and Jens Nilsson. 2006. Maltparser: A data-driven parser-generator for dependency parsing. In LREC.
  22. 22.Richard Socher, John Bauer, Christopher D Manning, and Andrew Y Ng. 2013. Parsing with compositional vector grammars. In ACL.
  23. 23.Richard Socher, Andrej Karpathy, Quoc V. Le, Christopher D. Manning, and Andrew Y. Ng. 2014. Grounded compositional semantics for finding and describing images with sentences. TACL.
  24. 24.Pontus Stenetorp. 2013. Transition-based dependency parsing using recursive neural networks. In NIPS Workshop on Deep Learning.
  25. 25.Ivan Titov and James Henderson. 2007. Fast and robust multilingual dependency parsing with a generative latent variable model. In EMNLP-CoNLL.
  26. 26.Kristina Toutanova, Dan Klein, Christopher D. Manning, and Yoram Singer. 2003. Feature-rich part-of-speech tagging with a cyclic dependency network. In NAACL.
  27. 27.Laurens van der Maaten and Geoffrey Hinton. 2008. Visualizing data using t-SNE. The Journal of Machine Learning Research.
  28. 28.Yue Zhang and Stephen Clark. 2008. A tale of two parsers: Investigating and combining graph-based and transition-based dependency parsing using beam-search. In EMNLP.
  29. 29.Yue Zhang and Joakim Nivre. 2011. Transition-based dependency parsing with rich non-local features. In ACL.

Citation

MLA
Chen, D., and C. D. Manning. “A Fast and Accurate Dependency Parser Using Neural Networks”. Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), 2014, pp. 740–50, https://doi.org/10.3115/v1/D14-1082.
APA
Chen, D., & Manning, C. D. (2014). A Fast and Accurate Dependency Parser using Neural Networks. Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), 740–750. https://doi.org/10.3115/v1/D14-1082
Chicago
Chen, D., and C. D. Manning. 2014. “A Fast and Accurate Dependency Parser Using Neural Networks”. Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), 740–50. https://doi.org/10.3115/v1/D14-1082.
Harvard
Chen, D. and Manning, C.D. (2014) “A Fast and Accurate Dependency Parser using Neural Networks”, Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP). Association for Computational Linguistics, pp. 740–750. Available at: https://doi.org/10.3115/v1/D14-1082.
Vancouver
1. Chen D, Manning CD (2014) A Fast and Accurate Dependency Parser using Neural Networks. In: Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP). Association for Computational Linguistics, pp 740–750

BibTeX

@inproceedings{chen-manning-2014-fast,
    title = "A Fast and Accurate Dependency Parser using Neural Networks",
    author = "Chen, Danqi  and
      Manning, Christopher",
    editor = "Moschitti, Alessandro  and
      Pang, Bo  and
      Daelemans, Walter",
    booktitle = "Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing ({EMNLP})",
    month = oct,
    year = "2014",
    address = "Doha, Qatar",
    publisher = "Association for Computational Linguistics",
    url = "https://aclanthology.org/D14-1082/",
    doi = "10.3115/v1/D14-1082",
    pages = "740--750"
}
Metadata:ACL Anthology

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF
License: https://creativecommons.org/licenses/by-nc-sa/4.0/