核技巧与常用核函数

一句话定义

核技巧注意到许多算法只依赖样本内积 x_i^⊤ x_j，于是把内积替换为核函数 K(x_i, x_j) = φ(x_i)^⊤ φ(x_j)，隐式地在高维（甚至无限维）特征空间里做线性学习，而无需显式计算 φ。

为什么重要

它让线性方法获得非线性能力且不失凸性：核 SVM、核岭回归、核 PCA 共享同一技巧。理解核方法就理解了「显式特征工程」与「隐式相似度度量」的等价性——这一视角也连接了后来核方法与深度核、高斯过程的谱系。

前置知识

最大间隔与线性 SVM 对偶问题「只含内积」这一关键结构；向量空间与内积概念。

核心概念

• 特征映射：φ: 𝒳 → ℋ，把原始空间映到高维希尔伯特空间。
• 核函数：K(x, z) = φ(x)^⊤ φ(z)，一个「相似度打分」。
• Mercer 条件：核矩阵半正定 ⇔ 存在某个 φ 使 K 是内积——合法核的判据。
• 多项式核：K(x, z) = (x^⊤ z + c)^d，对应 d 次单项式特征。
• RBF（高斯）核：K(x, z) = exp(-γ ‖ x - z ‖²)，无限维特征，局部相似度。
• 核矩阵（Gram 矩阵）：K_ij = K(x_i, x_j)，核方法的全部数据依赖。

直观类比

判断两份文档是否讲同一件事：不必把所有可能的「主题组合」显式列出来（维度爆炸），只需一个函数直接读出「这两份像不像」。核函数就是「不搬家就能享受高维客厅」的神奇契约——所有算法只跟「相似度」说话，相似度可以非法（无需真搬家）地模拟高维内积。

原理与机制

为什么可行：对偶 SVM、核岭回归的解都形如 f(x) = ∑_i α_i y_i K(x_i, x) + b，训练只需 Gram 矩阵。证明 K 合法只需 Mercer 条件（对称 + 半正定）。RBF 核的展开：

是无穷阶多项式核——对应无限维特征空间，表达能力极强，因此 γ 与 C 不当会严重过拟合。

代价与边界：Gram 矩阵 O(n²) 存储、训练 O(n² ∼ n³)，样本数万后吃力（此时转线性 SVM/GBDT）；核选择与 γ 调参对效果影响巨大（见 kp-024），默认 RBF + 标准化 + 网格 γ ∈ {10^-3,…,10} 是常规起手。

闭包性质：合法核的和、积、指数、与正数相乘仍是合法核（半正定锥的封闭性），可据此构造复合核。

公式与推导

核化的一般替换法则：把算法中每个 x_i^⊤ x_j 写成 K(x_i, x_j)、每个 ‖ x ‖² 写成 K(x, x)。以「样本到类均值的距离」为例：

全程只用核值——最近质心分类器就这样免费升级为核化版本。多项式核验证（d = 2）：(x^⊤ z + c)² 的展开项恰为特征向量 φ(x) = (x₁², …, √2x₁x₂, …, √2c x₁, …, c) 的内积。

图示

原始空间（同心圆不可线性分）      RBF 隐式高维空间
   × × ×                        z₁
  × ○ ○ ×        ──φ──▶          │  ○○○
  × ○ ○ ×                       │ ○○○○○
   × × ×                        │───────
                                 │  ××××
 决策面 = 高维平面 = 原空间的圆形边界

实例或案例

环形数据上对比线性与 RBF 核（经典的核技巧必要性演示）：

from sklearn.datasets import make_circles
from sklearn.svm import SVC
from sklearn.preprocessing import StandardScaler
from sklearn.pipeline import make_pipeline
from sklearn.model_selection import cross_val_score

X, y = make_circles(n_samples=500, factor=0.4, noise=0.12, random_state=0)
lin = make_pipeline(StandardScaler(), SVC(kernel="linear", C=1))
rbf = make_pipeline(StandardScaler(), SVC(kernel="rbf", C=1, gamma="scale"))
print("linear:", cross_val_score(lin, X, y, cv=5).mean().round(3))   # ≈0.5 不可分
print("rbf    :", cross_val_score(rbf, X, y, cv=5).mean().round(3))  # ≈0.98

常见误区

• 样本量上万仍硬上核 SVM：O(n²) 的 Gram 矩阵内存与训练时间爆炸，工程上应转 LinearSVC 或树集成。
• 用 RBF 核前不标准化：γ ‖ x - z ‖² 被大量纲特征主导，等价于废掉其他特征。
• 认为「核 = 万能非线性」：核方法解决不了「没有好相似度定义」的问题，文本/图等结构化数据需要领域核（字符串核、图核）设计。

与其他知识点的关系

软间隔 SVM 与铰链损失 的盒约束对偶是核 SVM 的完整问题形式；K-means 聚类与 k-means++ 的「距离 → 核替换」展示了同一技巧的扩展面；主成分分析 PCA 的核 PCA 是无监督侧的同源方法；超参数调优：网格、随机与贝叶斯搜索 中 (C, γ) 联合网格是核 SVM 的标准调参任务。

自测题

1. 核技巧省掉了什么计算？没有省掉什么？

- 要点：省掉显式 φ 与高维向量的运算；没省掉 O(n²) 的样本两两核值计算。

1. 判断 K(x, z) = (x^⊤ z)² - x^⊤ z 是否合法核？

- 要点：不合法。合法核的差不一定半正定（K₁ - K₂ 不保半正定），可找一个向量 v 使 v^⊤ K v < 0。

1. RBF 核的 γ 过大/过小各什么现象？

- 要点：过大→决策边界过碎、每个点自成孤岛（严重过拟合）；过小→趋于线性边界（欠拟合）。

延伸阅读

李航《统计学习方法》第 7.3 节；Hofmann 等， Kernel Methods in Machine Learning（Annals of Statistics, 2008）。