Level 3 — ProductionSequence Models

Sequence Models

⏱ 45 minutes60 marksprintable — key stays hidden on paper

Chapter: 3.5 Sequence Models Level: 3 — Production (from-scratch derivations, code-from-memory, explain-out-loud) Time limit: 45 minutes Total marks: 60

Instructions: Show all derivations. Where code is asked, pseudocode/NumPy-style from memory is acceptable if logic is correct. Use $...$ notation for math.

Question 1 — RNN forward + BPTT gradient (12 marks)

Consider a vanilla RNN with hidden update $h_t = \tanh(W_{hh} h_{t-1} + W_{xh} x_t + b), \qquad \hat{y}_t = W_{hy} h_t$

(a) Write the forward recurrence and state the shapes of $W_{hh}, W_{xh}, W_{hy}$ given input dim $d$ , hidden dim $n$ , output dim $m$ . (3)

(b) For scalar loss $L = \sum_t L_t$ , derive $\dfrac{\partial L}{\partial W_{hh}}$ using backpropagation through time. Include the recursive expression for $\dfrac{\partial L}{\partial h_t}$ . (6)

Question 2 — Vanishing gradients derivation (10 marks)

(a) Starting from $\dfrac{\partial h_t}{\partial h_k} = \prod_{i=k+1}^{t} \dfrac{\partial h_i}{\partial h_{i-1}}$ , give a bound on its norm in terms of the largest singular value $\gamma$ of $W_{hh}$ and $\tanh'$ bound. (4)

(b) State the precise condition on $\gamma$ (with $\tanh$ ) that guarantees vanishing gradients, and explain why. (3)

Question 3 — LSTM vs GRU from memory (12 marks)

(a) Write ALL LSTM gate equations (forget, input, candidate, cell update, output, hidden). (6)

(b) Write ALL GRU equations (update, reset, candidate, hidden). (4)

(c) Explain in one sentence each: why the LSTM additive cell path mitigates vanishing gradients, and how GRU differs in parameter count/structure. (2)

Question 4 — Attention mechanism (12 marks)

(a) Given encoder states $\{h_1,\dots,h_T\}$ and decoder state $s_{t-1}$ , write the general attention pipeline: score → weights → context vector. (4)

(b) Give the Bahdanau (additive) score and the Luong (multiplicative/dot) score formulas, and state one architectural difference between how they use the decoder state. (5)

(c) Compute attention weights: scores $e = [2, 1, 0]$ . Give the softmax weights (to 3 dp) and the resulting context if $h_1=[1,0], h_2=[0,1], h_3=[1,1]$ . (3)

Question 5 — Seq2seq, teacher forcing, beam search (10 marks)

(a) Draw/describe the encoder–decoder architecture and explain teacher forcing vs free-running decoding, plus one risk of teacher forcing. (4)

(b) Beam search with beam width $k=2$ . At step 1 vocab log-probs are $A:-0.5, B:-1.0, C:-2.0$ . From $A$ : next $\{X:-0.4, Y:-1.2\}$ ; from $B$ : next $\{X:-0.3, Y:-0.7\}$ . List surviving beams after step 2 with cumulative log-probs, ranked. (6)

Question 6 — Word embeddings + variable-length (4 marks)

(a) State the training objective difference between Word2Vec skip-gram and GloVe. (2)

(b) Explain padding + masking for variable-length batches in one sentence, and why masking matters for the loss. (2)

Answer keyMark scheme & solutions

Question 1 (12)

(a) Forward: $h_t = \tanh(W_{hh}h_{t-1} + W_{xh}x_t + b)$ , $\hat y_t = W_{hy}h_t$ , with $h_0=0$ . (1) Shapes: $W_{hh}\in\mathbb{R}^{n\times n}$ , $W_{xh}\in\mathbb{R}^{n\times d}$ , $W_{hy}\in\mathbb{R}^{m\times n}$ . (2, 1 each pair-set)

(b) Let $\delta_t = \partial L/\partial h_t$ . Since $h_t$ affects $L_t$ (via $\hat y_t$ ) and $h_{t+1}$ : $\delta_t = W_{hy}^\top \frac{\partial L_t}{\partial \hat y_t} + \Big(\frac{\partial h_{t+1}}{\partial h_t}\Big)^\top \delta_{t+1}$ (3) With $z_t = W_{hh}h_{t-1}+W_{xh}x_t+b$ , $\partial L/\partial z_t = \delta_t \odot (1-h_t^2)$ . Then $\frac{\partial L}{\partial W_{hh}} = \sum_{t} \big(\delta_t \odot (1-h_t^2)\big)\, h_{t-1}^\top$ (3) — summed over all timesteps because $W_{hh}$ is shared.

(c) $h_t=\tanh(z_t)$ , $\partial h_t/\partial z_t = \operatorname{diag}(1-h_t^2)$ ; $\partial z_t/\partial h_{t-1}=W_{hh}$ ; chain gives $\operatorname{diag}(1-h_t^2)W_{hh}$ . (3)

Question 2 (10)

(a) $\left\|\frac{\partial h_t}{\partial h_k}\right\| \le \prod_{i=k+1}^{t}\|\operatorname{diag}(1-h_i^2)\|\,\|W_{hh}\| \le (\beta \gamma)^{t-k}$ where $\beta = \max|\tanh'|=1$ , $\gamma=\sigma_{max}(W_{hh})$ . So bound $\le \gamma^{t-k}$ . (4)

(b) Vanishing if $\gamma < 1$ (more precisely $\gamma\cdot\beta<1$ with $\beta\le1$ , so $\gamma<1$ suffices): the product $\gamma^{t-k}\to0$ exponentially as $t-k$ grows, so gradients from distant timesteps vanish. (3)

(c) Fixes: LSTM/GRU gating (additive cell path); residual/skip connections; and training-time: gradient clipping (also helps exploding), or good init (orthogonal $W_{hh}$ ). (3)

Question 3 (12)

(a) (6, 1 each) $f_t=\sigma(W_f[h_{t-1},x_t]+b_f)$ $i_t=\sigma(W_i[h_{t-1},x_t]+b_i)$ $\tilde c_t=\tanh(W_c[h_{t-1},x_t]+b_c)$ $c_t=f_t\odot c_{t-1}+i_t\odot\tilde c_t$ $o_t=\sigma(W_o[h_{t-1},x_t]+b_o)$ $h_t=o_t\odot\tanh(c_t)$

(b) (4, 1 each) $z_t=\sigma(W_z[h_{t-1},x_t]),\quad r_t=\sigma(W_r[h_{t-1},x_t])$ $\tilde h_t=\tanh(W_h[r_t\odot h_{t-1},x_t])$ $h_t=(1-z_t)\odot h_{t-1}+z_t\odot\tilde h_t$

(c) LSTM: $c_t=f_t\odot c_{t-1}+\dots$ gives a near-identity additive path so gradient $\partial c_t/\partial c_{t-1}\approx f_t$ avoids repeated multiplicative shrink. GRU: fewer gates (2 vs 3), no separate cell state → fewer parameters. (2)

Question 4 (12)

(a) (4) Score $e_{tj}=\text{score}(s_{t-1},h_j)$ ; weights $\alpha_{tj}=\dfrac{\exp(e_{tj})}{\sum_k\exp(e_{tk})}$ ; context $c_t=\sum_j\alpha_{tj}h_j$ .

(b) (5) Bahdanau (additive): $e_{tj}=v^\top\tanh(W_s s_{t-1}+W_h h_j)$ . Luong (dot): $e_{tj}=s_t^\top h_j$ (or $s_t^\top W h_j$ general). Difference: Bahdanau uses previous state $s_{t-1}$ to compute attention before generating $s_t$ ; Luong uses the current state $s_t$ after the RNN step. (2 formulas, 2 formulas, 1 diff)

(c) (3) softmax of $[2,1,0]$ : denom $e^2+e^1+e^0=7.389+2.718+1=11.107$ ; weights $\approx[0.665,0.245,0.090]$ . Context $=0.665[1,0]+0.245[0,1]+0.090[1,1]=[0.755,0.335]$ .

Question 5 (10)

(a) (4) Encoder RNN compresses input into context (final hidden state); decoder RNN generates output conditioned on context, feeding previous token as input. Teacher forcing: feed ground-truth previous token during training; free-running: feed model's own prediction. Risk: exposure bias — train/inference mismatch degrades inference.

(b) (6) Step-2 cumulative log-probs:

A→X: $-0.5-0.4=-0.9$
A→Y: $-0.5-1.2=-1.7$
B→X: $-1.0-0.3=-1.3$
B→Y: $-1.0-0.7=-1.7$

Keep top $k=2$ : A→X ( $-0.9$ ), B→X ( $-1.3$ ). (4 computation, 2 selection/ranking)

Question 6 (4)

(a) (2) Skip-gram: predict context words from center word (local, softmax/negative sampling). GloVe: factorize/fit log co-occurrence counts globally, minimizing weighted least-squares on $w_i^\top w_j + b_i+b_j - \log X_{ij}$ .

(b) (2) Pad shorter sequences to max length with a pad token; a boolean mask zeros out padded positions so padding doesn't contribute to loss/attention — otherwise the model would learn from meaningless pad tokens.

[
  {"claim":"Softmax of [2,1,0] weights approx [0.665,0.245,0.090]","code":"e=[exp(2),exp(1),exp(0)];s=sum(e);w=[float(x/s) for x in e];result=all(abs(a-b)<1e-2 for a,b in zip(w,[0.665,0.245,0.090]))"},
  {"claim":"Attention context = [0.755,0.335]","code":"e=[exp(2),exp(1),exp(0)];s=sum(e);w=[x/s for x in e];h=[[1,0],[0,1],[1,1]];c=[sum(w[j]*h[j][d] for j in range(3)) for d in range(2)];result=all(abs(float(a)-b)<1e-2 for a,b in zip(c,[0.755,0.335]))"},
  {"claim":"Beam step-2 survivors are A-X(-0.9) and B-X(-1.3)","code":"cands={'AX':-0.5-0.4,'AY':-0.5-1.2,'BX':-1.0-0.3,'BY':-1.0-0.7};top=sorted(cands,key=lambda k:-cands[k])[:2];result=set(top)=={'AX','BX'} and abs(cands['AX']+0.9)<1e-9 and abs(cands['BX']+1.3)<1e-9"},
  {"claim":"Vanishing gradient product gamma=0.9 over 20 steps is tiny","code":"result=(Rational(9,10)**20) < Rational(1,10)"}
]