机器学习数学基础 120 章

核函数、正定核与 RKHS 直觉

层级：B｜建议先修：02-05、02-08、02-16、04-12

核方法把输入隐式映射到高维甚至无限维特征空间，再进行线性学习。只要算法最终仅通过特征内积工作，就可用核函数直接计算内积，避免显式构造高维特征。

1. 特征映射

设

ϕ:X→H,\phi:\mathcal X\to\mathcal H,

把原始输入映射到内积空间 H\mathcal H。在该空间中，线性模型为

f(x)=⟨w,ϕ(x)⟩H+b.f(x)=\langle w,\phi(x)\rangle_{\mathcal H}+b.

即使原空间中的关系非线性，在合适特征空间中也可能线性可分。

2. 核函数

核函数定义为特征内积

k(x,z)=⟨ϕ(x),ϕ(z)⟩H.k(x,z)=\langle\phi(x),\phi(z)\rangle_{\mathcal H}.

算法若只需要这些内积，就可直接用 k(x,z)k(x,z)，无需知道 ϕ\phi 的具体坐标。这称为核技巧。

3. 一个显式例子

对二维输入 x=(x1,x2)x=(x_1,x_2)，二次多项式核

k(x,z)=(xTz)2k(x,z)=(x^Tz)^2

可对应映射

ϕ(x)=(x12,2x1x2,x22)T.\phi(x)=(x_1^2,\sqrt2x_1x_2,x_2^2)^T.

因为

ϕ(x)Tϕ(z)=(x1z1+x2z2)2.\phi(x)^T\phi(z)=(x_1z_1+x_2z_2)^2.

核计算一次内积，就隐式包含了二次交互特征。

4. Gram 矩阵

给定样本 x1,ldots,xnx_1,ldots,x_n，核 Gram 矩阵定义为

Kij=k(xi,xj).K_{ij}=k(x_i,x_j).

若核来自内积，则对任意 c∈Rnc\in\mathbb R^n，

cTKc=∥∑iciϕ(xi)∥H2≥0.c^TKc =\left\|\sum_ic_i\phi(x_i)\right\|_{\mathcal H}^2\ge0.

所以 KK 必须对称半正定。

5. 正定核的判据

一个对称函数 kk 若对任意有限样本和任意实系数都有

∑i,jcicjk(xi,xj)≥0,\sum_{i,j}c_ic_jk(x_i,x_j)\ge0,

则称为正半定核，机器学习中常简称正定核。Mercer 理论在相应正则条件下保证它可以解释为某个 Hilbert 空间中的内积。

不是任意相似度函数都是合法核；仅有 k(x,z)=k(z,x)k(x,z)=k(z,x) 不够，还需所有 Gram 矩阵半正定。

6. 常用核

  • 线性核：k(x,z)=xTzk(x,z)=x^Tz；
  • 多项式核：k(x,z)=(γxTz+c)dk(x,z)=(\gamma x^Tz+c)^d；
  • Gaussian/RBF 核：
k(x,z)=exp⁡(−∥x−z∥22σ2);k(x,z)=\exp\left(-\frac{\|x-z\|^2}{2\sigma^2}\right);
  • Laplacian 核：exp⁡(−∥x−z∥1/σ)\exp(-\|x-z\|_1/\sigma)。

RBF 核对应无限维特征空间。σ\sigma 小时相似性很局部，模型更灵活；σ\sigma 大时函数更平滑。

7. 合法核的组合

若 k1,k2k_1,k_2 是合法核，则在适当条件下：

  • ak1+bk2ak_1+bk_2 对 a,b≥0a,b\ge0 仍是核；
  • k1k2k_1k_2 仍是核；
  • f(x)k1(x,z)f(z)f(x)k_1(x,z)f(z) 仍是核；
  • 对输入变换 gg，k1(g(x),g(z))k_1(g(x),g(z)) 仍是核。

这些规则允许用已有核构建组合特征相似性。

8. RKHS 是什么

再生核 Hilbert 空间（RKHS）是一个函数空间，每个 f∈Hkf\in\mathcal H_k 都是从 X\mathcal X 到实数的函数，并满足：

  1. 对每个 xx，函数 k(x,⋅)∈Hkk(x,\cdot)\in\mathcal H_k；
  2. 再生性质
f(x)=⟨f,k(x,⋅)⟩Hk.f(x)=\langle f,k(x,\cdot)\rangle_{\mathcal H_k}.

取 f=k(z,⋅)f=k(z,\cdot) 可得

k(z,x)=⟨k(z,⋅),k(x,⋅)⟩.k(z,x)=\langle k(z,\cdot),k(x,\cdot)\rangle.

所以核既定义了相似度，也定义了一整个函数空间及其几何。

9. RKHS 范数的直觉

∥f∥Hk\|f\|_{\mathcal H_k} 衡量函数相对于该核的复杂度或不平滑程度。其具体含义随核而变。正则化问题常写为

min⁡f∈Hk1n∑iℓ(f(xi),yi)+λ∥f∥Hk2.\min_{f\in\mathcal H_k} \frac1n\sum_i\ell(f(x_i),y_i) +\lambda\|f\|_{\mathcal H_k}^2.

λ\lambda 越大，越偏好 RKHS 范数小的函数。

10. 表示定理

表示定理说明，上述广泛一类正则化问题的最优解可写为

f∗(x)=∑i=1nαik(xi,x).f^*(x)=\sum_{i=1}^n\alpha_i k(x_i,x).

即使 RKHS 无限维，最优解仍落在训练样本核截面的有限张成空间中。优化变量由“无限维函数”化为 nn 个系数。

11. SVM 中的核技巧

线性 SVM 的对偶问题只含样本内积 xiTxjx_i^Tx_j。替换为 k(xi,xj)k(x_i,x_j) 后得到核 SVM，决策函数为

f(x)=∑iαiyik(xi,x)+b.f(x)=\sum_i\alpha_i y_i k(x_i,x)+b.

只有支持向量对应的 αi\alpha_i 非零，因此预测由它们决定。

12. 核岭回归

平方损失加 RKHS 范数正则可得到

α=(K+nλI)−1y\boldsymbol\alpha=(K+n\lambda I)^{-1}\mathbf y

（系数随目标中平均方式略有不同），预测为

f(x)=kxTα.f(x)=\mathbf k_x^T\boldsymbol\alpha.

实现时应解线性方程，而不是显式求逆。

13. 中心化与核 PCA

核 PCA 需要特征空间中心化。若 H=I−1n11TH=I-\frac1n\mathbf1\mathbf1^T，中心化 Gram 矩阵为

Kc=HKH.K_c=HKH.

再对 KcK_c 做特征分解，可得到隐式特征空间中的主成分。

14. 计算代价与近似

完整 Gram 矩阵需要 O(n2)O(n^2) 存储，求解可能达到 O(n3)O(n^3) 时间。大数据场景可用：

  • Nyström 低秩近似；
  • 随机 Fourier 特征；
  • 预算化在线核方法；
  • 迭代线性求解与分块计算。

15. 易错点

  1. 核函数不是任意“相似度”，必须满足半正定条件。
  2. 核技巧避免显式高维特征，但 Gram 矩阵会随样本数二次增长。
  3. RBF 核值大只表示在该尺度下接近，不自动带来因果或语义相似。
  4. 核参数与正则化参数要联合验证；过窄 RBF 加弱正则容易过拟合。

常见问答

Q1：核函数的特征映射唯一吗？
不唯一。不同坐标表示可以产生相同内积；核本身定义了等价的几何结构。

Q2：Gram 矩阵出现小负特征值怎么办？
若理论核合法，微小负值可能来自浮点误差，可做对称化和容差处理；明显负值说明核定义或实现可能有问题。

Q3：无限维特征是否意味着无限计算？
不一定。核技巧只计算成对核值，表示定理把解表示成有限样本展开；但样本规模仍带来计算瓶颈。

Q4：核方法和神经网络谁更好？
没有普遍答案。核方法在中小数据、凸优化和明确相似度先验时很强；深度网络更适合端到端学习层次表示和超大规模数据。

练习

  1. 验证二次多项式核给出的显式映射确实满足内积等式。
  2. 证明由特征内积定义的 Gram 矩阵半正定。
  3. 解释 RBF 核的 σ\sigma 变小时模型为何更局部。
  4. 写出表示定理对计算的意义。

答案与提示

  1. 展开 (x1z1+x2z2)2(x_1z_1+x_2z_2)^2，交叉项系数由两个 2\sqrt2 相乘得到 2。
  2. 对任意 cc，cTKc=∥∑iciϕ(xi)∥2≥0c^TKc=\|\sum_ic_i\phi(x_i)\|^2\ge0。
  3. 固定距离下指数衰减更快，只有非常邻近的样本保持较大核值。
  4. 无限维优化的最优解可用 nn 个核基函数展开，转为有限系数优化。