Sequence Models

Question 1

(a) [4] Since $h_t=\tanh(a_t)$ with $a_t=Wh_{t-1}+Ux_t+b$, by chain rule $\frac{\partial h_t}{\partial h_{t-1}} = \operatorname{diag}(\tanh'(a_t))\,W = D_t W,\quad D_t=\operatorname{diag}(1-\tanh^2(a_t)).$ (2) Loss gradient telescopes: $\frac{\partial L}{\partial h_k}=\frac{\partial L}{\partial h_T}\prod_{t=k+1}^{T}\frac{\partial h_t}{\partial h_{t-1}}=\frac{\partial L}{\partial h_T}\prod_{t=k+1}^{T}D_tW.$ (2)

(b) [6] Submultiplicativity of the spectral norm: $\|AB\|\le\|A\|\|B\|$. Applying to the product: $\Big\|\prod_{t=k+1}^{T}D_tW\Big\|\le\prod_{t=k+1}^{T}\|D_t\|\,\|W\|.$ (3) Since $\tanh'\in(0,1]$, $\|D_t\|\le1$. Hence if $\|W\|<1$ the bound is $\le\|W\|^{T-k}\to0$: sufficient condition $\|W\|<1$ gives geometric contraction (vanishing). (2) Necessary (non-vanishing) condition: the largest singular value $\sigma_{\max}(W)\ge1$ (and the $D_t$ not too small), otherwise the product norm is bounded above by $\|W\|^{T-k}<1$ decaying to $0$. (1)

(c) [4] Scalar factor per step $=\tanh'(a_t)\cdot w = 0.8\times0.5 = 0.4$. (2) Over 10 steps: $0.4^{10}=1.048576\times10^{-4}\approx1.05\times10^{-4}$. (1) This is $\ll1$, so the gradient vanishes. (1)

(d) [6] $c_t=f_t\odot c_{t-1}+i_t\odot\tilde c_t$. Treating $f_t,i_t,\tilde c_t$ as constants w.r.t. $c_{t-1}$ (ignoring gate dependence), $\frac{\partial c_t}{\partial c_{t-1}}=\operatorname{diag}(f_t).$ (3) The product over time is $\prod_t\operatorname{diag}(f_t)$; if $f_t\approx1$ the product stays near $1$, so gradients neither vanish nor explode — a constant error carousel. The tanh path instead multiplies by $D_tW$ with $\|D_t\|\le1$ and $\|W\|$ typically $<1$, giving geometric decay. (3)

Question 2

(a) [6]

• Computational: Bahdanau requires a small MLP ($v,W_a,U_a$, a tanh) per (query,key) pair — more parameters/FLOPs; Luong dot-product has no extra parameters and is cheaper/parallelisable. (2)
• Representational: additive scoring can align keys/queries of different subspaces and is more expressive for small dims; dot-product assumes query and key live in the same space and scale. (2)
• Bahdanau computes attention using $s_{t-1}$ because the context is fed into the RNN cell to produce $s_t$ (attention precedes the recurrence). Luong computes attention with $s_t$ because it applies attention after the RNN update, then combines context with $s_t$. (2)

(b) [4] Softmax $\alpha_i=e^{e_i}/\sum_m e^{e_m}$. $\frac{\partial\alpha_i}{\partial e_j}=\alpha_i(\delta_{ij}-\alpha_j),$ i.e. $\operatorname{diag}(\alpha)-\alpha\alpha^\top$. Derivation: for $i=j$, quotient rule gives $\alpha_i-\alpha_i^2$; for $i\ne j$, $-\alpha_i\alpha_j$. (4)

(c) [6] Exponentials: $e^2=7.389,\;e^1=2.718,\;e^0=1$. Sum $=11.107$. (2) $\alpha_1=7.389/11.107=0.665$, $\alpha_2=2.718/11.107=0.245$, $\alpha_3=1/11.107=0.090$. (3) Sum $=0.665+0.245+0.090=1.000$. Context $c=0.665\,h_1+0.245\,h_2+0.090\,h_3$. (1)

(d) [6] If $e_j=e$ for all $j$: $\alpha_j=e^{e}/(S e^{e})=1/S$, so $c=\frac1S\sum h_j$, uniform average. (3) This is the maximum-entropy / least-committal distribution — with no evidence favouring any position, equal weight avoids bias. (1) Let $e_{(1)}$ be the max with gap $\Delta=e_{(1)}-e_{(2)}\to\infty$. Then $\alpha_{(1)}=1/(1+\sum_{j\ne(1)}e^{-(e_{(1)}-e_j)})\to1/(1+0)=1$, all others $\to0$: attention selects a single position — hard attention / $\arg\max$. (2)

Question 3

(a) [4] From $k$ live hypotheses each is extended by every token in $V$, giving $k\cdot|V|$ candidates. Score each by (length-normalised) cumulative log-prob; keep the top $k$ overall as the new beam. (2) We sum log-probabilities because the joint probability is a product $\prod_t P(y_t\mid\cdot)$; multiplying many probabilities $\in(0,1)$ underflows numerically and log turns it into a numerically stable sum. (2)

(b) [8] Joint probabilities:

• $AA = 0.6\times0.7 = 0.42$
• $AB = 0.6\times0.3 = 0.18$
• $BA = 0.4\times0.5 = 0.20$
• $BB = 0.4\times0.5 = 0.20$ (4)

Sorted: $AA(0.42) > BA(0.20)=BB(0.20) > AB(0.18)$. Beams kept after step 2 (top 2): $\{AA=0.42,\; BA=0.20\}$ (ties broken to $BA$; $BB=0.20$ equally valid). (3) Most probable sequence: $AA$ with $0.42$. (1)

(c) [6] Per step we score $k|V|$ candidates and re-select top-$k$ (cost $O(k|V|\log k)$ or $O(k|V|)$); over $L$ steps total $O(L\,k\,|V|)$ (plus decoder forward passes). (2) Exhaustive search is $O(|V|^L)$ — exponential; greedy is the $k=1$ special case, cheapest but no back-up hypotheses. (2) Length-normalisation (dividing log-prob by length, or length$^\alpha$) is applied before final ranking because raw joint log-prob is a sum of negative terms that grows in magnitude with length, biasing beam search toward shorter sequences; normalising makes hypotheses of different lengths comparable. (2)

[
  {"claim":"Q1c gradient factor 0.4^10 approx 1.048576e-4",
   "code":"val=(Rational(8,10)*Rational(5,10))**10; result=abs(float(val)-1.048576e-4)<1e-9"},
  {"claim":"Q2c softmax weights of (2,1,0) sum to 1 and alpha1 approx 0.665",
   "code":"import math; e=[math.exp(2),math.exp(1),math.exp(0)]; s=sum(e); a=[x/s for x in e]; result=(abs(sum(a)-1)<1e-9) and (abs(a[0]-0.665)<1e-3)"},
  {"claim":"Q3b joint probabilities AA=0.42 max, AB=0.18",
   "code":"AA=Rational(6,10)*Rational(7,10); AB=Rational(6,10)*Rational(3,10); BA=Rational(4,10)*Rational(5,10); result=(AA==Rational(42,100)) and (AB==Rational(18,100)) and (AA>BA) and (AA>AB)"},
  {"claim":"Q2b softmax Jacobian diagonal entry equals alpha_i(1-alpha_i)",
   "code":"a1=symbols('a1'); result=simplify(a1*(1-a1)-(a1-a1**2))==0"}
]