2021人工智能领域新星创作者，带你从入门到精通，该博客每天更新，逐渐完善机器学习各个知识体系的文章，帮助大家更高效学习。

一、概述

上篇文章我们引出了SVM的硬间隔的概念，它是最大化我们每个样本到超平面的间隔，使每个样本的函数间隔大于等于1，即：

y i ( w T x i + b ) ≥ 1 y_i(w^Tx_i+b)\geq1yi(wTxi+b)≥1

而且它有个前提条件就是数据是线性可分的，就是能够找到一个超平面能够将数据完全区分，但是区分方式有很多种，硬间隔就是为了找到最优的一个超平面，但是在实际中，我们很多数据是不可分的，找不到一个超平面进行完全区分，比如说：

上面这幅图可以看到在黄色区域存在一个噪音点，我们是无论如何都无法进行完全分类的，但是我们还想找到一个超平面进行区分，显然仍然是中间这条线效果最好，尽管分类错误一个蓝色噪音点，但是只是牺牲一个样本的分类正确率，成就绝大数样本的分类正确。

也就是说，除去一些难以区分的噪音点，我们的数据仍旧是线性可分的。

此时就说明一些噪音点是不能满足我们之前函数间隔大于1的条件的，即 y i ( w T x i + b ) ≥ 1 y_i(w^Tx_i+b)\geq1yi(wTxi+b)≥1 ，那么我们可以引入一个松弛变量，让每个样本可以存在一定的误判误差，现在约束条件就变成了：

y i ( w T x i + b ) ≥ 1 − ξ i y_i(w^Tx_i+b)\geq1-\xi_iyi(wTxi+b)≥1−ξi

这样引入了松弛变量后，原来的约束条件就不那么强了，而且这个 ξ i \xi_iξi 每个样本是不同的，如果对于那些线性可分的数据他应该是为0的，仍满足之前的条件，但是如果是那些噪音点，就可以降低要求，比如说上面的那个蓝色噪音点，如果要满足新的约束条件，那么 ξ \xiξ 应该为大于1的，所以可以将它看成一种损失，如果正确线性可分的数据应该为0，如果是不可分的数据一定是大于0的，我们目标就是让每个样本的 ξ \xiξ 最小，那么我们的目标函数就从原来的 m i n 1 2 w T w min\frac{1}{2}w^Twmin21wTw 变为了：

m i n 1 2 w T w + C ∑ i = 1 m ξ i min\frac{1}{2}w^Tw+C\sum_{i=1}^m\xi_imin21wTw+Ci=1∑mξi

其中的C代表惩罚系数，和正则项的那个意义差不多，如果C值越大，我们允许错误的程度越小，即 ξ \xiξ 就越小，也就是容忍错误的能力越小。

那么此时的问题就变成了：

m i n 1 2 w T w + C ∑ i = 1 m ξ i min\frac{1}{2}w^Tw+C\sum_{i=1}^m\xi_imin21wTw+Ci=1∑mξi

y i ( w T x i + b ) ≥ 1 − ξ i y_i(w^Tx_i+b)\geq1-\xi_iyi(wTxi+b)≥1−ξi

ξ i ≥ 0 \xi_i\geq0ξi≥0

二、问题求解

求解软间隔的问题和硬间隔是一模一样的，都是构造拉格朗日，然后转化成对偶问题，利用KKT条件求解最优值。

1.构造拉格朗日函数

第一节中最终我们获得了目标函数和两个不等式约束条件，那么需要构造一个拉格朗日函数，为：

L ( w , b , ξ , λ , μ ) = 1 2 w T w + C ∑ i = 1 m ξ i + ∑ i = 1 m λ i [ ( 1 − ξ i ) − y i ( w T x i + b ) ] − ∑ i = 1 m μ i ξ i L(w,b,\xi,\lambda,\mu)=\frac{1}{2}w^Tw+C\sum_{i=1}^m\xi_i+\sum_{i=1}^m\lambda_i[(1-\xi_i)-y_i(w^Tx_i+b)]-\sum_{i=1}^m\mu_i\xi_iL(w,b,ξ,λ,μ)=21wTw+Ci=1∑mξi+i=1∑mλi[(1−ξi)−yi(wTxi+b)]−i=1∑mμiξi

λ i ≥ 0 \lambda_i\geq0λi≥0

μ i ≥ 0 \mu_i\geq0μi≥0

所以此时我们的原问题就转化成了：

m i n w , b , ξ m a x λ , μ L ( w , b , ξ , λ , μ ) min_{w,b,\xi}max_{\lambda,\mu}L(w,b,\xi,\lambda,\mu)minw,b,ξmaxλ,μL(w,b,ξ,λ,μ)

2.对偶问题

为了求解方便，我们将原问题转化为它的对偶问题，对偶问题是拉格朗日函数的极大极小问题，也就是：

m a x λ , μ m i n w , b , ξ L ( w , b , ξ , λ , μ ) max_{\lambda,\mu}min_{w,b,\xi}L(w,b,\xi,\lambda,\mu)maxλ,μminw,b,ξL(w,b,ξ,λ,μ)

对于该对偶问题，我们应该先求拉格朗日函数的极小值，首先对 w , b , ξ w,b,\xiw,b,ξ 进行求偏导，得到：

∂ L ∂ w = w − ∑ i = 1 m λ i y i x i = 0 \frac{\partial L}{\partial w}=w-\sum_{i=1}^m\lambda_iy_ix_i=0∂w∂L=w−i=1∑mλiyixi=0

∂ L ∂ b = − ∑ i = 1 m λ i y i = 0 \frac{\partial L}{\partial b}=-\sum_{i=1}^m\lambda_iy_i=0∂b∂L=−i=1∑mλiyi=0

∂ L ∂ ξ i = C − λ i − μ i = 0 \frac{\partial L}{\partial \xi_i}=C-\lambda_i-\mu_i=0∂ξi∂L=C−λi−μi=0

我们将上面获得的三个式子带入原拉格朗日函数中就可以获得 m i n w , b , ξ L ( w , b , ξ , λ , μ ) min_{w,b,\xi}L(w,b,\xi,\lambda,\mu)minw,b,ξL(w,b,ξ,λ,μ) ，得：

m i n w , b , ξ L ( w , b , ξ , λ , μ ) = − 1 2 ∑ i = 1 m ∑ j = 1 m λ i λ j y i y j x i T x j + ∑ i = 1 m λ i min_{w,b,\xi}L(w,b,\xi,\lambda,\mu)=-\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\lambda_i\lambda_jy_iy_jx_i^Tx_j+\sum_{i=1}^m\lambda_iminw,b,ξL(w,b,ξ,λ,μ)=−21i=1∑mj=1∑mλiλjyiyjxiTxj+i=1∑mλi

所以我们得对偶问题又变成了：

m a x λ , μ m i n w , b , ξ L ( w , b , ξ , λ , μ ) = m a x λ , μ − 1 2 ∑ i = 1 m ∑ j = 1 m λ i λ j y i y j x i T x j + ∑ i = 1 m λ i max_{\lambda,\mu}min_{w,b,\xi}L(w,b,\xi,\lambda,\mu)=max_{\lambda,\mu}-\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\lambda_i\lambda_jy_iy_jx_i^Tx_j+\sum_{i=1}^m\lambda_imaxλ,μminw,b,ξL(w,b,ξ,λ,μ)=maxλ,μ−21i=1∑mj=1∑mλiλjyiyjxiTxj+i=1∑mλi

由于一般情况下我们是优化最小值的，需要转换一下，添加个负号，得：

m i n λ , μ 1 2 ∑ i = 1 m ∑ j = 1 m λ i λ j y i y j x i T x j − ∑ i = 1 m λ i min_{\lambda,\mu}\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\lambda_i\lambda_jy_iy_jx_i^Tx_j-\sum_{i=1}^m\lambda_iminλ,μ21i=1∑mj=1∑mλiλjyiyjxiTxj−i=1∑mλi

∑ i = 1 m λ i y i = 0 \sum_{i=1}^m\lambda_iy_i=0i=1∑mλiyi=0

C − λ i − μ i = 0 C-\lambda_i-\mu_i=0C−λi−μi=0

λ i ≥ 0 \lambda_i\geq0λi≥0

μ i ≥ 0 \mu_i\geq0μi≥0

我们可以将后三个约束条件进行合并：

即：

0 ≤ λ i ≤ C 0\leq \lambda_i \leq C0≤λi≤C

我们的最终目标就是求出使上式达到最优的 λ \lambdaλ ,然后带入我们的w方程和b的方程中，获得最优解 w ∗ w^*w∗ 和 b ∗ b^*b∗ ，那么这个最优解方程如何获得呢？利用KKT条件。

3.KKT条件求解极值

由于我们的原问题是凸二次规划问题，所以最终的解满足KKT条件，条件如下：

∂ L ∂ w = w − ∑ i = 1 m λ i y i x i = 0 \frac{\partial L}{\partial w}=w-\sum_{i=1}^m\lambda_iy_ix_i=0∂w∂L=w−i=1∑mλiyixi=0

∂ L ∂ b = − ∑ i = 1 m λ i y i = 0 \frac{\partial L}{\partial b}=-\sum_{i=1}^m\lambda_iy_i=0∂b∂L=−i=1∑mλiyi=0

∂ L ∂ ξ i = C − λ i − μ i = 0 \frac{\partial L}{\partial \xi_i}=C-\lambda_i-\mu_i=0∂ξi∂L=C−λi−μi=0

该三个是拉格朗日函数取得极值点的条件。

λ i ∗ ( y i ( w T x i + b ) − 1 + ξ i ∗ ) = 0 \lambda_i^*(y_i(w^Tx_i+b)-1+\xi_i^*)=0λi∗(yi(wTxi+b)−1+ξi∗)=0

μ i ∗ ξ i ∗ = 0 \mu_i^*\xi_i^*=0μi∗ξi∗=0

这两个为不等式约束条件，可以看出就是用拉格朗日乘子乘以原来的不等式约束使其等于0。

y i ( w T x i + b ) − 1 + ξ i ∗ ≥ 0 y_i(w^Tx_i+b)-1+\xi_i^*\geq0yi(wTxi+b)−1+ξi∗≥0

ξ i ∗ ≥ 0 \xi_i^*\geq0ξi∗≥0

这两个为原来的不等式约束条件。

λ i ≥ 0 \lambda_i\geq0λi≥0

μ i ≥ 0 \mu_i\geq0μi≥0

这两个就是拉格朗日不等式约束的乘子必须大于等于0。

根据上面的KKT条件我们就可以获得下面的结论：

w ∗ = ∑ i = 1 m λ i ∗ y i x i w^*=\sum_{i=1}^m\lambda_i^*y_ix_iw∗=i=1∑mλi∗yixi

b ∗ = y j − ∑ i = 1 m y i λ i ∗ x i T x j b^*=y_j-\sum_{i=1}^my_i\lambda_i^*x_i^Tx_jb∗=yj−i=1∑myiλi∗xiTxj

这样我们就获得了最终参数的表达式，将我们第三步优化目标函数获得的 λ \lambdaλ 带入上边的两个方程就可以求出最优解参数了。

我们最终的分类超平面就可以写成：

∑ i = 1 m λ i ∗ y i ( x i T x ) + b ∗ = 0 \sum_{i=1}^m\lambda_i^*y_i(x_i^Tx)+b^*=0i=1∑mλi∗yi(xiTx)+b∗=0

分类决策函数可以写成：

f ( x ) = s i g n ( ∑ i = 1 m λ i ∗ y i ( x i T x ) + b ∗ ) f(x)=sign(\sum_{i=1}^m\lambda_i^*y_i(x_i^Tx)+b^*)f(x)=sign(i=1∑mλi∗yi(xiTx)+b∗)