支持向量机（SVM）
支持向量机
屏幕快照 2018-02-27 上午11.02.43.png
我们要像线性分类器一样找到一个超平面，不仅能够对数据点进行一个准确的分隔，同时我们希望所有的点尽量都能够远离我们的超平面。
一般来说，我们查找最近点和超平面之间的最大距离，上图中就是两边的Margin和最大。
超平面作为二分类器，如果wx+b>0， 判断类别y为1, 否则判定为-1。
衡量平面到数据集的距离远近的标准，需要函数间隔和几何间隔。
函数间隔
屏幕快照 2018-02-27 上午11.13.13.png
如果正确划分，函数间隔的值永远为正数。值越大，说明点离平面越远，分类的可靠程度更高
几何间隔
表示点到超平面的距离。
屏幕快照 2018-02-27 上午11.19.07.png
但是该间距是带符号的，所以为了取正值，我们可以通过乘以y获得。(f(x)为正时y为1，f(x)为负时y为-1）
下图为正值的几何间距。
屏幕快照 2018-02-27 上午11.36.24.png
SVM基本形式
我们可以发现，如果同时扩大w和b的相同倍数，既扩大函数间隔n倍，则分子扩大n倍，分母也同时扩大n倍，那么几何间距实际上不受影响。
我们通过同时缩放ω和b让距离超平面最近的那些样本点的函数间隔为1。那么最近点函数间隔为1，其余点函数间隔大于1.（为啥取1，是因为方便计算）
屏幕快照 2018-02-27 上午11.44.55.png
那么我们可以得出SVM的基本形式。
屏幕快照 2018-02-27 上午11.48.15.png
求解模型
根据上述约束，我们根据拉格朗日函数进行转换，变为以下问题：
屏幕快照 2018-02-27 下午5.33.28.png
通过计算上式的拉格朗日乘子：阿尔法a，我们可以得到最优解的 w 和 b。
低维映射到高维解决线性不可分问题
当超平面无法进行分割时，我们该怎么办？
一个合适的思路是将样本从原始空间映射到一个更高维的特征空间，使得样本在这个特征空间内线性可分。
屏幕快照 2018-02-28 上午11.42.32.png
比如上图，无法线性分割。如果原来的数据是 x ，我们给它增加一个维度 x2，从一维变成二维，数据就变成了这样
屏幕快照 2018-02-28 上午11.44.40.png
回到一维中，其实就是这样的一条曲线 x2 - x = 0：
屏幕快照 2018-02-28 上午11.54.03.png
核函数
我们通过映射函数讲上面问题转换为
屏幕快照 2018-02-27 下午5.37.11.png
由于样本 xi 和 xj 映射到特征空间之后的内积因为维数可能很高，所以比较难直接计算。为了避开这个障碍，我们设计了“核函数”（kernel function），这个函数使得 xi 和 xj 在特征空间的内积等于它们在原始样本空间中通过核函数 k(xi, xj) 计算的结果。
这样我们就避免了求映射函数，只通过一个核函数就可以在低维空间完成高维空间中才能完成的事！
如果特征维度为 n ，映射的阶数为 d，那我们可以得到的结果是：
屏幕快照 2018-02-28 下午12.29.46.png
