支持向量机
先验知识：
- 向量在向量上的投影长度
- 二次规划问题
模型引入
支持向量机是一种二类分类模型，基本模型是定义在特征空间上的“大间隔的分割超平面 ” (Large - Margin Separating Hyperplane)的线性分类器。什么意思呢？
以线性分类模型 PLA(感知机) 为例，其最终目标是找出一个超平面将所有的样本分割开（只要分开就行）。而支持向量机是在此基础上，保证离分割线最近的一些样本（）与超平面之间的距离（distance to closest ）尽量大。如下图，分别为PLA 和SVM学习得到的超分面
这使得对噪声的容忍度（amount of noise tolerance）更大，或者说该超平面鲁棒性（robustness of hyperplane）更强（more robust because of larger distance to closest x_n）
这样可以假设边界不是一条宽度不计的超平面，而是一个有宽度的胖超平面（fat hyperplane）如右图。这里的胖度实际上就相当于鲁棒性，即
那么现在的目标就是找出那个最胖的一个超平面（fattest separating hyperplane）使得该超平面讲所有的大数据正确分类。如下公式描述
所以就有两个问题：
- 如何定义超平面有多胖
- 如何定义该超平面能否正确分类
对于问题1， 超平面有多胖就是看距离超平面最近的数据点到超平面有多近。
对于问题2， 与符号是否一致可以表示分类是否正确，所以可以用来表示分类的准确性。
至此将胖的超平面正式叫做间隔（margin），据此将上式改写为：
转化为最优化问题
根据点到超平面的距离公式，可知
基于超平面 h(x) ，若该超平面能正确分类，则所有的点均满足, 所以 distance公式可以变换成如下：
注：此处本质原因是为了去掉距离公式的绝对值。可以直接乘 一方面是因为二分类问题本来就等于正负1；另一方面原因是因为此处的距离乘上一个正数只是相当于起到了放缩作用，对最后结果不影响
此时，目标函数转换为如下：
缩放margin, 我们知道超平面 和 是同一个超平面，也就是说，对和同时进行缩放还会得到同一超 平面。
那么假设超平面距离最近的点之间的距离的 分子 ,此时可对等号两边同时缩小k倍。即我们将和进行缩放，令距离超平面 最近的点满足 。即
此时，对所有的数据点则会满足如下公式，亦为约 束 条件1
缩放之后，约束条 件2有如下转换：
至此，优化问题的目标函数转为
最终，优化问题可以转换为如下：
对上式可以有如下直观理解：
对上图二分类问题，SVM期望找到红线所示的超平面，使得超平面满足以下两条件：
- 不仅能将样本点正确分开，即蓝绿点到超平面的距离≥1（或者数据距离虚线距离≥0）
- 能让距离超平面最近的数据点到超平面的距离最大，即图中虚线与红线的距离最大。
倒着往回推，目标就是这条红线，即超平面。
那么假设有红线超平面，方程为，然后两虚线方程为。
此时对上述方程进行缩小k倍，得到红线方程为 , 虚线方程为 。将融入到中就有新的方程,满足如下
所以此时，若要满足条件1，则有 y(w^Tx+b )≥ 1（毕竟虚线上的点都等于1了，虚线外面的可得大于1）。
对于条件2。先利用距离公式将虚线上的点距离红线的距离表示出来：
因为经过缩放后，虚线上的点满足 ，所以结合上式可得距离为:
而我们的条件2是想要距离最大化，所以目标函数为
最后，结合条件1（目标）和条件2（约束）可得如下优化函数：
转换为二次规划问题
因为SVM的目标是关于的二次函数，约束是关于和的一次函数。这是一个典型的二次规划问题，即Quadratic Programming（QP）。通常可以使用软件自带的二次规划的库函数来求解。下图给出SVM与标准二次规划问题的参数对应关系，左边为SVM优化问题，右边为二次规划标准形式。
所以，线性SVM算法可以总结为三步：
- 计算对应的二次规划参数
- 根据二次规划库函数，计算
- 将和w代入，得到最佳超平面
总结
对输入数据集, 其中 .如下图
SVM目标是找到一个超平面，该超平满足如下要求：
- 首先能正确的分来两类数据
- 其次是距离两类最近数据点的距离最大，可以理解为该超平面最胖
空间中超平面可以表示为
空间中任意一点到该超平面的距离
根据上述对超平面的要求，可以转为如下优化问题：
对约束2去绝对值可得
假设距离超平面最近的点满足,此时对进行缩放，使得
此时，
因此优化问题可以转换为
上述问题为凸二次规划问题。
先从最大间隔出发，写出SVM的目标（间隔最大）及约束（能正确分类），然后对距离公式去绝对值，再然后对缩放使得边界上的点满足，然后就可以简化优化问题为凸二次规划