3. 支持向量机(SVM)
https://gitee.com/fakerlove/machine-learning视屏链接
https://www.bilibili.com/video/BV1Hs411w7ci
3.0 基本概念
支持向量机（support vector machines, SVM）是一种二分类模型，它的基本模型是定义在特征空间上的间隔最大的线性分类器，间隔最大使它有别于感知机；SVM还包括核技巧，这使它成为实质上的非线性分类器。
SVM的的学习策略就是间隔最大化，可形式化为一个求解凸二次规划的问题，也等价于正则化的合页损失函数的最小化问题。
SVM的的学习算法就是求解凸二次规划的最优化算法。
support vector machine，一般用在小样本的，效果会非常好
SVM有三宝，间隔,对偶，核技巧
- hard-margin svm
- soft margin svm
- kenel svm
中文的话
- 硬间隔支持向量机（线性可分支持向量机）：当训练数据线性可分时，可通过硬间隔最大化学得一个线性可分支持向量机。
- 软间隔支持向量机：当训练数据近似线性可分时，可通过软间隔最大化学得一个线性支持向量机。
- 非线性支持向量机：当训练数据线性不可分时，可通过核方法以及软间隔最大化学得一个非线性支持向量机
下面我们学习都是硬间隔支持向量机
3.1 硬间隔支持向量机
数据是线性可分的，采用hard margin 就是说数据可以用一条直线将以区分，如下图所以，中间的线就是我们要距离间隔最大的线，就是我们要找到的超平面
3.1.1 概念介绍
1) 线性可分的定义
等于0的时候，虽然能分开，但是只有一条直线分开来。但是对于此题svm呢？中间有一段很大的距离，所以假设规定
2) 训练数据及标签
假设给定一个特征空间上的训练数据集
设空间有个向量，$x_1,x_2,x_3,... C_1C_2y_i=\begin{cases}1 ,如果x_i \in C_1 \ -1 ,如果x_i\in C_2\end{cases}$
3) 线性方程
描述超平面的线性方程,
定义线性方程，其中为法向量的方向，为距离原点的距离.
定义决策分类函数
3.1.2 问题描述
在这些样本中，有很多的和选取最合适的一条线，把和分来
请问如何选取最合适的一条线？？？
3.1.3 算法流程
怎么定义性能指标呢？？？？
找一个平面，向上与向下平行移动该平面，使之擦过一些向量，将距离d定义为此平面的优化向量，使d尽可能大，d叫做间距。擦过的向量叫做支持向量。
1) 支持向量
擦过的向量叫做支持向量。图中红色的圈，不管正的还是负的，都叫做支持向量
2) 几何间隔
对于给定的数据集T和超平面,定义超平面关于样本点的几何间隔为
超平面关于所有样本点的几何间隔的最小值为
实际上这个距离就是我们所谓的支持向量到超平面的距离。
其中
假设距离最佳超平面最近的几个训练样本点使上式中的等号成立，它们被称为“支持向量”（support vector）
3) 最优化问题-间隔最大化
根据以上定义，SVM模型的求解最大分割超平面问题可以表示为以下约束最优化问题
将约束条件两边同时除以,得到
因为都是标量，所以为了表达式简洁起见，令
得到
又因为最大化,等价于最大化,也就等价于最小化(是为了后面求导以后形式简洁，不影响结果），
因此SVM模型的求解最大分割超平面问题又可以表示为以下约束最优化问题
结论就是为了找到最大的d,
只需要最小化
4) 问题解惑
解释如下
首先看两个事实
事实1
与 是同一个平面，
事实2
点到平面的距离公式则到直线的距离为 同理
向量x到超平面的距离为样本中任一点到线的距离为
基于这两个事实
我们可以用a去缩放,最终使得支持向量上有,此时支持向量与平面的距离为
,等价于最大化,也就等价于最小化
3.2 原问题和对偶问题
参考链接
https://zhuanlan.zhihu.com/p/31886934对偶理论是研究线性规划中原始问题与对偶问题之间关系的理论。
对偶问题是利用拉格朗日对偶性将原始问题转换为对偶问题，通过解对偶问题得到原始问题的解。优点是：
- 对偶问题往往更易于求解
- 自然引入核函数，推广到非线性分类问题的求解
为什么求对偶问题
对于对偶问题来说，我们求解最小化部分时没有任何限制条件，而没有限制条件的最小化问题的解一定是在求得x的偏导数=0这处，那我们就能得到一些等式，将这些等式代入拉格朗日函数中就可以简化计算（svm中可以最终把min消去，且得到一个只与 有关的最大化问题）
3.2.0 前提准备
1) 强对偶定理
2) KKT 条件
推论1：
设和,分别是原始问题和对偶问题的可行解，并且，则和,分别是原始问题和对偶问题的最优解。
【即：如果某个解使得最优值相等，则这个解同时是原始和对偶问题的最优解】
定理2：
考虑原始问题和对偶问题，假设函数和是凸函数，是仿射函数；并且假设不等式约束是严格可行的，即存在x，对所有i有，则存在x∗和，使x∗是原始问题的解，是对偶问题的解，并且有
定理3：
分别是原问题和对偶问题的充分必要的条件是$x^,\alpha^,\beta^* $满足下面的KKT条件
3.2.1 原问题
求解一个约束最优化问题：
（注：这个问题用二次规划求解时复杂度与x的维度有关）
将问题一般化就变成
3.2.2 对偶问题
引入拉格朗日函数，由于约束条件有个，所以我们有：
其中是拉格朗日乘子
(求对有限制条件的的最优化问题转为对 没有限制条件的极值问题)
最大化:
限制条件:
实际上就是研究
若原始问题和对偶问题都有最优值，则对偶问题最优值d∗ 原始问题最优值p∗：
（通俗点就是宁做凤尾不做鸡头，凤尾（右）是原始问题，鸡头（左）是对偶问题）
换种说法
3.2.3 使用拉格朗日乘子法得到SVM对偶问题
这是一个含有不等式约束的凸二次规划问题，可以对其使用拉格朗日乘子法得到其对偶问题（dual problem）。
首先，我们将有约束的原始目标函数转换为无约束的新构造的拉格朗日目标函数
其中为拉格朗日乘子，且,现在我们令
当样本点不满足约束条件时，即在可行解区域外：
此时将设置成无穷大，则也为无穷大。
当满本点满足约束条件时，即在可行解区域内：
为原函数本身。于是，将两种情况合并起来就可以得到我们新的目标函数
此时，为原函数本身。于是，将两种情况合并起来就可以得到我们新的目标函数
于是原约束问题就等价于
看一下我们的新目标函数，先求最大值，再求最小值。这样的话，我们首先就要面对带有需要求解的参数w和b的方程，而又是不等式约束，这个求解过程不好做。所以，我们需要使用拉格朗日函数对偶性，将最小和最大的位置交换一下，这样就变成了：
要有,需要满足两个条件：
① 优化问题是凸优化问题
② 满足KKT条件
首先，本优化问题显然是一个凸优化问题，所以条件一满足，而要满足条件二，即要求
为了得到求解对偶问题的具体形式，令对和的偏导0，可得
将以上两个等式带入拉格朗日目标函数，消去和得
即
求对的极大，即是对偶问题
把目标式子加一个负号，将求解极大转换为求解极小
现在我们的优化问题变成了如上的形式。对于这个问题，我们有更高效的优化算法，即序列最小优化（SMO）算法。这里暂时不展开关于使用SMO算法求解以上优化问题的细节，下一篇文章再加以详细推导。
我们通过这个优化算法能得到 ，再根据 ，我们就可以求解出和，进而求得我们最初的目的：找到超平面，即”决策平面”。
前面的推导都是假设满足KKT条件下成立的，KKT条件如下
另外，根据前面的推导，还有下面两个式子成立
由此可知在中，至少存在一个（反证法可以证明，若全为0，则 ,矛盾），对此有
因此可以得到
3.2.4 总结
原问题
拉格朗日函数
原函数有
原问题
综合以上讨论，我们可以得到线性支持向量机学习算法如下：
输入:训练数据集,其中
输出:分离超平面和分类决策函数
选择惩罚参数，构造并求解凸二次规划问题
构件模型
得到最优解
计算
选择的一个分量，满足条件，计算
求分离超平面
3.2.5 SMO
(Sequential Minimal Optimazation)方法
上节最后得到的关于的式子是一个二次规划问题，使用通用算法开销比较大。
SMO方法是1998年提出的，用于求取SVM中的拉格朗日乘子，比通用算法更加高效。
其主要思想为，选取两个变量，固定其他参数，对这两个参数进行优化，然后重复这个过程。
注意到只需选取的中有一个不满足KKT条件(6.13),目标函数就会在迭代后减小[Osuna et al., 1997].
直观来看, KKT条件违背的程度越大，则变量更新后可能导致的目标函数值减幅越大.
于是,SMO先选取违背KKT条.件程度最大的变量.第二个变量应选择-一个使目标函数值减小最快的变量,但由于比较各变量所对应的目标函数值减幅的复杂度过高,
因此SMO采用了一个启发式:使选取的两变量所对应样本之间的间隔最大.一种直观的解释是,这样的两个变量有很大的差别，与对两个相似的变量进行更新相比,对它们进行更新会带给目标函数值更大的变化.
3.3 软间隔支持向量机
参考文章
https://blog.csdn.net/liugan528/article/details/79448379在现实任务中很难找到一个超平面将不同类别的样本完全划分开，即很难找到合适的核函数使得训练样本在特征空间中线性可分。退一步说，即使找到了一个可以使训练集在特征空间中完全分开的核函数，也很难确定这个线性可分的结果是不是由于过拟合导致的。解决该问题的办法是在一定程度上运行SVM在一些样本上出错，为此引入了“软间隔”（soft margin）的概念，如图4所示：
具体来说，硬间隔支持向量机要求所有的样本均被最佳超平面正确划分，而软间隔支持向量机允许某些样本点不满足间隔大于等于1的条件,当然在最大化间隔的时候也要限制不满足间隔大于等于1的样本的个数使之尽可能的少。于是我们引入一个惩罚系数,并对每个样本点引入一个松弛变量（slack variables） 此时可将式(10)改写为
上式中约束条件改为,表示间隔加上松弛变量大于等于1；优化目标改为,表示对每个松弛变量都要有一个代价损失,越大对误分类的惩罚越大、越小对误分类的惩罚越小。
最后得到的对偶问题是
对比软间隔支持向量机的对偶问题和硬间隔支持向量机的对偶问题可发现二者的唯一差别就在于对偶变量的约束不同，软间隔支持向量机对对偶变量的约束是,硬间隔支持向量机对对偶变量的约束是,于是可采用和硬间隔支持向量机相同的解法求解式(23)。同理在引入核方法之后同样能得到与式(23)同样的支持向量展开式。
类似式(16)对于软间隔支持向量机，KKT条件要求：
3.4 低维到高维映射-核函数
3.4.1 线性不可分
非线性SVM算法原理
需要放松限制条件，对每个训练样本及标签加入松弛变量
改造后的支持向量机优化版本如下
最小化
限制条件
其中 叫做正则项，意思为让整个目标函数规范化，是事先设定的参数。支持向量机需要改动的参数只有一个
3.4.2 基本概念
这是支持向量机求出来的解，显然是不符合要求的，问题出现哪里，是因为我们的函数是超平面，是线性的，线性模型的表现力的是不够的
这是线性不可分的例子，我们不能做出线性的东西。
这个时候呢？
对于是无限维，我们可以不知道无限维映射的显示表达，但是我们只要知道一个核函数,则这个优化式仍然可解
使用最多的核函数如下
能够写成的充要条件
,
有
为什么会出现核函数，
因为原始样本空间有可能并不是二维的，有可能是三维或者四维的。这样子呢，就不能够线性可分了，怎么办？，基于上面的解法，就是利用核函数变成高维特征空间使样本可分。
把样本x 映射到高维空间后，维数可能很高，甚至是无穷维的，计算十分的复杂，为了避开这个这个障碍，就会使用核函数让变成核函数的值，大大减小计算量
3.4.3 常见的核函数
这里表示多项式的阶数
| 名称 | 表达式 | 参数 |
|---|---|---|
| 拉普拉斯核 | ||
| 线性核 | ||
| 高斯核 | ||
| 多项式核 | 这里d 表示多项式的阶数 | |
| Tanh（Tanh核) | tanh为双曲正切函数 |
3.4.4 算法流程
3.5 应用问题-兵王问题
黑方只剩一个网，白方剩一个兵一个王
只有两种可能
- 白方将死黑方，获胜
- 和棋
- 这两种可能视三个棋子在棋盘的位置而确定
3.6 小结
3.6.1 优点
- 有严格的数学理论支持，可解释性强，不依靠统计方法，从而简化了通常的分类和回归问题；
- 能找出对任务至关重要的关键样本（即：支持向量）；
- 采用核技巧之后，可以处理非线性分类/回归任务；
- 最终决策函数只由少数的支持向量所确定，计算的复杂性取决于支持向量的数目，而不是样本空间的维数，这在某种意义上避免了“维数灾难”。
3.6.2 缺点
训练时间长。当采用 SMO 算法时，由于每次都需要挑选一对参数，因此时间复杂度为 ，其中 N 为训练样本的数量；
当采用核技巧时，如果需要存储核矩阵，则空间复杂度为
模型预测时，预测时间与支持向量的个数成正比。当支持向量的数量较大时，预测计算复杂度较高。
因此支持向量机目前只适合小批量样本的任务，无法适应百万甚至上亿样本的任务