ML Katas

Support Vector Machines (SVMs) are powerful, and the "kernel trick" allows them to find non-linear decision boundaries without explicitly mapping data to high-dimensional spaces.

1. Linear Separability: Consider a 2D dataset where points are not linearly separable in their original feature space. Sketch an example of such a dataset (e.g., concentric circles or an XOR-like pattern).
2. Feature Mapping: Imagine a simple mapping function $\varphi (𝐱)=[x_1^2,\sqrt{2}{x}_1{x}_2,x_2^2]$ that transforms a 2D input $𝐱=[x_1,x_2]$ into a 3D feature space. Apply this mapping to two sample points, say ${𝐱}_A=[1,0]$ and ${𝐱}_B=[0,1]$.
3. The Kernel Trick: The "kernel trick" avoids explicit mapping by directly computing the dot product in the higher-dimensional space using a kernel function $K({𝐱}_i,{𝐱}_j)=\varphi ({𝐱}_i{)}^T\varphi ({𝐱}_j)$. For the mapping $\varphi (𝐱)$ above, show that $K({𝐱}_i,{𝐱}_j)=({𝐱}_i^T{𝐱}_j{)}^2$. This is the quadratic (polynomial degree 2) kernel.
4. Intuition: Explain in simple terms how the kernel trick allows SVMs to find non-linear boundaries in the original space. Why is explicitly computing $\varphi (𝐱)$ often computationally expensive or even intractable for very high-dimensional spaces?
5. Verification: You can compute $\varphi ({𝐱}_A{)}^T\varphi ({𝐱}_B)$ directly and compare it to $({𝐱}_A^T{𝐱}_B{)}^2$ for the points you picked in step 2 to confirm your derivation of the kernel function.