支持向量机 SVM | 线性可分：硬间隔模型公式推导

在开始讲述SVM算法之前，我们先来看一段定义：

'''
支持向量机(Support VecorMachine, SVM)本身是一个二元分类算法，支持线性分类和非线性分类的分类应用，同时通过OvR或者OvO的方式可以应用在多元分类领域中能够直接将SVM应用于回归应用中
在不考虑集成学习算法或者特定的数据集时，SVM在分类算法中可以说是一种特别优秀的算法
'''

一. SVM的优越性

在Logistic回归算法中：
    我们追求是寻找一条决策边界，即找到一条能够正确划分所有训练样本的边界；
    当所有样本正确划分时，损失函数已降至最低，模型不再优化

在SVM算法中：
    我们追求是寻找一条最优决策边界

	那什么是最优呢？SVM提出的基本思想是，寻找一条决策边界，使得该边界到两边最近的点间隔最大这样做得目的在于：相比于其他边界，svm寻找到的边界对于样本的局部扰动容忍性最好，对新进样本更容易判断正确；也就是说，此时决策边界具有最好的鲁棒性

二. SVM算法推导

	注意：下面讲述的是线性分类

这里我们换一种思路寻找最佳决策边界：

首先假设决策边界为
$$y=\overrightarrow{\omega }\cdot \overrightarrow{x}+b$$

公式解释1：
 
为什么要这么设方程呢？

我们希望通过向量点乘来确定距离
换句话说，希望通过向量点乘来确定正负样本的边界

为了寻找最佳决策边界，我们可以：
以上述决策边界为中心线，向两边做平行线，让这两条平行线过两边最近的样本点；此时会形成一条“街道”，最佳决策边界就是使这条街道最宽的那个决策边界。

补充一点：
在Logistic回归算法中，我们人为的将数据集设为1，0
在SVM算法中，我们人为的将数据集设为1，-1
 
参数说明：

width：街宽
 
$\overrightarrow{\omega }$：决策边界的法向量
 
$\overrightarrow{u_{-}}$：街边上的负样本向量
 
$\overrightarrow{u_{+}}$：街边上的正样本向量
 
单位向量：$\frac{\overrightarrow{a}}{\Vert a\Vert }$

向量点乘几何的意义：
$\overrightarrow{a}\cdot \overrightarrow{b}=\left|\overrightarrow{a}\right||\overrightarrow{b}|\cos \theta$
可以理解为$\overrightarrow{a}$ 在$\overrightarrow{b}$上的投影长度乘以$|\overrightarrow{b}|$的模长

对于训练集中的任何一个数据，我们总会取到一个合适长度的$\overrightarrow{\omega }$，以及一个适合的常数b，得到：
$$\{\begin{array}{c}\overrightarrow{\omega }\cdot \overrightarrow{u_{+}}+b\ge 1\\ \overrightarrow{\omega }\cdot \overrightarrow{u_{-}}+b\le -1\end{array}$$

即可以合并为：$$y_i(\overrightarrow{\omega }\cdot \overrightarrow{u_i}+b)\ge 1$$
而对于街边点而言，满足
$$y_i(\overrightarrow{\omega }\cdot \overrightarrow{u_i}+b)=1$$

	注意：这些街边点对于决定决策边界取决定性作用，因此被称为支持向量

---

这样，我们就可以用数学方式将上述街宽抽象出来：
$$width=(\overrightarrow{u_{+}}-\overrightarrow{u_{-}})\cdot \frac{\overrightarrow{w}}{\Vert w\Vert }$$
推导式子，就可以进一步得到：

$width=(\overrightarrow{u_{+}}-\overrightarrow{u_{-}})\cdot \frac{\overrightarrow{w}}{\Vert w\Vert }$

       $=\frac{\overrightarrow{u_{+}}\cdot \overrightarrow{{\omega }_{}}}{\Vert \overrightarrow{\omega }\Vert }-\frac{\overrightarrow{u_{-}}\cdot \overrightarrow{{\omega }_{}}}{\Vert \overrightarrow{\omega }\Vert }$

       $=\frac{1-b}{\Vert \overrightarrow{w}\Vert }-\frac{-1-b}{\Vert \overrightarrow{w}\Vert }$

       $=\frac{2}{\Vert \overrightarrow{w}\Vert }$

此时，我们要求街宽最大，即是求$min(\Vert \overrightarrow{w}\Vert )$，这里为了后续求导方便，将值写成$min(\frac{1}{2}{\Vert \overrightarrow{w}\Vert }^2)$

需要明确，"街边"最大值的条件是基于支持向量的，而支持向量是属于数据集的，因此我们的问题就变成了：
$$\{\begin{array}{c}min(\frac{1}{2}{\Vert \overrightarrow{w}\Vert }^2)\\ s.t.y_i(\overrightarrow{\omega }\cdot \overrightarrow{x}+b)-1\ge 0\end{array}$$

这是一个典型的条件极值问题，我们用拉格朗日乘数法，得到拉格朗日函数为：
$$L=\frac{1}{2}{\Vert \overrightarrow{w}\Vert }^2-\sum _{i=1}^m{\beta }_i[y_i(\overrightarrow{\omega }\cdot \overrightarrow{x}+b)-1],({\beta }_i\ge 0)$$

这里的约束是不等式约束，所以要使用KKT条件(KKT是拉格朗日乘数法的一种泛化形式，此时${\beta }_i\ge 0$)，而KKT条件的计算方式为：$$\underset{\beta \ge 0}{\max }\underset{w,b}{\min }L(w,b,\beta )$$

$$\frac{\partial L}{\partial w}=w-\sum _{i=1}^m{\beta }_i{x}^{(i)}{y}^{(i)}=0\Rightarrow w=\sum _{i=1}^m{\beta }_i{x}^{(i)}{y}^{(i)}$$

$$\frac{\partial L}{\partial b}=-\sum _{i=1}^m{\beta }_i{y}^{(i)}=0\Rightarrow 0=\sum _{i=1}^m{\beta }_i{y}^{(i)}$$

公式解释：
$\beta$是每个样本对应的拉格朗日乘子

对于非支持向量而言， $\beta =0$，即对非支持向量无约束

则：$y^{(i)}\ast 0=0$

对于支持向量而言， $\beta >0$，即对支持向量有约束

则：$正样本支持向量\ast 1+负样本支持向量\ast (-1)=0$

此时$L(\beta )$为：

$L(\beta )=\frac{1}{2}{\Vert \overrightarrow{w}\Vert }^2-{\sum }_{i=1}^m{\beta }_i[y^{(i)}({\omega }^T\cdot x^{(i)}+b)-1]$

      $=\frac{1}{2}{\omega }^T\omega -{\sum }_{i=1}^m{\beta }_i{y}^{(i)}{\omega }^T\cdot x^{(i)}-b{\sum }_{i=1}^m{\beta }_i{y}^{(i)}+{\sum }_{i=1}^m{\beta }_i$

      $=\frac{1}{2}{\omega }^T{\sum }_{i=1}^m{\beta }_i{x}^{(i)}{y}^{(i)}-{\sum }_{i=1}^m{\beta }_i{y}^{(i)}{\omega }^T{x}^{(i)}+{\sum }_{i=1}^m{\beta }_i$

      $=-\frac{1}{2}{\omega }^T{\sum }_{i=1}^m{\beta }_i{x}^{(i)}{y}^{(i)}+{\sum }_{i=1}^m{\beta }_i$

      $=-\frac{1}{2}({\sum }_{j=1}^m{\beta }_j{x}^{(j)}{y}^{(j)}{)}^T({\sum }_{i=1}^m{\beta }_i{x}^{(i)}{y}^{(i)})+{\sum }_{i=1}^m{\beta }_i$

      $=-\frac{1}{2}{\sum }_{j=1}^m{\beta }_j{x}^{(j{)}^T}{y}^{(j)}{\sum }_{i=1}^m{\beta }_i{x}^{(i)}{y}^{(i)}+{\sum }_{i=1}^m{\beta }_i$

      $={\sum }_{i=1}^m{\beta }_i-\frac{1}{2}{\sum }_{i=1}^m{\sum }_{j=1}^m{\beta }_i{\beta }_j{y}^{(i)}{y}^{(j)}{x}^{(j{)}^T}{x}^{(i)}$

即：$$\{\begin{array}{c}L(\beta )={\sum }_{i=1}^m{\beta }_i-\frac{1}{2}{\sum }_{i=1}^m{\sum }_{j=1}^m{\beta }_i{\beta }_j{y}^{(i)}{y}^{(j)}{x}^{(j{)}^T}{x}^{(i)}\\ s.t:{\sum }_{i=1}^m{\beta }_i{y}^{(i)}=0\end{array}$$

解到这一步，我们发现L函数只与$\beta$有关，所以此时可以直接极大化我们的优化函数，且
$$\underset{\beta \ge 0}{\max }l(\beta )⟶\underset{\beta \ge 0}{\min }-l(\beta )$$
因此，求解$\beta$就变成了
$$\{\begin{array}{c}{\min }_{\beta \ge 0}\frac{1}{2}{\sum }_{i=1}^m{\sum }_{j=1}^m{\beta }_i{\beta }_j{y}^{(i)}{y}^{(j)}{x}^{(j{)}^T}{x}^{(i)}-{\sum }_{i=1}^m{\beta }_i\\ s.t:{\sum }_{i=1}^m{\beta }_i{y}^{(i)}=0\end{array}$$

但是对于$\beta$，可以使用SMO算法求得；对于SMO算法，我们先放一放

这里，假设我们用SMO求得了$\beta$的最优解，那么我们可以分别计算得到对应的：

$w={\sum }_{i=1}^m{\beta }_i{x}^{(i)}{y}^{(i)}$
b：一般使用所有支持向量的计算均值作为实际值

怎么得到支持向量呢？
$\beta =0$，该样本不是支持向量
$\beta >1$，该样本是支持向量

小节

对于线性可分的m个样本(x1,y1)，(x2,y2)… ：

	x为n维的特征向量y为二元输出，即+1，-1

SVM的输出为w，b，分类决策函数

通过构造约束问题：
$$\{\begin{array}{c}{\min }_{\beta \ge 0}\frac{1}{2}{\sum }_{i=1}^m{\sum }_{j=1}^m{\beta }_i{\beta }_j{y}^{(i)}{y}^{(j)}{x}^{(j{)}^T}{x}^{(i)}-{\sum }_{i=1}^m{\beta }_i\\ s.t:{\sum }_{i=1}^m{\beta }_i{y}^{(i)}=0\end{array}$$
使用SMO算法求出上述最优解$\beta$
找到所有支持向量集合：
$$S=(x^{(i)},y^{(i)})(\beta >0,i=1,2,...,m)$$
从而更新w，b

$w={\sum }_{i=1}^m{\beta }_i{x}^{(i)}{y}^{(i)}$

$b=\frac{1}{S}{\sum }_{i=1}^S(y^s-{\sum }_{i=1}^m{\beta }_i{x}^{(i{)}^T}{y}^{(i)}{x}^s)$

构造最终的分类器，为：
$$f(x)=sign(w\ast x+b)$$

	x<0时，y=-1x=0时，y=0x>0时，y=1注意：假设，不会出现0若出现，正负样本随意输出一个，即+0.00000001或-0.00000001都可以

概念

最后，我们定义具体概念：

分割超平面(Separating Hyperplane)：将数据集分割开来的直线、平面叫分割超平面

支持向量(Support Vector)：离分割超平面最近的那些点叫做支持向量

间隔(Margin)：支持向量数据点到分割超平面的距离称为间隔；任何一个支持向量到分割超平面的距离都是相等的

---

感谢阅读🌼
如果喜欢这篇文章，记得点赞👍和转发🔄哦！
有任何想法或问题，欢迎留言交流💬，我们下次见！
本文相关代码存放位置
    

祝愉快🌟！

---