首页 > 程序开发 > 综合编程 > 其他综合 >

机器学习(四):SVM(2)

2016-10-10

如果w不满足约束,也就是gi(w)>0或hi(w)≠0。这时由于L函数是无约束函数,αi、βi可以任意取值,因此∑ki=1αigi(w)或∑li=1βihi(w)并没有极值,也就是说θP(w)=∞。

拉格朗日对偶(续)

如果w不满足约束,也就是gi(w)>0hi(w)≠0。这时由于L函数是无约束函数,αiβi可以任意取值,因此∑ki=1αigi(w)∑li=1βihi(w)并没有极值,也就是说θP(w)=∞

反之,如果w满足约束,则∑ki=1αigi(w)∑li=1βihi(w)都为0,因此θP(w)=f(w)

综上:

θP(w)={f(w),∞,w满足约束w不满足约束

我们定义:

p?=minwθP(w)=minwmaxα,β:αi≥0L(w,α,β)

下面我们定义对偶函数:

θD(w)=minwL(w,α,β)

这里的D代表原始优化问题的对偶优化问题。仿照原始优化问题定义如下:

d?=maxα,β:αi≥0θD(w)=maxα,β:αi≥0minwL(w,α,β)

这里我们不加证明的给出如下公式:

d?=maxα,β:αi≥0minwL(w,α,β)≤minwmaxα,β:αi≥0L(w,α,β)=p?

这样的对偶问题被称作拉格朗日对偶(Lagrange duality)。

KKT条件

拉格朗日对偶公式中使p?=d?成立的条件,被称为KKT条件(Karush-Kuhn-Tucker conditions):

??wiL(w?,α?,β?)??βiL(w?,α?,β?)α?igi(w?)gi(w?)α?i=0,i=1,…,n=0,i=1,…,l=0,i=1,…,k≤0,i=1,…,k≥0,i=1,…,k(1)

其中的w?,α?,β?表示满足KKT条件的相应变量的取值。条件1也被称为KKT对偶互补条件(KKT dual complementarity condition)。显然这些w?,α?,β?既是原始问题的解,也是对偶问题的解。

严格的说,KKT条件是非线性约束优化问题存在最优解的必要条件。这个问题的充分条件比较复杂,这里不做讨论。

注:Harold William Kuhn,1925~2014,美国数学家,普林斯顿大学教授。

Albert William Tucker,1905~1995,加拿大数学家,普林斯顿大学教授。

William Karush,1917~1997,美国数学家,加州州立大学北岭分校教授。(注意,California State University和University of California是不同的学校)

支持向量

针对最优边距分类问题,我们定义:

gi(w)=?y(i)(wTx(i)+b)+1≤0

由KKT对偶互补条件可知,如果αi>0,则gi(w)=0

\

上图中的实线表示最大边距的分割超平面。由之前对于边距的几何意义的讨论可知,只有离该分界线最近的几个点(即图中的所示的两个x点和一个o点)才会取得约束条件的极值,即gi(w)=0。也只有这几个点的αi>0,其余点的αi=0。这样的点被称作支持向量(support vectors)。显然支持向量的数量是远远小于样本集的数量的。

为我们的问题构建拉格朗日函数如下:<喎"https://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4NCjxwPjxub2JyPkwodyxiLCZhbHBoYTspPTEyoc53oc4yPyZzdW07aT0xbSZhbHBoYTtpW3koaSkod1R4KGkpK2IpPzFdKDIpPC9ub2JyPjwvcD4NCjxwPs6qwcvH873iPC9wPg0KPHA+PG5vYnI+JnRoZXRhO0QoJmFscGhhOyk9bWludyxiTCh3LGIsJmFscGhhOyk8L25vYnI+PC9wPg0KPHA+v8m1w6O6PC9wPg0KPHA+PG5vYnI+P3dMKHcsYiwmYWxwaGE7KT13PyZzdW07aT0xbSZhbHBoYTtpeShpKXgoaSk9MDwvbm9icj48L3A+DQo8cD68tDwvcD4NCjxwPjxub2JyPnc9JnN1bTtpPTFtJmFscGhhO2l5KGkpeChpKSgzKTwvbm9icj48L3A+DQo8cD621GLH87W8v8m1w6O6PC9wPg0KPHA+PG5vYnI+Pz9iTCh3LGIsJmFscGhhOyk9JnN1bTtpPTFtJmFscGhhO2l5KGkpPTAoNCk8L25vYnI+PC9wPg0KPHA+sNG5q8q9M7T6yOu5q8q9MqOsv8m1w6O6PC9wPg0KPHA+PG5vYnI+TCh3LGIsJmFscGhhOyk9MTKhznehzjI/JnN1bTtpPTFtJmFscGhhO2lbeShpKSh3VHgoaSkrYik/MV09MTJ3VHc/JnN1bTtpPTFtJmFscGhhO2l5KGkpd1R4KGkpPyZzdW07aT0xbSZhbHBoYTtpeShpKWIrJnN1bTtpPTFtJmFscGhhO2k9MTJ3VCZzdW07aT0xbSZhbHBoYTtpeShpKXgoaSk/JnN1bTtpPTFtJmFscGhhO2l5KGkpd1R4KGkpPyZzdW07aT0xbSZhbHBoYTtpeShpKWIrJnN1bTtpPTFtJmFscGhhO2k9MTJ3VCZzdW07aT0xbSZhbHBoYTtpeShpKXgoaSk/d1Qmc3VtO2k9MW0mYWxwaGE7aXkoaSl4KGkpPyZzdW07aT0xbSZhbHBoYTtpeShpKWIrJnN1bTtpPTFtJmFscGhhO2k9PzEyd1Qmc3VtO2k9MW0mYWxwaGE7aXkoaSl4KGkpP2Imc3VtO2k9MW0mYWxwaGE7aXkoaSkrJnN1bTtpPTFtJmFscGhhO2k9PzEyKCZzdW07aT0xbSZhbHBoYTtpeShpKXgoaSkpVCZzdW07aT0xbSZhbHBoYTtpeShpKXgoaSk/YiZzdW07aT0xbSZhbHBoYTtpeShpKSsmc3VtO2k9MW0mYWxwaGE7aT0/MTImc3VtO2k9MW0mYWxwaGE7aXkoaSkoeChpKSlUJnN1bTtpPTFtJmFscGhhO2l5KGkpeChpKT9iJnN1bTtpPTFtJmFscGhhO2l5KGkpKyZzdW07aT0xbSZhbHBoYTtpPSZzdW07aT0xbSZhbHBoYTtpPzEyJnN1bTtpLGo9MW15KGkpeShqKSZhbHBoYTtpJmFscGhhO2ooeChpKSlUeChqKT9iJnN1bTtpPTFtJmFscGhhO2l5KGkpKDUpPC9ub2JyPjwvcD4NCjxwPs7Sw8e2qNLlyOfPwsTau/23+7rFPG5vYnI+P3gseT89eFR5PC9ub2JyPqOssqK9q7mryr00tPrI67mryr01v8m1w6O6PC9wPg0KPHA+PG5vYnI+TCh3LGIsJmFscGhhOyk9JnN1bTtpPTFtJmFscGhhO2k/MTImc3VtO2ksaj0xbXkoaSl5KGopJmFscGhhO2kmYWxwaGE7aj94KGkpLHgoaik/PC9ub2JyPjwvcD4NCjxwPtfu1tXO0sPHtcO1vcjnz8K21MW808W7r87KzOKjujwvcD4NCjxwPjxub2JyPm1heCZhbHBoYTtzLnQuVygmYWxwaGE7KT0mc3VtO2k9MW0mYWxwaGE7aT8xMiZzdW07aSxqPTFteShpKXkoaikmYWxwaGE7aSZhbHBoYTtqP3goaSkseChqKT8mYWxwaGE7aSZnZTswLGk9MSwmaGVsbGlwOyxtJnN1bTtpPTFtJmFscGhhO2l5KGkpPTA8L25vYnI+PC9wPg0KPHA+1eK49rbUxbzOyszitcTH873io6zB9NTauvPD5rXE1cK92qGj1eLA79a7zNbC28fzveKz9jxub2JyPiZhbHBoYTs/PC9ub2JyPtauuvO1xMfpv/ahozwvcD4NCjxwPsrXz8ijrLj5vt25q8q9M7/Jx/O94jxub2JyPnc/PC9ub2JyPqGjyLu68zwvcD4NCjxwPjxub2JyPmI/PT9tYXhpOnkoaSk9PzF3P1R4KGkpK21pbmk6eShpKT0xdz9UeChpKTI8L25vYnI+PC9wPg0KPHA+s/20y9auzeKjrM7Sw8e7udPQo7o8L3A+DQo8cD48bm9icj53VHgrYj0oJnN1bTtpPTFtJmFscGhhO2l5KGkpeChpKSlUeCtiPSZzdW07aT0xbSZhbHBoYTtpeShpKT94KGkpLHg/K2I8L25vYnI+PC9wPg0KPHA+1NrWrsewtcTM1sLb1tCjrM7Sw8fS0b6t1riz9ta709DWp7PWz/LBv7bU06a1xDxub2JyPiZhbHBoYTtpPC9ub2JyPrLFzqq3x8Hj1rWjrNLytMujujwvcD4NCjxwPjxub2JyPndUeCtiPSZzdW07aSZpc2luO1NWJmFscGhhO2l5KGkpP3goaSkseD8rYjwvbm9icj48L3A+DQo8cD6008nPyr2/ydLUv7Sz9qOs1Nq/1bzkzqzK/bHIvc+437XEx+m/9s/Co6xTVk2jqHN1cHBvcnQgdmVjdG9yIG1hY2hpbmVzo6m/ydLU09DQp721tc28xsvjwb+hozwvcD4NCjxoMiBpZD0="核函数">核函数

假设我们从样本点的分布中看到x和y符合3次曲线,那么我们希望使用x的三次多项式来逼近这些样本点。那么首先需要将特征x扩展到三维(x,x2,x3) ,然后寻找特征和结果之间的模型。我们将这种特征变换称作特征映射(feature mapping)。

映射函数记作?(x),在这个例子中

?(x)=???xx2x3???

有的时候,我们希望将特征映射后的特征,而不是最初的特征,应用于SVM分类。这样做的情况,除了上面提到的拟合问题之外,还在于样例可能存在线性不可分的情况,而将特征映射到高维空间后,往往就可分了。如下图所示:

\

为此,我们给出核函数(Kernel)的形式化定义:

K(x,z)=?(x)T?(z)

之所以是形式化定义,这主要在于我们并不利用?(x)来计算K(x,z),而是给定K(x,z),来倒推?(x),从而建立?(x)K(x,z)之间的对应关系。

例如:

K(x,z)=(xTz)2=(&sum;i=1nxizi)(&sum;i=1nxizi)=&sum;i=1n&sum;j=1nxixjzizj=&sum;i,j=1n(xixj)(zizj)

根据上式可得:(这里假设n=3

?(x)=??????????????????x1x1x1x2x1x3x2x1x2x2x2x3x3x1x3x2x3x3??????????????????

可以看出?(x)的计算复杂度是O(n2),而(xTz)2的计算复杂度是O(n)

下面我们讨论其他几种常用核函数和它对应的?(x)

K(x,z)=(xTz+c)2=&sum;i,j=1n(xixj)(zizj)+&sum;i=1n(2c??&radic;xi)(2c??&radic;zi)+c2

同样的:(n=3

?(x)=????????????????????????????x1x1x1x2x1x3x2x1x2x2x2x3x3x1x3x2x3x32c??&radic;x12c??&radic;x22c??&radic;x3c????????????????????????????

更一般的,对于K(x,z)=(xTz+c)d,其对应的?(x)(n+dd)维向量。

我们也可以从另外的角度观察K(x,z)=?(x)T?(z)。从内积的几何意义来看,如果?(x)?(z)夹角越小,则K(x,z)的值越大;反之,如果?(x)?(z)的夹角越接近正交,则K(x,z)的值越小。因此,K(x,z)也叫做?(x)?(z)的余弦相似度。

讨论另一个核函数:

K(x,z)=exp(?∥x?z∥22&sigma;2)

这个核函数被称为高斯核函数(Gaussian kernel),对应的?(x)是个无限维的向量。

注:(a+b)n是个p为0.5的二项分布,由棣莫佛-拉普拉斯定理(de Moivre&ndash;Laplace theorem)可知,当n&rarr;&infin;时,它的极限是正态分布。

核函数的有效性

如果对于给定的核函数K,存在一个特征映射?,使得K(x,z)=?(x)T?(z),则称K为有效核函数。

我们首先假设K为有效核函数,来看看它有什么性质。假设有m个样本{x(1),…,x(m)},我们定义m&times;m维的矩阵k:Kij=K(xi,xj)。这个矩阵被称为核矩阵(Kernel matrix)。

Kij=K(xi,xj)=?(x(i))T?(x(j))=?(x(j))T?(x(i))=K(xj,xi)=Kji

如果我们用?k(x)表示?(x)第k个元素的话,则对于任意向量z:

zTKz=&sum;i&sum;jziKijzj=&sum;i&sum;jzi?(x(i))T?(x(j))zj=&sum;i&sum;jzi&sum;k?k(x(i))?k(x(j))zj=&sum;k&sum;i&sum;jzi?k(x(i))?k(x(j))zj=&sum;k(&sum;izi?k(x(i)))2&ge;0

即K矩阵是半正定矩阵。事实上,K矩阵是对称半正定矩阵,不仅是K函数有效的必要条件,也是它的充分条件。相关的证明是由James Mercer给出的,被称为Mercer定理(Mercer Theorem)。

注:James Mercer,1883-1932,英国数学家,英国皇家学会会员,毕业于剑桥大学。曾服役于英国皇家海军,参加了日德兰海战。

Mercer定理给出了不用找到?(x),而判定K(x,z)是否有效的方法。因此寻找?(x)的步骤就可以跳过了,直接使用K(x,z)替换上面公式中的?x,z?即可。例如:

wTx+b=&sum;i&isin;SV&alpha;iy(i)?x(i),x?+b=&sum;i&isin;SV&alpha;iy(i)K(x(i),x)+b(6)

核函数不仅仅用在SVM上,但凡在一个算法中出现了?x,z?,我们都可以使用K(x,z)去替换,这可以很好地改善我们算法的效率。因此,核函数更多的被看作是一种技巧而非理论(kernel trick)。

规则化和不可分情况处理

我们之前讨论的情况都是建立在样例线性可分的假设上,当样例线性不可分时,我们可以尝试使用核函数来将特征映射到高维,这样很可能就可分了。然而,映射后我们也不能100%保证可分。那怎么办呢,我们需要将模型进行调整,以保证在不可分的情况下,也能够尽可能地找出分隔超平面。

这里写图片描述

上面的右图中可以看到一个离群点(可能是噪声),它会造成超平面的移动,从而导致边距缩小,可见以前的模型对噪声非常敏感。再有甚者,如果离群点在另外一个类中,那么这时候就是线性不可分的了。

相关文章
最新文章
热点推荐