vlambda博客
学习文章列表

这几天一直都在下雨，如果拿我家里的7月和8月放在一起对比还真的很鲜明：

7月一天到晚出太阳，我看着手机里各地防汛的新闻抬头看着太阳说：“你咋这么争气”

8月一天到晚就下雨，我看着手机里懂王的朋克操作抬头看着太阳说：“你咋这么不争气”

还想到8月的某个时候我要回一趟上海，就很兴奋

是真的回去待一段时间，但是时间还没确定

这写着呢，台风来了

时不时写笔记的好处就是能够巩固自己之前学习的东西

同时也想抛砖引玉一下，要是有大佬发现了我的笔记出现啥错误，欢迎指出，感激不尽😄

开始吧

yysy，Mathtype是真的好用

头发也掉的好多

作为机器学习的一个经典算法，支持向量机在我看来是一个非常优雅的，能够非常直观的对高维空间当中的样本进行分类的算法模型。

这一个算法我就不像随机森林一样举真实例子了

咱们假设一个二分类问题。需要将正类样本与反类样本进行分类。

这时候，咱们可以将一个样本的输入值构建成为一个输入空间。

这一个输入空间可以是离散的，也可以是连续的欧几里得空间。

咱们在构建一个特征空间。

这个特征空间可以是欧几里得空间，也可以是希尔伯特空间（维度可以为无限维）。

那么这个时候，就可以分出两种支持向量机的算法

1. 线性可分支持向量机

2. 非线性支持向量机器

前者输入空间与特征空间是一一对应的

后者输入空间通过一个非线性映射（核函数）将输入空间映射到特征空间当中。

在这次的笔记当中，我们介绍线性可分支持向量机，非线性的看心情吧

目录：

1. 线性可分支持向量机引入

2. 函数间隔与几何间隔

3. 线性可分支持向量机优化问题求解推导

4. 对偶问题求解
   

5. 序列最小优化算法

6. 线性支持向量机学习算法

7. 结束语
   

好，咱们开始

1.线性可分支持向量机引入

   

假设我们拥有含有N个样本的训练集

其中

那么，当输入样本没有标签的时候怎么样区分正类样本和反类样本呢？

咱们可以通过含有足够数量的训练集，通过学习算法学习出一个分类决策函数，使得分类决策函数在输入一个样本之后，映射得到一个+1或者-1的二值输出，最后完成分类。

在这里，分类决策函数的形式如下

括号里面的形式是不是有点熟悉？

当x为一维的时候就是咱们熟悉的直线方程

好，这时候，令

那么这时候这一个函数所指向的在n维欧几里得空间当中的平面就为分离超平面，咱们支持向量机的核心问题就是求出这一个超平面。并且这个超平面能够最大程度的将正类样本与反类样本区分开来，除此之外，还需要拥有一定的抗噪声能力。

咱们的目标就是求得其中的两个参数

通过这两个参数，我们就可以将正类样本与反类样本分开来

和这一个分离超平面平行的，穿过距离分离超平面最近的样本的向量，称为支持向量。支持向量机一共有2个支持向量，分离超平面就在两个支持向量的中间。

2.函数间隔与几何间隔

在学习如何求取这个超平面之前，我们需要知道，怎么样衡量不同的超平面分类能力的好坏

先观察一下如下这3个超平面

按照直觉，肯定是第三个更好，但是如何以量化的方式衡量这个超平面呢？

引入几何间隔。

在介绍几何间隔之前，先介绍函数间隔

定义超平面关于训练集T的函数间隔为：超平面关于训练集T当中所有样本点的函数间隔的最小值

即：

但是，如果成倍的改变两个参数的值，这时候超平面在欧氏空间当中的位置不会变化，但是函数间隔将会变成原来的2倍。

为解决这个问题，我们可以引入一个约束：令的范数为1

即

这时候，函数间隔就会变成

该间隔就会变为几何间隔。

形象化来说就是每一个样本距离超平面的几何距离，也就是图中的两条紫色线的长度。

定义超平面关于训练集T的几何间隔为：超平面关于训练集T当中所有样本点的几何间隔的最小值

即：

回到那3张图

咱们可以很明显的找到，从上至下的第三张图当中的最小的几何间隔很明显比第一张图和第二张图当中的最小几何间隔要大。

这时候很明显，第三张图是最优的。

好，在了解了如何求取几何间隔之后，支持向量机的核心思想为：

1. 求解能够正确划分训练数据集并且几何间隔最大的分离超平面
   

2. 通过分离超平面，以充分大的确信度对训练数据进行分类
   

咱们需要做的就是求得在这个评价标准下最优的超平面，并且尽可能对未知的新样本具有很好的分类预测能力。

这个问题，可以表示成为下面的约束最优化问题

小学二年级级别公式讲解：

s.t. 为受限制与某个条件

假设咱们的正类y值为+1，反类y值为-1，那么，一个能全部将二分类样本分割开的支持向量机

反类样本括号当中的得数就为负数(wx+b)<0;

正类样本括号当中的得数就为正数(wx+b)>0;

在乘上它们的标签，正类y值为+1，反类y值为-1

就能保证

这玩意永远是正数（>0)

如果得到的是负数，说明分类错了，需要继续优化

那么，如果得到了全都是正数，那么距离超平面最近那一个样本点作为最小值，其他的样本点距离超平面的距离一定大于这个最小值，支持向量机就满足这个限制条件，在这个限制条件下，目标函数是我们需要将这个最小间隔拉到最大。

那么怎么求得这个超平面呢

3.线性可分支持向量机优化问题求解推导

预告：本节非常硬核，请耐心观看

你可以将高数连同线代当中的知识全部串联起来，这可是一个不可多得的机会哦

本推导比较详细

这个是咱们的优化问题

从上面我们可以知道，几何间隔和函数间隔其实只差了一个常数，那么，我们可以尝试将这一个常数放进优化目标里边，得到

因为γ是一个正常数嘛，咱们把它变成0不影响限制条件的发挥

我们从初中知识可以知道二维下点到直线的距离公式

那么，拓展到n维空间的形式为

这时，优化问题当中的γ就可以如下的式子表示

因为

这一坨等价与min后面的那一坨，那么咱们把abs后边那一坨换掉

那么这时候，优化问题就变成了这个形式

w的二范数是一个常数，咱们往前挪无所谓

咱们令

有

整理一下

这时候，为了保证向量的范数为1，我们可以令r=1，这时，有

那么，咱们对w这个向量范数的倒数求最大值，完全可以把它转变为对w这个向量本身的范数求最小值，即

整理一下

在这之后，我们要对优化的函数进行求导，可是对一个向量的范数进行求导得到的式子很复杂，那么我们可以把它等价替换成向量w的内积，并且在其前面加上1/2，我们可以在求导之后保证它的系数为1

即

好，是否觉得这一个优化问题很陌生呢？

想想高数下的含有约束条件的极值，也就是在含有下面那个约束条件下，求上面式子的极值。

方法用什么？拉格朗日乘数法！

4.对偶问题求解

如果在复杂的情况下，直接对问题进行求解十分困难，这时候我们需要应用到拉格朗日对偶性这一性质，找到原问题的对偶问题，这样更容易求解。

咱们定义拉格朗日函数

为了去掉w和b的约束

所以咱们引入拉格朗日对偶性

为了不先求出N个拉格朗日乘子，我们可以假定它们是已知的，用对偶性把它放到后面再求。

咱们现在暂时把它当成一个已知量，因为需要通过下面的式子推导出求拉格朗日乘子数值的式子

咱们定义一个新的函数

这时候，我们假定如果当前w和b违反了我们的约束条件，理想情况下这个函数的值要变成无穷，即

怎么样才能满足这一个假设呢？

咱们就定义符合约束条件约束条件的为0，不符合约束条件的那一个样本点的趋向于无穷即可

这时候，整个式子就能趋向于无穷。

（实际情况下并不需要无穷，只需要变得很大即可）

也就是说，当前w和b所代表的的超平面只要有一个样本分类错误，那么整个式子的值就是无穷。

假设当前w和b所代表的超平面可以将训练数据集当中的每一个样本进行正确的分类，那么每一个样本点所对应的就是0

即

好，这个时候，将原来的式子套回优化问题当中，可以得到

Perfect！咱们成功的将针对w和b的约束条件扔进了拉格朗日函数当中，等效于消去了对w和b的约束条件，只剩下对的约束条件了。

这时候，因为支持向量机是一个凸二次优化问题，咱们天生满足强对偶条件，即：我们可以将上面式子当中的min和max调换位置，为了可以进一步摆脱的束缚，可以先不用把这玩意求出来

得到

到了拉格朗日乘数法求偏导的时候了，先找到w，b的最优解，咱们对w和b分别进行求偏导，得到

代入原来的式子当中，得

这时候，原来的优化问题就变成了

因为我们的支持向量机的优化函数与约束函数均为凸二次函数，约束函数是严格可行的，所以优化问题的最优解满足KKT条件：

这时候

这个时候，咱们支持向量就已经出来了。

决策函数就可以写成

但是，在我们这时候还缺少一样东西：

拉格朗日乘子！

这时候，整个优化问题的求解就转为如何求解拉格朗日乘子的问题了。

5.序列最小最优化算法

各位看官看这一节的时候，可以很明显感觉出来我的话变少了。

因为。。。。。

推导这玩意太累了

好，废话不多说，咱们开始

已知咱们的原问题可以等价于

我们添加一个负号把max换成min

第一条式子就是我们所称的目标函数

这时候我们首先定义惩罚参数C ,(C>0)

若C的值大，这时候对误分类的惩罚增大，反之则变小。

假定我们有一个初始化之后的拉格朗日乘子集，设定乘子集当中的元素初始值为0，这时候我们需要对上面的问题进行求解，找到全局最优的拉格朗日乘子集

给咱们的目标函数设定一个符号

我们知道，支持向量机是一个凸二次优化问题，该问题具有全局最优解，但是当样本量变得很大的时候，直接对这一问题进行求解将会变得非常低效，甚至于不可使用。

这时候，支持向量机常用序列最小优化算法（SMO）对拉格朗日乘子集进行求解

SMO的基本思想是：

1. 假设我们拥有一个待优化的拉格朗日乘子集

2. 选取拉格朗日乘子集当中的两个变量针对这两个变量构建一个二次规划的子问题，进行求解

针对这个二次规划问题求解出来的数值相对于初始值将会更接近最优解，同时也会使得目标函数的数值变得更小

重要的是，通过SMO算法，我们可以将一个大的优化问题转化成若干个对两个的优化问题，可以极大的提高问题求解的效率。

好，牛吹完了，咱们正式开始

假定我们拥有一个初始化后的拉格朗日乘子集

咱们假定我们优化目标为

注意！！！第一次提醒：

这里的lambda1和2只是拿来举例子的，真实计算当中的lambda1和2可能不是拉格朗日乘子集当中的第一个和第二个乘子

我们设定这两个数为变量，其余为常量

在目标函数当中，我们将这两个变量分离开来，把两个变量从求和符号当中抓出来

在看一眼目标函数

分离成

定义新变量

上式就有

利用约束条件

同样分离两个变量

令

这时候，代入当中有

这样，W函数就能变成只含有lambda2的单值函数了

这时候，对lambda2进行求导并令其为0得（注意对任一yi都有yi^2=1）

把等式右边的y2抽出来得

这时候，咱们就可以将等式左边的那个lambda2看成是更新之后的参数值，即

等号左边的lambda值都是旧的值，咱们可以利用下列条件

同时，咱们还有一个条件，还记得决策函数吗

我们把套在外边的符号函数sign给去掉，重新命名变成

这时候，我们看到

上面的这个的式子等号右边两个又臭又长的求和符号就可用f(xp)去掉

我们就可以一起代入求lambda2新值的公式，完成一个连环爆破之后整理得

定义两个新变量

代入参数更新式得

整理得

这个时候，得到的新的lambda2参数是未剪辑过的参数，有可能违反KKT条件。

由惩罚参数，我们定义lambda2参数的上限值与下限值

这时候，有

好，到了这里，咱们就成功的将lambda1和lambda2的更新值给算出来了

注意！！！第二次提醒！：

咱们这里举例子用到的lambda1和2并非拉格朗日乘子集当中的第一个和第二个乘子，但是推导出来的公式具有一般性

在实际使用当中，我们需要选择满足一定条件的lambda值作为拿来计算的lambda12，至于两个变量如何选择呢？咱们使用两层循环嵌套的方法进行寻找

1. 第一个变量选择

   第一个变量选择为外层循环，在外层循环当中找到违反KKT条件最严重的样本点，取其作为lambda1

   
   

   KKT条件：

   
   

   

   
   

   在变量选取过程中，优先寻找0<labmdai<C的所对应的样本点（xi,yi），若多个不符合，找到最不符合KKT条件的那一个，反之则转向遍历所有训练集，找到最不满足KKT条件的那个点。

   
   

2. 第二个变量选择

   由推导可以知道，lambda2的产生依赖于E1-E2,因为在第一个变量选择当中lambda1确定了，E1也随之确定，

   1.若E1为正，E2取所有Ei当中最小的那个

   2.若E1为负，E2区所有Ei当中最大的那个

注：

1. 为了节省遍历时间，我们可以事先求出所有Ei存储在表当中
   

2. 若内层循环通过以上方法找到的lambda2不能使目标函数产生足够的下降，则

1. 遍历间隔点边界上的支持向量点，依次将其对应的lambdai作为lambda2尝试，直至产生足够的下降

2. 若上一条不满足，可尝试遍历所有的样本点

3. 若两条仍然不满足，抛弃lambda1，重新选择

在完成了lambda1与lambda2的优化之后，我们还需要重新计算b与新的差值Ei

好，在完成了拉格朗日乘子的最优解计算之后，咱们就可以得到完整的拉格朗日乘子集

6.线性支持向量机学习算法

有了上面的公式推导之后，最终咱们可以得到线性支持向量机的学习算法

李航老师的书里讲的更好，我就搬上来了

图中的alpha即为上面的lambda

首先通过求解拉格朗日乘子的最优解，在通过计算获得超平面的w和b即可获得决策函数

7.结束语

相对于决策树算法，支持向量机算法所涉及到的数学推导和数学算法要更加的复杂，推导过程中所使用的数学符号和数学技巧也要更加的复杂。但是通过支持向量机的推导，你可以感觉到数学的美妙所在。

通过拉格朗日乘子法和拉格朗日对偶性质，还有kkt条件，最后在加上smo算法，完全可以看到，咱们大学高数当中学到的所有技巧在这里全都用上了。

哈哈哈，机器学习当中推导比较复杂的算法还有许多，以后有机会我再一一道来哈。

看完了嘛？还不够？

即可获得

周志华老师的《机器学习》与李航老师的《统计学习方法第二版》电子书

愿你的头发永葆生机

你这么可爱为啥不点个关注呢？