支持向量机(SVM)学习小记

标签：SVM 函数 KKT 间隔问题超平面小记向量变量

支持向量机(SVM)

简介

是一种二分类模型，基本模型的定义是在特征空间上的间隔最大的线性分类器
间隔最大有利于感知
学习策略：间隔最大化，可以形式化为一个求解凸二次规划问题，也等价于正则化的合页损失函数的最小化问题

线性可分支持向量机

通过间隔最大化或等价地求解相应的凸二次规划问题得到的分离超平面为
$支持向量机(SVM)学习小记_最小化$
以及相应的分离决策函数
$支持向量机(SVM)学习小记_二次规划_02$

支持向量机(SVM)学习小记_支持向量机_03

硬间隔

在超平面 $支持向量机(SVM)学习小记_二次规划_04$ 确定的情况下， $支持向量机(SVM)学习小记_机器学习_05$ 能够表示点 $支持向量机(SVM)学习小记_最小化_06$ 与超平面的距离， $支持向量机(SVM)学习小记_二次规划_04$ 的符号表示为预测为哪一类

函数间隔

定义函数间隔为
$支持向量机(SVM)学习小记_最小化_08$
定义最小值
$支持向量机(SVM)学习小记_二次规划_09$

规范化

只有函数间隔还不够，因为只要成比例的改变w和b，例如改成2w和2b。

这样超平面并没有改变，但是函数间隔却变成了原来的两倍，如果这样额话，那么只要改的很小，那么也会达到最小化的目的

所以我们要加上一点约束

对向量w规范化， $支持向量机(SVM)学习小记_二次规划_10$
这样使得间隔是确定的，此时的函数间隔变成了几何间隔

几何间隔

支持向量机(SVM)学习小记_最小化_11

点A与超平面(w,b)的距离由线段AB给出
总所周知，ax+by+c=0中(a,b)为直线的发现，所以w也为超平面的发现-
所以点到超平面的距离为
$支持向量机(SVM)学习小记_二次规划_12$
因此导出几何间隔

$支持向量机(SVM)学习小记_机器学习_13$
$支持向量机(SVM)学习小记_最小化_14$

所以，容易知道函数间隔和几何间隔之间额关系

$支持向量机(SVM)学习小记_二次规划_15$
而因为||w||=1所以两者相等，但是当w和b成比例变化的时候，函数间隔会变，但是几何间隔不会变(因为超平面并没有变化)

最大间隔分离超平面

几何间隔的问题

$支持向量机(SVM)学习小记_二次规划_16$

用函数间隔和几何间隔的关系
$支持向量机(SVM)学习小记_最小化_17$

此时将w和b成比例改变，可以也把 $支持向量机(SVM)学习小记_机器学习_18$ 也成比例改变，例如同时乘2。所以 $支持向量机(SVM)学习小记_机器学习_18$ 的值并不影响优化问题，所以固定其为1

再把最小化和最大化的问题转化，所以有
$支持向量机(SVM)学习小记_机器学习_20$
\ \最小化后变成这种形式可能只是习惯均方误差而已，不过也有是其他形式的变形

到此直接用SGD能简单的解决问题

对偶问题

拉格朗日乘子法

拉格朗日乘子法是一种寻找多元函数在其变量收到一个或多个条件的约束时的极值的方法。

这种方法可以把n个变量与k个约束条件的问题转化成n+k个变量的方程组问题
这个方法中引入了一个或一组新的未知数，即拉格朗日乘数，它们是约束方程作为梯度的线性组合中各向量的系数
这种方法所得到的极点会包含原问题中所有的极值点，但并不保证每个极值点都是原问题的极值点

形式

$支持向量机(SVM)学习小记_二次规划_21$

更一般的

$支持向量机(SVM)学习小记_支持向量机_22$

驻点一定在切点处

支持向量机(SVM)学习小记_机器学习_23

f(x,y)有n个变量，g(x,y)=c是限制条件画出来的曲线，图上越小的圈的值越小
$支持向量机(SVM)学习小记_最小化_24$ 是n个变量的所有集合组成使得f的值为d画出的曲线
易证在切线处有驻点
切线处，梯度方向相同，用向量的形式就是在且向上平行

拉格朗日乘子法的必要条件是 $支持向量机(SVM)学习小记_支持向量机_25$ ，就是两个梯度平行

引入变量表示梯度向量

引入变量 $支持向量机(SVM)学习小记_二次规划_26$

$支持向量机(SVM)学习小记_最小化_27$
所以，一旦求出 $支持向量机(SVM)学习小记_二次规划_28$ 的值，将其套入下列公式，容易求出在无约束条件下的极值和对应的极值点
$支持向量机(SVM)学习小记_支持向量机_29$
$支持向量机(SVM)学习小记_机器学习_30$

证明

$支持向量机(SVM)学习小记_机器学习_31$

对于不等式约束时

支持向量机(SVM)学习小记_二次规划_32

暂时把-c和g(x,y)划分到一起
形式为
$支持向量机(SVM)学习小记_支持向量机_33$

KKT条件（专门用于解决拉格朗日乘子法的不等式约束形式）

下面讲述的是KKT条件的感性理解，严格证明涉及拉格朗日对偶，由于是博主以前的文章，这里不做详解
现在g(x,y)有边界解和内部解

如果解本来就在g的内部，那么g的调价就没什么用了，我们的 $支持向量机(SVM)学习小记_机器学习_34$ 即可
如果解不在外部，那么我们就要在边界上找点了，那么就和等式条件一样了有 $支持向量机(SVM)学习小记_机器学习_35$
所以不管是什么上面的点都有 $支持向量机(SVM)学习小记_支持向量机_36$ ，称为互补松弛性

$支持向量机(SVM)学习小记_机器学习_37$

我们知道等式条件是要梯度平行的，但是这里我们不仅需要平行还需要相反，所以有 $支持向量机(SVM)学习小记_最小化_38$ 。就是说梯度f应该指向f最陡峭的地方，即指向g的内部，但是梯度g却是指向g的外部的。因此有 $支持向量机(SVM)学习小记_支持向量机_39$ 。
原因： $支持向量机(SVM)学习小记_二次规划_40$ 始终指向约束控制的可行区域，所以如果解在区域外的话那需要调整梯度的方向才不会造成影响，调整的方法就是 $支持向量机(SVM)学习小记_二次规划_41$
对偶可行性。按照上面的图就是，g(x)标的是≤，所以方向应该向里面指，但是梯度是从小的地方向大的地方指的，所以对于≤来说，切点的梯度方向是相反的。特殊的，如果要求的是max f(x)，g(x)≥0，则λ≤0

所以上面的那个形式要对应的KKT条件为
$支持向量机(SVM)学习小记_机器学习_42$
所对应的广义拉格朗日函数还是
$支持向量机(SVM)学习小记_支持向量机_43$

引入拉格朗日乘子+问题的对偶

$支持向量机(SVM)学习小记_二次规划_44$

问题会变成

$支持向量机(SVM)学习小记_机器学习_45$

为什么会有max(a)呢

max的存在代替了原来的约束条件

假设，各个参数范围是符合要求的话，那么会正常的返回值，但是假如有不符合条件的，那么会通过对a的调整取到+∞
所以这个max的作用就是来判断对错的

因为到了这一步之后还是无法求解，(因为我们对无穷大求最小并没有解决问题)所以我们引入对偶问题
将原始问题极小极大顺序互换后的极大极小问题称为原始问题的对偶问题，原始问题和对偶问题有相同解的条件就是KKT条件
对偶后的问题变成了一个极大极小问题
$支持向量机(SVM)学习小记_支持向量机_46$

先对w,b求导得到极小，再对a得到极大

分别对w，b偏导为0得
$支持向量机(SVM)学习小记_机器学习_47$
带入原问题
$支持向量机(SVM)学习小记_二次规划_48$

求解

得到 $支持向量机(SVM)学习小记_最小化_49$
根据 $支持向量机(SVM)学习小记_最小化_49$ 算 $支持向量机(SVM)学习小记_支持向量机_51$

$支持向量机(SVM)学习小记_二次规划_52$

$支持向量机(SVM)学习小记_支持向量机_51$ 只依赖于数据中对应的 $支持向量机(SVM)学习小记_支持向量机_54$ 的样本点，而其他样本点对这两个值没有影响。我们将数据集中对应的 $支持向量机(SVM)学习小记_支持向量机_54$ 的点称为支持向量

这个用坐标下降算法来优化

搞了半天最后的答案可能只和两个点有关系QAQ，不过毕竟这个还是只能解决线性可分的问题的，解决的都是硬间隔

软间隔

毕竟很多问题还是线性不可分的，所以上述的很多约束并不能成立

所以，我们考虑引入松弛变量 $支持向量机(SVM)学习小记_支持向量机_56$

约束条件变为 $支持向量机(SVM)学习小记_支持向量机_57$

对于每一个松弛变量我们支付一个 $支持向量机(SVM)学习小记_二次规划_58$ 的代价

$支持向量机(SVM)学习小记_机器学习_59$

这个的C是惩罚参数

原问题就变成
$支持向量机(SVM)学习小记_二次规划_60$
然后用类似硬间隔的解决方法就行了

通过拉格朗日乘子法

$支持向量机(SVM)学习小记_机器学习_61$

偏导

$支持向量机(SVM)学习小记_二次规划_62$

问题对偶为

$支持向量机(SVM)学习小记_二次规划_63$

软间隔的另一种解释：合页损失函数(hinge-loss)

另一种解释，最小化下面的函数
$支持向量机(SVM)学习小记_最小化_64$

下标“+”是取正值函数即max(x,0)，前面那一项是经验损失
优化这个问题和优化软间隔问题等价(经验损失那一项就等价于软间隔 $支持向量机(SVM)学习小记_二次规划_65$ )
这个东西直接SGD就行了

上面公式的形式就相当于使得两个类别的距离尽量的大

这种合页损失类的训练模式，在后续很多工作上都有使用，例如TransE

核技巧

非线性的东西往往不好求解，如图上点的范围是一个圆，直接用hinge-loss可能不会得到好的结果，而我们现在的策略就是把把非线性问题转化为线性的问题
设原空间 $支持向量机(SVM)学习小记_最小化_66$ ,新空间 $支持向量机(SVM)学习小记_二次规划_67$

从原空间到新空间的仿射变换为 $支持向量机(SVM)学习小记_二次规划_68$
然后就能把左边的图变成右边的图

这种方法被称为核化，用这种方法把非线性分类转化为线性的分类

核函数

设 $支持向量机(SVM)学习小记_最小化_69$ 是输入空间，又设 $支持向量机(SVM)学习小记_机器学习_70$ 为特征空间(希尔伯特空间)

如存在 $支持向量机(SVM)学习小记_支持向量机_71$ 为输入空间到特征空间的映射使得 $支持向量机(SVM)学习小记_最小化_72$ （这个是两个向量的内积）
经常把输入空间映射到高维空间，这样可能能更高的划分

核技巧在SVM中的应用

我们在对偶问题中涉及输入实例之间的内积，我们可以把内积用核函数代替

$支持向量机(SVM)学习小记_机器学习_73$

同样其他的有内积的地方也能用核函数来替换

$支持向量机(SVM)学习小记_二次规划_74$

正定核

已知映射函数 $支持向量机(SVM)学习小记_最小化_75$ ，可以通过内积来求核函数，但是我们能不构造 $支持向量机(SVM)学习小记_最小化_75$ 而直接判断一个给定的函数是不是核函数吗？
此地涉及大量的数学证明，不做讲述

常用的核函数

多项式核函数

$支持向量机(SVM)学习小记_二次规划_77$

对应的SVM是一个p次多项式分类器

高斯核函数

$支持向量机(SVM)学习小记_机器学习_78$

对应的SVM是高斯径向基函数分类器

字符串核函数

这个是基于离散集合的核函数
自行了解

SMO(序列最小优化方法)

SMO算法要解决如下的凸二次规划的对偶问题
$支持向量机(SVM)学习小记_支持向量机_79$
SMO算法是一个启发式算法

思路：

如果所有变量都满足此优化问题的KKT条件，那么答案就找到了
否则，选择两个变量，固定其他变量，针对两个变量构建一个二次规划问题，这二次规划关于这两个变量的解应该更接近与原始问题的解，因而会使原始二次规划问题的函数目标值更小

重要的是，子问题可以通过解析方法求解
子问题有两个变量，一个是违反KKT条件最严重的那个，另一个由约束条件自动确定
如此，SMO算法不断分解为子问题并对子问题求解，进而达到求解原问题的目的

注意子问题的两个变量只有一个是自由变量，如果a1,a2为两个变量，其他的固定，由约束条件可知，假如a2为自由变量，那么a1可以有其他变量求出来
SMO算法包括两个部分：求解两个变量二次规划的解析方法，选择变量的启发式方法

两个变量的二次规划的求解方法

我们选择变量a1,a2，其他变量固定
$支持向量机(SVM)学习小记_二次规划_80$

$支持向量机(SVM)学习小记_二次规划_81$ 是常数，显然上面列举的是不含a1,a2的常数项

然后，只是两个变量的优化问题我们就可以在二维的平面上来操作了

因为y是1或-1，所以，两个a在平行于对角线的斜线上
根据上面的条件有

L,H为a范围的上下边界
$支持向量机(SVM)学习小记_机器学习_82$

我们首先求沿着约束方向未经剪辑即未经过不等式约束时 $支持向量机(SVM)学习小记_二次规划_83$ 的最优解 $支持向量机(SVM)学习小记_最小化_84$ ，然后再求出 $支持向量机(SVM)学习小记_二次规划_85$

设
$支持向量机(SVM)学习小记_机器学习_86$

g(x)就是当前学习出的值，Ei就是误差值

然后有
$支持向量机(SVM)学习小记_支持向量机_87$

证明

$支持向量机(SVM)学习小记_机器学习_88$

由于 $支持向量机(SVM)学习小记_二次规划_89$
$支持向量机(SVM)学习小记_二次规划_90$
代入
$支持向量机(SVM)学习小记_支持向量机_91$
求导
$支持向量机(SVM)学习小记_最小化_92$
令其为零
$支持向量机(SVM)学习小记_机器学习_93$
因为 $支持向量机(SVM)学习小记_二次规划_94$
$支持向量机(SVM)学习小记_机器学习_95$
将 $支持向量机(SVM)学习小记_支持向量机_96$
$支持向量机(SVM)学习小记_二次规划_97$

再由约束得到 $支持向量机(SVM)学习小记_二次规划_85$ ，在得到 $支持向量机(SVM)学习小记_支持向量机_99$

变量的选择方法

如果只按照上面的方法的话，在寻找变量a会用掉很多的时间，所以我们考虑选择的优化

第一个变量的选择

SMO称选择第一个变量的过程为外层循环

外层循环在训练中选取违反KKT条件最严重的样本点，并将其作为第一个变量
$支持向量机(SVM)学习小记_二次规划_100$
该校验是在误差 $支持向量机(SVM)学习小记_二次规划_101$ 范围中进行的

在校验的过程中，外层循环首先遍历所有满足条件 $支持向量机(SVM)学习小记_支持向量机_102$ 的样本点，即在间隔边界的支持向量点，校验他们是否满足KKT条件，如果这些样本点都满足KKT条件，那么遍历整个训练集，校验他们是否满足KKT条件

第二个变量

SMO称选择第二个变量的过程为内层循环

假设已经找到了变量 $支持向量机(SVM)学习小记_最小化_103$ ，我们希望 $支持向量机(SVM)学习小记_机器学习_104$ 选择的是能是 $支持向量机(SVM)学习小记_机器学习_104$ 变化足够大的
所以 $支持向量机(SVM)学习小记_最小化_106$ 是依赖于 $支持向量机(SVM)学习小记_支持向量机_107$

为了加快计算，我们最简单的选择方法是使得 $支持向量机(SVM)学习小记_机器学习_108$ 最大
因为 $支持向量机(SVM)学习小记_支持向量机_109$ 确定， $支持向量机(SVM)学习小记_最小化_110$ 也确定，那么直接把所有的 $支持向量机(SVM)学习小记_支持向量机_111$ 存在一个列表(有序列表)中节省时间