90 minutes · 100 marks · 7 questions · 27 subparts.

This is an original self-study practice paper, not an official examination specification. Its question count, topic weighting, calculator practice instructions and marking suggestions do not forecast official requirements.

Answer all questions on separate paper before opening solutions. Show essential calculations, conditions and proofs. Use exact values where practicable; state rounding when using decimals. Consistently paired sign choices for eigenvectors or singular vectors are acceptable. Use the definitions, normalization factors and tie rules stated in each question; never assume an inverse exists without justification.

For this practice use a Casio fx-50FH II; one double-sided A4 reference sheet may be used. These are practice instructions, not a statement of current official exam permission. Write the mathematical setup before using scalar arithmetic. Ordinary REG output does not replace weighted, multivariable or regularized derivations; no CAS or full matrix functionality is assumed.

These are self-assessment marking suggestions, not an official rubric. Award equivalent correct reasoning. Preserve method credit when one arithmetic slip propagates. The solutions distinguish the objective, assumptions, computations and checks; a matching final number alone is insufficient.

Question paper · MATH3320

Q1. Robust loss and validation (16)

Question paper Q1

(a) [4]

Identify the optimization problem first. The four observations are fixed numbers; $a\in\mathbb R$ is the one parameter to choose, with the same $a$ shared by every prediction. Each residual $r_i=y_i-a$ is a scalar, and $F(a)=\sum_i\rho(r_i)$ adds the four prediction costs. The quadratic branch $\rho(r)=r^2/2$ differentiates to $r$. On the positive tail, $|r|-1/2$ equals $r-1/2$; on the negative tail it equals $-r-1/2$, giving derivatives 1 and −1. The appearance of an absolute value does not make this loss nondifferentiable at zero: the quadratic branch applies near zero. Convexity means the graph lies below each chord, not that it is strictly convex everywhere; its linear tails illustrate the distinction.

The argument is the residual $r=y_i-a$, not a coefficient penalty. Define $\psi=\rho^{\prime}$ and differentiate each branch:

$$\psi(r)=\begin{cases}-1,&r<-1,\\r,&-1\le r\le1,\\1,&r>1.\end{cases}$$

At r=1 both one-sided derivatives equal 1; at r=−1 both equal−1. Thus both joining points are differentiable, without choosing a side. The derivative is nondecreasing, so $\rho$ is convex. Composing a convex function with affine $y_i-a$ preserves convexity, and summing the four terms makes F convex.

Marking: Derivative branches 2; both joining points 1; convexity and transfer to F 1.

Question paper Q1(a)

(b) [6]

Why try $[0,1]$ first? Three observations are zero and only one is eight. Looking near the majority puts three residuals in the easily differentiated quadratic branch. This is a candidate interval, not an assumption that the answer must be there: check membership and global optimality afterwards. Term by term, the chain rule gives $d\rho(-a)/da=-\psi(-a)=\psi(a)$, hence $3\psi(a)$ from the zeros; the last observation contributes $-\psi(8-a)=\psi(a-8)$. At the candidate, the three small residuals each exert a slope contribution of magnitude $1/3$, balancing the outlier's saturated contribution of 1. For OLS, the contribution keeps growing linearly with residual size, so a large outlier pulls the mean much farther.

Differentiating the residual contributes a factor−1. Using the oddness of $\psi$,

$$F^{\prime}(a)=-\sum_{i=1}^4\psi(y_i-a)=3\psi(a)+\psi(a-8).$$

On $0\le a\le1$, $\psi(a)=a$ and $\psi(a-8)=-1$. Hence $F^{\prime}(a)=3a-1$ gives $a_H=1/3$, which lies in the assumed interval. Convexity makes a zero derivative globally sufficient. Uniqueness also needs explanation: for a below 0 the derivative is negative; on [0,1] it increases strictly through zero once; above 1 monotonicity and $F^{\prime}(1)=2$ make it positive.

$$G(a)=3a^2+(8-a)^2,\qquad G^{\prime}(a)=8a-16,\qquad a_{OLS}=2.$$

The two estimates optimize different objectives. Direct checks show:

$$F(1/3)=3\frac{(1/3)^2}{2}+\left(\frac{23}{3}-\frac12\right)=\frac{22}{3},\quad F(2)=10;\qquad G(2)=48,\quad G(1/3)=\frac{532}{9}>48.$$

Replacing 8 by 80 leaves $\psi(a-80)=-1$ throughout [0,1], so the same derivative and uniqueness argument give $a_H=1/3$ again. The OLS constant instead becomes 20. More generally an outlier value B keeps this Huber solution whenever $B-1/3\ge1$, i.e. $B\ge4/3$. This is bounded influence from the saturated residual derivative, not a claim that the loss ignores the outlier or minimizes RSS.

Marking: Correct derivative and applicable interval 2; solution and unique global optimality 2; OLS answer 1; unchanged value at 80 with reason 1.

Question paper Q1(b)

(c) [3]

Separate the two layers of differentiation. For $\sqrt{1+r^2}=(1+r^2)^{1/2}$, the outer derivative is $\tfrac12(1+r^2)^{-1/2}$ and the inner derivative is $2r$; multiply them to obtain the first derivative below. For the tail limits, divide numerator and denominator by $|r|$: $r/\sqrt{1+r^2}=\operatorname{sign}(r)/\sqrt{1+1/r^2}$. The two limits therefore have opposite signs, not both 1. “Bounded” describes the slope, not the loss value: the loss itself still increases with $|r|$.

$$\widetilde\rho^{\prime}(r)=\frac r{\sqrt{1+r^2}},\qquad\lim_{r\to+\infty}\widetilde\rho^{\prime}(r)=1,\qquad\lim_{r\to-\infty}\widetilde\rho^{\prime}(r)=-1.$$ $$\widetilde\rho^{\prime\prime}(r)=\frac1{(1+r^2)^{3/2}}>0.$$

By comparison, $(r^2/2)^{\prime}=r$ is unbounded. A large residual therefore has a bounded slope contribution under pseudo-Huber, rather than an arbitrarily large one under squared loss. Pseudo-Huber is smooth without the piecewise join, but its minimizer need not coincide exactly with the Huber minimizer.

Marking: Derivative 1; tail limits and squared-loss comparison 1; large-residual interpretation 1.

Question paper Q1(c)

(d) [3]

Separate fitting a transformation from applying it. If a training fold supplies mean $m_{train}$ and nonzero standard deviation $s_{train}$, a validation observation $x$ must become $(x-m_{train})/s_{train}$. Do not refit using the validation mean or use the full-data mean beforehand. The validation fold is meant to mimic unseen future data. Separately, taking the smallest CV value across losses selects the candidate that looks best on these validation observations, potentially selecting random good luck too. That is why a final independent test set is still needed.

First, whole-dataset scaling lets each validation fold affect training preprocessing even without using its labels. Second, the minimum CV score has been used for selecting a loss, so it is a selected validation result, not independent test error. Reserve an independent test set first. On the development data, run five-fold CV with preprocessing and fitting learned only inside each training fold. Apply those fixed transformations to that fold’s validation data. Select loss and hyperparameters, refit the entire pipeline on all development data, then evaluate once on the untouched test set. Renaming a selection dataset “test” changes none of these facts.

Marking: Preprocessing leakage 1; selection bias/validation versus independent test 1; corrected order 1.

Question paper Q1(d)

Q2. Greedy fitting, refitting, and nested models (18)

Question paper Q2

(a) [2]

Which objects are being correlated? The matrix $D$ is $3\times3$; each column $d_j\in\mathbb R^3$ is a direction available for the prediction. The vectors $y,r\in\mathbb R^3$ are the observations and their unexplained part; $c\in\mathbb R^3$ contains coefficients. Initially $c=0$, so $r=y$. Selection uses $|d_j^Tr|$ because either sign of a direction can improve the fit. To derive the increment, expand $\|r-\gamma d_j\|^2=\|r\|^2-2\gamma d_j^Tr+\gamma^2\|d_j\|^2$, differentiate in $\gamma$, and set to zero. This gives $\gamma=d_j^Tr/\|d_j\|^2$; only the unit column lengths remove the denominator here.

$$\|d_1\|_2^2=1,\quad\|d_2\|_2^2=(3/5)^2+(4/5)^2=1,\quad\|d_3\|_2^2=1,\qquad D^Ty=(2,2,1/5)^T.$$

The first two absolute correlations tie; select $d_1$ by the smaller-index rule. Unit norms justify the stated increment $d_j^Tr$. For general non-unit columns, the one-dimensional least-squares increment would divide by $\|d_j\|_2^2$.

Marking: Norms and correlations 1; tie handling 1.

Question paper Q2(a)

(b) [5]

Keep one accounting identity in every round: prediction plus residual equals $y$. The first prediction is $2d_1=(2,0,0)^T$; subtract it from $y=(2,1,1/5)^T$ to obtain the new residual. The second round adds $(4/5)d_2=(12/25,16/25,0)^T$ rather than replacing the prediction by that vector. Thus the final prediction is $(62/25,16/25,0)^T$. Coordinatewise subtraction gives $2-62/25=-12/25$ and $1-16/25=9/25$ for the first two residuals. RSS is the sum of the three squared residuals, not their sum and not MSE, which would divide by three.

The first increment is 2. Recompute correlations against the new residual before choosing again:

$$c^{(1)}=(2,0,0)^T,\quad r^{(1)}=(0,1,1/5)^T,\quad D^Tr^{(1)}=(0,4/5,1/5)^T.$$

Now select $d_2$ with increment $4/5$. The first coefficient remains 2; MP does not jointly refit it.

$$c_{MP}=(2,4/5,0)^T,\quad r_{MP}=r^{(1)}-\frac45d_2=\begin{pmatrix}-12/25\\9/25\\1/5\end{pmatrix},\quad\mathrm{RSS}_{MP}=\frac{144+81}{625}+\frac1{25}=\frac25.$$

Marking: First step 1; second correlations/choice 1; increment/final coefficients 1; residual 1; RSS 1.

Question paper Q2(b)

(c) [5]

What extra step does OMP perform? After selecting two columns it lets both coefficients change, so the unknown is $b=(b_1,b_2)^T\in\mathbb R^2$ and $D_A$ is $3\times2$. Differentiating the objective gives $2D_A^T(D_Ab-y)=0$, which rearranges into the $2\times2$ normal equations. Their right-hand side $D_A^Ty=(2,2)^T$ is not the previous residual's correlations: correlations select a column, whereas the original $y$ is the refitting target. Subtracting the two equations gives $(2/5)(b_1-b_2)=0$; substitute back to obtain their common value. Reducing the old coefficient from 2 to 5/4 is not a backward step: the new column also explains the first coordinate.

The first OMP step matches MP, and the second choice is again $d_2$. The active matrix and normal equations are:

$$D_A=\begin{pmatrix}1&3/5\\0&4/5\\0&0\end{pmatrix},\qquad\begin{pmatrix}1&3/5\\3/5&1\end{pmatrix}\begin{pmatrix}b_1\\b_2\end{pmatrix}=\begin{pmatrix}2\\2\end{pmatrix}.$$

The target is still the original y in $\min_b\|D_Ab-y\|_2^2$; we do not freeze the old coefficient. The determinant $1-9/25=16/25>0$ gives uniqueness. Subtracting equations gives $b_1=b_2$, then $(8/5)b_1=2$, so both equal 5/4.

$$c_{OMP}=(5/4,5/4,0)^T,\quad r_{OMP}=(0,0,1/5)^T,\quad\mathrm{RSS}_{OMP}=1/25.$$

Check the first two predicted entries: $5/4+(3/5)(5/4)=2$ and $(4/5)(5/4)=1$. They reproduce the corresponding observations.

Marking: Active set and correct normal equations 2; both coefficients 1; residual 1; RSS 1.

Question paper Q2(c)

(d) [3]

Orthogonal means inner product zero, not merely “different directions.” After a one-dimensional least-squares update, $d_j^T(r-\gamma d_j)=d_j^Tr-\gamma\|d_j\|^2=0$; this concerns the currently selected column only. Moving along another nonorthogonal direction changes the old inner product to $0-\gamma_2d_1^Td_2$, here $-(4/5)(3/5)=-12/25$. OMP's normal equations instead make all active-direction inner products zero together. This compares fits on the same active columns; it does not establish superiority on all future samples or all sparse supports.

$$d_1^Tr_{MP}=-12/25,\qquad d_2^Tr_{MP}=\frac35\!\left(-\frac{12}{25}\right)+\frac45\frac9{25}=0,\qquad D_A^Tr_{OMP}=0.$$

MP leaves the residual orthogonal to the most recently updated column but not to the earlier one. Since $d_1^Td_2=3/5\ne0$, updating along the second column changes the first coordinate and destroys the previous orthogonality. OMP reoptimizes every active coefficient, so the residual is orthogonal to both active columns and its RSS here is smaller. This example does not prove that OMP always finds a globally optimal sparse support.

Marking: MP inner products 1; OMP orthogonality 1; nonorthogonal columns and joint refit explanation 1.

Question paper Q2(d)

(e) [3]

The proof is not “larger models are usually better”; the old answer remains allowed. The sets $V_1,V_2$ contain allowable prediction vectors. After expansion one can still choose the old prediction, so the new minimum cannot be larger. If added directions are orthogonal to the old residual, the old prediction may remain optimal, allowing equality. In the counterexample below the second model predicts only $(t,t,t)^T$. Differentiating $(1-t)^2+2t^2$ gives $6t-2=0$, hence $t=1/3$. Its MAE is $((2/3)+(1/3)+(1/3))/3=4/9$, explicitly showing why the RSS conclusion cannot be transferred to another metric.

Let $\widehat y_1\in V_1$ be an optimal first-model prediction. Since $V_1\subseteq V_2$, it is feasible in the second optimization:

$$\mathrm{RSS}_2=\min_{v\in V_2}\|y-v\|_2^2\le\|y-\widehat y_1\|_2^2=\mathrm{RSS}_1.$$

This is non-increase, not strict decrease, and says nothing about test error. MAE is not the optimized objective, so it has no such guarantee. For an explicit counterexample take $y=(1,0,0)^T$, $V_1=\{0\}$, and $V_2=\operatorname{span}\{(1,1,1)^T\}$. Least-squares predictions are 0 and $(1/3,1/3,1/3)^T$, respectively:

$$\mathrm{RSS}_1=1,\quad\mathrm{RSS}_2=2/3,\quad\mathrm{MAE}_1=1/3,\quad\mathrm{MAE}_2=4/9.$$

Thus RSS falls while MAE rises. The numerical counterexample supports understanding; it is not an additional requirement beyond a correct explanation.

Marking: Feasible-set proof 2; correct explanation of no MAE guarantee 1.

Question paper Q2(e)

Q3. Kernel PCA and its normalization (17)

Question paper Q3

(a) [5]

Separate the three spaces first. Each input $t_i$ is scalar, but $\phi(t)=(t,t^2)^T$ maps it into a two-dimensional vector. Stacking three samples in rows makes $\Phi,\Phi_c$ both $3\times2$. The mean $\overline\phi$ is $2\times1$, and $\Phi_c=\Phi-\mathbf1\overline\phi^T$, with $\mathbf1$ of size $3\times1$. For example, the first row is $(-1,1)-(0,2/3)=(-1,1/3)$. The $3\times3$ matrix $K$ compares samples, not features: $K_{ij}=\phi(t_i)^T\phi(t_j)$, so $K_{13}=(-1)(1)+(1)(1)=0$.

Why center on both sides? Left multiplication by $C=I_3-\mathbf1\mathbf1^T/3$ subtracts the feature mean from each sample in $\Phi$. Thus $(C\Phi)(C\Phi)^T=C\Phi\Phi^TC=CKC$. Entrywise, $(K_c)_{ij}=K_{ij}-\overline K_{i\cdot}-\overline K_{\cdot j}+\overline K_{\cdot\cdot}$; adding the grand mean corrects the double subtraction. Here row means are $(2/3,0,2/3)$ and the grand mean is $4/9$, so $(K_c)_{11}=2-2/3-2/3+4/9=10/9$ and $(K_c)_{12}=0-2/3-0+4/9=-2/9$.

Construct the feature matrix before centering. The original scalar inputs have mean 0, but the nonlinear squared feature has mean 2/3:

$$\Phi=\begin{pmatrix}-1&1\\0&0\\1&1\end{pmatrix},\quad\overline\phi=\begin{pmatrix}0\\2/3\end{pmatrix},\quad\Phi_c=\begin{pmatrix}-1&1/3\\0&-2/3\\1&1/3\end{pmatrix}.$$

Subtract the same mean row from every observation. Since $C=C^T=C^2$, double-centering the Gram matrix equals taking the Gram matrix of centered features:

$$K=\Phi\Phi^T=\begin{pmatrix}2&0&0\\0&0&0\\0&0&2\end{pmatrix},\quad K_c=CKC=\Phi_c\Phi_c^T=\frac19\begin{pmatrix}10&-2&-8\\-2&4&-2\\-8&-2&10\end{pmatrix}.$$

The three row sums are $(10-2-8)/9$, $(-2+4-2)/9$, and $(-8-2+10)/9$, all zero. Thus $K_c\mathbf1=0$. A nonzero row sum often reveals that only row means were removed, rather than completing double centering.

Marking: Feature mean and centered matrix 2; K 1; centered K 1; zero-row-sum check 1.

Question paper Q3(a)

(b) [4]

The candidate vectors have a reason. Centering already gives $K_c\mathbf1=0$, so the constant vector is a zero-eigenvalue direction. Samples one and three are symmetric around zero, suggesting the antisymmetric vector $(-1,0,1)^T$. Multiplication gives $(-18,0,18)^T/9=2(-1,0,1)^T$. Next choose a vector perpendicular both to the constant vector and to this antisymmetric one: its endpoints must agree and its entries sum to zero, so take $(1,-2,1)^T$. Its product is $(6,-12,6)^T/9=(2/3)(1,-2,1)^T$. Divide by the respective lengths $\sqrt2,\sqrt6,\sqrt3$ to obtain unit vectors. Normalizing changes vector length, not the eigenvalue.

Use three mutually orthogonal unit vectors and verify each matrix-vector product:

$$q_1=\frac1{\sqrt2}(-1,0,1)^T,\quad q_2=\frac1{\sqrt6}(1,-2,1)^T,\quad q_3=\frac1{\sqrt3}(1,1,1)^T;$$ $$K_cq_1=2q_1,\qquad K_cq_2=\frac23q_2,\qquad K_cq_3=0.$$

They form an orthonormal basis of $\mathbb R^3$, so no eigenvalue is missing: the spectrum is $2,2/3,0$. The leading eigenvalue is distinct, leaving only a sign ambiguity. Choose $q=q_1$ and $\lambda=2$ because the third coordinate is positive. Check the trace: $\operatorname{tr}(K_c)=24/9=8/3=2+2/3+0$.

Marking: Three eigenvalues 2; unit leading eigenvector 1; verification and sign 1.

Question paper Q3(b)

(c) [4]

Check dimensions before normalization. The three entries of $q\in\mathbb R^3$ weight samples; they are not an axis in the two-dimensional feature space. Since $\Phi_c^T$ is $2\times3$, the vector $\Phi_c^Tq\in\mathbb R^2$ has the right dimension for a feature direction. Its first coordinate is $(-1)(-1/\sqrt2)+0+(1)(1/\sqrt2)=\sqrt2$, and its second is $(1/3)(-1/\sqrt2)+0+(1/3)(1/\sqrt2)=0$. Correct dimension does not mean unit length, so use $w=\Phi_c^Tq/\sqrt\lambda$.

The score $z_i$ is the inner product of centered feature row $i$ with $w$: one scalar per sample, stacked into $z\in\mathbb R^3$. Here $w=(1,0)^T$ keeps only the first feature, giving $(-1,0,1)^T$. In a general kernel method the features may not be explicitly available, but $z=K_cq/\sqrt\lambda$ still computes the same training scores. The length proof below also explains the requirement $\lambda>0$.

q is a unit vector in observation-index space; w is a direction in feature space. Their dimensions differ. For a positive eigenvalue,

$$\|w\|_2^2=\frac{q^T\Phi_c\Phi_c^Tq}{\lambda}=\frac{q^TK_cq}{\lambda}=q^Tq=1.$$ $$\Phi_c^Tq=(\sqrt2,0)^T,\qquad w=(1,0)^T,\qquad z=\Phi_cw=(-1,0,1)^T=\frac{K_cq}{\sqrt\lambda}=\sqrt\lambda\,q.$$

Without division by $\sqrt\lambda$, the direction has length $\sqrt2$, scores gain a factor $\sqrt2$, and their variance doubles. This violates the unit-direction constraint, not just a notation convention. Zero eigenvalues cannot appear in this denominator.

Marking: Unit-length proof 2; w and scores 1; consequence of missing normalization 1.

Question paper Q3(c)

(d) [4]

Keep three quantities distinct. The kernel eigenvalue 2 is the sum of squared scores; sample variance divides it by $n-1=2$; explained proportion divides retained variance by total variance. Directly, the score mean is zero, giving variance $[(-1)^2+0^2+1^2]/2=1$. The feature covariance cross-entry is $[(-1)(1/3)+0(-2/3)+(1)(1/3)]/2=0$, and its second diagonal entry is $[(1/3)^2+(-2/3)^2+(1/3)^2]/2=1/3$.

Why add the mean back? The vector $z_iw$ reconstructs a displacement from the mean, not the original feature. The full reconstruction is $\widehat\phi_i=\overline\phi+z_iw$. Here it retains the first coordinate exactly and replaces every second coordinate by 2/3, losing only the second feature's deviations. Reconstruction takes place in feature space and need not equal $\phi(t)$ for any real input: $(0,2/3)$ is not of the form $(t,t^2)$. The question does not request this inverse mapping.

The specified sample-covariance divisor is n−1=2, not 3:

$$S_\phi=\frac12\Phi_c^T\Phi_c=\begin{pmatrix}1&0\\0&1/3\end{pmatrix},\quad\operatorname{Var}(z)=1=\frac{\lambda_1(K_c)}{n-1},\quad\eta=\frac1{1+1/3}=\frac34.$$

Reconstruct centered features with the score times the direction, then add the mean back:

$$\widehat\Phi_c=zw^T=\begin{pmatrix}-1&0\\0&0\\1&0\end{pmatrix},\qquad\widehat\Phi=\begin{pmatrix}-1&2/3\\0&2/3\\1&2/3\end{pmatrix}.$$ $$\|\Phi-\widehat\Phi\|_F^2=(1/3)^2+(-2/3)^2+(1/3)^2=\frac23.$$

Check the error against the discarded kernel eigenvalue $\lambda_2(K_c)=2/3$, or $(n-1)\lambda_2(S_\phi)=2(1/3)$. Covariance normalization changes eigenvalue magnitudes but not the explained-variance ratio; total squared error is 2/3, not 1/3.

Marking: Sample variance 1; ratio 1; reconstruction and error 2.

Question paper Q3(d)

Q4. Learned distances and random projections (16)

Question paper Q4

(a) [4]

Factorization turns a quadratic form into a squared length. The matrix $M$ is $2\times2$, $h=(h_1,h_2)^T\in\mathbb R^2$, and we may choose a $1\times2$ matrix $L$ mapping a planar vector to one scalar. The four entries of $L^TL$ are $1,2,2,4$, recovering $M$. Positive semidefiniteness requires a nonnegative quadratic form for every $h$; positive definiteness requires strict positivity for every nonzero $h$. This strictness determines whether distinct points are separated by the distance. Since $Lh=h_1+2h_2$, the nonzero vector $h=(-2,1)^T$ maps to zero, so the rank is one rather than two.

$$L=\begin{pmatrix}1&2\end{pmatrix},\quad L^TL=M,\quad h^TMh=\|Lh\|_2^2=(h_1+2h_2)^2\ge0.$$

This proves positive semidefiniteness for every h, not by checking individual entries. The second row is twice the first and the first is nonzero, so rank(M)=1. Solving $h_1+2h_2=0$ gives the null space below. Its nonzero vectors show that M is not positive definite.

$$\ker M=\operatorname{span}\{(-2,1)^T\}.$$

Marking: L1; semidefinite proof 1; rank 1; null space 1.

Question paper Q4(a)

(b) [3]

Transform the coordinates before measuring distance. By definition, $d_M(x,y)=\sqrt{(x-y)^TM(x-y)}=|Lx-Ly|$. The distinct planar points $u=(2,0)^T$ and $v=(0,1)^T$ both map to 2 on the line, giving distance zero: the rank-deficient map collapses a direction. Adding $\tau I$ requires $\tau>0$ and adds $\tau$ times Euclidean squared length in every original direction. The final $5\tau$ is a squared distance; the distance itself is $\sqrt{5\tau}$.

$$Lo=0,\quad Lu=2,\quad Lv=2,\qquad d_M(o,u)=2,\quad d_M(o,v)=2,\quad d_M(u,v)=0.$$

Distinct u and v have zero distance, so this is a pseudometric, not a metric on the entire plane. The failing property is separation, not symmetry or nonnegativity. Adding $\tau I$ restores strict positivity in every nonzero direction:

$$h^TM_\tau h=(h_1+2h_2)^2+\tau\|h\|_2^2>0\quad(h\ne0).$$

Since $u-v=(2,-1)^T$ lies in the original null space,

$$d_{M_\tau}(u,v)^2=(u-v)^TM(u-v)+\tau\|u-v\|_2^2=5\tau.$$

Previously collapsed directions regain positive length; the positive-definite quadratic form defines a genuine metric.

Marking: Three distances 1; pseudometric with reason 1;5τ and positive-definite reason 1.

Question paper Q4(b)

(c) [3]

The matrix is random; this vector is fixed. Fix $a\in\mathbb R^d$, draw $R\in\mathbb R^{k\times d}$, and obtain $Ra\in\mathbb R^k$. Expectation refers to repeated matrix draws. Expanding one squared coordinate gives

$$\mathbb E b_\ell^2=\sum_j a_j^2\mathbb E R_{\ell j}^2+2\sum_{j<m}a_ja_m\mathbb E(R_{\ell j}R_{\ell m}).$$

Independence and zero means give $\mathbb E(R_{\ell j}R_{\ell m})=\mathbb ER_{\ell j}\mathbb ER_{\ell m}=0$, whereas $\mathbb E R_{\ell j}^2=\operatorname{Var}(R_{\ell j})=1/k$. Thus each output coordinate receives, on average, $1/k$ of the original squared length; summing $k$ coordinates restores the original squared length. This proves an expectation of the squared norm only. One cannot move a square root through expectation and conclude $\mathbb E\|Ra\|=\|a\|$.

Write the ℓth projected coordinate as $b_\ell=(Ra)_\ell=\sum_{j=1}^dR_{\ell j}a_j$. Zero means give $\mathbb E b_\ell=0$; independence eliminates cross terms. With entry variance 1/k,

$$\mathbb E b_\ell^2=\operatorname{Var}(b_\ell)=\sum_{j=1}^d a_j^2\frac1k=\frac{\|a\|_2^2}{k},\qquad\mathbb E\|Ra\|_2^2=\sum_{\ell=1}^k\mathbb E b_\ell^2=\|a\|_2^2.$$

Entry variance 1 would instead give $k\|a\|_2^2$. An expectation identity alone does not bound the error of every draw; part(d) adds a concentration assumption.

Marking: Coordinate mean/variance 1; independence removing cross terms 1; sum over rows 1.

Question paper Q4(c)

(d) [6]

Moving from one pair to all pairs costs a pair count. For a fixed pair set $a=x_i-x_j$. The supplied single-direction bound controls $E_{ij}=\{|\|Ra\|^2-\|a\|^2|>\varepsilon\|a\|^2\}$. Failure of any pair defeats the simultaneous requirement, so the bad event is a union, not an intersection. All pairs use the same $R$; their success probabilities cannot simply be multiplied as though independent.

For $n\ge2$ and $0<\delta<1$, the intermediate logarithmic inequality is $\log(n(n-1))-ck\varepsilon^2\le\log\delta$, hence $ck\varepsilon^2\ge\log(n(n-1))-\log\delta$. Check the sign when rearranging, then divide by the positive number $c\varepsilon^2$. Dimension is integer, so round upward to meet the threshold. The guarantee concerns squared distances. For ordinary distances the factors become $\sqrt{1-\varepsilon}$ and $\sqrt{1+\varepsilon}$; do not copy squared-distance factors without explanation.

There are at most $n(n-1)/2$ index pairs. A duplicate-point difference is zero and never fails, so keeping all pairs is still a valid upper bound. Let each bad event mean relative squared-distance error above ε. The union bound needs no independence between these events:

$$\Pr(\bigcup_{i<j}E_{ij})\le\frac{n(n-1)}2\,2e^{-ck\varepsilon^2}=n(n-1)e^{-ck\varepsilon^2}.$$

Require this to be at most δ, take natural logarithms, and rearrange. Since k is an integer, a sufficient condition is:

$$k\ge\left\lceil\frac{\log\!\bigl(n(n-1)/\delta\bigr)}{c\varepsilon^2}\right\rceil.$$

Then, with probability at least $1-\delta$, the same random matrix simultaneously gives

$$(1-\varepsilon)\|x_i-x_j\|_2^2\le\|Rx_i-Rx_j\|_2^2\le(1+\varepsilon)\|x_i-x_j\|_2^2\quad\forall\,i,j.$$

This is a sufficient bound, not the necessary minimum dimension. Even if it exceeds d, that alone does not prove all dimensionality reduction impossible. Two quantifiers matter: probability at least $1-\delta$ still permits failed draws, and the point set must be fixed before drawing R. If $k<d$, every linear map has a nonzero $a\in\ker R$, giving $\|Ra\|^2=0<(1-\varepsilon)\|a\|^2$ for $0<\varepsilon<1$. Therefore one such map cannot preserve all distances of the entire ambient space.

Marking: Pair count and union bound 2; sufficient dimension 2; possible failed draws 1; whole-space null-space contradiction 1.

Question paper Q4(d)

Q5. One complete Gaussian EM iteration (14)

Question paper Q5

(a) [4]

What does the E-step ask? Each $x_i$ is a one-dimensional observation. Each of the two components has a weight $\pi_k$, mean $\mu_k$, and variance $\sigma_k^2$; the unobserved quantity is the component that generated each observation. The responsibility $r_{ik}$ is the conditional probability of component $k$ after observing $x_i$, not the Gaussian density itself. Bayes' formula gives

$$r_{ik}=\frac{\pi_k^{old}\varphi(x_i;\mu_k^{old},(\sigma_k^2)^{old})}{\sum_{h=1}^{2}\pi_h^{old}\varphi(x_i;\mu_h^{old},(\sigma_h^2)^{old})}.$$

Rows of $r$ index observations and columns index components. A row shares one denominator: that observation's total mixture density. Every parameter here is old; do not update a mean after computing just one row. The old means are −2 and 2, so distances are zero to the matching mean and four to the other mean. Equal old variances let the common factor $A$ cancel, but the unequal priors $1/3,2/3$ cannot cancel. In row two the denominator is $A/6+2A/3=5A/6$, giving first responsibility $(A/6)/(5A/6)=1/5$.

Let the old common variance be $s^2=8/\log2$ and the density prefactor be $A=(2\pi s^2)^{-1/2}$. Being 4 away from a component mean multiplies its density by

$$\exp\!\left(-\frac{4^2}{2s^2}\right)=e^{-\log2}=\frac12.$$

The density rows are therefore $(A,A/2)$ and $(A/2,A)$. Multiply by the unequal old priors before normalizing. At x=−2 the unnormalized values are $(A/3,A/3)$; at x=2 they are $(A/6,2A/3)$. Thus

$$(r_{ik})=\begin{pmatrix}1/2&1/2\\1/5&4/5\end{pmatrix}.$$

Each row sums to 1. The first observation lies exactly at the first mean but has responsibility only 1/2: the second component’s larger prior cancels its smaller density. Nearest-mean hard assignment would miss this distinction.

Marking: Exponential density ratio 1; using priors 1; each responsibility row 1.

Question paper Q5(a)

(b) [6]

Why does the M-step use two different denominators? The E-step distributes one observation's unit probability across a row; the M-step collects each component's share down a column. Thus $N_k=\sum_i r_{ik}$ is an effective component sample size. The weight $\pi_k^{new}=N_k/n$ divides by the total count $n=2$, whereas the mean and variance divide by that component's own $N_k$. Normalizing the first column gives observation weights $5/7,2/7$; the second gives $5/13,8/13$. This also explains why both new means remain within $[-2,2]$.

Compute the second variance directly too. Around the new mean $6/13$, the deviations are $-2-6/13=-32/13$ and $2-6/13=20/13$. The weighted squared sum is $(1/2)(1024/169)+(4/5)(400/169)=832/169$; divide by $13/10$ to obtain $640/169$. Do not divide by two or retain the old center 2.

The second-moment shortcut follows by expanding $\sum_i r_{ik}(x_i-\mu)^2=\sum_i r_{ik}x_i^2-2\mu\sum_i r_{ik}x_i+\mu^2N_k$. At the new mean, $\sum_i r_{ik}x_i=N_k\mu$, so division by $N_k$ leaves the weighted second moment minus $\mu^2$. Equal old variances are an initialization, not a constraint that the two updated variances must remain equal.

Keep all responsibilities fixed during this M-step. Column sums give effective sample counts, which need not be integers but sum to 2:

$$N_1=\frac12+\frac15=\frac7{10},\quad N_2=\frac12+\frac45=\frac{13}{10},\quad\pi_1^{new}=\frac7{20},\quad\pi_2^{new}=\frac{13}{20}.$$

Divide each responsibility-weighted sum of observations by its own effective count:

$$\mu_1^{new}=\frac{(-2)(1/2)+2(1/5)}{7/10}=-\frac67,\qquad\mu_2^{new}=\frac{(-2)(1/2)+2(4/5)}{13/10}=\frac6{13}.$$

Both observations have squared value 4, so each normalized weighted second moment is 4. Subtract the new mean squared to obtain the variance:

$$(\sigma_1^2)^{new}=4-(-6/7)^2=\frac{160}{49},\qquad(\sigma_2^2)^{new}=4-(6/13)^2=\frac{640}{169}.$$

This is a shortcut for, not a change to, the variance definition:

$$(\sigma_k^2)^{new}=\frac{\sum_i r_{ik}(x_i-\mu_k^{new})^2}{N_k}.$$

For component 1 the deviations are $-8/7,20/7$. Their weighted squared sum is $(1/2)(64/49)+(1/5)(400/49)=112/49$; division by 7/10 gives 160/49. Three consistency checks recover total probability, the observed mean, and the observed second moment:

$$\sum_k\pi_k^{new}=1,\quad\sum_k\pi_k^{new}\mu_k^{new}=0,\quad\sum_k\pi_k^{new}\bigl((\sigma_k^2)^{new}+(\mu_k^{new})^2\bigr)=4.$$

Marking: Effective counts and weights 2; two means 2; two variances 2. Preserve method credit after an isolated arithmetic error.

Question paper Q5(b)

(c) [2]

Turn “maximize likelihood” into a derivative test. Write $S_k=\sum_i r_{ik}(x_i-\mu_k^{new})^2$. Then $Q'(v)=(S_k-N_kv)/(2v^2)$. Here $S_k>0,N_k>0$ and the denominator is positive: the derivative is positive for $v<S_k/N_k$ and negative above it, so the stationary point is indeed a maximum. If $N_k=0$, these updates cannot simply divide by it. If $S_k=0$, a zero-variance boundary degeneracy may arise, so the positive-variance conclusion needs conditions. Neither problem occurs here because both columns have positive responsibilities and the two observations differ.

The M-step maximizes a weighted log likelihood with responsibilities fixed. For a positive variance parameter v, its relevant terms are:

$$Q(v)=-\frac{N_k}{2}\log v-\frac1{2v}\sum_i r_{ik}(x_i-\mu_k^{new})^2+\mathrm{const},$$ $$Q^{\prime}(v)=-\frac{N_k}{2v}+\frac{\sum_i r_{ik}(x_i-\mu_k^{new})^2}{2v^2}=0.$$

Thus the denominator is $N_k$, not an unbiased-sample correction $N_k-1$. Here $N_1=0.7$, so mechanically dividing by $N_1-1$ could even yield a negative variance. The mean is also optimized in this M-step, so deviations are around the new mean, not the old−2 or 2.

Marking: Maximum-likelihood denominator 1; new mean and reason 1.

Question paper Q5(c)

(d) [2]

Sum over components before taking each observation's logarithm. An observation can come from either component, so its density is the weighted sum of component densities. Independence makes the joint density of two observations a product of two mixture densities; taking its logarithm produces the sum below. Do not interchange the logarithm and the component sum. The E-step uses the old posterior to make an auxiliary lower bound touch the observed log-likelihood at the old parameters. The M-step raises this fixed-responsibility bound, so the new observed log-likelihood cannot be lower. This is soft EM's improvement mechanism, not a guarantee of finding the best clustering in one update. Recompute responsibilities using all new parameters only in the next round.

$$\ell(\theta)=\sum_{i=1}^2\log\!\left[\pi_1\varphi(x_i;\mu_1,\sigma_1^2)+\pi_2\varphi(x_i;\mu_2,\sigma_2^2)\right],\qquad\ell(\theta^{new})\ge\ell(\theta^{old}).$$

The inequality holds when the E- and M-steps are executed correctly and the updates are defined. It concerns the observed mixture log likelihood, not a maximum component density. It guarantees neither a unique global optimum nor correct labels nor identical outcomes from different initializations. Swapping component labels preserves the mixture density; unconstrained Gaussian mixtures can also have singular behavior as variances approach zero. Update all specified parameters rather than only one component.

Marking: Correct objective and monotonicity 1; at least one valid limitation 1.

Question paper Q5(d)

Q6. Mean-shift and a density hierarchy (13)

Question paper Q6

(a) [4]

There are two kinds of positions: a moving query and fixed observations. Only $p_t$ moves; the reference set $\{0,1,2,4,8\}$ stays unchanged. The flat kernel tests $|x_i-p_t|\le2$, without assigning larger weights to nearer points. From 4 the five distances are 4,3,2,0,4, so select only 2 and 4 and average to $(2+4)/2=3$. From 3 select 1,2,4 and average to $(1+2+4)/3=7/3$. A smaller movement alone does not prove convergence: check the next neighborhood and average again.

The flat kernel gives equal weights to original observations within the closed radius 2. Therefore each update is their arithmetic mean:

$$p_0=4:\ \{2,4\}\longrightarrow p_1=3;\qquad p_1=3:\ \{1,2,4\}\longrightarrow p_2=7/3;$$ $$p_2=7/3:\ \{1,2,4\}\longrightarrow p_3=7/3=p_2.$$

At position 3, observation 1 is exactly at the radius 2 boundary and must be included. At 7/3 the distances to 0,1,2,4,8 are $7/3,4/3,1/3,5/3,17/3$, confirming the same selected neighborhood and the fixed point $p^*=7/3$. Do not replace the reference observation 4 by the moved position 3: the reference sample stays fixed.

Marking: Three neighborhoods and updates 3; explicit fixed-point check 1.

Question paper Q6(a)

(b) [4]

This subpart uses a new four-point dataset, not part (a)'s five points. Here $x_1=0,x_2=1,x_3=4,x_4=5$; subscripts are indices, not data values. A core distance is the smallest radius around the point covering three observations, including itself. From $x_2=1$, distances are 0 to itself, 1 to 0, 3 to 4, and 4 to 5; the third entry is therefore 3. Each edge then takes $\max\{\operatorname{core}_3(x_i),\operatorname{core}_3(x_j),|x_i-x_j|\}$. For example, edge (1,4) gives $\max\{4,4,5\}=5$, and edge (2,3) gives $\max\{3,3,3\}=3$.

Include self-distance zero before selecting the third distance:

$$\begin{array}{c|c|c}x_i&\mathrm{sort}_j|x_i-x_j|&\operatorname{core}_3(x_i)\\\hline0&0,1,4,5&4\\1&0,1,3,4&3\\4&0,1,3,4&3\\5&0,1,4,5&4\end{array}$$ $$\begin{array}{c|rrrrrr}(i,j)&(1,2)&(1,3)&(1,4)&(2,3)&(2,4)&(3,4)\\\hline |x_i-x_j|&1&4&5&3&4&1\\d_{mr}(x_i,x_j)&4&4&5&3&4&4\end{array}$$

For example, the ordinary distance for(1,2) is 1, but mutual reachability is $\max\{4,3,1\}=4$. This encodes the density requirements at both endpoints. It is the maximum of three quantities, not their sum; do not exclude self and then retain the same neighbor index.

Marking: Four core distances 2; six edge weights 2.

Question paper Q6(b)

(c) [3]

A spanning tree must be connected and cycle-free. A tree on four vertices has exactly three edges, but simply taking the three smallest edges may form a cycle among three vertices and leave the fourth disconnected. Kruskal checks whether each candidate edge's endpoints are already in the same connected component; if so, skip it. After (2,3), the components are $\{1\},\{2,3\},\{4\}$. After (1,2), they are $\{1,2,3\},\{4\}$. Edge (1,3) now stays inside one component, whereas (2,4) joins two components and is accepted.

Sort by weight, then by the specified lexicographic tie rule:

$$(2,3):3;\quad(1,2):4,\ (1,3):4,\ (2,4):4,\ (3,4):4;\quad(1,4):5.$$

Select(2,3), then(1,2). Skip(1,3), which closes a cycle with the first two edges. Select(2,4); all four vertices are now connected:

$$T=\{(2,3),(1,2),(2,4)\},\qquad w(T)=3+4+4=11.$$

In original values these edges join(1,4),(0,1),(1,5). Without a tie rule, other equal-weight MSTs could be valid, but this question supplies a rule and must follow it.

Marking: Ordering and cycle skip 1; selected edges 1; total weight 1.

Question paper Q6(c)

(d) [2]

Thresholding removes graph edges; it is not grouping adjacent values by ordinary gaps. Retention depends on mutual-reachability weight being at most 3. Although 0 and 1 are only one unit apart, their edge weight is 4 and the edge is removed. Isolated vertices are also connected components, so include both singletons. A connected component is a graph object at this threshold; a final cluster or noise label depends on later algorithmic rules. These names are not interchangeable.

Only edge(2,3) survives the weight-at-most 3 cut. The components are:

$$\{x_1\},\ \{x_2,x_3\},\ \{x_4\}=\{0\},\ \{1,4\},\ \{5\}.$$

This is one threshold slice of a density hierarchy. HDBSCAN still needs hierarchy condensation based on parameters such as minimum cluster size and a final stability-based selection. Those choices are not given. The singletons cannot be declared final clusters or noise solely from this slice.

Marking: Components 1; incomplete condensation/stability/final selection 1.

Question paper Q6(d)

Q7. Soft regions and median centers (6)

Question paper Q7

(a) [3]

A boundary is where two sites are equally close. Between 0 and 10, $|t|=|t-10|$ gives $t=5$. After inserting 3, its boundary with 0 is $(0+3)/2=3/2$, and with 10 is $(3+10)/2=13/2$. Retain the old regions from before insertion when taking overlaps with the new interval; using the updated old regions would leave disjoint interiors. By definition, $w_j=\operatorname{length}(R_x\cap R_j)/\operatorname{length}(R_x)$, giving $(7/2)/5=7/10$ and $(3/2)/5=3/10$. Both denominators are the same new-interval length.

The old sites 0 and 10 have midpoint 5. The new site 3 has boundaries at its midpoints with 0 and 10:

$$R_1=(-\infty,5],\quad R_2=[5,\infty),\quad R_x=[3/2,13/2],\quad\operatorname{length}(R_x)=5.$$ $$\operatorname{length}(R_x\cap R_1)=5-3/2=7/2,\qquad\operatorname{length}(R_x\cap R_2)=13/2-5=3/2,\quad(w_1,w_2)=(7/10,3/10).$$

The weights are nonnegative and sum to 1. Shared endpoints have length zero and do not affect the answer. Although old regions are unbounded, the new interval and its overlaps are finite; no infinite-length ratio is involved. These are overlap weights, not ratios of distances to sites.

Marking: Old boundary and new interval 1; two overlaps 1; normalized weights 1.

Question paper Q7(a)

(b) [3]

Identify the distance and the allowed centers first. The objective is a sum of absolute distances, not squared distances. A continuous center may be any real $c$, whereas a medoid must be one of $0,2,9,11$. First find all continuous minimizers, then intersect with the allowed observations. For $2\le c\le9$, $|2-c|=c-2$ and $|9-c|=9-c$, so left and right changes cancel as $c$ moves. Equality in the two paired lower bounds requires $c\in[0,11]$ and $c\in[2,9]$ respectively; their intersection gives the full answer. Squared distances would change both objective and derivative. The mean 5.5 happens to lie in this median interval, but that coincidence does not make the two rules generally identical.

$$H(c)=|c|+|2-c|+|9-c|+|11-c|.$$

For every c in[2,9], expand the signs to get the same value:

$$H(c)=c+(c-2)+(9-c)+(11-c)=18.$$

To prove global optimality and find all optimizers, pair endpoints and apply the triangle inequality:

$$|c|+|11-c|\ge11,\qquad|2-c|+|9-c|\ge7.$$

Their sum is at least 18. Both equalities hold exactly when c belongs to[2,9]. Thus all unrestricted one-median centers form[2,9]; restricting to observed points gives exactly the two one-medoids 2 and 9. For an even sample, the midpoint of the middle observations is one minimizer, not the only one.

$$\sum_i\|x_i-c\|_1=\sum_j\sum_i|x_{ij}-c_j|.$$

The L1 objective separates by coordinate, so coordinatewise medians minimize it. Euclidean lengths couple coordinates through square roots; their total is minimized by a geometric median, not generally coordinatewise medians. For points(0,0),(2,0),(0,2), the coordinatewise median is(0,0) with total Euclidean distance 4. At(1/2,1/2), the total is $1/\sqrt2+\sqrt{10}\approx3.869<4$, disproving that rule for Euclidean distance. The lower-bound proof and this counterexample clarify the result; they are not extra required proof tasks.

Marking: All continuous centers 1; all medoids 1; distinguish L1 from Euclidean 1.

Question paper Q7(b)

After correction: Q1—check chain rules and loss versus penalty; Q2—tabulate residual, selection, coefficients and prediction, retaining the original y for OMP; Q3—check zero row sums and distinguish kernel eigenvalues from feature-space variance; Q4—state the fixed point set, random draw, all-pairs event and failure probability; Q5—separate row responsibility normalization from column effective counts; Q6—check fixed reference points, closed boundaries and self-inclusion; Q7—state the distance and allowed center set before invoking a median rule.