141 lines
13 KiB
Markdown
141 lines
13 KiB
Markdown
---
|
||
title: 12 第十二章 支持向量机和灵活的判别方法
|
||
draft: false
|
||
tags:
|
||
- ESL
|
||
---
|
||
## [逻辑架构图]
|
||
|
||
本章笔记的知识点并非平行散落，而是遵循一个层层递进的**“抽象与解耦”**架构：
|
||
1. **基础表象层（几何学）**：寻找最大间隔超平面，解决线性分类（SVC与硬/软间隔）。
|
||
2. **计算解耦层（优化论）**：通过拉格朗日对偶性，丢掉原空间的坐标维度 $d$，只保留样本关系（内积与 KKT 稀疏性）。
|
||
3. **空间映射层（代数学）**：引入“核技巧（Kernel Trick）”，利用数学等价性将高维基函数的存储开销转化为低维标量计算。
|
||
4. **终极抽象层（泛函分析）**：切入 RKHS（再生核希尔伯特空间）与表示定理，证明 SVM 本质上是在做无穷维函数空间的平滑度正则化。
|
||
5. **系统工程层（现代 AI 对比）**：从内核机制到大模型（Transformer / 神经网络）的演进，探讨“坐标派（矩阵乘法）”与“关系派（核计算）”在现代底层硬件上的博弈。
|
||
|
||
---
|
||
|
||
## [深度整理正文]
|
||
|
||
### 一、 基础表象：寻找最稳固的系统边界 (SVC)
|
||
支持向量机（SVM）中的支持向量分类器（SVC）是一种经典的监督学习算法，主要用于二分类问题。它的核心思想非常直观：在特征空间中寻找一个最优的超平面，将不同类别的样本尽可能清晰地分隔开。
|
||
|
||
**1. 核心概念：最大化间隔 (Maximal Margin)**
|
||
想象在一个二维平面上有两组点。我们可以画出无数条直线将它们分开，但哪一条最好？SVM 认为，最好的直线是离两类样本点都尽可能远的那条。
|
||
* **间隔 (Margin)**：指超平面到最近样本点之间的距离。
|
||
* **支持向量 (Support Vectors)**：那些正好落在间隔边界上的样本点。它们是“支撑”起整个分类平面的关键。如果移动这些点，分类平面也会随之改变；而远离边界的点对分类平面的位置毫无影响。
|
||
{从底层鲁棒性来看，最大化间隔相当于在决策边界两侧预留了足够的“容错缓冲区（Buffer）”。在输入数据受到物理噪声（如传感器误差）扰动时，只要扰动幅度不超过 Margin，系统的输出就绝对稳定。}
|
||
|
||
**2. 线性不可分与软间隔 (Soft Margin)**
|
||
现实数据往往不是完美线性可分的。为了处理这种情况，SVC 引入了软间隔：允许一部分样本点落在间隔内部，甚至少量被错误分类。
|
||
* **惩罚参数 C**：超参数，平衡“间隔最大化”和“分类错误率”。
|
||
* **大 C**：对错误容忍度低，容易过拟合（类似于系统中追求 0 丢包率导致重传风暴）。
|
||
* **小 C**：对错误更宽容，追求更宽的间隔，提高模型泛化能力。
|
||
{在数学上，软间隔通过引入松弛变量 $\xi_i \ge 0$ 将绝对的几何约束变成了 Hinge Loss（折页损失）的优化。Hinge Loss 的特性是在 $y_i f(x_i) \ge 1$ 时梯度直接截断为 0，这正是算法产生“稀疏性”的微观根源。}
|
||
|
||
**3. 数学表达**
|
||
原问题（Primal Problem）是在寻找超平面方程 $w^T x + b = 0$，目标是最小化：
|
||
$$ \min_{w, b} \frac{1}{2} \|w\|^2 + C \sum_{i=1}^{n} \xi_i $$
|
||
其中 $\frac{1}{2} \|w\|^2$ 是为了让间隔最大化（因为间隔等于 $1/\|w\|$），$\xi_i$ 代表对分类错误的惩罚。
|
||
{这是一个典型的带不等式约束的凸二次规划（Quadratic Programming, QP）问题。在原问题下，变量的维度是 $d$（特征数）。如果 $d$ 是一百万，原问题将面临巨大的内存分配和计算压力。}
|
||
|
||
---
|
||
|
||
### 二、 计算解耦：拉格朗日对偶与稀疏性
|
||
“这是一个凸优化问题。”通过拉格朗日乘数法，我们将带约束的原问题转化为无约束的对偶问题（Dual Problem）。这不仅简化了计算，还为“核技巧”埋下了伏笔。
|
||
|
||
**1. 构建与转换对偶问题**
|
||
引入拉格朗日乘子 $\alpha_i \ge 0$，对 $w$ 和 $b$ 求偏导后得到核心结论：
|
||
$$ w = \sum_{i=1}^{n} \alpha_i y_i x_i $$
|
||
**重点：** $w$ 本质上是样本点 $x_i$ 的线性组合。代回原函数，我们得到只包含 $\alpha$ 的对偶问题：
|
||
$$ \max_{\alpha} \sum_{i=1}^{n} \alpha_i - \frac{1}{2} \sum_{i=1}^{n} \sum_{j=1}^{n} \alpha_i \alpha_j y_i y_j (x_i \cdot x_j) $$
|
||
约束为 $\sum \alpha_i y_i = 0$ 且 $0 \le \alpha_i \le C$（软间隔）。
|
||
{注意复杂度视角的转换：优化变量从 $d$ 维的 $w$ 变成了 $n$ 维的 $\alpha$。当特征维度远大于样本数（$d \gg n$）时，我们巧妙地绕开了维度灾难，将空间复杂度从 $O(d)$ 变成了 $O(n)$。}
|
||
|
||
**2. 深刻理解“支持向量”与 KKT 条件**
|
||
为什么叫“支持向量”？根据 KKT 互补松弛条件：
|
||
$$ \alpha_i [y_i(w^Tx_i + b) - 1 + \xi_i] = 0 $$
|
||
* **对于大部分点**：远离边界，括号内大于 0，则 $\alpha_i$ 必须为 0。它们对超平面的构成毫无贡献。
|
||
* **对于支持向量**：恰好在边界上（或违反边界），此时 $\alpha_i > 0$。最终的参数 $\hat{\beta}$ 仅由这些点加权求和支撑起来。
|
||
{在计算机系统中，这等价于一种极端的“工作集（Working Set）”机制。成千上万的非支持向量就像是常驻磁盘的冷数据，完全可以被 Page Out（换出）甚至丢弃。而少数的 Support Vectors 则是装载在 L1 Cache 中的热点数据，整个系统的行为仅由这几条 Cache Line 决定。这种基于点的表示极大地降低了推理时的内存访问带宽。}
|
||
|
||
**3. 数据的精简与计算的解耦**
|
||
* **信息压缩**：SVM 在处理高维稀疏数据时，处理的是由极少数点支撑的“骨架”，而不是整个稠密空间。
|
||
* **维度消失术**：对偶目标函数中完全没有特征维度 $d$ 的身影，只有样本之间的内积 $\langle x_i, x_j \rangle$。
|
||
* **求解效率**：{虽然标准的 QP 求解器在面对 $O(n^3)$ 计算量时仍会吃力，但 John Platt 发明的 SMO（序列最小优化）算法，每次只将两个 $\alpha$ 调入 CPU 寄存器进行解析求解，由于内存访问极其具备局部性（Locality），将实际训练速度提升了几个数量级。}
|
||
|
||
---
|
||
|
||
### 三、 空间映射：核技巧（Kernel Trick）的降维打击
|
||
如何处理非线性？这引发了你最精彩的顿悟：**“高维线性 = 低维非线性，这是描述的等价！”**
|
||
|
||
**1. 核技巧的本质：从坐标到内积**
|
||
如果数据扭曲在一起，基函数（Basis Functions）的做法是显式地升维 $\phi(x) = [1, x, x^2, \dots]$。但这会导致计算量爆炸。
|
||
转机在于对偶化：计算过程只需要样本间的内积。我们定义一个核函数 $K(x, z)$ 来代替标准内积：
|
||
$$ K(x, z) = \langle \phi(x), \phi(z) \rangle $$
|
||
{从底层硬件的角度看，基函数需要大量的内存（Memory-Bound）来存储升维后的庞大数组；而核技巧则是不存任何中间数组，直接在原始一维数据上通过算术指令（CPU ALU）即时算出内积结果（Compute-Bound）。这是一种极其优雅的“以计算换空间”的工程妥协。}
|
||
|
||
**2. “内积就是核”的数学验证**
|
||
你的推导非常漂亮：以 $\phi(x) = [1, x, x^2]^T$ 为例。
|
||
在高维空间做内积：$(1 \times 1) + (x_i \times x_j) + (x_i^2 \times x_j^2)$。
|
||
整理后直接得到核函数：$K(x_i, x_j) = 1 + x_i x_j + (x_i x_j)^2$。
|
||
我们不需要知道 $\phi(x)$，直接计算 $K$ 就等同于在高维空间寻找平面。只要函数满足 **Mercer 定理**（对称且半正定），它就是一个合法的核。
|
||
|
||
**3. 基函数（显式） vs 核函数（隐式）**
|
||
* **基函数是空间的“骨架”**：它关心“我是谁”（增加了什么具体特征），是显式的维度提升。
|
||
* **核函数是空间的“度量”**：它关心“我们像不像”，把所有维度的信息压缩成一个标量（相似度）。
|
||
就像你说的：如果你在桌面上撒一把豆子混在一起。你用力一拍桌子，豆子飞到空中（升维），你挥动平板电脑横切过去。在空中看是最简单的平动（高维线性），但在桌面的投影看来，你完成了一个复杂的轨迹捕捉（低维非线性）。**核函数就是连接这两个世界的“虫洞”。**
|
||
|
||
---
|
||
|
||
### 四、 终极抽象：泛函分析与 RKHS
|
||
这标志着从“调包使用”进入到了“统计学习理论”的深水区。
|
||
|
||
**1. 函数估计与再生核希尔伯特空间（RKHS）**
|
||
SVM 不仅仅是在找超平面，它实际上是在 RKHS（一个能承载无限维函数且依然能做几何计算的空间）里找一个最优函数 $f(x)$，最小化：
|
||
$$ \min_{f \in \mathcal{H}} \sum_{i=1}^n L(y_i, f(x_i)) + \lambda \|f\|_{\mathcal{H}}^2 $$
|
||
* **再生性（Reproducing）**：核函数像一个探针：$f(x) = \langle f, K(x, \cdot) \rangle_{\mathcal{H}}$。在 RKHS 中，“取值”等同于“做内积”。
|
||
{从信号处理（DSP）的角度来看，$\|f\|_{\mathcal{H}}^2$ 本质上是对函数高频分量的惩罚（低通滤波器）。RKHS 保证了你的分类边界不会随着噪声数据疯狂震荡。}
|
||
|
||
**2. 表示定理（Representer Theorem）**
|
||
这定理指出：无论 $\mathcal{H}$ 空间多么庞大（甚至无穷维如高斯核），最优的那个函数一定躺在由这 $n$ 个样本点核函数“撑开”的有限维子空间里：
|
||
$$ f^*(x) = \sum_{i=1}^n \alpha_i K(x, x_i) $$
|
||
这就解释了为什么 SVM 可以处理无穷维：最优解永远只跟你的 $n$ 个样本有关，并且由于 Hinge Loss，最终只与更少量的支持向量有关。
|
||
|
||
---
|
||
|
||
### 五、 现代映射：核方法 vs 神经网络
|
||
为什么现在满屏都是神经网络的 $Wx+b$ 而不是 SVM？因为核方法有其“权力边界”。
|
||
|
||
**1. 关系派 vs 坐标派**
|
||
* **核方法（关系派）**：放弃绝对坐标，拥抱相对位置。当你不知道如何描述数据（如 DNA 序列、树结构），但能定义相似度时，String Kernel 等核函数是降维打击。
|
||
* **神经网络（坐标派）**：利用庞大的基函数（隐藏层节点）提取显式特征。
|
||
{现代 GPU 的架构（如 NVIDIA Tensor Cores）是为高度规则化、密集型的矩阵乘法（$W \cdot x$）量身定制的。核方法因为要算 $n \times n$ 的点对点标量关系，属于严重的不规则内存访问，无法吃满 GPU 的算力红利。这是系统底层逼迫算法演进的典型案例。}
|
||
|
||
**2. 万物皆可核化：NTK 与 Transformer**
|
||
神经网络不仅能用核，而且内积是它的灵魂。
|
||
* **Attention 机制**：Transformer 中的 $QK^T$ 就是 Query 和 Key 的两两内积，本质上在算词与词的相似度关系。现代的 Linear Transformer 正是通过核技巧（Kernelization）将其 $O(N^2)$ 的复杂度降为 $O(N)$。
|
||
* **NTK (神经切线核)**：AI 理论界的炸裂结论——无穷宽的神经网络，在训练瞬间完全等价于一个核回归模型。
|
||
神经网络不用静态的“死核”，它是通过一层层线性计算+非线性激活，自己磨出了一套“活的基函数”，并最终构成了极其复杂的动态核！
|
||
|
||
---
|
||
|
||
## [边界知识联动]
|
||
|
||
如果你把这套理论套用在计算机系统科学上，你会发现惊人的底层同构性：
|
||
|
||
1. **核函数 $\leftrightarrow$ 虚拟内存 (Virtual Memory)**
|
||
* **SVM 核技巧**：你不必真实地分配 $10000$ 维的物理内存来存储特征，只需要一个映射函数 $K$，仿佛你拥有无限维的特征空间。
|
||
* **OS 虚拟内存**：进程不必关心真实的物理内存有多大，只需要通过页表映射（MMU），仿佛自己拥有独立的、连续的 4GB/256TB 寻址空间。两者的哲学都是“**延迟分配，按需映射**”。
|
||
2. **支持向量的稀疏性 $\leftrightarrow$ 缓存工作集 (Cache Working Set)**
|
||
* 大部分数据点 $\alpha_i = 0$，只有少数点定义了决策边界。在推理预测阶段，CPU 只需要频繁读取这些支持向量。只要支持向量的数量足够小，它们就能全驻留在 L1/L2 Cache 中，实现极速推理（Cache Hit）。
|
||
3. **Hinge Loss $\leftrightarrow$ 网络拥塞控制 (TCP Congestion Control)**
|
||
* Hinge Loss 的特性是“只要没越界，损失就是 0，不产生任何梯度”。这跟 TCP 拥塞避免的逻辑一致：只要缓冲区没有满（没丢包），系统就认为网络畅通，不做激进的退避调整；一旦越界（错误分类/丢包），才产生惩罚。
|
||
4. **矩阵乘法 vs 核计算 $\leftrightarrow$ SIMD vs 标量指令**
|
||
* 神经网络的基函数计算（坐标派）极容易转化为 `AVX-512` 或 GPU 的 SIMD（单指令多数据流）指令集进行并行加速；而基于 RBF 等复杂核函数的 $N \times N$ 距离计算涉及到指数运算和分支，是典型的标量密集型任务，这是导致传统核方法在大数据时代退居二线的物理限制。
|
||
|
||
|
||
|
||
---
|
||
|
||
### 这章笔记缺少SVM后面的内容：广义线性判别，FDA/PDA，混合判别等内容，后续重读需补充 |