SVM 支持向量机 (Support Vector Machine)

核心思想

SVM 寻找一个最大间隔超平面将不同类别的数据分开。核心直觉是：在所有能正确分类训练数据的超平面中，间隔最大的那个泛化能力最强。

硬间隔线性 SVM

超平面与函数间隔

超平面定义为：

$${\mathbf{w}}^T\mathbf{x}+b=0$$

样本 $({\mathbf{x}}_i,y_i)$ 到超平面的几何间隔：

$${\gamma }_i=y_i\cdot \frac{{\mathbf{w}}^T{\mathbf{x}}_i+b}{\parallel \mathbf{w}\parallel }$$

最大间隔优化问题

令所有样本的最小几何间隔为 $\gamma =\underset{i}{min}{\gamma }_i$，最大化 $\gamma$：

$$\underset{\mathbf{w},b}{max}\frac{2}{\parallel \mathbf{w}\parallel }\text{s.t.}{y}_i({\mathbf{w}}^T{\mathbf{x}}_i+b)\ge 1,\mathrm{\forall }i$$

等价于：

$$\underset{\mathbf{w},b}{min}\frac{1}{2}\parallel \mathbf{w}{\parallel }^2\text{s.t.}{y}_i({\mathbf{w}}^T{\mathbf{x}}_i+b)\ge 1,\mathrm{\forall }i$$

拉格朗日对偶

引入拉格朗日乘子 ${\alpha }_i\ge 0$，构造拉格朗日函数：

$$\mathcal{L}(\mathbf{w},b,\mathit{\alpha })=\frac{1}{2}\parallel \mathbf{w}{\parallel }^2-\sum _{i=1}^N{\alpha }_i[y_i({\mathbf{w}}^T{\mathbf{x}}_i+b)-1]$$

对 $\mathbf{w}$ 和 $b$ 求偏导并令其为零：

$$\frac{\partial \mathcal{L}}{\partial \mathbf{w}}=0⟹\mathbf{w}=\sum _{i=1}^N{\alpha }_i{y}_i{\mathbf{x}}_i$$$$\frac{\partial \mathcal{L}}{\partial b}=0⟹\sum _{i=1}^N{\alpha }_i{y}_i=0$$

代回得到对偶问题：

$$\underset{\mathit{\alpha }}{max}\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{\mathbf{x}}_i^T{\mathbf{x}}_j$$$$\text{s.t.}{\alpha }_i\ge 0,\sum _{i=1}^N{\alpha }_i{y}_i=0$$

KKT 条件

互补松弛条件：

$${\alpha }_i[y_i({\mathbf{w}}^T{\mathbf{x}}_i+b)-1]=0,\mathrm{\forall }i$$

这意味着只有支持向量（$y_i({\mathbf{w}}^T{\mathbf{x}}_i+b)=1$ 的样本）对应的 ${\alpha }_i>0$。

软间隔 SVM

引入松弛变量 ${\xi }_i\ge 0$ 和惩罚参数 $C>0$：

$$\underset{\mathbf{w},b,\mathit{\xi }}{min}\frac{1}{2}\parallel \mathbf{w}{\parallel }^2+C\sum _{i=1}^N{\xi }_i$$$$\text{s.t.}{y}_i({\mathbf{w}}^T{\mathbf{x}}_i+b)\ge 1-{\xi }_i,{\xi }_i\ge 0$$

对偶问题变为约束 $0\le {\alpha }_i\le C$。

核函数 (Kernel Trick)

对偶问题中的 ${\mathbf{x}}_i^T{\mathbf{x}}_j$ 可替换为核函数 $K({\mathbf{x}}_i,{\mathbf{x}}_j)$，实现隐式映射到高维空间而无需显式计算：

核函数	公式
线性核	$K(\mathbf{x},\mathbf{z})={\mathbf{x}}^T\mathbf{z}$
多项式核	$K(\mathbf{x},\mathbf{z})=(\gamma {\mathbf{x}}^T\mathbf{z}+r{)}^d$
RBF (高斯核)	$K(\mathbf{x},\mathbf{z})=\exp (-\gamma |\mathbf{x}-\mathbf{z}{|}^2)$
Sigmoid 核	$K(\mathbf{x},\mathbf{z})=\tanh (\gamma {\mathbf{x}}^T\mathbf{z}+r)$

Mercer 定理：$K$ 必须是正半定的，即对任意样本集，核矩阵 ${\mathbf{K}}_{ij}=K({\mathbf{x}}_i,{\mathbf{x}}_j)$ 满足 $\mathbf{K}⪰0$。

RBF 核的直觉

RBF 核相当于将样本映射到无穷维空间。参数 $\gamma$ 越大，决策边界越"弯曲"、越灵活（更容易过拟合）。

SMO 算法简述

序列最小优化（Sequential Minimal Optimization）每次选取两个 ${\alpha }_i,{\alpha }_j$ 进行解析更新，利用约束 ${\alpha }_i{y}_i+{\alpha }_j{y}_j=\text{const}$ 将二变量问题化为一元问题，得到闭式解。

代码对应

python -m pipelines.classification.svc