Machine Learning Techniques · Quiz 1 · May 2025

**1. Compare seeding rules:** After choosing a first seed, K-means++ samples each next seed with probability proportional to \(D(x)^2\), the squared distance to its nearest existing seed. **2. Explain the benefit:** Regions poorly represented by current seeds receive larger sampling probability, spreading the seeds and improving typical starting quality. K and the eventual number of Lloyd iterations are not determined by this rule. **Answer: B — It improves centroid initialization by spreading them out, leading to better .** A: **Incorrect:** No fixed iteration count is guaranteed. B: **Correct:** Distance-weighted seeding spreads centers across the data. C: **Incorrect:** K is still an input. D: **Incorrect:** The algorithm is randomized and multiple starts can still help.

**1. Read the objective sequence:** It decreases 800→500→400 at iterations 1–3, then remains 400 at iterations 4 and 5. **2. Identify the reached plateau:** The converged objective is first reached at iteration 3; the following unchanged iterations confirm the plateau. **Answer: B — Iteration 3.** **Convention note:** The key counts the iteration that reaches the plateau, not the subsequent iteration at which a stopping test first detects unchanged objective. A: **Incorrect:** A further decrease occurs after iteration 2. B: **Correct:** Iteration 3 is the first to attain the final objective 400. C: **Incorrect:** Iteration 5 only repeats an already reached value. D: **Incorrect:** Iteration 4 first verifies no decrease, but the plateau began at 3.

**1. Express the normalizer:** \(k(x,x)=\phi(x)^T\phi(x)=\|\phi(x)\|^2\). Thus the denominator is \(\|\phi(x)\|\|\phi(y)\|\). **2. Split the scale between both factors:** Taking \(\phi_1(x)=10\phi(x)/\|\phi(x)\|\) gives \[\phi_1(x)^T\phi_1(y)=\frac{100\,\phi(x)^T\phi(y)}{\|\phi(x)\|\|\phi(y)\|}=k_1(x,y).\] **Answer: C — \(\phi_1(x)=10\phi(x)/\|\phi(x)\|\).** **Convention note:** The formula requires k(x,x)>0 at each input. If a feature vector is zero, the original normalized-kernel expression is undefined there unless an additional convention is supplied. A: **Incorrect:** Scaling each feature vector by 100 multiplies the kernel by 10000. B: **Incorrect:** Scaling each vector by 1/10 multiplies the normalized kernel by 1/100. C: **Correct:** Scaling each vector by 10 yields the required factor 100. D: **Incorrect:** The displayed normalized feature map establishes validity.

**1. Read the data by columns:** \(x_1=(1,0,0)^T\), \(x_2=(0,1,0)^T\). With \(k(x_i,x_j)=(1+x_i^Tx_j)^2\), diagonal entries are 4 and off-diagonal entries 1: \(K=\begin{pmatrix}4&1\\1&4\end{pmatrix}\). **2. Compute means:** Both row/column means and the grand mean are 2.5. **3. Center the Gram matrix:** \(K^c_{ij}=K_{ij}-2.5-2.5+2.5\), yielding \[K^c=\begin{pmatrix}1.5&-1.5\\-1.5&1.5\end{pmatrix}.\] **Answer: B — \(\begin{pmatrix}1.5&-1.5\\-1.5&1.5\end{pmatrix}\).** A: **Incorrect:** It is the negative of the positive-semidefinite centered matrix. B: **Correct:** It subtracts the correct row and column means. C: **Incorrect:** It is the uncentered Gram matrix. D: **Incorrect:** It is not symmetric, so it cannot be this centered Gram matrix.

**1. Perform the E-step:** Use current parameters \(\theta^{old}\) to compute the latent-variable posterior and \(Q(\theta\mid\theta^{old})=E[\log p(X,Z\mid\theta)\mid X,\theta^{old}]\). **2. Perform the M-step:** Choose new parameters maximizing Q. This alternation improves the observed-data likelihood under the standard EM construction. **Answer: A — E-step: latent posterior expectation; M-step: maximize expected complete-data log likelihood.** A: **Correct:** It captures posterior estimation followed by parameter maximization, with the precise Q-function interpretation above. B: **Incorrect:** EM does not generally estimate the number of latent variables. C: **Incorrect:** The M-step optimizes parameters, not the number of latent variables. D: **Incorrect:** The M-step does not maximize parameter count.

**1. Relate Gram eigenvectors to unit PCs:** If \(X^TXv=\lambda v\) with \(\|v\|=1\), then \(w=Xv/\sqrt\lambda\). Hence \(\alpha_i=v_i/\sqrt\lambda\). **2. Normalize the printed direction:** The squared numerator norm is \(2^2+3^2+4^2+6^2=65\). Thus the unit eigenvector in that direction has second entry \(3/\sqrt{65}\), and \(\lambda=10\). **3. Compute:** \(\alpha_2=3/\sqrt{650}\approx0.117670\), giving 0.12 to two decimals. **Answer: 0.12.** **Convention note:** The printed denominator √54 does not normalize the vector: its squared norm is 65/54. If treated as already normalized, the intended mechanical formula gives 3/√540≈0.12910, or 0.13. The unit-PC calculation above corrects the normalization; both rounded values fall in the exported range.

**1. Write the log-likelihood:** For \(f(x\mid\theta)=\theta x^{-\theta-1}\), \[\ell(\theta)=n\log\theta-(\theta+1)\sum_i\log x_i.\] **2. Differentiate:** \(\ell\prime(\theta)=n/\theta-\sum_i\log x_i=0\) yields \(\hat\theta=n/\sum_i\log x_i\). Also \(\ell\prime\prime(\theta)=-n/\theta^2<0\). **3. Substitute the observations:** \(\sum_i\log x_i=\log2.5+\log1.8+\log3.2+\log2+\log2.7\approx4.353627\). Thus \(\hat\theta\approx1.148468\), which satisfies θ>1 and rounds to 1.148. **Answer: 1.148.**

**1. Store the basis:** Five retained principal directions in \(\mathbb R^{1000}\) require \(5\times1000=5000\) numbers. **2. Store the coordinates:** Each of 50 points requires five retained coordinates, giving \(50\times5=250\) more numbers. **3. Add:** \(5000+250=5250\) numbers suffice to reconstruct the centered rank-five dataset. **Answer: 5250.** **Convention note:** This is the course’s storage convention, excluding a separately stored mean. If the original nonzero mean must also be retained, add 1000 numbers, giving 6250.

**1. Center the observations:** Their mean is \(\bar x=(1,1)\), giving centered points (−1,−1),(1,0),(0,1). **2. Sum outer products:** \(\sum_i(x_i-\bar x)(x_i-\bar x)^T=\begin{pmatrix}2&1\\1&2\end{pmatrix}\). **3. Normalize:** \[C=\frac13\begin{pmatrix}2&1\\1&2\end{pmatrix}.\] **Answer: B — \(\frac13\begin{pmatrix}2&1\\1&2\end{pmatrix}\).** A: **Incorrect:** It uses uncentered second moments. B: **Correct:** It correctly centers and uses 1/3 normalization. C: **Incorrect:** This is a 3×3 sample Gram matrix, not the 2×2 feature covariance. D: **Incorrect:** The feature covariance must be 2×2, not 3×3.

**1. Center and form covariance:** With mean (1,1), \(C=\frac13\begin{pmatrix}2&1\\1&2\end{pmatrix}\). **2. Find the leading eigenvalue:** Along \(w=(1,1)/\sqrt2\), \(Cw=((2+1)/3)w=w\). The other eigenvalue is 1/3. **3. Read the projected variance:** The first-PC variance is the larger eigenvalue, 1. **Answer: 1.**

**1. Center and choose the first PC:** \(\bar x=(1,1)\) and \(w=(1,1)/\sqrt2\). The centered points are y1=(−1,−1), y2=(1,0), y3=(0,1). **2. Subtract the projections:** \(r_i=y_i-ww^Ty_i\). For y1 the residual is zero; for y2 subtract (0.5,0.5); for y3 subtract (0.5,0.5). **3. Collect residuals:** \[r_1=(0,0),\quad r_2=(0.5,-0.5),\quad r_3=(-0.5,0.5).\] These are orthogonal to w. **Answer: B — (0,0), (0.5,−0.5), (−0.5,0.5).** A: **Incorrect:** Its second and third vectors lie along the retained direction rather than orthogonal to it. B: **Correct:** It gives the three orthogonal reconstruction residuals. C: **Incorrect:** These do not equal centered observations minus their projections. D: **Incorrect:** The residual magnitudes and directions are incorrect.

**1. Solve two independent equations:** The first samples require \(4w_1+w_2=2\) and \(2w_1+8w_2=-14\). The first gives \(w_2=2-4w_1\); substitution yields \(-30w_1=-30\), so \(w_1=1,w_2=-2\). **2. Verify all observations:** \(x_1-2x_2\) predicts 2,−14,−7,−1, exactly the four given targets. Zero squared error is a global minimum. **Answer: B — \(y=x_1-2x_2\).** A: **Incorrect:** It predicts 6 rather than 2 on the first sample. B: **Correct:** It fits every target exactly. C: **Incorrect:** It predicts 3 rather than 2 on the first sample. D: **Incorrect:** It predicts 5 rather than 2 on the first sample.