🏠 总目录📚 本教程 06 · 核技巧 ← →

06 · 从问题进入原章节

不显式展开特征,为什么还能做非线性分类?

核函数直接算映射后的内积;是否可分仍取决于映射和数据。不同核与参数决定局部性和计算代价。

读后可检查:能区分特征映射、核计算和核算法适用条件,不把升维当成必然可分。

📑 本页目录(点开跳转)

06 · 核技巧:不用算就能算

⏱ 24 分钟 | ⭐⭐ 阅读时长仅供参考

本章目标:知道核函数省掉了哪一步,也知道它没有省掉什么。

先看七个点与两种算法得到的 121;要选参数,再去 γ 的作用;要评估数据规模,直接看计算代价。推导可以按需展开。


🎯 一句话

核技巧省掉的是“显式列出映射后的特征”,不是省掉计算。

增加平方半径后,用平面分开两类样本原输入:两类同心圆增加 z = x₁² + x₂²zx₁91边界:z = 5φ半径 1 与 3:直线不能分开右图为 (x₁, z) 投影,部分点重合三维中的平面 z = 5,在这个投影里显示为横线
看高度:两类位于分界两侧。

上图仍是同一批 19 个点:外圈 12 个、内圈 7 个。映射增加 $z=x_1^2+x_2^2$;右侧只画 $(x_1,z)$ 投影,重合点叠在一起。

外圈半径为 3,平方半径为 9;内圈相应为 1。三维平面 $z=5$ 能分开两类,在这个投影中显示为横线。这是可分性的例子,具体怎样省下计算,后面用 121 的算例解释。

如果算法可以只依赖特征之间的内积,我们就用核函数直接算出这个内积。高维特征不必一项项展开,但输入维度、样本数量和泛化问题仍然存在。

🧠 一、问题:线性不可分怎么办

设输入只有一个数 $x$。中间三个样本是一类,两侧四个样本是另一类。

在这条数轴上,一条分界线只能分出左侧与右侧,不能直接表达“中间一类、两端一类”。增加特征 $x^2$ 后,分类条件可以变成“平方有没有超过 2.5”。

同样七个点,增加一个平方特征先看原坐标:一条分界线不能把两侧都圈进同一类xxx²增加特征:φ(x) = (x, x²)-3-3-2-2-1-100112233边界:x² = 2.594
看下图虚线:中间三个点的平方不超过 1,外侧四个点的平方至少为 4,所以高度 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 核的 γ 到底在控制什么

先固定输入的单位,再比较 γ。 同一距离下,γ 越大,相似度衰减越快。

同一距离单位下比较 γ相似度 KK = exp(−γr²)00.510123γ = 0.01γ = 1γ = 100距离 r = ‖a−b‖
沿横轴向右看:距离相同,γ 越大,相似度下降越快。曲线比较的是核值,不是验证集误差。

用相同距离 $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,但它们的样本选择、归一化和输出不同;不能把算法或公式整个互换。

实际调参顺序:

  1. 先留出验证方式;标准化参数只从训练数据拟合,放进 Pipeline,避免泄漏。
  2. 对 SVC,gamma="scale" 是一个起点。在训练输入总体方差为正时,它按 1 / (n_features * X.var()) 取值,不会替你标准化每个特征。
  3. 可从 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: 对比实现与扩展成本,不把“谁赢了”当作选模型的理由。

✅ 检查点

  1. 核技巧省掉什么步骤?算法需要满足什么前提?
  2. 为什么二维输入的 $(a^\top b)^2$ 能表示上面那个三维内积?
  3. RBF 的无限维特征与有限 Gram 矩阵矛盾吗?γ 与带宽怎样对应?
  4. 为什么对角线非负不够?哪些核组合可以沿用合法性?
  5. 算核、存储和预测分别依赖哪些数量?
  6. 数据变大时,怎样比较精确核、核近似与其他模型?
查看答案:先核对结论,再回到对应段落

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

打卡记录保存在你的浏览器里,首页能看到总进度