Machine Learning Techniques · Quiz 1 · Jan 2026

**1. Compare the partitions:** Scenario 2 returns to the initial partition; scenario 1 has exactly the same two groups with their labels exchanged. Both therefore have the initial partition’s within-cluster sum of squared distances after fitting its means. **2. Use Lloyd’s descent property:** Updating means minimizes that objective for a fixed assignment; reassigning points to strictly nearer means decreases it. A genuine ten-iteration run cannot return to the same objective-equivalent partition after making such progress. **3. Apply the convergence condition:** If the initial assignment were already stable, the algorithm would stop immediately rather than first converge after ten iterations. Thus neither proposed final assignment is compatible with the stated nontrivial run. **Answer: D — Both scenarios are impossible under standard Lloyd updates.** **Convention note:** This uses the usual deterministic, noncycling tie handling and nonempty-cluster convention. Gratuitous relabelling or arbitrary changes between tied assignments are not the standard run meant here. A: **Incorrect:** A label-swapped initial partition cannot result after a genuinely descending ten-iteration run. B: **Incorrect:** Returning to the initial partition would contradict the same descent argument. C: **Incorrect:** Neither return is compatible with the stated iteration count. D: **Correct:** Both have the initial partition’s objective and cannot be reached after strict progress.

**1. Find a zero-variance direction:** All centered points satisfy \(a^Tx=0\) for \(a=(2,1,-1,2)^T\). Therefore \(Ca=0\), because every outer-product contribution \(xx^Ta\) is zero. **2. Normalize the normal vector:** \(\|a\|=\sqrt{4+1+1+4}=\sqrt{10}\). Thus \(a/\sqrt{10}\) and its negative are unit eigenvectors with eigenvalue zero. **3. Identify the last component:** PCA orders directions by decreasing variance; the hyperplane normal supplies the zero-variance fourth component. Both signs describe the same principal axis. **Answer: A, B — \(\pm(2,1,-1,2)/\sqrt{10}\).** **Convention note:** The intended answer assumes the data span the stated three-dimensional hyperplane. If their rank is smaller, additional zero-eigenvalue directions can also be chosen as the fourth component; the single equation alone does not exclude that degeneracy. A: **Correct:** It is the normalized normal vector with zero projected variance. B: **Correct:** It is the opposite orientation of the same zero-variance axis. C: **Incorrect:** It is not parallel to the stated hyperplane normal. D: **Incorrect:** It is not parallel to the stated hyperplane normal.

**1. State the kernel convention:** For the inhomogeneous polynomial kernel \(k(x,z)=(1+x^Tz)^3\), the feature map includes all monomials of total degree 0 through 3 in four variables. **2. Count monomials:** Introduce a slack exponent for the unused degree. Stars-and-bars gives \[\binom{4+3}{3}=\binom73=\frac{7\cdot6\cdot5}{3\cdot2\cdot1}=35.\] **Answer: 35.** **Convention note:** The question does not print the kernel formula. Its key uses the inhomogeneous convention. The homogeneous kernel (xᵀz)^3 has only degree-three monomials and dimension C(6,3)=20.

**1. Use the Gaussian kernel:** \(k(x,z)=\exp[-\|x-z\|^2/(2\sigma^2)]\). Here \(x=(0,1)\), \(z=(1,0)\), and \(\sigma=1\). **2. Compute squared distance:** \(\|x-z\|^2=(-1)^2+1^2=2\). **3. Substitute:** \(k=e^{-2/(2\cdot1)}=e^{-1}\approx0.367879\), giving 0.37. **Answer: 0.37.**

**1. Apply K-means++ sampling:** Each unchosen point is weighted by its squared distance to the nearest already chosen mean, (0,0) or (1,1). **2. Compute the weights:** For (−1,0), (2,1), and (1,−1), the nearest squared distances are respectively 1,1,2. The two chosen points have weight zero. **3. Normalize:** \[P(\mu_3=(1,-1))=\frac2{1+1+2}=\frac12=0.5.\] **Answer: 0.5.**

**1. Use symmetry:** The eight corners \((\pm1,\pm1,\pm1)\) have mean zero. Each coordinate has mean square 1; each cross-product averages to zero because all sign combinations occur. **2. Form covariance:** With normalization 1/8, \[C=\frac18\sum_{i=1}^8x_ix_i^T=\begin{pmatrix}1&0&0\\ 0&1&0\\ 0&0&1\end{pmatrix}.\] **3. Sum entries:** The three diagonal ones contribute \(1+1+1=3\). **Answer: 3.** **Convention note:** The course uses population/PCA normalization 1/n. The unbiased 1/(n−1) covariance would instead be (8/7)I.

**1. Compute covariance from the corners:** Equal coordinate sign combinations give \(C=I_3\) under the course’s 1/8 normalization. **2. Compute projected variance:** For any unit vector v, \[\operatorname{Var}(v^Tx)=v^TCv=v^Tv=\|v\|^2=1.\] The cube is equally variable in every direction. **Answer: 1.**

**1. Use PCA coordinates:** For centered data, the coordinate along a unit principal direction is the dot product \(a=w_1^Tx\). **2. Substitute:** With \(w_1=(1,1,0)/\sqrt2\) and \(x=(1,2,3)\), \[a=\frac{1+2+0}{\sqrt2}=\frac3{\sqrt2}\approx2.121320.\] To three decimal places: 2.121. **Answer: 2.121.**

**1. Select the second direction:** \(b=w_2^Tx\), where \(w_2=(-1,1,0)/\sqrt2\) and \(x=(1,2,3)\). **2. Take the dot product:** \[b=\frac{-1+2+0}{\sqrt2}=\frac1{\sqrt2}\approx0.707107.\] To three decimal places: 0.707. **Answer: 0.707.**

**1. Use positive-semidefinite Gram matrices:** If \(K_1,K_2\) are kernel Gram matrices, then for any coefficients c, \[c^T(2K_1+5K_2)c=2c^TK_1c+5c^TK_2c\ge0.\] **2. Conclude validity:** Symmetry is also preserved, so the positive weighted sum is a valid kernel. **Answer: A — True.** A: **Correct:** Nonnegative sums preserve the kernel’s positive-semidefinite property. B: **Incorrect:** The weights 2 and 5 are positive, so the closure property applies.

**1. Compare dimensions:** For \(X\in\mathbb R^{d\times n}\), \(X^TX\) is n×n and \(XX^T\) is d×d. Their eigenvectors generally live in different spaces. **2. State the correct relationship:** They share nonzero eigenvalues. If \(X^TXv=\lambda v\), \(\lambda>0\), then \(Xv/\sqrt\lambda\) is an eigenvector of \(XX^T\), not generally the same vector. **Answer: B — False.** A: **Incorrect:** Shared nonzero eigenvalues do not imply shared eigenvectors. B: **Correct:** Their eigenvectors have different dimensions in general and are related by multiplication by X.

**1. Compute initial means:** For points (0,0),(3,0),(4,1),(1,1) and assignment (1,1,2,2), \(\mu_1=(1.5,0)\), \(\mu_2=(2.5,1)\). **2. Reassign by squared distances:** Ordered distance pairs to the means are (2.25,7.25), (2.25,1.25), (7.25,2.25), (1.25,2.25). This gives (1,2,2,1). **3. Update and check:** New means are (0.5,0.5) and (3.5,0.5). Every point remains with its nearer mean, so (1,2,2,1) is final. **Answer: B — (1,2,2,1).** A: **Incorrect:** The middle two near-boundary points change from the initial assignment. B: **Correct:** It agrees with both reassignment and the stable updated means. C: **Incorrect:** It places the far-right point with the far-left point. D: **Incorrect:** It incorrectly keeps the two right-side points in cluster 1. E: **Incorrect:** The second point is nearer the updated right-side cluster.

**1. Compute means from the given assignment:** For (1,2,2,1), cluster 1 contains (0,0),(1,1), so \(\mu_1=(0.5,0.5)\); cluster 2 contains (3,0),(4,1), so \(\mu_2=(3.5,0.5)\). **2. Check the distances:** The first and fourth points each have squared distance 0.5 to cluster 1; the second and third each have squared distance 0.5 to cluster 2. All alternative distances are larger. **3. Conclude:** No assignment changes, so the initial assignment is already the final one. **Answer: B — (1,2,2,1).** A: **Incorrect:** It mixes the left and right groups. B: **Correct:** It is stable under its own centroid update. C: **Incorrect:** It pairs opposite-side points. D: **Incorrect:** It puts three points into the left cluster despite their distances. E: **Incorrect:** The second point belongs to the right cluster.

**1. Form the observed-data likelihood:** Independence gives \[L(\theta)=\prod_{i=1}^4[\theta f_1(x_i)+(1-\theta)f_2(x_i)].\] **2. Take logs and insert the densities:** \[\ell(\theta)=\sum_{i=1}^4\log[\theta e^{-x_i}+(1-\theta)3e^{-3x_i}].\] The logarithm applies to each mixture sum before summing across observations. **Answer: C — \(\sum_i\log[\theta e^{-x_i}+(1-\theta)3e^{-3x_i}]\).** A: **Incorrect:** It averages component log-densities instead of taking the log of the mixture density. B: **Incorrect:** Independence gives a product across observations, not a sum inside one logarithm. C: **Correct:** It is the sum of log mixture densities. D: **Incorrect:** It omits the second component entirely.

**1. Apply Bayes’ rule:** At \(\theta=0.6\), \[\gamma(x)=\frac{0.6e^{-x}}{0.6e^{-x}+0.4(3e^{-3x})}=\frac1{1+2e^{-2x}}.\] **2. Evaluate each observation:** For x=0.2,0.5,1.1,1.8, responsibilities are approximately 0.427234,0.576117,0.818594,0.948184. **3. Sum before rounding:** \(\sum_i\gamma_i\approx2.770129\), giving 2.77. **Answer: 2.77.**

**1. Use the component-2 rule:** Since \(\gamma(x)=P(Z=1\mid x)\), assign component 2 when \(\gamma(x)\le0.5\). **2. Solve the boundary:** \(1/(1+2e^{-2x})\le1/2\) gives \(x\le(\ln2)/2\approx0.346574\). **3. Check the four observations:** Only 0.2 lies below this threshold; 0.5,1.1,1.8 are assigned to component 1. **Answer: A — {0.2} only.** A: **Correct:** Only 0.2 has first-component responsibility at most one-half. B: **Incorrect:** 0.5 has responsibility approximately 0.576, above one-half. C: **Incorrect:** Both larger observations have high first-component responsibility. D: **Incorrect:** Three observations exceed the decision threshold.