5.SVM

SVM 通过最大化间隔实现分类，支持硬间隔、软间隔和核方法三种策略。

问题分类与策略

数据特点	SVM 方法
线性可分	Hard-margin
近似线性可分	Soft-margin
非线性	Kernel Method

约束优化基础

原问题：

${\min }_{x}f(x)s.t.m_i(x)\le 0,n_j(x)=0$

Lagrange 函数：

$L(x,\lambda ,\eta )=f(x)+{\sum }_i{\lambda }_i{m}_i(x)+{\sum }_j{\eta }_j{n}_j(x)$

对偶关系：${\max }_{\lambda ,\eta }{\min }_{x}L\le {\min }_x{\max }_{\lambda ,\eta }L$

凸优化满足 Slater 条件时强对偶成立，KKT 条件为充要条件：

1. 可行域：$m_i(x^{\ast })\le 0,n_j(x^{\ast })=0,{\lambda }^{\ast }\ge 0$
2. 互补松弛：${\lambda }^{\ast }{m}_i(x^{\ast })=0$
3. 梯度为零：${\nabla }_{x}L(x^{\ast },{\lambda }^{\ast },{\eta }^{\ast })=0$

Hard-margin SVM

最大化间隔：

${\mathrm{argmin}}_{w,b}\frac{1}{2}{w}^{T}ws.t.y_i(w^T{x}_i+b)\ge 1$

对偶问题：

${\max }_{\lambda }-\frac{1}{2}{\sum }_{i,j}{\lambda }_i{\lambda }_j{y}_i{y}_j{x}_i^T{x}_j+{\sum }_i{\lambda }_{i}s.t.{\lambda }_i\ge 0$

KKT 条件给出解：

$\hat{w}={\sum }_{i=1}^N{\lambda }_i{y}_i{x}_i,\hat{b}=y_k-w^T{x}_k$

仅支撑向量（${\lambda }_i>0$）参与决策边界构建。

Soft-margin SVM

引入松弛变量处理不可分数据：

${\mathrm{argmin}}_{w,b}\frac{1}{2}{w}^{T}w+C{\sum }_{i=1}^N{\xi }_{i}s.t.y_i(w^T{x}_i+b)\ge 1-{\xi }_i,{\xi }_i\ge 0$

损失等价于 Hinge 函数：$\max \{0,1-y_i(w^T{x}_i+b)\}$

Kernel Method

通过特征变换 $\varphi (x)$ 将数据映射到高维空间。核函数直接计算变换后的内积：

$k(x,x^{\prime })=\varphi (x{)}^T\varphi (x^{\prime })$

正定核条件：对称性 + Gram 矩阵半正定。

常用核函数如高斯核：$k(x,x^{\prime })=\exp (-\frac{\Vert x-x^{\prime }{\Vert }^2}{2{\sigma }^2})$