Machine Learning Techniques Quiz 1: 13 July 2025 (May 2025 term)

How does K-means++ algorithm enhance the initialization process as compared to the standard K- means algorithm?

Let $k : \mathbb{R}^d \times \mathbb{R}^d \to \mathbb{R}$ be a valid kernel function such that $k(x, y) = \phi(x)^T\phi(y)$, where $\phi : \mathbb{R}^d \to \mathbb{R}^D$, where $d < D$. Define

$k_1(x, y) = \frac{100k(x, y)}{\sqrt{k(x, x)k(y, y)}}.$

Find $\phi_1 : \mathbb{R}^d \to \mathbb{R}^D$ such that $k_1(x, y) = \phi_1(x)^T\phi_1(y)$.

Note: $||x||_2 = \sqrt{x^Tx}$.