05 SVM - 支持向量机 - 概念、线性可分
一、SVM概念
支持向量机(Support Vector Machine, SVM)本身是一个二元分类算法，是对感知器算法模型的一种扩展，现在的SVM算法支持线性分类和非线性分类的分类应用，并且也能够直接将SVM应用于回归应用中，同时通过OvR或者OvO的方式我们也可以将SVM应用在多元分类领域中。在不考虑集成学习算法，不考虑特定的数据集的时候，在分类算法中SVM可以说是特别优秀的。
SVM概念
在感知器模型中，算法是在数据中找出一个划分超平面，让尽可能多的数据分布在这个平面的两侧，从而达到分类的效果，但是在实际数据中这个符合我们要求的超平面是可能存在多个的。
出一个划分超平面，让尽可能多的数据分布在这个平面的两侧
在感知器模型中，我们可以找到多个可以分类的超平面将数据分开，并且优化时希望所有的点都离超平面尽可能的远，但是实际上离超平面足够远的点基本上都是被正确分类的，所以这个是没有意义的；反而比较关心那些离超平面很近的点，这些点比较容易分错。所以说我们只要让离超平面比较近的点尽可能的远离这个超平面，那么我们的模型分类效果应该就会比较不错。SVM其实就是这个思想。
让离超平面比较近的点尽可能的远离这个超平面
SVM核心思想：找到离分割超平面较近的点(预测错误可能会高)，然后想办法让它们离超平面的距离远。
PS： SVM在若干年前，当数据量还比较少的时候，SVM是最好的分类模型。但是现在随着数据量的不断增大，SVM模型运算速度较慢的缺点开始暴露。而且随着这些年集成学习的不算成熟，现在SVM普遍用于集成学习中基模型的构建。
几个重要的概念：
线性可分(Linearly Separable)：在数据集中，如果可以找出一个超平面，将两组数据分开，那么这个数据集叫做线性可分数据。
线性不可分(Linear Inseparable)：在数据集中，没法找出一个超平面，能够将两组数据分开，那么这个数据集就叫做线性不可分数据。
分割超平面(Separating Hyperplane)：将数据集分割开来的直线/平面叫做分割超平面。
间隔(Margin)：数据点到分割超平面的距离称为间隔。
支持向量(Support Vector)：离分割超平面最近的那些点叫做支持向量。
二、线性可分SVM
回顾: 支持向量到超平面的距离为：
支持向量到超平面的距离
PS:在SVM中支持向量到超平面的函数距离一般设置为1;
支持向量到超平面的距离 - 几何意义
SVM模型 是让所有的分类点在各自类别的支持向量的两边，同时要求支持向量尽可能的远离这个超平面，用数学公式表示如下：
让所有分类点在各自类别的支持向量的两边，同时要求支持向量
尽可能的远离这个超平面
SVM目标函数/损失函数为：
SVM损失函数
1、将此时的目标函数和约束条件使用KKT条件转换为拉格朗日函数，从而转换为无约束的优化函数。
无约束的优化函数
2、引入拉格朗日乘子后，优化目标变成：
原问题
3、根据拉格朗日对偶化特性，将该优化目标转换为等价的对偶问题来求解，从而优化目标变成：
对偶问题
4、所以对于该优化函数而言，可以先求优化函数对于w和b的极小值，然后再求解对于拉格朗日乘子β的极大值。
对偶问题 - 函数展开
5、首先求让函数L极小化的时候w和b的取值，这个极值可以直接通过对函数L分别求w和b的偏导数得到：
6、将求解出来的w和b带入优化函数L中，定义优化之后的函数如下：
7、通过对w、b极小化后，我们最终得到的优化函数只和β有关，所以此时我们可以直接极大化我们的优化函数，得到β的值，从而可以最终得到w和b的值；
PS：β值的求解使用SMO算法，后续会介绍
8、求解wT+b中b的值。
假设存在最优解β*； 根据w、b和β的关系，可以分别计算出对应的w值和b值(使用支持向量对应的样本点来计算，作为实际的b值，支持向量求解出的b值是唯一解)；
这里的(xs,ys)即支持向量，根据KKT条件中的对偶互补条件(松弛条件约束)，支持向量必须满足以下公式：
支持向量需要满足的公式
