核技巧与非线性分类

线性的天花板

上一篇我们看到，SVM 能找到间隔最大的线性边界。但「线性」意味着只能画直线——如果两类数据像两个新月一样交织在一起，再好的直线也只能切对一半。

问题不在于算法不够聪明，而在于特征空间的维度不够。一个天才的想法：

如果数据在当前维度不可分，那就把它搬到更高维的空间——也许在那里，一条直线就够了。

升维一刀：核技巧

最简单的例子：一维数轴上，两类点穿插排列——紫色在两端，青色在中段。一刀怎么切都分不开。

但如果给每个点加一个坐标 $x^2$，把 $(x)$ 变成 $(x, x^2)$：

映射到 2D 后，紫色点（$|x|$ 大）升到高处，青色点（$|x|$ 小）留在底部，一条水平线就够了。投影回 1D，这条线变成了两个切点——在低维看起来是「曲线」，在高维其实是「直线」。

这就是核技巧的核心直觉：非线性决策边界 = 高维空间里的线性边界投影回来。

数学上，映射 $\phi(\mathbf{x})$ 把数据送到高维后，SVM 在高维做线性分类：

精妙之处：SVM 的优化只用到数据点之间的内积 $\phi(\mathbf{x}_i) \cdot \phi(\mathbf{x}_j)$。核函数 $K(\mathbf{x}_i, \mathbf{x}_j)$ 直接算出这个内积，不需要先显式算 $\phi$ 再做点积。这就是为什么叫「技巧」——你从未真正计算过高维坐标，但效果就像在高维做了线性分类。

RBF 核：映射到无穷维

最常用的核函数是 RBF（Radial Basis Function）核：

它等价于映射到无穷维空间——但计算量跟原始维度一样。

$\gamma$ 控制「视野」：$\gamma$ 大时只看很近的邻居，边界贴着数据弯曲（容易过拟合）；$\gamma$ 小时看得远，边界平滑（可能欠拟合）。

在下面的散点图里，切到 RBF SVM 看它如何绕过两个新月。对比 Logistic 和 Linear SVM 的直线——差距一目了然：

决策树：轴对齐的递归切分

决策树用完全不同的画法绕过线性限制：它只切平行于坐标轴的线，但可以递归地切很多刀。

算法从根节点开始，每次选一个特征和一个阈值，把数据分成两半，让两边尽量「纯」（一类占压倒多数）。衡量「纯度」的标准通常是基尼系数：

$p_k$ 是集合 $S$ 中第 $k$ 类的比例。纯的节点（全是一类）Gini = 0；最不纯（均匀混合）时 Gini 最大。每次选使得分裂后加权 Gini 下降最多的那一刀。

递归下去，空间被切成一堆轴对齐的矩形。在上面的散点图里切到决策树，你能清楚看到这些方框的边界。

决策树的两个独特优势：

• 可解释——每个决策路径都能说成 "如果 $x_1 > 0.5$ 且 $x_2 < 0.3$ 则…"。
• 不需要特征缩放——分裂只看一个特征的阈值，不涉及特征之间的距离计算。

代价是：轴对齐意味着对角线方向的边界需要很多层才能逼近，容易过拟合到训练数据的噪声。随机森林（Random Forest）和 XGBoost 通过集成多棵树来缓解这个问题。

k-NN：跟邻居投票

k-近邻（k-NN） 是最"懒"的分类器：完全不训练，不画任何边界。分类一个新点时，找训练集里离它最近的 $k$ 个邻居，投票。

决策边界是训练数据点之间的 Voronoi 图——完全由数据的局部密度决定。在上面的散点图里切到 k-NN (k=5)，看它的边界如何贴着数据波浪起伏——比树更灵活，但也更不稳定。

k-NN 的几何直觉极其纯粹：相似的东西应该有相似的标签。这个直觉在 2026 年的 LLM 系统里以一个新名字活着——向量检索（embedding retrieval）。

$k$ 的选择是偏差-方差权衡：

• $k$ 小（如 1）：边界完全贴着每个训练点，噪声敏感。
• $k$ 大（如 50）：边界很平滑，但细节丢失。

k-NN 的致命缺点是维度诅咒（curse of dimensionality）：在高维空间里，所有点之间的距离都趋于相同，「最近邻」变得没有意义。这就是为什么现代系统不直接在原始特征上跑 k-NN，而是先用神经网络学出一个低维 embedding，再在 embedding 空间里做最近邻。

这个想法在前沿里