W1｜From n-grams to Seq2Seq: A Compressed History

Part I — Architecture · 從 n-gram 到 seq2seq：一條被壓縮的技術史

▶ Slides for this week

Where This Fits

This is the only week of pre-Transformer NLP in the course, so it is deliberately restrained: rather than a full tour of what came before, each component is introduced through the specific failure it was built to fix. The point is that when the Transformer arrives you can put a finger on each of its design choices and name the earlier pain it answers.

It is also where the course’s governing metaphor — compression is prediction — is set up, to be used again every few weeks. Two items that belong to no single unit close the week: the compute ledger, and the four questions to put to any paper.

Learning Objectives

  1. Write down the MLE estimate for an n-gram language model and the definition of perplexity, and explain why sparsity cannot be solved by more data — only by the inductive bias that smoothing or backoff supplies.
  2. Explain how the distributional hypothesis is made concrete by the word2vec objective, and identify the structural failure of static embeddings on polysemous words.
  3. Identify the multiplied gradients of BPTT in an RNN and the fixed-length bottleneck of the encoder-decoder, and say which specific symptom of the latter attention was proposed against.
  4. Use cross-entropy and bits-per-byte to argue that a language model is a compressor, and say where that equivalence breaks down.

References

  • JM3 Ch 3 N-gram Language Models, Ch 5 Embeddings, Ch 14 RNNs and LSTMs (the first half of each is enough)
  • UDL ch 1–2 (the catch-up route for students with no background); BB for the probability and optimization assumed here
  • ZZM ch 5 Basic Language Models (n-grams, smoothing, PPL, FNN-LM, LSTM-LM) and ch 3 Distributed Representation (CBOW / skip-gram / ELMo) — these two chapters are very nearly the skeleton of this week, and the book is open access, so it can be handed out directly; take the first half of ch 4 as well for the closing stretch (seq2seq → attention), and add ch 2 Basics of Neural Network if the background is missing
  • Bengio et al., A Neural Probabilistic Language Model, JMLR 2003 — the NPLM, where parameter sharing first answers sparsity
  • Mikolov et al., Efficient Estimation of Word Representations in Vector Space, arXiv:1301.3781 (2013); and Distributed Representations of Words and Phrases and their Compositionality, NeurIPS 2013 — negative sampling is in the second one
  • Pennington et al., GloVe: Global Vectors for Word Representation, EMNLP 2014
  • Sutskever, Vinyals & Le, Sequence to Sequence Learning with Neural Networks, NeurIPS 2014
  • Bahdanau, Cho & Bengio, Neural Machine Translation by Jointly Learning to Align and Translate, ICLR 2015 (arXiv:1409.0473)
  • Bengio, Simard & Frasconi, Learning Long-Term Dependencies with Gradient Descent is Difficult, IEEE Transactions on Neural Networks 5(2):157–166, 1994 — the source of the multiplied-gradient and spectral-radius argument used here
  • Hochreiter & Schmidhuber, Long Short-Term Memory, Neural Computation 9(8):1735–1780, 1997 — where the multiplicative path becomes an additive one; the same idea returns as the residual stream in W4
  • Levy & Goldberg, Neural Word Embedding as Implicit Matrix Factorization, NeurIPS 2014 — ties SGNS back to a PMI matrix factorization; the single strongest reference for the claim that an embedding’s similarity is whatever its training objective defined similarity to be
  • Delétang et al., Language Modeling Is Compression, arXiv:2309.10668 (2023) — turns compression is prediction into something measurable, by using an LLM as a general-purpose compressor and comparing compression rates across modalities. The course’s governing metaphor finally has a paper behind it
  • Theis, van den Oord & Bethge, A note on the evaluation of generative models, arXiv:1511.01844 (2015) — likelihood and sample quality are largely independent in high dimensions, with three constructed counterexamples. The reason a low perplexity does not mean good generations, and the first case study for the third of the four reading questions
  • Other ways into the compression–language-modeling equivalence — search arithmetic coding neural language model, bits per byte evaluation
  • Derivations for Good-Turing and Kneser-Ney — search Chen Goodman empirical study of smoothing
回到頂端