06 · 核技巧:不用算就能算
⏱ 24 分钟 | ⭐⭐ 阅读时长仅供参考
本章目标:知道核函数省掉了哪一步,也知道它没有省掉什么。
先看七个点与两种算法得到的 121;要选参数,再去 γ 的作用;要评估数据规模,直接看计算代价。推导可以按需展开。
🎯 一句话
核技巧省掉的是“显式列出映射后的特征”,不是省掉计算。
上图仍是同一批 19 个点:外圈 12 个、内圈 7 个。映射增加 $z=x_1^2+x_2^2$;右侧只画 $(x_1,z)$ 投影,重合点叠在一起。
外圈半径为 3,平方半径为 9;内圈相应为 1。三维平面 $z=5$ 能分开两类,在这个投影中显示为横线。这是可分性的例子,具体怎样省下计算,后面用 121 的算例解释。
如果算法可以只依赖特征之间的内积,我们就用核函数直接算出这个内积。高维特征不必一项项展开,但输入维度、样本数量和泛化问题仍然存在。
🧠 一、问题:线性不可分怎么办
设输入只有一个数 $x$。中间三个样本是一类,两侧四个样本是另一类。
在这条数轴上,一条分界线只能分出左侧与右侧,不能直接表达“中间一类、两端一类”。增加特征 $x^2$ 后,分类条件可以变成“平方有没有超过 2.5”。
核对图上的数。 这不是换了一批样本,只是给每个样本增加一个坐标:
| 输入 x | 平方 x² | 类别 |
|---|---|---|
| −3、3 | 9 | 空心 |
| −2、2 | 4 | 空心 |
| −1、1 | 1 | 实心 |
| 0 | 0 | 实心 |
映射空间里是一条水平直线;换回原来的 $x$,它对应两侧与中间的划分。“映射后线性”不等于“原坐标里也是一条直线”。
增加维度,不等于自动分得开
有用的是映射保留了什么、增加了什么特征,不是维度这个数字本身。给每个点附加一串零,就不会改善可分性。
如果两个样本输入完全相同、标签却相反,确定性映射仍把它们送到同一点,无法把它们分开。
关于“n 个点能映射到 n−1 维”的准确条件
对于 $n$ 个互不相同的输入点,可以专门构造映射,把它们放到一个 $(n-1)$ 维单纯形的顶点上。这样,任意二分类标签都能被某个带截距的线性分类器分开。
这是“存在一种合适映射”的结论,不是“任意升维都有效”。它也没有说明新样本会被分到哪里,不能当作泛化保证。
显式映射还要回答三个实际问题:
- 映射到哪些特征? 特征选择体现了模型假设。
- 能否算出它们? 高阶交互可能产生非常多的项。
- 能否存下它们? 每个样本都需要一份展开后的特征。
核技巧主要应对后两项中的特征展开成本,不自动解决第 5 章讨论的样本稀疏与泛化困难。
⭐ 二、核技巧:直接计算映射后的内积
先认三个对象:
- $a,b$:原始输入。
- $\varphi(x)$:把输入变成特征向量的映射。
- $K(a,b)$:直接返回这两个特征向量的内积。
$$K(a,b)=\langle\varphi(a),\varphi(b)\rangle$$
只有当算法能改写成依赖这些内积时,才可以把内积替换为 $K$。不是给任意算法换一个“相似度”就完成核化。
🔨 两种算法,同一个结果:121
从二维输入出发,定义三维映射:
$$\varphi(x)=(x_1^2,\sqrt{2}x_1x_2,x_2^2)$$
为看清完全平方公式,先把两个乘积临时记成:
$$s=a_1b_1,\qquad t=a_2b_2$$
那么展开后的内积是:
$$\langle\varphi(a),\varphi(b)\rangle=s^2+2st+t^2$$
$$s^2+2st+t^2=(s+t)^2=(a^\top b)^2$$
看中间的 $2st$: 映射里两个 $\sqrt{2}$ 相乘,正好给出完全平方公式需要的系数 2。
取 $a=(1,2)$、$b=(3,4)$,原始内积是 $3+8=11$。平方得到 121,与显式映射后的内积相同。
下面保留两条计算路线,方便你自己比较。第二条才是不展开三维特征的核技巧。
# 自己验证一下(10 秒)
import numpy as np
a, b = np.array([1., 2.]), np.array([3., 4.])
phi = lambda x: np.array([x[0]**2, np.sqrt(2)*x[0]*x[1], x[1]**2])
print(phi(a) @ phi(b)) # 显式映射到三维再点积
print((a @ b) ** 2) # 核技巧:二维点积后平方
# → 两个数完全相同 ✅
观察结果: 这段代码两次都输出 121.0。数学恒等式严格成立;更复杂的浮点计算比较时,应容许末位舍入误差。
哪些算法可以这样改写
- 感知机、SVM、岭回归: 使用相应的对偶或核化形式,让训练和预测依赖样本间的核值。
- PCA: Kernel PCA 使用核矩阵,并需要在特征空间中心化;不能只把普通 PCA 的一个点积换掉。
- K-Means: 核化版本把距离、簇中心相关计算改写成核值。两个映射点的距离可由下面的式子得到:
$$d_\varphi(a,b)^2=K(a,a)+K(b,b)-2K(a,b)$$
这里 $d_\varphi$ 是映射空间里的距离。这与原输入的欧氏距离未必相同。
🎩 三、为什么能省下大量特征
多项式核:一次内积代替很多交互项
令输入维度为 $D$,阶数为正整数 $r$:
$$K(a,b)=(a^\top b+c)^r$$
当 $c>0$ 时,可用包含 0 到 $r$ 阶单项式的特征映射表示。项数为:
$$M=\binom{D+r}{r}$$
例如 $D=100$、$r=5$,共有 96,560,646 项,接近一亿。核值却可通过原始内积、加常数、取五次方得到。
条件不能省略: 当 $c=0$ 时,只剩恰好 $r$ 阶的齐次项,项数变成 $\binom{D+r-1}{r}$。负的 $c$ 不能不加检查地沿用上述合法核结论。
RBF:隐式使用无限维特征
本章的 RBF 指高斯核。参数 $\sigma>0$:
$$K(a,b)=\exp\left(-\frac{\|a-b\|^2}{2\sigma^2}\right)$$
在整个欧氏输入空间上,它对应无限维的特征表示。但算一对输入的核值,仍只需要求距离、平方、缩放和指数。
这不意味着程序要存一个无限长数组。对固定的 $n$ 个训练点,核矩阵只有 $n\times n$ 个元素,秩不超过 $n$;也可以使用有限维的近似特征。
想看推导:指数级数如何对应特征
先令 $\gamma=1/(2\sigma^2)$,把只与一个输入有关的因子记为:
$$A_\gamma(x)=e^{-\gamma\|x\|^2}$$
利用平方距离展开,RBF 可以分成:
$$K(a,b)=A_\gamma(a)A_\gamma(b)e^{2\gamma a^\top b}$$
最后一项的级数为:
$$e^{2\gamma a^\top b}=\sum_{k=0}^{\infty}\frac{(2\gamma)^k}{k!}(a^\top b)^k$$
每个 $k$ 对应一组 $k$ 阶多项式特征,前面的 $A_\gamma$ 则缩放各自的特征。所有阶一起构成一种无限维映射。
要进一步判断“能否用固定有限维映射,对所有输入精确表示”,还需看核的秩:高斯核在任意数量的互异输入点上都可产生满秩 Gram 矩阵,因此不存在统一的有限维上限。
核函数返回的是一个数,而不是整条高维向量。“隐式特征”与“有限个训练点的核矩阵”是两件事。
📋 四、常用核函数
线性核
$$K(a,b)=a^\top b$$
相当于 $\varphi(x)=x$。高维稀疏文本可以先尝试线性模型;使用线性核不要求训练数据必须完全线性可分,软间隔 SVM 仍允许违反间隔。
多项式核
$$K(a,b)=(a^\top b+c)^r$$
适合把指定阶数的特征交互作为候选假设。这里使用 $c\geq0$、正整数 $r$;若加入内积缩放系数,也应使用非负系数来沿用这组充分条件。
高斯核 / RBF
$$K(a,b)=\exp(-\gamma\|a-b\|^2)$$
这里 $\gamma>0$。它按距离定义局部相似度,是非线性模型的常见候选,不是对所有数据都最好的默认答案。
Sigmoid 核
$$K(a,b)=\tanh(\kappa a^\top b+c)$$
它的形式与神经网络中的激活有关,但不等于训练了一个神经网络,也不对任意参数和输入域都半正定。API 接受这个名称,不等于标准凸核 SVM 的理论条件自动满足。
🎚️ RBF 核的 γ 到底在控制什么
先固定输入的单位,再比较 γ。 同一距离下,γ 越大,相似度衰减越快。
用相同距离 $r=\|a-b\|$ 代入,得到:
| 距离 r | γ = 0.01 | γ = 100 |
|---|---|---|
| 0 | 1 | 1 |
| 0.1 | 约 0.99990 | 约 0.36788 |
| 1 | 约 0.99005 | 约 $3.72\times10^{-44}$ |
较大的 γ 倾向于让影响范围更局部;较小的 γ 倾向于让变化更平滑。是否过拟合,还要结合 SVM 的 $C$、数据尺度与验证误差判断。 图上的 γ 数字不能单独给出欠拟合或过拟合结论。
带宽与 γ 的关系是:
$$\gamma=\frac{1}{2\sigma^2}$$
若第 4 章的高斯加权把带宽写成 $h$,对应关系就是 $\gamma=1/(2h^2)$:带宽越大,γ 反而越小。
高斯形状可以用于加权 kNN、核回归、KDE 和核 SVM,但它们的样本选择、归一化和输出不同;不能把算法或公式整个互换。
实际调参顺序:
- 先留出验证方式;标准化参数只从训练数据拟合,放进 Pipeline,避免泄漏。
- 对 SVC,
gamma="scale"是一个起点。在训练输入总体方差为正时,它按1 / (n_features * X.var())取值,不会替你标准化每个特征。 - 可从
0.001、0.01、0.1、1这类对数刻度候选开始,结合尺度扩展范围,并同时验证 $C$;不要把这一组数当成固定有效区间。
参数定义与计算限制见 SVC 官方文档。
📐 五、什么函数才能当核
这里讨论实数值的内积核。它需要对称:
$$K(a,b)=K(b,a)$$
还需要对任意有限输入集合,对应的 Gram 矩阵都半正定。先定义矩阵中的元素:
$$\mathbf K_{ij}=K(x_i,x_j)$$
半正定的意思是,对任意实系数向量 $z$:
$$z^\top\mathbf Kz\geq0$$
为什么要这个条件? 若它真来自特征内积,上式就是“加权特征和的长度平方”,不可能小于零。
对称与上述半正定条件等价于存在某个 Hilbert 空间特征映射。Mercer 定理还涉及相应条件下的特征函数展开;不要把“任意相似度矩阵看起来正常”叫作 Mercer 检验。Cornell 核方法讲义
对角线非负,为什么还不够
看这个矩阵:
$$\mathbf K=\begin{pmatrix}1&2\\2&1\end{pmatrix}$$
它对称、元素全为正,对角线也都为 1。但取 $z=(1,-1)^\top$:
$$z^\top\mathbf Kz=1-2-2+1=-2$$
所以它不是合法特征内积产生的 Gram 矩阵。只检查“自己与自己的相似度非负”会漏掉这个反例。
反过来,核值也不必处处非负。例如一维线性核 $K(1,-1)=-1$ 完全合法。别把内积直接当成概率。
实用规则:怎样组合已有的核
在相同输入域上,若 $K_1,K_2$ 已经是合法核,下列组合仍合法:
- 相加: $K_1(a,b)+K_2(a,b)$。
- 非负倍数: $cK_1(a,b)$,其中 $c\geq0$。
- 逐对相乘: $K_1(a,b)K_2(a,b)$;这里不是两个 Gram 矩阵做矩阵乘法。
- 成对缩放: $f(a)K_1(a,b)f(b)$,$f$ 为任意实值函数。
例如同一批对象同时有文本与图像,可分别定义核,再用非负权重加权。两部分的数值尺度和权重仍要验证,不是“合法”就一定好用。
自定义函数、Sigmoid 或外部提供的相似度矩阵都要留意条件。只测当前一张 Gram 矩阵半正定,不能证明这个函数在所有输入集合上都合法。
⚠️ 六、代价:核矩阵是 n×n 的
核技巧避开特征展开,但计算仍依赖原始输入维度 $D$ 和样本数 $n$。
先看内存,而不是只看公式长短
如果完整保存稠密 Gram 矩阵,并且每个元素用 8 字节的 float64:
| 样本数 n | 元素数量 | 仅矩阵本身 |
|---|---|---|
| 1 万 | $10^8$ | 约 800 MB |
| 10 万 | $10^{10}$ | 约 80 GB |
| 100 万 | $10^{12}$ | 约 8 TB |
这里 MB、GB、TB 按十进制字节计算,还没算其他训练数据和工作内存。具体求解器可能缓存部分核值,而不是一次存满整张矩阵。
再看计算落在哪一步
- 一对核值: 对稠密 $D$ 维输入,线性核、RBF 等通常需要 $O(D)$ 的计算。
- 完整 Gram 矩阵: 有 $n^2$ 对位置,直接计算通常为 $O(n^2D)$。
- 训练求解: 依算法而异。比如核岭回归的常规稠密线性方程求解可达到 $O(n^3)$;不能把这个阶数套给所有核算法。
- SVM 预测: 一个二分类预测分数通常需要与 $n_{\rm sv}$ 个支持向量算核,成本约为 $O(n_{\rm sv}D)$。不是所有核模型都只有支持向量参与。
因此,应分别估算“读入与算核、存储、求解、预测”,不要用一个复杂度口号代替整条计算路径。
数据太多时,还有哪些选择
Nyström: 选一部分代表样本,构造低秩核近似。
随机傅里叶特征: 对 RBF 等平移不变的正定核,构造有限维的随机近似特征,再使用线性学习器。它不是任意核的通用公式。
这些方法可以减少对完整 $n\times n$ 矩阵的依赖,但要验证近似误差、特征数量和最终任务指标。官方核近似说明
基础教程第 14 章讨论 Transformer 的可扩展实现。这里可以比较计算路径,但不能据此宣布“核方法必然输给深度学习”:样本量、模态、硬件、精度与延迟目标都影响选择。
🔗 七、和站内其他章的关系
- 第 4 章 kNN / KDE / 核回归: 高斯形状可能相同,权重归一化与输出含义不同。
- 第 5 章维度灾难: 区分展开成本与统计泛化,核技巧不包办两者。
- 第 7 章 SVM: 对偶形式如何让核值进入训练和预测。
- 推荐算法的相似度矩阵: 对一组对象,实对称半正定矩阵可以表示为特征内积;任意推荐相似度不自动满足条件。
- 基础教程的 Transformer: 对比实现与扩展成本,不把“谁赢了”当作选模型的理由。
✅ 检查点
- 核技巧省掉什么步骤?算法需要满足什么前提?
- 为什么二维输入的 $(a^\top b)^2$ 能表示上面那个三维内积?
- RBF 的无限维特征与有限 Gram 矩阵矛盾吗?γ 与带宽怎样对应?
- 为什么对角线非负不够?哪些核组合可以沿用合法性?
- 算核、存储和预测分别依赖哪些数量?
- 数据变大时,怎样比较精确核、核近似与其他模型?
查看答案:先核对结论,再回到对应段落
1.省掉显式特征展开。 算法需要能改写为依赖映射空间内积;仍要计算核值,并没有消除输入维度和样本数。
2.完全平方公式。 三维内积展开后是 $s^2+2st+t^2$,而 $s+t=a^\top b$。本例两种路线都得到 121。
3.不矛盾。 全输入空间的精确特征表示可以无限维,固定 $n$ 个训练点的 Gram 矩阵仍只有 $n^2$ 个数。带宽越大,$\gamma=1/(2\sigma^2)$ 越小;过拟合与否还要看验证结果。
4.还要检查所有加权组合。 正文的二阶矩阵对 $z=(1,-1)^\top$ 给出 −2。合法核可相加、取非负倍数、逐对相乘或成对函数缩放。
5.同时看 $D,n,n_{\rm sv}$。 一对稠密核值通常为 $O(D)$;完整矩阵需要 $O(n^2)$ 存储;上述二分类 SVM 预测约为 $O(n_{\rm sv}D)$。训练成本还取决于求解方法。
6.在同一验证与预算下比较。 记录精度、训练时间、内存和预测延迟。核近似可能改善扩展性,但需要检查近似误差;没有仅凭方法名字就决定胜负的规则。
本节回顾
先记住三件事
- 核函数直接返回映射空间的内积,省的是特征展开。
- 合法内积核要求对称,并在任意有限输入集合上半正定。
- 同时验证参数、泛化和计算成本;无限维特征不等于无限内存。
下一节 👉 07-SVM.md