Kernel Trick & RBF

SVM's dual optimization and prediction only depend on sample inner products $x_i^Tx_j$. The kernel trick computes inner products in a high- (even infinite-) dimensional feature space directly via $K(x, z) = \langle\phi(x), \phi(z)\rangle$ without ever constructing $\phi$ — as long as $K$ is a Mercer kernel (symmetric PSD). Common kernels: linear $K = x^Tz$, polynomial $K = (x^Tz + c)^d$, and the RBF Gaussian kernel $K(x, z) = \exp(-\gamma\Vert x - z\Vert^2)$ with bandwidth $\gamma = \frac{1}{2\sigma^2}$: larger $\gamma$ gives more complex boundaries (overfitting), smaller gives smoother ones (underfitting). The kernelized decision function is $f(x) = \sum_{i \in SV} \alpha_i y_i K(x_i, x) + b$ at $O(n_{SV} \cdot d)$ cost, independent of the feature-map dimension.

the weapon of choice for non-linearly separable data; interviews probe $\gamma$/$\sigma$ tuning direction, kernel-to-feature-map correspondence (polynomial kernel → $\binom{n+d}{d}$ dims, RBF → infinite-dim RKHS), and why kernel methods scale with data size.

explicit feature maps explode in dimension (quadratic polynomial map is $O(d^2)$-dimensional) and can be infinite (RBF expands via Taylor as $e^{-\gamma\Vert x-z\Vert^2} = e^{-\gamma\Vert x\Vert^2} e^{-\gamma\Vert z\Vert^2} \sum_k \frac{(2\gamma x \cdot z)^k}{k!}$, an infinite-dimensional feature space); the kernel computes the same inner product in $O(d)$ on the raw inputs, giving 'linear SVM + kernel' non-linear power — training needs only the Gram matrix $K_{ij} = K(x_i, x_j)$, dual and prediction read only inner products/kernel values, decoupled from feature dimension; valid kernels are closed under sums/scales/products (Mercer), so domain kernels (e.g. string kernels for text) can be designed freely.

Test Your Knowledge: Practice Questions for "Kernel Trick & RBF"

Single choice pitfall questions with instant feedback and mistake tracking.