核方法

核方法（Kernel Methods）是一类通过核技巧将数据隐式映射到高维特征空间的算法族，是经典机器学习中理论最优美的分支之一。支持向量机（SVM）是核方法最成功的代表，而高斯过程（GP）则将核方法与贝叶斯推断完美结合。

学习路线： 线性不可分问题 → 特征映射 → 核技巧 → SVM对偶问题 → 核函数理论 → 高斯过程 → 与神经网络的联系

派系视角：核方法是 Domingos 五学派中类比派 (Analogizers) 的核心 —— 核函数即隐式相似度度量。从派系视角看 k-NN / SVM / 度量学习 / 推荐系统的统一脉络，见 The Master Algorithm — 类比派、最近邻与核方法。

核方法概述

为什么需要核方法

许多现实问题中，数据在原始输入空间中是线性不可分的。一个直觉的思路是将数据映射到更高维的空间，在高维空间中寻找线性决策边界：

\[ \mathbf{x} \in \mathbb{R}^d \xrightarrow{\phi} \phi(\mathbf{x}) \in \mathbb{R}^D, \quad D \gg d \]

但显式计算高维映射 \(\phi(\mathbf{x})\) 的代价可能极其高昂（\(D\) 甚至可以是无穷维）。核技巧的核心洞察是：许多算法只依赖数据点之间的内积 \(\langle \phi(\mathbf{x}_i), \phi(\mathbf{x}_j) \rangle\)，而非映射本身。如果存在一个函数 \(k\) 满足：

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

那么我们可以直接在原始空间计算核函数，而无需显式构造 \(\phi\)。这就是核技巧（Kernel Trick）。

SVM 深入

线性 SVM：最大间隔分类器

给定线性可分的训练数据 \(\{(\mathbf{x}_i, y_i)\}_{i=1}^{N}\)（\(y_i \in \{-1, +1\}\)），SVM 寻找使几何间隔最大的超平面：

\[ \max_{\mathbf{w}, b} \; \frac{2}{\|\mathbf{w}\|} \quad \text{s.t.} \quad y_i(\mathbf{w}^T \mathbf{x}_i + b) \geq 1, \; \forall i \]

等价地，转化为最小化问题（原始问题）：

\[ \min_{\mathbf{w}, b} \; \frac{1}{2}\|\mathbf{w}\|^2 \quad \text{s.t.} \quad y_i(\mathbf{w}^T \mathbf{x}_i + b) \geq 1, \; \forall i \]

对偶问题

引入拉格朗日乘子 \(\alpha_i \geq 0\)，构建拉格朗日函数：

\[ L(\mathbf{w}, b, \boldsymbol{\alpha}) = \frac{1}{2}\|\mathbf{w}\|^2 - \sum_{i=1}^{N} \alpha_i \left[ y_i(\mathbf{w}^T \mathbf{x}_i + b) - 1 \right] \]

对 \(\mathbf{w}\) 和 \(b\) 求偏导并令其为零：

\[ \mathbf{w} = \sum_{i=1}^{N} \alpha_i y_i \mathbf{x}_i, \quad \sum_{i=1}^{N} \alpha_i y_i = 0 \]

代入得到对偶问题：

\[ \max_{\boldsymbol{\alpha}} \; \sum_{i=1}^{N} \alpha_i - \frac{1}{2}\sum_{i,j} \alpha_i \alpha_j y_i y_j \mathbf{x}_i^T \mathbf{x}_j \quad \text{s.t.} \quad \alpha_i \geq 0, \; \sum_i \alpha_i y_i = 0 \]

注意对偶问题中只涉及数据点之间的内积 \(\mathbf{x}_i^T \mathbf{x}_j\)，这正是核技巧的切入点。

KKT 条件

KKT（Karush-Kuhn-Tucker）条件是原始问题与对偶问题的最优性条件：

原始可行性：\(y_i(\mathbf{w}^T \mathbf{x}_i + b) \geq 1\)
对偶可行性：\(\alpha_i \geq 0\)
互补松弛：\(\alpha_i [y_i(\mathbf{w}^T \mathbf{x}_i + b) - 1] = 0\)

互补松弛条件意味着：要么 \(\alpha_i = 0\)（该点不是支持向量），要么 \(y_i(\mathbf{w}^T \mathbf{x}_i + b) = 1\)（该点恰好在间隔边界上，是支持向量）。

软间隔 SVM

对于非线性可分数据，引入松弛变量 \(\xi_i \geq 0\) 和惩罚参数 \(C > 0\)：

\[ \min_{\mathbf{w}, b, \boldsymbol{\xi}} \; \frac{1}{2}\|\mathbf{w}\|^2 + C\sum_{i=1}^{N} \xi_i \quad \text{s.t.} \quad y_i(\mathbf{w}^T \mathbf{x}_i + b) \geq 1 - \xi_i, \; \xi_i \geq 0 \]

对偶问题变为：约束 \(0 \leq \alpha_i \leq C\)（上界由 \(C\) 控制）。

核技巧

核函数的定义

一个函数 \(k: \mathcal{X} \times \mathcal{X} \to \mathbb{R}\) 称为核函数，如果存在特征映射 \(\phi: \mathcal{X} \to \mathcal{H}\) 使得：

\[ k(\mathbf{x}, \mathbf{x}') = \langle \phi(\mathbf{x}), \phi(\mathbf{x}') \rangle_{\mathcal{H}} \]

核化的 SVM 对偶问题只需将内积替换为核函数：

\[ \max_{\boldsymbol{\alpha}} \; \sum_{i} \alpha_i - \frac{1}{2}\sum_{i,j} \alpha_i \alpha_j y_i y_j \, k(\mathbf{x}_i, \mathbf{x}_j) \]

Mercer 定理

Mercer 定理给出了一个函数是有效核函数的充要条件：\(k(\mathbf{x}, \mathbf{x}')\) 是有效核函数，当且仅当对于任意有限数据集 \(\{\mathbf{x}_1, \dots, \mathbf{x}_N\}\)，核矩阵 \(K\) 是半正定的：

\[ K_{ij} = k(\mathbf{x}_i, \mathbf{x}_j), \quad K \succeq 0 \]

这意味着核矩阵的所有特征值非负。

常见核函数

核函数	表达式	特征空间维度	特点
线性核	\(k(\mathbf{x}, \mathbf{x}') = \mathbf{x}^T \mathbf{x}'\)	\(d\)	等价于线性 SVM
多项式核	\(k(\mathbf{x}, \mathbf{x}') = (\mathbf{x}^T \mathbf{x}' + c)^p\)	\(\binom{d+p}{p}\)	捕捉特征交互
RBF（高斯）核	\(k(\mathbf{x}, \mathbf{x}') = \exp\left(-\frac{\\|\mathbf{x}-\mathbf{x}'\\|^2}{2\sigma^2}\right)\)	\(\infty\)	最常用，局部相似性
Sigmoid 核	\(k(\mathbf{x}, \mathbf{x}') = \tanh(\kappa \mathbf{x}^T \mathbf{x}' + c)\)	--	类似神经网络

RBF 核的直觉：\(\sigma\) 控制"影响半径"。\(\sigma\) 小 → 每个支持向量只影响附近区域（容易过拟合）；\(\sigma\) 大 → 决策边界光滑（可能欠拟合）。

RKHS（再生核希尔伯特空间）

直觉解释

再生核希尔伯特空间（Reproducing Kernel Hilbert Space, RKHS）是核方法的理论基础。直觉上理解：

每个核函数 \(k\) 都唯一对应一个函数空间 \(\mathcal{H}_k\)（即 RKHS）
在这个空间中，函数的"内积"可以通过核函数来计算
再生性质：\(f(\mathbf{x}) = \langle f, k(\mathbf{x}, \cdot) \rangle_{\mathcal{H}_k}\)，即用核函数"探针"来求值

表示定理：在 RKHS 中，正则化经验风险最小化的解一定是核函数的线性组合：

\[ f^*(\mathbf{x}) = \sum_{i=1}^{N} \alpha_i \, k(\mathbf{x}_i, \mathbf{x}) \]

这意味着无论 RKHS 多么高维（甚至无穷维），最优解仍然可以用 \(N\) 个系数来表示。

高斯过程

定义

高斯过程（Gaussian Process, GP）是定义在函数空间上的概率分布。一个 GP 完全由均值函数 \(m(\mathbf{x})\) 和核函数（协方差函数）\(k(\mathbf{x}, \mathbf{x}')\) 决定：

\[ f(\mathbf{x}) \sim \mathcal{GP}\left(m(\mathbf{x}), k(\mathbf{x}, \mathbf{x}')\right) \]

对于任意有限个输入点 \(\mathbf{x}_1, \dots, \mathbf{x}_N\)，函数值 \(\mathbf{f} = [f(\mathbf{x}_1), \dots, f(\mathbf{x}_N)]^T\) 服从多元高斯分布。

GP 回归

给定训练数据 \((\mathbf{X}, \mathbf{y})\)（其中 \(y_i = f(\mathbf{x}_i) + \epsilon\)，\(\epsilon \sim \mathcal{N}(0, \sigma_n^2)\)），对新输入 \(\mathbf{x}_*\) 的预测分布为：

\[ f_* \mid \mathbf{X}, \mathbf{y}, \mathbf{x}_* \sim \mathcal{N}(\bar{f}_*, \text{Var}(f_*)) \]

其中：

\[ \bar{f}_* = \mathbf{k}_*^T (K + \sigma_n^2 I)^{-1} \mathbf{y} \]

\[ \text{Var}(f_*) = k(\mathbf{x}_*, \mathbf{x}_*) - \mathbf{k}_*^T (K + \sigma_n^2 I)^{-1} \mathbf{k}_* \]

\(\mathbf{k}_*\) 是测试点与训练点之间的核向量，\(K\) 是训练点的核矩阵。

核函数选择与超参数优化

GP 的核函数选择直接决定了模型的先验假设：

核函数	先验假设	适用场景
Squared Exponential (SE)	无限可微的光滑函数	默认选择
Matern 核	可控的光滑程度	物理过程建模
Periodic 核	周期性函数	季节性数据
核的组合（加法/乘法）	复合结构	复杂模式

超参数通过最大化边际似然（marginal likelihood）来优化：

\[ \log P(\mathbf{y} \mid \mathbf{X}, \theta) = -\frac{1}{2}\mathbf{y}^T (K_\theta + \sigma_n^2 I)^{-1}\mathbf{y} - \frac{1}{2}\log|K_\theta + \sigma_n^2 I| - \frac{N}{2}\log 2\pi \]

这自动平衡了数据拟合（第一项）和模型复杂度（第二项），天然具有 Occam's razor 的效果。

不确定性量化

GP 最大的优势之一是内建的不确定性量化：

预测均值 \(\bar{f}_*\) 给出点预测
预测方差 \(\text{Var}(f_*)\) 给出不确定性估计
在训练数据密集的区域，方差小（高置信度）
在训练数据稀疏的区域，方差大（低置信度）

这使得 GP 非常适合主动学习（Active Learning）和贝叶斯优化（Bayesian Optimization）等需要评估不确定性的任务。

核方法与神经网络

Neural Tangent Kernel（NTK）

Jacot et al. (2018) 提出了一个深刻的理论联系：在无限宽度极限下，神经网络的训练动态等价于核方法。

对于参数为 \(\theta\) 的神经网络 \(f(\mathbf{x}; \theta)\)，Neural Tangent Kernel 定义为：

\[ \Theta(\mathbf{x}, \mathbf{x}') = \left\langle \frac{\partial f(\mathbf{x}; \theta)}{\partial \theta}, \frac{\partial f(\mathbf{x}'; \theta)}{\partial \theta} \right\rangle \]

当网络宽度趋向无穷时，NTK 在训练过程中保持不变，网络的训练等价于在 NTK 对应的 RKHS 中做核回归。

核方法的现代启示

主题	核心观点
NTK 理论	无限宽网络 \(\approx\) 核方法，提供了理解深度学习的理论窗口
核近似	Random Fourier Features 等方法让核方法可以扩展到大规模数据
注意力机制	Softmax 注意力可以看作核函数的一种形式
GP 与 BNN	单隐层无限宽网络的先验等价于 GP（Neal, 1996）
核方法的局限	缺乏特征学习能力（核是固定的），这正是深度学习的优势所在

核方法提供了理解机器学习的优雅数学框架。虽然在实践中深度学习已经占据主导地位，但核方法的理论工具——RKHS、Mercer 定理、表示定理——仍然是理解和分析现代深度学习模型的重要理论基础。

核方法