Skip to content

Chapter 9 Formula Sheet

One page for the whole chapter. Equation numbers are the book’s; the measured columns are this module’s.

Three estimators, one linear system, three settings of the prior.

maximum likelihoodMAPBayesian
section§9.2.1§9.2.3§9.3
matrix invertedΦΦ\boldsymbol\Phi^\top\boldsymbol\PhiΦΦ+σ2b2I\boldsymbol\Phi^\top\boldsymbol\Phi + \tfrac{\sigma^2}{b^2}\mathbf{I}S01+σ2ΦΦ\mathbf{S}_0^{-1} + \sigma^{-2}\boldsymbol\Phi^\top\boldsymbol\Phi
equation9.199.319.43
the answera pointa pointa distribution
exists when K>NK > Nnoyesyes
predictive varianceσ2\sigma^2σ2\sigma^2ϕSNϕ+σ2\phi^\top\mathbf{S}_N\phi + \sigma^2
measured coverage0.74190.7419 / 0.11120.1112same0.9487\mathbf{0.9487} / 0.9499\mathbf{0.9499}
the prediction curveits ownidentical to MAP, to 8.4×10148.4\times10^{-14}
whatequation
the likelihoodp(yx)=N(yf(x),σ2)p(y \mid \mathbf{x}) = \mathcal{N}(y \mid f(\mathbf{x}), \sigma^2)9.1
equivalentlyy=f(x)+ϵy = f(\mathbf{x}) + \epsilon, ϵN(0,σ2)\epsilon \sim \mathcal{N}(0,\sigma^2) i.i.d. — 9.2
the linear casep(yx,θ)=N(yxθ,σ2)p(y \mid \mathbf{x},\boldsymbol\theta) = \mathcal{N}(y \mid \mathbf{x}^\top\boldsymbol\theta, \sigma^2)9.3, 9.4
with featuresy=ϕ(x)θ+ϵ=k=0K1θkϕk(x)+ϵy = \phi^\top(\mathbf{x})\boldsymbol\theta + \epsilon = \sum_{k=0}^{K-1}\theta_k\phi_k(\mathbf{x}) + \epsilon9.13
monomial featuresϕ(x)=[1,x,x2,,xK1]\phi(x) = [1, x, x^2, \ldots, x^{K-1}]^\top9.14
the feature matrixΦRN×K\boldsymbol\Phi \in \mathbb{R}^{N\times K}, Φij=ϕj(xi)\Phi_{ij} = \phi_j(x_i)9.16
whatequation
the likelihood factorizesp(YX,θ)=nN(ynxnθ,σ2)p(\mathcal{Y}\mid\mathcal{X},\boldsymbol\theta) = \prod_{n}\mathcal{N}(y_n \mid \mathbf{x}_n^\top\boldsymbol\theta, \sigma^2)9.5
the plug-in predictivep(yx,θ)=N(yxθ,σ2)p(y_* \mid \mathbf{x}_*, \boldsymbol\theta^*) = \mathcal{N}(y_* \mid \mathbf{x}_*^\top\boldsymbol\theta^*, \sigma^2)9.6
the error functionL(θ)=12σ2yXθ2\mathcal{L}(\boldsymbol\theta) = \frac{1}{2\sigma^2}\lVert\mathbf{y}-\mathbf{X}\boldsymbol\theta\rVert^29.10
its gradient1σ2(yX+θXX)\frac{1}{\sigma^2}(-\mathbf{y}^\top\mathbf{X} + \boldsymbol\theta^\top\mathbf{X}^\top\mathbf{X})9.11c
the normal equationsθML=(XX)1Xy\boldsymbol\theta_{\text{ML}} = (\mathbf{X}^\top\mathbf{X})^{-1}\mathbf{X}^\top\mathbf{y}9.12c
with featuresθML=(ΦΦ)1Φy\boldsymbol\theta_{\text{ML}} = (\boldsymbol\Phi^\top\boldsymbol\Phi)^{-1}\boldsymbol\Phi^\top\mathbf{y}9.19
the noise varianceσML2=1Nn(ynϕ(xn)θ)2\sigma^2_{\text{ML}} = \frac{1}{N}\sum_n (y_n - \phi^\top(\mathbf{x}_n)\boldsymbol\theta)^29.22
the RMSE1NyΦθ2\sqrt{\frac{1}{N}\lVert\mathbf{y}-\boldsymbol\Phi\boldsymbol\theta\rVert^2}9.23

Solvability: ΦΦ\boldsymbol\Phi^\top\boldsymbol\Phi is invertible iff rk(Φ)=K\mathrm{rk}(\boldsymbol\Phi) = K, which requires KNK \leqslant N and no redundant features.

Search bound: 0MN10 \leqslant M \leqslant N-1. Past it Φ\boldsymbol\Phi has a null space — measured dimension 11 at M=10M = 10, N=10N = 10 — and estimators with norms from 3.443.44 to 5000.005000.00 fit equally well. lstsq returns the minimum-norm one by convention.

whatequation
the posteriorp(θX,Y)p(YX,θ)p(θ)p(\boldsymbol\theta \mid \mathcal{X},\mathcal{Y}) \propto p(\mathcal{Y}\mid\mathcal{X},\boldsymbol\theta)p(\boldsymbol\theta)9.24
log-posterior=logp(YX,θ)+logp(θ)+const= \log p(\mathcal{Y}\mid\mathcal{X},\boldsymbol\theta) + \log p(\boldsymbol\theta) + \text{const}9.25
the MAP estimateθMAP=(ΦΦ+σ2b2I)1Φy\boldsymbol\theta_{\text{MAP}} = \left(\boldsymbol\Phi^\top\boldsymbol\Phi + \tfrac{\sigma^2}{b^2}\mathbf{I}\right)^{-1}\boldsymbol\Phi^\top\mathbf{y}9.31
regularized least squaresyΦθ2+λθ22\lVert\mathbf{y}-\boldsymbol\Phi\boldsymbol\theta\rVert^2 + \lambda\lVert\boldsymbol\theta\rVert_2^29.32
the negative log-priorlogp(θ)=12b2θ22+const-\log p(\boldsymbol\theta) = \frac{1}{2b^2}\lVert\boldsymbol\theta\rVert_2^2 + \text{const}9.33
its solutionθRLS=(ΦΦ+λI)1Φy\boldsymbol\theta_{\text{RLS}} = (\boldsymbol\Phi^\top\boldsymbol\Phi + \lambda\mathbf{I})^{-1}\boldsymbol\Phi^\top\mathbf{y}9.34

The pp-norm remark. Smaller pp gives sparser solutions; p=1p=1 is LASSO. Measured on 30 features with 3 real ones: ridge produced zero exact zeros at λ=2,8,20\lambda = 2, 8, 20; LASSO produced 1717 then 2727 (the truth has 2727). A quadratic penalty has zero gradient at the origin; 1\ell_1 has a kink.

whatequation
the modelp(θ)=N(m0,S0)p(\boldsymbol\theta) = \mathcal{N}(\mathbf{m}_0,\mathbf{S}_0),  p(yx,θ)=N(ϕ(x)θ,σ2)\ p(y\mid\mathbf{x},\boldsymbol\theta) = \mathcal{N}(\phi^\top(\mathbf{x})\boldsymbol\theta,\sigma^2)9.35
the jointp(y,θx)=p(yx,θ)p(θ)p(y,\boldsymbol\theta\mid\mathbf{x}) = p(y\mid\mathbf{x},\boldsymbol\theta)p(\boldsymbol\theta)9.36
prior predictiveN ⁣(ϕm0, ϕS0ϕ+σ2)\mathcal{N}\!\left(\phi^\top\mathbf{m}_0,\ \phi^\top\mathbf{S}_0\phi + \sigma^2\right)9.38
variance decompositionV[y]=Vθ[ϕθ]+Vϵ[ϵ]\mathbb{V}[y_*] = \mathbb{V}_{\boldsymbol\theta}[\phi^\top\boldsymbol\theta] + \mathbb{V}_\epsilon[\epsilon]9.39
noise-free versionN ⁣(ϕm0, ϕS0ϕ)\mathcal{N}\!\left(\phi^\top\mathbf{m}_0,\ \phi^\top\mathbf{S}_0\phi\right)9.40
the posteriorp(θX,Y)=p(YX,θ)p(θ)p(YX)p(\boldsymbol\theta\mid\mathcal{X},\mathcal{Y}) = \dfrac{p(\mathcal{Y}\mid\mathcal{X},\boldsymbol\theta)p(\boldsymbol\theta)}{p(\mathcal{Y}\mid\mathcal{X})}9.41
the marginal likelihoodp(YX)=p(YX,θ)p(θ)dθp(\mathcal{Y}\mid\mathcal{X}) = \int p(\mathcal{Y}\mid\mathcal{X},\boldsymbol\theta)p(\boldsymbol\theta)\,d\boldsymbol\theta9.42
 SN=(S01+σ2ΦΦ)1,mN=SN(S01m0+σ2Φy) \boxed{\ \mathbf{S}_N = \left(\mathbf{S}_0^{-1} + \sigma^{-2}\boldsymbol\Phi^\top\boldsymbol\Phi\right)^{-1}, \qquad \mathbf{m}_N = \mathbf{S}_N\left(\mathbf{S}_0^{-1}\mathbf{m}_0 + \sigma^{-2}\boldsymbol\Phi^\top\mathbf{y}\right)\ }
propertymeasured
verified as a posterior (log gap constant in θ\boldsymbol\theta)spread 1.805×10121.805\times10^{-12}
that constantlogp(YX)=30.453407-\log p(\mathcal{Y}\mid\mathcal{X}) = \mathbf{30.453407}
grid cross-check, 1400×14001400\times1400, 2-Dmean, sd, correlation to 10810^{-8}
precisions addmaxSNAI=6.9×1011\max\lvert\mathbf{S}_N\mathbf{A}-\mathbf{I}\rvert = 6.9\times10^{-11}
sequential updatingbatch vs one-at-a-time: 4.1×10124.1\times10^{-12}; over 500 points, 6.8×10156.8\times10^{-15}
mN\mathbf{m}_N vs θMAP\boldsymbol\theta_{\text{MAP}}1.19×10131.19\times10^{-13}
mN\mathbf{m}_N vs θML\boldsymbol\theta_{\text{ML}} at b2=108b^2 = 10^81.43×10101.43\times10^{-10}
contractionsd ×N0.37\times\sqrt{N} \to 0.37 past N=50N = 50
posterior correlations (prior’s are I\mathbf{I})up to 0.969560\mathbf{0.969560}
p(yX,Y,x)=N ⁣(ϕ(x)mN,  ϕ(x)SNϕ(x)+σ2)(9.57)p(y_*\mid\mathcal{X},\mathcal{Y},\mathbf{x}_*) = \mathcal{N}\!\left(\phi^\top(\mathbf{x}_*)\mathbf{m}_N,\ \ \phi^\top(\mathbf{x}_*)\mathbf{S}_N\phi(\mathbf{x}_*) + \sigma^2\right) \qquad \textbf{(9.57)}

with E[y]=ϕmN=ϕθMAP\mathbb{E}[y_*] = \phi^\top\mathbf{m}_N = \phi^\top\boldsymbol\theta_{\text{MAP}} — measured to 8.438×10148.438\times10^{-14} over 400 inputs, while the MLE’s curve differs by 0.2025780.202578.

E[YX]=Xm0(9.62),Cov[YX]=XS0X+σ2I(9.63)\mathbb{E}[\mathcal{Y}\mid\mathcal{X}] = \mathbf{X}\mathbf{m}_0 \quad \textbf{(9.62)}, \qquad \mathrm{Cov}[\mathcal{Y}\mid\mathcal{X}] = \mathbf{X}\mathbf{S}_0\mathbf{X}^\top + \sigma^2\mathbf{I} \quad \textbf{(9.63)}  p(YX)=N ⁣(y | Xm0, XS0X+σ2I) (9.64)\boxed{\ p(\mathcal{Y}\mid\mathcal{X}) = \mathcal{N}\!\left(\mathbf{y}\ \middle|\ \mathbf{X}\mathbf{m}_0,\ \mathbf{X}\mathbf{S}_0\mathbf{X}^\top + \sigma^2\mathbf{I}\right)\ } \qquad \textbf{(9.64)}

Use the K×KK\times K form. Woodbury gives det(XS0X+σ2I)=det(SN1)det(S0)σ2N\det(\mathbf{X}\mathbf{S}_0\mathbf{X}^\top + \sigma^2\mathbf{I}) = \det(\mathbf{S}_N^{-1})\det(\mathbf{S}_0)\sigma^{2N}: agreeing to 8.9×1068.9\times10^{-6} at N=5000N=5000 and 4341×4341\times faster at N=4000N=4000.

§9.4 Maximum likelihood as orthogonal projection

Section titled “§9.4 Maximum likelihood as orthogonal projection”
whatequation
the scalar estimatorθML=XyXX\theta_{\text{ML}} = \dfrac{\mathbf{X}^\top\mathbf{y}}{\mathbf{X}^\top\mathbf{X}}9.66
the projectionXθML=XXXXy\mathbf{X}\theta_{\text{ML}} = \dfrac{\mathbf{X}\mathbf{X}^\top}{\mathbf{X}^\top\mathbf{X}}\mathbf{y}9.67
the general caseP=Φ(ΦΦ)1ΦP = \boldsymbol\Phi(\boldsymbol\Phi^\top\boldsymbol\Phi)^{-1}\boldsymbol\Phi^\top9.69, 9.70
orthonormal featuresΦΦ=I\boldsymbol\Phi^\top\boldsymbol\Phi = \mathbf{I}, so P=ΦΦP = \boldsymbol\Phi\boldsymbol\Phi^\top
propertymeasured
idempotent, PP=PPP = P5.551×10175.551\times10^{-17}
symmetric, P=PP = P^\top0.000×1000.000\times10^{0}
tr(P)=K\mathrm{tr}(P) = Kexact to 8 decimals, every degree
residual orthogonal, Φr=0\boldsymbol\Phi^\top\mathbf{r} = \mathbf{0}9.551×10159.551\times10^{-15}
Pythagoras, y2=Py2+r2\lVert\mathbf{y}\rVert^2 = \lVert P\mathbf{y}\rVert^2 + \lVert\mathbf{r}\rVert^28.53×10148.53\times10^{-14}
pointerwhat it says
generalized linear modelsxk+1=σk(Akxk+bk)x_{k+1} = \sigma_k(\mathbf{A}_kx_k + \mathbf{b}_k)9.72. A KK-layer deep network is a composition of these.
neural networksfar more expressive, but maximum likelihood is non-convex and Bayesian marginalization is intractable
Gaussian processesplace a distribution directly on functions, “without the detour via the parameters”, via the kernel trick
non-Gaussian priorsfor NDN \ll D the problem is underdetermined; a Laplace prior enforces sparsity — equivalent to 1\ell_1, i.e. LASSO (Tibshirani, 1996)
quantityvaluepage
likelihood’s integral over θ\thetaexactly 1/x1/\lvert x\rvert901
superposition, θ\boldsymbol\theta vs xx4.4×10114.4\times10^{-11} vs 2.3×1052.3\times10^{5}901
product of NN densities underflows atN=1000N = 1000, exactly 0.00.0901
κ(ΦΦ)/κ(Φ)2\kappa(\boldsymbol\Phi^\top\boldsymbol\Phi)/\kappa(\boldsymbol\Phi)^21.0000001.000000902
normal equations vs lstsq at M=16M=161157.7×1157.7\times worse902
Eq 9.22 biasexactly (NK)/N(N-K)/N902
test RMSE at M=N1=9M = N-1 = 9100.850623100.850623903
M=4M=4 wins over 2000 draws46.1%46.1\%903
λ\lambda that makes RLS == MAPσ2/b2\sigma^2/b^2, to 0.00×1000.00\times10^{0}904
ridge exact zeros, any λ\lambda0\mathbf{0} of 30904
95% prior band at x=5x=5, degree 53125.59353125.5935905
prior band fits the book’s axes at4848 of 200200 inputs905
Cov[f(2),f(2)]\mathrm{Cov}[f(-2), f(2)]204.75-204.75905
Theorem 9.1’s constant offset30.45340730.453407906
sequential vs batch, 500 points6.772×10156.772\times10^{-15}906, 910
posterior correlation, prior =I=\mathbf{I}0.9695600.969560906
Eq 9.57 vs Eq 9.6 coverage0.94870.9487/0.94990.9499 vs 0.74190.7419/0.11120.1112907
SN\mathbf{S}_N under shuffled targets0.000×1000.000\times10^{0}907
K×KK\times K evidence speedup at N=4000N=40004341×4341\times908
evidence peakM=4M = 4, matching CV and the test set908, 910
tr(P)\mathrm{tr}(P)=K= K, exact909
E(IP)y2\mathbb{E}\lVert(\mathbf{I}-P)\mathbf{y}\rVert^20.2002220.200222 vs σ2(NK)=0.2\sigma^2(N-K) = 0.2909
κ\kappa: monomial vs orthonormal, M=18M=182.195×10262.195\times10^{26} vs 1.0000001.000000909
experimental design, clustered vs spread286.948028286.948028 vs 0.4739740.473974910
  1. Model the noise, not the loss. Everything follows from Equation 9.1.
  2. “Linear” constrains θ\boldsymbol\theta, not xx — to 4.4×10114.4\times10^{-11} against 2.3×1052.3\times10^{5}.
  3. Equation 9.4 has no intercept, and a missing feature corrupts the ones you kept.
  4. The objective is quadratic, so one solve suffices and Chapter 7 is unnecessary — until you leave the class.
  5. Write Equation 9.12c; call np.linalg.lstsq. The Gram matrix squares the condition number.
  6. Equation 9.22 is biased by (NK)/N(N-K)/N, because tr(IP)=NK\mathrm{tr}(\mathbf{I}-P) = N-K. Divide by NKN-K.
  7. The training error cannot rise, so it carries no information about generalization.
  8. A penalty is a prior — with λ=σ2/b2\lambda = \sigma^2/b^2 for Equation 9.32, and never without naming the objective.
  9. Precisions add, so the posterior update runs online in fixed memory, exactly.
  10. MAP and Bayesian give the same curve, to 8.4×10148.4\times10^{-14}. The whole return is ϕSNϕ\phi^\top\mathbf{S}_N\phi.
  11. That term is calibrated0.94870.9487 against 0.11120.1112 — and it never saw the targets, which makes it both a design tool and a blind spot.
  12. A projection is a property of the subspace. The basis is a coordinate system, and some are 102610^{26} times better than others.

Back to the start: Linear Regression Overview

pch.coffeeTagline

pch.coffeeCta

pch.feedbackHeading

pch.feedbackSubheading