The Kernel Trick, Mercer's Theorem & RBF Kernels
“Inner products in Hilbert spaces, Polynomial kernels, Gaussian RBF, and Mercer positive semi-definiteness.”
1.The Power of Mercer Kernels in High Dimensions
§ 4.1.When data is not linearly separable in the original input space R^d (e.g. concentric circles or the XOR problem), we map samples into a higher-dimensional feature space R^D via non-linear mapping phi(x).
Why Explicit Mapping Fails: Computing phi(x) explicitly in 10,000 dimensions is computationally intractable in time and memory.
The Kernel Miracle: Notice that in the SVM dual formulation, features appear ONLY through the dot product x_i^T x_j. By substituting K(x_i, x_j) = phi(x_i)^T phi(x_j), we perform optimal maximum margin separation in an infinite-dimensional space while computing only simple scalar distances in original O(d) time!
2. Worked Practice Problem: Polynomial Kernel Explicit Mapping Verification
Remember the sqrt(2) scaling factor on cross-terms when deriving the explicit feature vector phi(x).
Problem: For 2D vectors x = [x1, x2]^T and z = [z1, z2]^T, show that the kernel K(x, z) = (x^T z)^2 corresponds to an explicit 3D feature mapping phi(x).
Step 1: Expand the algebraic dot product:
x^T z = x1 z1 + x2 z2
Step 2: Square the sum:
(x^T z)^2 = (x1 z1 + x2 z2)^2 = (x1 z1)^2 + 2 (x1 z1)(x2 z2) + (x2 z2)^2
= (x1^2) (z1^2) + [ sqrt(2) x1 x2 ] [ sqrt(2) z1 z2 ] + (x2^2) (z2^2)
Step 3: Define explicit mapping phi(x):
phi(x) = [ x1^2, sqrt(2) x1 x2, x2^2 ]^T
Step 4: Verify dot product:
phi(x)^T phi(z) = x1^2 z1^2 + 2 x1 x2 z1 z2 + x2^2 z2^2 = (x^T z)^2 = K(x, z).
Conclusion: K(x, z) maps 2D coordinates into a 3D parabolic feature space where quadratic boundaries become linear hyperplanes.
Primary Academic References & Exam Sources
Every concept in Notes From a B.Tech Brain is synthesized from authoritative academic texts, seminal peer-reviewed research, verified exam archives, and renowned university lectures.