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.

Derive RBF as an infinite-dimensional map: expand $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!}$ to expose the features.

Mercer's theorem: what makes a valid kernel (symmetric PSD)? Which functions are invalid? Prove sums/products of kernels stay kernels.

Derive the explicit feature dimension of the polynomial kernel $K = (x^Tz + c)^d$ (e.g. $\binom{n+d}{d}$) and how the kernel avoids building it.

RBF tuning: bias-variance behavior as $\gamma$ (or $\sigma$) grows/shrinks, interplay with $C$; which direction to move each under under/overfitting?

Which algorithms are kernelizable (need only inner products/norms) and which are not? Linear vs RBF when $d$ is large or $n$ is small?