传统机器学习(七)支持向量机(1)

1 算法概述

1.1 超平面的理解

1.1.1 超平面公式

我们对“平面”概念的理解，一般是定义在三维空间中的，如下：

在这里插入图片描述

假设M和M0为平面上的两点，n为该平面的法向量，那么，通过下图可以容易推导出三维空间中的平面方程：
$A x + B y + C z + D = 0$
在这里插入图片描述

我们把A、B、C写作w，把x、y、z写作x，且拓展到n维空间：
$w_1x_1 + w_2x_2 + w_3x_3 + ...+w_nx_n + b=w^Tx + b=0$
因此，n维空间的超平面方程为
$\omega^T x + b = 0$
虽然当维度大于3才可以成为“超”平面，但是你仍然可以认为，一条直线是 R2 空间内的超平面，一个平面是 R3 空间内的超平面。Rn 空间的超平面是Rn 空间内的一个 n - 1 维的仿射子空间。

1.1.2 点到超平面的距离公式推导

我们已经知道，超平面A可以表达为：
$\omega^T x + b = 0$
假设x'为超平面上任意一点，那么显然就满足：
$\omega^T x’ + b = 0 (公式1)$

我们知道，对于空间上任意一点 x，到平面 A 的距离 H，等于向量 xx’ 在平面A法向量上的投影。

在这里插入图片描述

而计算投影，将 xx’ 乘以法向量 w 即可。并且，我们不光要投影，还要计算单位，即使用单位为 1 的投影。也就是在分母除以 || w ||。所以，距离 H 可以表示为：
$\frac{\mid \omega^T (x-x') \mid}{\mid\mid \omega \mid\mid}(公式2)$
然后，将公式1和公式2进行合并。

因此，样本空间中的任意一点 x，到超平面（w,b）的距离，可以表示为
$\frac{\mid \omega^T x + b \mid}{\mid\mid \omega \mid\mid}$

1.2 SVM硬间隔模型和损失函数

SVM硬间隔模型用于样本线性可分的二分类，它的原始目的是找出一个判别面，让样本离判断面的最小距离最大化。硬间隔是相对软间隔模型而言，软间隔不要求样本线性可分。

在这里插入图片描述

不过，由于直接找最优判别面较难找，SVM并不是直接找最优判别面，而是在两类样本之间，引入两个平行的支持面(支持面之间不能有样本)，然后让支持平面尽量撑开。

当两个支持平面的距离最大化时，两个支持平面的中心，就是要找的最优判别面。所以，SVM的直接目标是找出距离最大化的两个支持面，从而找出最优判别面的原始目的。

落在支持面上的样本，称为支持向量，它们是模型的关键样本。

1.2.1 SVM支持面的表达式

（w,b)代表两个支持面的中心平面(即判别面)wx + b = 0，中心平面向两边展开d距离，就是两个支持面。
$(0,+\infty ) \\对平面wx+b=0，\dfrac{1}{\left \| w \right \| } 的取值范围也是 (0,+\infty ) \\不妨用\dfrac{1}{\left \| w \right \| } 来替代d,这样可以消去d$

在这里插入图片描述

因此，SVM对于支持面的表示如下：
$\\ 其中，wx+b=0是两个支持面的中心(即判别面) \\ d=\dfrac{1}{\left \| w \right \| }是支持面离中面心的距离，即由wx+b=0，两边展开\dfrac{1}{\left \| w \right \| } 距离，\\ 就得到了两个支持面$

1.2.2 SVM模型表达式

SVM模型数学表达式为
$\text{y} = \text{sign}(wx+b)$
也就是判断样本是在判别面的正侧还是负侧，从而决定模型是正样本还是负样本。
$\left | \dfrac{wx+b}{\left \| w \right \| } \right | \\ 如果保留距离的正负号，则有 d_{\pm }(x) = \dfrac{wx_i+b}{\left \| w \right \| } \\ 即有：\\ \begin{aligned} &d_{\pm }(x) = \dfrac{wx+b}{\left \| w \right \| } \\ \Rightarrow &d_{\pm }(x) = d*(wx+b) \\ \Rightarrow & \dfrac{ d_{\pm }(x)}{d} = wx+b \end{aligned} \\ 其中 d=\dfrac{1}{\left \| w \right \| }是支持平面到判别平面的距离$
因此，如下图，wx + b的意义是：样本和判别面直接的距离与支持面到判别面的距离的比值，符号代表在判别面的正侧还是负侧。

在这里插入图片描述

1.2.3 SVM模型的损失函数

1.2.3.1 损失函数的推导

优化目标

在这里插入图片描述

目标函数

在这里插入图片描述

1.2.3.2 损失函数的意义

$\dfrac{1}{2} \left \| w \right \|^2 \\ 本质是最小化\left \| w \right \|，\\ 又因为\left \| w \right \|=\dfrac{1}{d}，所以本质是最大化两个支持面之间的距离(2d) \\ 将 \left \| w \right \| 改成 \dfrac{1}{2} \left \| w \right \|^2 ，加平方是为了可以去掉范数里的根号，\\同时乘以\dfrac{1}{2} ，进一步方便损失函数求导后的简洁$

$y_i(wx_i+b)⩾1，可以将它拆成\text{y}_i=1,和 \text{y}_i=-1两种情况 \\ (wx_i+b)⩾1,\text{y}_i=1 \\ (wx_i+b)≤-1,\text{y}_i=-1 \\ wx +b的意义就是样本和判别面直接的距离与支持面到判别面的距离的比值，符号代表在判别面的正侧还是负侧。\\ 因此约束条件是\text{y}_i=1时，即正样本，不能在正支持面的负侧\\ 因此约束条件是\text{y}_i=-1时，即负样本，不能在负支持面的正侧$
损失函数总的意思就是约束两个支持面必须在正负样本之间，且两个支持面之间不能有样本，然后最大化两个支持面之间的距离。

1.2.4 拉格朗日乘子法求解硬间隔损失函数

硬间隔的损失函数
$\dfrac{1}{2} \left \| w \right \|^2 \\ 约束条件: y_i(wx_i+b) - 1⩾0，i=1,2,3,...,N$
带有约束条件，一般先转为拉格朗日函数形式：
$\\ L(w,b,a) = \dfrac{1}{2} \left \| w \right \|^2 - \sum\limits_{i=1}^N a_i[y_i(wx_i+b) - 1] \\ = \dfrac{1}{2} \left \| w \right \|^2 - \sum\limits_{i=1}^Na_iy_i(wx_i+b)+ \sum\limits_{i=1}^Na_i \\ 其中a_i⩾0$
svm求解

-- 满足以下两个条件，可以转为对偶问题
1.目标函数与约束条件是凸函数                  
2.约束条件里，是严格可执行的(即一定有解)
原问题与对偶问题的解就相等,且两个问题的解满足满足KKT条件

在这里插入图片描述

通过拉格朗日乘子法以及对原问题的对偶问题进行求解，我们得到了二次规划的公式。虽然我们已经把式子化简成了只有一种参数α，但这个极值又应该怎么求呢？这需要引入一个新的算法——SMO。

SMO的全写是Sequential Minimal Optimization，翻译过来是序列最小优化算法。算法的核心思想是由于我们需要寻找的是一系列的α值使得二次规划的公式取极值。后续会详细介绍SMO算法。

1.2.5 SVM求解实例

在这里插入图片描述

1.3 SVM软间隔模型和损失函数

由于硬间隔损失函数的前提是样本一定线性可分，但现实中的数据往往无法线性可分，于是，在SVM硬间隔模型的基础上进行改进，提出了SVM软间隔模型。
软间隔SVM模型与硬间隔SVM模型一致，仍然是判别平面+两个支持平面，用(w,b)表示，其中(w,b)代表判别平面，1/|w|代表支持平面到判别平面的距离。
软间隔SVM模型与硬间隔SVM模型不同的是，软间隔SVM允许正支持平面的负侧有正样本，也允许负支持平面正侧有负样本，它的目标在于，尽量让两个支持面的距离更大的同时，样本的错误程度尽量少。

在这里插入图片描述

1.3.1 SVM软间隔模型

SVM模型数学表达式为：
$\text{y} = \text{sign}(wx+b)$
损失函数表达式为：
$\dfrac{1}{2} \left \| w \right \|^2 + C\sum\limits_{i=1}^N\epsilon_i \\ 约束条件: (1) y_i(wx_i+b) - (1-\epsilon_i)⩾0 \\ (2)\epsilon_i⩾0$

约束条件的意义：
$y_i(wx_i+b)⩾(1-\epsilon_i)，可以将它拆成\text{y}_i=1,和 \text{y}_i=-1两种情况 \\ (wx_i+b)⩾(1-\epsilon_i),\text{y}_i=1 \\ (wx_i+b)≤-(1-\epsilon_i),\text{y}_i=-1 \\ 硬间隔y_i(wx_i+b)⩾1，代表正样本不能在正支持面的负侧，现在改为y_i(wx_i+b)⩾(1-\epsilon_i)\\ 其实是引入了松弛变量\epsilon_i，代表允许第i个正样本，可以在正支持面的负侧\epsilon_i位置 \\ 同理，第i个负样本，可以在负支持面的正侧\epsilon_i位置$
在这里插入图片描述

目标函数的意义
$在约束条件的基础上，再在目标函数中，加入对所有样本总偏离的惩罚项C\sum\limits_{i=1}^N\epsilon_i，其中C为惩罚因子。\\ 当C很大的时候，意味着分类严格不能有错误。\\ 当C很大小时候，意味着可以有更大的错误容忍。\\总的损失函数为L(w,b) = \dfrac{1}{2} \left \| w \right \|^2 + C\sum\limits_{i=1}^N\epsilon_i \\ 这样既能够让两个支持面尽量最大化的同时，也在尽量降低支持面没有支持到样本的总偏离总量。$

软间隔支持向量定义

我们已经知道，硬间隔的支持向量，是指落在支持面上的样本。

而软间隔的支持向量，指的是落在支持面上的样本，及支持面没支持住的样本。

实质就是决定支持面的关键样本，在这点上与硬间隔是统一与一致的。不够软间隔支持面不仅要考虑最大间隔，还要考虑没支持住的样本。

在这里插入图片描述

1.3.2 拉格朗日乘子法求解软间隔损失函数

带有约束条件，一般先转为拉格朗日函数形式，再通过交换拉格朗日函数形式中的优化顺序来获得对偶问题。

软间隔损失函数如下：
$\dfrac{1}{2} \left \| w \right \|^2 + C\sum\limits_{i=1}^N\epsilon_i \\ 约束条件: (1) y_i(wx_i+b) - (1-\epsilon_i)⩾0 ，i=1,2,3,...,N\\ (2)\epsilon_i⩾0，i=1,2,3,...,N$

在这里插入图片描述

推导过程可以参考：http://ml.bbbdata.com/site/text/226

1.4 SVM多类别模型

SVM的多类别模型，是基于两分类模型的基础上，进行改进得到的。它将样本数据按类别进行两两建模，最终得到 k*(k-1)/2个模型，k是类别个数。
$个模型分别对样本进行投票，对于用i,j建立的模型，\\ 如果输出的判别值>0，则认为是i类，给i类投一票如果输出的判别值\leqslant0，则认为是j类，给j类投一票 \\ 共 k*(k-1)/2 个模型，所以一共 k*(k-1)/2票，最后哪个类别的得票最多，就认为是哪个类别$