Deep NLP

3 episodes · follows chapter 20 of the textbook

Dependency Parsing

Grammar as one typed arc per word. The module builds dependency trees as parent arrays, reads Universal Dependencies CoNLL-U, and defines projectivity by dominance and by crossing arcs. It then builds the two parser families from scratch: transition-based parsing (arc-standard and arc-eager state machines, static oracles, a sparse softmax action classifier with named losses, greedy and beam decoding, feature ablations) and graph-based parsing (a NumPy biaffine scorer with hand-written backprop, Chu-Liu/Edmonds and Eisner decoding), evaluated with token-level UAS/LAS and explicit punctuation and averaging conventions.

Progress — loading…

Objectives

Language

  • Read and write UD dependency trees; explain heads, relations and UD's content-head conventions
  • Explain why non-projective structures arise (extraposition, wh-movement, free word order)
  • Compare transition-based and graph-based parsers, and greedy vs global decoding
  • Evaluate parsers with UAS, LAS and exact match under stated conventions

Math & data structures

  • Trees as parent arrays; O(n) cycle detection; projectivity via dominance and crossing spans
  • Stack + buffer state machines; the 2n transition count; static oracles
  • Sparse softmax classification; cross-entropy plus L2 as named components
  • Maximum spanning arborescence by cycle contraction (gain rescoring); Eisner's O(n^3) DP
  • The biaffine score x^T U y as a learned bilinear compatibility; its gradient

Code

  • CoNLL-U reader, projectivity checker and toy treebank generator
  • Arc-standard/arc-eager systems and oracles that rebuild every projective gold tree (tested)
  • Biaffine scorer with gradcheck-verified gradients, CLE/Eisner decoders verified against brute force
  • UAS/LAS/exact match with punctuation and averaging options; a PyTorch BiLSTM-biaffine port

Episodes

  1. Dependency Relations and Universal Dependencies20 min · 36 cues

    Heads, dependents, relations, projectivity, UD.

  2. Transition-Based Parsing20 min · 36 cues

    Stack + buffer, arc-standard, oracles, classifiers.

  3. Graph-Based Parsing and Evaluation20 min · 36 cues

    MST parsing (Chu-Liu/Edmonds), biaffine scoring, UAS/LAS.

Exercises

ExerciseTierLadderTime
Trees as parent arrays, CoNLL-U, and a projectivity checker browserPredict · Scratch45 min
Arc-standard and arc-eager state machines with static oracles browserPredict · Scratch · Compose75 min
Biaffine arc scores, the head-selection loss with masking, Chu-Liu/Edmonds, UAS/LAS browserScratch · Harden · Compose90 min
Break it: an impatient arc-standard oracle, and what global decoding really buys browserPredict · Break it · Probe a claim75 min
Port: BiLSTM + biaffine dependency parser in PyTorch, with masks and two named losses gpuPort · Harden120 min

Labs

  • Dependency Relations and Universal Dependencies browser C20.01 lab: dependency trees as parent arrays, CoNLL-U, arc diagrams and projectivity. Exercise: C20.ex01-projectivity-checker (write the checker yourself; these cells use the library version so you can compare). Data: curriculum/modules/C20/data (run data/make_data.py if the .conllu files are missing). · 50 min
  • Transition-Based Parsing browser C20.02 lab: arc-standard and arc-eager, static oracles, and a greedy parser you can see inside. Exercise: C20.ex02-transition-oracle (implement the state machines and oracles yourself). Every step prints the actual configuration, the features that fired, the weights, and the named losses. · 75 min
  • Graph-Based Parsing and Evaluation browser C20.03 lab: a biaffine scorer, Chu-Liu/Edmonds decoding, and honest UAS/LAS. Exercises: C20.ex03-mst-biaffine (write the pieces), C20.ex04-decoding-break-it (the decoder experiment), C20.ex05-biaffine-torch (the GPU port with a BiLSTM). Every cell prints the actual matrices, losses and scores. · 75 min

Library contributions

Files in nlpcore this module teaches you to write.

Sources

  1. Chen, D. & Manning, C. D. (2014). A Fast and Accurate Dependency Parser using Neural Networks. EMNLP 2014, pp. 740-750 · link
  2. Chu, Y. J. & Liu, T. H. (1965). On the shortest arborescence of a directed graph. Scientia Sinica 14
  3. CoNLL 2018 Shared Task: Multilingual Parsing from Raw Text to Universal Dependencies, evaluation page · link
  4. de Marneffe, Manning, Nivre & Zeman (2021). Universal Dependencies. Computational Linguistics 47(2):255-308 · link
  5. Dozat, T. & Manning, C. D. (2017). Deep Biaffine Attention for Neural Dependency Parsing. ICLR 2017 · arXiv:1611.01734
  6. Edmonds, J. (1967). Optimum branchings. Journal of Research of the National Bureau of Standards 71B
  7. Eisner, J. (1996). Three New Probabilistic Models for Dependency Parsing: An Exploration. COLING 1996 · link · arXiv:cmp-lg/9706003
  8. Goldberg, Y. & Nivre, J. (2012). A Dynamic Oracle for Arc-Eager Dependency Parsing. COLING 2012
  9. Kiperwasser, E. & Goldberg, Y. (2016). Simple and Accurate Dependency Parsing Using Bidirectional LSTM Feature Representations. TACL 4 · link · arXiv:1603.04351
  10. Kun, A Programmer's Introduction to Mathematics (2nd ed.) · §Ch. 1 Like Programming, Mathematics has a Culture
  11. McDonald, Pereira, Ribarov & Hajič (2005). Non-projective Dependency Parsing using Spanning Tree Algorithms. HLT-EMNLP 2005, pp. 523-530 · link
  12. Nivre, J. (2003). An Efficient Algorithm for Projective Dependency Parsing. IWPT 2003, Nancy, pp. 149-160 · link
  13. Nivre, J. (2004). Incrementality in Deterministic Dependency Parsing (arc-standard), ACL workshop
  14. Nivre, J. (2008). Algorithms for Deterministic Incremental Dependency Parsing. Computational Linguistics 34(4):513-553 · link
  15. Nivre et al. (2016). Universal Dependencies v1: A Multilingual Treebank Collection. LREC 2016 · link
  16. Qi, Zhang, Zhang, Bolton & Manning (2020). Stanza: A Python Natural Language Processing Toolkit for Many Human Languages · arXiv:2003.07082
  17. Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft (Aug 19, 2026), Ch. 20 Dependency Parsing · link · §20.1, 20.1.1, 20.1.2, 20.1.3, 20.2, 20.2.1, 20.2.2, 20.2.3, 20.2.4, 20.3, 20.3.1, 20.3.2, 20.3.3, 20.4, 20.5, Historical Notes
  18. Tesnière, L. (1959). Éléments de syntaxe structurale. Paris: Klincksieck (posthumous; English translation 2015)