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.

Detailed solutions and marking · MATH3320

Q1. Robust loss and validation (16)

Detailed solutions and marking Q1

For residual r define the following two losses. They act on residuals, not coefficients. Four observations are $y_1=y_2=y_3=0$, $y_4=8$. Fit the constant model $\widehat y_i=a$.

$$\rho(r)=\begin{cases}\tfrac12r^2,&|r|\le1,\\|r|-\tfrac12,&|r|>1,\end{cases}\qquad\widetilde\rho(r)=\sqrt{1+r^2}-1.$$

(a) [4]

Find $\rho^{\prime}(r)$, including $r=\pm1$, and explain why $F(a)=\sum_{i=1}^4\rho(y_i-a)$ is convex.

Detailed solutions and marking Q1(a)

(b) [6]

Find the unique minimizer of F and justify global optimality. Also find the ordinary least-squares constant. If $y_4$ changes from 8 to 80, does the Huber minimizer change? Explain.

Detailed solutions and marking Q1(b)

(c) [3]

Differentiate $\widetilde\rho$. Compare its derivative for large $|r|$ with that of $r^2/2$, and explain the relevance to a large residual.

Detailed solutions and marking Q1(c)

(d) [3]

A student standardizes every predictor using the full dataset, performs five-fold CV to select a loss, then reports the smallest CV error as an independent test error. Identify two distinct problems and give a corrected evaluation procedure.

Detailed solutions and marking Q1(d)

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

Detailed solutions and marking Q2

The algorithms below have no regularization penalty. For matching pursuit (MP), start with $c=0,r=y$, choose the largest $|d_j^Tr|$, set $\gamma=d_j^Tr$, then update $c_j\leftarrow c_j+\gamma$, $r\leftarrow r-\gamma d_j$. Orthogonal matching pursuit (OMP) uses the same selection rule but jointly refits all selected columns by least squares after every choice. Never select an already active index in OMP. Break correlation ties by the smaller index.

$$d_1=\begin{pmatrix}1\\0\\0\end{pmatrix},\quad d_2=\begin{pmatrix}3/5\\4/5\\0\end{pmatrix},\quad d_3=\begin{pmatrix}0\\0\\1\end{pmatrix},\quad D=(d_1\ d_2\ d_3),\quad y=\begin{pmatrix}2\\1\\1/5\end{pmatrix}.$$

(a) [2]

Check all column norms, compute the initial correlations, and identify the first selected column.

Detailed solutions and marking Q2(a)

(b) [5]

Perform exactly two MP iterations. Give selected indices, coefficient increments, final coefficients, residual, and RSS.

Detailed solutions and marking Q2(b)

(c) [5]

Perform exactly two OMP iterations. Write and solve the normal equations for the second refit; give final coefficients, residual, and RSS.

Detailed solutions and marking Q2(c)

(d) [3]

Compute inner products of the final MP residual with $d_1,d_2$ and compare with OMP. Explain why the algorithms differ after two iterations.

Detailed solutions and marking Q2(d)

(e) [3]

For least-squares model spaces $V_1\subseteq V_2$, prove $\mathrm{RSS}_2\le\mathrm{RSS}_1$. Does this also guarantee non-increasing training MAE of the least-squares fits? Explain.

Detailed solutions and marking Q2(e)

Q3. Kernel PCA and its normalization (17)

Detailed solutions and marking Q3

Take $t_1=-1,t_2=0,t_3=1$ and $\phi(t)=(t,t^2)^T$, with kernel $k(s,t)=st+s^2t^2$. Let $\Phi$ have rows $\phi(t_i)^T$. Use the definitions below and sample covariance $S_\phi=\Phi_c^T\Phi_c/(3-1)$.

$$C=I_3-\tfrac13\mathbf1\mathbf1^T,\qquad\Phi_c=C\Phi,\qquad K=\Phi\Phi^T,\qquad K_c=CKC.$$

(a) [5]

Compute the feature mean, $\Phi_c,K,K_c$. Verify $K_c\mathbf1=0$.

Detailed solutions and marking Q3(a)

(b) [4]

Find all eigenvalues of $K_c$ and a unit eigenvector q for the largest eigenvalue $\lambda$. Choose its third entry positive.

Detailed solutions and marking Q3(b)

(c) [4]

For $w=\Phi_c^Tq/\sqrt\lambda$, prove $\|w\|_2=1$ and compute $z=\Phi_cw$. Explain why omitting the normalizing factor fails to produce a unit principal direction.

Detailed solutions and marking Q3(c)

(d) [4]

Compute the first-component variance, explained-variance ratio, and total squared feature-space reconstruction error when retaining only that component.

Detailed solutions and marking Q3(d)

Q4. Learned distances and random projections (16)

Detailed solutions and marking Q4

Use $d_M(x,y)=\sqrt{(x-y)^TM(x-y)}$ for the following matrix and points.

$$M=\begin{pmatrix}1&2\\2&4\end{pmatrix},\quad o=\begin{pmatrix}0\\0\end{pmatrix},\quad u=\begin{pmatrix}2\\0\end{pmatrix},\quad v=\begin{pmatrix}0\\1\end{pmatrix}.$$

(a) [4]

Factor $M=L^TL$ with L having one row. Prove positive semidefiniteness; find rank and null space.

Detailed solutions and marking Q4(a)

(b) [3]

Compute $d_M(o,u),d_M(o,v),d_M(u,v)$. Is this a metric on all of $\mathbb R^2$? For $M_\tau=M+\tau I_2$, $\tau>0$, compute $d_{M_\tau}(u,v)^2$ and explain the change.

Detailed solutions and marking Q4(b)

(c) [3]

Let $R\in\mathbb R^{k\times d}$ have independent $N(0,1/k)$ entries. For fixed $a\in\mathbb R^d$, prove $\mathbb E\|Ra\|_2^2=\|a\|_2^2$.

Detailed solutions and marking Q4(c)

(d) [6]

A fixed set of $n\ge2$ points is chosen before R. For each fixed nonzero difference a, assume the bound below, where $c>0$, $0<\varepsilon<1$. Use a union bound to give a sufficient k for all pairwise squared distances to obey $1\pm\varepsilon$ simultaneously with probability at least $1-\delta$, $0<\delta<1$. Explain why this guarantees neither every draw nor preservation of all distances in $\mathbb R^d$ by one map with $k<d$.

$$\Pr\!\left(\left|\|Ra\|_2^2-\|a\|_2^2\right|>\varepsilon\|a\|_2^2\right)\le2e^{-ck\varepsilon^2}.$$

Detailed solutions and marking Q4(d)

Q5. One complete Gaussian EM iteration (14)

Detailed solutions and marking Q5

For observations $x_1=-2,x_2=2$, use standard soft EM for the mixture likelihood with the parameters and density below. Update all weights, means, and variances. Here log is natural logarithm.

$$\pi_1=\tfrac13,\quad\pi_2=\tfrac23,\quad\mu_1=-2,\quad\mu_2=2,\quad\sigma_1^2=\sigma_2^2=\frac8{\log2}.$$ $$\varphi(x;\mu,\sigma^2)=\frac1{\sqrt{2\pi\sigma^2}}\exp\!\left(-\frac{(x-\mu)^2}{2\sigma^2}\right).$$

(a) [4]

Calculate the entire responsibility matrix $r_{ik}=\Pr(Z_i=k\mid x_i)$. Use old parameters for both observations.

Detailed solutions and marking Q5(a)

(b) [6]

Compute $N_k=\sum_i r_{ik}$, then all six updated parameters $\pi_k^{new},\mu_k^{new},(\sigma_k^2)^{new}$ for k=1,2, using exact values.

Detailed solutions and marking Q5(b)

(c) [2]

Why is the variance denominator $N_k$ rather than $N_k-1$, and why use the new mean in squared deviations?

Detailed solutions and marking Q5(c)

(d) [2]

State the monotonicity guarantee of an exact EM iteration. Does it ensure a unique global optimum or correct underlying labels?

Detailed solutions and marking Q5(d)

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

Detailed solutions and marking Q6

Use the definitions in each subpart; the datasets in (a) and (b) are separate.

(a) [4]

For fixed reference points $X=\{0,1,2,4,8\}$, use the flat kernel and update below. Start at $p_0=4$, list every selected neighborhood, and iterate until unchanged. Never move the original observations.

$$K(x,p)=\begin{cases}1,&|x-p|\le2,\\0,&|x-p|>2,\end{cases}\qquad p_{t+1}=\frac{\sum_{x\in X}K(x,p_t)x}{\sum_{x\in X}K(x,p_t)}.$$

Detailed solutions and marking Q6(a)

(b) [4]

For separate data $x_1=0,x_2=1,x_3=4,x_4=5$, define $\operatorname{core}_3(x_i)$ as the third-smallest distance, including self-distance zero. For distinct points use the mutual reachability formula below. Compute four core distances and all six edge weights.

$$d_{mr}(x_i,x_j)=\max\{\operatorname{core}_3(x_i),\operatorname{core}_3(x_j),|x_i-x_j|\}.$$

Detailed solutions and marking Q6(b)

(c) [3]

Construct an MST by scanning edges in increasing weight, skipping cycles; break equal weights lexicographically by $(i,j)$ with $i<j$. Give selected edges and total weight.

Detailed solutions and marking Q6(c)

(d) [2]

Keep only tree edges of weight at most 3. Give connected components and explain why these alone do not specify the final HDBSCAN output.

Detailed solutions and marking Q6(d)

Q7. Soft regions and median centers (6)

Detailed solutions and marking Q7

Use ordinary distances as specified below.

(a) [3]

Original sites on a line are $s_1=0,s_2=10$. Insert x=3. Let $R_x$ be its new Voronoi interval and $R_1,R_2$ the old regions. Compute $w_j=\operatorname{length}(R_x\cap R_j)/\operatorname{length}(R_x)$ for j=1,2. Show the old boundary, new interval, and overlap lengths.

Detailed solutions and marking Q7(a)

(b) [3]

For observations 0,2,9,11 with absolute distance, give all optimal one-median centers allowed anywhere on the line and all optimal one-medoid centers restricted to observations. In higher dimensions, which norm permits coordinatewise medians to minimize total distance? Does the same rule generally hold for Euclidean distance?

Detailed solutions and marking Q7(b)