SVM支持向量机
本片文章主要记录在学习《统计学习方法》中 SVM 章节的难点，不对详细内容进行讲解。主要是分析笔者在学习的过程中遇到的难点
支持向量机分为：
- 线性可分支持向量机
- 线性支持向量机
- 非线性支持向量机：通过核函数转换为
线性支持向量机而求得解
线性可分支持向量机
这是一种最简单的支持向量机了，我们只要能够找到一个超平面将数据集分为 2 个部分，一个部分是全部为正例，一个部分为全部是反例，这一点与下面的 线性支持向量机 有所不同
超平面.jpg
那么我们分类的决策函数就是
决策函数.jpg
sign函数 不懂的读者请自行查阅相关资料了解，十分简单。
函数间隔与几何间隔
函数间隔
按照机器学习的方法，我们需要找出一个损失函数或者叫风险函数，然后最小化该函数来找到我们的超平面。
在 SVM 中将数据集中的样本点到超平面的距离远近作为分类预测的确信程度，也就是样本点距离超平面越远，其可信的程度就越高。如果样本点越近，那么样本的预测准确度就越低。
最直接的，直接计算几何上的距离来表示远近，点到面的距离推导如下：
假设有超平面
在超平面上有 xi 和 xj 这 2 个点，那么就有以下式子
很明显的，将 2 个式子相减得到下面的式子
法向量.jpg
很明显，由向量的知识可以知道，wT 是超平面的法向量了
假设在超平面外有 1 个点 x1 ，那么假设有向量 (x1-xi)，通过向量的基本知识我们知道，向量乘以某个方向的单位向量，那么就能得到向量在该方向的长度。结合上面的超平面法向量，那么我们直接将 (x1-xi) 乘以 w 的单位向量就得到点 x1 到超平面的距离，其中||w||是 w 的L2范式，也就是平方和再开根
距离.jpg
结合(2)式，可以得到
因为 (6)式 是带有方向性的，我们再将 y1 乘上去后，那么这个距离就是非负的，无论 x1 在超平面的哪一边，所以最终我们得到的距离式子如下
将 x1 和 y1 用一般性的 x 和 y代替，这样就能得到最终的 几何间隔距离
一般距离.jpg
那么按照一开始说的，我们只要让数据集的每一个样本点的距离最大化，就能保证我们有充分大的确信度来让我们正确地分类，那么我们就需要优化 w 和 b 来得到这样的超平面，所以我们就要求解w 和 b
用符号来表示 几何间隔
几何间隔.jpg
并有
距离公式.jpg
（笔者开始时连基本的数学都给忘了，所以记下来好好给自己提个醒）
函数间隔
函数间隔 是为了让计算更加简单而使用的，参考附录的《函数间隔为什么可以为1》
函数间隔为：
函数间隔.jpg
在 SVM 的约束问题中，我们让函数间隔为 1 而便于计算，参考附录的《函数间隔为什么可以为1》
其本质的理解就是：让距离的变化全部都体现在 w 和 b 上，从而来求得解
支持向量
支持向量是什么呢？因为是超平面，那么就存在距离超平面最近的点，而我们要做的就是不断的调整超平面，让超平面离这些最近的点的距离最远，这里有点绕口，读者们可以好好理解一下。因为距离超平面最近的点的距离是未知的，所以我们可以不断的调整这个距离，让这个距离达到最大。
而这些距离超平面最近的点就是支持向量，其实可以这么理解，这些点对超平面的影响是最大的
而从约束条件来看，其实就是 y(w·x+b)=0 的那些点(这里比较抽象，需要结合书籍来看，笔者不多赘述，有需要可以留言交流)
可分线性约束条件.jpg
对偶解法
SVM 使用了对偶解法，但要注意的是，这里是使用 2 次对偶，也就是对对偶问题的极小化问题再使用一次对偶
线性对偶.jpg
我们先求最小化问题，也就是分别对 w 和 b 求导后另其为 0 。这样就求得到了最小化了
那么我们剩下最大化问题，最大化问题我们依旧可以转换为最小化问题，最简单就的取反值嘛，事实上也确实是这么做的，那么我们又得到了一个最小化问题，既然是最小化问题，那么我们再次使用对偶来求解，而这次的约束条件则是使用第一次最小化问题得来的解，也就是拿第一次最小化后的解来作为这次最小化的约束条件
最终的优化问题是，也就是对求解下面的约束问题，我们就求得了解
最终约束问题.jpg
我们可以从上面的式子中看出，式子是跟数据集的数量 N 存在关系的，也就是 N 影响了训练的轮数，N 越多，我们需要处理越多次。因为有这一层的关系，所以支持向量机在数据量少的时候也能得到很好的分类性能，前提是数据集是优质的
那么这样，第二次的对偶问题的最优解就是原始问题的最优解
书中给出了最优化之后 w 和 b 的表达式，那么我们在求出 a 之后，求出w 和 b 从而得到超平面
SVM与数据集
书里面有一句话需要注意！！！在P107
w 和 b只依赖于训练数据中对应的 ai > 0的样本点，而其他样本点对 w 和 b 没有影响，我们将训练数据中对应于 ai > 0的实例点称之为支持向量
这句话解释了为什么支持向量机只需要少量的数据样本就能得到了很好的效果。
书中 105 页有以下式子：
（笔者对 对偶的kkt条件不熟悉，是当成结论来用，有需要的读者自行查阅资料，）
由KKT条件推导得（可以手动推导得到）
线性可分kkt条件.jpg
因为几何距离最近的点就是函数间隔最小的点(如果这一点没理解的话参考附录链接)，根据上面的式子，我们知道：
数量.png
由上面可知，我们只需要那些距离超平面最近的点就可以了，其余的点是没有效果的，如果我们有这样的数据集(距离超平面距离最小)就可以训练出很好的SVM
总结
- 写出表达式
- 使用距离(间隔)来表示确信度
- 最大化距离超平面最近的点的函数间隔
- 使用两次对偶问题来求解函数间隔的约束问题
线性支持向量机
有些数据集具有一些特点点，这些特异点不满足线性可分
可理解为：
- 明明是正例，但它却在超平面的反例区域内
- 明明是反例，但它却在超平面的正例区域内
- 特异点在函数间隔小于1的范围内
以上的点都是特异点，而我们需要加入松弛变量来让他们变得线性可分，为什么加入松弛变量之后就线性可分呢？笔者有一种简单粗暴的理解：就是加入松弛变量后相当于让他们的函数间隔变得更小，小于1的点我也当你是支持向量。
因为这种数据集不能用一个简单的超平面就把它们分开，所以没有可分俩字了，是线性支持向量机
约束条件
通过一系列推导，书中P110-P111给出了我们最终需要优化的对偶问题
线性约束条件.jpg
同理，结合线性可分支持向量机章节 的 SVM与数据集小节，按照书中P111的式子7.52我们可以推导出以下关系，这个关系很重要，下一节的难点会用到，满足下面关系的点都是满足KKT条件的点。
线性KKT条件.png
这里需要注意，每一个点(xi,yi)都会有一个ai与之对应，如果这些点的ai不满足下面的条件，那么说明这个点的ai还不是最优化的，需要通过某种办法进行优化
注意！！！在解线性支持向量机 时，我们需要选定一个惩罚参数 C，这个是我们需要手动选择的
最后 w 和 b 的表达式请查看书中的P110-P111，这里不多做赘述，书上已经讲得非常好了
其实P112给了我们一个更加简洁的公式来表示超平面，如下：
可见这个公式直接去掉了 w，使用了 ai 来直接表示公式中w
合页函数
线性支持向量机 优化的另外一种方法就是最小化下面的式子
线性目标函数.jpg
书中P114给出了，最小化该式子就是最小化对偶问题
第 1 项被称为合页损失函数
合页函数.jpg
第 2 项是正则化项，也就是惩罚项
惩罚项.jpg
非线性支持向量机
有些数据集是无法通过简单的线性超平面来分类，所以我们需要将这些数据集映射到线性空间，意思就是让这些非线性分布的数据集映射到一个线性分布的空间
核函数
映射数据集的手段是找到一个映射函数来映射数据集。但在书中P116中讲到，使用核函数我们可以不用求得映射函数就能映射数据集
附录中的《关于核函数的一些思考》写得非常好，有需要的读者可以参考一下
这里简要说一下笔者的理解：核函数的作用就是将数据在低纬度的空间映射到高纬度的空间，从而将数据集线性分开，然后我们求得高纬度空间的超平面来分开高纬度空间中的数据集，从而实现了使用线性超平面求解非线性数据集
那怎么判定一个给定的函数 K(x,z) 是核函数的？其实就是证明这个函数是正定核函数，证明过程复杂，请阅读书中P118
当然啦，类似笔者这种水平是无法求解到核函数的，但是好在有一些先贤帮我们找出了一些常用核函数，比如高斯核函数，多项式核函数等等。
约束条件
根据书中推导，我们能够得到最后的最优化问题，如下：
非线性约束条件.jpg
其实就是将 x 的部分换成了核函数，按照这样的道理，最后 w 和 b 的解也是将 X 换位核函数
SMO算法
上面我已经得出了w 和 b 的表达式，但是它们两者都和 ai 挂钩，我们需要求出 ai 才能求出它们，而 SMO算法 就是求出 ai 的方法
附录《SMO算法剖析》讲得非常不错，读者们可以阅读一下。
下面笔者将一下这里面需要注意的细节
SMO 算法的过程大致是：
- 找出 2 个
ai，而其他的参数则固定为常量（这种方法类似坐标上升法） - 不断的优化这 2 个
ai，直到这 2 个ai满足 KKT条件 - 再找出其他的 2 个
ai，进行同样的处理。
假设我们找到了 2 个ai，分别是a1 和 a2，然后将最优化问题转换为转换为关于这 2 个参数的函数，也就是最优化函数转换为W(a1,a2)，我们最小化这个函数就行，而这个函数通过关系式可以转换为 a2 的一元函数 W(a2)，所以我们能够求解得到 a2，如下：
a2unc.jpg
其中的 new unc 表示的是说 a2 还没确定其值（官方的说法叫做裁剪）。
为什么叫没确定其值？
因为 a2 不是什么数都能取的，因为 ai 本身就有限制，求出的a2可能会超出取值范围，所以我们要将a2变成取值范围内的数。
如何找到 a2 的取值范围？附录链接已经解答了这个问题，笔者不多做赘述，给大家公式看看
a2求法.jpg
上面有带 old 的a1 和 a2 ，是什么意思呢，old 从哪里来呢？其实我们需要实现对所有的 ai 都初始化为 0，再进行计算，所以old 就好理解啦，当然是前面一次的值了
那么我们还剩下一个问题，如何寻找这 2 个参数呢？
书中讲得比较晦涩，笔者自己的理解如下：
找出 2 个参数需要进行 2 层循环
一、内层循环
内层循环的为了找到 1 个违反 KKT条件的样本点a1，注意了，是违反KKT条件
- 初始化所有
ai为0 -
遍历整个样本集计算符合KKT条件的点，也就是如下图所示的条件
非线性KKT..png
但是有 3 个条件，哪一个条件优先判断呢？
1、优先找出yg(x)=1 的样本点，也就是支持向量点，并查看这些点的ai是否满足0<ai<C
2、如果没找到，那么在判断其余的两个条件，笔者的理解是随便选择 1 项优先判断，或者 2 项一起判断
二、内层循环
经过内层循环后我们能找到一个样本点是严重违反KKT条件的，在此基础上我们再进行 1 次内层循环，内存循环是为了找到一个样本点a2，这个样本点它有足够大的变化
- 因为确定了
a1，所以可以计算出E1 - 遍历整个样本集找出
|E1-Ei|最大的ai作为a2
这里需要注意一下如果 E1 是负的，那么选择最大的 Ei 作为 E2，如果 E1 是正的，则选择最小的 Ei 作为 E2
通过上面的查找，我们能够确定出一组a1、a2，然后我们对这组 a1、a2 用我们上面的公式进行优化，直到都满足 KKT条件。根据书中P129-P130所讲，优化迭代 1 次a1、a2后我们都需要重新计算 b 跟 E1、E2 的值，用于下一次迭代。
当我们优化完一组 a1、a2 之后再对下一组进行优化，当优化完所有的ai后，我们的b也就随之确定了，最终完成我们的算法
后语
总算说完了，但笔者也只是讲了SVM的冰山一角，尽量将笔者在阅读《统计学习方法》中的SVM章节时遇到的重难点给记录下来，希望能够帮助到跟我一样遇到困难的。当然了，有些东西使用文字描述实在不易，还是需要各位读者去推导，去计算，这样才能有心领神会。因为本文重点在于疏导思路，所以有些地方并不会讲得非常清楚，甚至有些地方还需要读者自行推导公式，但笔者也是自己推导过来的。相信各位读者结合《统计学习方法》的内容自己去推导很快能够得到答案的。当然，《统计学习方法》中的SVM笔者感觉也比较初级，许多地方只给结论不给过程，但是我相信，能够理解到里面的内容，应该是SVM入门了吧，但也仅仅是入门，毕竟光是SVM就有一本导论可以阅读了。
以上就是SVM的简单的理论记录，毕竟SVM博大精深，关于动手部分就需要各位读者自行找代码去阅读运行了
附录
SVM几何间隔计算：https://www.zhihu.com/question/20466147/answer/197520556
函数间隔为什么可以为1：https://www.zhihu.com/question/64568136/answer/257874428
关于核函数的一些思考：https://www.jianshu.com/p/70426f1a468e
SMO算法剖析：https://blog.csdn.net/luoshixian099/article/details/51227754
关于SVM数学细节逻辑的个人理解三部曲：https://www.cnblogs.com/xxrxxr/p/7538430.html
网友评论