90 minutes · 100 marks · 7 questions. Original self-study practice, not an official examination specification or weighting forecast. Answer every part; show essential calculations and proofs. Exact values are preferred; if a decimal answer is requested, state the rounding used. Consistent paired eigenvector/singular-vector sign changes are acceptable. Follow each question’s normalization, domain and tie rules; never assume an inverse exists. Use a Casio fx-50FH II for this practice; one double-sided A4 reference sheet may be used. These are practice conditions, not a new claim about official examination rules.

Paired solutions · Revision

Q1. Weighted polynomial regression and uniqueness (20)

Paired solutions Q1

Fit a quadratic using the specified residual multipliers. The weights are squared in the objective; do not replace them by unsquared weights.

$$\begin{gathered} \begin{array}{c|rrrr}i&1&2&3&4\\x_i&-2&-1&1&2\\y_i&2&1&3&4\\w_i&1&2&2&1\end{array} \qquad f(x)=c_0+c_1x+c_2x^2,\quad R(c)=\sum_{i=1}^4w_i^2(y_i-f(x_i))^2. \end{gathered}$$

(a) [4]

Write the design matrix M, diagonal W and weighted normal equations. Derive the equations from the objective.

Paired solutions Q1(a)

(b) [7]

Calculate the fitted polynomial, residual vector r=y−Mc, and minimum R(c).

Paired solutions Q1(b)

(c) [5]

Now let x₁,…,xₙ be arbitrary distinct real inputs and let weights be nonnegative. Prove MᵀW²M is invertible if and only if at least three weights are positive.

Paired solutions Q1(c)

(d) [4]

For unregularized quadratic LOOCV with retained observations all assigned weight1 and distinct inputs, find the smallest n guaranteeing a unique fit in every fold. Prove sufficiency and minimality.

Paired solutions Q1(d)

Q2. Regularization, training scores and validation (14)

Paired solutions Q2

Keep the loss and intercept-penalty conventions explicit in each part.

(a) [6]

Fit a constant to y₁=2,y₂=4 using the displayed objective. Find its minimizer and training R². Explain why negative training R² here does not contradict ordinary least squares with an intercept.

$$\begin{gathered} F(a)=(2-a)^2+(4-a)^2+2a^2,\quad R^2=1-\mathrm{RSS}/\mathrm{TSS},\quad\mathrm{TSS}=\sum_i(y_i-\bar y)^2. \end{gathered}$$

Paired solutions Q2(a)

(b) [4]

For X∈Rⁿˣᵖ and TSS>0, prove every global minimizer of the displayed objective with unpenalized intercept has training0≤R²≤1.

$$\begin{gathered} \min_{a\in\mathbb R,\ b\in\mathbb R^p}\|y-a\mathbf1-Xb\|_2^2+\lambda\|b\|_2^2,\qquad\lambda>0. \end{gathered}$$

Paired solutions Q2(b)

(c) [4]

A student standardizes and fits PCA on all data, then splits training/test data, evaluates ten ridge penalties repeatedly on the test set, and reports the best test score. Identify two distinct leaks and give a corrected procedure.

Paired solutions Q2(c)

Q3. Negative dominant eigenvalue and one completion step (15)

Paired solutions Q3

Part(a) and parts(b)–(c) use different matrices.

(a) [4]

Perform one normalized power iteration and compute its Rayleigh quotient. Give the limiting eigenvalue estimate and explain the signs of the iterates.

$$\begin{gathered} B=\begin{pmatrix}-3&0\\0&1\end{pmatrix},\quad v^{(0)}=\frac1{\sqrt2}\binom11,\quad v^{(1)}=\frac{Bv^{(0)}}{\|Bv^{(0)}\|_2}. \end{gathered}$$

Paired solutions Q3(a)

(b) [6]

Find a full real SVD of the prescribed initialization, with nonnegative singular values decreasingly ordered. Verify the pairing of left and right vectors.

$$\begin{gathered} P=\begin{pmatrix}1&?\\2&1\end{pmatrix},\qquad X^{(0)}=\begin{pmatrix}1&2\\2&1\end{pmatrix}. \end{gathered}$$

Paired solutions Q3(b)

(c) [5]

Perform exactly one step with fixed thresholdλ=1: replace σᵢ by(σᵢ−1)₊ to obtain Y, then restore all observed P entries to obtain X¹. Give both ranks and explain why they need not agree.

Paired solutions Q3(c)

Q4. Classical multidimensional scaling (9)

Paired solutions Q4

The matrix contains Euclidean distances between three objects. D⁽²⁾ means entrywise squares, not matrix multiplication.

$$\begin{gathered} D=\begin{pmatrix}0&1&3\\1&0&2\\3&2&0\end{pmatrix},\qquad H=I_3-\frac13\mathbf1\mathbf1^T. \end{gathered}$$

(a) [5]

Explain why G=−HD⁽²⁾H/2 is the centered Gram matrix and calculate G.

Paired solutions Q4(a)

(b) [4]

Find all eigenvalues and a one-dimensional centered coordinate representation reproducing all three distances. State its remaining ambiguity.

Paired solutions Q4(b)

Q5. LDA with specified covariance normalization (9)

Paired solutions Q5

Use the class and covariance definitions exactly as given.

$$\begin{gathered} C_1=\{x_1=(-1,0)^T,x_2=(1,0)^T\},\quad C_2=\{x_3=(3,0)^T,x_4=(3,4)^T\}. \\\Sigma_W=\frac14\sum_{k=1}^2\sum_{x\in C_k}(x-\mu_k)(x-\mu_k)^T,\qquad\Sigma_B=\frac12\sum_{k=1}^2(\mu_k-\mu)(\mu_k-\mu)^T. \end{gathered}$$

(a) [4]

Find the two class means, overall mean, ΣW and ΣB.

Paired solutions Q5(a)

(b) [3]

Find a unit direction maximizing the Fisher ratio, with positive first coordinate, and its generalized eigenvalue.

$$\begin{gathered} \max_{\|u\|_2=1}\frac{u^T\Sigma_Bu}{u^T\Sigma_Wu}. \end{gathered}$$

Paired solutions Q5(b)

(c) [2]

Compute all four raw projected coordinates uᵀxᵢ.

Paired solutions Q5(c)

Q6. Hierarchical clustering: linkage matters (15)

Paired solutions Q6

Use ordinary absolute distance, not squared distance. Start with singleton clusters. If tied, choose the pair whose sorted sequence of member labels is lexicographically smallest.

$$\begin{gathered} A=0,\quad B=2,\quad C=5,\quad D=17/2,\qquad d(x,y)=|x-y|. \end{gathered}$$

(a) [4]

Perform single-linkage agglomeration and give every merge and height.

Paired solutions Q6(a)

(b) [7]

Repeat using average linkage. Show all updated intercluster distances after the first merge and calculate the final merge height.

$$\begin{gathered} d_{\rm av}(S,T)=\frac1{|S||T|}\sum_{s\in S}\sum_{t\in T}d(s,t). \end{gathered}$$

Paired solutions Q6(b)

(c) [4]

For disjoint nonempty S,T,U derive the update of d_av(S∪T,U) from the two previous distances. When is their unweighted mean guaranteed correct?

Paired solutions Q6(c)

Q7. DBSCAN: a shared border point is not a core bridge (18)

Paired solutions Q7

Process points alphabetically. Neighborhoods include the point itself and equality at the radius. Only core points expand clusters. A reachable noncore point may join as border but does not expand. A border reached by two core components stays assigned to the first processed component and is not reassigned. Unassigned points are noise.

$$\begin{gathered} \begin{array}{c|rrrrrrrrrr}p&A&B&C&D&E&F&G&H&I&J\\x_p&-1.8&-1.7&-1.6&-0.9&0&0.9&1.6&1.7&1.8&4\end{array} \\\varepsilon=1,\quad\mathrm{minPts}=4,\quad N_\varepsilon(p)=\{q:|p-q|\le\varepsilon\}. \end{gathered}$$

(a) [6]

Calculate every neighborhood count and classify all ten points as core, border or noise.

Paired solutions Q7(a)

(b) [4]

State the final clusters under the stated order and the noise set.

Paired solutions Q7(b)

(c) [4]

A researcher instead connects p,q by an undirected edge whenever distance≤ε and at least one endpoint is core, then uses connected components. Does the component containing D reproduce standard DBSCAN? Explain with explicit edges.

Paired solutions Q7(c)

(d) [4]

Let core₄(p) be the fourth-smallest distance including p itself. Compute core₄(D),core₄(E) and their mutual reachability distance. Explain how it reduces the influence of a sparse bridge.

$$\begin{gathered} d_{\rm mr}(D,E)=\max\{\operatorname{core}_4(D),\operatorname{core}_4(E),|D-E|\}. \end{gathered}$$

Paired solutions Q7(d)