支持向量机SVM(3)——软间隔

接上一篇博客支持向量机SVM(2)——拉格朗日乘数法
前面我们的问题假设数据处于理想状态，而现实情况是数据可能是线性不可分的，或者可分但是存在噪声。对于有噪声这种情况，如果我们还是使用前面的方法，那么就会把噪声也分类，就会存在过拟合的情况。解决这个问题的一个方法就是存于我们的超平面出一点点错，这也就是“软间隔”（soft margin），而前面我们所讲的就是“硬间隔”（hard margin）。
如下图所示：我们允许出现红色圈的那些点不满足约束条件$y_i(w^Tx_i+b)\geq1$yi​(wTxi​+b)≥1。

我们现在用loss来表示允许一点错误的损失，当$y_i(w^Tx_i+b)<1$yi​(wTxi​+b)<1不满足约束条件时，loss=1；$y_i(w^Tx_i+b)\geq1$yi​(wTxi​+b)≥1时满足条件时，这个时候没有错误，loss=0。这也称为0/1损失函数：
$loss(z)=\begin{cases}1，if\;z<1\\0，otherwise\end{cases}$loss(z)={1，ifz<10，otherwise​
那么我们原始的优化目标就变成了：
$min_{(w,b)}\frac{1}{2}w^Tw+C\sum_{i=1}^Nloss(y_i(w^Tx_i+b))$min(w,b)​21​wTw+Ci=1∑N​loss(yi​(wTxi​+b))
其中，C是常数。
很容易发现我们的损失函数并不连续，在后面我们求导过程中的处理会比较麻烦，这里我们会用一些其他的连续的损失函数来替代，常见的有三种替代损失函数：
$hinge损失：loss_{hinge}(z)=max(0,1-z)\\指数损失：loss_{exp}(z)=exp(-z)\\对率损失：loss_{log}(z)=log(1+exp(-z))$hinge损失：losshinge​(z)=max(0,1−z)指数损失：lossexp​(z)=exp(−z)对率损失：losslog​(z)=log(1+exp(−z))
这里我们采用hinge损失，那么我们上面的优化目标就变成如下形式：
$min_{(w,b)}\frac{1}{2}w^Tw+C\sum_{i=1}^Nmax(0,1-y_i(w^Tx_i+b))$min(w,b)​21​wTw+Ci=1∑N​max(0,1−yi​(wTxi​+b))
但一般我们不写成上面这种形式，我们先引入$\xi_i=1-y_i(w^Tx_i+b)$ξi​=1−yi​(wTxi​+b)。当$\xi_i$ξi​大于0时，上面的max就取$\xi_i$ξi​；当$\xi_i$ξi​小于0时，上面的max取0，所以我们直接添加一个约束$\xi_i\geq0$ξi​≥0，然后我们原始的问题就可以写成如下形式：
$\begin{cases}min_{(w,b,\xi_i)}\frac{1}{2}w^Tw+C\sum_{i=1}^N\xi_i\\s.t.\quad y_i(w^Tx_i+b)\geq1-\xi_i\\\qquad\;\xi_i\geq0\end{cases}$⎩⎪⎨⎪⎧​min(w,b,ξi​)​21​wTw+C∑i=1N​ξi​s.t.yi​(wTxi​+b)≥1−ξi​ξi​≥0​
其中$\xi_i$ξi​也称为松弛变量。

现在我们就可以采取和硬间隔中一样的办法来求解：即先构造拉了朗日函数，然后利用对偶关系求解对偶问题，最后求导。
（不懂得可以翻看前一篇博客）
简单走一下流程：
（1）构造拉格朗日函数：
$L(w,b,\lambda,\xi,u)=\frac{1}{2}w^Tw+C\sum_{i=1}^N\xi_i+\sum_{i=1}^N\lambda_i(1-\xi_i-y_i(w^Tx_i+b))-\sum_{i=1}^Nu_i\xi_i$L(w,b,λ,ξ,u)=21​wTw+Ci=1∑N​ξi​+i=1∑N​λi​(1−ξi​−yi​(wTxi​+b))−i=1∑N​ui​ξi​
其中，$\lambda_i\geq0，u_i\geq0$λi​≥0，ui​≥0是拉格朗日乘子。
（2）然后我们的优化问题可以写成如下形式(对$w,b,\xi$w,b,ξ无约束)：
$\begin{cases}min_{(w,b,\xi)}\;max_{(\lambda,u)}L(w,b,\lambda,\xi,u)\\ s.t. \quad \lambda_i\geq0，u_i\geq0\end{cases}${min(w,b,ξ)​max(λ,u)​L(w,b,λ,ξ,u)s.t.λi​≥0，ui​≥0​
（3）利用对偶关系求其对偶问题：
$\begin{cases}max_{(\lambda,u)}\;min_{(w,b,\xi)}L(w,b,\lambda,\xi,u)\\ s.t. \quad \lambda_i\geq0，u_i\geq0\end{cases}${max(λ,u)​min(w,b,ξ)​L(w,b,λ,ξ,u)s.t.λi​≥0，ui​≥0​

然后通过对$w,b,\xi$w,b,ξ分别求偏导并令其为0，来求解$min_{(w,b,\xi)}L(w,b,\lambda,\xi,u)$min(w,b,ξ)​L(w,b,λ,ξ,u)的最优解：
$\begin{cases}\frac{\delta L}{\delta b}=0\iff\sum_{i=1}^N\lambda_iy_i=0\\\frac{\delta L}{\delta w}=0\iff w=\sum_{i=1}^N\lambda_iy_ix_i\\\frac{\delta L}{\delta \xi_i}=0\iff C=\lambda_i+u_i\end{cases}$⎩⎪⎨⎪⎧​δbδL​=0⟺∑i=1N​λi​yi​=0δwδL​=0⟺w=∑i=1N​λi​yi​xi​δξi​δL​=0⟺C=λi​+ui​​
（4）将上面对min求得的最优解代入我们的对偶问题中，可得：
$\begin{cases}max_{\lambda}\;(-\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\lambda_i\lambda_jy_iy_jx^T_ix_j+\sum_{i=1}^N\lambda_i)\\ s.t. \quad 0\leq\lambda_i\leq C\\\qquad\sum_{i=1}^N\lambda_iy_i=0\end{cases}$⎩⎪⎨⎪⎧​maxλ​(−21​∑i=1N​∑j=1N​λi​λj​yi​yj​xiT​xj​+∑i=1N​λi​)s.t.0≤λi​≤C∑i=1N​λi​yi​=0​

可以看到这和我们硬间隔中得到最终优化问题唯一不同就是：软间隔$0\leq\lambda_i\leq C$0≤λi​≤C，而硬间隔$0\leq\lambda_i$0≤λi​。

并且仍然满足KKT条件：
$\begin{cases}\lambda_i(1- y_i(w^Tx_i+b)-\xi_i)=0\\ \lambda_i\geq0，u_i\geq0\\y_i(w^Tx_i+b)\geq1-\xi_i\\\xi_i\geq0,u_i\xi_i=0\end{cases}$⎩⎪⎪⎪⎨⎪⎪⎪⎧​λi​(1−yi​(wTxi​+b)−ξi​)=0λi​≥0，ui​≥0yi​(wTxi​+b)≥1−ξi​ξi​≥0,ui​ξi​=0​