Appendix C
Hints and Solutions
Solutions to selected exercises. Try each exercise seriously before reading its solution; the struggle is where the learning happens. Exercise numbers refer to the chapter’s own numbering.
C.1Part I: Foundations
1.3 Substituting $b=\bar y-w\bar x$ gives $\sum_i\big(w(x_i-\bar x)-(y_i-\bar y)\big)x_i=0$. Because $\sum_i(x_i-\bar x)=0$ we may replace $x_i$ by $x_i-\bar x$ in the outer factor, so $w\sum_i(x_i-\bar x)^2=\sum_i(x_i-\bar x)(y_i-\bar y)$.
1.5 The derivative of $\sum_i|y_i-c|$ (where it exists) is the number of labels below $c$ minus the number above $c$. It changes sign at a median, which is therefore a minimizer. Under squared error the minimizer is the mean $\bar y$.
2.1 $\norm\vx=(\vx\T\vx)^{1/2}$, so by the chain rule $\nabla\norm\vx=\frac12(\vx\T\vx)^{-1/2}\cdot2\vx=\vx/\norm\vx$. At $\mathbf 0$ the function has a cone-shaped kink and is not differentiable.
2.4 With 20% spam: flagged legitimate mail $=0.01\times0.8=0.008$, flagged spam $=0.98\times0.2=0.196$, so $0.008/0.204\approx3.9\%$ of flagged mail is legitimate. With 2% spam: $0.0098/(0.0098+0.0196)\approx33\%$. The rarer the positive class, the worse the precision at a fixed false-positive rate.
2.5 $\ell(\lambda)=n\log\lambda-\lambda\sum_ix_i$, so $\ell'(\lambda)=n/\lambda-\sum_ix_i=0$ gives $\hat\lambda=1/\bar x$.
2.6 $D_{\mathrm{KL}}(p\Vert q)=0.9\ln1.8+0.1\ln0.2\approx0.368$ nats and $D_{\mathrm{KL}}(q\Vert p)=0.5\ln(5/9)+0.5\ln5\approx0.511$ nats. They differ.
3.2 Each step multiplies $w-c$ by $r=1-\eta\lambda$, so $w_t-c=r^t(w_0-c)$. We need $|r|^t\le10^{-6}$, i.e. $t\ge\ln10^{-6}/\ln|r|$. For $\eta\lambda=0.1$ and for $\eta\lambda=1.9$, $|r|=0.9$ and $t\ge13.82/0.1054\approx131.1$, so 132 steps; in the second case the iterates alternate in sign.
3.3 $\max_j|1-\eta\lambda_j|=\max(|1-\eta\lambda_{\min}|,|1-\eta\lambda_{\max}|)$. The first term decreases and the second increases in $\eta$ (for the relevant range), so the maximum is smallest where they are equal: $1-\eta\lambda_{\min}=\eta\lambda_{\max}-1$, giving $\eta^\star=2/(\lambda_{\min}+\lambda_{\max})$ and value $(\lambda_{\max}-\lambda_{\min})/(\lambda_{\max}+\lambda_{\min})=(\kappa-1)/(\kappa+1)$.
3.4 The Hessian is $2\mX\T\mX$, and $\vv\T\mX\T\mX\vv=\norm{\mX\vv}^2\ge0$.
3.8 $f'(\theta)=\tanh\theta$ and $f''(\theta)=1/\cosh^2\theta$, so the step is $\tanh\theta\cosh^2\theta=\sinh\theta\cosh\theta=\frac12\sinh2\theta$. Iterating numerically shows convergence for $|\theta_0|<1.0887$ and divergence beyond. On $\theta^4/4$, $f'/f''=\theta^3/(3\theta^2)=\theta/3$, so $\theta_{t+1}=\frac23\theta_t$: the curvature vanishes at the minimum, the quadratic model is poor there, and the error shrinks only by a constant factor.
C.2Part II: Supervised Learning
4.1 $\mathbf H\T=\mX\big((\mX\T\mX)^{-1}\big)\T\mX\T=\mathbf H$ because $\mX\T\mX$ is symmetric, and $\mathbf H^2=\mX(\mX\T\mX)^{-1}(\mX\T\mX)(\mX\T\mX)^{-1}\mX\T=\mathbf H$. Then $(\mI-\mathbf H)^2=\mI-2\mathbf H+\mathbf H^2=\mI-\mathbf H$; it projects onto the orthogonal complement of the column space, where the residuals live.
4.4 $\hat\vw=(\mX\T\mX)^{-1}\mX\T(\mX\vw^\star+\vepsilon)=\vw^\star+(\mX\T\mX)^{-1}\mX\T\vepsilon$, so $\E\hat\vw=\vw^\star$ and $\Cov(\hat\vw)=(\mX\T\mX)^{-1}\mX\T(\sigma^2\mI)\mX(\mX\T\mX)^{-1}=\sigma^2(\mX\T\mX)^{-1}$. Nearly collinear features make $\mX\T\mX$ have tiny eigenvalues; its inverse has huge ones, so the weights have huge variance along those directions.
5.2 From $\mX\T(\mX\mX\T+\lambda\mI)=(\mX\T\mX+\lambda\mI)\mX\T$, multiply on the left by $(\mX\T\mX+\lambda\mI)^{-1}$ and on the right by $(\mX\mX\T+\lambda\mI)^{-1}$. The second form inverts an $n\times n$ matrix instead of $d\times d$, so it is cheaper when $n<d$; it is also the starting point of kernel methods.
5.4 The optimality condition is $0\in w-a+\lambda\,\partial|w|$, where $\partial|w|=\{\sign w\}$ for $w\ne0$ and $[-1,1]$ at $0$. For $w>0$: $w=a-\lambda$, valid if $a>\lambda$. For $w<0$: $w=a+\lambda$, valid if $a<-\lambda$. Otherwise $w=0$ satisfies the condition, since $a\in[-\lambda,\lambda]$.
6.1 The gradient is $\frac1n\sum_i(p_i-y_i)\vx_i$ and $\nabla_{\vw}p_i=p_i(1-p_i)\vx_i$, so the Hessian is $\frac1n\sum_ip_i(1-p_i)\vx_i\vx_i\T=\frac1n\mX\T\mathbf D\mX$. Since $p_i(1-p_i)\ge0$, $\vv\T\mX\T\mathbf D\mX\vv=\sum_ip_i(1-p_i)(\vx_i\T\vv)^2\ge0$.
6.4 Predicting positive costs $(1-p)c_{\mathrm{FP}}$ in expectation; predicting negative costs $p\,c_{\mathrm{FN}}$. Positive is better when $(1-p)c_{\mathrm{FP}}\le p\,c_{\mathrm{FN}}$, i.e. $p\ge c_{\mathrm{FP}}/(c_{\mathrm{FP}}+c_{\mathrm{FN}})$.
7.1 $\lambda e^{-\lambda y}=\exp(-\lambda y+\log\lambda)$, so $T(y)=y$, $\eta=-\lambda$, $b(y)=1$, and $a(\eta)=-\log(-\eta)$. Then $a'(\eta)=-1/\eta=1/\lambda=\E[y]$ and $a''(\eta)=1/\eta^2=1/\lambda^2=\Var[y]$. The canonical response is $h=-1/\eta$, which requires $\eta=\vtheta\T\vx<0$; in practice the log link $\E[y]=e^{\vtheta\T\vx}$ is used instead.
7.4 With only an intercept, $\ell(\theta_0)=\sum_i(y_i\theta_0-e^{\theta_0})+\text{const}$, so $\ell'(\theta_0)=\sum_iy_i-ne^{\theta_0}=0$ gives $\theta_0=\log\bar y$.
8.1 The side is $0.1^{1/d}$: $0.1$, $0.794$, and $0.977$ for $d=1,10,100$.
8.2 Each $x_j-x'_j\sim\Normal(0,2)$, so $(x_j-x'_j)^2=2Z^2$ with $Z$ standard normal: mean 2 and variance $4\Var(Z^2)=8$. Summing $d$ independent coordinates gives mean $2d$ and variance $8d$; the coefficient of variation is $\sqrt{8d}/(2d)=\sqrt{2/d}$.
9.1 Let $\vx_0$ be the projection of $\vx$ onto the hyperplane; then $\vx-\vx_0$ is parallel to $\vw$, say $\vx-\vx_0=t\,\vw/\norm\vw$. Applying $\vw\T\cdot+b$ and using $\vw\T\vx_0+b=0$ gives $\vw\T\vx+b=t\norm\vw$, so the distance is $|t|=|\vw\T\vx+b|/\norm\vw$.
9.3 $(x_1z_1+x_2z_2+1)^2=x_1^2z_1^2+x_2^2z_2^2+2x_1x_2z_1z_2+2x_1z_1+2x_2z_2+1$, so $\bm\phi(\vx)=(x_1^2,\,x_2^2,\,\sqrt2x_1x_2,\,\sqrt2x_1,\,\sqrt2x_2,\,1)$.
10.3 Each of the $n$ independent draws misses a given example with probability $1-1/n$, so all miss it with probability $(1-1/n)^n\to e^{-1}\approx0.368$.
10.4 $\partial\ell/\partial F=-y\,e^{-yF}/(1+e^{-yF})=-y\,\sigma(-yF)$. Boosting fits trees to $y\,\sigma(-yF)$: large for misclassified examples ($yF<0$), small for confidently correct ones.
11.1 Solve $2e^{-2\gamma^2n}\le\delta$ with $\gamma=0.02$ and $\delta=0.01$: $n\ge\log(200)/(2\cdot0.0004)\approx6{,}623$ examples.
11.3 Two points $a<b$ can be labeled in all four ways by intervals (choose an interval containing none, one, or both). For three points $a<b<c$, the labeling $(1,0,1)$ is impossible, because an interval containing $a$ and $c$ contains $b$. So the VC dimension is 2.
12.3 The best of 20 noisy estimates is about $80\%+1.87\times2\%\approx83.7\%$: almost four points of pure selection bias.
C.3Part III: Unsupervised Learning
13.2 $\norm{\vx-\vmu_1}^2=\norm{\vx-\vmu_2}^2$ expands to $-2\vmu_1\T\vx+\norm{\vmu_1}^2=-2\vmu_2\T\vx+\norm{\vmu_2}^2$, which rearranges to the stated hyperplane.
13.3 Setting the gradient of $\sum_ir_{ij}\log\Normal(\vx_i;\vmu_j,\mSigma_j)$ with respect to $\vmu_j$ to zero gives $\sum_ir_{ij}\mSigma_j^{-1}(\vx_i-\vmu_j)=\mathbf 0$, so $\vmu_j=\sum_ir_{ij}\vx_i/\sum_ir_{ij}$.
13.8 Since $\vz$ and $\vx$ are jointly Gaussian with $\Cov(\vz)=\mI$, $\Cov(\vz,\vx)=\mathbf\Lambda\T$, and $\Cov(\vx)=\mathbf\Lambda\mathbf\Lambda\T+\mathbf\Psi$, the conditioning formula of Appendix B gives $\E[\vz\mid\vx]=\mathbf\Lambda\T(\mathbf\Lambda\mathbf\Lambda\T+\mathbf\Psi)^{-1}(\vx-\vmu)$ and $\Cov(\vz\mid\vx)=\mI-\mathbf\Lambda\T(\mathbf\Lambda\mathbf\Lambda\T+\mathbf\Psi)^{-1}\mathbf\Lambda$. The identity follows by multiplying both sides on the right by $\mathbf\Lambda\mathbf\Lambda\T+\mathbf\Psi$ and on the left by $\mI+\mathbf\Lambda\T\mathbf\Psi^{-1}\mathbf\Lambda$.
14.1 $\vz=\mU\T\vx$ has covariance $\mU\T\mS\mU=\mathbf\Lambda$, which is diagonal with entries $\lambda_j$.
14.3 $\lambda_\pm=\frac{a+c}2\pm\sqrt{\big(\frac{a-c}2\big)^2+b^2}$, and the first component makes angle $\theta=\frac12\operatorname{atan2}(2b,\,a-c)$ with the first axis.
C.4Part IV: Deep Learning
15.1 Take $h_1=\relu(x_1+x_2)$, $h_2=\relu(-x_1-x_2)$, and output $h_1+h_2-1=|x_1+x_2|-1$. It is $+1$ for $(1,1)$ and $(-1,-1)$ and $-1$ for the other two points.
15.3 By symmetry of $z$ about 0, $\E[\relu(z)^2]=\int_0^\infty z^2p(z)\dd z=\frac12\E[z^2]=v/2$. With $z_i=\sum_jW_{ij}h_j$ and $h_j=\relu(z'_j)$, $\Var(z_i)=m\,s^2\,\E[h_j^2]=m\,s^2\,v'/2$. Keeping $\Var(z_i)=v'$ requires $s^2=2/m$.
16.1 With $\tanh z\approx z$, each layer multiplies the variance by $nv$, so after $L$ layers it is $(nv)^L$. For $v=1/n$ it stays 1; for $v=0.5/n$ it is $0.5^{20}\approx10^{-6}$ (the signal vanishes); for $v=2/n$ it would be $2^{20}\approx10^6$, but tanh saturates long before, so activations pile up at $\pm1$ and gradients vanish instead.
16.3 Each activation is kept with probability $1-p$ and then multiplied by $1/(1-p)$, so its expected value is $(1-p)\cdot a/(1-p)=a$. The variance is not preserved: $\E[\tilde a^2]=a^2/(1-p)$, so $\Var(\tilde a)=a^2p/(1-p)$; dropout adds multiplicative noise, which is why it regularizes.
17.1 Parameters: $128\times(64\cdot9+1)=73{,}856$. Multiply–adds: $32\cdot32\cdot128\cdot64\cdot9\approx75.5$ million. A dense layer from $32\cdot32\cdot64=65{,}536$ inputs to $131{,}072$ outputs needs about $8.6\times10^9$ weights. A depthwise separable layer needs $64\cdot9+64\cdot128=8{,}768$ weights (plus biases), about 8.4 times fewer than the full convolution.
17.2 (a) $1+5\cdot2=11$. (b) Jumps double after each pool: conv adds 2, pool adds 1; conv adds 4, pool adds 2; conv adds 8, pool adds 4; total $1+2+1+4+2+8+4=22$. (c) Effective kernel sizes 3, 5, 9, so $1+2+4+8=15$.
18.1 Vanilla RNN: $n(d+n+1)$ parameters. LSTM: four gates, $4n(d+n+1)$. GRU: three, $3n(d+n+1)$. (Plus the output layer in each case.)
18.4 With width 1, beam search keeps only the single best extension at each step, which is greedy decoding. Example: step-1 probabilities $p(A)=0.6$, $p(B)=0.4$; after $A$, both continuations have probability $0.5$; after $B$, one has probability $0.9$. Greedy finds a sequence of probability $0.3$; beam width 2 also keeps $B$ and finds $0.4\times0.9=0.36$.
19.2 The terms $q_lk_l$ are independent with mean 0 and variance $\E[q_l^2]\E[k_l^2]=1$, so the sum of $d_k$ of them has variance $d_k$.
19.5 Keys and values: $2\times80$ layers $\times\,128{,}000$ tokens $\times\,(8\times128)$ numbers $\times\,2$ bytes $\approx4.2\times10^{10}$ bytes, about 42 GB per sequence. With 64 key/value heads it would be eight times larger, about 335 GB: grouped-query attention is what makes such contexts feasible.
20.1 (a) Avoidable bias $0.5\%$, variance $6.5\%$: reduce variance (more data, regularization). (b) Avoidable bias $3.5\%$, variance $0.5\%$: reduce bias (bigger model, longer training). (c) Avoidable bias $0.5\%$, variance $0.5\%$, but a $4\%$ gap between dev and test: the dev set has been overfitted by tuning; get a larger dev set.
20.3 Plain data parallelism: $16\times70\times10^9=1.12$ TB per worker, which does not fit on one 80 GB device at all; at least 14 devices’ worth of memory would be needed for the state alone, so the model must be sharded. With ZeRO stage 3 on 64 workers: $1.12\text{ TB}/64\approx17.5$ GB per worker, leaving room for activations.
C.5Part V: Computer Vision
21.2 $n_{\text{out}}=(16-1)s-2p+k=32$, for example with $k=4$, $s=2$, $p=1$. For $k=3$, $s=2$ in one dimension, output position $2i$ receives contributions from inputs $i$ and $i-1$, position $2i+1$ only from input $i$: counts alternate 2, 1. In two dimensions the counts are products, 1, 2, or 4.
21.4 $\mathrm{FL}/\mathrm{CE}=(1-p_t)^\gamma$. For $\gamma=2$: $0.25$, $0.01$, $10^{-4}$ at $p_t=0.5,0.9,0.99$. For $\gamma=5$: $0.031$, $10^{-5}$, $10^{-10}$.
22.1 The change is $\varepsilon\norm{\vw}_1=\varepsilon dm$. For a change of 10 with $d=3072$ and $m=0.01$: $\varepsilon=10/30.72\approx0.33$ in the units of the inputs; for pixel values in $[0,255]$ that is about one third of an intensity level.
22.2 Let $g(\alpha)=s_c(\vx'+\alpha(\vx-\vx'))$. By the chain rule, $g'(\alpha)=\sum_i(x_i-x_i')\,\partial s_c/\partial x_i$ evaluated on the path, so $\sum_i\mathrm{IG}_i=\int_0^1g'(\alpha)\dd\alpha=g(1)-g(0)=s_c(\vx)-s_c(\vx')$.
23.3 On segment $i$, density $\sigma_i$ is constant, so the probability of being absorbed within it, given arrival, is $1-e^{-\sigma_i\delta_i}=\alpha_i$, and the probability of arriving is $T_i=\prod_{j<i}(1-\alpha_j)$. The weights $w_i=T_i\alpha_i$ telescope: $\sum_{i\le N}w_i=1-T_{N+1}\le1$, with equality only if the ray is fully absorbed before the far plane.
C.6Part VI: Frontier Techniques
24.1 Cross-entropy $-\ln0.25\approx1.386$ nats; perplexity 4.
24.2 $C\approx6\times7\times10^9\times2\times10^{12}=8.4\times10^{22}$ operations: $8.4\times10^7$ seconds, about 970 days, at $10^{15}$ operations per second. Real training runs spread this over thousands of accelerators.
24.4 $\E_\pi[r]-\beta D_{\mathrm{KL}}(\pi\Vert\pi_{\mathrm{ref}})=-\beta\sum_y\pi(y)\log\frac{\pi(y)}{\pi_{\mathrm{ref}}(y)e^{r(y)/\beta}}=-\beta D_{\mathrm{KL}}(\pi\Vert\pi^*)+\beta\log Z$, maximized by $\pi=\pi^*$. Then $r=\beta\log(\pi^*/\pi_{\mathrm{ref}})+\beta\log Z$; in the Bradley–Terry difference of two responses to the same prompt the $\beta\log Z(x)$ terms cancel, giving the DPO loss.
24.5 Mean $0.25$, standard deviation $\sqrt{0.25\cdot0.75}\approx0.433$: the two correct responses get advantage $+1.73$ and the six others $-0.58$. If all rewards are 1, every advantage is zero (implementations add a small constant to the denominator) and the prompt provides no learning signal.
24.6 Each $4096\times4096$ matrix gets $8\times(4096+4096)=65{,}536$ parameters; times 4 matrices and 32 layers gives about $8.4$ million, roughly $0.13\%$ of the $6.4$ billion block parameters.
25.1 Assume $\vx_{t-1}=\sqrt{\bar\alpha_{t-1}}\vx_0+\sqrt{1-\bar\alpha_{t-1}}\vepsilon'$. Then $\vx_t=\sqrt{\alpha_t}\vx_{t-1}+\sqrt{1-\alpha_t}\vepsilon$ has signal $\sqrt{\alpha_t\bar\alpha_{t-1}}\vx_0=\sqrt{\bar\alpha_t}\vx_0$ and independent Gaussian noise of variance $\alpha_t(1-\bar\alpha_{t-1})+1-\alpha_t=1-\bar\alpha_t$.
25.4 Pointwise, maximize $a\log D+b\log(1-D)$ with $a=p_{\text{data}}(\vx)$, $b=p_g(\vx)$. The derivative $a/D-b/(1-D)$ vanishes at $D=a/(a+b)$.
25.5 Given $\vx_t=\vx$, the noise was $\vx_0=(\vx-t\mathbf m)/(1-t)$, so the velocity is $\mathbf m-\vx_0=(\mathbf m-\vx)/(1-t)$. The ODE $\dot\vx=(\mathbf m-\vx)/(1-t)$ has solution $\vx(t)-\mathbf m=(1-t)(\vx(0)-\mathbf m)$, which equals $\mathbf 0$ at $t=1$.
26.2 $\norm{\bar q-\bar z}^2=\norm{\bar q}^2-2\bar q\T\bar z+\norm{\bar z}^2=2-2\bar q\T\bar z$ for unit vectors.
26.4 An exponential moving average with factor $m$ weights an update $k$ steps back by $(1-m)m^k$, so the effective memory is about $1/(1-m)=1{,}000$ steps.
27.1 With the reward received on entering the final state: $V^*=1$ one step before the goal, $0.9$ two steps before, and $0.81$ three steps before (the goal itself is terminal). Value iteration from $V_0=0$ reaches these values after one, two, and three sweeps.
27.3 The gradient of $a\T\mW a+(\mA s+\mB a)\T\mathbf P(\mA s+\mB a)$ in $a$ is $2\mW a+2\mB\T\mathbf P(\mA s+\mB a)$; setting it to zero gives $a=-(\mW+\mB\T\mathbf P\mB)^{-1}\mB\T\mathbf P\mA s$. Substituting back yields $s\T(\mathbf U+\mA\T\mathbf P\mA-\mA\T\mathbf P\mB\mK)s$. With noise, $\E[w\T\mathbf Pw]=\tr(\mathbf P\bm\Sigma_w)$ is added, which does not depend on $a$, so $\mK$ is unchanged.
27.4 $\E_{a\sim\pi}[\nabla\log\pi(a\mid s)\,b(s)]=b(s)\sum_a\pi(a\mid s)\nabla\log\pi(a\mid s)=b(s)\nabla\sum_a\pi(a\mid s)=b(s)\nabla1=0$.