机器学习核函数基本概念.docx

《机器学习核函数基本概念.docx》由会员分享，可在线阅读，更多相关《机器学习核函数基本概念.docx（30页珍藏版）》请在三一办公上搜索。

1、机器学习核函数基本概念机器学习-核函数基本概念 1 多项式空间和多项式核函数 n定义 1.1 (核或正定核) 设X是R中的一个子集，称定义在XX上的函数K(x,z)是核函数，如果存在一个从X到Hilbert空间H的映射F F:xaF(x)H (1.1) 使得对任意的x,zX， K(x,z)=(F(x)F(z) (1.2) 都成立。其中()表示Hilbert空间H中的内积。 定义1.2 设x=(x1,x2,L,xn)TRn，则称乘积xj1xj2Kxjd为x的一个d阶多项式，其中j1,j2,K,jd1,2,K,n。 1. 有序齐次多项式空间 考虑2维空间中的模式x=(x1,x2)T，其所有的2阶单

2、项式为 x1，x2，x1x2，x2x1 (1.3) 注意，在表达式(1.3)中，我们把x1x2和x2x1看成两个不同的单项式，所以称式中的单项式为有序单项式。这4个有序单项式张成的是一个4维特征空间，称为2阶有序齐次多项式空间，记为H。相应地可建立从原空间R到多项式空间H的非线性映射 C2:x=(x1,x2)aC2(x)=(x1,x2,x1x2,x2x1)H (1.4) 同理，从R到d阶有序齐次多项式空间H的映射可表示为 n2n22T22TCd:x=(x1,x2,K,xn)TaCd(x)=(xj1xj2Kxjd|j1,j2,K,jd1,2,K,n)TH(1.5) 这样的有序单项式xj1xj2K

3、xjd的个数为n，即多项式空间H的维数nH=n。如果在H中进行内积运算Cd(x)Cd(z)，当n和d都不太小时，多项式空间H的维数nH=nddd会相当大。如当n=200，d=5时，维数可达到上亿维。显然，在多项式空间H中直接进行内积运算将会引起“维数灾难”问题，那么，如何处理这个问题呢？ 我们先来考查n=d=2的情况，计算多项式空间H中两个向量的内积 2222 (1.6) (C2(x)C2(z)=x1z1+x2z+xxzz+xxzz=(xz)2212122121若定义函数 K(x,z)=(xz)2 (1.7) 则有 (C2(x)C2(z)=K(x,z) (1.8) 即4维多项式空间H上的向量内

4、积可以转化为原始2维空间上的向量内积的平方。对于一般的从R到d阶有序多项式空间H的映射也有类似的结论。 定理1.1 考虑由式定义的从R到多项式空间H的映射Cd(x)，则在空间H上的内积(Cd(x)Cd(z)可表为 nn(Cd(x)Cd(z)=K(x,z) (1.9) 其中 K(x,z)=(xz)d (1.10) 证明：直接计算可得 (Cd(x)Cd(z)=Kxj1=1njd=1nnj1Kxjdzj1Kzjd n =xj1=1nj1zj1Kxjdzjd jd=1=(xjzj)d=(xz)d (1.11) j=1 上述定理表明，我们并不需要在高维的多项式空间H中直接做内积运算(Cd(x)Cd(z)

5、， 而利用式定义的映射中，多项式空间H的分量由所有的d阶有序单项式组成。如果把该多项式空间的分量扩充为所有不超过d阶的有序单项式，便得到从R到有序多项式空间的映射Cd nnCd:x=(x1,x2,K,xn)aCd(x)=(xj1Kxjd,dxj1Kxjd,K,dx1,K,dxn,1|j1,j2,K,jd1,2,K,n)T(1.12) 对于这个映射，我们有如下的定理： T定理1.2 考虑有式定义的从R到多项式空间H的映射Cd，则空间H上的内积(Cd(x)Cd(z)可表为空间R上的内积(xz)的函数(xz)+1)d，即若定义两个变量nnx和z的函数 K(x,z)=(xz)+1)d (1.13) 则

6、有 (Cd(x)Cd(z)=K(x,z) (1.14) 上述有序多项式空间的一个简单的例子是 2TC2:x=(x1,x2)aC2(x)=(x1,x22,x1x2,x2x1,2x1,2x2,1)(1.15) T3. 无序多项式空间 如果我们把式中的x1x2和x2x1看作相同的单项式，那么我们就可以把从R2到4维多项式空间H的映射简化为从R2到3维多项式空间的映射 2T (x1x2)Ta(x1,x22,x1x2) (1.16) 将映射调整为 2 F2(x)=F2(x1,x2)=(x1,x22,2x1x2) (1.17) 则相应的多项式空间称为2阶无序多项式空间，并且有 (F2(x)F2(z)=(x

7、z) (1.18) 对式所示的变换Cd(x)按下述方式操作：把Cd(x)中次序不同但因子相同的各分量合并为一个分量，并在该分量前增加一个系数，这个系数取为相应次序不同但因子相同的分量在Cd(x)中出现次数的平方根。这样得到的从R到d阶无序多项式空间的变换n2Fd(x)仍满足关系式 (Fd(x)Fd(z)=K(x,z) (1.19) 其中 K(x,z)=(xz) (1.20) 根据定义1.1，我们称和分别为d阶多项式核函数和d阶齐次多项式核函数。 比较式定义的变换C2(x)和式定义的F2(x)可以发现，它们所映射到的多项式空间是不同的。前者是一个4维多项式空间，后者为一个3维多项式空间。但是内d

8、积是相同的，它们都可以表示为内积的函数K(x,z)=(xz)2。这说明：多项式空间不是由核函数唯一确定的。 2 Mercer 核 1.半正定矩阵的特征展开 给定向量集合X=x1,x2,K,xl，其中xiRn,i=1,2,K,l 。设K(x,z)是XX上的对称函数，我们定义 Gij=K(xi,xj),i,j=1,2,L,l (1.21) 则称G=(Gij)是K(x,z)关于X的Gram矩阵。我们首先要研究的问题是：当Gram矩阵G满足什么条件时，函数K(,)是一个核函数。 定义 1.2 定义在R上的矩阵算子G：对u=(u1,u2,K,ul)TRl，Gu的分量由下式确定 Gui=lK(x,x)u,

9、i=1,2,K,l (1.22) ijjj=1l定义1.3 考虑定义1.2给出的矩阵算子G。称lR为它的特征值，并称v为相应的特征向量，如果 Gv=lv 且v0 (1.23) 定义 1.4 考虑定义1.2给出的矩阵算子G。称它是半正定的，如果对u=(u1,u2,K,ul)TRl，有 uGu=Ti,j=1K(x,x)uuijilj0 (1.24) 引理 1.1 若定义1.2给出的矩阵算子G是半正定的，则存在着l个非负特征值lt和互相正交的单位特征向量vt，使得 K(xi,xj)=lvvt=1lttitj, i,j=1,2,m, (1.25) 证明： 由于G是对称的，所以存在着正交矩阵V=(v1,

10、v2,L,vl)和对角矩阵L=diag(l1,l2,L,ll)，使得 G=VLV (1.26) T这里vt=(vt1,vt2,L,vtl)T是矩阵G的第t个特征向量，它对应的特征值是lt。因为G是半正定的，所以所有特征值均为非负数。于是由推知 K(xi,xj)=vlv=lvvtittjt=1t=1lllttitj (1.27) 引理 1.2 若引理1.1的结论成立，则存在着从X到R的映射F，使得 K(xi,xj)=(F(xi)F(xj),i,j=1,2,L,l (1.28) 其中()是特征空间R的内积。因而K(,)是一个核函数。 证明： 定义映射 F:xiaF(xi)=(ll1v1i,l2v2

11、i,L,llvli)TRl (1.29) 直接验证可知引理1.2成立。 引理 1.3 若引理1.2的结论成立，则矩阵G是半正定的。 证明： 设G不是半正定的，则一定存在着与一个负特征值ls相对应的单位特征向量vs。定义Rl中的向量z z=F(x1),F(x2),L,F(xl)vs (1.30) 则有 TT0z=vSF(x1),L,F(xl)TF(x1),L,F(xl)vS=vSKvS=lSvS22=lS (1.31) 显然，这与ls是负特征值相矛盾。因此K必须是半正定的。 定理 1.3 设X是有限集合X=x1,x2,K,xl，K(x,z)是定义在XX上的对称函数。则由定义1.2给出的矩阵算子G

12、半正定，等价于K(,)可表示为 K(xi,xj)=其中lt0是矩阵 lvvt=1lttitj (1.32) G=(K(xi,xj)li,j=1 (1.33) 的特征值，vt=(vt1,vt2,L,vtl)T为对应于lt的特征向量，也等价于K(x,z)是一个核函数，即K(xi,xj)=(F(xi)F(xj)，其中映射F由式定义。 2. 半正定积分算子的特征展开 n设输入集合为R中的紧集X，并设K(x,z)是XX的连续对称函数。我们要研究的问题是，当K(x,z)满足什么条件时，它是一个核函数。 定义 1.5 定义积分算子TK为按下式确定的在L2(x)上的积分算子 TKf=TKf()=K(,z)f(

13、z)dz,fL2(x) (1.34) X 定义 1.6 考虑定义1.5给出的积分算子TK，称l为它的特征值，j为相应的特征函数，如果 TKj=lj (1.35) 定义 1.7 考虑定义1.5给出的积分算子TK。称它是半正定的，如果对fL2(x)，有 XXK(x,z)f(x)f(z)dxdz0 (1.36) 引理 1.4 若定义1.5给出的积分算子TK是半正定的，则存在着可数个非负特征值lt和相应的互相正交的单位特征函数jt(x)，使得K(,)可表示为XX上的一致收敛的级数 K(x,z)=lj(x)j(z) (1.37) tttt=1n引理 1.5 若引理1.4的结论成立，则存在着XR到Hilb

14、ert空间l2的映射F，使得 K(x,z)=(F(x)F(z)， x,zX (1.38) 其中()是l2上的内积。因而K(,)是一个核函数。 证明： 定义映射 F：xaF(x)=(l1j1(x),l2j2(x),L)T (1.39) 则可验证引理1.5成立。 引理 1.6 若引理1.5的结论成立则积分算子Tk是半正定的。 n定理 1.4 令X是R上的一个紧集，K(x,z)是XX上的连续实值对称函数。则由定义1.5给出的积分算子Tk半正定 XXz0 ， fL(x) (1.40) K(x,z)f(x)f(z)dxd2等价于K(,)可表示为XX的一致收敛序列 K(x,z)=lj(x)j(z) (1.

15、41) ttti-1其中lt0是Tk的特征值，jtL2(x)是对应lt的特征函数。它也等价于K(x,z)是一个核函数 K(x,z)=(F(x)F(z) (1.42) 其中映射F由式定义，而()是Hilbert空间l2上的内积。 定义 1.8 称函数K(x,z)为Mercer 核，如果K(x,z)是定义在XX上的连续对称函数，其中X是R的紧集，且由定义1.5给出的积分算子是半正定的。 n定理 1.5 设X为R上的紧集，K(x,z)是XX上的连续对称函数，则积分算子TK n半正定的充要条件是K(x,z)关于任意的x1,x2,L,xlX的Gram矩阵半正定。 3 正定核 n定理 1.6 设X是R的子

16、集。若K(x,z)是定义在XX上的正定核，则对x1,x2,L,xlX，函数K(x,z)关于x1,x2,L,xl的Gram矩阵都是半正定的。 证明： K(x,z)是定义在XX上的正定核，因此存在着从X到Hilbert空间H的映射F，使得 K(x,z)=(F(x)F(z) (1.43) 任取x1,x2,L,xlX，构造K(,)关于x1,x2,L,xl的Gram矩阵(Kij)li,j=1=(K(xi,xj)li.j=1。显然，根据由式可以断言，对C1,C2,L,ClR,我们有 2CCK(x,x)=CCF(x)F(x)=(CF(x)CF(x)=CF(x)ijijijijiijjjii,ji,jiji0

17、 (1.44) 这表明K(x,z)关于x1,x2,L,xl的Gram矩阵是半正定的。 引理 1.7 若集合S由所有的下列元素组成 f()=aK(,x) (1.45) iii=1l其中l为任意的正整数，a1,a2,L,alR,x1,x2,L,xlX,则S为一个向量空间。 证明： 由于集合S中的元素对于加法和数乘封闭，所以S构成一个向量空间。 引理 1.8 若对S中的两元素 f()=定义运算* f*g=naK(,x)和g()=bK(,xiilljj) (1.46) i=1j=1abK(x,x) (1.47) ijiji=1j=1ll并由此定义在SS上的函数K(f,g)=f*g，则该函数关于f1,f

18、2,L,flS的Gram矩阵都是半正定的。 证明： 由f*f=i,j=1aailjK(xi,xj)0知： 若任意选取f1,f2,L,flS，记函数K相应的Gram矩阵为(fi*fj)i.j=1。显然它是对称矩阵。由可知对C1,C2,L,ClR有： li,j=1CCilj(fi*fj)=(Cifi)*(Cjfj)0 (1.48) i=1i=1ll这表明Gram矩阵(fi*fj)i.j=1是半正定的。 引理 1.9 在引理1.8中定义的运算*具有如下性质：对于f,gS，有 f*gl2(f*f)(g*g) (1.49) 证明： 任取f,gS,则K关于f,g的Gram矩阵为 K(f,f)K(f,g)

19、(1.50) K(g,f)K(g,g)因为K(f,g)=K(g,f)，所以由引理1.8可知：矩阵是半正定的，其行列式非负。由此可知 K(f,f)K(g,g)-K(f,g)K(g,f)0 2K(f,g)K(f,f)K(g,g)f*g(f*f)(g*g)引理 1.10 引理1.8中定义的运算*是S上的内积运算，因而可记为 f*g=(fg) (1.52) 证明： 直接验证可知该运算具有内积运算应满足的如下性质：对f,g,hS和2 (1.51) c,dR有 f*f0 (1.53) f=0f*f=0 (1.54) (cf+dg)*h=c(f*h)+d(g*h) (1.55) f*g=g*f (1.56)

20、 只需证明：若f*f=0，则有f=0。事实上，若 f()=则按运算规则知，对xX，有 aK(,x) (1.57) iii=1l K(,x)*f=f(x) (1.58) 由于 K(,x)*f所以 2(K(,x)K(,x)(f*f)=(K(x,x)(f*f) (1.59) f(x)=K(,x)(f*f) (1.60) 此式意味着当f*f=0时，对x，都有f(x)=0，即f(x)为零元素。 引理 1.11 若H是引理1.7中的集合S在引理1.8中定义的内积运算意义下的闭包，则H是一个Hilbert空间。 定理 1.7 设K(x,z)是定义在XX上的对称函数。若对x1,x2,L,xlX，函数2K(x,

21、z)关于x1,x2,L,xl的Gram矩阵都是半正定的，则K(x,z)是一个正定核。 证明： 定义映射 F:xK(,x) (1.61) 由引理1.7和1.11知，该映射是从X到某一Hilbert空间的映射。由式可得到 K(,x)*K(,z)=K(x,z) (1.62) 由引理1.10知引理1.8中定义的运算*是内积运算。利用式可得到 K(x,z)=(F(x)F(z) (1.63) 由定义1.1知K(x,z)是正定核。 n 定义 1.12 设X是R的子集。称定义在XX上的对称函数K(x,z)为一个正定核，如果对x1,x2,L,xlX，K(,)相对于x1,x2,L,xl的Gram矩阵都是半正定的。

22、 定义 1.13 令X是一个非空的集合，H是一个由函数f：XR组成的，内积由式定义以及范数由f=Dff定义的Hilbert空间。称H是一个再生核Hilbert空间,如果存在K：XXR满足如下性质 K具有再生性，即对fH，有 (fK(x,)=f(x) (1.64) 特别地 (K(x,)K(,z)=K(x,z) (1.65) K张成空间H，即 H=spanK(x,)|xX (1.66) 其中A表示集合A的闭包。 若函数K是Mercer核，则对cR，有 mCCK(x,xijii,jlj)=CiCjF(xi)F(xj)=i,jl2CF(x)iii0 因此，K一定是一个正定核。因为Mercer是正定的，

23、所以它是再生核。 4 核函数的构造 根据正定核的等价定义，我们可以从简单的核来构造复杂的核。 定理 1.8 设K3(q,q)是RR上的核。若q(x)是从XR到R的映射，则llnlK(x,z)=K3(q(x),q(z)是RnRn上的核。特别地，若nn矩阵B是半正定的，则K(x,z)=xTBz是RnRn的核。 证明： 任取x1,x2,L,xlX，则K(x,z)=K3(q(x),q(z)相应的Gram矩阵为 l (K(xi,xj)li,j=1=(K3(q(xi),q(xj)i,j=1 (1.67) 记q(xt)=qt，t=1,2,K,l，则有 l (K(xi,xj)li,j=1=(K3(qi,qj)

24、i,j=1 (1.68) 由K3(q,q)是RR上的正定核可知：上式右端矩阵是半正定的。从而左端矩阵半正定。所以K(x,z)=K3(q(x),q(z)是正定核。 当B为半正定矩阵时，它可分解为 B=VLV (1.69) 定义RR上的核K3(q,q)=(q,q)，令q(x)=llllTLVx，则有 K(x,z)=K3(q(x),q(z)=q(x)Tq(z)=xTVTLLVz=xTBz0 (1.70) 从而K(x,z)=xTBz是正定核。 定理 1.9 若f()是定义在XR上的实值函数，则K(x,z)=f(x)f(z)是正定核。 证明： 只需把双线性形式重写如下 naaii=1j=1lljK(xi

25、,xj)=aiajf(xi）f(xj) i=1j=1lll =ai=1lif(xi)ajf(xj) j=1l =(ai=1if(xi)20 (1.71) n 定理 1.10 设K1和K2是XX上的核，XR。设常数a0，则下面的函数均是核： K(x,z)=K1(x,z)+K2(x,z) (1.72) K(x,z)=aK1(x,z) (1.73) K(x,z)=K1(x,z)K2(x,z) (1.74) 证明: 对给定的一个有限集合x1,x2,L,xl，令K1和K2分别是K1和K2相对于这个集合的Gram矩阵。 对aR,有 laT(K1+K2)a=aTK1a+aTK2a0 (1.75) 所以K1+

26、K2是半正定的，因而K1+K2是核函数。 aTaK1a=aaTK1a0aK1是核函数。 设K为K(x,z)=K1(x,z)K2(x,z)对应于x1,x2,L,xl的Gram矩阵，则K的元素是K1和K2对应元素的乘积 K=K1oK2 (1.76) 现证明K是半正定矩阵。令K1=CTC,K2=DTD，则 T xT(K1oK2)x=tr(diagx)K1(diagx)K2 =tr(diagx)CTC(diagx)DTD =trD(diagx)CTC(diagx)DT =trC(diagx)DC(diagx)D 0 (1.77) 定理 1.11 设K(x,z)是XX上的核。又设p(x)是系数全为正数的

27、多项式。则下面的函数均是核。 K(x,z)=p(K1(x,z) (1.78) K(x,z)=exp(K1(x,z) (1.79) TTTx-z K(x,z)=exp(-) (1.80) 2证明： 记系数全为正数的q阶多项式为p(x)=aqx+L+a1x+a0，则有 K(x,z)=p(K1(x,z)=aqK1(x,z)+L+a1K1(x,z)+a0 (1.81) 由定理1.10知结论成立。 由于指数函数可以用多项式无限逼近，所以exp(K1(x,z)是核函数的极限。再注意到核函数是闭集，便知结论成立。 qq2 由于 exp(-x-z2s2)=exp(-x2s2)exp(-z2s22(xz)exp(2) (1.82) s由定理1.9知，上式右端前两个因子构成一个正定核。由定理1.8知，(xz)是一个正定核。从结论可知：第三个因子也是一个正定核。由定理1.10的结论，便知结论成立。