🏠 总目录📚 本教程 06 · 核技巧 ← →
📑 本页目录（点开跳转）

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

⏱ 24 分钟 ｜ ⭐⭐⭐ 机器学习里最优雅的想法

🎯 一句话

想在高维空间里干活，但高维算不动（第 5 章）。 核技巧：不去那个高维空间，却拿到在那里计算的结果。

原空间：画不出一条直线分开φ‖x‖²升维后：一条直线就够了
左边在原空间里画不出一条直线分开；把「到圆心的距离」当成一个新维度抬起来之后，一条直线就够了。核技巧的妙处在于：它能拿到右边的效果，却从不真的把点搬到右边去。

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

   一维数据，线性不可分：
   ○ ○ ○ ● ● ● ○ ○ ○         ← 一刀切不开（中间是●，两边是○）
   ────────────────► x

   把它映射到二维：φ(x) = (x, x²)
                                    ●●●
   x² ▲          ○           ○      ← 现在一条直线能切开了！✅
      │      ○                 ○
      │  ●  ●  ●
      └──────────────► x

💡 核心思想：在低维分不开的数据，映射到高维往往就分得开了。

这不是巧合——维度越高，"能把点分开的方式"就越多。 极端情况下，n 个点映射到 n−1 维后总是线性可分的。

但问题来了：

问题 说明
映射到几维？ 为了保险可能要几千维甚至无穷维
算不动 高维计算量爆炸（第 5 章）
存不下 每个样本变成一个几千维的向量

⭐ 二、核技巧：那个漂亮的观察

关键发现：很多算法（感知机、SVM、PCA、岭回归、K-Means…） 只用到样本之间的内积 $x_i^\top x_j$，从不需要单个样本本身。

   如果算法只需要 φ(xᵢ)·φ(xⱼ)，
   而我们能【直接算出这个内积】，不必先算出 φ(xᵢ) 和 φ(xⱼ)……

   那我们就根本不需要去那个高维空间！ ⭐

🔨 一个 30 秒能验证的例子

   取二维输入 x = (x₁, x₂)，定义映射到三维：
   φ(x) = (x₁², √2·x₁x₂, x₂²)

   算两个点在【三维空间】里的内积：

   φ(a)·φ(b) = a₁²b₁²  +  2a₁a₂b₁b₂  +  a₂²b₂²

              = (a₁b₁)² + 2(a₁b₁)(a₂b₂) + (a₂b₂)²     ← 完全平方式！

              = (a₁b₁ + a₂b₂)²

              = (a·b)²                      ⭐⭐
                 ↑ 只用【二维】的内积，平方一下就得到了

💡 人话：

在原空间算个内积，平方一下 —— 你就白拿到了三维空间里的内积。 从头到尾没有构造过任何三维向量。

$$K(a,b) = (a^\top b)^2 = \varphi(a)^\top\varphi(b)$$

这个函数 K 就叫「核函数」。

# 自己验证一下（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)        # 核技巧：二维点积后平方
# → 两个数完全相同 ✅

🎩 三、为什么这叫"魔法"

   多项式核 K(a,b) = (a·b + c)^d
   → 对应的 φ 把 n 维映射到 C(n+d, d) 维
   → d=5, n=100 时是【近亿维】
   → 但你只需要：算一次点积，加个常数，取 5 次方 ✅

   高斯核（RBF） K(a,b) = exp(−‖a−b‖²/2σ²)
   → 对应的 φ 是【无穷维】的！ ⭐
   → 你永远算不出 φ(x)，但 K(a,b) 一行就算完
📐 为什么 RBF 核是无穷维（想看再点）

把指数展开成泰勒级数：

$$e^{a^\top b} = \sum_{k=0}^{\infty}\frac{(a^\top b)^k}{k!}$$

每一项 $(a^\top b)^k$ 都对应一个 k 阶多项式核 —— 也就是一个有限维映射。 无穷多项加起来 = 无穷维的特征空间。

而 RBF 核 $\exp(-\gamma\|a-b\|^2) = e^{-\gamma\|a\|^2}e^{-\gamma\|b\|^2}e^{2\gamma a^\top b}$， 最后那项正是上面的形式。

🔑 核技巧的威力一句话： 你在一个自己永远无法写下来的空间里做线性分类，而计算成本只和原始维度有关。

📋 四、常用核函数

核 公式 特点 什么时候用
线性核 $a^\top b$ 就是不做映射 数据本身线性可分；高维稀疏（文本）
多项式核 $(a^\top b + c)^d$ 捕捉 d 阶特征交互 知道存在特定阶的交互
高斯核 / RBF ⭐ $\exp(-\gamma\|a-b\|^2)$ 无穷维，极其灵活 默认首选
Sigmoid 核 $\tanh(\kappa a^\top b + c)$ 类似两层神经网络 少用（不总满足 Mercer 条件）

🎚️ RBF 核的 γ 到底在控制什么

   K(a,b) = exp(−γ‖a−b‖²)

   γ = 0.01  →  距离要很远相似度才降下来
                每个点影响一大片 → 边界平滑 → 【欠拟合】

   γ = 100   →  稍微远一点相似度就掉到 0
                每个点只影响身边一丁点 → 边界极其扭曲 → 【过拟合】
                （极端情况：退化成"只有自己和自己相似" = 记住训练集）

⭐ γ 是偏差-方差旋钮，和第 4 章 kNN 的带宽 h 是同一个东西的两种写法。

💡 一个漂亮的连接：RBF 核 exp(−γ‖a−b‖²) 和第 4 章 kNN 的高斯加权完全一致。 「离得近的样本更重要」这个朴素想法，一路长成了核方法。

实用起点：gamma="scale"（sklearn 默认，按特征方差自适应），然后在 [0.001, 0.01, 0.1, 1] 附近扫。

✅ 五、什么函数才能当核（Mercer 条件）

不是随便一个二元函数都能当核。必须存在某个 φ 使得 K(a,b) = φ(a)·φ(b)。

判据（Mercer 定理）：K 是合法核 ⟺ 对任意样本集，核矩阵（Gram 矩阵）半正定。

$$\mathbf{K} = \begin{pmatrix} K(x_1,x_1) & \cdots & K(x_1,x_n)\\ \vdots & & \vdots \\ K(x_n,x_1) & \cdots & K(x_n,x_n)\end{pmatrix} \succeq 0$$

💡 人话：核矩阵必须是一个"合法的相似度矩阵"—— 半正定保证了不会出现「某个样本和自己的相似度是负的」这类荒谬情况。

实用规则（不用记定理）

   ✅ 常用核（线性/多项式/RBF）都是合法的，直接用

   ✅ 核的【组合】仍是核，可以放心造新核：
      K₁ + K₂          （和）
      c·K   (c > 0)    （正数倍）
      K₁ · K₂          （乘积）
      f(x)·K·f(y)      （函数缩放）

   ⚠️ 只有自己发明核函数时，才需要验证半正定

一个实用场景：多模态数据可以分别用不同的核再相加—— 比如 K_文本 + K_图像，这仍是合法核。

⚠️ 六、代价：核矩阵是 n×n 的

   核方法的计算量和【样本数 n】有关，而不是维度 d
   —— 这正好和你的直觉相反！

   n = 1 万   → 核矩阵 10⁸ 个数 ≈ 800 MB       还行
   n = 10 万  → 10¹⁰ 个数 ≈ 80 GB             💀 存不下
   n = 100 万 → 10¹² 个数                      💀💀

   训练复杂度：O(n²) ~ O(n³)
   预测复杂度：O(n_sv × d)   ← 要和每个支持向量算核

⭐ 这就是核方法在大数据时代输给深度学习的根本原因： 它的复杂度随样本数超线性增长，无法 scale。

🔗 对比基础教程第 14 章的教训： Transformer 赢在能并行、能 scale。 核方法优雅但不 scale——这在深度学习时代是致命的。 又一次印证：可扩展性胜过精巧的结构设计。

缓解手段（了解即可）：Nyström 近似、随机傅里叶特征（把核近似成有限维显式特征）。

🔗 七、和站内其他章的关系

相关的地方 这里的位置
第 4 章 kNN 的高斯加权 就是 RBF 核
第 5 章维度灾难 核技巧是绕过它的一条路（不真去高维）
第 7 章 SVM 的对偶形式 对偶让核技巧能用上（下一章）
推荐算法的相似度矩阵 就是一个核矩阵（如果它半正定的话）
基础教程：Transformer 赢在可扩展 核方法输在 O(n²)

✅ 检查点

  1. 核技巧解决什么问题？它的关键前提是什么？
  2. 为什么 (a·b)² 等于三维空间里的内积？（能推一遍吗）
  3. RBF 核对应多少维的映射？γ 大和小分别导致什么？
  4. Mercer 条件的实用含义是什么？怎么造新核？
  5. 核方法的复杂度和什么有关？为什么这和直觉相反？
  6. 为什么说核方法"优雅但输了"？
👀 答案
  1. 解决"想用高维空间的表达力但算不动"的问题。关键前提：算法只用到样本间的内积，从不需要单个样本本身。
  2. 展开 φ(a)·φ(b) = a₁²b₁² + 2a₁a₂b₁b₂ + a₂²b₂²，这是完全平方式 (a₁b₁+a₂b₂)²，也就是 (a·b)²。所以原空间算内积再平方，就白拿到了高维内积。
  3. 无穷维（指数的泰勒展开对应无穷多个多项式核）。γ 大 → 只有极近的点相似 → 边界扭曲 → 过拟合；γ 小 → 远处也算相似 → 边界平滑 → 欠拟合。
  4. 核矩阵必须半正定（合法的相似度矩阵）。造新核：核的和、正数倍、乘积仍是核，所以可以 K_文本 + K_图像 这样组合。
  5. 和样本数 n 有关（核矩阵 n×n），不是维度 d。这和直觉相反——直觉以为高维更难，但核技巧恰恰把维度问题消掉了，代价转移到了样本数上。
  6. 它用一个极其优雅的数学技巧绕过了维度灾难，但复杂度 O(n²~n³) 使它无法处理大数据。可扩展性胜过精巧设计。

🛑 可以停在这里

⚡ 走神救援

核技巧 = 不去那个高维空间，却拿到在那里计算的结果。低维分不开的数据映射到高维往往就分得开（n 个点映射到 n−1 维后总是线性可分），但高维算不动、存不下。⭐关键观察：SVM、PCA、岭回归、感知机只用到样本间的内积，不需要单个样本本身——只要能直接算出高维内积，就不必去那个空间。例子：φ(x) = (x₁², √2·x₁x₂, x₂²) 时 φ(a)·φ(b) 恰好是个完全平方式，等于 (a·b)²——在原空间算个内积、平方一下，就白拿到三维内积，全程没构造过任何三维向量。威力：多项式核 (a·b + c)^d 在 d=5、n=100 时对应近亿维映射，你只需算一次点积、加常数、取 5 次方；RBF 核 exp(−γ‖a−b‖²) 更是对应无穷维（泰勒展开 = 无穷多个多项式核叠加），你永远算不出 φ(x)，但 K(a,b) 一行算完。⭐你在一个自己永远无法写下来的空间里做线性分类，而计算成本只和原始维度有关。RBF 是默认首选。γ 是偏差-方差旋钮：γ 小则每点影响一大片、边界平滑 → 欠拟合；γ 大则只影响身边一点 → 过拟合（极端时退化成「只和自己相似」= 记住训练集）。💡RBF 核就是第 4 章 kNN 的高斯加权，γ 和带宽 h 是同一个东西。合法性看 Mercer 条件：核矩阵必须半正定；核的和、正数倍、乘积仍是核，多模态可放心写 K_文本 + K_图像。⚠️代价：核矩阵是 n×n 的——n=1 万约 800 MB，n=10 万就是 80 GB，存不下；训练复杂度 O(n²)~O(n³)。⭐复杂度取决于样本数 n 而不是维度 d，正好和直觉相反；这也是核方法输给深度学习的根本原因——优雅但无法 scale，可扩展性胜过精巧的结构设计。缓解：Nyström 近似、随机傅里叶特征。

下一节 👉 07-SVM.md

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