参考
https://www.cnblogs.com/pinard/p/6097604.html
https://blog.csdn.net/alwaystry/article/details/60957096
https://www.jianshu.com/p/55458caf0814
https://blog.csdn.net/luoshixian099/article/details/51227754
概述
支持向量机是一个二分类算法，主要用于2元分类任务（是或不是的问题）。
我的理解，比如在二维空间上有两种类型的无数个点，我们需要找到一条线将这两类点分离开来，这就是支持向量机的本质。如果再三维空间上，就是找到一个平面来分割两类点。三维以上的空间是超平面。
这个线或者面定义为 wx + b = 0。 我们的任务就是要算出这个w和b。
训练样本一般有三种情况： 线性可分，软线性可分，线性不可分。
下面就来说说这三种情况。
线性可分支持向量机
当我们的训练集中的样本是线性可分的时候，我们可以定义一条线为 y = wx + b；y的取值为+1或者-1，当y= +1时，说明训练样本x为正类，当y = -1时，训练样本为负类。
函数间隔与几何间隔
当超平面 wx + b = 0 确定的情况下，| wx + b | 可以表示点 x 到超平面的距离，而 wx + b 的符号与y值对比可以判断是否分类正确（只有计算值与y值一样时才是分类正确的），所以我们可以用 y(wx + b) 来表示分类的正确性以及点离超平面的距离。
引出函数间隔的概念:
而超平面 (w, b) 关于 T 中所有样本点 (x, y) 的函数间隔的最小值，为超平面 (w, b) 关于 T 的数函间隔。
但是这样的定义还有问题，如果等量的增加 w 和 b 的值，这样超平面不变，函数间隔会无限的增大。我们可以给 w 增加约束条件，这样引出几何间隔：
将函数间隔除上 w的二阶范数，这样 w 和 b 即使增加也不会影响几何间隔的大小。所以我们使用几何间隔来表示点 (x, y) 到超平面的距离。
而我们知道如果点离超平面的距离越大，说明这个点的分类可信度越高 (如果点就在超平面的旁边，是不是会怀疑它是否分类正确)，所以我们要尽可能的让所有的点离超平面远远的，这样分类的确信度就会很高。
在上面的图中，我们找到了一个超平面 wx + b = 0 ，它使得最近的打叉的点与最近的圆圈的点离超平面的距离是一样的，我们需要找的超平面就是这样的超平面。最近的点离超平面的距离我们定义为 1 。
而这些离超平面距离最近的点我们就叫它支持向量。
从上面的图中我们可以看出超平面的确定，其实只与这些支持向量有关系，而与其它点没有关系。如果我们不考虑其它点，只考虑支持向量，而且定义支持向量到超平面的距离为1，也就是函数间隔为1，那么几何间隔就可以化简成为：
这样我们只要使这些支持向量的函数间隔最大，就能确定超平面了。
不过也有约束条件，支持向量的函数间隔我们定义为1了，那么其它点的函数间隔呢？肯定是大于1的吧，所以约束条件是 y(wx + b) 大于等于 1 。
而在数学中，我们求极大值不好求，可以转换为就极小值，就上图中的极大值相当于是就下图中的极小值：
这样我们将问题转换为了求极小值的问题。
拉格朗日乘子法
求极小值的方法有很多，这里说说拉格朗日乘子法。
我们通过求解原始问题的对偶问题，间接来原始问题。(什么是对偶问题呢，我的白话理解就是，两个问题的解是相同的，通过求解其中一个问题的解，另外一个问题的解就相应的得到了，这样的两个问题就是对偶问题，具有对偶性。)
至于拉格朗日乘子法转换后的问题为什么是这个原始问题的对偶问题，这个太深奥了，还需要深入研究学习，这里我只需要知道这样转换后的问题是对偶问题就好了。
那什么是拉格朗日对偶转换呢？简单说，就是通过给每一个约束条件加上一个拉格朗日乘子，然后在全部相加，得到一个拉格朗日函数，拉格朗日乘子大于等于0。
然后令：
(我自己理解一下这个图，有时候像我这种小白经常就是这种基础的地方不明白：意思就是 调整参数 阿尔法 使得拉格朗日函数的值最大化。)
在看上面的拉格朗日函数，函数中右边部分肯定是大于0的，我们要让拉格朗日函数值最大，要么就是 阿尔法 等于0，要么就是点的函数间隔 y(wx + b) 是等于1的。这样右边的式子等于0了，才能让拉格朗日函数最大。而 y(wx + b) 等于 1 的这些点是不是就是我们的支持向量啊。
所以，当所有约束条件都满足的情况下，函数最后也就只剩下
最后目标函数就变成了：
在满足KKT条件的情况下，目标函数等价于下面的函数
这样我们先求最小值，在求最大值。
至于为什么目标函数满足KKT条件，已经满足KKT条件后两个式子是等价的，得在深入研究，现在就知道我们满足KKT条件。
KKT条件
一般，一个最优化模型能够表示成下面的标准形式：
常用的方法是KKT条件，同样地，把所有的不等式约束、等式约束和目标函数全部写为一个式子：
L(a, b, x)= f(x) + ag(x)+bh(x)
而KKT条件就是这个标准形式的最优值要满足：
- L(a, b, x)对x求导为零；
- h(x) = 0；
- a*g(x) = 0；
x是参数。
推导
这样我们分别对 w 和 b 求偏导，由于满足KKT条件，所以求导都等于0；
还有一种说法，由于我们满足KKT条件，目标函数被转换为了下面的式子：
我们先求 L(w, b, a) 关于 w 和 b 的最小值，然后在求关于 a 的最大值。
求 w 和 b 的最小值，在数学中可以分别对 w 和 b 求偏导，使偏导的值等于0，也就得到了最小的极值点，同样是上面的式子。
将得到的结果带入拉格朗日原式中，我们可以得到:
这样得到了 L(w, b, a) 的关于 w 和 b 的最小值，然后就求关于 a 的极大值了，式子转换为
极大值不好求，又要想办法转换为求最小值。求上面式子的极大值，那我们给它加个负号，那是不是就可以转换为就加上负号后式子的极小值的呀。
SMO算法求a
先来一段自己的理解文，假设有n个特征，那么a的个数也有n个，我们取两个 a 变量，分别为 a1 和 a2 ，将其他的 ai 都视为常数，那将所有值带入，目标函数就可以写成：
注意上面图中，约束条件1红框中的内容是不是可以替换掉目标函数中红框中的内容啊！因为他们都是一个表达式，这样替换上去，目标函数就剩下了 a1 和 a2 两个未知变量了。
现在就剩下求极小值问题了，我们分别对 a1 和 a2 求偏导等于 0 ，这是一个二元函数，这样可以直接求出 a1 和 a2 的值。
不过求出的 a 值需要满足约束条件，那就是:
当a 不满足这两个条件时，需要对a值进行截取 ，比如： a1 = -0.5，那么就取 a1 = 0，然后相应的调整 a2 使上面的相加条件成立。这样逐步递归，就能求得所有的 a 的值了。
软线性可分支持向量机
上面的支持向量机算法还不完善，因为我们有个前提条件是样本数据是完全线性可分的，就是可以找到一条直线，将所有的样本分为两类。但是万一有一些干扰点，不按常理出牌，就偏过去了一点点，导致了找不到这样的线了，上面的算法就不可以用了。
对于这种情况我们有软线性可分支持向量机的解决办法。就是对于每个样本，我们允许偏离超平面一定的距离，这个距离我们定义为松弛变量。
原来，我们定义 y (wx + b) 为点到超平面的距离，而约束所有的样本距离，都是大于等于1的。
现在我们加入松弛变量：
如果松弛变量无限大的话，那么所有数据集都能符合条件了，所以，还要在元目标函数后加上一项，使松弛变量的和也要最小。
这样整体达到最小：
C是固定的一个常量，C >= 0，为惩罚参数，可以理解为我们一般回归和分类问题正则化时候的参数。C越大，对误分类的惩罚越大，C越小，对误分类的惩罚越小。
用之前的拉格朗日乘子法，同理推导，得新的函数:
然后分别对 w 和 b 和 松弛变量 求导：
w 带回函数，得到和原来一样的目标函数:
阿尔法 和 r 都是拉格朗日乘子，都是大于0的。而 C - 阿尔法 - r = 0，所以 阿尔法 <= C，整个问题变成了：
最后使用SMO算法求 阿尔法 就可以了。不过再求得 阿尔法 进行截取时，需要使用新的约束条件，0 < 阿尔法 < C。得到 阿尔法的解。
线性不可分支持向量机
而还有一种情况，所有的样本点已经无法用，f(x) = wx + b 这样的函数完全分类的时候，这种情况我们叫线性不可分情况。那这种情况下咋办呢？
我理解，就是将之前计算得到的目标函数中 <x_i, x_j> 的内积，替换成一个函数，原来的 x 通过这个函数转换后得到了新的值，这些值是可以线性可分的，更容易计算：
核函数
核函数有很多种，我们可以选择适合的。
- 多项式核函数
- 高斯核函数
- 线性核函数 就是x1 和 x2的内积，相当于不进行映射转换。
问题
- 怎么选择核函数
可以先用线性核函数得到结果，然后在使用其他核函数，对比结果，选择结果好的。
- 怎么判断是否线性可分
不用判断，一般进行训练时，先选线性核函数，在使用其他核函数计算，选择最优的模型。
