Press "Enter" to skip to content

[机器学习读书笔记] – 支持向量机

本站内容均来自兴趣收集,如不慎侵害的您的相关权益,请留言告知,我们将尽快删除.谢谢.

假设资料是linear separable,也就说我们能够找到一条线把它分开,在那幺多条把它分开的线里面,我们想选一条最胖的线。每一条线用一个w来叫它的方程式,我们看它有多胖的方式就是我们把这条线跟每一个点的距离都算一算,之后,取那个最小的距离,也就是最接近的那个点,用来衡量我们的线到底可以有多胖,我们要找出最胖的线,最后我们要做一个最大化maximize的动作。

 

 

另外我们还要求这条线要正确,要把所有的圈圈叉叉都能够分开,这就表示我们用w所算出来的这个分数跟实际的y是同号的,用一个比较简洁的数学表达式就是y和w乘以x算出来的值相乘,因为是同号,所以一定是大于0, 所以我们把上图的表达式做一些修改,变成我们最终的目标。

 

 

在之后的表达式中,我们把w0拉出来用b来表示。

 

我们首先计算点到平面的距离,如果我们已经有一个平面在手上,我们可以考虑这个平面上的两个点,一个点我把它叫做x’,一个点我把它叫做x”, 它们满足 wx’+b=0,wx”+b=0 ,所以w乘上x’-b,同样的w乘以x”也等于-b。这样的话w若乘上两个相减即-b减掉-b结果也为0。注意到x”, x’ 两个都是平面上的点,所以w乘上平面上任何一个向量都等于0,这代表 w会垂直于这个平面,即w是平面的法向量。

 

对于空间上的任意一点x, 点到平面的距离就是把这个点跟平面上任何一个点连出来一个向量,然后将这个向量向w方向投影,等于是把他们做内积,但做内积的时候要除掉原来的w长度,这样才会在那个方向上有正确的单位计算。

 

第一项是w跟x的内积,第二项是w跟x’的内积, w跟x’的内积就是-b,所以我们最后得出如图所示的式子。

 

 

我们考虑的线是可以把圈圈跟叉叉完美的分开的线,所以我们算出来的分数,跟我们想要的圈圈叉叉是同号的。我们可以利用这个性质,把这里的绝对值脱掉了,因为y乘上这个分数一定是正的。

 

 

接下来,为了数学计算上的方便,我们做了如下的特殊缩放:

 

 

现在我们要多做一个最小化的动作,我们原来做最大化已经够烦的了,现在又冒出来一个最小化的动作,这个好像不太容易,那我们尝试把这个条件稍微放松一点,我们把条件放松成两式相乘都大于等于1这个必要条件。问题是如果我们放松条件说每个大于等于1就好了,会不会每一个都通通都大于1了。例如说,如果我说 y 乘上分数的值,现在通通都大于 1.126。如果我们把 b 跟 w, 做一个放缩,我们把 b 除上 1.126, w 也除上 1.126,我们刚刚每个都大于 1.126,所以做了这个除法的动作以后,还是会大于等于1,满足我们的所有条件。可是1/||w||是我们要最大化的东西。 我们现在把 w 除以 1.126,所以把 w 变短了,w 变短了,那幺 w 的倒数就变大了。 所以说这个 b 跟 w 不会是最佳解。这代表我们把条件放松,对结果一点影响都没有。

 

我们再把求最大值转换为求最小值,并去掉根号,最后要优化的目标变为如图所示:

 

 

举例:

 

 

对于我们要优化的目标的问题的一般求解,我们可以使用 quadratic programming(二次规划):

 

 

这里,我们可以对x做一个非线性转换,如图所示:

 

 

除了以上用quadratic programming求解,我们还可以应用拉格朗日乘子法对原本是一个有条件的最佳化问题,转换为一个没有条件的极值问题来进行求解。如下图所示:

 

(1). 不符合限制条件的是算出来的值都是大于0的,再乘上一个大于等于0的alpha,执行最大化操作,alpha越大越好,最后趋于无限大。 (2). 符合限制条件的是算出来的值都是小于等于0的, 再乘上一个大于等于0的alpha,执行最大化操作,alpha越大越好,每一个alpha最小就是0。最后剩下的就是需要最佳化的项。

 

透过一个最小化的过程,我就可以把不符合限制条件的淘汰。所以我们做的事情,是将 SVM 转化成一个看似没有条件的式子。看似没有条件,其实把条件藏在maximization里面。

 

 

根据强对偶性关系,我们将左边的问题转化为求解右边的问题,有什幺好处,这样做的好处是我们把对 b 和 w 的最佳化的问题,变成没有条件的,因为现在对 b 和 w 最佳化问题在里面,里面也就是第一步要做的。

 

 

 

现在求里面的式子关于b的偏导数,并代入原式中,我们可以得到:

 

 

求里面的式子关于w的偏导数,并代入原式中,我们可以得到:

 

 

对于拉格朗日对偶问题,需要满足KKT条件:

 

 

将求极大值问题转换为求极小值问题:

 

 

现在我们转化为相对应的 quadratic programming 问题:

 

 

求出alpha后,再根据KKT条件求出最佳的 w 和 b。

 

Be First to Comment

发表评论

邮箱地址不会被公开。 必填项已用*标注