Deep Learning,
Week 8

The LSTM works but is heavy: two state vectors and four weight blocks. The Gated Recurrent Unit (GRU) (Cho et al., 2014) keeps the central idea, a gate that lets the state pass through unchanged, with a lighter design: one state vector, two gates.

1.1The equations

The reset gate lets the candidate ignore the past ($r\approx0$) when a fresh start is appropriate, for instance at the start of a new clause. The update gate is a dimmer between "copy the old state" ($z\approx1$) and "replace it with the candidate" ($z\approx0$). Write the cell by hand and compare it with nn.GRU:

import torch, torch.nn as nn
torch.manual_seed(0)
d, h, T = 3, 4, 6
gru = nn.GRU(d, h, batch_first=True)
x = torch.randn(1, T, d)
Wi, Wh, bi, bh = gru.weight_ih_l0, gru.weight_hh_l0, gru.bias_ih_l0, gru.bias_hh_l0     # blocks stacked in the order: reset, update, candidate
sig = torch.sigmoid

hs, h_t = [], torch.zeros(h)
for t in range(T):
    gi, gh = Wi @ x[0, t] + bi, Wh @ h_t + bh
    r = sig(gi[:h] + gh[:h])                           # reset gate: how much of the past to use when proposing a new state
    z = sig(gi[h:2 * h] + gh[h:2 * h])                 # update gate: how much of the old state to KEEP
    n = torch.tanh(gi[2 * h:] + r * gh[2 * h:])        # candidate state
    h_t = (1 - z) * n + z * h_t                        # PyTorch convention: z is the weight on the OLD state
    hs.append(h_t)
print("hand-written GRU matches nn.GRU:", torch.allclose(torch.stack(hs), gru(x)[0][0], atol=1e-6))
print("gate values at the last step: reset", [round(v, 2) for v in r.tolist()], " update", [round(v, 2) for v in z.tolist()])
count = lambda m: sum(p.numel() for p in m.parameters())
d, h = 10, 20
print(f"\nparameters for d={d}, h={h}:  RNN {count(nn.RNN(d, h))},  GRU {count(nn.GRU(d, h))},  LSTM {count(nn.LSTM(d, h))}   (GRU = 3x RNN, LSTM = 4x)")
print("GRU has ONE state vector (h); the LSTM has two (h and c)")

hand-written GRU matches nn.GRU: True
gate values at the last step: reset [0.65, 0.59, 0.3, 0.29]  update [0.82, 0.46, 0.61, 0.32]

parameters for d=10, h=20:  RNN 640,  GRU 1920,  LSTM 2560   (GRU = 3x RNN, LSTM = 4x)
GRU has ONE state vector (h); the LSTM has two (h and c)

1.2What the update gate really does

Force the update gate to extremes in a real nn.GRU by setting its bias to $\pm30$, and see what happens to the state over 30 steps:

import torch, torch.nn as nn
torch.manual_seed(0)
d, h, T = 3, 5, 30
def make(update_bias):
    gru = nn.GRU(d, h, batch_first=True)
    with torch.no_grad():
        gru.bias_ih_l0[h:2 * h] = update_bias          # the update-gate block of the bias
        gru.bias_hh_l0[h:2 * h] = 0.0
    return gru
x = torch.randn(1, T, d)
h0 = torch.randn(1, 1, h)
for name, bias in (("update gate forced to ~1 (keep)", 30.0), ("update gate forced to ~0 (overwrite)", -30.0)):
    gru = make(bias)
    out, hT = gru(x, h0)
    print(f"{name:40s}  max |h_T - h_0| = {(hT - h0).abs().max().item():.6f}")
x2 = torch.randn(1, T, d)                               # a different input sequence
for name, bias in (("update gate ~1", 30.0), ("update gate ~0", -30.0)):
    gru = make(bias)
    a = gru(x, h0)[1]; b = gru(x2, h0)[1]
    print(f"{name}: final state for two DIFFERENT inputs differs by {(a - b).abs().max().item():.6f}")
print("z ~ 1 copies the old state through every step (the input is ignored); z ~ 0 replaces it by the new candidate each step")

update gate forced to ~1 (keep)           max |h_T - h_0| = 0.000000
update gate forced to ~0 (overwrite)      max |h_T - h_0| = 1.829469
update gate ~1: final state for two DIFFERENT inputs differs by 0.000000
update gate ~0: final state for two DIFFERENT inputs differs by 0.637222
z ~ 1 copies the old state through every step (the input is ignored); z ~ 0 replaces it by the new candidate each step

With the gate pinned at "keep", the state after 30 steps is identical to the starting state (difference 0.000000), and two completely different input sequences give the same final state: the input is ignored and the memory is perfectly preserved. Pinned at "overwrite", the final state has nothing to do with the start and differs for different inputs (by 0.64). A trained GRU sits between these, per dimension and per step. This is the GRU's analogue of the LSTM's forget gate: the gradient also takes the copy path, with derivative $z$ per step, so near 1 the signal survives long ranges. And, exactly as with the LSTM, this only helps when the gate actually learns to stay open.

1.3GRU versus LSTM

The GRU is smaller (25% fewer parameters) and slightly faster; the LSTM has a little more control. Which is better? The honest answer is "it depends on the data, try both": on many tasks they perform about the same. The source notes' rule "LSTM for long sentences, GRU for medium" is a common heuristic, but not a law and not something proved in this course.

1.4Chapter summary

• GRU: reset $r$, update $z$, candidate $\tilde h$; one state $h$; $h_t=(1-z)\odot\tilde h+z\odot h_{t-1}$ (PyTorch convention; the notes swap $z$ and $1-z$).
• Measured: update gate $\approx1$ copies the state exactly across 30 steps; $\approx0$ overwrites it.
• 3 weight blocks against the LSTM's 4; comparable accuracy on many tasks: try both.

A normal RNN reads left to right, so the state at position $t$ knows only $x_1\ldots x_t$. Often the meaning of a word depends on what comes after it: "I saw Apple announce a new phone" (company) against "I ate an apple pie" (fruit); "not bad at all"; filling in a missing word. A bidirectional RNN reads the sequence twice.

• A forward RNN reads $x_1\to x_T$ giving $\overrightarrow{h}_t$ (the left context).
• A backward RNN reads $x_T\to x_1$ giving $\overleftarrow{h}_t$ (the right context). The two RNNs have separate weights.
• At each position concatenate $h_t=[\overrightarrow{h}_t;\overleftarrow{h}_t]$: the output is $2h$ wide, and the parameter count doubles.

2.1A task that needs the future

Make the difference measurable. A sequence of random symbols from 5 choices; the task at each position is to output either the previous symbol or the next symbol. Same GRU size, same training, one network reading one way and one reading both ways:

import torch, torch.nn as nn
torch.set_num_threads(1)
V, T = 5, 10

def batch(B, offset):
    x = torch.randint(0, V, (B, T))
    y = torch.roll(x, shifts=-offset, dims=1)           # offset=+1: target is the NEXT token; offset=-1: the PREVIOUS token
    return x, y

class Tagger(nn.Module):
    def __init__(self, bidirectional):
        super().__init__()
        self.emb = nn.Embedding(V, 16)
        self.rnn = nn.GRU(16, 32, batch_first=True, bidirectional=bidirectional)
        self.out = nn.Linear(32 * (2 if bidirectional else 1), V)
    def forward(self, x):
        return self.out(self.rnn(self.emb(x))[0])

def accuracy(bidirectional, offset, seed=0, steps=700):
    torch.manual_seed(seed)
    m = Tagger(bidirectional); opt = torch.optim.Adam(m.parameters(), lr=5e-3)
    for _ in range(steps):
        x, y = batch(64, offset)
        loss = nn.functional.cross_entropy(m(x).reshape(-1, V), y.reshape(-1))
        opt.zero_grad(); loss.backward(); opt.step()
    x, y = batch(2000, offset)
    pred = m(x).argmax(-1)
    inner = slice(1, T - 1)                              # skip the sequence ends, where roll wraps around
    return (pred[:, inner] == y[:, inner]).float().mean().item()

print("per-token accuracy (chance = 0.20)            unidirectional   bidirectional")
for name, off in (("tag each position with the PREVIOUS token", -1), ("tag each position with the NEXT token    ", +1)):
    print(f"  {name}      {accuracy(False, off):10.2f}      {accuracy(True, off):10.2f}")

m = Tagger(True); out, hn = m.rnn(m.emb(torch.randint(0, V, (3, T))))
print("\nbidirectional GRU output:", tuple(out.shape), "= (batch, T, 2*hidden): forward and backward states concatenated;  final states:", tuple(hn.shape))

per-token accuracy (chance = 0.20)            unidirectional   bidirectional
  tag each position with the PREVIOUS token            1.00            1.00
  tag each position with the NEXT token                0.20            1.00

bidirectional GRU output: (3, 10, 64) = (batch, T, 2*hidden): forward and backward states concatenated;  final states: (2, 3, 32)

Predicting the previous symbol is easy for both (1.00): the information is already in the past. Predicting the next symbol is impossible for the unidirectional network (0.20, exactly chance for 5 symbols, since random symbols cannot be guessed) but trivial for the bidirectional one (1.00), because its backward half has already read it. The output shape confirms the doubling: $(\text{batch},T,2h)$, with the final states of the two directions stacked as $(2,\text{batch},h)$.

2.2When to use it, and when not

2.3Chapter summary

• Two RNNs with separate weights, forward and backward; concatenate the states ($2h$ wide, double the parameters).
• Measured: tagging with the NEXT token: 0.20 unidirectional (chance), 1.00 bidirectional; the PREVIOUS token: 1.00 for both.
• For understanding with the whole input available; not for generation or real-time use.

So far the output had the same length as the input, or was a single label. Translation breaks that: "I love cats" (3 words) becomes "mujhe billiyan pasand hain" (4 words) and the second sentence cannot be produced one-to-one with the first. The architecture for variable-length input to variable-length output is the encoder-decoder, or sequence-to-sequence (seq2seq) model (Sutskever et al., 2014).

3.1The architecture

• Encoder: an RNN (LSTM or GRU) that reads the whole input; its final hidden state is the context vector, a summary of the input.
• Decoder: another RNN whose initial state is the context vector. It produces the output one token at a time, each step taking the previous output token as input, until it emits <eos>.
• The two halves are trained jointly, end to end, with cross-entropy on every output token.

The class below is a complete, runnable seq2seq model (a GRU encoder and decoder). The test task is deliberately simple, copy the input digits, because the answer is known exactly and any failure must be the architecture's. Note the two different ways the decoder is driven in forward (training) and generate (inference). The table reports three numbers per setting; the next two sections explain them.

import torch, torch.nn as nn
torch.set_num_threads(1)
V, BOS = 12, 10                                          # tokens 0..9 are digits, 10 = start-of-output

class Seq2Seq(nn.Module):
    def __init__(self, hidden):
        super().__init__()
        self.emb = nn.Embedding(V, 32)
        self.encoder = nn.GRU(32, hidden, batch_first=True)
        self.decoder = nn.GRU(32, hidden, batch_first=True)
        self.out = nn.Linear(hidden, V)
    def forward(self, src, tgt_in):                      # TRAINING, teacher forcing: the decoder is fed the TRUE previous tokens
        context = self.encoder(self.emb(src))[1]         # the final encoder state: ONE vector for the whole input
        return self.out(self.decoder(self.emb(tgt_in), context)[0])
    @torch.no_grad()
    def generate(self, src, length):                     # INFERENCE: the decoder is fed its OWN previous outputs
        state = self.encoder(self.emb(src))[1]
        tok, outputs = torch.full((src.size(0), 1), BOS), []
        for _ in range(length):
            o, state = self.decoder(self.emb(tok), state)
            tok = self.out(o).argmax(-1); outputs.append(tok)
        return torch.cat(outputs, 1)

def evaluate(length, hidden, seed=0, steps=2500):
    torch.manual_seed(seed)
    model = Seq2Seq(hidden); opt = torch.optim.Adam(model.parameters(), lr=3e-3)
    def batch(B):
        src = torch.randint(0, 10, (B, length))          # the task: copy the input sequence
        tgt_in = torch.cat([torch.full((B, 1), BOS), src[:, :-1]], 1)
        return src, tgt_in
    for _ in range(steps):
        src, tgt_in = batch(64)
        loss = nn.functional.cross_entropy(model(src, tgt_in).reshape(-1, V), src.reshape(-1))
        opt.zero_grad(); loss.backward(); nn.utils.clip_grad_norm_(model.parameters(), 1.0); opt.step()
    src, tgt_in = batch(1000)
    with torch.no_grad():
        forced = (model(src, tgt_in).argmax(-1) == src).float().mean().item()
        free = model.generate(src, length)
    return forced, (free == src).float().mean().item(), (free == src).all(1).float().mean().item()

print("copy task, chance = 0.10 per token")
print("sequence length  hidden   teacher-forced acc   free-running acc   whole sequence exact")
for length, hidden in ((4, 32), (8, 32), (16, 32), (32, 32), (16, 16), (16, 64), (16, 128)):
    a, b, c = evaluate(length, hidden)
    print(f"{length:10d}      {hidden:6d}   {a:14.3f}      {b:14.3f}      {c:14.3f}")

copy task, chance = 0.10 per token
sequence length  hidden   teacher-forced acc   free-running acc   whole sequence exact
         4          32            0.998               0.997               0.993
         8          32            0.921               0.794               0.514
        16          32            0.641               0.303               0.000
        32          32            0.396               0.147               0.000
        16          16            0.470               0.197               0.000
        16          64            0.829               0.564               0.028
        16         128            0.947               0.870               0.405

3.2The bottleneck

Read the free-running column. With a hidden size of 32, copying 4 digits is perfect (0.997), 8 digits drops to 0.79, 16 to 0.30 and 32 to 0.15, close to the 0.10 of random guessing. At length 16, growing the hidden vector from 16 to 64 to 128 lifts accuracy from 0.20 to 0.56 to 0.87. Everything the decoder will ever know about the input has to pass through that one fixed-size vector, the encoder's last state, which is also overwritten at every step. The longer the input, the more must be crammed in and the more is lost. This is the bottleneck problem of the plain encoder-decoder, and it is exactly what the attention mechanism of Week 9 is invented to remove: instead of one vector, let the decoder look back at all the encoder states.

3.3Teacher forcing and exposure bias

How should the decoder be trained? At step $t$ it needs the previous token as input. Two choices: feed it its own previous prediction (what will happen at test time) or feed it the true previous token from the training data. Teacher forcing chooses the second: the decoder is "forced" to follow the teacher's answer, whatever it would have said itself. It makes training fast and stable, because an early mistake does not poison every later step. At inference there is no teacher, so the model's own outputs are fed back, always. (Never use teacher forcing at inference: there is no truth to feed.)

The price is a train-test mismatch called exposure bias: the model is only ever trained on perfect histories, then deployed on its own imperfect ones, so one early slip puts it in a situation it never practised, and errors can compound. The experiment shows the gap directly. At length 8 the decoder gets 0.92 of tokens right when fed the truth but 0.79 when fed itself; at length 16, 0.64 against 0.30; at length 32, 0.40 against 0.15. The same network, the same weights, tested the two ways. Remedies (beyond this course) include scheduled sampling (gradually feed the model its own outputs during training) and training objectives defined on the whole sequence.

3.4Chapter summary

• Encoder RNN reads the input to a context vector; decoder RNN starts from it and writes the output token by token until <eos>.
• Bottleneck: one fixed vector for the whole input. Measured free-running copy accuracy at hidden 32: 0.997, 0.79, 0.30, 0.15 for length 4, 8, 16, 32; hidden 16, 64, 128 at length 16: 0.20, 0.56, 0.87. Fix: attention (Week 9).
• Teacher forcing in training only (fast, stable); at inference feed own outputs. The mismatch (exposure bias) is visible: 0.92 against 0.79 at length 8.

Training gives a decoder that, at each step, outputs a probability for every word in the vocabulary. Decoding is the separate question of how to turn those probabilities into a sentence, and evaluation is how to judge the sentence. Both are exam favourites.

4.1Greedy decoding and its trap

Greedy decoding picks the most probable word at every step. It is fast, but the best first word is not always part of the best sentence: a likely start can lead to a dead end where the model is unsure of everything that follows.

4.2Beam search

Beam search keeps the $k$ best partial sentences (the beam width) at each step, scored by their total log-probability, extends each by every possible next word, and prunes back to the best $k$. $k=1$ is greedy decoding; $k=\infty$ is exhaustive search; practical values are 4 to 10. It is not guaranteed to find the best sequence, only a good one. Code it, and run the notes' example (vocabulary $\{a,b,c,d\}$, $k=2$) and a case built so that greedy fails:

import math

def beam_search(step_probs, k, length_norm=False, max_len=3, eos=None):
    """step_probs(prefix) -> {token: probability}. Keep the k best prefixes by total log-probability at every step."""
    beams = [((), 0.0)]
    for _ in range(max_len):
        candidates = []
        for prefix, score in beams:
            if eos is not None and prefix and prefix[-1] == eos:
                candidates.append((prefix, score)); continue                  # a finished hypothesis stays as it is
            for tok, p in step_probs(prefix).items():
                candidates.append((prefix + (tok,), score + math.log(p)))
        norm = (lambda c: c[1] / len(c[0])) if length_norm else (lambda c: c[1])
        beams = sorted(candidates, key=norm, reverse=True)[:k]
    return beams

# --- the worked example from the notes: vocabulary {a, b, c, d}, beam width 2 -------------------------------
table = {(): {"a": 0.4, "b": 0.3, "c": 0.2, "d": 0.1},
         ("a",): {"a": 0.2, "c": 0.6, "b": 0.1, "d": 0.1},
         ("b",): {"a": 0.3, "d": 0.5, "b": 0.1, "c": 0.1}}
step = lambda prefix: table.get(prefix, {"a": 0.25, "b": 0.25, "c": 0.25, "d": 0.25})
print("notes' example, k=2, after 2 steps:")
for prefix, score in beam_search(step, k=2, max_len=2):
    print("   ", "".join(prefix), "probability", round(math.exp(score), 3))

# --- a case where the greedy choice is a trap ----------------------------------------------------------------
trap = {(): {"a": 0.5, "b": 0.4, "c": 0.1},
        ("a",): {"x": 0.3, "y": 0.3, "z": 0.4},                   # after 'a' the model is unsure: its best next word has 0.4
        ("b",): {"x": 0.9, "y": 0.05, "z": 0.05},                 # after 'b' it is almost certain
        ("c",): {"x": 0.34, "y": 0.33, "z": 0.33}}
step = lambda prefix: trap[prefix]
print("\nthe trap: P(a)=0.5, P(b)=0.4 at step 1, but 'b' is followed by x with probability 0.9")
for k in (1, 2, 3):
    best = beam_search(step, k=k, max_len=2)[0]
    print(f"   beam width {k}: best sequence {''.join(best[0])} with probability {math.exp(best[1]):.3f}" + ("   <- greedy decoding" if k == 1 else ""))
exhaustive = max(((p1 + (t2,), math.log(trap[()][p1[0]] * trap[p1][t2])) for p1 in [("a",), ("b",), ("c",)] for t2 in trap[p1]), key=lambda c: c[1])
print(f"   exhaustive search (all 9 sequences): {''.join(exhaustive[0])} with probability {math.exp(exhaustive[1]):.3f}")

notes' example, k=2, after 2 steps:
    ac probability 0.24
    bd probability 0.15

the trap: P(a)=0.5, P(b)=0.4 at step 1, but 'b' is followed by x with probability 0.9
   beam width 1: best sequence az with probability 0.200   <- greedy decoding
   beam width 2: best sequence bx with probability 0.360
   beam width 3: best sequence bx with probability 0.360
   exhaustive search (all 9 sequences): bx with probability 0.360

The notes' example reproduces: ac with 0.24 and bd with 0.15 are the two survivors. In the trap, greedy ($k=1$) picks a because 0.5 beats 0.4, then the best that follows is only 0.4, ending at 0.20. With $k=2$ the beam also keeps b, finds that it is followed by x with probability 0.9, and returns 0.36, the same as the exhaustive search over all 9 sequences. Bigger beams cost more time and memory, roughly $k$ times, and the gains flatten quickly.

Length normalisation

There is a hidden bias. A sentence's probability is a product of per-word probabilities, each below 1, so every extra word lowers the total and beam search drifts toward short outputs. The standard fix is to score by the length-normalised log-probability, $\tfrac1{|y|}\sum_t\log P(y_t\mid\ldots)$ (the notes say "normalized by sequence length"). A model where an early <eos> is cheap shows the bias:

import math

# every extra word costs probability, so a plain product of probabilities favours SHORT outputs
def step(prefix):
    table = {(): {"ok": 0.5, "the": 0.5},
             ("ok",): {"<eos>": 1.0},
             ("the",): {"cat": 0.95, "dog": 0.05},
             ("the", "cat"): {"sat": 0.95, "ran": 0.05},
             ("the", "cat", "sat"): {"down": 0.95, "up": 0.05},
             ("the", "cat", "sat", "down"): {"<eos>": 0.95, "now": 0.05}}
    return table.get(prefix, {"<eos>": 1.0})

def beam(k, normalise, steps=6):
    key = (lambda c: c[1] / len(c[0])) if normalise else (lambda c: c[1])
    beams = [((), 0.0)]
    for _ in range(steps):
        cand = []
        for prefix, score in beams:
            if prefix and prefix[-1] == "<eos>":
                cand.append((prefix, score)); continue                  # a finished sentence stays as it is
            for tok, p in step(prefix).items():
                cand.append((prefix + (tok,), score + math.log(p)))
        beams = sorted(cand, key=key, reverse=True)[:k]
    return max(beams, key=key)

for normalise in (False, True):
    seq, score = beam(3, normalise)
    print(f"{'with   ' if normalise else 'without'} length normalisation: {' '.join(seq):24s} probability {math.exp(score):.3f}   log-prob per word {score / len(seq):6.3f}")
print("'ok <eos>' has the larger TOTAL probability (0.50 against 0.41) but every word of the long sentence is more certain (-0.18 against -0.35 per word)")

without length normalisation: ok <eos>                 probability 0.500   log-prob per word -0.347
with    length normalisation: the cat sat down <eos>   probability 0.407   log-prob per word -0.180
'ok <eos>' has the larger TOTAL probability (0.50 against 0.41) but every word of the long sentence is more certain (-0.18 against -0.35 per word)

Without normalisation the beam returns ok <eos> (total probability 0.50) because the long sentence's total, 0.41, is lower, although every word of the long sentence is more certain ($-0.18$ against $-0.35$ per word). With normalisation it returns the long sentence.

4.3BLEU: judging a translation

How good is "the cat sat on the mat" as a translation of the reference "the cat is on the mat"? BLEU (Bilingual Evaluation Understudy) compares the machine output to one or more human references by n-gram precision: what fraction of the output's 1-grams, 2-grams, 3-grams and 4-grams also appear in the reference. Two details make it work.

• Clipped precision. An output n-gram is credited at most as many times as it occurs in the reference. Otherwise "the the the the the the" would score 100%.
• Brevity penalty (BP). Precision alone rewards short outputs (say only the one word you are sure of), so outputs shorter than the reference are penalised.

import math
from collections import Counter

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

def precision(hyp, ref, n):
    h, r = ngrams(hyp, n), ngrams(ref, n)
    clipped = sum(min(c, r[g]) for g, c in h.items())             # a hypothesis n-gram counts at most as often as it occurs in the reference
    return clipped, max(sum(h.values()), 1)

def bleu(hyp, ref, max_n=4):
    ps = []
    for n in range(1, max_n + 1):
        num, den = precision(hyp, ref, n); ps.append(num / den)
    bp = 1.0 if len(hyp) > len(ref) else math.exp(1 - len(ref) / len(hyp))      # brevity penalty
    geo = math.exp(sum(math.log(p) for p in ps) / max_n) if min(ps) > 0 else 0.0
    return bp * geo, ps, bp

ref = "the cat is on the mat".split()
cases = {"perfect": "the cat is on the mat",
         "one word wrong": "the cat sat on the mat",
         "word salad, same words": "mat the on is cat the",
         "all 'the'": "the the the the the the",
         "too short": "the cat"}
print("reference: 'the cat is on the mat'")
for name, text in cases.items():
    score, ps, bp = bleu(text.split(), ref)
    score2 = bleu(text.split(), ref, 2)[0]
    print(f"{name:24s} precisions 1..4 = {[round(p, 2) for p in ps]}  brevity penalty {bp:.2f}  BLEU-2 = {score2:.3f}  BLEU-4 = {score:.3f}")
c, t = precision("the the the the the the".split(), ref, 1)
print("one short sentence is a harsh test for BLEU-4 (no matching 4-gram means 0); real BLEU is computed over a whole corpus")
print(f"\nwithout clipping, 'the the the the the the' would have unigram precision 6/6; clipped it is {c}/{t} (the reference has 'the' only twice)")

reference: 'the cat is on the mat'
perfect                  precisions 1..4 = [1.0, 1.0, 1.0, 1.0]  brevity penalty 1.00  BLEU-2 = 1.000  BLEU-4 = 1.000
one word wrong           precisions 1..4 = [0.83, 0.6, 0.25, 0.0]  brevity penalty 1.00  BLEU-2 = 0.707  BLEU-4 = 0.000
word salad, same words   precisions 1..4 = [1.0, 0.0, 0.0, 0.0]  brevity penalty 1.00  BLEU-2 = 0.000  BLEU-4 = 0.000
all 'the'                precisions 1..4 = [0.33, 0.0, 0.0, 0.0]  brevity penalty 1.00  BLEU-2 = 0.000  BLEU-4 = 0.000
too short                precisions 1..4 = [1.0, 1.0, 0.0, 0.0]  brevity penalty 0.14  BLEU-2 = 0.135  BLEU-4 = 0.000
one short sentence is a harsh test for BLEU-4 (no matching 4-gram means 0); real BLEU is computed over a whole corpus

without clipping, 'the the the the the the' would have unigram precision 6/6; clipped it is 2/6 (the reference has 'the' only twice)

Read the rows. The perfect copy scores 1. "the cat sat on the mat" keeps unigram precision 0.83 (5 of 6 words) and bigram precision 0.60, so BLEU-2 is a respectable 0.707, but no 4-gram of the output is in the reference, so BLEU-4 is 0 (on one sentence; real BLEU is computed over a whole corpus, where such zeros average out). "mat the on is cat the" has all the right words, unigram precision 1.0, and scores 0: BLEU rewards matching order, not just vocabulary. "the the the the the the" is clipped to 2/6, and "the cat" gets a brevity penalty of 0.14. BLEU is cheap and correlates with human judgement on average, but it ignores meaning (a good paraphrase scores badly) and treats all words as equally important.

4.4Chapter summary

• Greedy takes the best word each step and can fall into a trap (0.20); beam search keeps the $k$ best partial sentences (found 0.36 = the exhaustive optimum at $k=2$); $k=1$ is greedy.
• Normalise by length or beam search prefers short outputs (0.50 short against 0.41 long, yet the long one is better per word).
• BLEU = brevity penalty times the geometric mean of clipped n-gram precisions; order matters (word salad scores 0).

What is likely to be asked from Week 8, with 30-second answers, deeper explanations, a lecture-or-extra tag on each question, and code you can run.

Week 8 questions are about the gated variants, how sequences are read in both directions, and how an encoder-decoder produces and is judged on its output. Each answer starts with a 30-second version. Questions are tagged From the notes or Extra.

5.1Interview heat-map: what is most likely

5.2GRU and bidirectional RNNs

hand-written GRU matches nn.GRU: True
gate values at the last step: reset [0.65, 0.59, 0.3, 0.29]  update [0.82, 0.46, 0.61, 0.32]

update gate forced to ~1 (keep)           max |h_T - h_0| = 0.000000
update gate forced to ~0 (overwrite)      max |h_T - h_0| = 1.829469
update gate ~1: final state for two DIFFERENT inputs differs by 0.000000
update gate ~0: final state for two DIFFERENT inputs differs by 0.637222
z ~ 1 copies the old state through every step (the input is ignored); z ~ 0 replaces it by the new candidate each step

parameters for d=10, h=20:  RNN 640,  GRU 1920,  LSTM 2560   (GRU = 3x RNN, LSTM = 4x)
GRU has ONE state vector (h); the LSTM has two (h and c)

per-token accuracy (chance = 0.20)            unidirectional   bidirectional
  tag each position with the PREVIOUS token            1.00            1.00
  tag each position with the NEXT token                0.20            1.00

bidirectional GRU output: (3, 10, 64) = (batch, T, 2*hidden): forward and backward states concatenated;  final states: (2, 3, 32)

5.3Encoder-decoder

sequence length  hidden   teacher-forced acc   free-running acc   whole sequence exact
         4          32            0.998               0.997               0.993
         8          32            0.921               0.794               0.514
        16          32            0.641               0.303               0.000
        32          32            0.396               0.147               0.000

sequence length  hidden   teacher-forced acc   free-running acc   whole sequence exact
         4          32            0.998               0.997               0.993
         8          32            0.921               0.794               0.514
        16          32            0.641               0.303               0.000

5.4Decoding and evaluation

notes' example, k=2, after 2 steps:
    ac probability 0.24
    bd probability 0.15

the trap: P(a)=0.5, P(b)=0.4 at step 1, but 'b' is followed by x with probability 0.9
   beam width 1: best sequence az with probability 0.200   <- greedy decoding
   beam width 2: best sequence bx with probability 0.360
   beam width 3: best sequence bx with probability 0.360
   exhaustive search (all 9 sequences): bx with probability 0.360

without length normalisation: ok <eos>                 probability 0.500   log-prob per word -0.347
with    length normalisation: the cat sat down <eos>   probability 0.407   log-prob per word -0.180
'ok <eos>' has the larger TOTAL probability (0.50 against 0.41) but every word of the long sentence is more certain (-0.18 against -0.35 per word)

reference: 'the cat is on the mat'
perfect                  precisions 1..4 = [1.0, 1.0, 1.0, 1.0]  brevity penalty 1.00  BLEU-2 = 1.000  BLEU-4 = 1.000
one word wrong           precisions 1..4 = [0.83, 0.6, 0.25, 0.0]  brevity penalty 1.00  BLEU-2 = 0.707  BLEU-4 = 0.000
word salad, same words   precisions 1..4 = [1.0, 0.0, 0.0, 0.0]  brevity penalty 1.00  BLEU-2 = 0.000  BLEU-4 = 0.000
all 'the'                precisions 1..4 = [0.33, 0.0, 0.0, 0.0]  brevity penalty 1.00  BLEU-2 = 0.000  BLEU-4 = 0.000
too short                precisions 1..4 = [1.0, 1.0, 0.0, 0.0]  brevity penalty 0.14  BLEU-2 = 0.135  BLEU-4 = 0.000
one short sentence is a harsh test for BLEU-4 (no matching 4-gram means 0); real BLEU is computed over a whole corpus

without clipping, 'the the the the the the' would have unigram precision 6/6; clipped it is 2/6 (the reference has 'the' only twice)

logits = model(x)[:, -1]                        # scores for the next token
probs = torch.softmax(logits / temperature, -1)
next_token = torch.multinomial(probs, 1)             # sample; temperature < 1 sharpens, > 1 flattens

Week 8 on one page: chapter glance, the GRU equations, the pairs to tell apart, a decoding comparison, a checklist and corrections to the source notes.

6.1Week 8 at a glance

6.2GRU and LSTM side by side

6.3Key terms

6.4The pairs you must tell apart

6.5Last-minute checklist

6.6Corrections and additions to the source notes