「svm」支持向量机（SVM）从入门到放弃再到掌握

svm

#前言

朋友，你通过各种不同的途经初次接触支持向量机（SVM）的时候，是不是会觉得这个东西耳熟能详，感觉大家都会，却唯独自己很难理解？

每一次你的老板或者同仁让你讲解SVM的时候，你觉得你看过这么多资料，使用过这么多次，讲解应该没有问题，但偏偏在分享的时候结结巴巴，漏洞百出？

每一次机器学习相关的面试在问到支持向量机（SVM）的时候，尽管你觉得你都准备好了，可是一次又一次败下阵来，以至于觉得问那些问题的人（是不是脑子有…）是那么的厉害，每一次都能精准发觉到你的不足和漏洞，让你怀疑你掌握的是假的SVM，然后让你怀疑人生？

那还等什么，快来看看这篇文章吧，原价998，现在只要。。。（不好意思，扯偏了。）

以上可能真的只是我的个人经历（在这里，学渣给各位大佬鞠躬了！），但不管怎么样，我还是要自己写一篇从头到尾的SVM的理解，然后呈现给各位大佬审阅，欢迎您批评指正！

按照以下问题成文：

由线性分类任务开始
为何需要最大化间隔
怎么解决凸二次规划问题
对偶问题的求解
SMO算法
核函数的由来和使用
SVM与LR的异同

#SVM由线性分类开始

在这之前，假设读者们对线性分类模型和向量矩阵求导有大概的了解。

给定训练样本集 $D = (x_{1}, y_{1}), (x_{2}, y_{2}), . . ., (x_{m}, y_{m}))), y_{i} \in {- 1, 1} D={(x_{1},y_{1}),(x_{2},y_{2}),...,(x_{m},y_{m})))}, y_{i}\in \left \{ -1, 1\right \}$ D=(x1,y1),(x2,y2),...,(xm,ym))),yi∈{−1,1}, 线性分类器基于训练样本D 在二维空间中找到一个超平面来分开二类样本。当然，这样的超平面有很多。

这里写图片描述

但我们可以直观感受到，这根红色线代表的超平面抗“扰动”性最好。这个超平面离直线两边的数据的间隔最大，对训练集的数据的局限性或噪声有最大的“容忍”能力。

在这里，这个超平面可以用函数 $f (x) = w^{T} x + b f(x) = w^{T}x+b$ f(x)=wTx+b 表示。当 $f (x) f(x)$ f(x) 等于0的时候，x便是位于超平面

上的点，而 $f (x) f(x)$ f(x) 大于0的点对应 y=1 的数据点， $f (x) f(x)$ f(x) 小于0的点对应y=-1的点。

为什么是 $y_{i} \in {- 1, 1} y_{i}\in \left \{ -1, 1\right \}$ yi∈{−1,1},换句话说， $y y$ y 只能是-1，和1吗？不能是 $y y$ y =-100 表示反例， $y y$ y =2000表示正例，或 $y y$ y =0表示反例， $y y$ y =300表示正例，或 $y y$ y =5表示反例 $y y$ y =-7 表示正例吗？当然可以。y 只是一个label ，标注为{-1，+1}不过为了描述方便。

若 $y y$ y =0表示反例， $y y$ y =300表示正例，只不过分正类的标准变为 $(y - 150 ） * f （ x) > 0 (y-150）*f（x)>0$ (y−150）∗f（x)>0

不妨令：

${\begin{matrix} w^{T} x_{i} + b ⩾ + 1, y_{i} = + 1; \\ w^{T} x_{i} + b \leq - 1, y_{i} = - 1 \end{matrix} \left\{\begin{matrix}w^{T}x_{i}+b \geqslant +1, y_{i} = +1 ;& \\ w^{T}x_{i}+b \leq -1, y_{i} = -1 & \end{matrix}\right.$ {wTxi+b⩾+1,yi=+1;wTxi+b≤−1,yi=−1

为什么可以这么令呢？我们知道，所谓的支持向量，就是使得上式等号成立，即最靠近两条虚边界线的向量。那么，不难理解当 $w^{T} x + b w^{T}x+b$ wTx+b的值大于+1，或小于-1的时候，就更加支持“样本的分类”了。为什么要这么令呢？还是为了计算方便。接着往下看，你一定能悟到这么令的原因。

我们可以计算得到空间中任意样本点 $x x$ x到超平面的距离为： $r = \frac{∣ w^{T} x + b ∣}{∥ w ∥} r = \frac{|w^{T}x+b|}{\left \| w \right \|}$ r=∥w∥∣wTx+b∣。为什么呢？

这里写图片描述

如图所示，有： $x = x_{0} + r \frac{w}{∥ w ∥} x = x_{0}+r\frac{w}{\left \| w \right \|}$ x=x0+r∥w∥w(简单平面几何)

又有： $w^{T} x_{0} + b = 0 w^{T}x_{0}+b = 0$ wTx0+b=0，代入上式，求得： $r = \frac{∣ w^{T} x + b ∣}{∥ w ∥} r = \frac{|w^{T}x+b|}{\left \| w \right \|}$ r=∥w∥∣wTx+b∣。

因为 $y_{i} \in {- 1, 1} y_{i}\in \left \{ -1, 1\right \}$ yi∈{−1,1},，两个异类支持向量到超平面的距离之和（也称为“间隔”）可表示为： $r = \frac{2}{∥ w ∥} r = \frac{2}{\left \| w \right \|}$ r=∥w∥2。

很显然，我们要找到符合这样一个条件的超平面来分开两类数据：

这个超平面离两类样本都足够远，也就是使得“间隔”最大。即最终确定的参数 $w 和 b w 和 b$ w和b,使得 $r r$ r最大。即要：

$_{w, b}^{max} \frac{2}{∥ w ∥}_{w,b}^\textrm{max}\frac{2}{\left \| w \right \|}$ w,bmax∥w∥2

$s . t . y_{i} (w^{T} x_{i} + b) \geq 1 ， i = 1, 2, . . ., m s.t. y_{i}( w^{T}x_{i}+b)\geq 1，i=1,2,...,m$ s.t.yi(wTxi+b)≥1，i=1,2,...,m

这等价于

$_{w, b}^{min} \frac{1}{2} {∥ w ∥}^{2}_{w,b}^\textrm{min}\frac{1}{2}{\left \| w \right \|}^{2}$ w,bmin21∥w∥2

$s . t . y_{i} (w^{T} x_{i} + b) \geq 1 ， i = 1, 2, . . ., m s.t. y_{i}( w^{T}x_{i}+b)\geq 1，i=1,2,...,m$ s.t.yi(wTxi+b)≥1，i=1,2,...,m

由此我们得到了SVM的基本型。

##凸优化

我们可以看到，上面的基本型目标函数是二次的，约束条件是线性的，这是一个凸二次规划问题。可以直接用现成的优化计算包求解。但若利用“对偶问题”来求解，会更高效。

啥是凸？什么是凸优化？
凸优化说的是这么一回事情，
$X \subset R^{n} X\subset R^{n}$ X⊂Rn 为一凸集， $f : X \to R f:X\rightarrow R$ f:X→R 为一凸函数，凸优化就是要找出一点 $x^{*} \in X, x^{*} \in X,$ x∗∈X,使得任意 $x \in X, x \in X,$ x∈X,都满足 $f (x^{*}) \leq f (x) f(x^{*})\leq f(x)$ f(x∗)≤f(x) .
可以想象成给我一个凸函数，我要去找到最低点。当然凸优化是一个很大很厉害的领域，在这里，我们只需要知晓这个问题是这么一回事。然后，这回事要怎么样求解，就好，有兴趣的朋友可以参考凸优化的概念或者Stephen Boyd & Lieven Vandenberghe 的《Convex Optimization》。
为啥叫二次规划问题呢？

据了解（其实就是知道），目标函数和约束条件都为变量的线性函数，叫做-----线性规划问题。

目标函数为变量的二次函数和约束条件为变量的线性函数，叫做-----二次规划问题。

目标函数和约束条件都为非线性函数，叫做-----非线性规划问题。

#对偶问题

对于

$_{w, b}^{min} \frac{1}{2} {∥ w ∥}^{2}_{w,b}^\textrm{min}\frac{1}{2}{\left \| w \right \|}^{2}$ w,bmin21∥w∥2

$s . t . y_{i} (w^{T} x_{i} + b) \geq 1 ， i = 1, 2, . . ., m s.t. y_{i}( w^{T}x_{i}+b)\geq 1，i=1,2,...,m$ s.t.yi(wTxi+b)≥1，i=1,2,...,m

为了后面的描述方便，记这个式子为（1）式。

使用**拉格朗日乘子法**可以得到其“对偶问题”。

这是拉格朗日对偶性，即，通过给每一个约束条件加上一个拉格朗日乘子。然后定义出拉格朗日函数，通过拉格朗日函数将约束条件融合进目标函数中。目的是，只需要通过一个目标函数包含约束条件，便可以清楚解释问题。

比如对（1）式每一个约束（共有m个约束， $y_{i} (w^{T} x_{i} + b) \geq 1 y_{i}( w^{T}x_{i}+b)\geq 1$ yi(wTxi+b)≥1），添加拉格朗日乘子 $α_{i} \geq 0 \alpha _{i} \geq 0$ αi≥0,则整个问题的拉格朗日函数可写为：

$L (w, b, α) = \frac{1}{2} {∥ w ∥}^{2} + \sum_{i = 1}^{m} α^{i} (1 - y_{i} (w^{T} x_{i} + b)) L(w,b,\alpha )= \frac{1}{2}\left \|w\right \| ^{2} +\sum _{i=1}^{m}\alpha ^{i}(1- y_{i}( w^{T}x_{i}+b))$ L(w,b,α)=21∥w∥2+∑i=1mαi(1−yi(wTxi+b))

为什么使用这样的拉格朗日乘子，又为何这样构建？这实际上是因为我们的目标函数是不等式约束，解这样的二次规划问题，我们选择用KKT条件，而KKT条件需要这样的一个约束 $α_{i} \geq 0 \alpha _{i} \geq 0$ αi≥0。最终我们便通过KKT条件来产生原问题的对偶问题。

同样的，将上面这个式子记为（2）式。

可以看到，由于 $α_{i} \geq 0 \alpha _{i} \geq 0$ αi≥0, 这样，但凡有约束条件之一不满足，如 $y_{k} (w^{T} x_{k} + b) < 1 y_{k}( w^{T}x_{k}+b)< 1$ yk(wTxk+b)<1），

$L (w, b, α) = \infty L(w,b,\alpha )= \infty$ L(w,b,α)=∞。只有约束条件均满足的时候，

$L (w, b, α) L(w,b,\alpha )$ L(w,b,α)有最优值，为 $L (w, b, α) = \frac{1}{2} {∥ w ∥}^{2} L(w,b,\alpha )= \frac{1}{2}\left \|w\right \| ^{2}$ L(w,b,α)=21∥w∥2

所以优化 $\frac{1}{2} {∥ w ∥}^{2} \frac{1}{2}\left \|w\right \| ^{2}$ 21∥w∥2 等价于优化 $L (w, b, α) L(w,b,\alpha )$ L(w,b,α)当然，要满足约束条件 $α_{i} \geq 0 \alpha _{i} \geq 0$ αi≥0。

于是，我们的目标函数可以表示为：

$_{w, b}^{m i n}_{w,b}^{min}$ w,bmin $_{_{α \geq 0}}^{m a x}_{_{\alpha\geq 0}}^{max}$ α≥0max $L (w, b, α) L(w,b,\alpha )$ L(w,b,α)

满足一定条件下，等价于（注意，这个满足一定条件，是指满足KKT条件）

$_{_{α \geq 0}}^{m a x}_{_{\alpha\geq 0}}^{max}$ α≥0max $_{w, b}^{m i n}_{w,b}^{min}$ w,bmin $L (w, b, α) L(w,b,\alpha )$ L(w,b,α)

后者把最小和最大的位置交换，这样使得运算方便起来。

##KKT条件

什么是KKT条件？其实在这之前，本文有稍微有提到过。在这里正式介绍一下。

KKT条件是一个线性规划问题能有最优解的充分和必要条件。

一般地，一个最优化数学模型可以表示成如下形式：

$m i n f (x) minf(x)$ minf(x)

$s . t . h_{i} (x) = 0, i = 1, 2, . . ., p s.t. h_{i}(x) = 0 , i = 1,2,...,p$ s.t.hi(x)=0,i=1,2,...,p

$g_{j} (x) \leq 0, j = 1, 2, . . ., q g_{j}(x) \leq 0 , j = 1,2,...,q$ gj(x)≤0,j=1,2,...,q

$x \in X \in R^{n} x\in X \in R^{n}$ x∈X∈Rn

$h (x) h(x)$ h(x) 是等式约束。

$g (x) g(x)$ g(x) 是不等式约束。

$p, q p,q$ p,q 表示约束的数量。

而这个最优化数学模型的最优解 $x^{*} x^{*}$ x∗须满足的条件，即KKT条件为：

$h_{i} (x^{*}) = 0, i = 1, 2, . . ., p h_{i}(x^{*}) = 0 , i = 1,2,...,p$ hi(x∗)=0,i=1,2,...,p,和 $g_{j} (x^{*}) \leq 0, j = 1, 2, . . ., q g_{j}(x^{*}) \leq 0 , j = 1,2,...,q$ gj(x∗)≤0,j=1,2,...,q
$▽ f (x^{*}) + \sum_{i = 1}^{p} λ_{i} ▽ h_{i} (x^{*}) + \sum_{j = 1}^{q} μ_{k} ▽ g_{k} (x^{*}) = 0 \bigtriangledown f(x^{*}) + \sum_{i=1}^{p}\ lambda_{i}\bigtriangledown h_{i}(x^{*}) + \sum_{j=1}^{q} \mu _{k}\bigtriangledown g_{k}(x^{*}) = 0$ ▽f(x∗)+∑i=1pλi▽hi(x∗)+∑j=1qμk▽gk(x∗)=0
$λ_{i} \neq 0, μ_{k} \geq 0, μ_{k} g_{k} (x^{*}) = 0 \lambda _{i}\neq 0, \mu _{k}\geq 0, \mu _{k}g_{k}(x^{*}) = 0$ λi=0,μk≥0,μkgk(x∗)=0

于是我们的整个问题转化为

$L (w, b, α) L(w,b,\alpha)$ L(w,b,α) 对 $w, b w,b$ w,b求最小
再对 $α \alpha$ α 求最大。

对于第一步，先令 $L (w, b, α) L(w,b,\alpha )$ L(w,b,α)对 $w, b w,b$ w,b求偏导为0，可得：

$w = \sum_{i = 1}^{m} α_{i} y_{i} x_{i}, w=\sum_{i=1}^{m}\alpha_{i}y_{i}x_{i},$ w=∑i=1mαiyixi,

$0 = \sum_{i = 1}^{m} α_{i} y_{i} . 0=\sum_{i=1}^{m}\alpha_{i}y_{i}.$ 0=∑i=1mαiyi.

将此两个式子带入（2）式消去 $w, b w,b$ w,b。便得到了（1）式的对偶问题。

$_{α \geq 0}^{m a x} \sum_{i = 1}^{m} α_{i} - \frac{1}{2} \sum_{i, j = 1}^{m} α_{i} α_{j} y_{i} y_{j} x_{i}^{T} x_{j}_{\alpha\geq 0 }^{max}\sum_{i=1}^{m}\alpha_{i}-\frac{1}
{2}\sum_{i,j=1}^{m}\alpha_{i}\alpha_{j}y_{i}y_{j}x_{i}^{T}x_{j}$ α≥0max∑i=1mαi−21∑i,j=1mαiαjyiyjxiTxj

$s . t . \sum_{i = 1}^{m} α_{i} y_{i} . = 0, s.t. \sum_{i=1}^{m}\alpha_{i}y_{i}.=0,$ s.t.∑i=1mαiyi.=0,

$α_{i} \geq 0, i = 1, 2, . . ., m \alpha_{i}\geq 0 , i = 1,2,...,m$ αi≥0,i=1,2,...,m

类比来看，我们的目标函数没有 $h (x) = 0 h(x) = 0$ h(x)=0 的等式约束。

于是，上面的过程，需要满足的KKT条件是

${\begin{matrix} α_{i} \geq 0; \\ 1 - y_{i} (w^{T} x_{i} + b) \leq 0; \\ α_{i} (1 - y_{i} (w^{T} x_{i} + b)) = 0. \end{matrix} \left\{\begin{matrix}\alpha_{i} \geq 0 ;\\1- y_{i}( w^{T}x_{i}+b) \leq 0;\\ \alpha_{i}(1-y_{i}( w^{T}x_{i}+b))=0.\end{matrix}\right.$ ⎩⎨⎧αi≥0;1−yi(wTxi+b)≤0;αi(1−yi(wTxi+b))=0.

我们看到，对于任意样本，总有 $α_{i} = 0 \alpha_{i} = 0$ αi=0 或者 $y_{i} (w^{T} x_{i} + b) = 1 y_{i}( w^{T}x_{i}+b) =1$ yi(wTxi+b)=1 .若 $α_{i} = 0 \alpha_{i} = 0$ αi=0 ，则由 $w = \sum_{i = 1}^{m} α_{i} y_{i} x_{i}, w=\sum_{i=1}^{m}\alpha_{i}y_{i}x_{i},$ w=∑i=1mαiyixi,知 $w = 0 w = 0$ w=0 , 则此 $α_{i} \alpha_{i}$ αi 对应的向量不会对 $f (x) f(x)$ f(x) 的确定有任何影响。而 $α_{i} > 0 \alpha_{i} > 0$ αi>0 时，必有 $y_{i} (w^{T} x_{i} + b) = 1 y_{i}( w^{T}x_{i}+b) =1$ yi(wTxi+b)=1 ，此时 $α_{i} \alpha_{i}$ αi 对应的向量在最大间隔的边缘上（一开始示意图的虚线上），即是支持向量。这也说明，最终模型的确定，只与支持向量有关。

接下来，怎么求 $α \alpha$ α呢？

##SMO算法

###############################

一些延展:

我们可以在这里从损失函数的角度看一下LR与SVM的异同:

对于LR与SVM的异同我总结如下:

LR的详细介绍:https://blog.csdn.net/b285795298/article/details/88683987

- 相同点:

LR和SVM都是分类算法
LR和SVM都是监督学习算法。
LR和SVM都是判别模型。
如果不考虑核函数，LR和SVM都是线性分类算法，也就是说他们的分类决策面都是线性的。
说明:LR也是可以用核函数的.但LR通常不采用核函数的方法.(计算量太大)

LR和SVM不同点:

1、LR采用log损失，SVM采用合页(hinge)损失。

逻辑回归的损失函数：

在这里插入图片描述

支持向量机的目标函数:

在这里插入图片描述

逻辑回归方法基于概率理论，假设样本为1的概率可以用sigmoid函数来表示，然后通过极大似然估计的方法估计出参数的值(基于统计的,其损失函数是人为设定的凸函数) 。支持向量机基于几何间隔最大化原理，认为存在最大几何间隔的分类面为最优分类面.(有严格的推导)

2、LR对异常值敏感，SVM对异常值不敏感(抗燥能力,SVM要强)(https://www.jianshu.com/p/1a41a1567b87)。支持向量机只考虑局部的边界线附近的点，而逻辑回归考虑全局（远离的点对边界线的确定也起作用，虽然作用会相对小一些）。LR模型找到的那个超平面，是尽量让所有点都远离他，而SVM寻找的那个超平面，是只让最靠近中间分割线的那些点尽量远离，即只用到那些支持向量的样本。

支持向量机改变非支持向量样本并不会引起决策面的变化：

在这里插入图片描述逻辑回归中改变任何样本都会引起决策面的变化：

在这里插入图片描述 LR则受所有数据点的影响，如果数据不同类别strongly unbalance，一般需要先对数据做balancing。（引自http://www.zhihu.com/question/26768865/answer/34078149）

3、计算复杂度不同。对于海量数据，SVM的效率较低，LR效率比较高。 对于两者在feature和样本数量不同的情况下的效率问题,可以参考:https://blog.csdn.net/a244659184/article/details/81122521。该文章说明了:

当样本较少，特征维数较低时，SVM和LR的运行时间均比较短，SVM较短一些。准确率的话，LR明显比SVM要高。当样本稍微增加些时，SVM运行时间开始增长，但是准确率赶超了LR。SVM时间虽长，但在接收范围内。当数据量增长到20000时，特征维数增长到200时，SVM的运行时间剧烈增加，远远超过了LR的运行时间。但是准确率却和LR相差无几。(这其中主要原因是大量非支持向量参与计算,造成SVM的二次规划问题)

4、对非线性问题的处理方式不同，LR主要靠特征构造，必须组合交叉特征，特征离散化。SVM也可以这样，还可以通过kernel(因为只有支持向量参与核计算,计算复杂度不高)。(由于可以利用核函数,。SVM则可以通过对偶求解高效处理。LR则在特征空间维度很高时，表现较差。)

5、SVM的损失函数就自带正则！！！（损失函数中的1/2||w||^2项），这就是为什么SVM是结构风险最小化算法的原因！！！而LR必须另外在损失函数上添加正则项！！！

在这里插入图片描述

关于正则化:

给定一个数据集，一旦完成Linear SVM的求解，所有数据点可以被归成两类

1）一类是落在对应分界平面外并被正确分类的点，比如落在正分界左侧的正样本或落在负分界右侧的负样本

2）第二类是落在gap里或被错误分类的点。

在这里插入图片描述

假设一个数据集已经被Linear SVM求解，那么往这个数据集里面增加或者删除更多的一类点并不会改变重新求解的Linear SVM平面。这就是它区分与LR的特点，下面我们在看看LR。

值得一提的是求解LR模型过程中，每一个数据点对分类平面都是有影响的，它的影响力远离它到分类平面的距离指数递减。换句话说，LR的解是受数据本身分布影响的。在实际应用中，如果数据维度很高，LR模型都会配合参数的L1 regularization。

要说有什么本质区别，那就是两个模型对数据和参数的敏感程度不同，Linear SVM比较依赖penalty的系数和数据表达空间的测度，而（带正则项的）LR比较依赖对参数做L1 regularization的系数。但是由于他们或多或少都是线性分类器，所以实际上对低维度数据overfitting的能力都比较有限，相比之下对高维度数据，LR的表现会更加稳定，为什么呢？

因为Linear SVM在计算margin有多“宽”的时候是依赖数据表达上的距离测度(可以理解为度量标准,即在什么样的标准上计算gap的大小)的，换句话说如果这个测度不好（badly scaled，这种情况在高维数据尤为显著），所求得的所谓Large margin就没有意义了，这个问题即使换用kernel trick（比如用Gaussian kernel）也无法完全避免。所以使用Linear SVM之前一般都需要先对数据做normalization，(这里的normalization是对数据的归一化,注意区分之前的LR在类别不平衡的时候做的balancing)而求解LR（without regularization）时则不需要或者结果不敏感。

同时会有：feature scaling会使得gradient descent的收敛更好。

如果不归一化，各维特征的跨度差距很大，目标函数就会是“扁”的：

（图中椭圆表示目标函数的等高线，两个坐标轴代表两个特征）

这样feature scaling之后，在进行梯度下降的时候，梯度的方向就会偏离最小值的方向，走很多弯路。

如果归一化了，那么目标函数就“圆”了：

在这里插入图片描述每一步梯度的方向都基本指向最小值，可以大踏步地前进。（引自https://www.zhihu.com/question/37129350）

向您推荐我的其他文章:

支持向量机（SVM）从入门到放弃再到掌握 :https://blog.csdn.net/b285795298/article/details/81977271

逻辑回归(logistic regression-LR)从入门到放弃再到掌握 :https://blog.csdn.net/b285795298/article/details/88683987

决策树（decesion Tree）从入门到放弃再到掌握 :https://blog.csdn.net/b285795298/article/details/89086854

随机森林(Random forest) 从入门到放弃再到掌握:https://blog.csdn.net/b285795298/article/details/89084257

#######################################################

参考博文：

机器学习中的线性代数之矩阵求导 https://blog.csdn.net/u010976453/article/details/54381248

周志华老师的《机器学习》

参考:：https://www.jianshu.com/p/e8dca5613da6

https://www.jianshu.com/p/1a41a1567b87

https://www.cnblogs.com/bentuwuying/p/6616761.html

https://blog.csdn.net/zwqjoy/article/details/82312783

支持向量机（SVM）从入门到放弃再到掌握

svm

对于LR与SVM的异同我总结如下:

- 相同点:

LR和SVM不同点:

相关阅读

栏目导航

推荐阅读

热门阅读