Deep NLP

4 episodes · follows chapter 18 of the textbook

Sequence Labeling: Parts of Speech and Named Entities

Tagging is the first structured-prediction problem: assign a label to every token when the right label depends on its neighbours. We measure ambiguity and the most-frequent-tag baseline, build the hidden Markov model (counting, the generative story, the forward algorithm in log space), derive Viterbi decoding with backpointers (in NumPy and in C), and replace the generative model with a linear-chain CRF whose partition function, marginals and gradient we compute and gradcheck. NER closes the loop: BIO encoding, entity-level vs token-level evaluation, invalid transitions, and a transformer + CRF tagger on CoNLL-2003.

Progress — loading…

Objectives

Language

  • Explain parts of speech as distributional classes, UD (17) vs Penn Treebank (45) tagsets, and type vs token ambiguity
  • Encode named entities as BIO/IO/BIOES and explain what each scheme can and cannot represent
  • Evaluate taggers with the right metric: token accuracy for POS, exact-match entity P/R/F1 for NER, with baselines
  • Compare HMM, per-token softmax, CRF and encoder+CRF taggers on unseen words and BIO validity

Math & data structures

  • Markov chains as weighted state machines; HMM parameters pi, A, B estimated by counting (with smoothing and <UNK>)
  • The forward algorithm as dynamic programming over a trellis; O(T K^2) vs K^T; log space and log-sum-exp
  • Viterbi: max instead of sum, backpointers, optimal substructure (cut-and-paste argument), shortest path in a DAG
  • Linear-chain CRF: softmax over sequences, log Z by forward, gradient = expected - observed counts via forward-backward
  • Generative vs discriminative modelling (links Naive Bayes and Generative vs Discriminative (Appendix B)); temperature view: forward = soft Viterbi

Code

  • nlpcore.structure.hmm: CoNLL-U reader, supervised estimation, forward/backward/posteriors, underflow demo
  • nlpcore.structure.viterbi: log-space Viterbi with backpointers, masks, greedy/brute-force/n-best, trellis frames
  • nlpcore.structure.crf: NumPy linear-chain CRF with gradcheck, feature templates and a logged training loop
  • nlpcore.eval.ner: BIO validation/repair, span conversion, token vs entity P/R/F1, error table, BIO transition mask
  • Systems lane: Viterbi in C over row-major arrays with a gcc assert harness and timing
  • PyTorch port: batched, masked CRF layer on a transformer encoder (toy NER on CPU, CoNLL-2003 on GPU)

Episodes

  1. Word Classes, Tagsets, and the Tagging Task19 min · 35 cues

    POS classes, PTB and UD tagsets, ambiguity, baselines, NER and BIO encoding.

  2. Hidden Markov Models20 min · 35 cues

    Markov chains, hidden states, emission/transition matrices, generative story, forward algorithm.

  3. The Viterbi Algorithm20 min · 41 cues

    DP over a lattice, backpointers, log space, complexity.

  4. CRFs, Neural Taggers, and NER Evaluation20 min · 39 cues

    From HMM to discriminative CRF; transformer taggers; entity-level F1; invalid BIO transitions.

Exercises

ExerciseTierLadderTime
Ambiguity statistics and the most-frequent-tag baseline browserPredict · Scratch45 min
An HMM from counts, and the forward algorithm in probability and log space browserPredict · Scratch · Harden · Compose60 min
Viterbi decoding in log space with backpointers and a visible trellis browserScratch · Harden · Compose50 min
Systems lane: Viterbi in C with a gcc assert harness systems · cScratch · Harden60 min
Break it: underflow, no lookahead, no smoothing (three mini-experiments) browserPredict · Break it60 min
A linear-chain CRF from scratch in NumPy (partition function, marginals, gradcheck, training, probe a claim) browserScratch · Harden · Probe a claim90 min
NER evaluation: BIO validation and repair, token- vs entity-level F1, error analysis browserScratch · Harden · Compose60 min
Port the CRF to PyTorch: transformer + CRF tagger (toy NER on CPU, CoNLL-2003 on GPU) gpuPort · Compose120 min

Labs

Library contributions

Files in nlpcore this module teaches you to write.

Sources

  1. Baum, L. E., Petrie, T., Soules, G., Weiss, N. A Maximization Technique Occurring in the Statistical Analysis of Probabilistic Functions of Markov Chains. Annals of Mathematical Statistics 41(1):164-171, 1970. doi:10.1214/aoms/1177697196
  2. Church, K. W. A Stochastic Parts Program and Noun Phrase Parser for Unrestricted Text. Second Conference on Applied Natural Language Processing (ANLP), Austin, Texas, pp. 136-143, 1988 · link
  3. eriktks/conll2003 on the Hugging Face Hub (annotations; Reuters text under NIST/Reuters research agreements) · link
  4. Zhang, Lipton, Li, Smola. Dive into Deep Learning: Sec. 9.4.1 (Bidirectional RNNs), 'Dynamic Programming in Hidden Markov Models' · link
  5. DeRose, S. J. Grammatical Category Disambiguation by Statistical Optimization. Computational Linguistics 14(1):31-39, 1988 · link
  6. Eisner, J. An interactive spreadsheet for teaching the forward-backward algorithm. ACL-02 Workshop on Effective Tools and Methodologies for Teaching NLP and CL, Philadelphia, 2002
  7. Greene, B. B., Rubin, G. M. Automatic grammatical tagging of English (TAGGIT), 1971
  8. Lafferty, J., McCallum, A., Pereira, F. Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data. ICML 2001 · link
  9. Lample, G., Ballesteros, M., Subramanian, S., Kawakami, K., Dyer, C. Neural Architectures for Named Entity Recognition. NAACL-HLT 2016 · link · arXiv:1603.01360
  10. Manning, C. D. Part-of-Speech Tagging from 97% to 100%: Is It Time for Some Linguistics? CICLing 2011 · link
  11. Marcus, M. P., Santorini, B., Marcinkiewicz, M. A. Building a Large Annotated Corpus of English: The Penn Treebank. Computational Linguistics 19(2):313-330, 1993 · link
  12. Markov, A. A. (1913): vowel/consonant sequences in Pushkin's Eugene Onegin
  13. Merialdo, B. Tagging English text with a probabilistic model. Computational Linguistics 20(2):155-172, 1994
  14. Nivre, J., de Marneffe, M.-C., Ginter, F., Goldberg, Y., Hajic, J., Manning, C. D., McDonald, R., Petrov, S., Pyysalo, S., Silveira, N., Tsarfaty, R., Zeman, D. Universal Dependencies v1: A Multilingual Treebank Collection. LREC 2016 · link
  15. Nivre, J., de Marneffe, M.-C., Ginter, F., Hajic, J., et al. Universal Dependencies v2: An Evergrowing Multilingual Treebank Collection. arXiv:2004.10643, 2020 (LREC 2020) · arXiv:2004.10643
  16. Rabiner, L. R. A tutorial on hidden Markov models and selected applications in speech recognition. Proceedings of the IEEE 77(2):257-286, Feb 1989
  17. Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft (Aug 19, 2026), Appendix A: Hidden Markov Models · link · §A.1, A.2, A.3, A.4, A.5, Historical Notes
  18. Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft (Aug 19, 2026), Ch. 18 Sequence Labeling for Parts of Speech and Named Entities · link · §18.1, 18.2, 18.3, 18.4, 18.5, 18.6, 18.7, Historical Notes
  19. Dionysius Thrax (attrib.), Techne Grammatike, c. 100 BC: eight parts of speech
  20. Tjong Kim Sang, E. F., De Meulder, F. Introduction to the CoNLL-2003 Shared Task: Language-Independent Named Entity Recognition. CoNLL 2003 · link · arXiv:cs/0306050
  21. UD English-EWT (Universal Dependencies), built on the English Web Treebank (LDC2012T13) · link
  22. Andrew Viterbi (Wikipedia): not patented on a lawyer's advice; Linkabit 1968 with Irwin Jacobs; Qualcomm co-founded 1985; algorithm used for error correction in cell phones, speech recognition, DNA analysis · link
  23. Viterbi, A. J. Error bounds for convolutional codes and an asymptotically optimum decoding algorithm. IEEE Transactions on Information Theory 13(2):260-269, April 1967 · link