SVM的简介

1.SVM要解决的问题

对于线性可分的问题，我们可以得到很多的决策面将不同类别的样本分开，以二分类为例，如图所示，可以画出很多决策面（在二维平面上，决策面退化为线）
在这里插入图片描述
那么SVM希望解决的就是，找到这众多决策面中，最优的决策面，使得模型更具有鲁棒性，也就是找到两类样本的最大间隔，如图所示：

2.SVM与逻辑回归的区别

SVM的决策面只与支持向量（与决策面距离最近的向量）有关，而逻辑回归与所有向量都有关系，即在不改变支持向量的情况下，改变其他的点，SVM的决策面不变，而逻辑回归的结果会发生变化，即SVM抗干扰的能力更强，更具有鲁棒性。
这是因为逻辑回归中梯度更新的方式为：
在这里插入图片描述
而 $\sigma ( x)$ 的函数为

因此对于任何样本点， $y-\sigma \left( \theta ^{T} x\right)$ )的值都不会为0，即数据变化，就会影响 $\theta$ 的值，也就会影响决策面。
第二种方式理解，如下图所示：

目标函数为：

则进行预测时：
在这里插入图片描述
当样本点离决策面越远， $s(x)$ )越大，但是 $1/(1+e^{-s(x)})$ 永远不会等于1，误差永远存在，梯度也就永远存在，进而会更新参数，影响最终的决策面。

3.SVM的推导

1.一些变量定义：
1.特征向量： $x$
2.类别标签： $y\in \{-1,1\}$
3.待优化参数： $b,w$
4.预测函数：

$\begin{array}{l} h_{w,b}( x) =g\left( w^{T} x+b\right)\\ g( z) =+1\ \ \ z\geqslant 0\\ g( z) =-1\ otherwise \end{array}$

这里我们把负样本的标签定义为-1，为了后期计算的方便。
物理意义方面：
（1） $w$ 表示决策面的法向量，它决定了决策面的朝向
（2） $b$ 表示决策面到原点的距离（函数距离，不是物理上的几何距离）

2.几何间隔与函数间隔：
如图所示
在这里插入图片描述
我们定义函数间隔为： $\hat{\gamma }^{( i)} =y^{( i)}\left( w^{T} x^{( i)} +b\right)$
等比例缩放 $w,b$ 并不会改变决策面函数，而函数间隔可以进行不同比例的调整，即 $g\left( w^{T} x+b\right) =g\left( 2w^{T} x+2b\right)$
几何间隔也就是物理上的距离，为： $\gamma ^{( i)} =y^{( i)}\left( w^{T} x^{( i)} +b\right)$ ),其中 $||w||^{2} =1$ ,即单位法向量。

注意几何间隔是唯一的，有确定的物理意义；函数间隔不唯一，可以对w,b进行不同程度的缩放。

3.决策边界
根据上面的定义，我们可以写出决策边界的函数表达式为： $w^{T}\left( x^{( i)} -\gamma ^{( i)} y^{( i)}\frac{w}{||w||}\right) +b=0$
辅助下图可以更好的帮助我们理解该表达式：
在这里插入图片描述
从中我们可以推出几何间隔为：进行等比缩放的，换句话说想要多大要多大，想要多小要多小，都能满足决策面方程。

因为我们的优化参数是 $w,b$ ),而在上式中， $w$ )在优化目标的分母上，导致优化目标不是凸函数，为我们求解带来不便，考虑到函数间隔可以根据 $w,b$ )进行任意的调整，我们可以将函数间隔固定为1，即 $\hat\gamma=1$
从而我们的优化目标可以写成： $![](https://www.nowcoder.com/equation?tex=%20%5Cbegin%7Barray%7D%7Bl%7D%0Amax%5C%20%5Cfrac%7B1%7D%7B%7C%7Cw%7C%7C%7D%5C%5C%0As.t.%5C%20y%5E%7B(%20i)%7D%5Cleft(%20w%5E%7BT%7D%20x%5E%7B(%20i)%7D%20%2Bb%5Cright)%20%5Cgeqslant%201%20%2Ci%3D1%2C...%2Cm%0A%5Cend%7Barray%7D&preview=true)![](https://www.nowcoder.com/equation?tex=%0A%E8%BF%99%E6%97%B6%E8%A7%82%E5%AF%9F%E4%BC%98%E5%8C%96%E7%9B%AE%E6%A0%87%E5%8F%98%E6%88%90%E5%85%B3%E4%BA%8E&preview=true)||w||![](https://www.nowcoder.com/equation?tex=%E7%9A%84%E5%8D%95%E8%B0%83%E5%87%BD%E6%95%B0%EF%BC%8C%E7%AD%89%E4%BB%B7%E4%BA%8E%EF%BC%9A%0A&preview=true)![](https://www.nowcoder.com/equation?tex=%20%5Cbegin%7Barray%7D%7Bl%7D%0Amax%5C%20%5Cfrac%7B1%7D%7B2%7D%20%7C%7Cw%7C%7C%5E%7B2%7D%5C%5C%0As.t.%5C%20y%5E%7B(%20i)%7D%5Cleft(%20w%5E%7BT%7D%20x%5E%7B(%20i)%7D%20%2Bb%5Cright)%20%5Cgeqslant%201%20%2Ci%3D1%2C...%2Cm%0A%5Cend%7Barray%7D&preview=true)$
至此，我们将该问题转化为了凸集上的凸优化问题！便于使用优化方法进行求解。

SVM的优化

1.准备工作-拉格朗日函数-对偶问题

1.拉格朗日函数
对于凸优化问题：
在这里插入图片描述
可以定义拉格朗日函数：

该问题的解为拉格朗日函数偏导为0的点，即

因为 $f(w)$ 为凸函数，其等高线为椭圆形。

同样对于含有不等约束的优化问题（该问题就和SVM的优化目标一样了，求解了该问题就求解了SVM的优化问题）：
在这里插入图片描述
依然可以定义拉格朗日函数：

注意转化成 $\mathcal{L}( w,\alpha ,\beta )$ )后，引入了 $\alpha,\beta$ 变量，这个问题如何来优化求解呢？
我们定义原问题如下：

分析一下这个原问题：
对于一个给定的 $w$ ),如果存在 $g_{i}( w) >0\ \ \ or\ \ \ h_{i}( w) \neq 0$ ),那么一定能够找到 $\alpha,\beta$ )，使得 $\theta _{\mathcal{P}}( w)\rightarrow +\infty$
而如果我们的 $w$ )满足了原始优化问题的所有约束，即 $g_{i}( w) \leqslant 0,\ h_{i}( w) =0$ ),那么一定有 $\theta _{\mathcal{P}}( w) =f( w)$ ),因为 $g_{i}( w) \leqslant 0$ ),对于 $g_{i}( w) = 0$ )的部分， $\alpha$ )可以去大于等于0的所有值，而 $g_{i}( w) < 0$ )的部分，必有 $\alpha=0$ )，而 $h(w)=0$ ),因此 $\beta$ )可以任意取，总之 $\mathcal{L}( w,\alpha ,\beta )$ 后两项为0。
根据以上的分析，我们可以定义最小化优化问题：
在这里插入图片描述
该问题和原始问题等价：

那么这样做的好处是什么？可以发现我们定义的最小化优化问题扔掉了约束项，直接对 $w$ 进行优化，转化为无约束优化问题！！！
2.对偶问题
先说一下我们为什么要考虑对偶问题，因为我们定义的最小化优化问题其实实际上是对 $w$ )的优化问题，而无法对 $\alpha,\beta$ )进行求解，而最后的 $w$ )结果又与 $\alpha,\beta$ )有关。因此我们需要求解出 $\alpha,\beta$ )，而通过对偶问题求解出 $\alpha,\beta$ 。
对偶优化问题为：
原问题为：
图片说明
定义它的对偶优化问题：

即交换了最大最小值的位置。很显然，先最大化再最小化>先最小化再最大化：
直观的理解：

严格证明：

当满足KKT条件时，取得等号，KKT条件为：

即 $图片说明$ 是凸函数， $图片说明$ 是线性函数，则存在 $图片说明$ ，且二者等价。

SVM的求解

svm的优化问题是：
图片说明
为了方便用上述优化方法求解，将约束条件进行转化：

从而满足标准的优化问题：

考虑等于0的条件，函数间隔为1，也就是最小的函数间隔，因为我们之前设置了最小的函数间隔为1

根据该优化问题，构造拉格朗日函数：
图片说明
函数的极值点对应偏导为0的点，对拉格朗日函数求偏导：

因为y=1或-1，单纯看b的偏导，其说明要保证正负支持向量的系数 $图片说明$ 加在一起为0，将结果带入拉格朗日函数：

写成了关于 $图片说明$ 的函数，因此只要求解出 $图片说明$ 就能优化方程的解。
而 $图片说明$ 可以通过对偶问题简单求得，从而问题得到解决：

求解出来可以发现，其实只有支持向量的 $图片说明$ 不为0，其他向量的 $图片说明$ 全部为0，也就是决策面由支持向量唯一决定。
当知道 $图片说明$ 之后，
w的求解：

b的求解：

对于一个新的样本，判断其所属类别：

可以看到真正在使用时，我们用到的只是支持向量和 $图片说明$ ，而并不关心真正的w*的取值。