【机器学习】支持向量机SVM原理总结

@(Machine Learning)

支持向量机涉及的知识点多，应用广泛，现在特别总结一下支持向量机SVM的基本原理，只涉及一些结论总结下SVM的基本思路思想和结论，详细的证明可以参考下面的References。

References：
《机器学习》 西瓜书_周志华
《统计学习方法》 李航

问题引入

这部分西瓜书上面说的比较简单，《统计学习方法》上面更加详细。

给定线性可分数据集，分离超平面为：

这里，w是平面的法向量，b是截距。

函数间隔与几何间隔

函数间隔的定义：

需要注意的是这里的yi取值只有+1和-1，+1表示xi为正例，-1表示xi为负例。
函数间隔的意义就是，看真实类标与预测类标的符号是否一致，一致的话就表示为正确分类。

对法向量的规范化，比如||w||= 1，使间隔是确定的话，函数间隔就成为几何间隔。
几何间隔的定义：

函数间隔和几何间隔的关系：

最大间隔分离超平面

能够正确分类的超平面，具有很多个，我们想要找到一个感觉上最合理的超平面。那么这个合理的超平面就是对训练数据集找到几何间隔最大的超平面，因为这样能够最好地把正负类分隔。

求的这个超平面的问题表示为最优化问题，最大化几何间隔：

考虑函数间隔和几何间隔的关系，问题转化为：

因为我们只关心最优化问题的解，训练集确认的情况下，函数间隔不影响最优化问题的解，为了方便我们取为1。问题转化为最大化1/||w||，这和最小化||w||是等价的，因此问题最终转化为：

这是标准的SVM的最优化问题，这是一个凸二次规划问题。下一步我们将关心怎么求解这个最优化问题。

关于支持向量与间隔的理解很直观，参看西瓜书上面的图：

最优化问题求解_对偶算法

上述SVM的最优化问题现在已经有很多现成的包能够帮助求解，但是我们一般应用对偶算法。优点有两个：
1. 对偶问题往往更容易求解
2. 自然引入核函数，能够将线性分类问题推广到非线性问题。

关于拉格朗日对偶性的一些简单总结可以看我的这篇博客：
https://blog.****.net/timso1997/article/details/80357589

根据上述得到的最优化问题，定义拉格朗日函数：

原始问题的对偶问题是极大极小问题：

先利用偏导数为0求最小化问题，然后求最大问题，最后将最大问题转换为最小问题，原始问题能够转换为下面的对偶问题：

上述问题求的α后（至于怎么求解α，后面概述），可以求得w和b。
可以利用KKT条件证明，求得的w*和b*如下：

最后可以得到下列算法：

上述问题加入松弛变量和惩罚参数C后，能够得到：

利用相同的过程和原理，可以得到加入松弛变量和惩罚参数C后的算法：

线性支持向量机学习的另一种解释

引入合页损失函数：

如下图：

在吴恩达的机器学习的课程中，是利用该函数来引出支持向量机的。

下面定理给出线性支持向量机学习的另一种解释：

非线性支持向量机与核函数

上述的支持向量机只能解决线性分类问题，为了求解非线性支持向量机，采取的方法是将非线性问题转换为线性问题，这需要一个非线性变换。进行这个变换，一般使用核函数。

核函数的定义：

核技巧只定义函数K，不定义映射函数。书上说的原因是：直接计算K比较容易，而通过映射函数计算K不容易。

将核函数应用到支持向量机中，可以得到对偶问题的目标函数成为：

我们可以理解为：利用核函数，我们就对原来的线性不可分问题进行了一个映射，将之转换为一个线性可分问题，求解原来的线性不可分问题就能够利用我们之前的求解线性可分问题的方法。

最终我们可以得到一个非线性支持向量机学习算法：

上述提到的正定核函数，详情可看《统计学习方法》。

我们一般用到的核函数有：
多项式核函数、高斯核函数、字符串核函数等等。

求解对偶问题

上述提到，怎么求解α呢？求解α是一个二次规划问题，可以使用二次规划的算法来求解。一般的求解方法是使偏导为0将α求解。
但是问题的规模是正比于训练样本数的，样本数很大的时候，效率是非常低的。
为了高效率求解这个问题，提出了很多高效的算法，其中一个书上讲的比较多的就是SMO算法。
关于SMO算法不在本文展开了。
推荐阅读：西瓜书、《统计学习方法》中关于支持向量机的部分，有相应介绍。