Machine Learning Techniques · Quiz 1 · Sep 2025

**1. Explain convergence:** Each Lloyd assignment/update step cannot increase \(J=\sum_i\|x_i-\mu_{z_i}\|^2\). With standard consistent tie handling and nonempty clusters, the finite set of assignments reaches a stable solution. **2. Explain limitations:** Squared distance gives extreme observations large influence on the means, so outliers matter. A stable solution is not guaranteed to be the global minimum. **Answer: A, C — Converges under standard assumptions; sensitive to outliers.** A: **Correct:** Standard Lloyd updates converge to a fixed assignment under the usual tie/empty-cluster assumptions. B: **Incorrect:** Initialization changes the reached solution, not the standard convergence property. C: **Correct:** The squared-distance objective and arithmetic means are sensitive to outliers. D: **Incorrect:** Different initializations can lead to different suboptimal fixed points.

**1. Compute K-means++ weights:** From (0,0), squared distances to (0,2),(2,0),(2,2) are 4,4,8. Normalization gives probabilities 1/4,1/4,1/2. **2. Analyze diagonal seeds:** If the second seed is (2,2), the two other corners tie between the seeds. After assigning those ties and updating means once, the resulting partition is stable: it can be a horizontal split, vertical split, or a three-versus-one corner partition. **3. Conclude:** The diagonal corner is twice as likely as an adjacent corner, and the tie rule changes the final means. One nontrivial centroid update suffices for this square. **Answer: B, C, D — B, C and D.** **Convention note:** “One iteration” counts the assignment-plus-mean update; an implementation may make an additional unchanged pass to detect convergence. This is a property of the particular square, not a general K-means++ guarantee. A: **Incorrect:** The diagonal point has twice the squared-distance weight. B: **Correct:** 8/(4+4+8)=1/2 is twice 4/16=1/4. C: **Correct:** For this square the partition chosen at the first tie resolution is stable after its mean update. D: **Correct:** Different tie assignments give different stable partitions and means.

**1. Update the Beta prior:** Three defects and 97 nondefects give posterior \(\mathrm{Beta}(a+3,b+97)\). Its mean is \((a+3)/(a+b+100)\). **2. Use the uniform prior:** With a=b=1, the mean is \(4/102\approx0.0392157\), matching A. **3. Use the half-parameter prior:** With a=b=0.5, the mean is \(3.5/101\approx0.0346535\), matching the intended approximate value in D. **Answer: A, D — A and D — posterior means 0.039216 and 0.034653.** **Convention note:** D prints 0.034, which truncates rather than correctly rounds the exact value to three decimals. Conventional three-decimal rounding would give 0.035. A: **Correct:** 4/102 is approximately 0.039. B: **Incorrect:** 0.03 is the raw sample proportion, not this posterior mean. C: **Incorrect:** The half-parameter posterior mean is approximately 0.03465, not 0.025. D: **Correct:** This is the intended approximate choice for 3.5/101.

**1. Use known positive-semidefinite kernels:** The Gaussian squared-exponential kernel and the exponential-distance kernel are valid for positive scale. The latter is the Matérn kernel with smoothness 1/2. **2. Expand the polynomial:** For c≥0 and integer d, \((x^Ty+c)^d\) is a nonnegative sum of monomial inner products, so it is a valid kernel. **3. Reject raw distance:** For distinct x,y, the Gram matrix for \(k(x,y)=\|x-y\|\) is \(\begin{pmatrix}0&r\\ r&0\end{pmatrix}\), whose eigenvalues are r and −r. It is not positive semidefinite. **Answer: A, B, D — Gaussian, polynomial and exponential-distance kernels.** A: **Correct:** The Gaussian kernel is positive semidefinite for positive bandwidth. B: **Correct:** The stated nonnegative offset and integer degree yield a valid polynomial kernel. C: **Incorrect:** A two-point Gram matrix has a negative eigenvalue. D: **Correct:** The exponential Euclidean-distance kernel is positive semidefinite.

**1. Establish a lower bound:** Independent columns \(c_1,c_2,c_3\) give rank at least 3. **2. Establish an upper bound:** \(c_4=2c_1-c_2\), \(c_5=c_2+c_3\), \(c_6=4c_1-3c_3\), so every column is in their span and rank is at most 3. **3. Connect rank to PCA:** Exactly three eigenvalues are positive. Retaining those three PCs reconstructs the centered data with zero residual; thus the minimum k is 3. **Answer: 3.**

**1. Use shared nonzero eigenvalues:** \(X^TX\) and \(XX^T\) share the same positive eigenvalues. The covariance’s common normalization factor cancels in a variance ratio. **2. Divide the largest by the total:** \[\text{fraction}=\frac{10}{10+5+3+2+1}=\frac{10}{21}\approx0.476190.\] Rounded to two decimals: 0.48. **Answer: 0.48.** **Convention note:** As is customary in this PCA question, X is treated as centered. If it were not centered, eigenvalues of its uncentered Gram matrix would not directly determine centered variance.

**1. Read and center the points:** The dataset is (2,1),(1,2),(−2,−1),(−1,−2), whose mean is (0,0). **2. Sum coordinate products:** \(\sum x_1^2=10\), \(\sum x_2^2=10\), and \(\sum x_1x_2=8\). **3. Normalize by n=4:** \[C=\frac14\begin{pmatrix}10&8\\8&10\end{pmatrix}=\begin{pmatrix}2.5&2\\2&2.5\end{pmatrix}.\] **Answer: B — \(C=\begin{pmatrix}2.5&2\\2&2.5\end{pmatrix}\).** **Convention note:** Covariance uses 1/n normalization, consistent with the question’s scoring key. A: **Incorrect:** It uses twice the required 1/4-normalized covariance. B: **Correct:** Both diagonal variances and covariance match the coordinate sums. C: **Incorrect:** Its entries do not match the dataset’s second moments. D: **Incorrect:** Its entries are too large under the stated PCA convention.

**1. Form covariance:** The centered points give \(C=\begin{pmatrix}2.5&2\\2&2.5\end{pmatrix}\). **2. Find its eigenvalues:** For a matrix with diagonal a and off-diagonal b, the eigenvalues are a+b and a−b. Here they are 4.5 and 0.5. **3. Select the first PC:** PCA chooses the largest eigenvalue, so its projected variance is 4.5 along \((1,1)/\sqrt2\). **Answer: 4.5.**

**1. Compute covariance:** The dataset yields \(C=\begin{pmatrix}2.5&2\\2&2.5\end{pmatrix}\). **2. Use the orthogonal direction:** Along \(w_2=(1,-1)/\sqrt2\), \(Cw_2=(2.5-2)w_2=0.5w_2\). **3. Read the variance:** The second-PC variance is its eigenvalue, 0.5; together the two PCs explain total variance 5. **Answer: 0.5.**

**1. Form one observation’s density:** A two-component Gaussian mixture has \(p(x_i)=\sum_{k=1}^2\pi_k\mathcal N(x_i;\mu_k,\sigma_k^2)\). **2. Multiply independent observations:** \[L(\theta)=\prod_{i=1}^{3}\sum_{k=1}^{2}\pi_k\frac1{\sigma_k\sqrt{2\pi}}\exp\!\left[-\frac{(x_i-\mu_k)^2}{2\sigma_k^2}\right].\] **Answer: B — Weighted mixture densities multiplied over all three observations.** A: **Incorrect:** It omits the mixing probabilities πk. B: **Correct:** It contains the weights, two-component sum and product over all three observations. C: **Incorrect:** It omits weights and includes only two observations. D: **Incorrect:** It includes weights but omits the third observation.

**1. Apply Bayes’ rule to the first row:** \[\lambda_1^{,1}=\frac{\pi_1f(x_1\mid z_1=1)}{\pi_1f(x_1\mid z_1=1)+\pi_2f(x_1\mid z_1=2)}.\] **2. Insert the supplied densities:** \(\pi_1=0.3\), \(\pi_2=0.7\), and the first row is (0.242,0.054). Thus the numerator is 0.0726 and denominator is \(0.0726+0.0378=0.1104\). **3. Normalize:** \(0.0726/0.1104\approx0.657609\), giving 0.66. **Answer: 0.66.** **Convention note:** The other table rows are inconsistent with the stated x=10,20 and Gaussian means 2,3, but the requested first-observation responsibility uses the supplied first row and is unaffected.

**1. Assign to the initial means:** From \(\mu_1=(-2,3)\), \(\mu_2=(2,-1)\), the points (−3,4),(−2,3),(1,4),(−3,−1) join cluster 1; (2,−1),(1,−2) join cluster 2. **2. Average each group:** \[\mu_1=\left(\frac{-3-2+1-3}{4},\frac{4+3+4-1}{4}\right)=(-1.75,2.5),\quad\mu_2=(1.5,-1.5).\] **3. Verify stability:** Recomputing nearest-centroid assignments at these means leaves both groups unchanged, so these are the final means. **Answer: A — (−1.75,2.5) and (1.5,−1.5).** A: **Correct:** It matches the averages of the stable groups. B: **Incorrect:** These are the initial seeds, which change on the first update. C: **Incorrect:** This grouping does not match the nearest-mean assignments from the given seeds. D: **Incorrect:** These positive first coordinates cannot describe the left-heavy first group.