核技巧

线性不可分怎么办

第 10 章那个棋盘数据,一条直线分不开。当时的解法是决策树。

SVM 的解法是另一条路:把数据映射到更高维,让它在高维里变线性可分。

一个具体的例子

一维上,两个类交替排列(红蓝红蓝),任何一条线(一个点)都分不开。

但如果给每个点加一个特征 x2x^2,投射到二维平面上,红点会在上面、蓝点在下面——一条水平线就能分开。

维度升高,可分性变好。这是核方法的核心直觉。

问题:算不动

理想情况下映射到无穷维,可分性最好。但显式地算每个点的无穷维坐标是不可能的。

关键观察:SVM 的求解过程(对偶形式)里,数据点只以内积的形式出现 xi⊤xjx_i^{\top}x_j, 从来不需要单独的 xix_i。

所以如果我能直接算出高维空间里的内积,就不需要真的把点映射过去。

K(xi,xj)=ϕ(xi)⊤ϕ(xj)K(x_i, x_j) = \phi(x_i)^{\top}\phi(x_j)

KK 就叫核函数。它接收两个原始空间的点,返回它们在高维空间的内积。

这就是“核技巧”

不用真的升维,就能得到升维后的效果。

代价从“算出每个点的高维坐标”降到“算一次原始空间的内积”——后者往往只是几次乘加。

最常用的核

线性核

K(xi,xj)=xi⊤xjK(x_i, x_j) = x_i^{\top}x_j

就是原始空间的内积,等于没升维。特征已经很多(比如文本)时用它。

多项式核

K(xi,xj)=(γxi⊤xj+r)dK(x_i, x_j) = (\gamma x_i^{\top}x_j + r)^d

对应所有 dd 阶以内的组合特征。想引入特征交互时用。

RBF 核(高斯核)

K(xi,xj)=exp⁡(−γ∥xi−xj∥2)K(x_i, x_j) = \exp(-\gamma \|x_i - x_j\|^2)

对应无穷维的映射。它是默认选择,下一课专门讲。

什么函数能当核

不是随便什么函数都行。它必须对应某个真实的高维空间的内积——数学上的条件是核矩阵半正定。

实际影响:你不需要自己造核函数。上面那三个(加上 sigmoid 核)覆盖了绝大多数场景。

核方法的代价

核矩阵是 n×nn \times n 的。一万个样本就是 1 亿个数,几百 MB。

所以 SVM 在样本量大时会爆内存。这也是它在深度学习时代退居二线的原因之一—— 神经网络能处理百万级样本,SVM 到十万级就吃力了。

这一课解决了什么

核技巧让 SVM 能处理非线性问题,而不付出升维的计算代价。

RBF 核有个参数 γ 需要调,它的作用比 C 更微妙。下一课讲。