[关闭]
@PandoraKey 2021-07-14T09:19:25.000000Z 字数 7849 阅读 39

支持向量机

Kernel


二分类

硬间隔支持向量机

支持向量机很早很早就被提出来了,而且在最近几年里一直在被更新和改进,但是追本溯源,我们还是得回到那个古老的年代,去看看支持向量机原本的模样。

我们总是希望这世界上的事情没有那么多的弯弯绕绕,能一刀切开就好了。SVM 最早干的就是这一刀切的工作。现在有两拨样本,标签分别是 ,它们在原空间上的分布如下图所示:

image_1e5ruc3u7gooqcn1eqmpjdimem.png-48.2kB

我们希望能够找到一条分界线,把两拨样本合理地分开,而且尽可能地让最靠近分解的样本点之间的距离最大,也就是图中的 之和要最大。当我们确定分界线之后,无论类别是什么,我们取最靠近分界线的样本点,做穿过该样本点且与分界线平行的直线,称之为边界线,两个类别的边界线距离就是间隔(Margin)。我们给图中的线 定义一个方程,即:

则分别是

我们合并这两个边界线的方程,即:

那我们会开始思考,既然我是想要让间隔最大,那我应该考虑间隔是什么,于是这里就要用到高中学的一个知识点——两直线间的距离公式:

由于 的距离和 的距离势必要相等的,因此间隔就是:

在式 中,我们能发现如果希望 越大,那必须让 越小,因此这就转换成一个最优化问题,求的是 的最小值,当然还有一个限制条件,就是要限制样本点不能出现在间隔当中,只能是在间隔边上或者间隔外,即:

接着我们得构造 的拉格朗日多项式,要先做个说明的是,为什么是减号,而不是加号:

说明结束,转换成拉格朗日多项式就是

接着对 做微分:

那这样子我们就能求出在原空间中的 是个啥了。将拉格朗日多项式的微分所得带回 中,但我们可以先算 即:

接着我们把上面两结果带进 里,可得:

到这里,我们可算是把 给整出来了,于是乎我们就转换成了一个对偶问题,来求 的最大值,但是要记得它有俩限制式:

到这里,我们对于原空间的推导就结束了,因为我们的主要目的是把它映射到高维空间去,也就是把全部的 都换成 ,推导过程和在原空间时是一致的,只不过是把 换成了 ,即:

接着通过 KKT 来对 做分析,我们会发现当 时,因为 ,所以 ,那样本点刚好就落在边界线上;如果 ,则意味着 ,换句话说,当 时,该样本点处于间隔之外。

于是我们就能确定:

最终得到最后的分界线方程就是:

软间隔支持向量机

原始优化问题:

构造拉格朗日方程:

分别对做微分:

很明显,在这之前我们对原空间进行计算,现在我们要将投射到高维空间,于是所有的都要变成


分别对做微分:




将拉格朗日等式展开,并代入上述结果,得:

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注