​

6. 支持向量机（Support Vector Machine，SVM）

6.1. 相关概念

6.1.1. 分类

• 硬间隔（Hard-margin）SVM，又叫最大间隔分类SVM；
• 软间隔（Soft-margin）SVM；
• 核（Kernel）SVM；

6.2. 硬间隔SVM

6.2.1. 问题定义：

  之前的分类算法中，模型致力于寻找一个超平面，可以将训练集中的两类样本分开，但这个超平面理论上存在无数个，它们在训练集上的分类效果可能是相同的，但模型的鲁棒性是不同的，为了寻找最鲁棒的模型，SVM便想要寻找一个所有样本总间隔最大的超平面。
  首先定义间隔：假设通过一个超平面 $f(\vec{x})=sign\left({\vec{w}}^T\vec{x}+b\right)$，可以完美拟合训练集所有样本，即对任意样本 $i$，都有 $y_i({\vec{w}}^T{\vec{x}}_i+b)>0$，则所有样本中最小的间隔为 $\text{margin}(\vec{w})=\underset{\vec{w},{\vec{x}}_i}{\min }\frac{1}{\Vert \vec{w}\Vert }\left|\vec{w}{\vec{x}}_i+b\right|$。
因此硬间隔SVM的优化目标即为最大化这个间隔，使得分类边界具有最高的鲁棒性，即
$$\begin{array}{rl}\underset{\vec{w}}{\max }\text{margin}(\vec{w})& =\underset{\vec{w}}{\max }\underset{{\vec{x}}_i}{\min }\frac{1}{\Vert \vec{w}\Vert }\left|{\vec{w}}^T{\vec{x}}_i+b\right|\\ & =\underset{\vec{w},b}{\max }\frac{1}{\Vert \vec{w}\Vert }\underset{{\vec{x}}_i}{\min }\left|{\vec{w}}^T{\vec{x}}_i+b\right|,\end{array}\text{\hspace{1em}(6.1)}$$

6.2.2. 问题化简：

  因为 yi∈{−1,1}y_i\in \{-1,1\}yi​∈{−1,1}，所以可以写作 $\left|{\vec{w}}^T{\vec{x}}_i+b\right|=y_i({\vec{w}}^T{\vec{x}}_i+b)$，因此优化目标可以写作$\underset{\vec{w},b}{\max }\text{margin}(\vec{w})=\underset{\vec{w},b}{\max }\frac{1}{\Vert \vec{w}\Vert }\underset{{\vec{x}}_i}{\min }{y}_i({\vec{w}}^T{\vec{x}}_i+b)$
  又因为对超平面 $\vec{w}$，我们只关心其方向，对 $\Vert \vec{w}\Vert$ 无要求，因此对 ${\vec{w}}^T{\vec{x}}_i+b$ 我们只关心正负，无所谓值的大小，因此对 $y_i({\vec{w}}^T{\vec{x}}_i+b)$ 我们只关心是否大于0，无所谓值的大小。因此为了简化优化目标，可以令 $\underset{\vec{w},{\vec{x}}_i,b}{\min }{y}_i({\vec{w}}^T{\vec{x}}_i+b)=1$，则优化目标变为
$$\begin{array}{r}\underset{\vec{w}}{\max }\text{margin}(\vec{w})=\{\begin{array}{c}\underset{\vec{w}}{\max }\frac{1}{\Vert \vec{w}\Vert }\cdot 1=\underset{\vec{w}}{\min }\Vert \vec{w}\Vert =\underset{\vec{w}}{\min }{\vec{w}}^T\vec{w}\\ \text{s.t.}{y}_i({\vec{w}}^T{\vec{x}}_i+b)⩾1\end{array}.\end{array}\text{\hspace{1em}(6.2)}$$
变为一个凸优化问题。

6.2.3. 问题求解：

  优化问题首先考虑使用拉格朗日乘数法：

• $\mathcal{L}(\vec{w},\vec{\lambda },b)={\vec{w}}^T\vec{w}+{\sum }_{i=1}^N{\lambda }_i\left[1-y_i({\vec{w}}^T{\vec{x}}_i+b)\right]$
  ，将带约束的原问题变为无约束优化问题：$\{\begin{array}{c}\underset{\vec{w},b}{\min }\underset{\vec{\lambda }}{\max }\mathcal{L}(\vec{w},\vec{\lambda },b)\\ s.t.{\lambda }_i⩾0\end{array}$.
• 若原问题的约束 $y_i({\vec{w}}^T{\vec{x}}_i+b)⩾1$ 不满足，即 $1-y_i({\vec{w}}^T{\vec{x}}_i+b)>0$，则 $\underset{\vec{\lambda }}{\max }\mathcal{L}(\vec{w},\vec{\lambda },b)\to \infty$，反之若都满足，则 $\underset{\vec{\lambda }}{\max }\mathcal{L}(\vec{w},\vec{\lambda },b)={\vec{w}}^T\vec{w}$，因此优化目标其实是 $\{\begin{array}{c}\underset{\vec{w}}{\min }(\infty ,{\vec{w}}^T\vec{w})\\ s.t.{\lambda }_i⩾0\end{array}$，因此这个优化目标函数为了取到 $\underset{\vec{w}}{\min }(\infty ,{\vec{w}}^T\vec{w})={\vec{w}}^T\vec{w}$，会调整 $\vec{w}$ 使得 $y_i({\vec{w}}^T{\vec{x}}_i+b)⩾1$ 对所有 ${\hat{\vec{x}}}_i$ 都满足，由此原问题的约束成立。
• 而此时 $\mathcal{L}(\vec{w},\vec{\lambda },b)={\vec{w}}^T\vec{w}+{\sum }_{i=1}^N{\lambda }_i\left[1-y_i({\vec{w}}^T{\vec{x}}_i+b)\right]={\vec{w}}^T\vec{w}$，因此对任意 $i$，有 ${\lambda }_i\left[1-y_i({\vec{w}}^T{\vec{x}}_i+b)\right]=0$，则 ${\lambda }_i=0$ 或 $1-y_i({\vec{w}}^T{\vec{x}}_i+b)=0$，由于绝大多数情况，只有两个点离超平面最近（存在更多点距离超平面也是0的理论可能，但实际数据中几乎不存在），即 $1-y_i({\vec{w}}^T{\vec{x}}_i+b)=0$，其他情况都是${\lambda }_i=0$（但这里不能直接带入 ${\lambda }_i=0$，因为这个是目标函数为了达到优化而隐含的约束，如果直接带入则变成了优化之间的已知约束，问题会变得无法求解）。
  
• 这两个距离最近的样本我们称其为 ${\vec{x}}_m$（$y_m=1$）和 ${\vec{x}}_n$（$y_n=-1$），这两个向量被称为支持向量。

  变为对偶问题：

• 弱对偶关系：$\min \max F⩾\max \min F$（宁做凤尾，不做鸡头），当中间取等号时变为强对偶关系，而线性约束的二次优化问题天然满足强对偶性（此处不做数学证明）$\{\begin{array}{c}\underset{\vec{\lambda }}{\max }\underset{\vec{w},b}{\min }\pounds (\vec{w},\vec{\lambda },b)\\ s.t.{\lambda }_i⩾0\end{array}$.
• 因此这里可以将优化目标变为 $\{\begin{array}{c}\underset{\vec{\lambda }}{\max }\underset{\vec{w},b}{\min }\pounds (\vec{w},\vec{\lambda },b)\\ \text{s.t.}{\lambda }_i⩾0\end{array}$。

  求偏导得到结果：

• $\frac{\partial \mathcal{L}}{\partial b}=-{\sum }_{i=1}^N{\lambda }_i{y}_i=0$。
• $\frac{\partial \mathcal{L}}{\partial \vec{w}}=2\vec{w}-{\sum }_{i=1}^N{\lambda }_i{y}_i{\vec{x}}_i=0\Rightarrow {\vec{w}}^{\ast }=\frac{1}{2}{\sum }_{i=1}^N{\lambda }_i{y}_i{\vec{x}}_i$.
• 则$$\begin{array}{rl}\mathcal{L}(\vec{w},\vec{\lambda },b)& =\frac{1}{4}\sum _{i=1}^N\sum _{j=1}^N{\lambda }_i{\lambda }_j{y}_i{y}_j({\vec{x}}_i^T{\vec{x}}_i)-\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\lambda }_i{\lambda }_j{y}_i{y}_j({\vec{x}}_i^T{\vec{x}}_i)+\sum _{i=1}^N{\lambda }_i\\ & =-\frac{1}{4}\sum _{i=1}^N\sum _{j=1}^N{\lambda }_i{\lambda }_j{y}_i{y}_j({\vec{x}}_i^T{\vec{x}}_i)+\sum _{i=1}^N{\lambda }_i.\end{array}\text{\hspace{1em}(6.3)}$$

  因为对 $\{\begin{array}{c}\underset{\vec{\lambda }}{\max }\underset{\vec{w},b}{\min }\mathcal{L}(\vec{w},\vec{\lambda },b)\\ \text{s.t.}{\lambda }_i⩾0\end{array}$ 的优化必须使 $\vec{\lambda }$ 和 $\vec{w}$ 满足：只有两个点 ${\vec{x}}_m$ 和 ${\vec{x}}_n$ 离超平面最近，即 $1-y_i({\vec{w}}^T{\vec{x}}_i+b)=0$，其他情况都是 ${\lambda }_i=0$，将这个条件带入 ${\sum }_{i=1}^N{\lambda }_i{y}_i=0$ 可得：${\lambda }_m={\lambda }_n,{\lambda }_{i\ne m,n}=0$。

  带入目标函数得 $\mathcal{L}(\vec{w},\vec{\lambda },b)=-\frac{1}{4}\left({\lambda }_m^2({\vec{x}}_m^T{\vec{x}}_m)+{\lambda }_n^2({\vec{x}}_n^T{\vec{x}}_n)-2{\lambda }_m{\lambda }_n({\vec{x}}_m^T{\vec{x}}_n)\right)+{\lambda }_m+{\lambda }_n=-\frac{1}{4}{\lambda }_m^2\Vert {\vec{x}}_m-{\vec{x}}_n\Vert +2{\lambda }_m$，对其求偏导：$\frac{\partial \mathcal{L}}{\partial {\lambda }_m}=-\frac{1}{2}{\lambda }_m\Vert {\vec{x}}_m-{\vec{x}}_n\Vert +2=0\Rightarrow {\lambda }_m=\frac{4}{\Vert {\vec{x}}_m-{\vec{x}}_n\Vert }$，带入原式得 $\begin{array}{r}\mathcal{L}(\vec{w},\vec{\lambda },b)=-\frac{1}{4}{\lambda }_m^2\Vert {\vec{x}}_m-{\vec{x}}_n\Vert +2{\lambda }_m=\frac{4}{\Vert {\vec{x}}_m-{\vec{x}}_n\Vert }\end{array}$，因此 $\max \mathcal{L}(\vec{w},\vec{\lambda },b)=\min \Vert {\vec{x}}_m-{\vec{x}}_n\Vert$，找到两个类中，间距最小的两个样本，计算其欧氏距离可以算得 $\vec{\lambda }$。

  再带入 ${\vec{w}}^{\ast }={\sum }_{i=1}^N{\lambda }_i{y}_i{\vec{x}}_i={\lambda }_m({\vec{x}}_m-{\vec{x}}_n)$，$b^{\ast }=y_m-{\lambda }_m{\vec{x}}_m^T({\vec{x}}_m-{\vec{x}}_n)$ 即可得到分类边界。

6.3. 软间隔SVM

6.3.1. 引入软间隔的思想

  硬间隔SVM假设所有样本都可以被完美分类，但实际情况很难做到，因此需要允许一些错误，但又要尽可能控制错误，便有了软间隔SVM的思想。

  相比于硬间隔，软间隔SVM取消了约束 $\text{s.t.}{y}_i({\vec{w}}^T{\vec{x}}_i+b)⩾1$，而是采用一个损失函数来代替，即设定一组参数 ξ⃗={ξ1,ξ2,⋯ ,ξN}, ξi⩾0\vec{\xi}=\{ \xi_1, \xi_2, \cdots, \xi_N\}, \ \xi_i \geqslant 0ξ ​={ξ1​,ξ2​,⋯,ξN​}, ξi​⩾0，目标函数变为 $\{\begin{array}{c}\underset{\vec{w},b,\vec{\xi }}{\min }{\vec{w}}^T\vec{w}+C{\sum }_{i=1}^N{\xi }_i\\ \text{s.t.}{y}_i({\vec{w}}^T{\vec{x}}_i+b)⩾1-{\xi }_i,{\xi }_i⩾0\end{array}$

  通过这个目标函数，原本间隔外的点（$y_i({\vec{w}}^T{\vec{x}}_i+b)⩾1$）的参数 ${\xi }_i$ 会被优化到0，而间隔内的点无论是否可以被分类正确，都可以尽可能使其向两边分散。

  $C$ 是一个乘法因子，可以作为模型超参数，其作用有点像正则化，$C$ 的值越大，$\vec{\xi }$ 被惩罚得越厉害，间隔小的点越少。

6.3.2. 软间隔SVM的求解

  前面的部分和硬间隔相同，化为无约束目标函数和对偶优化问题，分别对 $\vec{w}$ 和 $b$ 求偏导后，最终目标函数化简如下：$\{\begin{array}{c}\underset{\vec{\lambda }}{\min }\frac{1}{4}{\sum }_{i=1}^N{\sum }_{j=1}^N{\lambda }_i{\lambda }_j{y}_i{y}_j({\vec{x}}_i^T{\vec{x}}_i)-{\sum }_{i=1}^N{\lambda }_i\\ s.t.0⩽{\lambda }_i⩽C,{\sum }_{i=1}^N{\lambda }_i{y}_i=0\end{array}$，${\vec{w}}^{\ast }=\frac{1}{2}{\sum }_{i=1}^N{\lambda }_i{y}_i{\vec{x}}_i$.

  同样先求得 $\vec{\lambda }$ 后（这里需要用到SMO迭代求解算法，过于复杂，后补），即可得到超平面。
​