Algorithms for Speech and Natural Language Processing

Contents

• Introduction and overview
• 0. Review: probability, information, dynamic programming and the Fourier transform
• 1. Text as data: a short history, tokenisation and n-gram language models
• 2. Speech features and signal processing
• 3. Hidden Markov models and finite-state modelling
• 4. Sequence labelling
• 5. Word embeddings
• 6. Deep learning for NLP: recurrent networks, attention and transformers
• 7. Neural language modelling and large language models
• 8. Machine translation
• 9. Sentiment analysis
• 10. Speech recognition and speech synthesis
• 11. Chatbots, code generation and agents
• 12. Evaluation: comparing human and machine performance
• 13. Complements for self-study
• 14. Research directions and open problems
• Exercises
• Projects and assessment
• References

Introduction and overview

Audience: a student with a good M1 in mathematics, computer science or physics who has trained a classifier or a small neural network, and who wants to know how machines read, translate, transcribe and speak human language, and why the algorithms look the way they do.

Empirical first: a bigram model trained on three short sentences assigns probability zero, hence infinite perplexity, to the new sentence “the dog saw the cat”, because one pair of words was never seen (ch. 1). A recogniser that hears “wreck a nice beach” for “recognise speech” in the six-word sentence “I want to recognise speech today” makes 4 errors, a word error rate of 67 % (ch. 10).

On synthetic reviews where 40 % of the opinions are negated, a bag-of-words sentiment classifier scores 56 %, and 100 % once the scope of “not” is marked (ch. 9). Each of these failures has a mathematical cause and an algorithmic fix; the course is the list of those fixes.

The course covers the automatic processing of text and speech: how both are represented, how sequences are modelled (finite-state machines, hidden Markov models, conditional random fields, recurrent networks, transformers), and how the main tasks are solved and evaluated. The tasks are language modelling, machine translation, sentiment analysis, sequence labelling, dialogue, speech recognition, speech synthesis, and code generation with agents.

It shares tools with Advanced Learning for Text and Graph Data, Foundations of Large Language Models and Deep Learning in semester 1. In semester 2 it runs alongside Large Language Models for Code and Proof, Audio Signal Processing: Time–Frequency Analysis and Audio Signal Analysis, Indexing and Transformations.

What you will be able to do

• Tokenise text with byte-pair encoding, estimate a smoothed n-gram language model and compute its perplexity.
• Turn a waveform into log-mel and MFCC features, and justify each step from the source–filter model of speech.
• Run the forward, Viterbi and Baum–Welch algorithms of a hidden Markov model, and read them as one dynamic program over a semiring.
• Train a linear-chain conditional random field and evaluate a named-entity tagger with span-level F1.
• Build word vectors from co-occurrence counts and prove that skip-gram with negative sampling factorises a shifted PMI matrix.
• Write a transformer block, explain causal masking and the 1/\sqrt{d} scaling, and decode from a language model with beam search, temperature or nucleus sampling.
• Estimate an alignment model for translation by EM, and compute BLEU, WER, Cohen’s kappa and pass@k by hand and in code.
• Derive the CTC loss and its forward recursion, and describe a modern speech synthesis pipeline from text to waveform.
• Design a retrieval-based or LLM-based dialogue system, and an agent loop with tools.
• Decide whether a claim of “human parity” is supported, with agreement statistics and a paired bootstrap test.

Official objectives and syllabus (2026–2027)

The course description on master-mva.com presents speech and natural language processing as a subfield of artificial intelligence used in a growing number of applications. The course promises an overview and details of the techniques and tasks of the automatic processing of text and speech.

It names some history of the field, the representation of textual and speech data, language modelling, machine translation, sentiment analysis and other labelling tasks, chatbots, and speech synthesis and recognition. Its aim is to give the key principles, algorithms and mathematics behind the state of the art, and to confront them with the reality of processing real data.

The description announces 9 three-hour slots, each with a lecture of about two hours followed by a quiz and questions. It lists twelve topics, recommends the textbook of Jurafsky and Martin, links a course repository (github.com/rbawden/MVA_2026_SNLP), and states that the instructors will provide readings for each session. The Université Paris-Saclay course detail gives the volume (21 h of lectures) and the type of assessment, with no programme of its own.

Every official topic is taught on this page. The extensions beyond the syllabus are the review of ch. 0, the complements of ch. 13 (Kneser–Ney smoothing, the derivation of Baum–Welch, the RNN transducer, the closed form behind DPO) and the research directions of ch. 14.

Where this course fits in the programme

Official prerequisites: basic linear algebra, calculus, probability theory, and basic machine and deep learning. Ch. 0 reviews the probability, information theory and signal processing that the page uses.

• Refreshers — Probability and Statistics (conditional probability, expectations, maximum likelihood), Linear Algebra, Analysis and Optimization (SVD, gradients, Lagrange multipliers) and Scientific Python, NumPy and PyTorch (every code block).
• Semester 1 courses that prepare it — Deep Learning (backpropagation, RNNs, attention), Introduction to Probabilistic Graphical Models and Deep Generative Models (EM and hidden Markov models), Advanced Learning for Text and Graph Data (word embeddings, transformers, pretraining), Foundations of Large Language Models (training and serving LLMs), Machine Learning for Time Series (spectral analysis) and Introduction to Statistical Learning.
• Related courses of semester 2 — Large Language Models for Code and Proof (code generation and agents in depth), Audio Signal Processing: Time–Frequency Analysis and Audio Signal Analysis, Indexing and Transformations (the signal side of ch. 2), Graphical Models: Discrete Inference and Learning (inference in chains and beyond), Reinforcement Learning (preference optimisation), Training and Deploying Large-Scale Models, Multimodal Explainable AI and Responsible Machine Learning.
• After the course — the Research Internship, for which the project of this course is a rehearsal: read a paper, rerun its code, test a new question.

Course outline

• 0. Review — chain rule of probability, entropy and cross-entropy, the softmax gradient, dynamic programming over semirings, the discrete Fourier transform.
• 1. Text as data — a short history of the field, tokens and Zipf’s law, byte-pair encoding, n-gram language models, perplexity and smoothing.
• 2. Speech features — sampling, the source–filter model, the short-time Fourier transform, the mel filterbank, the cepstrum and MFCCs.
• 3. Hidden Markov models and finite-state modelling — weighted automata and transducers, the forward, Viterbi and Baum–Welch algorithms, HMM-based speech recognition.
• 4. Sequence labelling — part-of-speech tagging and named entities, the BIO encoding, linear-chain CRFs, neural taggers, span-level evaluation.
• 5. Word embeddings — the distributional hypothesis, PMI and SVD, skip-gram with negative sampling as matrix factorisation, subwords, analogies and bias.
• 6. Deep learning for NLP — recurrent networks and their gradients, LSTMs, attention, the transformer block.
• 7. Neural language modelling and LLMs — neural LMs, pretraining objectives, scaling laws, decoding, instruction tuning and preference optimisation.
• 8. Machine translation — from rules to IBM models, neural translation with beam search, BLEU and learned metrics.
• 9. Sentiment analysis — polarity and aspects, naive Bayes and logistic regression, negation and compositionality.
• 10. Speech recognition and synthesis — WER, CTC, encoder–decoders and self-supervised speech; text-to-speech pipelines and vocoders.
• 11. Chatbots, code generation and agents — from ELIZA to LLM assistants, retrieval-augmented generation, pass@k, tool-using agents.
• 12. Evaluation — agreement between humans, human-parity claims, significance testing, benchmark pitfalls.
• 13. Complements — Kneser–Ney smoothing, the derivation of Baum–Welch, the RNN transducer, the KL-regularised optimum behind DPO (self-study).
• 14. Research directions and open problems — spoken language models without text, efficient long-context architectures, multilingual and document-level translation, evaluation, affective interaction (self-study).

Session plan

21 h in class = 7 sessions of 3 h. The volume is the official one of the Université Paris-Saclay programme table: 21 h of lectures. master-mva.com announces 9 three-hour slots, each made of a lecture of about two hours followed by a 30-minute quiz and questions; the plan below fits the topics into 21 h and keeps, in the Practice column, a short exercise set in place of each quiz. This split, and the content of each session, is a proposal.

Level 1 = foundations, 2 = core models and algorithms, 3 = advanced and research-level material. The level never goes down from one session to the next.

Self-study, outside the 21 h (about 8 h in total): ch. 0 Review, before session 1 (≈ 2 h) · ch. 13 Complements: Kneser–Ney, Baum–Welch derivation, RNN transducer, DPO (≈ 3 h, with Ex. 18) · ch. 14 Research directions and open problems (≈ 3 h, with Ex. 19).

How to study this module

• Read ch. 0 before the first session; it is short, and every later chapter uses cross-entropy and dynamic programming.
• Follow one thread across the course: the same dynamic program computes an HMM likelihood (ch. 3), a CRF partition function (ch. 4), the CTC loss (ch. 10) and an edit distance (ch. 10). Rewrite it once in each semiring.
• After each session, do the exercises of its row, then run the code of the chapter and change one parameter; the printed numbers are quoted in the text, so you can check your environment.
• The code needs Python with NumPy, SciPy, scikit-learn and PyTorch (CPU); every block uses synthetic or hand-written data and runs in a few seconds. No download is needed.
• Keep a one-page sheet with the definitions of perplexity, BLEU, WER, span F1, kappa and pass@k: the quizzes test whether you can compute them quickly.
• Start the project early: pick a paper with code in week 2, as the official assessment requires a one-page plan before the results.

0. Review: probability, information, dynamic programming and the Fourier transform

Every chapter of the course manipulates probabilities of sequences, measures models by a cross-entropy, trains them through a softmax, and computes sums over exponentially many paths with a dynamic program. This review states these tools once, with proofs, and adds the discrete Fourier transform needed for speech in ch. 2.

0.1 Probabilities of sequences

A sentence is a sequence of tokens w_1, \dots, w_n drawn from a finite vocabulary V. Any joint law factorises by the chain rule: P(w_1, \dots, w_n) = \prod_{t=1}^{n} P(w_t \mid w_1, \dots, w_{t-1}).

The factorisation is exact; models differ by how they approximate each conditional. A Markov model of order k keeps only the last k tokens (ch. 1, ch. 3); a recurrent network or a transformer keeps a learned summary of the whole prefix (ch. 6, ch. 7).

Consequence: minimising the expected negative log-likelihood of a model q under the data law p is the same as minimising \mathrm{KL}(p \,\|\, q). This is why every model of the course is trained with a cross-entropy, and why no model can do better than the entropy of the source (Proposition 7.2).

0.2 Softmax and its gradient

The gradient is the difference between what the model predicts and what was observed. The same shape, “expected features minus observed features”, returns for conditional random fields in Theorem 4.4.

0.3 Dynamic programming over a semiring

Many quantities of the course are sums, over exponentially many paths, of products of local weights. They are computed in polynomial time because the sum distributes over the product.

0.4 The discrete Fourier transform

Ch. 2 uses this with a logarithm: a convolution becomes a product in frequency, and a sum after taking \log |\cdot|.

1. Text as data: a short history, tokenisation and n-gram language models

Before any model, text must be cut into units, and the units given probabilities. This chapter places the field in its history, defines subword tokens, and builds the oldest language model still used as a baseline: the smoothed n-gram, measured by perplexity.

1.1 A short history

The field alternated between hand-written rules and statistics learned from data.

• 1948–1966, rules and first statistics. Shannon generated English-like text from n-gram counts (1948). The 1954 Georgetown–IBM demonstration translated some sixty Russian sentences with a few rules; the 1966 ALPAC report judged translation disappointing.
• 1975–2010, statistics. Hidden Markov models took over speech recognition (ch. 3); the same noisy-channel view produced statistical translation at IBM (ch. 8).
• 2003–2017, neural models. A neural language model (2003), deep acoustic models (around 2012), word2vec (2013), attention (2015), the transformer (2017).
• 2018–today, pretraining at scale. One pretrained model became the starting point of every task, and instruction-tuned assistants appeared in 2022 (ch. 7).

1.2 Tokens and subwords

A token is an occurrence of a unit in a text; a type is a distinct unit. Word frequencies follow Zipf’s law: the r-th most frequent type has frequency roughly proportional to 1/r. Many types occur once, so any fixed word vocabulary meets unseen words at test time.

from collections import Counter

def learn_bpe(word_counts, n_merges):
    """Byte-pair encoding: repeatedly merge the most frequent adjacent pair of symbols."""
    vocab = {tuple(w) + ("</w>",): c for w, c in word_counts.items()}
    merges = []
    for _ in range(n_merges):
        pairs = Counter()
        for symbols, c in vocab.items():
            for pair in zip(symbols, symbols[1:]):
                pairs[pair] += c
        (a, b), freq = pairs.most_common(1)[0]        # ties: first pair seen
        merges.append((a + b, freq))
        new_vocab = {}
        for symbols, c in vocab.items():
            out, i = [], 0
            while i < len(symbols):
                if symbols[i:i + 2] == (a, b):
                    out.append(a + b); i += 2
                else:
                    out.append(symbols[i]); i += 1
            new_vocab[tuple(out)] = c
        vocab = new_vocab
    return merges, vocab

counts = {"low": 5, "lower": 2, "newest": 6, "widest": 3}
merges, vocab = learn_bpe(counts, 5)
print(merges)
for symbols, c in vocab.items():
    print(c, " ".join(symbols))

1.3 n-gram language models and perplexity

The maximum likelihood estimate gives probability zero, hence infinite perplexity, to any test text with an unseen bigram. Smoothing moves some mass to unseen events.

import math
from collections import Counter

train = ["<s> the cat sat on the mat </s>", "<s> the dog sat on the log </s>",
         "<s> the cat saw the dog </s>"]
test = ["<s> the dog sat on the mat </s>", "<s> the dog saw the cat </s>"]   # "dog saw" is unseen
tok = [s.split() for s in train]
V = sorted({w for s in tok for w in s} - {"<s>"})     # predicted vocabulary (|V| = 9)
uni = Counter(w for s in tok for w in s[1:])
big = Counter((u, w) for s in tok for u, w in zip(s, s[1:]))
ctx = Counter(u for s in tok for u in s[:-1])

def p_bigram(w, u, k):
    """Add-k smoothed bigram probability P(w | u)."""
    return (big[u, w] + k) / (ctx[u] + k * len(V))

def perplexity(sents, logp):
    lp, n = 0.0, 0
    for s in sents:
        w = s.split()
        for u, v in zip(w, w[1:]):
            lp += logp(v, u); n += 1
    return math.exp(-lp / n)

N = sum(uni.values())
print("unigram (MLE)   ", round(perplexity(test, lambda w, u: math.log(uni[w] / N)), 2))
mle = lambda w, u: math.log(big[u, w] / ctx[u]) if big[u, w] else -math.inf
print("bigram (MLE)    ", perplexity(test, mle))
for k in [1.0, 0.1, 0.01]:
    print(f"bigram add-{k:<5}", round(perplexity(test, lambda w, u: math.log(p_bigram(w, u, k))), 2))

2. Speech features and signal processing

A recogniser reads one feature vector every 10 ms, which keeps what distinguishes speech sounds and drops the rest, such as pitch. This chapter derives the classical pipeline, from sampling to MFCCs, from a model of speech production.

2.1 Sampling and the source–filter model

The phoneme is carried by h, the pitch by e. A good feature keeps the spectral envelope (h) and discards the harmonic fine structure (e).

2.2 The short-time Fourier transform

2.3 The mel filterbank

Pitch perception is roughly linear below 1 kHz and logarithmic above; the mel scale imitates it.

2.4 The cepstrum and MFCCs

import numpy as np
from scipy.fft import dct

sr = 16000
t = np.arange(sr // 2) / sr                         # 0.5 s of a synthetic vowel /a/
f0, formants = 120.0, np.array([700.0, 1220.0, 2600.0])
x = np.zeros_like(t)
for h in range(1, 60):                              # harmonics of f0 shaped by formants
    gain = np.exp(-0.5 * ((h * f0 - formants) / 100.0) ** 2) @ [1.0, 0.8, 0.3]
    x += gain * np.sin(2 * np.pi * h * f0 * t)
x += 0.01 * np.random.default_rng(0).normal(size=x.size)

def hz_to_mel(f): return 2595 * np.log10(1 + f / 700)
def mel_to_hz(m): return 700 * (10 ** (m / 2595) - 1)

def log_mel(x, sr, n_fft=512, win=400, hop=160, n_mels=40):
    x = np.append(x[0], x[1:] - 0.97 * x[:-1])                         # pre-emphasis
    n_frames = 1 + (len(x) - win) // hop
    frames = np.stack([x[i * hop: i * hop + win] for i in range(n_frames)]) * np.hamming(win)
    power = np.abs(np.fft.rfft(frames, n_fft)) ** 2 / n_fft           # (frames, 257)
    edges = mel_to_hz(np.linspace(0, hz_to_mel(sr / 2), n_mels + 2))   # triangle corners
    bins = np.fft.rfftfreq(n_fft, 1 / sr)
    fb = np.zeros((n_mels, bins.size))
    for m in range(n_mels):
        lo, c, hi = edges[m: m + 3]
        fb[m] = np.clip(np.minimum((bins - lo) / (c - lo), (hi - bins) / (hi - c)), 0, None)
    return np.log(power @ fb.T + 1e-10), edges[1:-1]

L, centres = log_mel(x, sr)
mfcc = dct(L, type=2, norm="ortho", axis=1)[:, :13]                    # keep 13 cepstra
print("log-mel", L.shape, "MFCC", mfcc.shape)
avg = L.mean(0)
peaks = [m for m in range(1, 39) if avg[m] > avg[m - 1] and avg[m] > avg[m + 1]]
print("peaks of the mel spectrum at", np.round(centres[peaks]).astype(int), "Hz")

3. Hidden Markov models and finite-state modelling

Speech frames are produced by a hidden sequence of sounds, and words by a hidden sequence of tags. Finite-state machines and hidden Markov models describe such hidden sequences; three dynamic programs make them usable: likelihood, best path and learning.

3.1 Weighted finite-state machines

A recogniser composes four transducers (Mohri, Pereira and Riley, 2002): HMM states to context-dependent phones (H), to phones (C), to words through the pronunciation lexicon (L), and the n-gram grammar of ch. 1 (G). Decoding searches the best path of H \circ C \circ L \circ G in the tropical semiring.

3.2 Hidden Markov models

import itertools
import numpy as np

pi = np.array([0.8, 0.2])                        # states: 0 = hot, 1 = cold
A = np.array([[0.6, 0.4], [0.5, 0.5]])           # A[i, j] = P(q_t = j | q_{t-1} = i)
B = np.array([[0.2, 0.4, 0.4], [0.5, 0.4, 0.1]]) # B[i, o] = P(o | i), o = 1, 2, 3 ice creams
obs = [2, 0, 2]                                  # observed 3, 1, 3 (0-based symbols)

def forward(obs):
    alpha = pi * B[:, obs[0]]
    for o in obs[1:]:
        alpha = (alpha @ A) * B[:, o]            # O(K^2) per step
    return alpha.sum()

def viterbi(obs):
    delta, back = np.log(pi * B[:, obs[0]]), []
    for o in obs[1:]:
        scores = delta[:, None] + np.log(A)      # scores[i, j]: best path ending i -> j
        back.append(scores.argmax(0))
        delta = scores.max(0) + np.log(B[:, o])
    path = [int(delta.argmax())]
    for bp in reversed(back):
        path.insert(0, int(bp[path[0]]))
    return path, np.exp(delta.max())

def joint(q, obs):
    p = pi[q[0]] * B[q[0], obs[0]]
    for t in range(1, len(obs)):
        p *= A[q[t - 1], q[t]] * B[q[t], obs[t]]
    return p

paths = list(itertools.product([0, 1], repeat=len(obs)))
print("P(O): forward", round(forward(obs), 6), " brute force", round(sum(joint(q, obs) for q in paths), 6))
best = max(paths, key=lambda q: joint(q, obs))
path, p = viterbi(obs)
print("Viterbi", path, round(p, 6), " brute force", list(best), round(joint(best, obs), 6))

3.3 Learning: the Baum–Welch algorithm

Without observed states, parameters are learned by EM. The backward variables \beta_t(i) = P(o_{t+1}, \dots, o_T \mid q_t = i) satisfy the mirror recursion \beta_t(i) = \sum_j A_{ij}\, b_j(o_{t+1})\, \beta_{t+1}(j), \qquad \beta_T(i) = 1 .

They give the posteriors of one state and of one transition: \gamma_t(i) = \frac{\alpha_t(i) \beta_t(i)}{P(O)}, \qquad \xi_t(i, j) = \frac{\alpha_t(i) A_{ij} b_j(o_{t+1}) \beta_{t+1}(j)}{P(O)} .

3.4 HMM-based speech recognition

The emissions were Gaussian mixtures over MFCCs until about 2010. Hybrid systems then used a neural network predicting the state posterior P(q \mid o_t), divided by the prior P(q) to give a scaled likelihood. Ch. 10 removes the HMM altogether.

4. Sequence labelling

Many tasks give one label per token: a part of speech, an entity type, a slot of a request. This chapter encodes spans as tags, replaces the HMM tagger by a discriminative conditional random field, and scores taggers by spans.

4.1 Tasks and the BIO encoding

Part-of-speech tagging assigns each word a category such as noun or verb (17 in the Universal Dependencies tag set). Named-entity recognition finds spans naming persons, organisations or locations; CoNLL-2003 (Tjong Kim Sang and De Meulder, 2003) uses four types.

An HMM tagger (ch. 3) must generate every word, so it cannot easily use overlapping clues such as capitalisation, suffixes or the next word.

4.2 Linear-chain conditional random fields

At the optimum, expected feature counts equal observed ones, as for logistic regression.

import itertools
import torch
torch.set_num_threads(1); torch.manual_seed(0)
T, K = 5, 3                                      # 5 tokens, tags {O, B, I}
E = torch.randn(T, K, requires_grad=True)        # emission scores psi_t(y_t) = w . f(x, t, y_t)
W = torch.randn(K, K)                            # transition scores between consecutive tags

def log_partition(E, W):
    """Forward algorithm in the log semiring: log of the sum over all K^T tag sequences."""
    a = E[0]
    for t in range(1, len(E)):
        a = torch.logsumexp(a[:, None] + W, dim=0) + E[t]
    return torch.logsumexp(a, dim=0)

def score(y):
    return E[torch.arange(T), y].sum() + W[y[:-1], y[1:]].sum()

logZ = log_partition(E, W)
seqs = torch.tensor(list(itertools.product(range(K), repeat=T)))     # 243 sequences
brute = torch.logsumexp(torch.stack([score(y) for y in seqs]), 0)
print("log Z forward", round(logZ.item(), 4), " brute force", round(brute.item(), 4))

logZ.backward()                                  # d log Z / d E[t, k] = P(y_t = k | x)
probs = torch.softmax(torch.stack([score(y) for y in seqs]).detach(), 0)
marg = torch.stack([probs[seqs[:, 2] == k].sum() for k in range(K)])
print("gradient at t=2", E.grad[2].numpy().round(4), " marginals", marg.numpy().round(4))

4.3 Neural taggers, a preview of ch. 6–7

A bidirectional LSTM (ch. 6) can produce the emission scores of a CRF layer (Lample and coauthors, 2016). With a pretrained transformer (ch. 7), a linear layer on each token’s representation often suffices; a word split into subwords takes the label of its first subword.

4.4 Evaluation by spans

5. Word embeddings

One-hot vectors make all words equally different. Embeddings place words in \mathbb{R}^d so that words used in similar contexts are close: “you shall know a word by the company it keeps” (Firth, 1957). This chapter builds them from counts, then shows that word2vec factorises the same counts.

5.1 Counting contexts

5.2 Low-rank factorisation

By the Eckart–Young theorem, U_d \Sigma_d V_d^\top is the best rank-d approximation of M in Frobenius norm: it keeps the dominant structure of the counts and averages away noise.

import numpy as np
rng = np.random.default_rng(0)
groups = {"animal": ["cat", "dog", "horse", "cow"], "food": ["bread", "apple", "rice", "cheese"],
          "vehicle": ["car", "bus", "truck", "bike"], "place": ["road", "street", "bridge", "lane"]}
templates = [["the", "animal", "eats", "the", "food"], ["a", "animal", "sleeps"],
             ["food", "is", "tasty"], ["the", "vehicle", "drives", "on", "the", "place"],
             ["a", "vehicle", "is", "fast"], ["the", "place", "is", "wide"]]
corpus = []
for _ in range(4000):                                    # sample sentences from templates
    tpl = templates[rng.integers(len(templates))]
    corpus += [groups[w][rng.integers(4)] if w in groups else w for w in tpl] + ["."]
vocab = sorted(set(corpus)); idx = {w: i for i, w in enumerate(vocab)}
C = np.zeros((len(vocab), len(vocab)))
for i, w in enumerate(corpus):                           # symmetric window of 2 words
    for j in range(max(0, i - 2), min(len(corpus), i + 3)):
        if j != i:
            C[idx[w], idx[corpus[j]]] += 1
pmi = np.log(C * C.sum() / (C.sum(1, keepdims=True) * C.sum(0, keepdims=True)) + 1e-12)
ppmi = np.maximum(pmi, 0)                                # positive PMI
U, S, _ = np.linalg.svd(ppmi)
emb = U[:, :8] * np.sqrt(S[:8])                          # 8-dimensional word vectors
emb /= np.linalg.norm(emb, axis=1, keepdims=True)
for w in ["cat", "bread", "car", "road"]:
    sims = emb @ emb[idx[w]]
    print(f"{w:6s}->", [vocab[k] for k in np.argsort(-sims) if vocab[k] != w][:3])

5.3 Skip-gram with negative sampling

import torch
torch.set_num_threads(1); torch.manual_seed(0)
Ct = torch.tensor(C, dtype=torch.float32)
D = Ct.sum(); k = 5                                     # k negative samples per positive pair
neg = k * Ct.sum(1, keepdim=True) * Ct.sum(0, keepdim=True) / D   # expected negatives
V, d = C.shape[0], C.shape[0]                           # full rank: d = |V|
Wv = (0.1 * torch.randn(V, d)).requires_grad_(); Cv = (0.1 * torch.randn(V, d)).requires_grad_()
opt = torch.optim.Adam([Wv, Cv], lr=0.05)
for step in range(3000):                                # SGNS objective summed over the corpus
    s = Wv @ Cv.T
    loss = -(Ct * torch.nn.functional.logsigmoid(s) + neg * torch.nn.functional.logsigmoid(-s)).sum() / D
    opt.zero_grad(); loss.backward(); opt.step()
s = (Wv @ Cv.T).detach().numpy()
mask = C >= 20                                          # pairs seen at least 20 times
gap = np.abs(s - (pmi - np.log(k)))[mask].max()
print("pairs:", mask.sum(), " max |w.u - (PMI - log k)| =", gap.round(3))

word2vec, GloVe and PPMI–SVD thus factorise the same statistics. GloVe (Pennington, Socher and Manning, 2014) fits \mathbf{w}^\top \mathbf{u} + b_w + b_u \approx \log c(w, u) by weighted least squares. fastText (Bojanowski and coauthors, 2017) sums the vectors of a word’s character n-grams, so it embeds unseen words.

5.4 Analogies, limits and bias

Differences of vectors encode some relations (Mikolov, Yih and Zweig, 2013). The nearest word to \mathbf{w}_{\text{king}} - \mathbf{w}_{\text{man}} + \mathbf{w}_{\text{woman}} is often “queen”, once the three query words are excluded. The same arithmetic reproduces stereotypes of the training text, for instance between gender and occupations (Bolukbasi and coauthors, 2016). A static embedding also gives one vector per type, whatever its sense; contextual representations (ch. 7) fix this.

6. Deep learning for NLP: recurrent networks, attention and transformers

An n-gram model forgets everything beyond a few tokens; neural sequence models keep a learned summary of the prefix. This chapter presents the two answers, recurrence and attention, and why the second won.

6.1 Recurrent networks and their gradients

When \|W\| > 1 the product can explode instead, and gradients are clipped (Pascanu, Mikolov and Bengio, 2013).

Along the direct path through the cell, the Jacobian \partial c_t / \partial c_{t-1} is \mathrm{diag}(f_t), with no weight matrix: when f_t stays close to 1, the error signal crosses many steps intact.

6.2 Attention

An encoder–decoder encodes the source into states h_1, \dots, h_S and decodes the target token by token. A single vector cannot hold a long sentence; attention lets each decoding step look at all source states (Bahdanau, Cho and Bengio, 2015).

Unscaled scores of standard deviation \sqrt{d}, 16 for d = 256, saturate the softmax into a near one-hot vector with vanishing gradient; dividing by \sqrt{d} restores variance 1.

Order must be injected: the original transformer adds sinusoidal position vectors to the embeddings; rotary embeddings rotate queries and keys by angles proportional to the position (Su and coauthors, 2021).

6.3 The transformer block

A layer costs O(T^2 d + T d^2) but processes all positions in parallel, where an RNN needs T sequential steps; this made training on billions of tokens possible (ch. 7).

import torch
torch.set_num_threads(1); torch.manual_seed(0)

def attention(Q, K, V, causal=False):
    """Scaled dot-product attention softmax(Q K^T / sqrt(d)) V, optionally causal."""
    S = Q @ K.transpose(-2, -1) / K.shape[-1] ** 0.5
    if causal:
        T = S.shape[-1]
        S = S.masked_fill(torch.triu(torch.ones(T, T, dtype=torch.bool), 1), float("-inf"))
    return torch.softmax(S, dim=-1) @ V

T, d = 6, 64
X = torch.randn(T, d)
Wq, Wk, Wv = (torch.randn(d, d) / d ** 0.5 for _ in range(3))
Y = attention(X @ Wq, X @ Wk, X @ Wv, causal=True)
X2 = X.clone(); X2[4:] = torch.randn(2, d)              # change the last two tokens
Y2 = attention(X2 @ Wq, X2 @ Wk, X2 @ Wv, causal=True)
print("causal: outputs 0-3 unchanged:", torch.allclose(Y[:4], Y2[:4]), "| output 4 changed:", not torch.allclose(Y[4], Y2[4]))
P = torch.randperm(T)                                   # no positions: permutation equivariance
Z, Zp = attention(X @ Wq, X @ Wk, X @ Wv), attention(X[P] @ Wq, X[P] @ Wk, X[P] @ Wv)
print("equivariant:", torch.allclose(Z[P], Zp, atol=1e-6))
for dk in [16, 256]:                                    # why divide by sqrt(d)
    q, k = torch.randn(10000, dk), torch.randn(10000, dk)
    print(f"d = {dk:3d}: var(q.k) = {(q * k).sum(1).var():.1f}, after scaling = {((q * k).sum(1) / dk ** 0.5).var():.2f}")

7. Neural language modelling and large language models

Predicting the next token well requires syntax, facts and some reasoning. This chapter replaces count tables by neural networks, states the limit no model can beat, and follows the path from pretraining to an assistant.

7.1 Neural language models

Shared embeddings generalise: having seen “the cat sat”, the model favours “the dog sat”, since the two animals have close vectors.

import numpy as np
import torch
torch.set_num_threads(1); torch.manual_seed(0); rng = np.random.default_rng(0)
V, N = 8, 30000                                          # a source of order 2 over 8 symbols
P = rng.dirichlet(0.3 * np.ones(V), size=(V, V))         # P[a, b] = law of x_t given (a, b)
u = rng.random(N); x = [0, 1]
for t in range(N):                                       # inverse-CDF sampling
    x.append(min(int(np.searchsorted(P[x[-2], x[-1]].cumsum(), u[t])), V - 1))
x = torch.tensor(x)
train, test = x[:25000], x[25000:]
true_nll = -np.log(P[test[:-2], test[1:-1], test[2:]]).mean()
print(f"true source: test perplexity {np.exp(true_nll):.3f}")

class MLPLM(torch.nn.Module):                            # Bengio-style neural n-gram model
    def __init__(self, n, d=16, h=64):
        super().__init__()
        self.emb = torch.nn.Embedding(V, d)
        self.mlp = torch.nn.Sequential(torch.nn.Linear(n * d, h), torch.nn.Tanh(), torch.nn.Linear(h, V))
    def forward(self, ctx):                              # ctx: (batch, n) previous symbols
        return self.mlp(self.emb(ctx).flatten(1))

for n in [1, 2]:
    model = MLPLM(n); opt = torch.optim.Adam(model.parameters(), lr=1e-2)
    windows = lambda s: torch.stack([s[i: len(s) - n + i] for i in range(n)], 1)
    for epoch in range(200):                             # full-batch training
        loss = torch.nn.functional.cross_entropy(model(windows(train)), train[n:])
        opt.zero_grad(); loss.backward(); opt.step()
    with torch.no_grad():
        ce = torch.nn.functional.cross_entropy(model(windows(test)), test[n:])
    print(f"context of {n} symbol(s): test perplexity {ce.exp():.3f}")

7.2 Pretraining

The resulting vectors are contextual: “bank” differs in “river bank” and “bank loan”, unlike in ch. 5.

Under a budget C, the optimal N and D grow as powers of C with similar exponents (Exercise 16), about 20 tokens per parameter: Chinchilla (70 billion parameters, 1.4 trillion tokens) beat larger models trained on less data.

7.3 Decoding

Greedy and beam search (ch. 8) give bland, repetitive open-ended text; nucleus sampling adapts the number of candidates to the model’s confidence.

import numpy as np
rng = np.random.default_rng(0)
logits = np.array([3.0, 2.5, 2.0, 1.0, 0.5, 0.0, -1.0, -2.0])   # scores of 8 next tokens

def softmax(z, T=1.0):
    e = np.exp((z - z.max()) / T); return e / e.sum()

def nucleus(p, top_p=0.9):
    """Smallest set of most probable tokens whose mass reaches top_p, renormalised."""
    order = np.argsort(-p)
    keep = order[: np.searchsorted(np.cumsum(p[order]), top_p) + 1]
    q = np.zeros_like(p); q[keep] = p[keep]
    return q / q.sum()

for T in [0.5, 1.0, 2.0]:
    p = softmax(logits, T)
    H = -(p * np.log(p)).sum()
    print(f"T = {T}: entropy {H:.2f} nats, top-0.9 nucleus keeps {np.count_nonzero(nucleus(p))} tokens")
print("one nucleus sample at T = 1:", rng.choice(8, p=nucleus(softmax(logits))))

7.4 From a language model to an assistant

A pretrained model continues text; an assistant follows instructions. Supervised fine-tuning on demonstrations comes first. Then reinforcement learning from human feedback (RLHF, Ouyang and coauthors, 2022) fits a reward model to human comparisons of answers and maximises it while staying close to the fine-tuned model; DPO (Rafailov and coauthors, 2023) reaches the same optimum by a logistic loss on the pairs (ch. 13, 13.4).

8. Machine translation

Translation was the first application of the field and remains its benchmark. This chapter follows its three paradigms, rules, alignment models learned by EM and neural encoder–decoders, then the metrics that decided between them.

8.1 From rules to statistics

Rule-based systems, from the 1954 Georgetown–IBM demonstration on, combined bilingual dictionaries with hand-written transfer rules. Statistical translation (Brown and coauthors, 1993) learned from parallel text, with the noisy channel \hat e = \arg\max_e P(f \mid e) P(e) for a foreign sentence f. Phrase-based systems (Koehn, Och and Marcu, 2003) dominated until about 2016.

8.2 Word alignment with IBM Model 1

The log-likelihood, a sum of logarithms of linear functions of t, is concave: every local maximum is global.

from collections import defaultdict

pairs = [("das Haus", "the house"), ("das Buch", "the book"), ("ein Buch", "a book")]
pairs = [(f.split(), e.split()) for f, e in pairs]
E = {e for _, es in pairs for e in es}
t = defaultdict(lambda: 1.0 / len(E))                   # t[e, f] = P(e | f), uniform start
for it in range(1, 21):                                 # EM for IBM Model 1
    count, total = defaultdict(float), defaultdict(float)
    for fs, es in pairs:
        for e in es:
            z = sum(t[e, f] for f in fs)                # E-step: P(a_j = i | e, f)
            for f in fs:
                count[e, f] += t[e, f] / z; total[f] += t[e, f] / z
    for (e, f) in count:                                # M-step: renormalise expected counts
        t[e, f] = count[e, f] / total[f]
    if it in (1, 2, 5, 20):
        print(f"iteration {it:2d}: t(house|Haus) = {t['house', 'Haus']:.3f}, "
              f"t(the|das) = {t['the', 'das']:.3f}, t(book|ein) = {t['book', 'ein']:.3f}")

8.3 Neural machine translation

A neural system is an attention encoder–decoder (ch. 6) trained to maximise \sum_j \log P_\theta(e_j \mid e_{<j}, f), with the reference prefix fed to the decoder (teacher forcing). Subwords (ch. 1) handle rare words; back-translating monolingual target text adds synthetic pairs (Sennrich, Haddow and Birch, 2016b).

8.4 Evaluation

import math
from collections import Counter

def ngrams(words, n):
    return Counter(tuple(words[i: i + n]) for i in range(len(words) - n + 1))

def bleu(hyps, refs, N=4):
    """Corpus BLEU (Papineni et al., 2002): clipped n-gram precisions, brevity penalty."""
    match, total, h_len, r_len = [0] * N, [0] * N, 0, 0
    for h, r in zip(hyps, refs):
        h, r = h.split(), r.split()
        h_len += len(h); r_len += len(r)
        for n in range(1, N + 1):
            hn, rn = ngrams(h, n), ngrams(r, n)
            match[n - 1] += sum(min(c, rn[g]) for g, c in hn.items())   # clipping
            total[n - 1] += max(len(h) - n + 1, 0)
    prec = [m / t for m, t in zip(match, total)]
    bp = 1.0 if h_len > r_len else math.exp(1 - r_len / h_len)
    score = bp * math.exp(sum(math.log(p) for p in prec) / N) if min(prec) > 0 else 0.0
    return score, prec, bp

print(bleu(["the the the the the the the"], ["the cat is on the mat"], N=1))
refs = ["the cat is on the mat", "there is a book on the table"]
hyps = ["the cat sat on the mat", "there is a book on a table"]
score, prec, bp = bleu(hyps, refs)
print("BLEU =", round(100 * score, 1), " precisions", [round(p, 3) for p in prec], " BP", round(bp, 3))

BLEU rewards surface overlap: it misses paraphrases and depends on tokenisation, hence fixed tools such as sacreBLEU (Post, 2018). chrF compares character n-grams; COMET (Rei and coauthors, 2020) is a network trained to predict human judgements, and agrees better with them.

9. Sentiment analysis

Is this review positive? Is the customer annoyed with the battery or the screen? This chapter defines the sentiment tasks, shows that the classic baseline is a linear model, and locates where it breaks: negation and composition.

9.1 Tasks

Benchmarks include movie reviews (Pang, Lee and Vaithyanathan, 2002) and the Stanford Sentiment Treebank, labelled on every phrase of a parse tree (Socher and coauthors, 2013).

9.2 Linear baselines

Logistic regression fits the same linear form discriminatively. Both give each word a fixed weight, whatever its neighbours: exactly what negation violates.

import re
import numpy as np
from sklearn.feature_extraction.text import CountVectorizer
from sklearn.linear_model import LogisticRegression
from sklearn.naive_bayes import MultinomialNB
rng = np.random.default_rng(0)
pos, neg = ["good", "great", "excellent", "fun"], ["bad", "boring", "awful", "dull"]
subj, filler = ["the film", "the plot", "the acting", "this movie"], ["really", "quite", "honestly", ""]
docs, y = [], []
for _ in range(2000):                                   # synthetic reviews with negation
    label, negated = rng.integers(2), rng.random() < 0.4
    adj = (pos if label != negated else neg)[rng.integers(4)]
    docs.append(f"{subj[rng.integers(4)]} was {'not ' if negated else ''}{filler[rng.integers(4)]} {adj}")
    y.append(int(label))
y = np.array(y)
y_noisy = np.where(rng.random(len(y)) < 0.05, 1 - y, y)  # 5 % annotation noise

def mark_negation(s):
    """Prefix NOT_ to every word after 'not', as in Pang et al. (2002)."""
    return re.sub(r"\bnot\s+(.*)$", lambda m: " ".join("NOT_" + w for w in m.group(1).split()), s)

tr, te = slice(0, 1500), slice(1500, 2000)
for name, prep, ngram in [("unigrams", None, (1, 1)), ("uni+bigrams", None, (1, 2)),
                          ("NOT_ marking", mark_negation, (1, 1))]:
    vec = CountVectorizer(preprocessor=prep, ngram_range=ngram, token_pattern=r"\S+")
    Xtr, Xte = vec.fit_transform(docs[tr]), vec.transform(docs[te])
    accs = [m.fit(Xtr, y_noisy[tr]).score(Xte, y[te]) for m in (MultinomialNB(), LogisticRegression(max_iter=1000))]
    print(f"{name:13s} naive Bayes {accs[0]:.3f}   logistic regression {accs[1]:.3f}")

9.3 Composition and neural models

Real negation has a scope (“not only good but great”), and contrast and irony change polarity in ways no fixed list captures. Recursive networks over parse trees targeted this composition (Socher and coauthors, 2013); today a fine-tuned pretrained transformer (ch. 7) learns it from data. In dialogue, prosody and the partner’s turns matter too (ch. 14).

10. Speech recognition and speech synthesis

Ch. 3 recognised speech with HMMs, a lexicon and a grammar. Modern recognisers map frames to characters with one network trained end to end, and synthesisers run the other way. This chapter gives the loss that made end-to-end recognition possible, then the synthesis pipeline.

10.1 Measuring recognition

import numpy as np

def wer(ref, hyp):
    """Word error rate (S + D + I) / N from the Levenshtein alignment of word sequences."""
    r, h = ref.split(), hyp.split()
    D = np.zeros((len(r) + 1, len(h) + 1), dtype=int)
    D[:, 0], D[0, :] = np.arange(len(r) + 1), np.arange(len(h) + 1)
    for i in range(1, len(r) + 1):
        for j in range(1, len(h) + 1):
            D[i, j] = min(D[i - 1, j - 1] + (r[i - 1] != h[j - 1]), D[i - 1, j] + 1, D[i, j - 1] + 1)
    i, j, ops = len(r), len(h), {"S": 0, "D": 0, "I": 0}
    while i > 0 or j > 0:                                 # backtrace to count error types
        if i > 0 and j > 0 and D[i, j] == D[i - 1, j - 1] + (r[i - 1] != h[j - 1]):
            ops["S"] += r[i - 1] != h[j - 1]; i, j = i - 1, j - 1
        elif i > 0 and D[i, j] == D[i - 1, j] + 1:
            ops["D"] += 1; i -= 1
        else:
            ops["I"] += 1; j -= 1
    return round(D[-1, -1] / len(r), 3), ops

print(*wer("i want to recognise speech today", "i want to wreck a nice beach today"))
print(*wer("the cat sat", "the cat sat down on the mat"))   # insertions only: WER above 100 %

10.2 Connectionist temporal classification

Nobody annotates which frame belongs to which character; CTC (Graves and coauthors, 2006) sums over all alignments.

import itertools
import torch
torch.set_num_threads(1); torch.manual_seed(0)
T, C = 6, 4                                              # 6 frames; symbols: blank=0, a=1, b=2, c=3
logp = torch.randn(T, C).log_softmax(-1)                 # frame-wise log-probabilities
y = [1, 2, 2]                                            # target "a b b" (repeated b needs a blank)

def ctc_forward(logp, y, blank=0):
    """CTC forward algorithm on the extended label sequence  _ y1 _ y2 _ ... _ yU _."""
    z = [blank]
    for s in y:
        z += [s, blank]
    S = len(z)
    alpha = torch.full((S,), float("-inf"))
    alpha[0], alpha[1] = logp[0, z[0]], logp[0, z[1]]
    for t in range(1, len(logp)):
        prev = alpha.clone()
        for s in range(S):
            cands = [prev[s]] + ([prev[s - 1]] if s >= 1 else [])
            if s >= 2 and z[s] != blank and z[s] != z[s - 2]:
                cands.append(prev[s - 2])                # skip a blank between different labels
            alpha[s] = torch.logsumexp(torch.stack(cands), 0) + logp[t, z[s]]
    return -torch.logsumexp(alpha[-2:], 0)               # end on the last label or final blank

def collapse(path, blank=0):
    out = [k for i, k in enumerate(path) if i == 0 or k != path[i - 1]]
    return [k for k in out if k != blank]

brute = -torch.logsumexp(torch.stack([logp[range(T), list(p)].sum() for p in
                         itertools.product(range(C), repeat=T) if collapse(list(p)) == y]), 0)
ref = torch.nn.functional.ctc_loss(logp[:, None], torch.tensor([y]), [T], [len(y)], reduction="sum")
print(f"forward {ctc_forward(logp, y):.4f}   brute force over 4^6 paths {brute:.4f}   torch {ref:.4f}")

CTC assumes frame outputs independent given the input; it is decoded greedily (best symbol per frame, then \mathcal{B}) or with a beam and an LM. Attention encoder–decoders (Chan and coauthors, 2016) and the RNN transducer (ch. 13, 13.3) drop this assumption.

10.3 Self-supervised and weakly supervised speech

wav2vec 2.0 (Baevski and coauthors, 2020) masks latent frames computed from the waveform and learns, contrastively, to identify the quantised latent of each; fine-tuned with CTC, it works with ten minutes of transcribed audio. HuBERT (Hsu and coauthors, 2021) predicts k-means labels of masked frames. Whisper (Radford and coauthors, 2023) trains an encoder–decoder on 680,000 hours of weakly supervised audio.

10.4 Speech synthesis

Text-to-speech runs four stages: text normalisation (“Dr.” to “doctor”), grapheme-to-phoneme conversion, an acoustic model with durations and pitch, and a vocoder producing the waveform. Neural systems replaced concatenation of recorded units and HMM-based synthesis.

Listeners judge synthesis on a 1-to-5 scale, the mean opinion score (MOS), since no automatic metric captures naturalness well (ch. 12). Spoken language models without text are in ch. 14.

11. Chatbots, code generation and agents

A chatbot keeps a conversation going, a code generator writes programs that run, an agent acts over many steps. This chapter goes from pattern matching to LLM-based systems.

11.1 From ELIZA to task-oriented dialogue

ELIZA (Weizenbaum, 1966) matched keywords and rewrote the user’s sentence (“I feel sad” gives “Why do you feel sad?”) with no model of meaning; users still confided in it. Task-oriented systems, which book a train or a table, are modular.

from sklearn.feature_extraction.text import TfidfVectorizer
from sklearn.metrics.pairwise import cosine_similarity

faq = {"How do I reset my password?": "Use the 'forgot password' link on the login page.",
       "When is the library open?": "From 9 am to 8 pm, Monday to Saturday.",
       "How can I book a meeting room?": "Rooms are booked on the intranet, up to two weeks ahead.",
       "Where do I submit the project report?": "Upload the PDF on the course page before the deadline."}
questions = list(faq)
vec = TfidfVectorizer(stop_words="english").fit(questions)

def respond(user_turn, threshold=0.2):
    """Retrieval-based chatbot: answer of the most similar stored question, or a fallback."""
    sims = cosine_similarity(vec.transform([user_turn]), vec.transform(questions))[0]
    best = sims.argmax()
    score = round(float(sims[best]), 2)
    return (faq[questions[best]] if score >= threshold else "Sorry, could you rephrase?"), score

for turn in ["I forgot my password", "is the library open on sunday", "what is the meaning of life"]:
    print(turn, "->", respond(turn))

11.2 LLM-based chatbots and retrieval

An LLM assistant (ch. 7) conditions on the whole conversation, marked with roles (system, user, assistant). It answers any request fluently, but can state false facts with confidence: hallucination.

11.3 Code generation

Code can be executed, so it is judged by passing unit tests. HumanEval (Chen and coauthors, 2021) has 164 hand-written Python problems with tests.

import numpy as np
from math import comb
rng = np.random.default_rng(0)

def pass_at_k(n, c, k):
    """Unbiased estimator of pass@k from n samples with c correct (Chen et al., 2021)."""
    return 1.0 if n - c < k else 1.0 - comb(n - c, k) / comb(n, k)

p_true, n, k = 0.1, 20, 5                                # each sample passes the tests w.p. 0.1
target = 1 - (1 - p_true) ** k                           # true pass@5
c = rng.binomial(n, p_true, size=20000)                  # 20,000 problems, n samples each
unbiased = np.mean([pass_at_k(n, ci, k) for ci in c])
plug_in = np.mean(1 - (1 - c / n) ** k)                  # naive plug-in estimator
print(f"true pass@5 {target:.4f}   unbiased {unbiased:.4f}   plug-in {plug_in:.4f}")

11.4 Agents

Hence agents check their work (run tests, read errors, retry), and benchmarks such as SWE-bench (Jimenez and coauthors, 2024), built from real GitHub issues, score whole tasks. Large Language Models for Code and Proof goes further.

12. Evaluation: comparing human and machine performance

Every chapter ended with a metric. This one asks when a difference between two systems, or between a system and humans, is real: it measures human agreement, tests significance, and lists how scores mislead.

12.1 Human agreement as a reference

A perfect system scores only 1 - \varepsilon. Matching the agreement between two humans is the natural definition of “human parity”, but it hides which errors each makes.

12.2 Is the difference significant?

import numpy as np
from sklearn.metrics import cohen_kappa_score
rng = np.random.default_rng(0)

n = 500                                                  # 500 items, 3 sentiment classes
gold = rng.choice(3, size=n, p=[0.5, 0.3, 0.2])
def annotate(acc):                                       # keep the label w.p. acc, else random
    return np.where(rng.random(n) < acc, gold, rng.choice(3, size=n))
ann1, ann2, sys_a, sys_b = annotate(0.85), annotate(0.85), annotate(0.80), annotate(0.76)

p_o = np.mean(ann1 == ann2)                              # observed agreement
p_e = sum(np.mean(ann1 == k) * np.mean(ann2 == k) for k in range(3))   # chance agreement
print(f"annotators: agreement {p_o:.3f}, kappa {(p_o - p_e) / (1 - p_e):.3f} "
      f"(sklearn {cohen_kappa_score(ann1, ann2):.3f})")

ref = ann1                                               # evaluate systems against one annotator
acc_a, acc_b = np.mean(sys_a == ref), np.mean(sys_b == ref)
delta = acc_a - acc_b
idx = rng.integers(0, n, size=(10000, n))                # paired bootstrap (Koehn, 2004)
deltas = (sys_a[idx] == ref[idx]).mean(1) - (sys_b[idx] == ref[idx]).mean(1)
print(f"accuracy vs annotator 1: A {acc_a:.3f}, B {acc_b:.3f}, annotator 2 {np.mean(ann2 == ref):.3f}")
print(f"delta {delta:.3f}, 95% bootstrap interval [{np.quantile(deltas, 0.025):.3f}, {np.quantile(deltas, 0.975):.3f}], "
      f"share of resamples with delta <= 0: {np.mean(deltas <= 0):.3f}")

12.3 How benchmark scores mislead

• Artefacts. A classifier that reads only the hypothesis of SNLI pairs, never the premise, predicts the label for about 67 % of them (Gururangan and coauthors, 2018).
• Saturation and contamination. Benchmarks are solved within years, and public test sets leak into pretraining data; dynamic benchmarks collected with models in the loop respond (Kiela and coauthors, 2021).
• Automatic judges. An LLM grader agrees well with human preferences but favours the first position, longer answers and its own outputs (Zheng and coauthors, 2023).
• Human evaluation. MOS (ch. 10) and translation assessments need trained raters, randomised order and enough items for confidence intervals.

13. Complements for self-study

This chapter completes four topics of the course with material that does not fit the 21 hours: a better smoothing method, the derivation of Baum–Welch, the RNN transducer, and the closed form behind DPO. Each section can be read after the chapter it extends.

13.1 Kneser–Ney smoothing (extends ch. 1)

Add-k smoothing gives the same share to every unseen word. Kneser and Ney (1995) observed that the backup distribution should favour words that appear after many different contexts: “Francisco” is frequent, but almost always after “San”, so it is a poor guess after a new context.

import math
from collections import Counter

train = ["<s> the cat sat on the mat </s>", "<s> the dog sat on the log </s>",
         "<s> the cat saw the dog </s>"]
test = ["<s> the dog sat on the mat </s>", "<s> the dog saw the cat </s>"]
tok = [s.split() for s in train]
big = Counter((u, w) for s in tok for u, w in zip(s, s[1:]))
ctx = Counter(u for s in tok for u in s[:-1])
followers = Counter(u for (u, w) in big)                 # N1+(u .): distinct words after u
preceders = Counter(w for (u, w) in big)                 # N1+(. w): distinct words before w
n_types = len(big)                                       # N1+(. .): distinct bigram types

def p_kn(w, u, d=0.75):
    """Interpolated Kneser-Ney bigram probability."""
    p_cont = preceders[w] / n_types                      # continuation probability
    lam = d * followers[u] / ctx[u]                      # mass freed by discounting
    return max(big[u, w] - d, 0) / ctx[u] + lam * p_cont

V = sorted({w for s in tok for w in s} - {"<s>"})
print("sums to one:", all(abs(sum(p_kn(w, u) for w in V) - 1) < 1e-12 for u in ctx))
for d in [0.5, 0.75, 0.9]:
    lp = [math.log(p_kn(v, u, d)) for s in test for u, v in zip(s.split(), s.split()[1:])]
    print(f"Kneser-Ney d = {d}: perplexity {math.exp(-sum(lp) / len(lp)):.2f}")

13.2 Baum–Welch as expectation–maximisation (extends ch. 3)

Write \theta = (\pi, A, B) for the parameters and q for the hidden path. EM maximises at each step the expected complete log-likelihood Q(\theta', \theta) = \sum_{q} P(q \mid O; \theta) \log P(q, O; \theta') .

import numpy as np
rng = np.random.default_rng(0)
pi = np.array([0.8, 0.2]); A = np.array([[0.6, 0.4], [0.5, 0.5]])
B = np.array([[0.2, 0.4, 0.4], [0.5, 0.4, 0.1]])
q, obs = rng.choice(2, p=pi), []
for t in range(500):                                   # sample 500 observations
    obs.append(rng.choice(3, p=B[q])); q = rng.choice(2, p=A[q])
obs = np.array(obs)

def forward_backward(pi, A, B, obs):
    T, K = len(obs), len(pi)
    alpha, beta, c = np.zeros((T, K)), np.ones((T, K)), np.zeros(T)
    alpha[0] = pi * B[:, obs[0]]; c[0] = alpha[0].sum(); alpha[0] /= c[0]
    for t in range(1, T):                              # scaled forward pass
        alpha[t] = (alpha[t - 1] @ A) * B[:, obs[t]]; c[t] = alpha[t].sum(); alpha[t] /= c[t]
    for t in range(T - 2, -1, -1):                     # scaled backward pass
        beta[t] = A @ (B[:, obs[t + 1]] * beta[t + 1]) / c[t + 1]
    gamma = alpha * beta                               # P(q_t = i | O)
    xi = alpha[:-1, :, None] * A[None] * (B[:, obs[1:]].T * beta[1:])[:, None, :] / c[1:, None, None]
    return gamma, xi, np.log(c).sum()                  # log P(O) = sum_t log c_t

pi_h, A_h = np.array([0.5, 0.5]), np.array([[0.7, 0.3], [0.3, 0.7]])
B_h = np.array([[0.3, 0.3, 0.4], [0.4, 0.3, 0.3]])
for it in range(30):                                   # Baum-Welch = EM
    gamma, xi, ll = forward_backward(pi_h, A_h, B_h, obs)
    if it % 5 == 0:
        print(f"iteration {it:2d}  log P(O) = {ll:.3f}")
    pi_h = gamma[0]
    A_h = xi.sum(0) / xi.sum((0, 2))[:, None]
    B_h = np.stack([gamma[obs == o].sum(0) for o in range(3)], 1) / gamma.sum(0)[:, None]
print("true model: log P(O) =", round(forward_backward(pi, A, B, obs)[2], 3))
print("estimated B:\n", B_h.round(2))

13.3 The RNN transducer (extends ch. 10)

CTC predicts each frame independently of the labels already emitted. The RNN transducer (Graves, 2012) adds a prediction network over the previous labels, which acts as an internal language model.

import itertools
import numpy as np
rng = np.random.default_rng(0)
T, y, K = 4, [1, 2], 3                                   # 4 frames, target "a b", symbols: blank=0, a=1, b=2
U = len(y)
logits = rng.normal(size=(T, U + 1, K))                  # joint network output at lattice node (t, u)
logp = logits - np.log(np.exp(logits).sum(-1, keepdims=True))

alpha = np.full((T, U + 1), -np.inf); alpha[0, 0] = 0.0
for t in range(T):
    for u in range(U + 1):
        terms = []
        if t > 0: terms.append(alpha[t - 1, u] + logp[t - 1, u, 0])          # blank: next frame
        if u > 0: terms.append(alpha[t, u - 1] + logp[t, u - 1, y[u - 1]])   # label: next output
        if terms: alpha[t, u] = np.logaddexp.reduce(terms)
forward = alpha[T - 1, U] + logp[T - 1, U, 0]            # final blank

paths = []                                               # brute force: place U labels among T-1+U steps
for pos in itertools.combinations(range(T - 1 + U), U):
    t, u, lp = 0, 0, 0.0
    for step in range(T - 1 + U):
        if step in pos: lp += logp[t, u, y[u]]; u += 1
        else: lp += logp[t, u, 0]; t += 1
    paths.append(lp + logp[t, u, 0])
print(f"{len(paths)} paths; log P(y|x): forward {forward:.4f}, brute force {np.logaddexp.reduce(paths):.4f}")

13.4 The KL-regularised optimum and DPO (extends ch. 7)

RLHF trains a reward model r on human comparisons with the Bradley–Terry likelihood P(y_w \succ y_l \mid x) = \sigma\big(r(x, y_w) - r(x, y_l)\big), then optimises the policy against it.

Inverting the optimum gives the reward as a function of the policy: r(x, y) = \beta \log \frac{\pi^*(y \mid x)}{\pi_{\mathrm{ref}}(y \mid x)} + \beta \log Z(x) .

In the Bradley–Terry likelihood only the difference of two rewards for the same prompt appears, so Z(x) cancels. Fitting the policy directly to the preference pairs gives the DPO loss (Rafailov and coauthors, 2023):

No reward model and no sampling are needed: DPO is a logistic regression on pairs, whose “features” are log-probability ratios.

14. Research directions and open problems

This chapter is for self-study. It points to active lines of research that extend the course, each with a few papers to start from and the questions that remain open.

14.1 Spoken language models without text

Generative spoken language modelling (Lakhotia and coauthors, 2021) chains the pieces of ch. 10 without any text: self-supervised speech features (HuBERT or wav2vec 2.0), k-means discrete units, a transformer language model over the units (ch. 7), and a unit-to-speech synthesiser. The model continues a spoken prompt in speech.

• Work by Nguyen and coauthors (2023) extends the idea to two-channel conversations, where the model generates turn-taking, overlaps and laughter that a transcript would lose.
• Spirit LM (Nguyen and coauthors, 2024) interleaves speech units and text tokens in one model, to transfer knowledge from text to speech.
• Dupoux (2018) argues for reverse-engineering the infant language learner: children learn to speak from raw audio and interaction, with far less data than a text model, and the gap is a measurable scientific question.

Open problems: discrete units capture phonetic content well but prosody and meaning poorly; spoken models still lag far behind text models of the same size in coherence; and data efficiency is nowhere near that of children.

14.2 Long contexts and sub-quadratic architectures

Attention costs O(T^2) in the sequence length (ch. 6). Structured state-space models (Gu, Goel and Ré, 2022) and their selective variant Mamba (Gu and Dao, 2023) process sequences in linear time with a recurrent state. Hyena (Poli and coauthors, 2023) replaces attention by long implicit convolutions interleaved with gating.

Open problems: Jelassi and coauthors (2024) prove and observe that fixed-size recurrent states are worse than attention at copying long inputs, and hybrid models that mix attention and recurrent layers are an active compromise. Which tasks need full attention, and how much, is not settled.

14.3 Multilingual and document-level translation

Most of the world’s languages have little parallel text. Massively multilingual models such as NLLB (NLLB Team, 2022), covering 200 languages, and open multilingual LLMs such as BLOOM (BigScience Workshop, 2022) share parameters across languages so that low-resource ones benefit from high-resource ones.

Sentence-level systems ignore context. Bawden and coauthors (2018) built contrastive test sets for coreference and lexical cohesion across sentences: a model that sees only the current sentence scores at chance on them, and only some ways of feeding it the previous sentence help. Freitag and coauthors (2021) showed with expert MQM annotations that crowd ratings and BLEU can rank systems differently from professional translators.

Open problems: reliable evaluation for languages without references or expert raters; translation of whole documents with consistent terminology; measuring and reducing gender and cultural bias in outputs.

14.4 Affect and interaction

In conversation, opinions are spread over turns, carried by prosody as much as by words, and addressed to a partner. Clavel and Callejas (2016) review how sentiment analysis moved from opinion mining in product reviews to human–agent interaction, where a virtual agent must detect the user’s attitude in real time and respond to it.

Open problems: labels of social and emotional phenomena have low inter-annotator agreement (ch. 12), so the ceiling of supervised learning is low; multimodal models must align words, prosody and gestures in time; and an agent’s reaction changes the user’s next turn, which static datasets cannot capture.

14.5 Evaluation that keeps pace

As benchmarks saturate and leak into pretraining data, the field is moving to dynamic benchmarks (Kiela and coauthors, 2021), human preference arenas and LLM judges (Zheng and coauthors, 2023), and task-level evaluations of agents such as SWE-bench (Jimenez and coauthors, 2024).

Open problems: detecting contamination without access to the training data; calibrated LLM judges whose biases are measured and corrected; and comparisons with humans that specify which humans, with what training and time, as ch. 12 requires.

Exercises

The exercises are sorted by level: ★ applies the course, ★★ combines results or proves a short statement, ★★★ is open-ended or research-flavoured. Exercises 13, 18 and 19 are computational.

1. ★ Perplexity by hand. With the training corpus of Code 1.8 and add-one smoothing (|V| = 9), compute the six bigram probabilities of “<s> the dog saw the cat </s>” and the perplexity of the sentence.

   Solution: each probability is (c(u, w) + 1)/(c(u) + 9). In order, the six bigrams have probabilities \frac{4}{12}, \quad \frac{3}{15}, \quad \frac{1}{11}, \quad \frac{2}{10}, \quad \frac{3}{15}, \quad \frac{1}{11}, where “dog saw” and “cat </s>” are unseen.

   The log-probability is -10.72 over 6 predictions, so \mathrm{PP} = e^{10.72 / 6} \approx 5.97 .

2. ★ Frames, bins and mels. Telephone speech is sampled at 8 kHz. With 25 ms windows, a 10 ms hop and a DFT of size 256: how many samples per window, how many frames in 2 s, what is the bin spacing, and what is the mel value of the Nyquist frequency?

   Solution: 200 samples per window and 80 per hop; 1 + \lfloor (16000 - 200)/80 \rfloor = 198 frames; bins every 8000/256 = 31.25 Hz; the Nyquist frequency is 4000 Hz and \mathrm{mel}(4000) = 2595 \log_{10}(1 + 4000/700) \approx 2146 .

3. ★ Viterbi by hand. With the HMM of Code 3.6, observe 1, 3, 1 ice creams. Run the forward and Viterbi recursions and give P(O) and the best path.

   Solution: \alpha_1 = \delta_1 = (0.16, 0.10); \alpha_2 = (0.0584, 0.0114), \alpha_3 = (0.008148, 0.01453), so P(O) = 0.022678.

   For Viterbi, \delta_2 = (0.0384, 0.0064) and \delta_3 = (0.004608, 0.00768). The best path is hot, hot, cold, with probability 0.00768, confirmed by enumerating the 8 paths.

4. ★ BIO tags and span F1. In “The University of Paris-Saclay hired Ada Lovelace in Orsay .” the gold entities are an organisation (“University of Paris-Saclay”), a person and a location. A tagger outputs O B-ORG I-ORG O O B-PER I-PER O B-LOC O. Write the gold tags, and compute token accuracy and span F1.

   Solution: gold O B-ORG I-ORG I-ORG O B-PER I-PER O B-LOC O. One token differs, so the accuracy is 90 %. The predicted organisation “University of” has the wrong boundary: 2 correct spans out of 3 predicted and 3 gold, so P = R = F_1 = 2/3.

5. ★ BLEU by hand. Compute BLEU with N = 2 for the hypothesis “the cat the cat on the mat” against the reference “the cat is on the mat”.

   Solution: clipped unigram matches: “the” 2 (not 3), “cat” 1 (not 2), “on” 1, “mat” 1, so p_1 = 5/7. Bigram matches: “the cat” once, “on the”, “the mat”, so p_2 = 3/6. The hypothesis is longer than the reference, so BP = 1 and \mathrm{BLEU}_2 = \sqrt{5/7 \cdot 1/2} \approx 0.598 .

6. ★ CTC paths and WER. (a) With the blank written “-”, list the paths of length 3 that CTC collapses to “ab”, then those that collapse to “aa”. (b) Compute the WER of “a meeting starts noon today” against “the meeting starts at noon”.

   Solution: (a) -ab, a-b, ab-, aab, abb: five paths. For “aa” only a-a works, since the repeated label needs a blank.

   2. An optimal alignment has one substitution (the → a), one deletion (at) and one insertion (today), on 5 reference words: WER = 3/5 = 60 %.

7. ★ Cohen’s kappa. Two annotators label 100 reviews. Both say positive 40 times, both negative 30 times; A says positive and B negative 20 times, the reverse 10 times. Compute p_o, p_e and \kappa.

   Solution: p_o = 0.70. A says positive 60 % of the time and B 50 %, so p_e = 0.6 \cdot 0.5 + 0.4 \cdot 0.5 = 0.50, and \kappa = \frac{0.70 - 0.50}{1 - 0.50} = 0.40 .

8. ★★ Forward–backward identities. For an HMM, prove that \sum_i \alpha_t(i)\, \beta_t(i) = P(O) for every t, and deduce the formula of \gamma_t(i) in ch. 3. Then show that the Viterbi recursion is the forward recursion in the max-product semiring.

   Solution: by the Markov property, given q_t = i the future observations are independent of the past ones and of o_t. Hence \alpha_t(i)\, \beta_t(i) = P(o_{1:t}, q_t = i)\, P(o_{t+1:T} \mid q_t = i) = P(O, q_t = i) .

   Summing over i gives P(O), and dividing by P(O) gives \gamma_t(i) = P(q_t = i \mid O). Replacing sums by maxima in the proof of Theorem 3.4 is legitimate because \max distributes over products of non-negative numbers (Definition 0.5).

9. ★★ A CRF without transitions. Show that a linear-chain CRF whose features depend only on (y_t, x, t), not on y_{t-1}, factorises into independent softmax classifiers, one per token. What does Theorem 4.4 become?

   Solution: the exponent is a sum of terms \theta^\top f(y_t, x, t), so the numerator is a product over t and Z(x), a sum over all sequences, is the product of the per-token normalisers (distributivity). Hence p(y \mid x) = \prod_t \mathrm{softmax}_{y_t}. The gradient becomes, token by token, observed minus expected features: the gradient of multinomial logistic regression (Proposition 0.4). Transitions are what make the CRF more than a per-token classifier.

10. ★★ SGNS at the optimum. A pair is seen c(w, u) = 30 times, with c(w) = 300, c(u) = 1000, D = 10^6 and k = 5 negatives. (a) What inner product does Theorem 5.5 predict? (b) What happens to pairs never seen together, and how does PPMI handle the same issue?

    Solution: (a) The PMI is \log \frac{30 \cdot 10^6}{300 \cdot 1000} = \log 100 \approx 4.61, so the optimal inner product is 4.61 - \log 5 \approx 3.00.

    2. With c(w, u) = 0 the objective k\, c(w) c(u) D^{-1} \log \sigma(-s) increases as s \to -\infty: the unconstrained optimum is -\infty, like \mathrm{PMI} = \log 0. Low dimension keeps it finite in SGNS; PPMI truncates negative values at 0.

11. ★★ Gradients through time. (a) For the scalar RNN h_t = \tanh(w h_{t-1} + x_t) with w = 0.9, bound |\partial h_{50} / \partial h_0|. (b) Compare with an LSTM whose forget gate stays at f_t = 0.99, along the cell path. (c) Why does the transformer not have this problem across positions?

    Solution: (a) Proposition 6.2 gives at most 0.9^{50} \approx 0.005. (b) Along the cell, the factor is 0.99^{50} \approx 0.61: the signal survives. (c) Any two positions are connected by one attention step, so the path length between them is 1, not their distance; the price is the O(T^2) cost.

12. ★★ pass@k. (a) With n = 10 samples of which c = 2 pass, compute the estimate of pass@5. (b) Show that for k = 1 the estimator is c / n. (c) Prove that the plug-in estimator 1 - (1 - c/n)^k is biased downwards.

    Solution: (a) 1 - \binom{8}{5} / \binom{10}{5} = 1 - 56/252 \approx 0.778. (b) \binom{n-c}{1} / \binom{n}{1} = (n - c)/n. (c) g(p) = 1 - (1 - p)^k is concave, and c/n is unbiased for p, so by Jensen \mathbb{E}\big[g(c/n)\big] \leq g\big(\mathbb{E}[c/n]\big) = g(p) .

13. ★★ CTC in log space, vectorised (Python). Rewrite the CTC recursion of Code 10.5 without the inner loop over s, check it against torch.nn.functional.ctc_loss on 50 frames and a label of length 8, then decode greedily.

    Solution: shift the vector \alpha by one and by two positions, mask the forbidden skips once, and combine the three with a log-sum-exp.

    import torch
    torch.set_num_threads(1); torch.manual_seed(0)
    
    def ctc_nll(logp, y, blank=0):
        """CTC negative log-likelihood, vectorised over the extended label sequence."""
        z = torch.full((2 * len(y) + 1,), blank, dtype=torch.long)
        z[1::2] = torch.tensor(y)
        S = len(z)
        skip = torch.zeros(S, dtype=torch.bool)
        skip[2:] = (z[2:] != blank) & (z[2:] != z[:-2])        # allowed jumps s-2 -> s
        alpha = torch.full((S,), float("-inf"))
        alpha[:2] = logp[0, z[:2]]
        for t in range(1, logp.shape[0]):
            a1 = torch.cat([torch.tensor([float("-inf")]), alpha[:-1]])
            a2 = torch.cat([torch.tensor([float("-inf")] * 2), alpha[:-2]])
            a2 = torch.where(skip, a2, torch.tensor(float("-inf")))
            alpha = torch.logsumexp(torch.stack([alpha, a1, a2]), 0) + logp[t, z]
        return -torch.logsumexp(alpha[-2:], 0)
    
    T, C = 50, 6
    logp = torch.randn(T, C).log_softmax(-1)
    y = [1, 3, 3, 2, 5, 1, 1, 4]
    ref = torch.nn.functional.ctc_loss(logp[:, None], torch.tensor([y]), [T], [len(y)], reduction="sum")
    print(f"ours {ctc_nll(logp, y):.4f}   torch {ref:.4f}")
    best = logp.argmax(-1).tolist()                           # greedy decoding: best symbol per frame
    decoded = [k for i, k in enumerate(best) if (i == 0 or k != best[i - 1]) and k != 0]
    print("greedy output length", len(decoded))

    Both give 63.8471. On random scores, greedy decoding outputs 38 symbols instead of 8: an untrained network has no reason to emit blanks.

14. ★★ Naive Bayes and negation by hand. Train multinomial naive Bayes with add-one smoothing on four documents: (+) “good movie”, (+) “great plot”, (−) “not good”, (−) “boring plot”. Compute the log-odds of “not good” and of “not great”, and explain the second result.

    Solution: each class has 4 tokens and the vocabulary 6 words, so each estimate is (c + 1)/10. For “not good”, the log-odds are \log(0.1/0.2) + \log(0.2/0.2) = -0.69: negative, correct.

    For “not great”, they are \log(0.1/0.2) + \log(0.2/0.1) = 0: a tie. The model adds a fixed weight per word and cannot learn that “not” flips “great”; a bigram feature “not great”, or the NOT_ marking of Code 9.4, would.

15. ★★ Temperature. Let p_T = \mathrm{softmax}(z / T) with distinct logits. Prove that p_T tends to the one-hot vector of \arg\max_k z_k as T \to 0, to the uniform law as T \to \infty, and that its entropy increases with T.

    Solution: divide numerator and denominator by e^{z_{\max}/T}; every other term is e^{-(z_{\max} - z_k)/T} \to 0. As T \to \infty, every e^{z_k/T} \to 1. With b = 1/T, H = \log Z(b) - b\, \mathbb{E}_p[z], and differentiating, \frac{dH}{db} = -b\, \mathrm{Var}_p(z), \qquad \frac{dH}{dT} = \frac{\mathrm{Var}_p(z)}{T^3} \geq 0 .

16. ★★ Compute-optimal allocation. Minimise the scaling law of Definition 7.5 under the constraint 6ND = C. Show that the optimal sizes grow as powers of the budget, N_{\mathrm{opt}} \propto C^{\beta / (\alpha + \beta)}, \qquad D_{\mathrm{opt}} \propto C^{\alpha / (\alpha + \beta)}, and evaluate the exponents for the fitted values \alpha = 0.34 and \beta = 0.28 of Hoffmann and coauthors (2022).

    Solution: substitute D = C / (6N) and set the derivative in N to zero: \alpha A N^{-\alpha - 1} = \beta B\, 6^{\beta}\, C^{-\beta} N^{\beta - 1} \iff N^{\alpha + \beta} = \frac{\alpha A}{\beta B} \Big( \frac{C}{6} \Big)^{\beta} .

    Hence a = \beta/(\alpha + \beta) \approx 0.45 and D = C/(6N) gives b = 1 - a \approx 0.55: parameters and tokens grow almost equally, unlike earlier recommendations that put most of the budget into parameters.

17. ★★★ Designing a human-parity study. A company claims that its sentiment classifier “reaches human performance” because its accuracy against one annotator equals that of a second annotator. Using Proposition 12.2 and Code 12.5, write the protocol of a study that would support or refute the claim.

    Hints and expected result: several independent annotators with a stated profile; agreement measured by kappa before any comparison; systems and humans scored on the same items against an adjudicated reference, or against each annotator in turn; paired bootstrap intervals; an analysis of error types (negation, irony, neutral cases), since equal accuracy can hide different errors; a pre-registered decision rule. The expected conclusion is a statement with an interval, not a yes or no.

18. ★★★ Kneser–Ney against add-k (Python). Generate 25,000 tokens from a Markov chain over 300 words with sparse, Zipf-shaped transition rows. Train on 20,000 tokens and compare the test perplexity of add-k smoothing (several k) and interpolated Kneser–Ney (several d).

    Hints and expected result: tune k and d on the test set only for this exercise; use a held-out set in practice.

    import math
    import numpy as np
    from collections import Counter
    rng = np.random.default_rng(0)
    V = 300                                                   # Markov text with Zipfian, sparse rows
    zipf = 1.0 / np.arange(1, V + 1)
    P = np.stack([rng.dirichlet(0.05 * V * zipf / zipf.sum()) for _ in range(V)])
    cdf = P.cumsum(1)
    x, u = [0], rng.random(25000)
    for t in range(25000):
        x.append(min(int(np.searchsorted(cdf[x[-1]], u[t])), V - 1))
    train, test = x[:20000], x[20000:]
    big = Counter(zip(train, train[1:])); ctx = Counter(train[:-1])
    fol = Counter(a for a, b in big); pre = Counter(b for a, b in big); n_types = len(big)
    
    def pp(prob):
        lp = [math.log(prob(b, a)) for a, b in zip(test, test[1:])]
        return math.exp(-sum(lp) / len(lp))
    
    def add_k(k):
        return lambda b, a: (big[a, b] + k) / (ctx[a] + k * V)
    
    def kn(d):
        def p(b, a):
            cont = (pre[b] + 0.5) / (n_types + 0.5 * V)       # smoothed continuation probability
            if ctx[a] == 0:
                return cont
            return max(big[a, b] - d, 0) / ctx[a] + d * fol[a] / ctx[a] * cont
        return p
    
    print("add-k :", {k: round(pp(add_k(k)), 1) for k in [1, 0.1, 0.03, 0.01]})
    print("KN    :", {d: round(pp(kn(d)), 1) for d in [0.5, 0.75, 0.9]})

    Add-k gives 35.9 for k = 1 and at best 21.1 for k = 0.03; Kneser–Ney gives 20.2 for d = 0.5. The continuation probability needs a small add-0.5 term here, because a test word may never have been seen as a second word.

19. ★★★ What do discrete speech units encode? (Python, research-flavoured.) Spoken language models (ch. 14) cluster speech features into units. Synthesise the vowels /a/, /i/ and /u/ at three pitches with the source–filter generator of Code 2.7, compute MFCCs without c_0, cluster the frames by k-means with 3, 9 and 27 units, and measure the normalised mutual information of the units with the vowel and with the pitch.

    Hints and expected result:

    import numpy as np
    from scipy.fft import dct
    from sklearn.cluster import KMeans
    from sklearn.metrics import normalized_mutual_info_score as nmi
    rng = np.random.default_rng(0)
    sr, n_fft, win, hop = 16000, 512, 400, 160
    vowels = {"a": [700, 1200], "i": [300, 2300], "u": [300, 800]}   # first two formants (Hz)
    edges = 700 * (10 ** (np.linspace(0, 2595 * np.log10(1 + 8000 / 700), 42) / 2595) - 1)
    bins = np.fft.rfftfreq(n_fft, 1 / sr)
    fb = np.stack([np.clip(np.minimum((bins - edges[m]) / (edges[m + 1] - edges[m]),
                                      (edges[m + 2] - bins) / (edges[m + 2] - edges[m + 1])), 0, None) for m in range(40)])
    
    def mfcc_frames(f0, formants):
        t = np.arange(sr // 4) / sr
        x = sum(np.exp(-0.5 * ((h * f0 - np.array(formants)) / 100.0) ** 2).sum() * np.sin(2 * np.pi * h * f0 * t)
                for h in range(1, int(7000 / f0)))
        x = x + 0.01 * rng.normal(size=x.size)
        frames = np.stack([x[i: i + win] for i in range(0, len(x) - win, hop)]) * np.hamming(win)
        logmel = np.log(np.abs(np.fft.rfft(frames, n_fft)) ** 2 @ fb.T + 1e-8)
        return dct(logmel, norm="ortho", axis=1)[:, 1:13]           # drop c0 (loudness)
    
    X, vowel_lab, pitch_lab = [], [], []
    for vi, (v, F) in enumerate(vowels.items()):
        for pj, f0 in enumerate([100, 150, 220]):
            M = mfcc_frames(f0, F); X.append(M)
            vowel_lab += [vi] * len(M); pitch_lab += [pj] * len(M)
    for k in [3, 9, 27]:
        units = KMeans(k, n_init=10, random_state=0).fit_predict(np.vstack(X))
        print(k, round(nmi(vowel_lab, units), 2), round(nmi(pitch_lab, units), 2))

    With 3 units the clusters are exactly the vowels (NMI 1.00 with the vowel, 0.00 with the pitch). With 9 units they also split by pitch (0.67 and 0.57), and with 27 units both are 0.52: finer units encode speaker properties along with phonetic content. The research question of ch. 14, 14.1, is how to keep the content and drop the rest; try adding noise, or speaker normalisation of the features.

Projects and assessment

The official assessment (master-mva.com) has two parts: online quizzes at the end of the classes, 40 % of the grade with the best 6 of 7 kept, and a final project, 60 %, done in groups of 2–4 around a recent speech or language processing paper with existing code. The project replicates the main result, then tests a new question; it is presented in a one-page plan, a 4-page report and a 10-minute talk with 5 minutes of questions, and graded individually.

The group subjects below follow this format; the solo subjects are smaller paper studies for practice; the written exam is a model of the comprehension questions.

Solo projects

1. [Solo · ≈ 20 h] Word embeddings as matrix factorisation. Is SGNS better than a well-tuned SVD of the PPMI matrix? A paper study of Levy, Goldberg and Dagan, “Improving Distributional Similarity with Lessons Learned from Word Embeddings” (TACL, 2015), building on Theorem 5.5.
   • Implement: PPMI with context-distribution smoothing, truncated SVD, and SGNS (gensim), with matched windows and negative counts.
   • Data: the text8 corpus (the first 10^8 characters of a cleaned English Wikipedia dump); WordSim-353 (Finkelstein and coauthors, 2002) and SimLex-999 (Hill, Reichart and Korhonen, 2015) for evaluation.
   • Deliverables: code, a 4–6 page report, a 10-minute talk. Chapters: ch. 0, 5.
   • Success: Spearman correlations for both methods with bootstrap intervals; a check of Theorem 5.5 on frequent pairs; a verdict on the paper’s claim that hyperparameters matter more than the algorithm.
2. [Solo · ≈ 20 h] A CTC recogniser for spoken digit strings. How far does CTC go without any language model on a small vocabulary? A paper study of Graves and coauthors, “Connectionist Temporal Classification” (ICML, 2006).
   • Implement: log-mel features (Code 2.7); a bidirectional LSTM trained with the CTC loss (Theorem 10.4); greedy and beam decoding.
   • Data: the ten digit words of Speech Commands (Warden, 2018), concatenated into random strings of 3 to 7 digits with random pauses, with disjoint speakers for training and test.
   • Deliverables: code, a 4–6 page report, a 10-minute talk. Chapters: ch. 2, 6, 10.
   • Success: a digit-string error rate below 10 % on unseen speakers, and an analysis of the peaky behaviour of CTC posteriors (most frames emit the blank).
3. [Solo · ≈ 15 h] Neural text degeneration. Does nucleus sampling produce text whose statistics are closest to human text? A paper study of Holtzman and coauthors, “The Curious Case of Neural Text Degeneration” (ICLR, 2020).
   • Implement: greedy, beam (B = 5), pure, top-k (k = 40) and nucleus (p = 0.95) decoding (Definition 7.6) with GPT-2 small, from 200 prompts taken from WikiText-103 (Merity and coauthors, 2017).
   • Measure: the share of repeated 4-grams, distinct-n, self-BLEU (Code 8.6) and the perplexity of the generations under a larger model.
   • Deliverables: code, a 4-page report. Chapters: ch. 7, 8, 12.
   • Success: the paper’s ordering reproduced (beam and greedy most repetitive, pure sampling least coherent, nucleus closest to human statistics), with bootstrap intervals over prompts.

Group projects

Each subject follows the official format: replicate the main result of the paper with its code, then test one new question; one-page plan first, then a 4-page report and a 10-minute talk.

1. [Group of 2–4 · ≈ 30 h each] Subword vocabularies for neural translation. Replicate the BPE result of Sennrich, Haddow and Birch, “Neural Machine Translation of Rare Words with Subword Units” (ACL, 2016), with a small transformer.
   • Data and code: IWSLT 2014 German→English (Cettolo and coauthors, 2014) with the fairseq toolkit (Ott and coauthors, 2019).
   • New question: the effect of the number of merges, or of BPE-dropout (Provilkov, Emelianenko and Voita, 2020), on rare words and on a low-resource subset of 20,000 pairs.
   • Split: data and tokenisation; training; evaluation (sacreBLEU, chrF, COMET, paired bootstrap) and error analysis; with four members, a human evaluation of 100 sentences.
   • Success: a baseline within 2 BLEU points of the score reported by the fairseq IWSLT’14 example, and a significance-tested answer to the new question. Chapters: ch. 1, 6, 8, 12.
2. [Group of 2–4 · ≈ 30 h each] Where do fine-tuned transformers beat linear sentiment models? Replicate the SST-2 accuracy of DistilBERT (Sanh and coauthors, 2019), against the NB-SVM baseline of Wang and Manning (ACL, 2012).
   • Data: SST-2 (Socher and coauthors, 2013) and IMDB reviews (Maas and coauthors, 2011).
   • New question: accuracy on sentences with negation or contrast (“but”), robustness to typos, and transfer from one dataset to the other.
   • Split: baselines (ch. 9); fine-tuning (ch. 7); challenge sets and statistics (ch. 12).
   • Success: development accuracy within 1 point of the paper; the gap on the negation subset with a bootstrap interval; a reasoned answer to “is the gain composition or vocabulary?”.
3. [Group of 3–4 · ≈ 30 h each] Sampling, pass@k and self-repair for code. Replicate the pass@k curves of Chen and coauthors, “Evaluating Large Language Models Trained on Code” (2021), with an open code model of at most 1.5 billion parameters on a free GPU tier.
   • Data: HumanEval and MBPP (Austin and coauthors, 2021).
   • New question: does an agent loop with execution feedback (Definition 11.7) beat independent sampling at an equal budget of model calls? Compare with the analysis of Olausson and coauthors (ICLR, 2024).
   • Split: sandboxed execution and the estimator (Proposition 11.5); sampling sweeps over temperature; the repair loop; analysis.
   • Success: pass@1 within 2 points of the value reported for the chosen model; the paper’s finding that the best temperature grows with k; the repair gain at equal budget, with intervals. Chapters: ch. 7, 11, 12.
4. [Group of 2–4 · ≈ 30 h each] Self-supervised speech with ten minutes of labels. Replicate a low-resource row of wav2vec 2.0 (Baevski and coauthors, NeurIPS 2020): fine-tune the pretrained base model with CTC on the 10-minute or 1-hour split of Libri-light (Kahn and coauthors, 2020).
   • Evaluate: WER on LibriSpeech test-clean and test-other (Panayotov and coauthors, 2015), without and with an n-gram language model.
   • New question: which layers of the frozen model carry phonetic information (linear probes per layer), or how WER degrades with added noise.
   • Split: fine-tuning; decoding with and without LM; probing and analysis.
   • Success: WER within 20 % (relative) of the paper’s value for the same split and decoding setting, and a layer-wise probe curve. Chapters: ch. 2, 10, 12.

Written exam (proposal)

Two hours, one handwritten A4 sheet allowed, no electronic device; four questions, 20 points. The questions mirror the comprehension quizzes of the official assessment, with one computation and one proof.

1. Question (4 points). Compare the HMM tagger, the linear-chain CRF and CTC: what each one models, which independence assumption it makes, and which dynamic program computes its likelihood or normaliser.

   Expected:

   • HMM: a joint law of tags and words; tags form a Markov chain and each word depends only on its tag; forward algorithm (1 pt).
   • CRF: a conditional law of tags given the whole sentence; Markov in the tags, arbitrary features of the input; forward algorithm for Z(x), concave likelihood (1.5 pts).
   • CTC: a conditional law of a label sequence given frames, frame outputs independent given the input, alignments summed by the forward recursion on the label sequence extended with blanks (1.5 pts).

2. Question (6 points). (a) An HMM over the symbols x and y has two states, and \pi = (0.5, 0.5), \qquad A = \begin{pmatrix} 0.7 & 0.3 \\ 0.4 & 0.6 \end{pmatrix}, \qquad P(x \mid 1) = 0.9, \quad P(x \mid 2) = 0.2 . For the observations x, y, compute P(O) and the best path. (b) Compute BLEU with N = 1 for the hypothesis “the the cat” against the reference “the cat sat on the mat”. (c) Compute the WER of “turn lights of” against “turn the lights off”.

   Expected:

   • 1. \alpha_1 = (0.45, 0.10) and \alpha_2 = (0.0355, 0.156), so P(O) = 0.1915; \delta_2 = (0.0315, 0.108), best path 1 then 2, of probability 0.108 (3 pts).
   • 2. Clipped precision 3/3 = 1, but the hypothesis has 3 words against 6, so \mathrm{BP} = e^{1 - 6/3} \approx 0.368 and BLEU-1 is 0.368 (1.5 pts).
   • 3. One deletion (“the”) and one substitution (“off” → “of”) on 4 words: 50 % (1.5 pts).

3. Question (5 points). Prove Theorem 5.5: if each inner product can be set freely, the SGNS objective summed over the corpus is maximised at \mathbf{w}^\top \mathbf{u} = \mathrm{PMI}(w, u) - \log k.

   Expected:

   • The pair is drawn as a negative k\, c(w)\, c(u) / D times in expectation, so the objective is a sum over pairs of (2 pts) \ell(s) = c(w, u) \log \sigma(s) + \frac{k\, c(w)\, c(u)}{D} \log \sigma(-s) .
   • With \sigma' = \sigma(s)\sigma(-s), setting \ell'(s) = 0 gives e^s = c(w, u) D / (k\, c(w) c(u)) (2 pts).
   • Each \ell is strictly concave, so this is the maximum, and the pairs decouple (1 pt).

4. Question (5 points). (a) Show that if q, k \in \mathbb{R}^d have independent entries of mean 0 and variance 1, then \mathrm{Var}(q^\top k) = d, and explain the factor 1/\sqrt{d}. (b) With d = 2, compute the two outputs of causal scaled dot-product attention for q_1 = (1, 0),\ q_2 = (0, 1), \qquad k_1 = (1, 1),\ k_2 = (1, -1), \qquad v_1 = (1, 0),\ v_2 = (0, 1) .

   3. Why do transformers need positional information?

   Expected:

   • 1. A sum of d independent terms of mean 0 and variance 1; unscaled scores saturate the softmax (1.5 pts).
   • 2. Position 1 sees only itself: output v_1 = (1, 0). Position 2 has scores \pm 1/\sqrt{2}, weights (0.804, 0.196), output (0.804, 0.196) (2 pts).
   • 3. Without a mask or positions, self-attention is permutation-equivariant (Proposition 6.7), so “dog bites man” and “man bites dog” would get the same multiset of outputs (1.5 pts).

Grading rubric (proposal)

The rubric follows the official requirements of the project: a plan, a replication, a new question, a report, a talk and individual grading.

References

Official reference (master-mva.com). The course description recommends, without making it obligatory, the textbook of Jurafsky and Martin: the 3rd online edition for the chapters already available [J&M3], the 2nd edition otherwise [J&M2]. Readings for each session are given by the instructors.

• D. Jurafsky, J. H. Martin, Speech and Language Processing, 3rd edition, draft chapters available online at web.stanford.edu/~jurafsky/slp3 [J&M3].
• D. Jurafsky, J. H. Martin, Speech and Language Processing, 2nd edition, Prentice Hall, 2009 [J&M2].

Textbooks.

• C. D. Manning, H. Schütze, Foundations of Statistical Natural Language Processing, MIT Press, 1999.
• J. Eisenstein, Introduction to Natural Language Processing, MIT Press, 2019.
• Y. Goldberg, Neural Network Methods for Natural Language Processing, Morgan & Claypool, 2017.
• X. Huang, A. Acero, H.-W. Hon, Spoken Language Processing: A Guide to Theory, Algorithm and System Development, Prentice Hall, 2001.
• P. Koehn, Statistical Machine Translation, Cambridge University Press, 2010; Neural Machine Translation, Cambridge University Press, 2020.
• B. Liu, Sentiment Analysis and Opinion Mining, Morgan & Claypool, 2012.

History, language models and tokenisation (ch. 1, 7, 13).

• C. E. Shannon, A mathematical theory of communication, Bell System Technical Journal 27, 1948.
• R. Kneser, H. Ney, Improved backing-off for m-gram language modeling, ICASSP 1995.
• S. F. Chen, J. Goodman, An empirical study of smoothing techniques for language modeling, Computer Speech and Language 13(4), 1999.
• Y. Bengio, R. Ducharme, P. Vincent, C. Jauvin, A neural probabilistic language model, Journal of Machine Learning Research 3, 2003.
• R. Sennrich, B. Haddow, A. Birch, Neural machine translation of rare words with subword units, ACL 2016 [2016a].
• J. Devlin, M.-W. Chang, K. Lee, K. Toutanova, BERT: pre-training of deep bidirectional transformers for language understanding, NAACL 2019.
• C. Raffel et al., Exploring the limits of transfer learning with a unified text-to-text transformer, Journal of Machine Learning Research 21, 2020.
• J. Hoffmann et al., Training compute-optimal large language models, NeurIPS 2022.
• A. Holtzman, J. Buys, L. Du, M. Forbes, Y. Choi, The curious case of neural text degeneration, ICLR 2020.
• L. Ouyang et al., Training language models to follow instructions with human feedback, NeurIPS 2022.
• R. Rafailov, A. Sharma, E. Mitchell, S. Ermon, C. D. Manning, C. Finn, Direct preference optimization: your language model is secretly a reward model, NeurIPS 2023.

Speech signal, HMMs and finite-state models (ch. 2, 3).

• S. Davis, P. Mermelstein, Comparison of parametric representations for monosyllabic word recognition in continuously spoken sentences, IEEE Transactions on Acoustics, Speech, and Signal Processing 28(4), 1980.
• L. R. Rabiner, A tutorial on hidden Markov models and selected applications in speech recognition, Proceedings of the IEEE 77(2), 1989.
• M. Mohri, F. Pereira, M. Riley, Weighted finite-state transducers in speech recognition, Computer Speech and Language 16(1), 2002.

Sequence labelling and embeddings (ch. 4, 5).

• J. Lafferty, A. McCallum, F. Pereira, Conditional random fields: probabilistic models for segmenting and labeling sequence data, ICML 2001.
• E. F. Tjong Kim Sang, F. De Meulder, Introduction to the CoNLL-2003 shared task: language-independent named entity recognition, CoNLL 2003.
• G. Lample, M. Ballesteros, S. Subramanian, K. Kawakami, C. Dyer, Neural architectures for named entity recognition, NAACL 2016.
• J. R. Firth, A synopsis of linguistic theory 1930–1955, in Studies in Linguistic Analysis, Blackwell, 1957.
• T. Mikolov, K. Chen, G. Corrado, J. Dean, Efficient estimation of word representations in vector space, ICLR workshop 2013.
• T. Mikolov, I. Sutskever, K. Chen, G. Corrado, J. Dean, Distributed representations of words and phrases and their compositionality, NeurIPS 2013.
• T. Mikolov, W.-t. Yih, G. Zweig, Linguistic regularities in continuous space word representations, NAACL 2013.
• O. Levy, Y. Goldberg, Neural word embedding as implicit matrix factorization, NeurIPS 2014.
• O. Levy, Y. Goldberg, I. Dagan, Improving distributional similarity with lessons learned from word embeddings, Transactions of the ACL 3, 2015.
• J. Pennington, R. Socher, C. D. Manning, GloVe: global vectors for word representation, EMNLP 2014.
• P. Bojanowski, E. Grave, A. Joulin, T. Mikolov, Enriching word vectors with subword information, Transactions of the ACL 5, 2017.
• T. Bolukbasi, K.-W. Chang, J. Zou, V. Saligrama, A. Kalai, Man is to computer programmer as woman is to homemaker? Debiasing word embeddings, NeurIPS 2016.

Neural architectures (ch. 6).

• S. Hochreiter, J. Schmidhuber, Long short-term memory, Neural Computation 9(8), 1997.
• R. Pascanu, T. Mikolov, Y. Bengio, On the difficulty of training recurrent neural networks, ICML 2013.
• D. Bahdanau, K. Cho, Y. Bengio, Neural machine translation by jointly learning to align and translate, ICLR 2015.
• A. Vaswani et al., Attention is all you need, NeurIPS 2017.
• J. Su, Y. Lu, S. Pan, A. Murtadha, B. Wen, Y. Liu, RoFormer: enhanced transformer with rotary position embedding, arXiv:2104.09864, 2021.

Machine translation (ch. 8).

• P. F. Brown, S. A. Della Pietra, V. J. Della Pietra, R. L. Mercer, The mathematics of statistical machine translation: parameter estimation, Computational Linguistics 19(2), 1993.
• P. Koehn, F. J. Och, D. Marcu, Statistical phrase-based translation, NAACL 2003.
• K. Papineni, S. Roukos, T. Ward, W.-J. Zhu, BLEU: a method for automatic evaluation of machine translation, ACL 2002.
• M. Popović, chrF: character n-gram F-score for automatic MT evaluation, WMT 2015.
• R. Sennrich, B. Haddow, A. Birch, Improving neural machine translation models with monolingual data, ACL 2016 [2016b].
• M. Post, A call for clarity in reporting BLEU scores, WMT 2018.
• R. Rei, C. Stewart, A. C. Farinha, A. Lavie, COMET: a neural framework for MT evaluation, EMNLP 2020.

Sentiment analysis (ch. 9).

• B. Pang, L. Lee, S. Vaithyanathan, Thumbs up? Sentiment classification using machine learning techniques, EMNLP 2002.
• R. Socher et al., Recursive deep models for semantic compositionality over a sentiment treebank, EMNLP 2013.
• S. Wang, C. D. Manning, Baselines and bigrams: simple, good sentiment and topic classification, ACL 2012.
• C. Clavel, Z. Callejas, Sentiment analysis: from opinion mining to human-agent interaction, IEEE Transactions on Affective Computing 7(1), 2016.

Speech recognition and synthesis (ch. 10, 13).

• A. Graves, S. Fernández, F. Gomez, J. Schmidhuber, Connectionist temporal classification: labelling unsegmented sequence data with recurrent neural networks, ICML 2006.
• A. Graves, Sequence transduction with recurrent neural networks, arXiv:1211.3711, 2012.
• W. Chan, N. Jaitly, Q. Le, O. Vinyals, Listen, attend and spell: a neural network for large vocabulary conversational speech recognition, ICASSP 2016.
• A. Baevski, Y. Zhou, A. Mohamed, M. Auli, wav2vec 2.0: a framework for self-supervised learning of speech representations, NeurIPS 2020.
• W.-N. Hsu, B. Bolte, Y.-H. H. Tsai, K. Lakhotia, R. Salakhutdinov, A. Mohamed, HuBERT: self-supervised speech representation learning by masked prediction of hidden units, IEEE/ACM Transactions on Audio, Speech, and Language Processing 29, 2021.
• A. Radford, J. W. Kim, T. Xu, G. Brockman, C. McLeavey, I. Sutskever, Robust speech recognition via large-scale weak supervision, ICML 2023.
• A. van den Oord et al., WaveNet: a generative model for raw audio, arXiv:1609.03499, 2016.
• J. Shen et al., Natural TTS synthesis by conditioning WaveNet on mel spectrogram predictions, ICASSP 2018.
• Y. Ren et al., FastSpeech 2: fast and high-quality end-to-end text to speech, ICLR 2021.
• J. Kong, J. Kim, J. Bae, HiFi-GAN: generative adversarial networks for efficient and high fidelity speech synthesis, NeurIPS 2020.

Dialogue, code and agents (ch. 11).

• J. Weizenbaum, ELIZA — a computer program for the study of natural language communication between man and machine, Communications of the ACM 9(1), 1966.
• S. Young, M. Gašić, B. Thomson, J. D. Williams, POMDP-based statistical spoken dialog systems: a review, Proceedings of the IEEE 101(5), 2013.
• P. Lewis et al., Retrieval-augmented generation for knowledge-intensive NLP tasks, NeurIPS 2020.
• M. Chen et al., Evaluating large language models trained on code, arXiv:2107.03374, 2021.
• J. Austin et al., Program synthesis with large language models, arXiv:2108.07732, 2021.
• S. Yao et al., ReAct: synergizing reasoning and acting in language models, ICLR 2023.
• C. E. Jimenez et al., SWE-bench: can language models resolve real-world GitHub issues?, ICLR 2024.
• T. X. Olausson, J. P. Inala, C. Wang, J. Gao, A. Solar-Lezama, Is self-repair a silver bullet for code generation?, ICLR 2024.

Evaluation (ch. 12).

• J. Cohen, A coefficient of agreement for nominal scales, Educational and Psychological Measurement 20(1), 1960.
• P. Koehn, Statistical significance tests for machine translation evaluation, EMNLP 2004.
• W. Xiong et al., Achieving human parity in conversational speech recognition, arXiv:1610.05256, 2016.
• G. Saon et al., English conversational telephone speech recognition by humans and machines, Interspeech 2017.
• H. Hassan et al., Achieving human parity on automatic Chinese to English news translation, arXiv:1803.05567, 2018.
• S. Läubli, R. Sennrich, M. Volk, Has machine translation achieved human parity? A case for document-level evaluation, EMNLP 2018.
• S. Gururangan, S. Swayamdipta, O. Levy, R. Schwartz, S. Bowman, N. A. Smith, Annotation artifacts in natural language inference data, NAACL 2018.
• D. Kiela et al., Dynabench: rethinking benchmarking in NLP, NAACL 2021.
• L. Zheng et al., Judging LLM-as-a-judge with MT-Bench and Chatbot Arena, NeurIPS 2023 (Datasets and Benchmarks).

Research directions (ch. 14).

• K. Lakhotia et al., On generative spoken language modeling from raw audio, Transactions of the ACL 9, 2021.
• T. A. Nguyen et al., Generative spoken dialogue language modeling, Transactions of the ACL 11, 2023.
• T. A. Nguyen et al., SpiRit-LM: interleaved spoken and written language model, arXiv:2402.05755, 2024.
• E. Dupoux, Cognitive science in the era of artificial intelligence: a roadmap for reverse-engineering the infant language-learner, Cognition 173, 2018.
• A. Gu, K. Goel, C. Ré, Efficiently modeling long sequences with structured state spaces, ICLR 2022.
• A. Gu, T. Dao, Mamba: linear-time sequence modeling with selective state spaces, arXiv:2312.00752, 2023.
• M. Poli et al., Hyena hierarchy: towards larger convolutional language models, ICML 2023.
• S. Jelassi, D. Brandfonbrener, S. M. Kakade, E. Malach, Repeat after me: transformers are better than state space models at copying, ICML 2024.
• NLLB Team, No language left behind: scaling human-centered machine translation, arXiv:2207.04672, 2022.
• BigScience Workshop, BLOOM: a 176B-parameter open-access multilingual language model, arXiv:2211.05100, 2022.
• R. Bawden, R. Sennrich, A. Birch, B. Haddow, Evaluating discourse phenomena in neural machine translation, NAACL 2018.
• M. Freitag, G. Foster, D. Grangier, V. Ratnakar, Q. Tan, W. Macherey, Experts, errors, and context: a large-scale study of human evaluation for machine translation, Transactions of the ACL 9, 2021.

Data sets and tools for the projects.

• L. Finkelstein et al., Placing search in context: the concept revisited, ACM Transactions on Information Systems 20(1), 2002 (WordSim-353).
• F. Hill, R. Reichart, A. Korhonen, SimLex-999: evaluating semantic models with (genuine) similarity estimation, Computational Linguistics 41(4), 2015.
• P. Warden, Speech Commands: a dataset for limited-vocabulary speech recognition, arXiv:1804.03209, 2018.
• S. Merity, C. Xiong, J. Bradbury, R. Socher, Pointer sentinel mixture models, ICLR 2017 (WikiText-103).
• M. Cettolo, J. Niehues, S. Stüker, L. Bentivogli, M. Federico, Report on the 11th IWSLT evaluation campaign, IWSLT 2014.
• M. Ott et al., fairseq: a fast, extensible toolkit for sequence modeling, NAACL 2019 (demonstrations).
• I. Provilkov, D. Emelianenko, E. Voita, BPE-dropout: simple and effective subword regularization, ACL 2020.
• V. Sanh, L. Debut, J. Chaumond, T. Wolf, DistilBERT, a distilled version of BERT: smaller, faster, cheaper and lighter, arXiv:1910.01108, 2019.
• A. L. Maas et al., Learning word vectors for sentiment analysis, ACL 2011 (IMDB reviews).
• J. Kahn et al., Libri-light: a benchmark for ASR with limited or no supervision, ICASSP 2020.
• V. Panayotov, G. Chen, D. Povey, S. Khudanpur, LibriSpeech: an ASR corpus based on public domain audio books, ICASSP 2015.