支持向量机(SVM)(三)----核函数及正则化

前端之家收集整理的这篇文章主要介绍了支持向量机(SVM)(三)----核函数及正则化前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

上一节最后我们说到我们根据求得的,可求得,,然后求出决策函数,但是我们知道:


是的函数,我们也许不必把带入上式来求解,我们直接把上式带入决策函数可有:



假如我们已经求得最优的,在作出预测的时候,我们可以只进行输入数据x与训练样本的内积即可。在转化为对偶条件的时候,我们知道要满足KKT条件,KKT条件中有一个是:


其中:


由此可以知道,若,则有函数间隔必然等于1,也就是说,只有支持向量满足,而不是支持向量的样本点,必然有。故而在计算下式的时候,我们只需考虑支持向量,而是支持向量的样本点有很少,所以这样会降低计算复杂度。这种形式也为引入核函数做出铺垫。

Kernels

我们上次最后说明了,如果遇到线性不可分的情况,根据现有的分类函数,可能解决不了,比如,下图(来源:知乎


上图中的红点服从,蓝点服从,很明显红蓝点是不可分的,但是通过映射,将其映射到三维空间后,便有:


映射到三维空间之后,红蓝点变得线性可分了。核函数作用其实就是通过一个映射,把低维线性不可分的样本点,映射到高维中,使之变得线性可分。

吴恩达老师说,“原始”的输入我们称之为问题的属性,当“原始”输入经过映射得到一个新的集合,而这个集合传递给学习算法,这样的一个新的集合称之为特征。SVM的输入就是特征而不是原始的输入属性。当低维线性不可分 的时候,我们把输入属性,映射到一个高维特征空间,并把映射后的特征作为新的输入,而新的决策函数,只是把原来的内积运算<x,z>简单替换为即可。而接下我们探讨这个核函数

函数定义为:


其中的为映射函数

凭直觉来看,要求出,我们需要求出,然而要求代价是很大的,因为很难求得,另外当高维的维数很大的时候(这是很有可能的),我们的计算量也是很大的,这让我们很难承受,那么我们可不可以把的值在低维求出呢?

我们先看一个例子:

我们可以把上式写成如下的形式:


假如当N=3时,那么就是如下形式:


对于这个例子,我们在高维中计算的时间复杂度为,而在输入属性中计算,只需的时间,这样给了我们启发,对于高维中的内积,我们在低维中就可以解决

对于kernel,我们有多项式kernel,Gaussian kernel等等,那么给定一个函数K,我们怎么知道他是不是有效的呢?也就是说对于所有的x,z是否存在一个映射,使得成立?

假如K是有效的,那么有,因此K一定是对称的。另外我们令表示向量的第k个坐标,对于任意向量z有:


这就说明了如果K是有效的,那么其对应的核矩阵就是半正定的。这是一个充分必要条件,也是Mercer定理。好了到此我们也说明了什么是核函数。下一节我们将继续上一节的话题,怎么样求解对偶问题的解。请看:

支持向量机(SVM)(四)----SMO

猜你在找的正则表达式相关文章