Kernel Trick —— 核技巧与常用核函数

前言

在前三篇文章中，我们从线性回归一路走到了支持向量机（SVM）。细心的读者可能已经注意到：SVM的对偶形式中，所有计算都只依赖于样本之间的内积 $x_i^T x_j$ 。这个看似不起眼的观察，却打开了一扇通往高维非线性世界的大门。

核方法（Kernel Methods） 的核心思想极其简洁而深刻：如果我们能把算法中的所有内积运算替换为一个核函数（Kernel Function），就能在不显式计算高维特征的情况下，让线性算法具备处理非线性问题的能力。

这就是著名的核技巧（Kernel Trick）。

这篇文章，我们将从核函数的数学定义出发，理解Mercer定理为何是核方法的理论基础，然后深入分析多项式核与RBF（高斯）核的映射本质，最后通过可视化理解RBF核中 gamma 参数如何影响模型的过拟合与欠拟合。

一、什么是核函数？

1.1 从特征映射说起

假设我们有一个二维数据集，在原始空间中线性不可分。一个自然的想法是：把数据映射到更高维的空间，在高维空间中它们可能变得线性可分。

设特征映射为 $\phi: \mathcal{X} \rightarrow \mathcal{F}$ ，其中 $\mathcal{F}$ 是高维特征空间（甚至是无穷维的）。在特征空间中，线性SVM的对偶问题变为：

\max_{\alpha} \sum_{i=1}^{N} \alpha_i - \frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_i \alpha_j y_i y_j \cdot \phi(x_i)^T \phi(x_j)

关键问题来了：我们真的需要显式计算 $\phi(x_i)$ 吗？

如果特征空间的维度是 $10^6$ 甚至无穷大，显式计算特征映射在计算上是不可行的。

1.2 核函数的定义

核函数（Kernel Function）就是一个巧妙的替代方案。它定义为：

\boxed{K(x, z) = \phi(x)^T \phi(z)}

也就是说，核函数直接计算两个样本在特征空间中的内积，而不需要我们显式地知道 $\phi$ 是什么。

核函数可以理解为一种相似性度量—— $K(x, z)$ 越大，表示 $x$ 和 $z$ 在特征空间中越相似。

1.3 核函数的三个基本性质

一个函数要想成为合法的核函数，必须满足以下条件：

对称性： $K(x, z) = K(z, x)$ ，因为内积是对称的
连续性：作为相似性度量，应该是平滑的
正半定性（Positive Semi-Definite） ：对于任意 $N$ 个样本 $\{x_1, ..., x_N\}$ ，核矩阵（Gram矩阵） $K_{ij} = K(x_i, x_j)$ 必须是正半定的，即所有特征值非负

第3条性质尤其重要——它保证了优化问题是凸的，从而有唯一的全局最优解。

二、Mercer定理：核方法的理论基石

2.1 定理的直观含义

Mercer定理（1909年，由James Mercer提出）是核方法的理论基石。它的核心意思是：

如果一个对称连续的核函数 $K$ 能保证对任意有限样本集形成的Gram矩阵都是正半定的，那么就一定存在一个特征映射 $\phi$ ，使得 $K(x, z) = \phi(x)^T \phi(z)$ 。

换句话说：Mercer定理保证了“核函数”与“特征空间中的内积”是等价的。

2.2 数学表述

更严格地，Mercer定理可以表述为：

设 $\mathcal{X}$ 是紧集， $K: \mathcal{X} \times \mathcal{X} \rightarrow \mathbb{R}$ 是一个连续、对称、正定的核函数。则存在一组正交特征函数 $\{\psi_j\}_{j=1}^{\infty}$ 和非负特征值 $\{\lambda_j\}_{j=1}^{\infty}$ ，使得：

K(x, z) = \sum_{j=1}^{\infty} \lambda_j \psi_j(x) \psi_j(z)

其中级数在 $\mathcal{X} \times \mathcal{X}$ 上绝对且一致收敛。

这个展开式意味着：核函数可以分解为无穷多个特征函数的加权和，而每个特征函数 $\psi_j$ 可以看作是特征映射的一个“坐标”。

2.3 为什么Mercer定理如此重要？

Mercer定理为核方法提供了三个关键保证：

存在性保证：任何一个满足条件的核函数，都对应着某个（可能是无穷维的）特征空间
凸性保证：核矩阵的正半定性保证了SVM的目标函数是凸的，优化问题有唯一解
计算可行性：我们可以在原始空间中计算核函数值，而无需涉足高维特征空间

一言以蔽之：Mercer定理告诉我们“可以这么做”，核技巧告诉我们“怎么高效地做”。

三、核技巧：将线性SVM扩展为非线性

3.1 从对偶形式看核技巧

回顾软间隔SVM的对偶问题：

\max_{\alpha} \sum_{i=1}^{N} \alpha_i - \frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_i \alpha_j y_i y_j \cdot \underbrace{x_i^T x_j}_{\text{内积}}

\text{s.t.} \quad \sum_{i=1}^{N} \alpha_i y_i = 0, \quad 0 \leq \alpha_i \leq C

核技巧的核心操作极其简单：把对偶问题中的内积 $x_i^T x_j$ 替换为核函数 $K(x_i, x_j)$ ：

\boxed{\max_{\alpha} \sum_{i=1}^{N} \alpha_i - \frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_i \alpha_j y_i y_j \cdot K(x_i, x_j)}

就这么一个替换，线性SVM就变成了非线性SVM。

3.2 预测时的核技巧

训练完成后，对于新样本 $x'$ ，决策函数为：

f(x') = \text{sign}\left( \sum_{i=1}^{N} \alpha_i y_i K(x_i, x') + b \right)

同样，我们只需要计算核函数，而不需要显式计算 $\phi(x')$ 。

3.3 核技巧的通用性

核技巧并不仅限于SVM。任何可以用内积形式表达的算法都可以被“核化” ——包括主成分分析（Kernel PCA）、岭回归（Kernel Ridge Regression）、Fisher判别分析等。

四、常用核函数及其映射本质

4.1 线性核（Linear Kernel）

K(x, z) = x^T z

线性核实际上就是不做任何映射， $\phi(x) = x$ 。它对应的是原始空间中的线性模型，是核方法的特例。

适用场景：数据本身线性可分，或特征维度已经很高（如文本分类中的词袋模型）。

4.2 多项式核（Polynomial Kernel）

\boxed{K(x, z) = (x^T z + c)^d}

其中 $d$ 是多项式的次数， $c \geq 0$ 是常数项（通常取1）。

映射本质：多项式核对应的特征映射 $\phi(x)$ 包含了所有次数不超过 $d$ 的单项式。

以二维输入 $x = (x_1, x_2)$ 、 $d=2$ 、 $c=1$ 为例：

K(x, z) = (x_1 z_1 + x_2 z_2 + 1)^2

展开后：

K(x, z) = 1 + 2x_1 z_1 + 2x_2 z_2 + x_1^2 z_1^2 + 2x_1 x_2 z_1 z_2 + x_2^2 z_2^2

对应的特征映射为（忽略常数系数）：

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

关键洞察：二维数据被映射到了六维特征空间！在原始空间中，我们只需要计算 $(x^T z + 1)^2$ 这个标量值，就等价于在六维空间中计算内积。

1
import numpy as np
2

3
def polynomial_kernel(x, z, degree=2, coef0=1):
4
    """多项式核函数"""
5
    return (np.dot(x, z) + coef0) ** degree
6

7
# 示例：二维向量
8
x = np.array([1, 2])
9
z = np.array([3, 4])
10
print(f"多项式核 (d=2): {polynomial_kernel(x, z, degree=2):.2f}")
11
# 输出: (1*3 + 2*4 + 1)^2 = (3+8+1)^2 = 144

适用场景：数据有交互特征（如图像识别中的像素组合）。

参数影响：

$d$ 越大，模型越复杂，越容易过拟合
实际中 $d=2$ 或 $d=3$ 最为常用

4.3 RBF（高斯）核

\boxed{K(x, z) = \exp\left(-\gamma \|x - z\|^2\right)}

其中 $\gamma > 0$ 控制核函数的宽度。等价形式为 $K(x, z) = \exp\left(-\frac{\|x - z\|^2}{2\sigma^2}\right)$ ，其中 $\gamma = \frac{1}{2\sigma^2}$ 。

RBF核是最常用的核函数，因为它只有一个参数且性能优异。

映射本质：无穷维特征空间

RBF核的特征映射是无穷维的。我们可以通过泰勒展开来理解：

K(x, z) = e^{-\gamma \|x - z\|^2} = e^{-\gamma \|x\|^2} \cdot e^{-\gamma \|z\|^2} \cdot e^{2\gamma x^T z}

展开 $e^{2\gamma x^T z} = \sum_{j=0}^{\infty} \frac{(2\gamma)^j}{j!} (x^T z)^j$ ，可以看到RBF核是无穷多个多项式核的加权和。

对应的特征映射包含所有阶数的单项式（从0阶到无穷阶）：

\phi(x) = e^{-\gamma \|x\|^2} \left(1, \sqrt{\frac{2\gamma}{1!}}x, \sqrt{\frac{(2\gamma)^2}{2!}}x^2, \sqrt{\frac{(2\gamma)^3}{3!}}x^3, \dots \right)

这意味着：RBF核可以在无穷维空间中计算内积，而我们只需要在原始空间中计算一个指数函数！

这就是核技巧的威力所在。

1
def rbf_kernel(x, z, gamma=1.0):
2
    """RBF（高斯）核函数"""
3
    return np.exp(-gamma * np.linalg.norm(x - z) ** 2)
4

5
x = np.array([1, 2])
6
z = np.array([3, 4])
7
print(f"RBF核 (gamma=1.0): {rbf_kernel(x, z, gamma=1.0):.4f}")
8
# 输出: exp(-1 * ((1-3)^2 + (2-4)^2)) = exp(-8) ≈ 0.0003

RBF核的直观理解：

当 $x$ 和 $z$ 非常接近时， $K(x, z) \approx 1$
当 $x$ 和 $z$ 相距很远时， $K(x, z) \approx 0$
$\gamma$ 控制着“多远算远”—— $\gamma$ 越大，相似性衰减得越快

适用场景：绝大多数非线性问题，是SVM的默认选择。

4.4 Sigmoid核

K(x, z) = \tanh(\gamma x^T z + r)

其中 $\gamma > 0$ ， $r$ 是偏移量。

Sigmoid核源自神经网络，但对于某些参数取值，它不满足Mercer条件（即不是正半定的）。尽管如此，它在实践中仍然可能表现良好。

适用场景：特定问题中可作为神经网络的替代。

五、RBF核中 `gamma` 参数的影响

5.1 gamma 的几何含义

在RBF核 $K(x, z) = \exp(-\gamma \|x - z\|^2)$ 中， $\gamma$ 控制着单个训练样本的影响力范围：

较小的 $\gamma$ ：影响力范围远 —— 即使距离较远的样本也会相互影响，决策边界平滑
较大的 $\gamma$ ：影响力范围近 —— 只有非常接近的样本才会相互影响，决策边界复杂

$\gamma$ 可以被理解为 RBF核的“半径”的倒数。

5.2 gamma 对过拟合/欠拟合的影响

scikit-learn 官方文档用验证曲线清晰地展示了 $\gamma$ 的影响：

$\gamma$ 取值	训练集表现	验证集表现	诊断
非常小（如 $10^{-6}$ ）	低	低	欠拟合 —— 模型过于平滑，无法捕捉数据模式
中等（如 $10^{-3} \sim 10^{-1}$ ）	高	高	良好 —— 模型复杂度适中
非常大（如 $10$ ）	极高（接近100%）	低	过拟合 —— 每个样本只影响自己，决策边界极度扭曲

5.3 直观理解

当 $\gamma$ 非常小时：

RBF核几乎对所有样本对都给出接近1的值
模型相当于一个非常平滑的模型，类似于线性模型
无法捕捉数据的复杂结构 → 欠拟合

当 $\gamma$ 非常大时：

只有几乎完全相同的样本才会互相影响
每个支持向量只“管辖”自己周围极小的一片区域
决策边界变得极度曲折，完美拟合每一个训练点 → 过拟合

当 $\gamma$ 取中间值时：

样本的影响力范围适中
决策边界既能捕捉数据的主要模式，又不会被噪声过度影响
验证集表现最佳

5.4 与参数 C 的协同作用

$\gamma$ 和 $C$ 共同控制着RBF-SVM的复杂度：

$\gamma$ 控制着特征空间的“曲率” —— 决定模型能拟合多复杂的决策边界
$C$ 控制着对误分类的容忍度 —— 决定模型是否愿意为了拟合个别点而牺牲平滑性

在实践中， $\gamma$ 和 $C$ 通常需要在对数空间中通过网格搜索进行调优（如 $10^{-3}, 10^{-2}, ..., 10^3$ ）。

1
from sklearn.svm import SVC
2
from sklearn.model_selection import validation_curve
3
from sklearn.datasets import load_digits
4
import numpy as np
5
import matplotlib.pyplot as plt
6

7
# 加载数据（二分类：1 vs 2）
8
X, y = load_digits(return_X_y=True)
9
mask = np.isin(y, [1, 2])
10
X, y = X[mask], y[mask]
11

12
# 验证曲线：观察gamma的影响
13
param_range = np.logspace(-6, -1, 5)
14
train_scores, test_scores = validation_curve(
15
    SVC(kernel='rbf', C=1.0),
16
    X, y,
17
    param_name='gamma',
18
    param_range=param_range,
19
    cv=5,
20
    scoring='accuracy'
21
)
22

23
# 绘制结果
24
train_mean = np.mean(train_scores, axis=1)
25
test_mean = np.mean(test_scores, axis=1)
26

27
plt.semilogx(param_range, train_mean, label='Training score', marker='o')
28
plt.semilogx(param_range, test_mean, label='Validation score', marker='o')
29
plt.xlabel('gamma')
30
plt.ylabel('Accuracy')
31
plt.legend()
32
plt.title('Validation Curve for SVM with RBF Kernel')
33
plt.show()
34
# 观察：gamma极小时两者都低（欠拟合），gamma适中时两者都高，
35
# gamma过大时训练高但验证低（过拟合）

六、核函数的组合与构造

6.1 核函数的代数运算

如果 $K_1$ 和 $K_2$ 是合法的核函数，那么以下组合也是合法的核函数：

加法： $K(x, z) = K_1(x, z) + K_2(x, z)$
数乘： $K(x, z) = c \cdot K_1(x, z)$ ，其中 $c \geq 0$
乘法： $K(x, z) = K_1(x, z) \cdot K_2(x, z)$
多项式： $K(x, z) = p(K_1(x, z))$ ，其中 $p$ 是正系数多项式
指数： $K(x, z) = \exp(K_1(x, z))$

这些性质允许我们根据问题的特点定制核函数。

6.2 如何选择核函数？

场景	推荐核函数	原因
特征维度远大于样本数	线性核	数据在高维空间中通常已经线性可分
特征数适中，样本数适中	RBF核	通用性强，只有一个超参数
特征数很少，需要复杂交互	多项式核	可以显式控制特征交互的次数
与神经网络类比	Sigmoid核	等价于单隐层神经网络

实际建议：当不确定时，先用RBF核。它是最通用、最稳健的选择。

七、总结

概念	核心内容
核函数	$K(x,z) = \phi(x)^T\phi(z)$ ，在原始空间中计算高维特征空间的内积
Mercer定理	对称连续的PSD核函数一定对应某个（可能无穷维的）特征映射
核技巧	将对偶问题中的内积替换为核函数，将线性算法扩展为非线性
多项式核	$K=(x^Tz+c)^d$ ，映射到包含所有≤d阶单项式的特征空间
RBF核	$K=\exp(-\gamma\\|x-z\\|^2)$ ，映射到无穷维特征空间
gamma参数	控制单个样本的影响力范围：小→欠拟合，中→良好，大→过拟合

核心要点回顾

核函数的本质：核函数 $K(x,z)$ 是在原始空间中计算高维（甚至无穷维）特征空间的内积。它让我们既享受了高维映射的好处，又避免了高维计算的代价。
Mercer定理：保证了“核函数”与“特征空间内积”的等价性。任何满足对称性、连续性和正半定性的核函数，都对应着某个特征映射。
核技巧：将SVM对偶问题中的内积 $x_i^T x_j$ 替换为核函数 $K(x_i, x_j)$ ，一句话将线性SVM变成了非线性SVM。这种技巧可以推广到任何以内积形式表达的算法。
多项式核的映射：将 $d$ 维输入映射到包含所有次数不超过 $d$ 的单项式的特征空间。维度从 $p$ 暴涨到 $\binom{p+d}{d}$ 。
RBF核的无穷维映射：通过泰勒展开可知，RBF核等价于无穷多个多项式核的加权和，对应的特征空间是无穷维的。这是核技巧最震撼的体现——在原始空间中算一个指数函数，就等价于在无穷维空间中算内积。
gamma参数：控制RBF核的宽度。 $\gamma$ 太小→欠拟合（模型过于平滑）， $\gamma$ 太大→过拟合（每个样本只影响自己）。通常需要在对数空间中进行网格搜索调优。

Clear Eyes, Full Heart