软间隔最大化SVM

假设有训练集：
$T=\{(x_1, y_1),(x_2, y_2),...,(x_m, y_m)\}$T={(x1​,y1​),(x2​,y2​),...,(xm​,ym​)}
其中$y_i \in \{-1, +1\}$yi​∈{−1,+1}。再假设数据集线性不可分，即数据中存在一些异常值(离群点)，若去除这些异常值，剩下的大部分样本仍然线性可分。

对于线性可分的情况，样本点都满足下面的条件$y_i(w^T x_i +b) \geq 1$yi​(wTxi​+b)≥1。而线性不可分意味着某些样本不满足函数间隔大于等于1的约束条件，我们引入变量$loss$loss用于表示样本偏离$y_i(w^T x_i +b) \geq 1$yi​(wTxi​+b)≥1的距离。

如果$y_i(w^T x_i +b) \geq 1$yi​(wTxi​+b)≥1，则$loss=0$loss=0。

如果不满足条件，即$y_i(w^T x_i +b) \lt 1$yi​(wTxi​+b)<1时，则必须加上loss才能最低限度的符合条件：$y_i(w^T x_i +b) +loss = 1$yi​(wTxi​+b)+loss=1，因此$loss = 1-y_i(w^T x_i +b) $。

于是有：
$loss = \max\{0, 1-y_i(w^T x_i +b) \}$loss=max{0,1−yi​(wTxi​+b)}
为此，我们可以引入松弛变量$\xi_i \geq 0$ξi​≥0用于表示loss，使得函数间隔加上松弛变量后始终满足大于等于1的条件：
$y_i(w^T x_i +b) + \xi_i \geq 1$yi​(wTxi​+b)+ξi​≥1
于是约束条件可以变为：
$1 - \xi_i - y_i(w^T x_i +b) \leq 0$1−ξi​−yi​(wTxi​+b)≤0
加入松弛变量后，样本到超平面的函数距离的要求放松了，在预期的函数间隔内允许一定程度上的误分类情况，因此称之为软间隔。同时，对引入的每个松弛变量都加上一定大小的惩罚，得到软间隔最大化的SVM学习条件如下：
$min\;\; \frac{1}{2}||w||^2 +C\sum\limits_{i=1}^{m}\xi_i$min21​∣∣w∣∣2+Ci=1∑m​ξi​
其中，C为惩罚系数，用于指定对误分类情况的惩罚力度。也就是说，我们希望$\frac{1}{2}||w||^2$21​∣∣w∣∣2尽量小的同时，误分类点也尽可能的少，C用于协调二者。最终得到凸二次规划的问题为：
$\begin{aligned} &\min\limits_{w,b,\xi} \;\; \frac{1}{2}||w||^2 +C\sum\limits_{i=1}^{m}\xi_i \\ &s.t. \;\; 1 - \xi_i - y_i(w^T x_i +b) \leq 0 \;\;(i =1,2,...m) \\ &\xi_i \geq 0 \;\;(i =1,2,...m) \end{aligned} \tag 1$​w,b,ξmin​21​∣∣w∣∣2+Ci=1∑m​ξi​s.t.1−ξi​−yi​(wTxi​+b)≤0(i=1,2,...m)ξi​≥0(i=1,2,...m)​(1)

学习的对偶算法

首先用拉格朗日函数转化原始的约束问题为无约束问题：
$L(w,b,\xi,\alpha,\mu) = \frac{1}{2}||w||^2 +C\sum\limits_{i=1}^{m}\xi_i + \sum\limits_{i=1}^{m}\alpha_i[1 - \xi_i - y_i(w^T x_i +b)] + \sum\limits_{i=1}^{m}\mu_i(-\xi_i)$L(w,b,ξ,α,μ)=21​∣∣w∣∣2+Ci=1∑m​ξi​+i=1∑m​αi​[1−ξi​−yi​(wTxi​+b)]+i=1∑m​μi​(−ξi​)
其中$\alpha_i \geq 0，\mu_i \geq 0$αi​≥0，μi​≥0 均为拉格朗日乘子。于是要优化的目标函数为：
$\min\limits_{w,b,\xi} \;\max\limits_{\alpha_i \geq 0, \;\mu_i \geq 0} L(w,b,\alpha, \xi,\mu)$w,b,ξmin​αi​≥0,μi​≥0max​L(w,b,α,ξ,μ)
本问题满足KKT条件，转换为对偶问题可得：
$\max\limits_{\alpha_i \geq 0, \;\mu_i \geq 0}\;\min\limits_{w,b,\xi} L(w,b,\alpha, \xi,\mu)$αi​≥0,μi​≥0max​w,b,ξmin​L(w,b,α,ξ,μ)
首先是优化函数的$w, b, \xi$w,b,ξ求极小值，对变量求偏导得：
$\frac{\partial L}{\partial w} = 0 \;\Rightarrow w = \sum\limits_{i=1}^{m}\alpha_iy_ix_i \tag 2$∂w∂L​=0⇒w=i=1∑m​αi​yi​xi​(2)

$\frac{\partial L}{\partial b} = 0 \;\Rightarrow \sum\limits_{i=1}^{m}\alpha_iy_i = 0 \tag 3$∂b∂L​=0⇒i=1∑m​αi​yi​=0(3)

$\frac{\partial L}{\partial \xi_i} = 0 \;\Rightarrow C- \alpha_i - \mu_i = 0 \tag 4$∂ξi​∂L​=0⇒C−αi​−μi​=0(4)

将求导结果代入拉格朗日函数得到：
$\begin{aligned} L(w,b,\xi,\alpha,\mu) & = \frac{1}{2}||w||^2 +C\sum\limits_{i=1}^{m}\xi_i + \sum\limits_{i=1}^{m}\alpha_i[1 - \xi_i - y_i(w^T x_i +b)] + \sum\limits_{i=1}^{m}\mu_i(-\xi_i) 　\\&= \frac{1}{2}||w||^2 - \sum\limits_{i=1}^{m}\alpha_i[y_i(w^Tx_i + b) - 1 + \xi_i] + \sum\limits_{i=1}^{m}\alpha_i\xi_i \\& = \frac{1}{2}||w||^2 - \sum\limits_{i=1}^{m}\alpha_i[y_i(w^Tx_i + b) - 1] \\& = \frac{1}{2}w^Tw-\sum\limits_{i=1}^{m}\alpha_iy_iw^Tx_i - \sum\limits_{i=1}^{m}\alpha_iy_ib + \sum\limits_{i=1}^{m}\alpha_i \\& = \frac{1}{2}w^T\sum\limits_{i=1}^{m}\alpha_iy_ix_i -\sum\limits_{i=1}^{m}\alpha_iy_iw^Tx_i - \sum\limits_{i=1}^{m}\alpha_iy_ib + \sum\limits_{i=1}^{m}\alpha_i \\& = \frac{1}{2}w^T\sum\limits_{i=1}^{m}\alpha_iy_ix_i - w^T\sum\limits_{i=1}^{m}\alpha_iy_ix_i - \sum\limits_{i=1}^{m}\alpha_iy_ib + \sum\limits_{i=1}^{m}\alpha_i \\& = - \frac{1}{2}w^T\sum\limits_{i=1}^{m}\alpha_iy_ix_i - \sum\limits_{i=1}^{m}\alpha_iy_ib + \sum\limits_{i=1}^{m}\alpha_i \\& = - \frac{1}{2}w^T\sum\limits_{i=1}^{m}\alpha_iy_ix_i - b\sum\limits_{i=1}^{m}\alpha_iy_i + \sum\limits_{i=1}^{m}\alpha_i \\& = -\frac{1}{2}(\sum\limits_{i=1}^{m}\alpha_iy_ix_i)^T(\sum\limits_{i=1}^{m}\alpha_iy_ix_i) - b\sum\limits_{i=1}^{m}\alpha_iy_i + \sum\limits_{i=1}^{m}\alpha_i \\& = -\frac{1}{2}\sum\limits_{i=1}^{m}\alpha_iy_ix_i^T\sum\limits_{i=1}^{m}\alpha_iy_ix_i - b\sum\limits_{i=1}^{m}\alpha_iy_i + \sum\limits_{i=1}^{m}\alpha_i \\& = -\frac{1}{2}\sum\limits_{i=1}^{m}\alpha_iy_ix_i^T\sum\limits_{i=1}^{m}\alpha_iy_ix_i + \sum\limits_{i=1}^{m}\alpha_i \\& = -\frac{1}{2}\sum\limits_{i=1,j=1}^{m}\alpha_iy_ix_i^T\alpha_jy_jx_j + \sum\limits_{i=1}^{m}\alpha_i \\& = \sum\limits_{i=1}^{m}\alpha_i - \frac{1}{2}\sum\limits_{i=1,j=1}^{m}\alpha_i\alpha_jy_iy_jx_i^Tx_j \end{aligned}$L(w,b,ξ,α,μ)​=21​∣∣w∣∣2+Ci=1∑m​ξi​+i=1∑m​αi​[1−ξi​−yi​(wTxi​+b)]+i=1∑m​μi​(−ξi​)　=21​∣∣w∣∣2−i=1∑m​αi​[yi​(wTxi​+b)−1+ξi​]+i=1∑m​αi​ξi​=21​∣∣w∣∣2−i=1∑m​αi​[yi​(wTxi​+b)−1]=21​wTw−i=1∑m​αi​yi​wTxi​−i=1∑m​αi​yi​b+i=1∑m​αi​=21​wTi=1∑m​αi​yi​xi​−i=1∑m​αi​yi​wTxi​−i=1∑m​αi​yi​b+i=1∑m​αi​=21​wTi=1∑m​αi​yi​xi​−wTi=1∑m​αi​yi​xi​−i=1∑m​αi​yi​b+i=1∑m​αi​=−21​wTi=1∑m​αi​yi​xi​−i=1∑m​αi​yi​b+i=1∑m​αi​=−21​wTi=1∑m​αi​yi​xi​−bi=1∑m​αi​yi​+i=1∑m​αi​=−21​(i=1∑m​αi​yi​xi​)T(i=1∑m​αi​yi​xi​)−bi=1∑m​αi​yi​+i=1∑m​αi​=−21​i=1∑m​αi​yi​xiT​i=1∑m​αi​yi​xi​−bi=1∑m​αi​yi​+i=1∑m​αi​=−21​i=1∑m​αi​yi​xiT​i=1∑m​αi​yi​xi​+i=1∑m​αi​=−21​i=1,j=1∑m​αi​yi​xiT​αj​yj​xj​+i=1∑m​αi​=i=1∑m​αi​−21​i=1,j=1∑m​αi​αj​yi​yj​xiT​xj​​
将(3)代入第一行即可得到第二行；第二行消去$\sum\limits_{i=1}^{m}\alpha_i\xi_i$i=1∑m​αi​ξi​得到第三行；第三行与线性可分的SVM一样，所以最后计算结果和线性可分的SVM也一样，唯一不同的只是约束条件。

继续对式子求极大：
$\max \limits_{\alpha} \quad \sum\limits_{i=1}^{m}\alpha_i - \frac{1}{2}\sum\limits_{i=1,j=1}^{m}\alpha_i\alpha_jy_iy_jx_i^Tx_j \\ s.t. \;\; \sum\limits_{i=1}^{m}\alpha_iy_i = 0\\ C- \alpha_i - \mu_i = 0\\ \alpha_i \geq 0 \;(i =1,2,...,m) \\ \mu_i \geq 0 \;(i =1,2,...,m)$αmax​i=1∑m​αi​−21​i=1,j=1∑m​αi​αj​yi​yj​xiT​xj​s.t.i=1∑m​αi​yi​=0C−αi​−μi​=0αi​≥0(i=1,2,...,m)μi​≥0(i=1,2,...,m)
对于$C- \alpha_i - \mu_i = 0 ， \alpha_i \geq 0 ，\mu_i \geq 0$C−αi​−μi​=0，αi​≥0，μi​≥0有：
$\begin{aligned} &C- \alpha_i = \mu_i \ge 0 \\ &\rightarrow \quad C \ge \alpha_i\\ &\rightarrow 0 \le \alpha_i \le C \end{aligned}$​C−αi​=μi​≥0→C≥αi​→0≤αi​≤C​
基于上面的条件$0 \le \alpha_i \le C$0≤αi​≤C，同时将目标函数变号求极小值，得到：
$\min \limits_{\alpha} \quad \frac{1}{2}\sum\limits_{i=1,j=1}^{m}\alpha_i\alpha_jy_iy_jx_i^Tx_j-\sum\limits_{i=1}^{m}\alpha_i \\ s.t. \;\; \sum\limits_{i=1}^{m}\alpha_iy_i = 0\\ 0 \le \alpha_i \le C$αmin​21​i=1,j=1∑m​αi​αj​yi​yj​xiT​xj​−i=1∑m​αi​s.t.i=1∑m​αi​yi​=00≤αi​≤C
上面的式子就是软间隔最大化SVM的优化目标，与硬间隔SVM相比，约束条件中的$0 \le \alpha_i$0≤αi​变为$0 \le \alpha_i \le C$0≤αi​≤C。这样的问题同样可以使用SMO算法求极小值，进而求出w，b。

软间隔最大化的支持向量

硬间隔最大化SVM，所有满足$\alpha_{i}^{*}\gt0$αi∗​>0的样本$i$i即为支持向量。对于软间隔最大化的SVM，由于引入了松弛变量$\xi_i$ξi​，支持向量的判断稍微复杂一些。

如下图所示，划分超平面用实线表示，间隔边界由虚线表示。误分类的点到间隔平面的几何距离为$\frac{\xi_i}{||w||_2}$∣∣w∣∣2​ξi​​。

软间隔支持向量$x_i$xi​要么在间隔边界上，要么在间隔边界内，还可能在分离超平面误分类的一侧：

(1) 如果$\alpha = 0$α=0,那么$y_i(w^Tx_i + b) - 1 \geq 0$yi​(wTxi​+b)−1≥0,即样本在间隔边界上或者已经被正确分类。如图中所有远离间隔边界的点。

(2) 如果$0 \lt \alpha \lt C$0<α<C，且$\xi_i = 0 ,\;\; y_i(w^Tx_i + b) - 1 = 0$ξi​=0,yi​(wTxi​+b)−1=0，即点在间隔边界上(蓝框部分)。

(3) 如果$\alpha = C$α=C，说明这是一个可能比较异常的点，需要检查此时$\xi_i$ξi​：

1. 如果$0 \lt \xi_i \lt 1$0<ξi​<1，那么点被正确分类，但是却在超平面和自己类别的间隔边界之间(黄框部分)。

2. 如果$\xi_i =1$ξi​=1，那么点在分离超平面上，无法被正确分类。

3. 如果$\xi_i \gt 1$ξi​>1，那么点在超平面的另一侧，也就是说，这个点不能被正常分类(红框部分)。

于是，上面图片中所有标注了距离的都是支持向量。

软间隔最大化SVM算法过程

输入：线性可分的m个样本${(x_1,y_1), (x_2,y_2), ..., (x_m,y_m),}$(x1​,y1​),(x2​,y2​),...,(xm​,ym​),

输出：分离超平面的参数$w^{*}$w∗和$b^{*}$b∗和分类决策函数。

(1) 选择惩罚系数C>0，构造优化问题：
$\min\limits_{\alpha} \frac{1}{2}\sum\limits_{i=1,j=1}^{m}\alpha_i\alpha_jy_iy_jx_i^Tx_j -\sum\limits_{i=1}^{m} \alpha_i$αmin​21​i=1,j=1∑m​αi​αj​yi​yj​xiT​xj​−i=1∑m​αi​

$s.t. \quad \sum\limits_{i=1}^{m}\alpha_iy_ix_i =0 \\ 0 \le \alpha_i \leq C, i=1,2,...,m$s.t.i=1∑m​αi​yi​xi​=00≤αi​≤C,i=1,2,...,m

(2) 采用SMO算法求出使得上式极小化的$\alpha^*$α∗

(3) 计算$w^{*} = \sum\limits_{i=1}^{m}\alpha_i^{*}y_ix_i$w∗=i=1∑m​αi∗​yi​xi​

(4) 找到所有的S个支持向量$(x_s,y_s)$(xs​,ys​)，计算：
$b^*_s = y_s - (w^*)^Tx_s = y_s -\sum\limits_{i=1}^{m}\alpha_i^{*}y_ix_i^Tx_s$bs∗​=ys​−(w∗)Txs​=ys​−i=1∑m​αi∗​yi​xiT​xs​
​ 最终得到：
$b^{*} = \frac{1}{S}\sum\limits_{i=1}^{S}b_s^{*}$b∗=S1​i=1∑S​bs∗​
(5) 得到划分超平面与决策函数：
$w^{*T}x+b^* = 0 \\ f(x) = sign(w^{*T} x + b^{*})$w∗Tx+b∗=0f(x)=sign(w∗Tx+b∗)

参考文章：

《统计学习方法 第二版》

支持向量机原理(二) 线性支持向量机的软间隔最大化模型