[机器学习] SVM原理及推导

朴灿烈づ我的快乐病毒、 2022-05-26 13:11 222阅读 0赞

# 0 由来 #

在二分类问题中，我们可以计算数据代入模型后得到的结果，如果这个结果有明显的区别，这就说明模型可以把数据分开。那么，怎么表示“区别”这个词呢，拿最简单的二维问题来讲，“区别”可以是数据点分布在一条直线的两侧，而数据点代入方程后得到的结果符号是不同的，这就达到了分类的目的。 而SVM的思想也是这样，目的就是找到一个超平面，将数据点都正确地分在超平面的两侧。那么，又怎么表示这个“都正确”呢？可以这样考虑：就是让那些“很有可能不正确”的数据点彼此分开得明显一点就可以了。对于其它“不那么可能不正确”或者说“一看就很正确”的数据点，就可以不用管了。这也是SVM名称的由来，模型是由那些支持向量（Support Vector）决定的。这也是为什么SVM对outlier不敏感。

# 1 间隔 #

遵循上面的逻辑，我们去假设空间里找模型了。但是一下子出来好多个模型都符合我们的要求，怎么办？自然我们想要找到“最优”的那一个模型。那么，怎么衡量这个“最优”呢？根据【超平面】【数据点】【分开】这几个词，我们可以想到最优的模型必然是最大程度地将数据点划分开的模型，不能靠近负样本也不能靠近正样本，要不偏不倚，并且与所有Support Vector的距离尽量大才可以。这就引出了间隔的讨论。

![geometric_margin.png][]

上图中 x0x0 是 xx 在超平面上的投影，ωω 是超平面的法向量，二者平行可以得到：

x−x0=γω∥ω∥(1.1)(1.1)x−x0=γω‖ω‖

两边同乘  ωTωT  并利用  ωTx0\+b=0,ωTω=∥ω∥2ωTx0+b=0,ωTω=‖ω‖2  得到：

γ=ωT\+b∥ω∥=f(x)∥ω∥(1.2)(1.2)γ=ωT+b‖ω‖=f(x)‖ω‖

当然，上式是带正负号的，如果要得到正值，即点到超平面的距离，乘上数据点的类别就好：

γ~=yγ(1.3)(1.3)γ~=yγ

# 2 最大间隔分类器 #

上面我们推导出了间隔的表达式，自然的，我们想让数据点离超平面越远越好。

![Svm_max_sep_hyperplane_with_margin.png][]

回顾一下，在这样的模型中，我们只考虑那些支持向量就可以了，对于那些显然可以分类成功的数据点，我们顺带着讨论它们就可以。  
不妨令那些“有可能分类不成功的点”，即靠近超平面的点，分布在超平面 ωTx\+b=±1ωTx+b=±1 上，这里的取值 1 只是为了方便推导，后面我们可以看到，这个值不影响最后的优化过程。  
这样，支持向量到达我们要优化的超平面 ωTx\+b=0ωTx+b=0 的距离就是 1∥ω∥1‖ω‖，两侧的距离加起来就是2∥ω∥2‖ω‖，同时，我们要求模型对正负样本要做到“不偏不倚”，对于这一条，我们加上限制条件 y(ωT\+b)⩾1y(ωT+b)⩾1 就好。于是我们得到了不等式约束优化问题：

⎧⎩⎨⎪⎪max2∥ω∥s.t.yi(ωTxi\+b)⩾1,i=1,2,...,m(2.1)(2.1)\{max2‖ω‖s.t.yi(ωTxi+b)⩾1,i=1,2,...,m

为了方便推导，上式可以等价地写成：

⎧⎩⎨min12∥ω∥2s.t.yi(ωTxi\+b)⩾1,i=1,2,...,m(2.2)(2.2)\{min12‖ω‖2s.t.yi(ωTxi+b)⩾1,i=1,2,...,m

# 3 拉格朗日乘子法对偶问题 #

(2.2) 的优化目标是二次的，约束是线性的，整体是一个凸二次规划问题。有现成的优化包可以求解。但将其转化为拉格朗日对偶问题后求解更容易，也方便我们后面引入核函数。

对式 (2.2) 的每一个不等式约束条件（m个数据点共有m个不等式）设置对应的拉格朗日乘子 αi>0αi>0 ，得到原始问题的拉格朗日函数：

L(ω,b,α)=12∥ω∥2\+∑i=1mαi\[1−yi(ωTxi\+b)\](3.1)(3.1)L(ω,b,α)=12‖ω‖2+∑i=1mαi\[1−yi(ωTxi+b)\]

目标是让拉格朗如函数  L(ω,b,α)L(ω,b,α)  针对  αα  达到最大值。为什么能够这么写呢，我们可以这样想，哪怕有一个  yi(ωTxi\+b)⩾1yi(ωTxi+b)⩾1  不满足，只要让对应的  αiαi  是正无穷就好了。所以，如果 L(ω,b,α)L(ω,b,α)  有有限的最大值，那么那些不等式条件是自然满足的。 之后，我们再让  L(ω,b,α)L(ω,b,α)  针对  ω,bω,b  达到最小值，就可以了。 从而，我们的目标函数变成：

minω,bmaxαL(ω,b,α)=p∗(3.2)(3.2)minω,b⁡maxα⁡L(ω,b,α)=p∗

为方便求解，我们将 min 和 max 的位置交换一下：

maxαminω,bL(ω,b,α)=d∗(3.3)(3.3)maxα⁡minω,b⁡L(ω,b,α)=d∗

可以证明，  d∗⩽p∗d∗⩽p∗  ，可以通过求解  d∗d∗  而近似求解  p∗p∗  。(3.3)即为原始问题的对偶问题。 由于原始优化问题中有不等式条件，这里的对偶问题需要满足下面形式的KKT条件才能有解：

⎧⎩⎨⎪⎪αi⩾0yi(ωTxi\+b)−1⩾0αi\[yi(ωTxi\+b)−1\]=0(3.4)(3.4)\{αi⩾0yi(ωTxi+b)−1⩾0αi\[yi(ωTxi+b)−1\]=0

这里知道到我们到目前为止的推导是需要满足KKT条件的就好了。

下面我们看一下具体怎样求解对偶问题 (3.3) ：

## 3.1 ω,bω,b 的部分 ##

我们先看一下 minω,bminω,b 的部分。分别令 L(ω,b,α)L(ω,b,α) 对 ω,bω,b 的导数等于0：

∂L(ω,b,α)∂ω=ω−∑i=1mαiyixi=0(3.5)(3.5)∂L(ω,b,α)∂ω=ω−∑i=1mαiyixi=0

∂L(ω,b,α)∂b=∑i=1mαiyi=0(3.6)(3.6)∂L(ω,b,α)∂b=∑i=1mαiyi=0

将（3.5）（3.6）代入（3.1）：

L(ω,b,α)=12∥ω∥2\+∑i=1mαi\[1−yi(ωTxi\+b)\]=12∥∥∥∑i=1mαiyixi∥∥∥2\+∑i=1mαi−ωT∑i=1mαiyixi=∑i=1mαi\+12ωT∑i=1mαiyixi−ωT∑i=1mαiyixi=∑i=1mαi−(∑i=1mαiyixTi)(∑i=1mαiyixi)=∑i=1mαi−∑i=1m∑j=1mαiαjyiyjxTixj(3.7)(3.7)L(ω,b,α)=12‖ω‖2+∑i=1mαi\[1−yi(ωTxi+b)\]=12‖∑i=1mαiyixi‖2+∑i=1mαi−ωT∑i=1mαiyixi=∑i=1mαi+12ωT∑i=1mαiyixi−ωT∑i=1mαiyixi=∑i=1mαi−(∑i=1mαiyixiT)(∑i=1mαiyixi)=∑i=1mαi−∑i=1m∑j=1mαiαjyiyjxiTxj

问题就变为了：

⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪maxαs.t.∑i=1mαi−∑i=1m∑j=1mαiαjyiyjxTixj∑i=1mαiyi=0αi⩾0(3.8)(3.8)\{maxα∑i=1mαi−∑i=1m∑j=1mαiαjyiyjxiTxjs.t.∑i=1mαiyi=0αi⩾0

## 3.2 αα 的部分 ##

得到（3.8）之后怎么求解呢？不难发现这是一个二次规划问题。,但如果样本数过多，则计算量过大。SMO是高效求解这个问题的算法代表。

我们选取两个变量 αi,αjαi,αj ，（3.8）中的其它变量保持固定。得到：

αiyi\+αjyj=−∑k≠i,jmαkyk=c(3.9)(3.9)αiyi+αjyj=−∑k≠i,jmαkyk=c

可以将  αjαj  消掉，只保留  αiαi  ，（3.8）就变成了关于  αiαi  的单变量二次规划问题，约束是  αi⩾0αi⩾0  ，有\*\*闭式解\*\*。这样算起来肯定快。 那么，怎样找这两个变量  αi,αjαi,αj  比较好呢？第一个变量  αiαi  我们肯定选取那个最不满足KKT条件的  αα  ，第二个我们需要选让目标函数增长得最多的  αα  ，但每次计算太过麻烦。所以有一个启发式的方法：我们选取那个与  αiαi  所对应的样本间隔最大的样本所对应的  αα  作为  αjαj  。这样与更新两个相似的样本相比，目标函数值变化更大。这里的具体推导可以参考 http://blog.csdn.net/ajianyingxiaoqinghan/article/details/73087304 。具体来说，我们可以用\*\*预测值与真实值之差\*\*来衡量这个“样本间的差异”，如果  αiαi  对应的样本预测值与真实值之差为负的，那么我们就尽量找一个差值为正的且绝对值较大的，反之我们就找一个差值为负的且绝对值较大的。在几何上可以理解为找那些暂时被分类错误的样本。 当然，如果得到的  αjαj  不能使函数值下降很多，那么我们还可以干脆就暴力找一个让函数值下降最多的  αjαj  ，或者再找一个不符合KKT条件的  αjαj  当做第二个  αα  。 求解出  αnewiαinew  αnewjαjnew  之后，由KKT条件(3.4)可得，若  αnewi>0αinew>0  ，则：

yi(∑i=1mαiyixi\+b)=1(3.10)(3.10)yi(∑i=1mαiyixi+b)=1

就可以对 b 进行更新，更新之后将预测值与真实值之差的列表更新一遍，以供下次循环使用。 当然，如果  αnewj>0αjnew>0  ，也可以计算出相应的 b 值，如果两个 b 值相等就取该值。 如果不相等就取平均值。 还有一种做法就是，对目前模型中所有的  α>0α>0  ，都计算一个 b ，取平均值。 等到算法停止，b 也计算好了，  ωω  由（3.5）式得：

ω=∑i=1mαiyixi(3.11)(3.11)ω=∑i=1mαiyixi

这样，原始优化问题就解完了。

# 4 核函数 #

在前面的讨论中，我们假设数据集是线性可分的。但是现实任务中，可能并不存在一个超平面将数据集完美得分开。  
这种情况下，我们可以通过将原始空间映射到一个高维空间，如果高维空间中数据集是线性可分的，那么问题就可以解决了。  
这样，超平面变为：

ωTϕ(x)\+b=0(4.1)(4.1)ωTϕ(x)+b=0

经过像前面的一顿推导之后我们得到：

⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪maxαs.t.∑i=1mαi−∑i=1m∑j=1mαiαjyiyjϕ(xi)Tϕ(xj)∑i=1mαiyi=0αi⩾0(4.2)(4.2)\{maxα∑i=1mαi−∑i=1m∑j=1mαiαjyiyjϕ(xi)Tϕ(xj)s.t.∑i=1mαiyi=0αi⩾0

可见，需要计算  ϕ(xi)Tϕ(xj)ϕ(xi)Tϕ(xj)  ，但很多时候，我们并不知道高维空间是什么样子，也就是我们根本连  ϕ(x)ϕ(x)  是什么样子都不知道，更不要说如果高维空间维数很大，  ϕ(xi)Tϕ(xj)ϕ(xi)Tϕ(xj)  计算十分困难。 其实  ϕ(xi)Tϕ(xj)ϕ(xi)Tϕ(xj)  只是一个实数，如果将它们看成一个整体，它也是关于  xi,xjxi,xj  的一个函数，所以， 如果存在那么一个神奇的函数 κ(xi,xj)=ϕ(xi)Tϕ(xj)κ(xi,xj)=ϕ(xi)Tϕ(xj) ，我们就可以在低维空间计算出高维空间的点积结果。这个函数 κ(xi,xj)κ(xi,xj)  就叫做\*\*核函数\*\*。 常用的核函数有：

<table style="border-spacing:0px;width:852px;text-align:center;color:rgb(51,51,51);font-family:'-apple-system', 'SF UI Text', Arial, 'PingFang SC', 'Hiragino Sans GB', 'Microsoft YaHei', 'WenQuanYi Micro Hei', sans-serif, SimHei, SimSun;font-size:14px;background-color:rgb(255,255,255);"> 
 <tbody> 
 <tr> 
 <th style="margin:0px;vertical-align:middle;">名称</th> 
 <th style="margin:0px;vertical-align:middle;">表达式</th> 
 <th style="margin:0px;vertical-align:middle;">参数</th> 
 </tr> 
 <tr> 
 <td style="margin:0px;vertical-align:middle;">线型核</td> 
 <td style="margin:0px;vertical-align:middle;">κ(xi,xj)=xTixjκ(xi,xj)=xiTxj</td> 
 <td style="margin:0px;vertical-align:middle;">&nbsp;</td> 
 </tr> 
 <tr> 
 <td style="margin:0px;vertical-align:middle;">多项式核</td> 
 <td style="margin:0px;vertical-align:middle;">κ(xi,xj)=(xTixj)dκ(xi,xj)=(xiTxj)d</td> 
 <td style="margin:0px;vertical-align:middle;">d⩾1d⩾1&nbsp;为多项式次数</td> 
 </tr> 
 <tr> 
 <td style="margin:0px;vertical-align:middle;">高斯核</td> 
 <td style="margin:0px;vertical-align:middle;">κ(xi,xj)=exp(−∥xi−xj∥22σ2)κ(xi,xj)=exp⁡(−‖xi−xj‖22σ2)</td> 
 <td style="margin:0px;vertical-align:middle;">σ&gt;0σ&gt;0为高斯核的带宽</td> 
 </tr> 
 <tr> 
 <td style="margin:0px;vertical-align:middle;">拉普拉斯核</td> 
 <td style="margin:0px;vertical-align:middle;">κ(xi,xj)=exp(−∥xi−xj∥σ)κ(xi,xj)=exp⁡(−‖xi−xj‖σ)</td> 
 <td style="margin:0px;vertical-align:middle;">σ&gt;0σ&gt;0</td> 
 </tr> 
 <tr> 
 <td style="margin:0px;vertical-align:middle;">Sigmoid核</td> 
 <td style="margin:0px;vertical-align:middle;">κ(xi,xj)=tanh(βxTixj+θ)κ(xi,xj)=tanh⁡(βxiTxj+θ)</td> 
 <td style="margin:0px;vertical-align:middle;">β&gt;0,θ&lt;0tanhβ&gt;0,θ&lt;0tanh为双曲正切函数</td> 
 </tr> 
 </tbody> 
</table>

# 5 松弛变量 #

现实任务中，可能用上核函数还是不能线性可分。或者即使找到线性可分的超平面，也不能判断是不是过拟合。因此，我们将标准放宽一些，允许SVM模型在某些数据点上“出错”，为此，要引入“软间隔”：

![Optimal-Hyper-Plane-2.png][]

前面的推导我们要求 yi(ωTxi\+b)⩾1yi(ωTxi+b)⩾1 ，现在，我们将条件放宽：

yi(ωTxi\+b)⩾1−ξi,i=1,2,...,m(5.1)(5.1)yi(ωTxi+b)⩾1−ξi,i=1,2,...,m

但同时，我们希望这个 ξiξi 尽可能小一点，越小不就越接近前面推导的线性可分么。在目标函数中体现这一点，就得到新的优化问题（对比2.2式）：

⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪mins.t.12∥ω∥2\+C∑i=1mξiyi(ωTxi\+b)⩾1,i=1,2,...,mξi>0(5.2)(5.2)\{min12‖ω‖2+C∑i=1mξis.t.yi(ωTxi+b)⩾1,i=1,2,...,mξi>0

C是衡量我们“放宽力度”的常数。  
与前面的推导类似，我们得到新的拉格朗日函数：

L(ω,b,ξ,α,μ)=12∥ω∥2\+C∑i=1mξi\+∑i=1mαi\[1−ξi−yi(ωTxi\+b)\]−∑i=1mμiξi(5.3)(5.3)L(ω,b,ξ,α,μ)=12‖ω‖2+C∑i=1mξi+∑i=1mαi\[1−ξi−yi(ωTxi+b)\]−∑i=1mμiξi

分别令 L(ω,b,ξ,α,μ)L(ω,b,ξ,α,μ) 对 ω,b,ξiω,b,ξi 的导数等于0：

∂L(ω,b,ξ,α,μ)∂ω=ω−∑i=1mαiyixi=0(5.4)(5.4)∂L(ω,b,ξ,α,μ)∂ω=ω−∑i=1mαiyixi=0

∂L(ω,b,ξ,α,μ)∂b=∑i=1mαiyi=0(5.5)(5.5)∂L(ω,b,ξ,α,μ)∂b=∑i=1mαiyi=0

∂L(ω,b,ξ,α,μ)∂ξi=C−αi−μi=0(5.6)(5.6)∂L(ω,b,ξ,α,μ)∂ξi=C−αi−μi=0

将（5.4）（5.5）（5.6）代入（5.3）得到对偶问题：

⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪maxαs.t.∑i=1mαi−∑i=1m∑j=1mαiαjyiyjxTixj∑i=1mαiyi=00⩽αi⩽C(5.7)(5.7)\{maxα∑i=1mαi−∑i=1m∑j=1mαiαjyiyjxiTxjs.t.∑i=1mαiyi=00⩽αi⩽C

KKT条件：

⎧⎩⎨⎪⎪⎪⎪⎪⎪αi⩾0,μi⩾0yi(ωTxi\+b)−1\+ξi⩾0αi\[yi(ωTxi\+b)−1\+ξi\]=0ξi⩾0,μiξi=0(5.8)(5.8)\{αi⩾0,μi⩾0yi(ωTxi+b)−1+ξi⩾0αi\[yi(ωTxi+b)−1+ξi\]=0ξi⩾0,μiξi=0

根据这些条件，用SMO算法求解就可以了，只是在求解相关变量的时候注意有新的范围限制。

从另一个角度观察（5.2），我们可以把 12∥ω∥212‖ω‖2 看成是一个正则化项，也就是结构风险，描述了我们希望模型具有某些性质，也就是引入了先验知识。 C∑mi=1ξiC∑i=1mξi 项是经验风险，用于描述模型与训练集的契合程度，可以把ξiξi写成一个更一般的形式：l(f(xi),yi)l(f(xi),yi)，上面推导的模型我们可以认为 ll 是 hinge损失：l(f(xi),yi)=max(0,1−yif(xi))l(f(xi),yi)=max(0,1−yif(xi))。  
从这里也可以看出，引入先验知识，可以减小模型求解时的搜索空间，因为我们给了它一个目标：间隔最大化。

[geometric_margin.png]: /images/20220526/7f78b4bcc0144d16abba55c946d40a4e.png
[Svm_max_sep_hyperplane_with_margin.png]: https://upload.wikimedia.org/wikipedia/commons/2/2a/Svm_max_sep_hyperplane_with_margin.png
[Optimal-Hyper-Plane-2.png]: /images/20220526/5920c0b377954ed19a0eb2d06add7fd5.png