SVM支持向量机
一、了解SVM
支持向量机，它是一种二类分类模型，其基本模型定义为特征空间上的间隔最大的线性分类器，其学习策略便是间隔最大化，最终可转化为一个凸二次规划问题的求解。
1.1、分类的起源：logistic回归
线性分类器 ：给定一些数据点，它们分别属于两个不同的类，现在要找到一个线性分类器把这些数据分成两类。
一个线性分类器的学习目标便是要在n维的数据空间中找到一个超平面（hyper plane），这个超平面的方程可以表示为（ wT中的T代表转置）：
映射函数：使用logistic函数（或称作sigmoid函数）将自变量映射到(0,1)上，映射后的值被认为是属于y=1的概率。
1.2、线性分类实例
这个超平面应该是最适合分开两类数据的直线。而判定“最适合”的标准就是这条直线离直线两边的数据的间隔最大。所以，得寻找有着最大间隔的超平面。
1.3、函数间隔和几何间隔
函数间隔：通过观察w*x+b的符号与类标记y的符号是否一致可判断分类是否正确
几何间隔：
1.4、最大间隔分类器
最大间隔分类器（maximum margin classifier）的目标函数可以定义为：
如果令函数间隔r等于1 ，目标函数变为：
二、深入SVM
2.1、从原始问题到对偶问题的求解
上述目标函数等价于：
因为现在的目标函数是二次的，约束条件是线性的，所以它是一个凸二次规划问题。
在一定的约束条件下，目标最优，损失最小。
此外，由于这个问题的特殊结构，还可以通过拉格朗日对偶性（Lagrange Duality）变换到对偶变量 (dual variable) 的优化问题，即通过求解与原问题等价的对偶问题（dual problem）得到原始问题的最优解，这就是线性可分条件下支持向量机的对偶算法，这样做的优点在于：一者对偶问题往往更容易求解；二者可以自然的引入核函数，进而推广到非线性分类问题。
所以定义拉格朗日函数：
令
则目标函数变为：
不妨把最小和最大的位置交换一下，变成：
换言之，之所以从minmax的原始问题，转化为maxmin的对偶问题，一者因为是的近似解，二者，转化为对偶问题后，更容易求解。
2.2、对偶问题求解的3个步骤
1、我们分别对w，b求偏导数，即L对w、b的偏导等于零 ，化简得：
2、求a的极大值
这样，求出了 ai，然后求得w，b，最后得出分离超平面和分类决策函数。
3、在求得L(w, b, a) 关于 w 和 b 最小化，以及对a的极大之后，最后一步则可以利用SMO算法求解对偶问题中的拉格朗日乘子a。
到目前为止，我们的 SVM 还比较弱，只能处理线性的情况，下面我们将引入核函数，进而推广到非线性分类问题。
2.3、核函数
直观理解：
我们把这里的计算两个向量在隐式映射过后的空间中的内积的函数叫做核函数 (Kernel Function) ， 分类函数加上核函数后变为：
常用的核函数：
多项式核、高斯核（会将原始空间映射为无穷维空间 ）、线性核
核函数的本质
简要三点：
实际中，我们会经常遇到线性不可分的样例，此时，我们的常用做法是把样例特征映射到高维空间中去(映射到高维空间后，相关特征便被分开了，也就达到了分类的目的)；
但进一步，如果凡是遇到线性不可分的样例，一律映射到高维空间，那么这个维度大小是会高到可怕的。那咋办呢？
此时，核函数就隆重登场了，核函数的价值在于它虽然也是讲特征进行从低维到高维的转换，但核函数绝就绝在它事先在低维上进行计算，而将实质上的分类效果表现在了高维上，也就如上文所说的避免了直接在高维空间中的复杂计算。
2.4、使用松弛变量处理 outliers 方法
其实就是加上最后的误差项，使目标函数变为：
新的拉格朗日函数为：
最终求a时的dual问题变为：
可以看到唯一的区别就是现在 dual variable的 a 多了一个上限 C。
这样一来，一个完整的，可以处理线性和非线性并能容忍噪音和 outliers 的支持向量机才终于介绍完毕了。
2.5、小结
SVM它本质上即是一个分类方法，用w^T+b定义分类函数，于是求w、b，为寻最大间隔，引出1/2||w||^2，继而引入拉格朗日因子，化为对拉格朗日乘子a的求解（求解过程中会涉及到一系列最优化或凸二次规划等问题），如此，求w.b与求a等价，而a的求解可以用一种快速学习算法SMO，至于核函数，是为处理非线性情况，若直接映射到高维计算恐维度爆炸，故在低维计算，等效高维表现。
支持向量机的优点是：
- 在高维空间有效。
- 在维度数量大于样本数量的情况下仍然有效。
- 在决策功能（称为支持向量）中使用训练点的子集，因此它也是内存有效的。
- 多功能：可以为决策功能指定不同的内核函数。提供通用内核，但也可以指定自定义内核。
支持向量机的缺点包括：
- 如果特征数量远远大于样本数量，则该方法可能会导致较差的性能。
- 支持向量机不直接提供概率估计，这些是使用昂贵的五-折交叉验证计算的