支持向量机（SVM）：算法讲解与原理推导

1 SVM介绍

SVM是一个二类分类器，它的全称是Support Vector Machine，即支持向量机。

SVM的目标是找到一个超平面，使用两类数据离这个超平面越远越好，从而对新的数据分类更准确，即使分类器更加健壮。比如上面的图中，两种分界线都成功划分了所有数据，但是浅颜色的线距离样本很近，距离分界线比较近的样本很容易被误判，相比之下黑色的线就好得多。
它有两个核心思想，一个是对于线性可分数据，SVM通过寻找最大化类别间距离的超平面进行分类；另一个是对于线性不可分数据，SVM就利用核函数将数据映射到高维空间，再找到线性可分的超平面。这个后面再详细说。

2 公式推导

2.1 距离求解

下面需要求解样本点与分界平面之间的距离。这里用到两个概念：投影、向量点乘。
可设分界超平面为$wX+b=0$，$b$是偏移量，$\vec{w}$ 就是平面法向量。

如图，$x$是任意样本点，平面是需要求解的分界面。$x^{\prime }$ 是平面上任意一点，$\vec{w}$ 是平面法向量。其中 $\overrightarrow{x^{\prime }x}$ 为 $x-x^{\prime }$。需要求解 $x$ 到平面的距离 $d$，也就是$\overrightarrow{x^{\prime }x}$ 在 $\vec{w}$ 方向上的投影。
为了符合线性代数的习惯，向量符号就不使用箭头标识了。
根据向量点乘公式知：
$w^T(x-x^{\prime })=||w||\times ||x-x^{\prime }||\times \cos <w^T,x-x^{\prime }>$
则投影为：
$||x-x^{\prime }||\cos <w^T,x-x^{\prime }>=\frac{W^T(x-x^{\prime })}{||w||}=\frac{1}{||w||}(w^{T}x+b)$
所以距离公式为：
$d=\frac{1}{||w||}|w^{T}x+b|$
为了方便求解，约定$w$方向朝向正例样本所在方向，正例样本标签$y$记为1，负例样本标签$y$记为-1，那么距离公式可记为：
$$d=\frac{1}{||w||}y(w^{T}x+b)$$

2.2 目标表示

距离平面的最小间隔，公式表示为：
${\min }_{x_i}\frac{1}{||w||}{y}_i(w^T{x}_i+b)$
目标是最大化所有样本点中距离平面的最小间隔，公式表示为：
${\max }_{w,b}{\min }_{x_i}\frac{1}{||w||}{y}_i(w^T{x}_i+b)={\max }_{w,b}\frac{1}{||w||}{\min }_{x_i}{y}_i(w^T{x}_i+b)$
随着$w$和$b$的任意变化，$y_i(w^T{x}_i+b)$大小可以随之变化。在同一个最优解情况下，会有多个$w$和$b$。于是为了便于求解，约定以下公式作为约束条件：
${\min }_{x_i}{y}_i(w^T{x}_i+b)=1\Rightarrow y_i(w^T{x}_i+b)\ge 1\Rightarrow 1-y_i(w^T{x}_i+b)\le 0$
注意这里每个样本点都构成一个约束。因此求解目标转变为在该限制下的${\max }_{w,b}\frac{1}{||w||}$。为了符合习惯，将其转换为求解最小值，则：
${\max }_{w,b}\frac{1}{||w||}$=${\min }_{w,b}||w||={\min }_{x,b}\frac{1}{2}{w}^{T}w$
这里增加$\frac{1}{2}$是为了便于求导，不会影响结果。
此时优化目标使用公式表示为：
$$\{\begin{array}{l}{\min }_{x,b}\frac{1}{2}{w}^{T}w\\ s.t.1-y_i(w^T{x}_i+b)\le 0,i=1,2,...N\end{array}$$

2.3 求解 $w$

下面就是使用数学原理拉格朗日乘数法、Karush-Kuhn-Tucker (KKT)条件、对偶问题求解上述公式。可以不过于纠结数学原理，如果另有需要，再深入研究。
上述求解目标是有不等式约束下的凸二次优化问题。于是根据拉格朗日乘数法，问题可以转换为：
$$\{\begin{array}{l}{\min }_{w,b}{\max }_{\alpha }L(w,b,\alpha )\\ s.t.{\alpha }_i\ge 0\end{array}$$

其中拉格朗日函数$L(w,b,\alpha )=\frac{1}{2}{w}^{T}w+{\sum }_{i=1}^N{\alpha }_i(1-y_i(w^T{x}_i+b))$。
该公式需要满足KKT条件：
$$\{\begin{array}{l}1-y_i(w^T{x}_i+b)\le 0\\ {\alpha }_i(1-y_i(w^T{x}_i+b))=0\\ {\alpha }_i\ge 0\end{array}$$

$L(w,b,\alpha )$一定是强对偶问题，上述问题可以转换为：
$$\{\begin{array}{l}{\max }_{\alpha }{\min }_{w,b}L(w,b,\alpha )\\ s.t.{\alpha }_i\ge 0\end{array}$$

那么当前首要任务是求解有约束下的${\min }_{x,b}L(w,b,\alpha )$。求解思路是：$L(w,b,\alpha )$对$w$和$b$求偏导，最小值就在偏导为0的点上，那么比较这些点的$L$值大小，最小的点就是最优解。
则求解下面式子：
$$\{\begin{array}{l}\frac{\partial L}{\partial w}=w-{\sum }_{i=1}^N{\alpha }_i{y}_i{x}_i=0\\ \frac{\partial L}{\partial b}={\sum }_{i=1}^N{\alpha }_i{y}_i=0\\ {\alpha }_i\ge 0\end{array}$$

可知：
$w={\sum }_{i=1}^N{\alpha }_i{y}_i{x}_i$
将 $w$ 带回原式子，则：
$$\begin{array}{l}L(w,b,\alpha )\\ =\frac{1}{2}{w}^{T}w+{\sum }_{i=1}^N{\alpha }_i(1-y_i(w^T{x}_i+b))\\ =\frac{1}{2}{\sum }_{i=1}^N{\sum }_{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j{x}_i{x}_j+{\sum }_{i=1}^N{\alpha }_i-{\sum }_{i=1}^N{\alpha }_i{y}_i({\sum }_{j=1}^N{\alpha }_j{y}_j{x}_j{x}_i+b)\\ =\frac{1}{2}{\sum }_{i=1}^N{\sum }_{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j{x}_i{x}_j+{\sum }_{i=1}^N{\alpha }_i-{\sum }_{i=1}^N{\sum }_{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j{x}_i{x}_j-b{\sum }_{i=1}^N{\alpha }_i{y}_i\\ ={\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{x}_j\end{array}$$

下一步又需要求解：
$$\{\begin{array}{l}{\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{x}_j]\\ s.t.{\sum }_{i=1}^N{\alpha }_i{y}_i=0,{\alpha }_i\ge 0\end{array}$$

即：
$$\{\begin{array}{l}{\min }_{\alpha }[\frac{1}{2}{\sum }_{i=1}^N{\sum }_{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j{x}_i{x}_j-{\sum }_{i=1}^N{\alpha }_i]\\ s.t.{\sum }_{i=1}^N{\alpha }_i{y}_i=0,{\alpha }_i\ge 0\end{array}$$

2.4 求解 $b$

支持向量是位于间隔边界上样本点，即$1-y_i(w^T{x}_i+b))=0$。
对于任意一个支持向量，求可以通过$1-y_i(w^T{x}_i+b))=0$计算得到$b$。
如果有多个支持向量，记$S$为支持向量集合，那么可以求解：
$b=\frac{1}{|S|}{\sum }_S{y}_i-w^T{x}_i$。

2.5 求解支持向量（SOM算法）

下面需要基于上面的公式求解每个样本点的${\alpha }_i$。所有满足 ${\alpha }_i\le 0$ 的样本均为支持向量。
如果使用传统二次规划算法求解，样本量较大时效率较为低下。可以使用序列最小优化算法(Sequential Minimal Optimization, SMO)求解：

1. 初始化
   设置所有拉格朗日乘子α的初始值，通常设为零。

2. 选择两个变量 ${\alpha }_i$ 和 ${\alpha }_j$

   • 外层循环：
     遍历训练集中的每个样本，检查其是否违反KKT条件。如果发现某个样本不满足KKT条件，则将其作为第一个要优化的变量${\alpha }_i$。
   • 内层循环：
     选择第二个变量${\alpha }_j$，目标是最大化$|E1-E2|$，即两者的误差差异。这有助于确保每次迭代都能带来显著的变化。（$E_i={\mathbf{w}}^{\top }{\mathbf{x}}_i+b-y_i$，是样本预测值与真实值的误差。）

3. 优化子问题
   固定其他$\alpha$，仅优化 ${\alpha }_i$ 和 ${\alpha }_j$。由于约束 ${\alpha }_i{y}_i+{\alpha }_j{y}_j=-{\sum }_{k\ne i,j}{\alpha }_k{y}_k=\zeta (\text{常数})$，可用${\alpha }_1$表示${\alpha }_2$，将问题转换为单变量二次函数优化。然后求导找极值点可得：
   ${\alpha }_j^{\text{new}}={\alpha }_j^{\text{old}}+\frac{y_j(E_i-E_j)}{\eta },\eta =K(x_i,x_i)+K(x_j,x_j)-2K(x_i,x_j)$
   其中$K(x_i,x_j)=x_i\ast x_j$，称为线性核。$\eta =\Vert {\mathbf{x}}_i-{\mathbf{x}}_j{\Vert }^2$（几何意义：两个样本的欧氏距离平方）。
   然后对 ${\alpha }_j^{\text{new}}$ 进行剪裁，也就是约束其在可行域内：
   $${\alpha }_2^{\text{new,clipped}}=\{\begin{array}{ll}H& \text{if }{\alpha }_2^{\text{new}}>H\\ L& \text{if }{\alpha }_2^{\text{new}}<L\\ {\alpha }_2^{\text{new}}& \text{otherwise}\end{array}$$

   其中：

   • 若 $y_i\ne y_j$，则：$L=\max (0,{\alpha }_j^{\text{old}}-{\alpha }_i^{\text{old}}),H=+\infty$
   • 若 $y_i=y_j$，则：$L=\max (0,{\alpha }_i^{\text{old}}+{\alpha }_j^{\text{old}}-\zeta ),H=+\infty$

   然后更新 ${\alpha }_i$：
   ${\alpha }_1^{\text{new}}={\alpha }_1^{\text{old}}+y_1{y}_2({\alpha }_2^{\text{old}}-{\alpha }_2^{\text{new,clipped}})$。

4. 更新阈值 $b$ 和误差缓存

   • 根据新 ${\alpha }_i$ 和 ${\alpha }_j$ 计算阈值 $b$。
   • 更新所有样本的误差缓存 $E_i$，用于后续变量选择。

5. 收敛判断
   重复上述步骤，直到所有 ${\alpha }_i$ 满足KKT条件，或达到最大迭代次数。

3 优化

3.1 软间隔

允许部分样本不满足约束，引入松弛变量 ${\xi }_i\ge 0$，优化目标变为：
$$\{\begin{array}{l}{\min }_{x,b}\frac{1}{2}{w}^{T}w+C{\sum }_{i=1}^n{\xi }_i\\ s.t.1-y_i(w^T{x}_i+b)\le {\xi }_i,{\xi }_i\ge 0,i=1,2,...N\end{array}$$
其中 $C$ 是惩罚参数，控制分类错误与间隔的权衡。

3.2 核技巧（Kernel Trick）

当数据线性不可分时，可以通过映射 $\phi(x)$ 将数据投影到高维空间，使其线性可分。
为了避免显式计算高维内积 $\varphi (x_i)\cdot \varphi (x_j)$，可以直接使用核函数 ( K(x_i, x_j) ) 代替。
常用核函数：

• 线性核：$K(x_i,x_j)=x_i\cdot x_j$
• 多项式核：$K(x_i,x_j)=(x_i\cdot x_j+c{)}^d$
• 高斯核（RBF）：$K(x_i,x_j)=\exp \left(-\frac{\Vert x_i-x_j{\Vert }^2}{2{\sigma }^2}\right)$

2.5的优化目标变为：
$$\{\begin{array}{l}{\min }_{\alpha }[\frac{1}{2}{\sum }_{i=1}^N{\sum }_{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_{j}K(x_i,x_j)-{\sum }_{i=1}^N{\alpha }_i]\\ s.t.{\sum }_{i=1}^N{\alpha }_i{y}_i=0,{\alpha }_i\ge 0\end{array}$$