1 硬间隔SVM

1.1 由感知机到SVM

假设样本点是线性可分的，感知机模型的思想是：利用分割超平面$\vec{w}\cdot \vec{x}+b=0$将样本点划分为两类；假设存在误分类点，则通过使误分类点到分割超平面的距离最小来不断调整超平面，直到所有误分类点被纠正后迭代停止。

感知机模型的表达式如下：

$$h(x)=sign(wx+b)=\left\{\begin{matrix} -1, & wx+b<0 \\ 1, & wx+b>0 \end{matrix}\right. \tag{1.1}$$

由于初始的$w$和b的取值不同，因此最后得到的分割超平面也可能不同，所以感知机模型的分割超平面$wx+b=0$有多个。

既然这样，那么能不能进一步找到一个最优的分割超平面呢？办法就是下面介绍的支持向量机(Support Vector Machines, SVM)模型。

SVM模型和感知机模型一样，也是一种二分类模型，SVM的思想是：不仅要让样本点被分割超平面分开，还希望那些距离分割超平面最近的点到分割超平面的距离最大。

1.2 公式推导与求解

1.2.1 公式推导

假设样本点$(x_i, y_i)$到超平面$wx+b=0$的几何间距为$\gamma _i$，则：

$$\gamma _i=\frac{\left | wx_i+b \right | }{\left \| w \right \| } \tag{1.2}$$

又因为$\left | y_i \right | =1$恒成立，且对于正确分类点$y_i\times (wx_i+b)>0$恒成立，所以进一步有：

$$\gamma _i=\frac{\left | wx_i+b \right | }{\left \| w \right \| } =\frac{|y_i|\cdot \left | wx_i+b \right | }{\left \| w \right \| }=\frac{ \left | y_i\cdot (wx_i+b) \right | }{\left \| w \right \| }=\frac{ y_i\cdot (wx_i+b)}{\left \| w \right \| } \tag{1.3}$$

取训练数据集T中距离超平面的最小几何间距$\min_{} \gamma _i,(i=1,2,…,M)$作为数据集T关于超平面$wx+b=0$的几何间距，记为$\gamma$，即：$\gamma=\min_{} \gamma _i,(i=1,2,…,M)$，按照SVM的思想，即需要求解以下优化问题：

$$\begin{align*} \max_{w,b}\gamma & \\ s.t. \gamma _i\ge \gamma , & i=1,2,...,M \end{align*} \tag{1.4}$$

即：

$$\begin{align*} \max_{w,b}\gamma & \\ s.t. \frac{ y_i\cdot (wx_i+b)}{\left \| w \right \| }\ge \gamma , & i=1,2,...,M \end{align*} \tag{1.5}$$

令：

$$\begin{align*} M=\frac{w}{||w||\gamma } \\ N=\frac{b}{||w||\gamma } \end{align*} \tag{1.6}$$

则约束条件为：$s.t. y_i(M\cdot x_i+N)\ge 1$，优化目标为$\gamma$最大，由：$||M||=\frac{||w||}{||w||\gamma }=\frac{1}{\gamma } $，因此最大化$\gamma$，即最小化$\frac{1}{2}||M||^2 $，则整个优化问题转化为：

$$\begin{align*} \min_{M,N} \frac{1}{2}||M||^2 \\ s.t. y_i(Mx_i+N)\ge 1 \end{align*} \tag{1.7}$$

重写为：

$$\begin{align*} \min_{w,b} \frac{1}{2}||2||^2 \\ s.t. y_i(wx_i+b)\ge 1,i=1,2,...,M \end{align*} \tag{1.8}$$

这是一个含有不等式约束的凸二次规划问题，可以对其使用拉格朗日乘子法得到其对偶问题。

1.2.2 求最优解

首先，我们将有约束条件的原始目标函数转换为无约束的新构造的拉格朗日目标函数：

$$L(w,b,\alpha )=\frac{1}{2}||w||^2 - {\textstyle \sum_{i=1}^{M}} \alpha _i(y_i(wx_i+b)-1) \tag{1.9}$$

其中$\alpha _i$为拉格朗日乘子，且$\alpha _i\ge 0$，令：$\theta (w)=\max_{\alpha _i\ge 0} L(w,b,\alpha )$，当样本点不满足约束条件时，即在可行解区域外：$y_i(wx_i+b)<1$，此时，将$\alpha _i$设置为无穷大，则$\theta(w)$也为无穷大。

当样本点满足约束条件时，即在可行解区域内：$y_i(wx_i+b)\ge1$，此时$\theta(w)$为原函数本身，于是，合并两种情况得到新的目标函数：

$$\theta (w)=\left\{\begin{matrix} \frac{1}{2}||w||^2,x\in 可行区域 \\ +\propto ,x\in 不可行区域 \end{matrix}\right. \tag{1.10}$$

原约束问题等价于：

$$\min_{w,b}\theta (w)=\min_{w,b}\max_{\alpha _i\ge 0}L(w,b,\alpha )=p^{\ast } \tag{1.11}$$

新的目标函数先求最大值，再求最小值，这样的话首先要面对带有需要求解的参数$w$和$b$的方程，而$\alpha_i$又是不等式约束，求解过程不好做，所以我们需要使用拉格朗日函数对偶性，将最小和最大位置互换，得到：

$$\max_{\alpha _i\ge 0}\min_{w,b}L(w,b,\alpha )=d^{\ast } \tag{1.12}$$

要有$p^{\ast }=d^{\ast }$，需要满足两个条件：

1) 优化问题是凸优化问题；

2) 满足KKT条件；

本优化问题显然是一个凸优化问题，因此条件1满足，对于条件2，即要求：

$$\left\{\begin{matrix} \alpha _i\ge 0 \\ y_i(wx_i+b)-1\ge 0 \\ \alpha _i(y_i(wx_i+b)-1)=0 \end{matrix}\right. \tag{1.13}$$

为了得到求解对偶问题的具体形式，令$L(w,b,\alpha)$对$w$和$b$求偏导为0，可得：

$$\begin{align*} w= {\textstyle \sum_{i=1}^{N}}\alpha _iy_ix_i \\ {\textstyle \sum_{i=1}^{N}}\alpha _iy_i=0 \end{align*} \tag{1.14}$$

将式(1.14)代入拉格朗日目标函数，即式(1.9)，消去$w$和$b$得到：

$$\begin{aligned} L(w,b,\alpha )&=\frac{1}{2} {\textstyle \sum_{i=1}^{M}} {\textstyle \sum_{j=1}^{M}}\alpha _i\alpha _jy_iy_j(x_i\cdot x_j)- {\textstyle \sum_{i=1}^{M}}\alpha _iy_i(( {\textstyle \sum_{j=1}^{M}}\alpha _jy_jx_j)\cdot x_i+b)+ {\textstyle \sum_{i=1}^{M}}\alpha_i \\ &=-\frac{1}{2} {\textstyle \sum_{i=1}^{M}} {\textstyle \sum_{j=1}^{M}}\alpha _i\alpha _jy_iy_j(x_i\cdot x_j)+ {\textstyle \sum_{i=1}^{M}}\alpha _i \end{aligned}\tag{1.15}$$

即：

$$\min_{w,b}L(w,b,\alpha ) =\min_{w,b} -\frac{1}{2} {\textstyle \sum_{i=1}^{M}} {\textstyle \sum_{j=1}^{M}}\alpha _i\alpha _jy_iy_j(x_i\cdot x_j)+ {\textstyle \sum_{i=1}^{M}}\alpha _i \tag{1.16}$$

求$\min_{w,b}L(w,b,\alpha )$对$\alpha$的极大，即是对偶问题：

$$\begin{align*} \max_{\alpha } -\frac{1}{2} {\textstyle \sum_{i=1}^{M}} {\textstyle \sum_{j=1}^{M}}\alpha _i\alpha _jy_iy_j(x_i\cdot x_j)+ {\textstyle \sum_{i=1}^{M}}\alpha _i \\ s.t. {\textstyle \sum_{i=1}^{M}}\alpha _iy_i=0 \\ \alpha _i \ge 0,i=1,2,...,N \end{align*} \tag{1.17}$$

把目标式子加一个负号，求解最大转换为求解最小:

$$\begin{align*} \min_{\alpha } \frac{1}{2} {\textstyle \sum_{i=1}^{M}} {\textstyle \sum_{j=1}^{M}}\alpha _i\alpha _jy_iy_j(x_i\cdot x_j)- {\textstyle \sum_{i=1}^{M}}\alpha _i \\ s.t. {\textstyle \sum_{i=1}^{M}}\alpha _iy_i=0 \\ \alpha _i \ge 0,i=1,2,...,N \end{align*} \tag{1.18}$$

现在我们的优化问题变成了公式(1.18)，对于这个问题，有更高效的优化算法，即序列最小优化（SMO）算法，通过SMO算法可以得到$\alpha ^{\ast } $ ，在根据$\alpha ^{\ast } $可以求解出$w$和$b$，进而求得最初的目标：找到最优决策平面。

前面的推导都是基于KKT条件成立的假设进行的，KKT条件如下：

$$\left\{\begin{matrix} \alpha _i\ge 0\\ y_i(w_i\cdot x_i+b)-1\ge 0\\ \alpha _i(y_i(w_i\cdot x_i+b)-1)=0 \end{matrix}\right. \tag{1.19}$$

另外根据前面的推导，下面公式成立：

$$\begin{align*} w= {\textstyle \sum_{i=1}^{M}}\alpha _iy_ix_i \\ {\textstyle \sum_{i=1}^{M}}\alpha _iy_i=0 \end{align*} \tag{1.20}$$

由此可知，在$\alpha ^{\ast } $中，至少存在一个$\alpha _j ^{\ast }>0$(若全为0，则$w=0$，矛盾)，对此$j$有：$y_j(w^*\cdot x_j+b^{\ast })-1=0$，因此得到：

$$w^{\ast }= {\textstyle \sum_{i=1}^{M}}\alpha _i^{\ast }y_ix_i$$ $$b^{\ast }= y_j-{\textstyle \sum_{i=1}^{M}}\alpha _i^{\ast }y_i(x_i \cdot x_j) \tag{1.21}$$

对于任意训练样本$(x_i,y_i)$，总有$\alpha_i=0$
或者$y_j(wx_j+b)=1$,。若$\alpha_i=0$，则该样本不会再最后求解模型参数的式子中出现，若$\alpha_i>0$，则必有$y_j(wx_j+b)=1$，所对应的样本点位于最大间隔边界上，是一个支持向量，这显示出SVM的一个重要特性：训练完成后，大部分的训练样本都不需要保留，最终模型只跟支持向量相关。

1.2.3 小结

总结一下线性可分SVM模型的过程：

输入：

线性可分训练集$T=\left \{ (x_1,y_1),(x_2,y_2),…,(x_M,y_M) \right \} $，且$y_i \in\left \{ -1,1 \right \} ,i=1,2,…,M$。

输出：

分割超平面$wx+b=0$和分类决策函数$h(x)=sign(wx+b)$。

步骤如下：

第1步：构造约束优化问题：

$$\begin{align*} \min_{\alpha } \frac{1}{2} {\textstyle \sum_{i=1}^{M}} {\textstyle \sum_{j=1}^{M}}\alpha _i\alpha _jy_iy_j(x_i\cdot x_j)- {\textstyle \sum_{i=1}^{M}}\alpha _i \\ s.t. {\textstyle \sum_{i=1}^{M}}\alpha _iy_i=0 \\ \alpha _i \ge 0,i=1,2,...,N \end{align*} \tag{1.22}$$

第2步：利用SMO算法求解上面的优化问题，得到$\alpha$向量的值$\alpha ^\ast $；

第3步：利用公式1.21计算$w$向量的值$w ^\ast $；

第4步：找到满足$\alpha _{s}^{\ast } >0$对应的支持向量点$(x_s,y_s),s=1,2,…,S$，利用公式1.21计算$b^{\ast }$；

第5步：由$w ^\ast $和$b^{\ast }$得到分割超平面$w^{\ast }x+b^{\ast }=0$和分类决策函数$h(x)=sign(w^{\ast }x+b^{\ast })$。

2 软间隔SVM

硬间隔SVM模型虽然比感知机具有更好的鲁棒性，但其前提是要求样本数据点线性可分，在实际问题中，不同类别的样本点可能会存在混叠，针对这种情况，可以通过增加松弛因子来解决。

线性可分SVM模型的原始优化问题为公式(1.8)，考虑到实际情况下存在样本混叠，所以为每一个样本点$(x_i,y_i)$增加一个对应的松弛变量$\xi _i,\xi _i\ge 0$，则约束条件变为：$y_i(wx_i+b)\ge 1-\xi_i,i=1,2,…,M$，因为$1-\xi_i\le1$，所以这相当于在原来的基础上对每个样本点$(x_i,y_i)$降低了限制要求，这个特权可以随便给吗？显然不行，如果只是给予各个样本点特权而不对其进行适当的约束，那么这个模型之前建立的约束就变得毫无意义了，所以SVM模型采取的措施是：每个样本点在软间隔里面享受了优惠，对应的就要在优化问题里面接受惩罚，具体就是在优化目标里面加上一个惩罚项$c\xi_i$，所以原来的优化问题变为：

$$\min_{w,b}\frac{1}{2}||w||^2 +c\sum_{i=1}^{M}\xi _i \tag{2.1}$$

约束条件：

$$\begin{align*} s.t. y_i(wx_i+b)\ge 1-\xi_i \\ \xi _i\ge 0,i=1,2,...,M \end{align*}$$

其中$c>0$是一个惩罚参数。

采取跟硬间隔SVM类似的步骤，先将优化问题(2.1)转换为对偶优化问题，然后依次求解出拉格朗日乘子向量、权重向量$w$和偏置常数b，得到分割超平面和分类决策函数。

3 合页损失函数

硬间隔SVM和软间隔SVM都叫做线性SVM，是一种线性模型，线性SVM还有另外一种解释，就是最小化如下目标函数：

$$\min_{w,b}\sum_{i=1}^{M}[1-y_i(wx_i+b)]_{+}+\lambda ||w||^2 \tag{3.1}$$

式中第一项$[1-y_i(wx_i+b)]_{+}$称为合页损失函数，如:

$$[z]_{+}=\left\{\begin{matrix} z,z>0\\ 0,z\le 0 \end{matrix}\right.\tag{3.2}$$

第二项是正则化项。

由公式3.2可知:

$$[1-y_i(wx_i+b)]_{+}=\left\{\begin{matrix} 1-y_i(wx_i+b),y_i(wx_i+b)<1\\ 0,y_i(wx_i+b)\ge 1 \end{matrix}\right. \tag{3.3}$$

当样本点$(x_i,y_i)$被正确分类且函数间隔$y_i(wx_i+b)$大于1时，损失是0，否则损失是$1-y_i(wx_i+b)$。

令$[1-y_i(wx_i+b)]_{+}=\xi_i$，则$\xi_i\ge0$成立，且有：

1) 当$1-y_i(wx_i+b)>0$时，有$y_i(wx_i+b)=1-\xi_i$；

2) 当$1-y_i(wx_i+b)\le0$时，有$\xi_i=0$，即$y_i(wx_i+b)\ge1-\xi_i$；

综合1)和2)可知$y_i(wx_i+b)\ge1-\xi_i$恒成立。

进一步，取$\lambda=\frac{1}{2c}$，则公式(3.1)等价于如下约束优化问题：

$$\min_{w,b,\xi } \frac{1}{c}(\frac{1}{2}||w||^2+c\sum_{i=1}^{M}\xi _i ) \tag{3.4}$$

约束条件：

$$\begin{align*} s.t. y_i(wx_i+b)\ge 1-\xi _i,i=1,2,...,M \\ \xi _i\ge 0,i=1,2,...,M \end{align*}$$

公式(3.4)就是前面软间隔支持向量机模型的原始最优化问题，即公式(2.1)。

即软间隔SVM模型的原始最优化问题等价于最小化合页损失，从损失函数的角度证明了线性SVM模型的合理性。

4 非线性SVM

对于输入空间中的非线性问题，可以通过非线性变换将它转换为某个维度特征空间中的线性分类问题，在高维特征空间中学习线性SVM。由于线性SVM学习的对偶问题里，目标函数和分类决策函数都只涉及实例和实例之间的内积，所以不需要显示指定非线性变换，而是用核函数替换当中的内积。核函数表示，通过一个非线性变换后的两个实例健的内积，具体地，$K(x,z)$是一个函数，或正定核，意味着存在一个从输入空间到特征空间的映射$\phi (x)$，对任意输入空间中的$x,z$，有：$K(x,z)=\phi(x)\cdot\phi(z)$，在线性SVM学习的对偶问题中，用核函数$K(x,z)$替代内积，求解得到的就是非线性SVM：

$$f(x)=sign(\sum_{i=1}^{M}\alpha _i^\ast y_iK(x,x_i)+b^\ast ) \tag{4.1}$$

综合以上讨论，可以得到非线性SVM的学习算法如下：

输入：

训练数据集$T=\left \{ (x_1,y_1),(x_2,y_2),…,(x_M,y_M) \right \} ,其中y_i\int \left \{ +1,-1 \right \} ,i=1,2,…,M$；

输出：分离超平面和分类决策函数；

1) 选择适当的核函数$K(x,z)$和惩罚参数$c>0$，构造并求解凸二次规划问题:

$$\min_{\alpha }\frac{1}{2}\sum_{i=1}^{M}\sum_{j=1}^{M}\alpha _i\alpha _jy_iy_jK(x_i,x_j)-\sum_{i=1}^{M}\alpha _i$$

约束条件：

$$\begin{align*} s.t. \sum_{i=1}^{M}\alpha _iy_i=0 \\ 0\le \alpha _i\le c,i=1,2,...,M \end{align*}$$

2) 计算

选择$\alpha ^\ast $的一个分量$\alpha_j ^\ast $满足条件$0 < \alpha_j ^\ast < c$，计算$b^\ast =y_j-\sum_{i=1}^{M}\alpha _i^\ast y_iK(x_i,x_j)$

3) 得到分类决策函数，即公式(4.1)。