Chapter 10 Worked Problems
| # | problem | sections | the answer in one line |
|---|---|---|---|
| 1 | What do the two ends of the budget cost? | §10.2–10.3 | is the mean image, RMS |
| 2 | How should you choose ? | §10.2, §10.8 | four defensible rules, four answers: , , , |
| 3 | What is PCA equivariant to? | §10.3.3, §10.6 | rotations yes (), rescaling no () |
| 4 | Make the code’s components comparable | §10.2.2 | whitening: covariance to |
| 5 | Fill in pixels you never observed | §10.7 | better than mean-filling at missing |
| 6 | Score novelty with what PCA discards | §10.3.3, §10.7 | every digit “0” above the s’ th percentile |
| 7 | Where must a linear method fail? | §10.8 | a circle: two eigenvalues, and |
| 8 | Run §10.5’s derivation with a kernel | §10.5, §10.8 | separation |
All eight share one setup:
import numpy as np
from sklearn.datasets import load_digits
dig = load_digits()
A8 = dig.data[dig.target == 8] # (174, 64) -- rows are images
N, D = A8.shape
MU = A8.mean(0)
X = (A8 - MU).T # D x N, the book's column layout
S = X @ X.T / N # Equation 10.1
w, V = np.linalg.eigh(S)
LAM, PC = w[::-1], V[:, ::-1] # descending
TOT = LAM.sum() # 741.158872
def J(B):
"""Equation 10.29, for all N points at once."""
return float(((X - B @ B.T @ X) ** 2).sum() / N)Problem 1 — What do the two ends of the budget cost?
Section titled “Problem 1 — What do the two ends of the budget cost?”Statement. Page 1004 measured for every . Evaluate the two extremes and say in plain terms what each one is.
Method. Read off and , then confirm against a direct computation that never mentions eigenvectors.
for M in (0, 1, 52, 64):
print(f"{M:>4} {LAM[:M].sum():>14.6f} {LAM[M:].sum():>14.6f} "
f"{TOT:>14.6f}")
print(f"J_0 = trace(S) : {TOT:.6f}")
print(f"measured, mean-only RMS error : "
f"{float(np.sqrt(((A8 - MU)**2).sum(1).mean())):.6f}")
print(f"sqrt(J_0) : {np.sqrt(TOT):.6f}") 0 0.000000 741.158872 741.158872
1 151.568412 589.590460 741.158872
52 741.158872 0.000000 741.158872
64 741.158872 0.000000 741.158872
J_0 = trace(S) : 741.158872
measured, mean-only RMS error : 27.224233
sqrt(J_0) : 27.224233Answer. is the mean image, and it is not a trivial baseline.
| what the model is | RMS error | ||
|---|---|---|---|
| predict for every input | |||
| the data’s own rank | |||
| the whole space |
exactly, and is the RMS distance from each image to the mean image — so every reported reconstruction error should be read against , not against zero. At , is a reduction in squared error; at it is .
The two rows at the top of the table are the same row twice. Rows and are identical because the last eigenvalues are page 1001’s dead border pixels — the last twelve components are free and worthless simultaneously.
Problem 2 — How should you choose M?
Section titled “Problem 2 — How should you choose M?”Statement. The chapter never says. §10.8 mentions the Gavish–Donoho heuristic, cross-validation, and Bayesian model selection. Apply four defensible rules to the same spectrum and compare.
Method. Estimate from the tail; apply the singular-value threshold; take the and variance crossings; take the largest one-step drop.
sig = np.linalg.svd(X, compute_uv=False)
s2_hat = LAM[30:].mean() # a rough noise estimate
thr = 4 * np.sqrt(s2_hat) * np.sqrt(D) / np.sqrt(3)
cum = np.cumsum(LAM) / TOT
drops = LAM[:-1] - LAM[1:]
print(f"noise estimate (mean of lambda_31..64) : {s2_hat:.6f}")
print(f"Gavish-Donoho threshold : {thr:.6f}")
print(f" singular values above it : M = {int((sig > thr).sum())}")
print(f"90% of the variance : "
f"M = {int(np.searchsorted(cum, 0.90) + 1)}")
print(f"95% of the variance : "
f"M = {int(np.searchsorted(cum, 0.95) + 1)}")
print(f"largest one-step drop ('the elbow') : "
f"M = {int(np.argmax(drops[:40]) + 1)}")noise estimate (mean of lambda_31..64) : 0.555996
Gavish-Donoho threshold : 13.776062
singular values above it : M = 38
90% of the variance : M = 18
95% of the variance : M = 25
largest one-step drop ('the elbow') : M = 1Answer. Four rules, four answers: , , , .
The elbow rule returns , which is worth dwelling on. It looks for the biggest step down, and the biggest step down is always near the top of a decaying spectrum — here against . “Look for the elbow” is not an algorithm; it works when there is a visible cliff and returns nonsense when there is not.
And the obvious remaining rule does not work either:
rng = np.random.default_rng(0)
idx = rng.permutation(N)
tr, te = idx[:120], idx[120:]
mu_t = A8[tr].mean(0)
Xt = (A8[tr] - mu_t).T
PCt = np.linalg.eigh(Xt @ Xt.T / len(tr))[1][:, ::-1]
for M in (1, 5, 10, 20, 30, 40, 50, 60, 64):
B = PCt[:, :M]
Xe = (A8[te] - mu_t).T
print(f"{M:>4} {float(((Xt - B @ B.T @ Xt)**2).sum()/len(tr)):>14.6f} "
f"{float(((Xe - B @ B.T @ Xe)**2).sum()/len(te)):>14.6f}") 1 582.549798 615.960690
5 315.499541 355.419932
10 161.603235 201.835913
20 54.636152 88.043453
30 15.545064 37.539126
40 2.103496 7.816653
50 0.000910 0.087346
60 0.000000 0.000000
64 0.000000 0.000000Problem 3 — What is PCA equivariant to?
Section titled “Problem 3 — What is PCA equivariant to?”Statement. Page 1007 measured that rescaling a column changes the answer. Is the reverse true for rotations — and is that a coincidence?
Method. Rotate the whole dataset by an orthogonal and check whether the new principal subspace is the old one rotated. Then rescale a block of columns and measure the angle.
def lead_sub(A, M=5):
Ac = A - A.mean(0)
w2, V2 = np.linalg.eigh(Ac.T @ Ac / len(A))
return V2[:, ::-1][:, :M]
R = np.linalg.qr(np.random.default_rng(11).standard_normal((D, D)))[0]
Braw, Brot = lead_sub(A8), lead_sub(A8 @ R.T)
print(f"is R B inside the rotated subspace? "
f"{np.abs(R @ Braw - Brot @ Brot.T @ (R @ Braw)).max():.3e}")
print(f"J_5 before : {J(Braw):.6f}")
Xr = (A8 @ R.T - (A8 @ R.T).mean(0)).T
print(f"J_5 after : {float(((Xr - Brot @ Brot.T @ Xr)**2).sum()/N):.6f}")
sc = np.ones(D); sc[:32] = 4.0
Bsc = lead_sub(A8 * sc)
print(f"rescaling 32 columns by 4: angle b_1 moves "
f"{np.degrees(np.arccos(min(1.0, abs(Braw[:, 0] @ Bsc[:, 0])))):.4f} deg")is R B inside the rotated subspace? 8.049e-16
J_5 before : 320.123369
J_5 after : 320.123369
rescaling 32 columns by 4: angle b_1 moves 59.2214 degAnswer. PCA commutes with rotations and does not commute with rescaling, and both follow from one line of algebra.
Under the covariance becomes , whose eigenvectors are with the same eigenvalues — so the subspace rotates with the data and is unchanged to . Under a diagonal rescaling becomes , which has no such relationship.
This is page 1007’s Step 2 in one sentence: rescaling is the one transformation PCA is sensitive to, which is precisely why standardising is a decision you have to make rather than a step you can skip.
Problem 4 — Make the code’s components comparable
Section titled “Problem 4 — Make the code’s components comparable”Statement. The code’s components have variances , spanning a factor of at on this data. Any downstream method using Euclidean distance in code space will weight them unequally. Fix it without losing anything.
Method. Divide each component by and measure the resulting covariance.
M = 10
B = PC[:, :M]
Z = B.T @ X
Zw = Z / np.sqrt(LAM[:M])[:, None]
for name, Q in (("z = B'x", Z), ("whitened", Zw)):
C = np.cov(Q, bias=True)
print(f"{name:>10}: diag {np.round(np.diag(C)[:4], 4)} ... "
f"max off-diagonal {np.abs(C - np.diag(np.diag(C))).max():.2e}")
print(f"whitened covariance vs I : "
f"{np.abs(np.cov(Zw, bias=True) - np.eye(M)).max():.3e}") z = B'x: diag [151.5684 87.7138 75.2849 54.0551] ... max off-diagonal 5.05e-14
whitened: diag [1. 1. 1. 1.] ... max off-diagonal 4.76e-16
whitened covariance vs I : 1.665e-15Answer. Whitening makes the code’s covariance the identity, to .
Two things to be clear about. First, it is not PCA — it is a change of units applied afterwards, and it is exactly invertible, so nothing is discarded. Second, it undoes something PCA deliberately produced: the sorted variances that page 1004 identified as the eigenbasis’s free gift. After whitening every component looks equally important, which is right for a distance-based method downstream and wrong if you wanted to know which components matter.
A practical caution: dividing by amplifies the components you trust least. Page 1008 measured the posterior variance as — largest exactly where is smallest — so whitening the tail of the spectrum multiplies up the noisiest directions.
Problem 5 — Fill in pixels you never observed
Section titled “Problem 5 — Fill in pixels you never observed”Statement. §10.7’s payoff list includes “deal with data dimensions that are missing at random by applying Bayes’ theorem”. The chapter never does it. Do it, and measure against the obvious baseline.
Method. With PPCA at and , condition on the observed entries only: , then predict the hidden ones as .
rg = np.random.default_rng(4)
M = 10
sig2 = LAM[M:].mean()
Bml = PC[:, :M] * np.sqrt(np.maximum(LAM[:M] - sig2, 0.0))
for frac in (0.1, 0.25, 0.5):
em, ep = [], []
for n in range(N):
x = A8[n].astype(float)
obs = rg.random(D) > frac
if obs.sum() < M + 1:
continue
em.append(((x[~obs] - MU[~obs]) ** 2).mean())
Bo = Bml[obs]
m = np.linalg.solve(Bo.T @ Bo + sig2*np.eye(M),
Bo.T @ (x[obs] - MU[obs]))
ep.append(((x[~obs] - (Bml[~obs] @ m + MU[~obs])) ** 2).mean())
a, b = np.sqrt(np.mean(em)), np.sqrt(np.mean(ep))
print(f"{frac:>4.0%} hidden: mean-fill {a:.6f} PPCA {b:.6f} "
f"({100*(1-b/a):.1f}% better)") 10% hidden: mean-fill 3.382414 PPCA 2.137729 (36.8% better)
25% hidden: mean-fill 3.427848 PPCA 2.322339 (32.3% better)
50% hidden: mean-fill 3.359769 PPCA 2.457468 (26.9% better)Answer. PPCA beats mean-filling by at missing, falling to at .
The advantage shrinks as more is hidden, which is the honest behaviour: with fewer observed pixels the posterior over the code is wider, so its mean is pulled further toward and the prediction further toward — the baseline.
Plain PCA cannot do this at all. Equation 10.32’s needs every entry of ; there is no partial version. The probabilistic model supplies one for free, because conditioning a Gaussian on a subset of its coordinates is just Gaussian conditioning again.
Problem 6 — Score novelty with what PCA discards
Section titled “Problem 6 — Score novelty with what PCA discards”Statement. §10.7’s list includes “give us a notion of the novelty of a new data point” and credits it to the probabilistic model. Show that the non-probabilistic part already gives most of it.
Method. Fit on the “8”s only. Score every image by — page 1003’s displacement, the part living in .
M = 10
B = PC[:, :M]
res = np.linalg.norm(X - B @ B.T @ X, axis=0)
print(f"digit '8' : mean {res.mean():.4f}, sd {res.std():.4f}, "
f"max {res.max():.4f}")
for d in (0, 1, 3, 5):
Xo = (dig.data[dig.target == d] - MU).T
ro = np.linalg.norm(Xo - B @ B.T @ Xo, axis=0)
print(f"digit '{d}' : mean {ro.mean():.4f}, "
f"{100*float((ro > np.percentile(res, 95)).mean()):.1f}% above "
f"the 8s' 95th percentile")digit '8' : mean 12.6019, sd 2.7169, max 20.1055
digit '0' : mean 29.9223, 100.0% above the 8s' 95th percentile
digit '1' : mean 21.6711, 63.7% above the 8s' 95th percentile
digit '3' : mean 24.1030, 97.8% above the 8s' 95th percentile
digit '5' : mean 25.3754, 100.0% above the 8s' 95th percentileAnswer. The residual norm is already a usable novelty score, at no extra cost.
| digit | mean residual | flagged at the th percentile |
|---|---|---|
| (the training class) | by construction | |
The digit “1” is the hard case at , and the reason is visible in the data rather than the method: a “1” is mostly a vertical stroke, which the “8” subspace can partly express because an “8” contains one.
What §10.7 adds is a calibrated version. from Equation 10.70b converts the residual into a density, which combines the part with how extreme the code is inside — a point sitting on the subspace but at ten standard deviations along has residual zero and is still an outlier.
Problem 7 — Where must a linear method fail?
Section titled “Problem 7 — Where must a linear method fail?”Statement. §10.8 lists nonlinear extensions. Construct the smallest example that forces one.
Method. A noisy circle in : one intrinsic degree of freedom, the angle.
t = np.linspace(0, 2*np.pi, 400, endpoint=False)
circ = (np.c_[np.cos(t), np.sin(t)]
+ 0.02 * np.random.default_rng(1).standard_normal((400, 2)))
cc = circ - circ.mean(0)
wc = np.linalg.eigvalsh(cc.T @ cc / len(cc))[::-1]
print(f"eigenvalues : {np.round(wc, 6)}")
print(f"best 1-D subspace keeps : {wc[0]/wc.sum():.2%}")
print(f"M = 1 loses : {wc[1]/wc.sum():.2%}")eigenvalues : [0.501038 0.497606]
best 1-D subspace keeps : 50.17%
M = 1 loses : 49.83%Answer. Two nearly equal eigenvalues, and no one-dimensional subspace keeps more than .
The data has one degree of freedom and PCA needs two dimensions to represent it. The failure is not approximation error — it is that the circle’s intrinsic coordinate is an angle, and no linear map from to is injective on a circle.
Note what this does not say. PCA is not wrong here; it is answering its own question correctly, and its own question is “which linear subspace”. Every extension §10.8 lists — kernel PCA, deep auto-encoders, the GP-LVM — replaces the linear map, not the objective.
And the near-tie has a second consequence worth seeing: with , page 1005’s power iteration would need roughly steps to separate them, and the “first principal component” that emerges is an arbitrary direction determined by noise.
Problem 8 — Run §10.5’s derivation with a kernel
Section titled “Problem 8 — Run §10.5’s derivation with a kernel”Statement. Page 1006 noted that every entry of is an inner product and that never appears. §10.8 says the idea “can be pushed to the extreme”. Push it.
Method. Replace with , centre the kernel matrix, and decompose it. Test on two concentric rings, which Problem 7 says linear PCA cannot separate.
rg2 = np.random.default_rng(2)
n1 = 150
r = np.r_[rg2.normal(1.0, 0.08, n1), rg2.normal(3.0, 0.08, n1)]
th = rg2.uniform(0, 2*np.pi, 2*n1)
P2 = np.c_[r*np.cos(th), r*np.sin(th)]
lab = np.r_[np.zeros(n1), np.ones(n1)]
Pc = P2 - P2.mean(0)
z_lin = Pc @ np.linalg.eigh(Pc.T @ Pc / len(Pc))[1][:, -1]
d2 = ((P2[:, None, :] - P2[None, :, :]) ** 2).sum(-1)
K = np.exp(-0.6 * d2)
n = len(P2); O = np.ones((n, n)) / n
Kc = K - O @ K - K @ O + O @ K @ O # the centring of Step 1
ww, VV = np.linalg.eigh(Kc)
z_ker = VV[:, -1] * np.sqrt(max(ww[-1], 0))
for name, z in (("linear PCA", z_lin), ("kernel PCA", z_ker)):
a, b = z[lab == 0], z[lab == 1]
sep = abs(a.mean() - b.mean()) / np.sqrt(0.5*(a.var() + b.var()))
ov = 100*float(((a > b.min()) & (a < b.max())).mean())
print(f"{name}: separation {sep:>8.4f}, inner-ring points inside "
f"the outer ring's range {ov:5.1f}%")linear PCA: separation 0.0597, inner-ring points inside the outer ring's range 100.0%
kernel PCA: separation 7.5299, inner-ring points inside the outer ring's range 0.0%Answer. Separation , and the overlap goes from complete to none.
Linear PCA scores — the two rings share a centre, so no direction separates them and every inner point falls inside the outer ring’s range. One component of kernel PCA separates them completely.
The point is what changed in the code: the kernel matrix replaced the Gram matrix and nothing else. The centring step is the kernel version of Step 1, the eigendecomposition is §10.2’s, and the coordinates come out as in §10.5. The feature map behind an RBF kernel is infinite-dimensional and is never written down — which is the entire content of §10.8’s remark, and of Chapter 12’s treatment of the support vector machine.
-
Why is held-out reconstruction error useless for choosing M?
Measured on a 120/54 split: 615.960690 at M = 1 falling to 0.000000 at M = 60, with no rise anywhere. Chapter 9's test RMSE could rise because a prediction of y can get worse; there is no y here. Choosing M needs an external cost, or Section 10.7's likelihood, which integrates rather than fits.
pch.quizShowAnswer
B — It falls monotonically to zero at M = D, because a larger subspace can never project a point further away — Measured on a 120/54 split: 615.960690 at M = 1 falling to 0.000000 at M = 60, with no rise anywhere. Chapter 9's test RMSE could rise because a prediction of y can get worse; there is no y here. Choosing M needs an external cost, or Section 10.7's likelihood, which integrates rather than fits.
-
What transformation is PCA equivariant to, and which is it not?
Under an orthogonal R the covariance becomes R S R-transpose, whose eigenvectors are R b with the same eigenvalues; J_M is unchanged. A diagonal rescaling gives Sigma S Sigma, which has no such relationship. That is exactly why Section 10.6's Step 2 is a decision and not a formality.
pch.quizShowAnswer
B — Rotation yes — the subspace rotates with the data, measured to 8.0e-16 — but rescaling no, which moved the leading direction 59.2214 degrees — Under an orthogonal R the covariance becomes R S R-transpose, whose eigenvectors are R b with the same eigenvalues; J_M is unchanged. A diagonal rescaling gives Sigma S Sigma, which has no such relationship. That is exactly why Section 10.6's Step 2 is a decision and not a formality.
-
How does PPCA fill in a pixel it never observed?
Restrict B to the observed rows, solve the M-by-M system, and read off the hidden rows. Plain PCA has no partial version of z = B-transpose x. The advantage shrinks as more is hidden — 26.9 percent at half missing — because a wider posterior pulls the prediction back towards the mean, which is the baseline.
pch.quizShowAnswer
B — It conditions the Gaussian on the observed entries only, giving a posterior over the code that predicts the rest — 36.8 percent better than mean-filling at 10 percent missing — Restrict B to the observed rows, solve the M-by-M system, and read off the hidden rows. Plain PCA has no partial version of z = B-transpose x. The advantage shrinks as more is hidden — 26.9 percent at half missing — because a wider posterior pulls the prediction back towards the mean, which is the baseline.
-
What did the kernel-PCA problem actually change?
Every entry of Section 10.5's N-by-N matrix is an inner product, and the dimension D appears nowhere in it. Swap the inner product for an RBF kernel and the separation of two concentric rings goes from 0.0597 to 7.5299 on one component. The feature map is infinite-dimensional and never written down.
pch.quizShowAnswer
B — Only the matrix being decomposed: a kernel matrix in place of the Gram matrix of inner products — Every entry of Section 10.5's N-by-N matrix is an inner product, and the dimension D appears nowhere in it. Swap the inner product for an RBF kernel and the separation of two concentric rings goes from 0.0597 to 7.5299 on one component. The feature map is infinite-dimensional and never written down.
Exercises
Section titled “Exercises”Exercise 1 – The baseline every error should be read against
Section titled “Exercise 1 – The baseline every error should be read against”Exercise 2 – Four rules that disagree
Section titled “Exercise 2 – Four rules that disagree”Exercise 3 – Rotate the data, then rescale it
Section titled “Exercise 3 – Rotate the data, then rescale it”Exercise 4 – Predict what you cannot see
Section titled “Exercise 4 – Predict what you cannot see”Exercise 5 – Swap the inner product for a kernel
Section titled “Exercise 5 – Swap the inner product for a kernel”Recall card
Section titled “Recall card”- M equal to zero is the mean image, and its error is 27.224233 on this data. Every reconstruction error should be read against that, not against zero.
- The last twelve components are free and worthless at the same time — they are the dead border pixels, so keeping the data’s full rank of 52 and keeping all 64 give the same error.
- Four defensible rules for choosing M give 1, 18, 25 and 38. The elbow rule returns one, because the biggest step down is near the top of any decaying spectrum.
- Held-out reconstruction error is not a model-selection criterion. It falls monotonically to zero, because a larger subspace can never project a point further away — on any data at all.
- PCA commutes with rotations and not with rescaling, measured at 8.0e-16 and 59.2214 degrees. That asymmetry is the entire reason standardising is a decision.
- Whitening makes the code’s covariance the identity to 1.7e-15, is exactly invertible, and amplifies the components the model trusts least.
- PPCA can predict pixels it never saw, beating mean-filling by 36.8 percent at ten percent missing and 26.9 percent at half. Plain PCA has no partial version of the code.
- The residual norm is already a novelty score. Fitted on eights, it flags every zero and every five, 97.8 percent of threes, and 63.7 percent of ones.
- A noisy circle defeats PCA completely: two nearly equal eigenvalues, and no line keeps more than 50.17 percent. The intrinsic coordinate is an angle, and no linear map is injective on a circle.
- Kernel PCA takes one line. Swap the Gram matrix for a kernel matrix and the separation of two concentric rings goes from 0.0597 to 7.5299 — because the dimension never appeared in that matrix to begin with.
Next: Chapter 10 Formula Sheet — every equation, every measured constant, on one page.
pch.coffeeTagline
pch.coffeeCtapch.feedbackHeading
pch.feedbackSubheading