DTU 02471 · Problem set 1

Validation, probability and first signals

How to test a model honestly, two classic distance-based methods, the rules of expectation and Bayes, and the first signal tools: convolution, spectra and PCA.

Problem 1.1

Cross-validation

Which statement about cross-validation is correct? (a) LOO is expensive because one model per observation is trained; (b) with few observations LOO is in general worse than 5-fold; (c) two levels of CV are necessary to choose parameters; (d) 4-fold CV equals a 25 % hold-out.

A model always looks good on the data it was trained on. To estimate how it does on new data, hide part of the data, train on the rest and test on the hidden part. K-fold cross-validation does this K times, so that every observation is tested exactly once, and averages the K test errors.

$$\hat E_{\text{CV}}=\frac1K\sum_{k=1}^{K}E_k$$ $$N_{\text{train}}=N-\tfrac NK,\ \ N_{\text{test}}=\tfrac NK$$ $$\text{LOO: }K=N$$

Section 3.13, p. 108

The red fold is the test set and blue is training. Drag K up to N = 20 to get leave-one-out: 20 models, each trained on 19 points.

Solution

(a) true. LOO means $K=N$, so $N$ models are trained on $N-1$ points each.

(b) false. There is no general rule. LOO even keeps more training data per fit, which helps when $N$ is small.

(c) false. One level of CV is enough to select parameters. The outer level is needed only to estimate the error of that selection.

(d) false. 4-fold CV uses 4 splits and tests every point once. A 25 % hold-out is one split.

Answer: (a)

Tip: the stated cost of LOO is in "models trained": $N$ of them, versus only $K$ for K-fold. That count is what makes (a) true.

Problem 1.2

Two-level cross-validation: what it costs

N = 5000. Hold out 10 % for the final error estimate, run 5-fold CV on the rest for 4 values of λ, then retrain on all CV data and test on the hold-out. Training on n points costs n², testing costs ½n². Total time?

The inner level chooses λ, and the outer hold-out grades the chosen model on data it never saw. To find the cost, count every train and every test block with its size.

$$\begin{aligned}C&=|\Lambda|\cdot K\left(N_{\text{tr}}^2+\tfrac12N_{\text{te}}^2\right)\\&\quad+N_{\text{CV}}^2+\tfrac12N_{\text{hold}}^2\end{aligned}$$ line 1: inner CV · line 2: final fit · K-fold scheme: Section 3.13, p. 108

Each square of the 4 × 5 grid is one train (3600 points) + test (900 points) run. The counter adds its cost as it ticks.

Solution

Hold-out: $0.1\cdot5000=500$, so $N_{\text{CV}}=4500$.

Each fold: test $4500/5=900$, train $4500-900=3600$.

Inner CV: $4\cdot5\,(3600^2+\tfrac12\cdot900^2)=20\cdot13\,365\,000=267\,300\,000$

Final fit: $4500^2+\tfrac12\cdot500^2=20\,250\,000+125\,000=20\,375\,000$

Total: 287 675 000 units of time

Trap: inside the CV, models are trained on 3600 points, not 4500. And don't forget the final retrain on all 4500 points with the best λ.

Problem 1.3

k-nearest neighbours with k = 3

Given the 6 × 6 table of Euclidean distances between R1, R2, R3 (red) and B1, B2, B3 (blue), classify each point with k = 3 using the other points. Which are classified correctly?

k-NN has no training step: to label a point, find the k closest labelled points and let them vote. Only the distances matter, so a distance table is all we need. Below, each query's neighbours are laid out on a distance ruler, and a circle grows until it has caught three of them.

$$\hat y_n=\arg\max_{c\in\{R,B\}}\ \sum_{m\in N_3(n)}\mathbf 1\{y_m=c\}$$ $$n\notin N_3(n)$$

Section 7.5, p. 307

The ruler shows exact distances from the table, so no 2-D map is needed. Step moves to the next query point.

Solution

point	3 nearest (distance)	vote	predicted
R1	B2 1.59, B3 2.61, R3 2.84	2B 1R	B ✗
R2	R3 1.05, R1 3.80, B3 3.82	2R 1B	R ✓
R3	R2 1.05, R1 2.84, B3 2.86	2R 1B	R ✓
B1	B2 1.61, B3 2.62, R1 2.91	2B 1R	B ✓
B2	B3 1.51, R1 1.59, B1 1.61	2B 1R	B ✓
B3	B2 1.51, R1 2.61, B1 2.62	2B 1R	B ✓

Correct: R2, R3, B1, B2, B3. Only R1 is misclassified.

Trap: skip the zero on the diagonal. A point is always its own nearest neighbour, and counting it would make every point vote for itself.

Problem 1.4

k-means clustering

Seven points A(2,4), B(0,0), C(0,2), D(1.5,5), E(3,5), F(1,0), G(1,1); K = 2 with μ₁ = (2, 0.5), μ₂ = (1.5, 3.5). (1) Initial clusters? (2) μ₁ after one iteration?

k-means repeats two simple moves: assign each point to its nearest centre, then move each centre to the mean of its points. Each move can only lower the total squared distance, so the loop settles down after a few rounds.

$$b(n)=\arg\min_k\ \lVert\mathbf x_n-\boldsymbol\mu_k\rVert^2$$ $$\boldsymbol\mu_k\leftarrow\frac1{|C_k|}\sum_{\mathbf x_n\in C_k}\mathbf x_n$$

Algorithm 12.1, pp. 610–611

Step assigns one point at a time (dashed lines show both squared distances), then moves the centres. Keep stepping to watch C switch clusters in round 2 before the loop converges.

Solution

1.4.1: compare $d_1^2$ and $d_2^2$ for each point:

	A	B	C	D	E	F	G
$d_1^2$	12.25	4.25	6.25	20.5	21.25	1.25	1.25
$d_2^2$	0.5	14.5	4.5	2.25	4.5	12.5	6.5

Cluster 1 = {B, F, G}, cluster 2 = {A, C, D, E}

1.4.2: $\boldsymbol\mu_1^{\text{new}}=\frac{(0,0)+(1,0)+(1,1)}{3}=$ $(\tfrac23,\tfrac13)$

Tip: to compare distances you never need the square root. Comparing $d^2$ gives the same nearest centre.

Problem 1.5

Expectation is linear

Using the definition of expectation for continuous random variables, show that 𝔼[aX + bY] = a𝔼[X] + b𝔼[Y].

An expectation is a weighted average, with the density as the weights. The trick in the proof is marginalisation: if you sum the joint density $p(x,y)$ along a slice of fixed $x$, you get the density of $X$ alone. Once each term only involves one variable, the joint density turns into a marginal and the result follows.

$$\mathbb E[g(X,Y)]=\iint g(x,y)\,p(x,y)\,dx\,dy$$ $$p_X(x)=\int p(x,y)\,dy$$

Eqs. (2.23)–(2.24), p. 25

The dots show a joint density (dot size ∝ p). X and Y are clearly dependent here. Play slices the density column by column: each column's sum becomes one bar of p_X, then each row's sum becomes one bar of p_Y.

Solution

Assume $\mathbb E|X|,\mathbb E|Y|<\infty$. All integrals run over $\mathbb R$.

1. Definition. $aX+bY$ is a function of the pair $(X,Y)$, so we average it against the joint density:

$\mathbb E[aX+bY]=\iint (ax+by)\,p(x,y)\,dx\,dy$

2. Split the integral. An integral of a sum is the sum of the integrals, and the constants $a,b$ come outside. Both parts are finite by the assumption, so the split is allowed:

$=a\iint x\,p(x,y)\,dx\,dy+b\iint y\,p(x,y)\,dx\,dy$

3. Integrate the other variable first. In the first term, $x$ doesn't depend on $y$, so for each fixed $x$ we pull it out of the $y$-integral. The second term works the same way with the roles swapped:

$=a\int x\Big[\int p(x,y)\,dy\Big]dx+b\int y\Big[\int p(x,y)\,dx\Big]dy$

4. The brackets are marginals. Summing the joint density over all $y$ leaves the density of $X$ alone, $\int p(x,y)\,dy=p_X(x)$, and likewise for $Y$ (this is the slicing in the animation):

$=a\int x\,p_X(x)\,dx+b\int y\,p_Y(y)\,dy$

5. Recognise the definitions of $\mathbb E[X]$ and $\mathbb E[Y]$:

$=$ $a\,\mathbb E[X]+b\,\mathbb E[Y]$

Nowhere did we write $p(x,y)=p_X(x)p_Y(y)$, so independence is not needed. Marginalising works for any joint density.

Trap: linearity needs no independence, but $\mathbb E[XY]=\mathbb E[X]\,\mathbb E[Y]$ does. Don't mix up the two rules.

Problem 1.6

Roulette: the expected gain per bet

American wheel. Bet one dollar on red: if red comes up you profit one dollar, otherwise you lose it. What do you earn per bet in the long run (2 significant digits)?

For a discrete variable, the expectation is the sum of outcome × probability. It is also what the running average of many independent bets settles to (the law of large numbers), so "in the long run" means $\mathbb E[G]$.

$$\mathbb E[G]=\sum_g g\,P(G=g)$$ discrete expectation, after Eq. (2.24), p. 25

Each spin is a one-dollar bet on red. The running average is noisy early on, then settles on −1/19 (the x-axis is logarithmic).

Solution

38 equally likely pockets: 18 red, 18 black, 2 green (0, 00).

$\mathbb E[G]=(+1)\cdot\frac{18}{38}+(-1)\cdot\frac{20}{38}=-\frac{2}{38}=-\frac1{19}$

Answer: ≈ −0.053 dollars per bet (a loss of about 5.3 ¢)

Tip: the two green pockets are the house edge. Without them the bet would be fair: 18/36 − 18/36 = 0.

Problem 1.7

Bayes: a positive mammogram

P(cancer) = 0.7 %, P(+ | cancer) = 90 %, P(+ | no cancer) = 8 %. Find P(cancer | +) with two significant digits.

Bayes' rule turns $P(+\mid C)$ around into $P(C\mid +)$. The easiest way to see it is to count people. Out of 10,000 women, few have cancer, but 8 % of the many healthy ones also test positive. So most positives are false alarms.

$$P(C\mid +)=\frac{P(+\mid C)\,P(C)}{P(+)}$$ $$P(+)=P(+\mid C)P(C)+P(+\mid\bar C)P(\bar C)$$

Bayes: Eq. (2.14), p. 23 · total probability: display on p. 24

10,000 women, one dot each. Play: colour the 70 with cancer, run the test, then move everyone who tested positive into one group.

Solution

$P(+)=0.90\cdot0.007+0.08\cdot0.993=0.0063+0.07944=0.08574$

$P(C\mid+)=\dfrac{0.0063}{0.08574}\approx$ 0.073 (about 7.3 %)

Check by counting: $63/(63+794)=63/857\approx0.073$.

Trap: $P(+\mid C)=0.9$ is not $P(C\mid +)$. Leaving out the small base rate $P(C)$ is the classic mistake (the "base-rate fallacy").

Problem 1.8

Convolution

$x_n=n/3$ for $0\le n\le6$, $h_n=1$ for $-2\le n\le2$, both zero elsewhere. Compute $y_n=x_n*h_n$ for every $n$.

To get output sample $y_n$: flip $h$, slide it so that it is centred at $n$, multiply it with $x$ sample by sample, and add up. Here $h$ is a box of five ones, so $y_n$ is just the sum of the five $x$-values around $n$ (a moving sum).

$$y_n=\sum_{k=-\infty}^{\infty}x_k\,h_{n-k}=\sum_{k=-\infty}^{\infty}h_k\,x_{n-k}$$ Eq. (2.126), p. 48 · course note preliminaries-dsp.pdf, slide 27

The amber window is $h_{n-k}$, the flipped and shifted kernel. Green stems are the products that overlap, and their sum becomes the new bar of $y$ below.

Solution

Terms are nonzero only when $0\le k\le6$ and $n-2\le k\le n+2$, so

$y_n=\frac13\sum_{k=\max(0,\,n-2)}^{\min(6,\,n+2)}k,\quad -2\le n\le 8$, else $0$.

e.g. $y_3=(1+2+3+4+5)/3=5$

$n$	−2	−1	0	1	2	3	4	5	6	7	8
$y_n$	0	$\frac13$	1	2	$\frac{10}3$	5	$\frac{20}3$	6	5	$\frac{11}3$	2

Answer: y = [0, 1/3, 1, 2, 10/3, 5, 20/3, 6, 5, 11/3, 2] for n = −2 … 8

Tip: the output support is the sum of the input supports, $[0,6]+[-2,2]=[-2,8]$, so 11 samples. $y_{-2}=0$ only because $x_0=0$.

Problem 1.9

Spectrum of a sinusoid

(1) Write $x(t)=A\cos(2\pi F_0t+\theta)$ with complex exponentials. (2) Give its Fourier coefficients, and sketch the magnitude and phase spectra.

A cosine is two arrows (phasors) of length $A/2$ spinning in opposite directions. Their imaginary parts cancel and their real parts add up to the cosine. Each arrow is one line in the spectrum: one at $+F_0$ and one at $-F_0$.

$$x(t)=\sum_{k}c_k\,e^{j2\pi kF_0t}$$ $$e^{j\phi}=\cos\phi+j\sin\phi$$

Euler: footnote 13, p. 565 · Fourier series: course note preliminaries-dsp.pdf, slide 14

Blue: $c_1e^{j2\pi F_0t}$, turning counter-clockwise. Red: $c_{-1}e^{-j2\pi F_0t}$, turning clockwise. Their tip-to-tail sum always lies on the real axis and traces $x(t)$ downward. The A and θ sliders change the heights and phases of the two spectral lines.

Solution

1.9.1: $\cos\phi=\tfrac12(e^{j\phi}+e^{-j\phi})$ with $\phi=2\pi F_0t+\theta$:

$x(t)=\frac A2e^{j\theta}e^{j2\pi F_0t}+\frac A2e^{-j\theta}e^{-j2\pi F_0t}$

1.9.2: compare with $\sum_kc_ke^{j2\pi kF_0t}$:

$c_1=\frac A2e^{j\theta}$, $c_{-1}=\frac A2e^{-j\theta}$, $c_k=0$ otherwise

Magnitude $A/2$ at $\pm F_0$. Phase $+\theta$ at $F_0$ and $-\theta$ at $-F_0$. So $c_{-1}=c_1^{*}$.

Tip: every real signal has $c_{-k}=c_k^{*}$. Its magnitude spectrum is even and its phase spectrum is odd, which is why the negative-frequency line is needed.

Problem 1.10

PCA with a Lagrange multiplier

With $z_{1,n}=\mathbf u_1^\top\mathbf x_n$ and zero-mean data: (1) show $\operatorname{var}[z_1]=\mathbf u_1^\top\hat\Sigma_x\mathbf u_1$; (2) maximise it subject to $\mathbf u^\top\mathbf u=1$ with a Lagrangian, and show that the answer is the eigenvector with the largest eigenvalue.

Project the data onto a unit direction $\mathbf u$ and measure how spread out the projections are. PCA picks the direction with the most spread. The constraint $\lVert\mathbf u\rVert=1$ is essential, since otherwise a longer $\mathbf u$ would always win. The Lagrange multiplier handles the constraint, and an eigenvalue problem comes out.

$$\mathbf u_1=\arg\max_{\mathbf u^\top\mathbf u=1}\mathbf u^\top\hat\Sigma_x\mathbf u$$ $$L(\mathbf u,\lambda)=\mathbf u^\top\hat\Sigma_x\mathbf u-\lambda(\mathbf u^\top\mathbf u-1)$$

Eqs. (20.2)–(20.4), p. 1106

Rotate the unit vector u. The amber ticks are the projections $z_n$, and the bar marks ±1 standard deviation. In the second plot, the variance $\mathbf u^\top\hat\Sigma\mathbf u$ peaks exactly at the top eigenvector, at height λ_max.

Solution

1.10.1: the data has zero mean, so $z_1$ does too. With $\hat\Sigma_x=\frac1N\sum_n\mathbf x_n\mathbf x_n^\top$ (Eq. (20.1), p. 1106):

$\operatorname{var}[z_1]=\frac1N\sum_n(\mathbf u_1^\top\mathbf x_n)^2=\frac1N\sum_n\mathbf u_1^\top\mathbf x_n\mathbf x_n^\top\mathbf u_1=\mathbf u_1^\top\hat\Sigma_x\mathbf u_1$

1.10.2: $L(\mathbf u,\lambda)=\mathbf u^\top\hat\Sigma_x\mathbf u-\lambda(\mathbf u^\top\mathbf u-1)$

$\hat\Sigma_x$ is symmetric, so $\nabla_{\mathbf u}(\mathbf u^\top\hat\Sigma_x\mathbf u)=2\hat\Sigma_x\mathbf u$ (footnote 8, p. 98):

$\nabla_{\mathbf u}L=2\hat\Sigma_x\mathbf u-2\lambda\mathbf u=\mathbf 0\ \Rightarrow\ $$\hat\Sigma_x\mathbf u=\lambda\mathbf u$ (an eigenvalue problem)

$\partial L/\partial\lambda=0\ \Rightarrow\ \mathbf u^\top\mathbf u=1$

At such a $\mathbf u$: $\mathbf u^\top\hat\Sigma_x\mathbf u=\lambda\,\mathbf u^\top\mathbf u=\lambda$. The variance is the eigenvalue (Eqs. (20.5)–(20.6)).

The maximum exists on the unit sphere and must be a stationary point, so take the largest:

$\mathbf u_1=$ unit eigenvector of $\lambda_{\max}$, with variance $\lambda_{\max}$

Tip: the book's $\hat\Sigma_x$ uses $1/N$. Using $1/(N-1)$ scales every eigenvalue by the same factor, so the eigenvectors (the principal directions) don't change.