11.4 Support Vector Machines (SVM) II: Non-linear SVM and Kernels

Introduction

Many real-world classification problems are not linearly separable in the original feature space. The kernel trick allows SVMs to efficiently learn non-linear decision boundaries by implicitly mapping data to high-dimensional feature spaces without explicitly computing the transformation.

1. The Feature Mapping Idea

Instead of working with the original features $\mathbf{x} \in \mathbb{R}^d$, we map them to a higher-dimensional space using a transformation $\phi: \mathbb{R}^d \to \mathbb{R}^D$ where $D \gg d$.

Example: Quadratic Features

For $\mathbf{x} = (x_1, x_2)$, define:

$$\phi(\mathbf{x}) = (1, x_1, x_2, x_1^2, x_2^2, x_1 x_2)$$

A linear classifier in this space:

$$w_0 + w_1 x_1 + w_2 x_2 + w_3 x_1^2 + w_4 x_2^2 + w_5 x_1 x_2 = 0$$

This represents a conic section (ellipse, parabola, or hyperbola) in the original space.

2. The Kernel Trick

Recall that the SVM dual formulation depends only on inner products between data points:

$$\max_{\boldsymbol{\alpha}} \sum_{i=1}^{n} \alpha_i - \frac{1}{2}\sum_{i,j} \alpha_i \alpha_j y_i y_j \langle \mathbf{x}_i, \mathbf{x}_j \rangle$$

With feature mapping $\phi$, this becomes:

$$\max_{\boldsymbol{\alpha}} \sum_{i=1}^{n} \alpha_i - \frac{1}{2}\sum_{i,j} \alpha_i \alpha_j y_i y_j \langle \phi(\mathbf{x}_i), \phi(\mathbf{x}_j) \rangle$$

Kernel Function

A kernel function $k(\mathbf{x}_i, \mathbf{x}_j)$ computes the inner product in feature space:

$$k(\mathbf{x}_i, \mathbf{x}_j) = \langle \phi(\mathbf{x}_i), \phi(\mathbf{x}_j) \rangle$$

Key insight: We can compute $k(\mathbf{x}_i, \mathbf{x}_j)$ directly without explicitly computing $\phi(\mathbf{x})$. This allows us to work in very high (even infinite) dimensional spaces efficiently.

Example: Polynomial Kernel

For $\mathbf{x}, \mathbf{z} \in \mathbb{R}^2$, consider:

$$k(\mathbf{x}, \mathbf{z}) = (\mathbf{x}^T \mathbf{z})^2 = (x_1 z_1 + x_2 z_2)^2$$

Expanding:

$$k(\mathbf{x}, \mathbf{z}) = x_1^2 z_1^2 + 2x_1 x_2 z_1 z_2 + x_2^2 z_2^2$$

This equals $\langle \phi(\mathbf{x}), \phi(\mathbf{z}) \rangle$ where $\phi(\mathbf{x}) = (x_1^2, \sqrt{2}x_1 x_2, x_2^2)$.

Computing $k(\mathbf{x}, \mathbf{z})$ takes $O(d)$ time, while computing $\phi(\mathbf{x})$ and then the inner product takes $O(d^2)$ time.

3. Common Kernel Functions

3.1 Linear Kernel

$$k(\mathbf{x}, \mathbf{z}) = \mathbf{x}^T \mathbf{z}$$

This is the standard linear SVM (no transformation).

3.2 Polynomial Kernel

$$k(\mathbf{x}, \mathbf{z}) = (\mathbf{x}^T \mathbf{z} + c)^d$$

Parameters:

• $d$: degree of the polynomial
• $c \geq 0$: constant term (often 1)

The feature space has dimension $\binom{d + D - 1}{d}$ where $D$ is the original dimension.

3.3 Radial Basis Function (RBF) / Gaussian Kernel

$$k(\mathbf{x}, \mathbf{z}) = \exp\left(-\frac{\|\mathbf{x} - \mathbf{z}\|^2}{2\sigma^2}\right) = \exp(-\gamma \|\mathbf{x} - \mathbf{z}\|^2)$$

where $\gamma = \frac{1}{2\sigma^2}$ is the bandwidth parameter.

Properties:

• Maps to an infinite-dimensional space
• $k(\mathbf{x}, \mathbf{x}) = 1$ (normalized)
• $k(\mathbf{x}, \mathbf{z}) \to 0$ as $\|\mathbf{x} - \mathbf{z}\| \to \infty$
• Small $\gamma$: smooth, simple decision boundary
• Large $\gamma$: complex, wiggly decision boundary (risk of overfitting)

3.4 Sigmoid Kernel

$$k(\mathbf{x}, \mathbf{z}) = \tanh(\alpha \mathbf{x}^T \mathbf{z} + c)$$

Inspired by neural networks. Not positive semi-definite for all parameter values.

4. Decision Function with Kernels

The optimal decision function is:

$$f(\mathbf{x}) = \text{sign}\left(\sum_{i \in SV} \alpha_i^* y_i k(\mathbf{x}_i, \mathbf{x}) + b^*\right)$$

Prediction requires:

• Computing kernel values $k(\mathbf{x}_i, \mathbf{x})$ for all support vectors
• Weighted sum of these values
• Time complexity: $O(n_{SV} \cdot d)$ where $n_{SV}$ is the number of support vectors

5. Valid Kernels (Mercer's Theorem)

Not every function $k(\mathbf{x}, \mathbf{z})$ is a valid kernel. A function is a valid kernel if and only if it is positive semi-definite.

Mercer's Condition

A symmetric function $k: \mathcal{X} \times \mathcal{X} \to \mathbb{R}$ is a valid kernel if for any finite set of points $\{\mathbf{x}_1, \ldots, \mathbf{x}_n\}$, the kernel matrix (Gram matrix):

$$K_{ij} = k(\mathbf{x}_i, \mathbf{x}_j)$$

is positive semi-definite (all eigenvalues $\geq 0$).

Constructing New Kernels

If $k_1$ and $k_2$ are valid kernels, then so are:

• $k(\mathbf{x}, \mathbf{z}) = k_1(\mathbf{x}, \mathbf{z}) + k_2(\mathbf{x}, \mathbf{z})$ (sum)
• $k(\mathbf{x}, \mathbf{z}) = a \cdot k_1(\mathbf{x}, \mathbf{z})$ for $a > 0$ (positive scaling)
• $k(\mathbf{x}, \mathbf{z}) = k_1(\mathbf{x}, \mathbf{z}) \cdot k_2(\mathbf{x}, \mathbf{z})$ (product)
• $k(\mathbf{x}, \mathbf{z}) = f(\mathbf{x}) \cdot f(\mathbf{z})$ for any function $f$
• $k(\mathbf{x}, \mathbf{z}) = \mathbf{x}^T A \mathbf{z}$ for any positive semi-definite matrix $A$

6. Choosing the Right Kernel

Guidelines

• Linear kernel: High-dimensional data, many features, linear relationships expected
• Polynomial kernel: Features have natural polynomial relationships, image data
• RBF kernel: Default choice, works well in many cases, good for non-linear data
• Custom kernels: Domain-specific structure (strings, graphs, biological sequences)

Hyperparameter Selection

Parameters like $C$, $\gamma$, and polynomial degree $d$ should be selected using cross-validation:

1. Create a grid of parameter values
2. For each combination, train SVM and evaluate on validation set
3. Select parameters with best validation performance
4. Retrain on full training set with selected parameters

7. Kernel Methods Beyond SVM

Kernel Ridge Regression

Ridge regression with kernels:

$$f(\mathbf{x}) = \sum_{i=1}^{n} \alpha_i k(\mathbf{x}_i, \mathbf{x})$$

where $\boldsymbol{\alpha} = (K + \lambda I)^{-1} \mathbf{y}$ and $K$ is the kernel matrix.

Kernel PCA

Principal component analysis in feature space for non-linear dimensionality reduction.

Kernel K-means

Clustering in feature space without explicitly computing $\phi(\mathbf{x})$.

8. Computational Considerations

Training Complexity

Computing the kernel matrix requires $O(n^2)$ kernel evaluations. Each kernel evaluation for RBF or polynomial kernels is $O(d)$. Total: $O(n^2 d)$ just for the kernel matrix.

Solving the dual QP: $O(n^2)$ to $O(n^3)$ depending on the method.

Prediction Complexity

Each prediction requires computing $k(\mathbf{x}_i, \mathbf{x})$ for all $n_{SV}$ support vectors: $O(n_{SV} \cdot d)$.

For large-scale problems, $n_{SV}$ can be a significant fraction of $n$, making prediction slow.

Approximation Methods

• Random Fourier Features: Approximate kernel with explicit low-dimensional features
• Nyström Method: Approximate kernel matrix using subset of data points
• Core Vector Machines: Use minimum enclosing ball to reduce support vectors

9. Kernel Design for Structured Data

String Kernels

For text or biological sequences, count common subsequences:

$$k(s, t) = \sum_{u \in \Sigma^*} w(u) \cdot \#(u \text{ in } s) \cdot \#(u \text{ in } t)$$

where $w(u)$ weights subsequence $u$.

Graph Kernels

For molecular or social network data:

• Random walk kernel: count common walks
• Subtree kernel: count common subtrees
• Weisfeiler-Lehman kernel: based on graph isomorphism test

10. Connection to LLMs

Kernel methods influence modern language models:

• Attention as kernel: Self-attention $\text{softmax}(\mathbf{Q}\mathbf{K}^T)$ computes similarity (kernel-like) between query and key vectors
• Embedding spaces: Learned embeddings create implicit feature spaces similar to $\phi(\mathbf{x})$
• Positional encodings: RBF-like kernels used in position representations
• Kernel approximations: Efficient attention mechanisms (Linformer, Performer) use kernel approximations
• Infinite width networks: Neural networks in the infinite width limit correspond to kernel methods (Neural Tangent Kernel)
• Transfer learning: Pre-trained models act as learned feature extractors, similar to kernel feature maps

Key Takeaways

• The kernel trick allows SVMs to learn non-linear decision boundaries efficiently
• Kernels compute inner products in high-dimensional spaces without explicit mapping
• RBF kernel is the most commonly used, mapping to infinite-dimensional space
• Valid kernels must be positive semi-definite (Mercer's condition)
• Kernel choice and hyperparameters significantly affect performance
• Decision function is a weighted sum of kernels evaluated at support vectors
• Kernels can be designed for structured data (strings, graphs, etc.)
• Kernel methods connect to modern neural networks through attention and infinite width limits