The Kernel Trick

From Inner Products to Kernels

The starting point is any learning algorithm whose decision rule depends on the training data only through inner products. Consider a linear classifier in an explicit feature space φ(x) ∈ ℝᵈ. The decision function takes the form:

Explanation: The model scores a new point x by projecting its feature representation φ(x) onto a weight vector w — this is the standard linear model in the lifted feature space. By the representer theorem, the optimal weight vector w can always be written as a linear combination of the mapped training points:

Explanation: The solution weight vector lives in the span of the training features, meaning we never need to find w explicitly — only the coefficients αᵢ. Substituting [2] into [1]:

Explanation: Every inner product ⟨φ(xᵢ), φ(x)⟩ is replaced by a single kernel evaluation k(xᵢ, x), eliminating the need to compute φ explicitly. Here, k : 𝒳 × 𝒳 → ℝ is a kernel function. For this substitution to be mathematically valid, k must be a positive semi-definite (PSD) kernel — equivalently, by Mercer's theorem, it must correspond to an inner product in some Hilbert space (the RKHS). The kernel matrix K with entries Kᵢⱼ = k(xᵢ, xⱼ) must satisfy:

Explanation: Positive semi-definiteness of the Gram matrix K guarantees that k corresponds to a genuine inner product somewhere, making the geometry consistent and the optimization convex.

The SVM Dual and Kernelization

The SVM hard-margin primal is a QP in w. Its Lagrangian dual is:

Explanation: The dual depends on data only through the n×n kernel matrix K — once K is computed, the original input dimensionality is irrelevant to the optimizer. subject to αᵢ ≥ 0 and Σᵢ αᵢ yᵢ = 0, where yᵢ ∈ {−1, +1} are class labels. The entire optimization lives in α-space (dimension n, the number of training points), not in the feature space dimension d which may be infinite.

Common Kernel Functions

PyTorch Implementation

```python import torch import torch.nn.functional as F def rbf_kernel(X: torch.Tensor, Y: torch.Tensor, gamma: float = 1.0) -> torch.Tensor: """ Compute the RBF (Gaussian) kernel matrix between rows of X and Y. K[i,j] = exp(-gamma * ||X[i] - Y[j]||^2) Args: X: (n, d) tensor Y: (m, d) tensor gamma: bandwidth parameter Returns: K: (n, m) kernel matrix """

# ||x - y||^2 = ||x||^2 + ||y||^2 - 2 x^T y X_sq = (X 2).sum(dim=1, keepdim=True) # (n, 1) Y_sq = (Y 2).sum(dim=1, keepdim=True) # (m, 1) cross = X @ Y.T # (n, m) dists_sq = X_sq + Y_sq.T - 2 cross # (n, m) via broadcasting return torch.exp(-gamma dists_sq)

def polynomial_kernel(X: torch.Tensor, Y: torch.Tensor, degree: int = 3, c: float = 1.0) -> torch.Tensor: """Polynomial kernel: k(x,y) = (x^T y + c)^degree""" return (X @ Y.T + c) ** degree

# --- Kernel SVM prediction (inference only, alphas from sklearn) --- def kernel_svm_predict(X_train: torch.Tensor, X_test: torch.Tensor, alphas: torch.Tensor, y_train: torch.Tensor, bias: float, gamma: float = 0.5) -> torch.Tensor: """ Predict using a kernelized SVM. f(x) = sum_i alpha_i y_i k(x_i, x) + b Only support vectors (alpha_i > 0) contribute. """ K = rbf_kernel(X_train, X_test, gamma=gamma) # (n_train, n_test) scores = (alphas y_train).unsqueeze(1) K # broadcast (n_train, n_test) return scores.sum(dim=0) + bias # (n_test,)

# --- Verify RBF kernel is PSD via eigenvalues --- def check_psd(K: torch.Tensor, tol: float = 1e-6) -> bool: eigenvalues = torch.linalg.eigvalsh(K) return bool((eigenvalues >= -tol).all())

# Example usage torch.manual_seed(42) X = torch.randn(50, 4) K = rbf_kernel(X, X, gamma=0.5) print(f"Kernel matrix shape: {K.shape}") # (50, 50) print(f"Is PSD: {check_psd(K)}") # True print(f"Diagonal (self-similarity): {K.diag()[:5]}") # all 1.0 for RBF ```

Support Vector Machines · Gaussian Processes · Kernel PCA · Reproducing Kernel Hilbert Spaces · Random Fourier Features · Representer Theorem · Radial Basis Functions