12.4 Kernel Methods and Basis Functions

Introduction

Kernel methods provide an elegant framework for non-linear learning. They rely on two key ideas: basis function expansion and the kernel trick. This chapter explores their theoretical foundations and connections to reproducing kernel Hilbert spaces (RKHS).

1. Basis Function Expansion

1.1 Linear Models in Feature Space

Transform input $\mathbf{x} \in \mathbb{R}^d$ via a feature map:

$$\phi: \mathbb{R}^d \to \mathbb{R}^D, \quad \mathbf{x} \mapsto \phi(\mathbf{x})$$

Learn a linear model in the transformed space:

$$f(\mathbf{x}) = \mathbf{w}^T \phi(\mathbf{x}) + b = \sum_{j=1}^{D} w_j \phi_j(\mathbf{x}) + b$$

This is non-linear in the original space but linear in the feature space.

1.2 Common Basis Functions

Polynomial basis:

For $\mathbf{x} = [x_1, x_2]$, degree 2:

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

Radial basis functions (RBF):

$$\phi_j(\mathbf{x}) = \exp\left(-\frac{\|\mathbf{x} - \boldsymbol{\mu}_j\|^2}{2\sigma^2}\right)$$

where $\{\boldsymbol{\mu}_j\}$ are centers.

Fourier basis:

$$\phi_j(\mathbf{x}) = \sin(\omega_j^T \mathbf{x}), \quad \phi_{j+D/2}(\mathbf{x}) = \cos(\omega_j^T \mathbf{x})$$

Sigmoid basis:

$$\phi_j(\mathbf{x}) = \sigma(\mathbf{a}_j^T \mathbf{x} + b_j), \quad \sigma(z) = \frac{1}{1+e^{-z}}$$

2. From Features to Kernels

2.1 The Kernel Trick

When $D$ is very large or infinite, computing $\phi(\mathbf{x})$ explicitly is intractable. The kernel trick avoids this:

Define a kernel function:

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

Computing inner products in feature space only requires evaluating $k(\mathbf{x}, \mathbf{z})$!

2.2 Example: Polynomial Kernel

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

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

This corresponds to:

$$\phi(\mathbf{x}) = [1, \sqrt{2}x_1, \sqrt{2}x_2, x_1^2, \sqrt{2}x_1x_2, x_2^2]^T$$

Verify: $\phi(\mathbf{x})^T \phi(\mathbf{z}) = (\mathbf{x}^T\mathbf{z} + 1)^2$

2.3 Example: RBF Kernel

The RBF (Gaussian) kernel:

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

corresponds to an infinite-dimensional feature space! The Taylor expansion shows:

$$k(\mathbf{x}, \mathbf{z}) = \sum_{n=0}^{\infty} \frac{1}{n!} \left(\frac{\mathbf{x}^T\mathbf{z}}{\sigma^2}\right)^n \exp\left(-\frac{\|\mathbf{x}\|^2 + \|\mathbf{z}\|^2}{2\sigma^2}\right)$$

3. Positive Definite Kernels

3.1 Definition

A function $k: \mathcal{X} \times \mathcal{X} \to \mathbb{R}$ is a positive definite kernel if:

1. Symmetry: $k(\mathbf{x}, \mathbf{z}) = k(\mathbf{z}, \mathbf{x})$
2. Positive definiteness: For any $n$ points $\{\mathbf{x}_i\}_{i=1}^n$ and coefficients $\{c_i\}_{i=1}^n$: $$\sum_{i=1}^{n}\sum_{j=1}^{n} c_i c_j k(\mathbf{x}_i, \mathbf{x}_j) \geq 0$$

Equivalently, the Gram matrix $\mathbf{K}$ with $K_{ij} = k(\mathbf{x}_i, \mathbf{x}_j)$ is positive semidefinite.

3.2 Mercer's Theorem

For a continuous positive definite kernel $k$ on a compact domain, there exists a feature map $\phi$ such that:

$$k(\mathbf{x}, \mathbf{z}) = \sum_{i=1}^{\infty} \lambda_i \phi_i(\mathbf{x}) \phi_i(\mathbf{z})$$

where $\lambda_i > 0$ are eigenvalues and $\{\phi_i\}$ are eigenfunctions of the integral operator.

4. Kernel Construction

4.1 Closure Properties

Valid kernels can be combined to create new kernels:

• Addition: If $k_1$ and $k_2$ are kernels, so is $k_1 + k_2$
• Multiplication: $k_1 \cdot k_2$ is a kernel
• Scalar multiplication: $c \cdot k$ is a kernel for $c > 0$
• Function composition: $k(\phi(\mathbf{x}), \phi(\mathbf{z}))$ is a kernel if $k$ is a kernel and $\phi$ is any function
• Exponential: $\exp(k(\mathbf{x}, \mathbf{z}))$ is a kernel

4.2 Examples of Compound Kernels

Sum of RBF with different scales:

$$k(\mathbf{x}, \mathbf{z}) = \sum_{i=1}^{m} w_i \exp\left(-\frac{\|\mathbf{x} - \mathbf{z}\|^2}{2\sigma_i^2}\right)$$

Product of linear and RBF:

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

5. Reproducing Kernel Hilbert Space (RKHS)

5.1 Hilbert Space Basics

A Hilbert space $\mathcal{H}$ is a complete vector space with an inner product $\langle \cdot, \cdot \rangle_{\mathcal{H}}$.

For functions, consider $\mathcal{H} = \{f: \mathcal{X} \to \mathbb{R}\}$ with appropriate structure.

5.2 Reproducing Property

A Hilbert space $\mathcal{H}$ of functions on $\mathcal{X}$ is an RKHS if there exists a kernel $k$ such that:

1. For all $\mathbf{x} \in \mathcal{X}$, $k(\mathbf{x}, \cdot) \in \mathcal{H}$
2. Reproducing property: For all $f \in \mathcal{H}$ and $\mathbf{x} \in \mathcal{X}$: $$\langle f, k(\mathbf{x}, \cdot) \rangle_{\mathcal{H}} = f(\mathbf{x})$$

This means function evaluation is an inner product!

5.3 Moore-Aronszajn Theorem

There is a one-to-one correspondence between positive definite kernels and RKHSs.

For any positive definite kernel $k$, there exists a unique RKHS $\mathcal{H}_k$ with $k$ as its reproducing kernel.

5.4 Functions in RKHS

Any function $f \in \mathcal{H}_k$ can be represented as:

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

for some coefficients $\{\alpha_i\}$ and points $\{\mathbf{x}_i\}$.

6. The Representer Theorem

6.1 General Statement

Consider the optimization problem:

$$\min_{f \in \mathcal{H}} \left[\sum_{i=1}^{n} L(y_i, f(\mathbf{x}_i)) + \lambda \|f\|_{\mathcal{H}}^2\right]$$

where $L$ is a loss function and $\lambda > 0$.

Representer Theorem: The solution has the form:

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

This justifies working with kernels: optimal solutions lie in the span of kernel functions at training points!

6.2 Implications

• The solution depends only on kernel evaluations, not explicit features
• Problem reduces to finding $n$ coefficients $\{\alpha_i\}$
• Applies to many learning algorithms: SVM, kernel ridge regression, etc.

7. Kernel PCA

Principal Component Analysis (PCA) finds directions of maximum variance. Kernel PCA extends this to non-linear settings.

7.1 Algorithm

1. Compute centered kernel matrix: $\tilde{\mathbf{K}} = \mathbf{K} - \mathbf{1}_n\mathbf{K} - \mathbf{K}\mathbf{1}_n + \mathbf{1}_n\mathbf{K}\mathbf{1}_n$
2. Eigenvalue decomposition: $\tilde{\mathbf{K}} = \mathbf{V}\boldsymbol{\Lambda}\mathbf{V}^T$
3. Principal components are columns of $\mathbf{V}$
4. Project new point $\mathbf{x}$: $z_j = \sum_{i=1}^{n} v_{ij} k(\mathbf{x}_i, \mathbf{x})$

8. Connection to Neural Networks

8.1 Neural Tangent Kernel (NTK)

An infinite-width neural network with random initialization behaves as a Gaussian process with a specific kernel—the Neural Tangent Kernel.

For a network $f(\mathbf{x}; \boldsymbol{\theta})$, the NTK is:

$$k_{\text{NTK}}(\mathbf{x}, \mathbf{z}) = \left\langle \frac{\partial f(\mathbf{x}; \boldsymbol{\theta})}{\partial \boldsymbol{\theta}}, \frac{\partial f(\mathbf{z}; \boldsymbol{\theta})}{\partial \boldsymbol{\theta}} \right\rangle$$

This bridges kernel methods and deep learning!

8.2 Kernel Methods in Deep Learning

• Attention mechanism: Computes weighted sums using similarity kernels
• Graph neural networks: Use graph kernels for structured data
• Metric learning: Learn kernels/distances from data
• Kernel approximation: Random features approximate kernels for scalability

9. Connection to LLMs

Kernel methods relate to modern language models in several ways:

• Attention as kernel: Transformer attention $\text{softmax}(\mathbf{Q}\mathbf{K}^T)$ computes kernel similarities
• Contextual embeddings: Token representations form implicit kernel spaces
• Infinite-width limit: Transformers at infinite width behave as GPs with specific kernels
• RKHS regularization: Weight decay in neural nets corresponds to RKHS norm penalties
• Kernel approximation: Efficient attention mechanisms (Linformer, Performer) use random features
• Transfer learning: Pre-trained models provide learned kernel representations
• Meta-learning: Few-shot learning similar to kernel methods on small data

10. Practical Considerations

Advantages

• Mathematically principled with strong theory
• Work with arbitrary data types (graphs, strings, sets)
• No local minima (convex optimization)
• Uncertainty quantification (GPs)
• Interpretable via kernel inspections

Challenges

• Scalability: $O(n^3)$ training, $O(n^2)$ memory
• Kernel selection is critical and dataset-dependent
• Limited to specific inductive biases encoded in kernel
• Not end-to-end learnable like neural networks

Key Takeaways

• Basis functions transform inputs to enable non-linear learning with linear models
• Kernels compute inner products in feature space without explicit transformation
• Positive definite kernels correspond to feature spaces via Mercer's theorem
• RKHS provides rigorous functional analytic framework for kernel methods
• Representer theorem shows optimal solutions lie in span of kernel functions
• Kernels can be constructed and composed using closure properties
• Neural Tangent Kernel connects kernel methods to deep learning
• Attention mechanisms in Transformers are kernel-based computations