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 likelihood MAP Bayesian section §9.2.1 §9.2.3 §9.3 matrix inverted Φ ⊤ Φ \boldsymbol\Phi^\top\boldsymbol\Phi Φ ⊤ Φ Φ ⊤ Φ + σ 2 b 2 I \boldsymbol\Phi^\top\boldsymbol\Phi + \tfrac{\sigma^2}{b^2}\mathbf{I} Φ ⊤ Φ + b 2 σ 2 I S 0 − 1 + σ − 2 Φ ⊤ Φ \mathbf{S}_0^{-1} + \sigma^{-2}\boldsymbol\Phi^\top\boldsymbol\Phi S 0 − 1 + σ − 2 Φ ⊤ Φ equation 9.19 9.31 9.43 the answer a point a point a distribution exists when K > N K > N K > N no yes yes predictive variance σ 2 \sigma^2 σ 2 σ 2 \sigma^2 σ 2 ϕ ⊤ S N ϕ + σ 2 \phi^\top\mathbf{S}_N\phi + \sigma^2 ϕ ⊤ S N ϕ + σ 2 measured coverage 0.7419 0.7419 0.7419 / 0.1112 0.1112 0.1112 same 0.9487 \mathbf{0.9487} 0.9487 / 0.9499 \mathbf{0.9499} 0.9499 the prediction curve its own — identical to MAP , to 8.4 × 10 − 14 8.4\times10^{-14} 8.4 × 1 0 − 14
what equation the likelihood p ( y ∣ x ) = N ( y ∣ f ( x ) , σ 2 ) p(y \mid \mathbf{x}) = \mathcal{N}(y \mid f(\mathbf{x}), \sigma^2) p ( y ∣ x ) = N ( y ∣ f ( x ) , σ 2 ) — 9.1 equivalently y = f ( x ) + ϵ y = f(\mathbf{x}) + \epsilon y = f ( x ) + ϵ , ϵ ∼ N ( 0 , σ 2 ) \epsilon \sim \mathcal{N}(0,\sigma^2) ϵ ∼ N ( 0 , σ 2 ) i.i.d. — 9.2 the linear case p ( y ∣ x , θ ) = N ( y ∣ x ⊤ θ , σ 2 ) p(y \mid \mathbf{x},\boldsymbol\theta) = \mathcal{N}(y \mid \mathbf{x}^\top\boldsymbol\theta, \sigma^2) p ( y ∣ x , θ ) = N ( y ∣ x ⊤ θ , σ 2 ) — 9.3 , 9.4 with features y = ϕ ⊤ ( x ) θ + ϵ = ∑ k = 0 K − 1 θ k ϕ k ( x ) + ϵ y = \phi^\top(\mathbf{x})\boldsymbol\theta + \epsilon = \sum_{k=0}^{K-1}\theta_k\phi_k(\mathbf{x}) + \epsilon y = ϕ ⊤ ( x ) θ + ϵ = ∑ k = 0 K − 1 θ k ϕ k ( x ) + ϵ — 9.13 monomial features ϕ ( x ) = [ 1 , x , x 2 , … , x K − 1 ] ⊤ \phi(x) = [1, x, x^2, \ldots, x^{K-1}]^\top ϕ ( x ) = [ 1 , x , x 2 , … , x K − 1 ] ⊤ — 9.14 the feature matrix Φ ∈ R N × K \boldsymbol\Phi \in \mathbb{R}^{N\times K} Φ ∈ R N × K , Φ i j = ϕ j ( x i ) \Phi_{ij} = \phi_j(x_i) Φ ij = ϕ j ( x i ) — 9.16
Equation 9.4 has no intercept
“The class of functions described by (9.4) are straight lines that pass through the origin.” Measured on
data with a true intercept of 4.0 4.0 4.0 : RMSE 4.091288 4.091288 4.091288 against 0.514303 0.514303 0.514303 , and the slope comes out at
1.193712 1.193712 1.193712 against a true 1.3 1.3 1.3 . A missing feature corrupts the features you kept.
“Linear regression” constrains theta, not x
Measured on a degree-9 model: superposition holds in θ \boldsymbol\theta θ to 4.366 × 10 − 11 4.366\times10^{-11} 4.366 × 1 0 − 11 and
fails in x x x by 2.341 × 10 5 2.341\times10^{5} 2.341 × 1 0 5 — sixteen orders of magnitude apart. That gap licenses Equation 9.19
being Equation 9.12c with X \mathbf{X} X replaced by Φ \boldsymbol\Phi Φ .
The likelihood is a density in y, not in theta
integral value ∫ p ( y ∣ x , θ ) d y \int p(y \mid x, \theta)\,dy ∫ p ( y ∣ x , θ ) d y 1.00000000 1.00000000 1.00000000 ∫ p ( y ∣ x , θ ) d θ \int p(y \mid x, \theta)\,d\theta ∫ p ( y ∣ x , θ ) d θ exactly 1 / ∣ x ∣ 1/\lvert x\rvert 1/ ∣ x ∣ — measured 0.50000000 0.50000000 0.50000000 at x = 2 x=2 x = 2
It reaches 1 1 1 only when ∣ x ∣ = 1 \lvert x\rvert = 1 ∣ x ∣ = 1 and diverges as x → 0 x \to 0 x → 0 . The missing normaliser is
what §9.3.3 supplies and §9.3.5 computes.
what equation the likelihood factorizes p ( Y ∣ X , θ ) = ∏ n N ( y n ∣ x n ⊤ θ , σ 2 ) p(\mathcal{Y}\mid\mathcal{X},\boldsymbol\theta) = \prod_{n}\mathcal{N}(y_n \mid \mathbf{x}_n^\top\boldsymbol\theta, \sigma^2) p ( Y ∣ X , θ ) = ∏ n N ( y n ∣ x n ⊤ θ , σ 2 ) — 9.5 the plug-in predictive p ( y ∗ ∣ x ∗ , θ ∗ ) = N ( y ∗ ∣ x ∗ ⊤ θ ∗ , σ 2 ) p(y_* \mid \mathbf{x}_*, \boldsymbol\theta^*) = \mathcal{N}(y_* \mid \mathbf{x}_*^\top\boldsymbol\theta^*, \sigma^2) p ( y ∗ ∣ x ∗ , θ ∗ ) = N ( y ∗ ∣ x ∗ ⊤ θ ∗ , σ 2 ) — 9.6 the error function L ( θ ) = 1 2 σ 2 ∥ y − X θ ∥ 2 \mathcal{L}(\boldsymbol\theta) = \frac{1}{2\sigma^2}\lVert\mathbf{y}-\mathbf{X}\boldsymbol\theta\rVert^2 L ( θ ) = 2 σ 2 1 ∥ y − X θ ∥ 2 — 9.10 its gradient 1 σ 2 ( − y ⊤ X + θ ⊤ X ⊤ X ) \frac{1}{\sigma^2}(-\mathbf{y}^\top\mathbf{X} + \boldsymbol\theta^\top\mathbf{X}^\top\mathbf{X}) σ 2 1 ( − y ⊤ X + θ ⊤ X ⊤ X ) — 9.11c the normal equations θ ML = ( X ⊤ X ) − 1 X ⊤ y \boldsymbol\theta_{\text{ML}} = (\mathbf{X}^\top\mathbf{X})^{-1}\mathbf{X}^\top\mathbf{y} θ ML = ( X ⊤ X ) − 1 X ⊤ y — 9.12c with features θ ML = ( Φ ⊤ Φ ) − 1 Φ ⊤ y \boldsymbol\theta_{\text{ML}} = (\boldsymbol\Phi^\top\boldsymbol\Phi)^{-1}\boldsymbol\Phi^\top\mathbf{y} θ ML = ( Φ ⊤ Φ ) − 1 Φ ⊤ y — 9.19 the noise variance σ ML 2 = 1 N ∑ n ( y n − ϕ ⊤ ( x n ) θ ) 2 \sigma^2_{\text{ML}} = \frac{1}{N}\sum_n (y_n - \phi^\top(\mathbf{x}_n)\boldsymbol\theta)^2 σ ML 2 = N 1 ∑ n ( y n − ϕ ⊤ ( x n ) θ ) 2 — 9.22 the RMSE 1 N ∥ y − Φ θ ∥ 2 \sqrt{\frac{1}{N}\lVert\mathbf{y}-\boldsymbol\Phi\boldsymbol\theta\rVert^2} N 1 ∥ y − Φ θ ∥ 2 — 9.23
Solvability: Φ ⊤ Φ \boldsymbol\Phi^\top\boldsymbol\Phi Φ ⊤ Φ is invertible iff r k ( Φ ) = K \mathrm{rk}(\boldsymbol\Phi) = K rk ( Φ ) = K ,
which requires K ⩽ N K \leqslant N K ⩽ N and no redundant features.
Never form the Gram matrix
Measured, κ ( Φ ⊤ Φ ) = κ ( Φ ) 2 \kappa(\boldsymbol\Phi^\top\boldsymbol\Phi) = \kappa(\boldsymbol\Phi)^2 κ ( Φ ⊤ Φ ) = κ ( Φ ) 2 to six decimal
places at every degree. Against a known θ \boldsymbol\theta θ :
degree κ ( Φ ) \kappa(\boldsymbol\Phi) κ ( Φ ) normal equations lstsq ratio 8 8 8 3.162 × 10 5 3.162\times10^{5} 3.162 × 1 0 5 3.207 × 10 − 12 3.207\times10^{-12} 3.207 × 1 0 − 12 5.517 × 10 − 13 5.517\times10^{-13} 5.517 × 1 0 − 13 5.8 × 5.8\times 5.8 × 12 12 12 3.262 × 10 8 3.262\times10^{8} 3.262 × 1 0 8 3.405 × 10 − 8 3.405\times10^{-8} 3.405 × 1 0 − 8 4.665 × 10 − 9 4.665\times10^{-9} 4.665 × 1 0 − 9 7.3 × 7.3\times 7.3 × 16 16 16 3.922 × 10 11 3.922\times10^{11} 3.922 × 1 0 11 3.313 × 10 − 5 3.313\times10^{-5} 3.313 × 1 0 − 5 2.861 × 10 − 8 2.861\times10^{-8} 2.861 × 1 0 − 8 1157.7 × \mathbf{1157.7\times} 1157.7 × 20 20 20 4.988 × 10 14 4.988\times10^{14} 4.988 × 1 0 14 3.868 × 10 − 2 3.868\times10^{-2} 3.868 × 1 0 − 2 4.757 × 10 − 1 4.757\times10^{-1} 4.757 × 1 0 − 1 both failed
Equation 9.12c is a derivation; np.linalg.lstsq is the implementation.
Equation 9.22 is biased by exactly (N-K)/N
N N N K K K E [ σ ^ ML 2 ] / σ 2 \mathbb{E}[\hat\sigma^2_{\text{ML}}]/\sigma^2 E [ σ ^ ML 2 ] / σ 2 ( N − K ) / N (N-K)/N ( N − K ) / N 10 10 10 5 5 5 0.500606 \mathbf{0.500606} 0.500606 0.500000 0.500000 0.500000 20 20 20 5 5 5 0.750030 0.750030 0.750030 0.750000 0.750000 0.750000 200 200 200 5 5 5 0.974591 0.974591 0.974591 0.975000 0.975000 0.975000 1000 1000 1000 5 5 5 0.994725 0.994725 0.994725 0.995000 0.995000 0.995000
Divide by N − K N-K N − K . Verified unbiased: 0.04017 0.04017 0.04017 , 0.04013 0.04013 0.04013 , 0.04005 0.04005 0.04005 , 0.03997 0.03997 0.03997 against a true
0.04 0.04 0.04 . §9.4 explains why — t r ( I − P ) = N − K \mathrm{tr}(\mathbf{I}-P) = N-K tr ( I − P ) = N − K .
Figure 9.6, reproduced
M M M training RMSE test RMSE ∥ θ ∥ \lVert\boldsymbol\theta\rVert ∥ θ ∥ 1 1 1 0.743590 0.743590 0.743590 0.745097 0.745097 0.745097 0.2150 0.2150 0.2150 4 \mathbf{4} 4 0.270626 0.270626 0.270626 0.324947 \mathbf{0.324947} 0.324947 0.9904 0.9904 0.9904 6 6 6 0.207586 0.207586 0.207586 0.473424 0.473424 0.473424 1.1985 1.1985 1.1985 9 9 9 6.506 × 10 − 11 \mathbf{6.506\times10^{-11}} 6.506 × 1 0 − 11 100.850623 \mathbf{100.850623} 100.850623 4.2030 4.2030 4.2030
The training error never increases — nine steps, zero increases. It is a theorem from set inclusion,
so it carries no information. At M = N − 1 M = N-1 M = N − 1 the fit is exact and generalization is destroyed.
And Figure 9.6 is one draw. Over 2000 2000 2000 repeats, M = 4 M = 4 M = 4 wins only 46.1 % 46.1\% 46.1% of the time; M = 6 M = 6 M = 6 wins
20.8 % 20.8\% 20.8% ; M = 1 M = 1 M = 1 wins 11.3 % 11.3\% 11.3% .
Search bound: 0 ⩽ M ⩽ N − 1 0 \leqslant M \leqslant N-1 0 ⩽ M ⩽ N − 1 . Past it Φ \boldsymbol\Phi Φ has a null space — measured
dimension 1 1 1 at M = 10 M = 10 M = 10 , N = 10 N = 10 N = 10 — and estimators with norms from 3.44 3.44 3.44 to 5000.00 5000.00 5000.00 fit equally
well. lstsq returns the minimum-norm one by convention .
what equation the posterior p ( θ ∣ X , Y ) ∝ p ( Y ∣ X , θ ) p ( θ ) p(\boldsymbol\theta \mid \mathcal{X},\mathcal{Y}) \propto p(\mathcal{Y}\mid\mathcal{X},\boldsymbol\theta)p(\boldsymbol\theta) p ( θ ∣ X , Y ) ∝ p ( Y ∣ X , θ ) p ( θ ) — 9.24 log-posterior = log p ( Y ∣ X , θ ) + log p ( θ ) + const = \log p(\mathcal{Y}\mid\mathcal{X},\boldsymbol\theta) + \log p(\boldsymbol\theta) + \text{const} = log p ( Y ∣ X , θ ) + log p ( θ ) + const — 9.25 the MAP estimate θ MAP = ( Φ ⊤ Φ + σ 2 b 2 I ) − 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} θ MAP = ( Φ ⊤ Φ + b 2 σ 2 I ) − 1 Φ ⊤ y — 9.31 regularized least squares ∥ y − Φ θ ∥ 2 + λ ∥ θ ∥ 2 2 \lVert\mathbf{y}-\boldsymbol\Phi\boldsymbol\theta\rVert^2 + \lambda\lVert\boldsymbol\theta\rVert_2^2 ∥ y − Φ θ ∥ 2 + λ ∥ θ ∥ 2 2 — 9.32 the negative log-prior − log p ( θ ) = 1 2 b 2 ∥ θ ∥ 2 2 + const -\log p(\boldsymbol\theta) = \frac{1}{2b^2}\lVert\boldsymbol\theta\rVert_2^2 + \text{const} − log p ( θ ) = 2 b 2 1 ∥ θ ∥ 2 2 + 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} θ RLS = ( Φ ⊤ Φ + λ I ) − 1 Φ ⊤ y — 9.34
Three lambdas for one idea
objective λ \lambda λ reproduces Eq 9.31? Eq 9.32, ∥ ⋅ ∥ 2 + λ ∥ θ ∥ 2 \lVert\cdot\rVert^2 + \lambda\lVert\boldsymbol\theta\rVert^2 ∥ ⋅ ∥ 2 + λ ∥ θ ∥ 2 σ 2 / b 2 \boldsymbol\sigma^2/b^2 σ 2 / b 2 yes , 0.00 × 10 0 0.00\times10^{0} 0.00 × 1 0 0 Eq 9.33’s stated value 1 / ( 2 b 2 ) 1/(2b^2) 1/ ( 2 b 2 ) no — off by 1.87 × 10 − 1 1.87\times10^{-1} 1.87 × 1 0 − 1 Eq 8.12, 1 N ∥ ⋅ ∥ 2 + λ ∥ θ ∥ 2 \frac1N\lVert\cdot\rVert^2 + \lambda\lVert\boldsymbol\theta\rVert^2 N 1 ∥ ⋅ ∥ 2 + λ ∥ θ ∥ 2 σ 2 / ( N τ 2 ) \sigma^2/(N\tau^2) σ 2 / ( N τ 2 ) yes , 7.8 × 10 − 15 7.8\times10^{-15} 7.8 × 1 0 − 15
Equation 9.33’s statement matches the two penalty terms ; Equation 9.34’s matches the two
estimators , and the difference is a factor of 2 σ 2 2\sigma^2 2 σ 2 . A λ \lambda λ is meaningless without its
objective.
What the extra term does
It adds σ 2 / b 2 \sigma^2/b^2 σ 2 / b 2 to every eigenvalue . Measured at M = 12 M = 12 M = 12 , N = 10 N = 10 N = 10 : a smallest eigenvalue of
exactly 0 0 0 becomes 0.04 0.04 0.04 , and an infinite condition number becomes finite. At M = 4 M = 4 M = 4 the condition
number barely moves (1.817 × 10 5 → 1.794 × 10 5 1.817\times10^{5} \to 1.794\times10^{5} 1.817 × 1 0 5 → 1.794 × 1 0 5 ) — it is not a preconditioner.
Example 9.6 measured: at M = 9 M = 9 M = 9 the prior cuts ∥ θ ∥ \lVert\boldsymbol\theta\rVert ∥ θ ∥ from 4.2030 4.2030 4.2030 to
1.2062 1.2062 1.2062 and test RMSE from 100.8506 100.8506 100.8506 to 29.9717 29.9717 29.9717 . But best MAP is 0.323740 0.323740 0.323740 against best MLE’s
0.324947 0.324947 0.324947 — 0.4 % 0.4\% 0.4% — and at M = 7 M = 7 M = 7 MAP is worse by 1.1652 × 1.1652\times 1.1652 × .
The p p p -norm remark. Smaller p p p gives sparser solutions; p = 1 p=1 p = 1 is LASSO . Measured on 30 features
with 3 real ones: ridge produced zero exact zeros at λ = 2 , 8 , 20 \lambda = 2, 8, 20 λ = 2 , 8 , 20 ; LASSO produced 17 17 17 then
27 27 27 (the truth has 27 27 27 ). A quadratic penalty has zero gradient at the origin; ℓ 1 \ell_1 ℓ 1 has a kink.
what equation the model p ( θ ) = N ( m 0 , S 0 ) p(\boldsymbol\theta) = \mathcal{N}(\mathbf{m}_0,\mathbf{S}_0) p ( θ ) = N ( m 0 , S 0 ) , p ( y ∣ x , θ ) = N ( ϕ ⊤ ( x ) θ , σ 2 ) \ p(y\mid\mathbf{x},\boldsymbol\theta) = \mathcal{N}(\phi^\top(\mathbf{x})\boldsymbol\theta,\sigma^2) p ( y ∣ x , θ ) = N ( ϕ ⊤ ( x ) θ , σ 2 ) — 9.35 the joint p ( y , θ ∣ x ) = p ( y ∣ x , θ ) p ( θ ) p(y,\boldsymbol\theta\mid\mathbf{x}) = p(y\mid\mathbf{x},\boldsymbol\theta)p(\boldsymbol\theta) p ( y , θ ∣ x ) = p ( y ∣ x , θ ) p ( θ ) — 9.36 prior predictive N ( ϕ ⊤ m 0 , ϕ ⊤ S 0 ϕ + σ 2 ) \mathcal{N}\!\left(\phi^\top\mathbf{m}_0,\ \phi^\top\mathbf{S}_0\phi + \sigma^2\right) N ( ϕ ⊤ m 0 , ϕ ⊤ S 0 ϕ + σ 2 ) — 9.38 variance decomposition V [ y ∗ ] = V θ [ ϕ ⊤ θ ] + V ϵ [ ϵ ] \mathbb{V}[y_*] = \mathbb{V}_{\boldsymbol\theta}[\phi^\top\boldsymbol\theta] + \mathbb{V}_\epsilon[\epsilon] V [ y ∗ ] = V θ [ ϕ ⊤ θ ] + V ϵ [ ϵ ] — 9.39 noise-free version N ( ϕ ⊤ m 0 , ϕ ⊤ S 0 ϕ ) \mathcal{N}\!\left(\phi^\top\mathbf{m}_0,\ \phi^\top\mathbf{S}_0\phi\right) N ( ϕ ⊤ m 0 , ϕ ⊤ S 0 ϕ ) — 9.40 the posterior p ( θ ∣ X , Y ) = p ( Y ∣ X , θ ) p ( θ ) p ( Y ∣ X ) 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})} p ( θ ∣ X , Y ) = p ( Y ∣ X ) p ( Y ∣ X , θ ) p ( θ ) — 9.41 the marginal likelihood p ( Y ∣ X ) = ∫ p ( Y ∣ X , θ ) p ( θ ) d θ p(\mathcal{Y}\mid\mathcal{X}) = \int p(\mathcal{Y}\mid\mathcal{X},\boldsymbol\theta)p(\boldsymbol\theta)\,d\boldsymbol\theta p ( Y ∣ X ) = ∫ p ( Y ∣ X , θ ) p ( θ ) d θ — 9.42
S N = ( S 0 − 1 + σ − 2 Φ ⊤ Φ ) − 1 , m N = S N ( S 0 − 1 m 0 + σ − 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)\ } S N = ( S 0 − 1 + σ − 2 Φ ⊤ Φ ) − 1 , m N = S N ( S 0 − 1 m 0 + σ − 2 Φ ⊤ y )
property measured verified as a posterior (log gap constant in θ \boldsymbol\theta θ ) spread 1.805 × 10 − 12 1.805\times10^{-12} 1.805 × 1 0 − 12 that constant − log p ( Y ∣ X ) = 30.453407 -\log p(\mathcal{Y}\mid\mathcal{X}) = \mathbf{30.453407} − log p ( Y ∣ X ) = 30.453407 grid cross-check, 1400 × 1400 1400\times1400 1400 × 1400 , 2-D mean, sd, correlation to 10 − 8 10^{-8} 1 0 − 8 precisions add max ∣ S N A − I ∣ = 6.9 × 10 − 11 \max\lvert\mathbf{S}_N\mathbf{A}-\mathbf{I}\rvert = 6.9\times10^{-11} max ∣ S N A − I ∣ = 6.9 × 1 0 − 11 sequential updating batch vs one-at-a-time: 4.1 × 10 − 12 4.1\times10^{-12} 4.1 × 1 0 − 12 ; over 500 points, 6.8 × 10 − 15 6.8\times10^{-15} 6.8 × 1 0 − 15 m N \mathbf{m}_N m N vs θ MAP \boldsymbol\theta_{\text{MAP}} θ MAP 1.19 × 10 − 13 1.19\times10^{-13} 1.19 × 1 0 − 13 m N \mathbf{m}_N m N vs θ ML \boldsymbol\theta_{\text{ML}} θ ML at b 2 = 10 8 b^2 = 10^8 b 2 = 1 0 8 1.43 × 10 − 10 1.43\times10^{-10} 1.43 × 1 0 − 10 contraction sd × N → 0.37 \times\sqrt{N} \to 0.37 × N → 0.37 past N = 50 N = 50 N = 50 posterior correlations (prior’s are I \mathbf{I} I ) up to 0.969560 \mathbf{0.969560} 0.969560
p ( y ∗ ∣ X , Y , x ∗ ) = N ( ϕ ⊤ ( x ∗ ) m N , ϕ ⊤ ( x ∗ ) S N ϕ ( 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)} p ( y ∗ ∣ X , Y , x ∗ ) = N ( ϕ ⊤ ( x ∗ ) m N , ϕ ⊤ ( x ∗ ) S N ϕ ( x ∗ ) + σ 2 ) (9.57)
with E [ y ∗ ] = ϕ ⊤ m N = ϕ ⊤ θ MAP \mathbb{E}[y_*] = \phi^\top\mathbf{m}_N = \phi^\top\boldsymbol\theta_{\text{MAP}} E [ y ∗ ] = ϕ ⊤ m N = ϕ ⊤ θ MAP — measured to
8.438 × 10 − 14 8.438\times10^{-14} 8.438 × 1 0 − 14 over 400 inputs, while the MLE’s curve differs by 0.202578 0.202578 0.202578 .
S_N contains no targets
change to y \mathbf{y} y max ∣ S N − S N new ∣ \max\lvert\mathbf{S}_N - \mathbf{S}_N^{\text{new}}\rvert max ∣ S N − S N new ∣ shuffled 0.000 × 10 0 \mathbf{0.000\times10^{0}} 0.000 × 1 0 0 replaced with nonsense 0.000 × 10 0 \mathbf{0.000\times10^{0}} 0.000 × 1 0 0
while m N \mathbf{m}_N m N moves by 0.734789 0.734789 0.734789 . Feature: error bars are computable during experimental
design — measured, a clustered design gives a worst half-width of 286.948028 286.948028 286.948028 against 0.473974 0.473974 0.473974 for a
spread one, a factor of 605 605 605 . Limitation: the shading does not widen when the model fits badly.
E [ Y ∣ X ] = X m 0 (9.62) , C o v [ Y ∣ X ] = X S 0 X ⊤ + σ 2 I (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)} E [ Y ∣ X ] = X m 0 (9.62) , Cov [ Y ∣ X ] = X S 0 X ⊤ + σ 2 I (9.63)
p ( Y ∣ X ) = N ( y | X m 0 , X S 0 X ⊤ + σ 2 I ) (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)} p ( Y ∣ X ) = N ( y X m 0 , X S 0 X ⊤ + σ 2 I ) (9.64)
Use the K × K K\times K K × K form. Woodbury gives
det ( X S 0 X ⊤ + σ 2 I ) = det ( S N − 1 ) det ( S 0 ) σ 2 N \det(\mathbf{X}\mathbf{S}_0\mathbf{X}^\top + \sigma^2\mathbf{I}) = \det(\mathbf{S}_N^{-1})\det(\mathbf{S}_0)\sigma^{2N} det ( X S 0 X ⊤ + σ 2 I ) = det ( S N − 1 ) det ( S 0 ) σ 2 N :
agreeing to 8.9 × 10 − 6 8.9\times10^{-6} 8.9 × 1 0 − 6 at N = 5000 N=5000 N = 5000 and 4341 × 4341\times 4341 × faster at N = 4000 N=4000 N = 4000 .
It chooses the degree
M M M log p ( Y ∣ X ) \log p(\mathcal{Y}\mid\mathcal{X}) log p ( Y ∣ X ) max log lik test RMSE 2 2 2 − 46.492910 -46.492910 − 46.492910 − 36.6089 -36.6089 − 36.6089 0.6848 0.6848 0.6848 4 \mathbf{4} 4 − 23.985921 \mathbf{-23.985921} − 23.985921 − 2.2498 -2.2498 − 2.2498 0.3210 \mathbf{0.3210} 0.3210 6 6 6 − 34.643032 -34.643032 − 34.643032 1.5185 1.5185 1.5185 0.4440 0.4440 0.4440 9 9 9 − 54.242980 -54.242980 − 54.242980 6.9050 \mathbf{6.9050} 6.9050 16.7174 16.7174 16.7174
The maximum log likelihood rises from − 112.66 -112.66 − 112.66 to + 6.91 +6.91 + 6.91 and never turns . The evidence peaks at
M = 4 M=4 M = 4 — the same degree a 200-point test set picks, and the same one 5-fold CV picks, using none of it.
And it is hostage to the prior
Widening b 2 b^2 b 2 from 0.01 0.01 0.01 to 10 8 10^8 1 0 8 on identical data: degree 9 loses 91.07 \mathbf{91.07} 91.07 nats, degree 1
loses 20.60 20.60 20.60 . The ordering of degrees 5 and 3 flips from + 10.21 +10.21 + 10.21 to − 6.42 -6.42 − 6.42 . The winner held at M = 4 M=4 M = 4
here; page 808 measured a case where it did not.
what equation the scalar estimator θ ML = X ⊤ y X ⊤ X \theta_{\text{ML}} = \dfrac{\mathbf{X}^\top\mathbf{y}}{\mathbf{X}^\top\mathbf{X}} θ ML = X ⊤ X X ⊤ y — 9.66 the projection X θ ML = X X ⊤ X ⊤ X y \mathbf{X}\theta_{\text{ML}} = \dfrac{\mathbf{X}\mathbf{X}^\top}{\mathbf{X}^\top\mathbf{X}}\mathbf{y} X θ ML = X ⊤ X X X ⊤ y — 9.67 the general case P = Φ ( Φ ⊤ Φ ) − 1 Φ ⊤ P = \boldsymbol\Phi(\boldsymbol\Phi^\top\boldsymbol\Phi)^{-1}\boldsymbol\Phi^\top P = Φ ( Φ ⊤ Φ ) − 1 Φ ⊤ — 9.69 , 9.70 orthonormal features Φ ⊤ Φ = I \boldsymbol\Phi^\top\boldsymbol\Phi = \mathbf{I} Φ ⊤ Φ = I , so P = Φ Φ ⊤ P = \boldsymbol\Phi\boldsymbol\Phi^\top P = Φ Φ ⊤
property measured idempotent, P P = P PP = P P P = P 5.551 × 10 − 17 5.551\times10^{-17} 5.551 × 1 0 − 17 symmetric, P = P ⊤ P = P^\top P = P ⊤ 0.000 × 10 0 0.000\times10^{0} 0.000 × 1 0 0 t r ( P ) = K \mathrm{tr}(P) = K tr ( P ) = K exact to 8 decimals, every degree residual orthogonal, Φ ⊤ r = 0 \boldsymbol\Phi^\top\mathbf{r} = \mathbf{0} Φ ⊤ r = 0 9.551 × 10 − 15 9.551\times10^{-15} 9.551 × 1 0 − 15 Pythagoras, ∥ y ∥ 2 = ∥ P y ∥ 2 + ∥ r ∥ 2 \lVert\mathbf{y}\rVert^2 = \lVert P\mathbf{y}\rVert^2 + \lVert\mathbf{r}\rVert^2 ∥ y ∥ 2 = ∥ P y ∥ 2 + ∥ r ∥ 2 8.53 × 10 − 14 8.53\times10^{-14} 8.53 × 1 0 − 14
Why Equation 9.22 is biased, in one line
E [ ∥ ( I − P ) y ∥ 2 ] = σ 2 t r ( I − P ) = σ 2 ( N − K ) \mathbb{E}\!\left[\lVert(\mathbf{I}-P)\mathbf{y}\rVert^2\right] = \sigma^2\,\mathrm{tr}(\mathbf{I}-P) = \sigma^2(N-K) E [ ∥( I − P ) y ∥ 2 ] = σ 2 tr ( I − P ) = σ 2 ( N − K ) Measured 0.200222 0.200222 0.200222 against σ 2 ( N − K ) = 0.200000 \sigma^2(N-K) = 0.200000 σ 2 ( N − K ) = 0.200000 , where Equation 9.22 assumes σ 2 N = 0.400000 \sigma^2 N = 0.400000 σ 2 N = 0.400000 .
The fit has already spent K K K of the N N N dimensions.
The basis is only a coordinate system
Monomials and an orthonormal basis for the same span: projection matrices agree to 2.384 × 10 − 13 2.384\times10^{-13} 2.384 × 1 0 − 13 ,
fitted values to 4.802 × 10 − 13 4.802\times10^{-13} 4.802 × 1 0 − 13 — with κ = 2.195 × 10 26 \kappa = 2.195\times10^{26} κ = 2.195 × 1 0 26 and 1.000000 \mathbf{1.000000} 1.000000 , and
parameter norms of 1.198468 1.198468 1.198468 and 3.096718 3.096718 3.096718 .
A ridge penalty acts on coordinates , so changing the basis changes what it penalises while leaving
the unregularised fit untouched. Nothing here is special to polynomials: Gaussian bumps give trace 6 6 6
and are 4 4 4 –5 5 5 orders of magnitude better conditioned.
pointer what it says generalized linear models x k + 1 = σ k ( A k x k + b k ) x_{k+1} = \sigma_k(\mathbf{A}_kx_k + \mathbf{b}_k) x k + 1 = σ k ( A k x k + b k ) — 9.72 . A K K K -layer deep network is a composition of these.neural networks far more expressive, but maximum likelihood is non-convex and Bayesian marginalization is intractable Gaussian processes place a distribution directly on functions , “without the detour via the parameters”, via the kernel trick non-Gaussian priors for N ≪ D N \ll D N ≪ D the problem is underdetermined; a Laplace prior enforces sparsity — equivalent to ℓ 1 \ell_1 ℓ 1 , i.e. LASSO (Tibshirani, 1996)
The Gaussian process is already here
Page 905 measured that p ( θ ) = N ( 0 , S 0 ) p(\boldsymbol\theta) = \mathcal{N}(\mathbf{0},\mathbf{S}_0) p ( θ ) = N ( 0 , S 0 ) induces the
covariance function k ( x a , x b ) = ϕ ( x a ) ⊤ S 0 ϕ ( x b ) k(x_a,x_b) = \phi(x_a)^\top\mathbf{S}_0\phi(x_b) k ( x a , x b ) = ϕ ( x a ) ⊤ S 0 ϕ ( x b ) — matched to sampling within
0.5 % 0.5\% 0.5% , including a negative value of − 204.75 -204.75 − 204.75 between x = − 2 x=-2 x = − 2 and x = + 2 x=+2 x = + 2 . That function is the
kernel §9.5 points to.
quantity value page likelihood’s integral over θ \theta θ exactly 1 / ∣ x ∣ 1/\lvert x\rvert 1/ ∣ x ∣ 901 superposition, θ \boldsymbol\theta θ vs x x x 4.4 × 10 − 11 4.4\times10^{-11} 4.4 × 1 0 − 11 vs 2.3 × 10 5 2.3\times10^{5} 2.3 × 1 0 5 901 product of N N N densities underflows at N = 1000 N = 1000 N = 1000 , exactly 0.0 0.0 0.0 901 κ ( Φ ⊤ Φ ) / κ ( Φ ) 2 \kappa(\boldsymbol\Phi^\top\boldsymbol\Phi)/\kappa(\boldsymbol\Phi)^2 κ ( Φ ⊤ Φ ) / κ ( Φ ) 2 1.000000 1.000000 1.000000 902 normal equations vs lstsq at M = 16 M=16 M = 16 1157.7 × 1157.7\times 1157.7 × worse902 Eq 9.22 bias exactly ( N − K ) / N (N-K)/N ( N − K ) / N 902 test RMSE at M = N − 1 = 9 M = N-1 = 9 M = N − 1 = 9 100.850623 100.850623 100.850623 903 M = 4 M=4 M = 4 wins over 2000 draws46.1 % 46.1\% 46.1% 903 λ \lambda λ that makes RLS = = = MAPσ 2 / b 2 \sigma^2/b^2 σ 2 / b 2 , to 0.00 × 10 0 0.00\times10^{0} 0.00 × 1 0 0 904 ridge exact zeros, any λ \lambda λ 0 \mathbf{0} 0 of 30904 95% prior band at x = 5 x=5 x = 5 , degree 5 3125.5935 3125.5935 3125.5935 905 prior band fits the book’s axes at 48 48 48 of 200 200 200 inputs905 C o v [ f ( − 2 ) , f ( 2 ) ] \mathrm{Cov}[f(-2), f(2)] Cov [ f ( − 2 ) , f ( 2 )] − 204.75 -204.75 − 204.75 905 Theorem 9.1’s constant offset 30.453407 30.453407 30.453407 906 sequential vs batch, 500 points 6.772 × 10 − 15 6.772\times10^{-15} 6.772 × 1 0 − 15 906, 910 posterior correlation, prior = I =\mathbf{I} = I 0.969560 0.969560 0.969560 906 Eq 9.57 vs Eq 9.6 coverage 0.9487 0.9487 0.9487 /0.9499 0.9499 0.9499 vs 0.7419 0.7419 0.7419 /0.1112 0.1112 0.1112 907 S N \mathbf{S}_N S N under shuffled targets0.000 × 10 0 0.000\times10^{0} 0.000 × 1 0 0 907 K × K K\times K K × K evidence speedup at N = 4000 N=4000 N = 4000 4341 × 4341\times 4341 × 908 evidence peak M = 4 M = 4 M = 4 , matching CV and the test set908, 910 t r ( P ) \mathrm{tr}(P) tr ( P ) = K = K = K , exact909 E ∥ ( I − P ) y ∥ 2 \mathbb{E}\lVert(\mathbf{I}-P)\mathbf{y}\rVert^2 E ∥( I − P ) y ∥ 2 0.200222 0.200222 0.200222 vs σ 2 ( N − K ) = 0.2 \sigma^2(N-K) = 0.2 σ 2 ( N − K ) = 0.2 909 κ \kappa κ : monomial vs orthonormal, M = 18 M=18 M = 18 2.195 × 10 26 2.195\times10^{26} 2.195 × 1 0 26 vs 1.000000 1.000000 1.000000 909 experimental design, clustered vs spread 286.948028 286.948028 286.948028 vs 0.473974 0.473974 0.473974 910
Model the noise, not the loss. Everything follows from Equation 9.1.
“Linear” constrains θ \boldsymbol\theta θ , not x x x — to 4.4 × 10 − 11 4.4\times10^{-11} 4.4 × 1 0 − 11 against 2.3 × 10 5 2.3\times10^{5} 2.3 × 1 0 5 .
Equation 9.4 has no intercept , and a missing feature corrupts the ones you kept.
The objective is quadratic , so one solve suffices and Chapter 7 is unnecessary — until you leave the class.
Write Equation 9.12c; call np.linalg.lstsq . The Gram matrix squares the condition number.
Equation 9.22 is biased by ( N − K ) / N (N-K)/N ( N − K ) / N , because t r ( I − P ) = N − K \mathrm{tr}(\mathbf{I}-P) = N-K tr ( I − P ) = N − K . Divide by N − K N-K N − K .
The training error cannot rise , so it carries no information about generalization.
A penalty is a prior — with λ = σ 2 / b 2 \lambda = \sigma^2/b^2 λ = σ 2 / b 2 for Equation 9.32, and never without naming the objective.
Precisions add , so the posterior update runs online in fixed memory, exactly.
MAP and Bayesian give the same curve , to 8.4 × 10 − 14 8.4\times10^{-14} 8.4 × 1 0 − 14 . The whole return is ϕ ⊤ S N ϕ \phi^\top\mathbf{S}_N\phi ϕ ⊤ S N ϕ .
That term is calibrated — 0.9487 0.9487 0.9487 against 0.1112 0.1112 0.1112 — and it never saw the targets, which makes it both a design tool and a blind spot.
A projection is a property of the subspace. The basis is a coordinate system, and some are 10 26 10^{26} 1 0 26 times better than others.
Back to the start: Linear Regression Overview