Paste_Image.png
一.什么是支持向量机
1、支持向量机（Support Vector Machine，常简称为SVM）是一种 监督式学习的方法，可广泛地应用于统计分类以及回归分析。支持向量机属于一般化线性分类器，这族分类器的特点是他们能够同时最小化经验误差与最大化几何边缘区，因此支持向量机也被称为最大边缘区分类器。
2、支持向量机将向量映射到一个更高维的空间里，在这个空间里建立有一个最大间隔超平面。在分开数据的超平面的两边建有两个互相平行的超平面，分隔超平面使两个平行超平面的距离最大化。假定平行超平面间的距离或差距越大，分类器的总误差越小。
3、假设给定一些分属于两类的2维点，这些点可以通过直线分割， 我们要找到一条最优的分割线，如何来界定一个超平面是不是最优的呢?
Paste_Image.png
二、求解过程
最优超平面可以有无数种表达方式，即通过任意的缩放 w 和 b 。 习惯上我们使用以下方式来表达最优超平面。
Paste_Image.png
我们令两类的点分别为+1, -1，所以当有一个新的点x需要预测属于哪个分类的时候，我们用
sgn(f(x))，就可以预测了，sgn表示符号函数，当f(x) > 0的时候，sgn(f(x)) = +1, 当f(x) < 0的时候sgn(f(x)) = –1。
通过几何学的知识，我们知道点 x 到超平面 的距离为:
Paste_Image.png
对于超平面, 表达式中的分子为1,
Paste_Image.png
然后得到目标函数
Paste_Image.png
这是一个拉格朗日优化问题，可以通过拉格朗日乘数法得到最优超平面的权重向量W和偏置b
Paste_Image.png
三、拉格朗日对偶
如何确定w和b呢？
答案是寻找两条边界端或极端划分直线中间的最大间隔（之所以要寻最大间隔是为了能更好的划分不同类的点，下文你将看到：为寻最大间隔，导出1/2||w||^2，继而引入拉格朗日函数和对偶变量a，化为对单一因数对偶变量a的求解），从而确定最终的最大间隔分类超平面hyper plane和分类函数；
拉格朗日对偶的原理
Paste_Image.png
上述式子有两个条件（等式条件和不等式条件）由此我们定义一般化的拉格朗日公式
Paste_Image.png
由此我们定义一般化的拉格朗日公式
Paste_Image.png
这里的P代表primal。我们设如下约束条件（primal constraints）：
Paste_Image.png
如果条件不全部满足的话，我们总可以调整
α和β使最大值出现正无穷，即会出现下面情况(这里比较重要，说明了为什么要求最大)
Paste_Image.png
因此我们可以得出如下式子：
Paste_Image.png
这样我们原来要求的min f(w)可以转换成求了
Paste_Image.png
这个问题就是原问题的对偶问题，相对于原问题只是更换了min和max的顺序，而一般更换顺序的结果是
Max Min(X) <= Min Max(X)。然而在这里两者相等。由此我们可以设如下
Paste_Image.png
Paste_Image.png
四、最优间隔分类器求解（求解过程，上两步是铺垫）**
在之前为了寻找最有分类器，我们提出了如下优化问题
Paste_Image.png
在这里我们可以把约束条件改写成如下：
Paste_Image.png
Paste_Image.png
很显然我们可以看出实线是最大间隔超平面，假设×号的是正例，圆圈的是负例。在虚线上的点和在实线上面的两个一共这三个点称作支持向量。现在我们结合KKT条件分析下这个图。
Paste_Image.png
这个也就说明[图片上传中个
gi(w)时，w处于可行域的边界上，这时才是起作用的约束。
1、那我们现在可以构造拉格朗日函数如下：
Paste_Image.png
2、接下来我们对w和b分别求偏导数
Paste_Image.png
3、将上式带回到拉格朗日函数中得到：
Paste_Image.png
4.优化等式
Paste_Image.png
Paste_Image.png
6.最终问题
Paste_Image.png
五、核函数 ——高维空间映射，在低维时空里解决
如下所示，无法线性标示进行分割，但是可以用二次函数简单分割
Paste_Image.png
映射到高维空间，可以很容易进行分割
Paste_Image.png
在计算的时候，它可以让x和z不用通过H()映射到高维空间再计算内积，而是直接在低维空间里计算了。
我们用K()表示核函数，那么核函数作用就是：K(x,z)=
避开了X映射到H(X)，Y映射到H(Y)这么一个过程
Paste_Image.png
线性核：
Paste_Image.png
高斯核：
通过调控参数σ，高斯核具有相当的灵活性
Paste_Image.png
六、SMO算法求解α
Paste_Image.png
要解决的是在参数{α1, α2,...α3}上求最大值W(α)的问题，至于xi,yi都是已知数。C由我们预先设定，也是已知数。
按照坐标上升的思路，我们首先固定除α1 以外的所有参数，然后在α2上求极值。等一下，这个思路有问题，因为如果固定α1以外的所有参数，那么α2 将不再是变量（可以由其他值推出）
Paste_Image.png
SMO的主要步骤如下：
- 1.选择连个
α， 如α1、α2，选取方法使用启发式方法，固定其他参数 - 2.确定极值
W，αi由αj表示
假设确定了α1、α2，则：
Paste_Image.png
{α1, α2,...α3}都是已知固定值，因此为了方便，可将等式右边标记成实数值
Paste_Image.png
当y(i),y(j) 异号时，也就是一个为1，一个为-1时，他们可以表示成一条直线，斜率为1。如下图：
Paste_Image.png
Paste_Image.png
当y(i),y(j) 同号时
Paste_Image.png
然后我们打算将α1用α2表示：
Paste_Image.png
Paste_Image.png
α2满足以下条件：
Paste_Image.png
w、b求解公式
Paste_Image.png
启发式搜索的方法和求b值的公式
Paste_Image.png
[1] http://www.tuicool.com/articles/2aYryeV
[2] https://wizardforcel.gitbooks.io/dm-algo-top10/content/svm-1.html
网友评论