《机器学习——核函数讲义》由会员分享，可在线阅读，更多相关《机器学习——核函数讲义（16页珍藏版）》请在金锄头文库上搜索。
1、第一章核函数1多项式空间和多项式核函数定义核或正定核设X是Rn中的一个子集，称定义在XX上的函数K(x,z)是核函数，如果存在一个从X到Hilbert空间H的映射：x(X)GH(1.1)(1.2)(1.3)使得对任意的X,zGX，K(X,z)=(X)(z)定义1.2都成立。其中()表示Hilbert空间H中的内积。阶多项式)设x(x,x,x)tGRn，则称乘积xx12nj1j2为x的一个d阶多项式，其中j,j,，jG1,2,，n。12d1.有序齐次多项式空间考虑2维空间中(xgRn)的模式x(x,x)t，其所有的2阶单项式为12x2，x2，xx，xx121221注意，在表达式(1.3)中，我们
2、把xx和xx看成两个不同的单项式，所以称式(1.3)1221中的单项式为有序单项式。这4个有序单项式张成的是一个4维特征空间，称为2阶有序齐次多项式空间，记为H。相应地可建立从原空间R2到多项式空间H的非线性映射C:x(x,x)TC(x)=(x2,x2,xx,xx)TGH(1.4)2122121221同理，从Rn到d阶有序齐次多项式空间H的映射可表示为C:x(x,x,x)TC(x)(xxxIj,j，,jg1,2,n)TgH(1.5)d12ndj1j2jd12d这样的有序单项式xxx的个数为nd，即多项式空间H的维数nnd。如果j1j2jdH在H中进行内积运算C(x)C(z)，当n和d都不太小时
3、，多项式空间H的维数nndddH会相当大。如当n200，d5时，维数可达到上亿维。显然，在多项式空间H中直接进行内积运算将会引起“维数灾难”问题，那么，如何处理这个问题呢？我们先来考查nd2的情况，计算多项式空间H中两个向量的内积(c(x)C(z)=x2z2+x2z2+xxzz+xxzz(xz)2(1.6)22112212122121若定义函数(1.7)则有(C(x)-C(z)=，(x,z)1.8)22即维多项式空间H上的向量内积可以转化为原始维空间上的向量内积的平方。对于一般的从Rn到d阶有序多项式空间H的映射(1.5)也有类似的结论。定理1.1考虑由式(1.5)定义的从Rn到多项式空间H的
4、映射C(x)，则在空间Hd上的内积(C(x)C(z)可表为dd(C(x)C(z)=K(x,z)(1.9)dd其中K(x,z)=(xz)d(1.10)证明：直接计算可得(C(x)C(z)=工工xxzzddj1jdj1jd=1jd=1=为xz为xzj1j1jdjd=1jd=1=(为xz)d=(xz)d(1.11)jjj=1上述定理表明，我们并不需要在高维的多项式空间H中直接做内积运算(C(x)C(z)，dd而利用式(给出的输入空间Rn上的二元函数K(x,z)来计算高维多项式空间中的内积。2有.序多项式空间在式()定义的映射中，多项式空间H的分量由所有的d阶有序单项式组成。如果把该多项式空间的分量扩
5、充为所有不超过d阶的有序单项式，便得到从Rn到有序多项式空间的映射CdCd：x=(叫叫，叫)TTCd(x)=(叫叫，dx.xj，dx1，叫1jj2jd12,讪(1.12)对于这个映射，我们有如下的定理：定理1.2考虑有式(1.12)定义的从Rn到多项式空间H的映射C，则空间H上的d内积(C(x)C(z)可表为空间Rn上的内积(xz)的函数(xz)+1)d，即若定义两个变量dd(1.13)(1.14)2x,1)T(1.15)2x和z的函数K(x,z)，(xz)+1)d则有(C(x)C(z)，K(x,z)dd上述有序多项式空间的一个简单的例子是C:x，(x,x)TC(x)，(x2,x2,xx,xx
6、,2x,212212122113无序多项式空间如果我们把式()中的xx和xx看作相同的单项式，那么我们就可以把从1221R2到4维多项式空间H的映射(1.4)简化为从R2到3维多项式空间的映射(xx)T(x2,x2,xx)T(1.16)121212将映射(1.16)调整为(x)，(x,x)，(x2,x2,2xx)(1.17)22121212则相应的多项式空间称为2阶无序多项式空间，并且有(x)(z)，(xz)2(1.18)22对式(1.5)所示的变换C(x)按下述方式操作：把C(x)中次序不同但因子相同的各dd分量合并为一个分量，并在该分量前增加一个系数，这个系数取为相应次序不同但因子相同的分
7、量在C(x)中出现次数的平方根。这样得到的从Rn到d阶无序多项式空间的变换d(x)仍满足关系式d(x)(z)，K(x,z)(1.19)dd其中K(x,z)，(xz)d(1.20)根据定义1.1，我们称(1.13)和(1.20)分别为d阶多项式核函数和d阶齐次多项式核函数。比较式(1.4)定义的变换C(x)和式(1.17)定义的(x)可以发现，它们所映射到22的多项式空间是不同的。前者是一个4维多项式空间，后者为一个3维多项式空间。但是内积是相同的，它们都可以表示为内积的函数,(x,z)=(xz)2。这说明：多项式空间不是由核函数唯一确定的。核半正定矩阵的特征展开给定向量集合X=x,x,x，其中
8、xeRn,i=1,2,.,l。设,(x,z)是XX上12li的对称函数，我们定义G=K(x,x),i,j=l,2,，l(1.21)ijij则称G=(G)是,(x,z)关于X的Gram矩阵。我们首先要研究的问题是：当Gram矩阵Gij满足什么条件时，函数K(,)是一个核函数。定义1.2(矩阵算子)定义在R1上的矩阵算子G:对u=(u,u,u)teR1，Gu12l的分量由下式确定Gu二K(x,x)u,i=1,2,1(1.22)iijjj=1定义1.3(特征值和特征向量)考虑定义1.2给出的矩阵算子G。称九eR为它的特征值，并称v为相应的特征向量，如果Gv=九v且v工0(1.23)定义1.4(半正定
9、性)考虑定义1.2给出的矩阵算子G。称它是半正定的，如果对Vu=(u,u,u)TeR1，有121uTGu二K(x,x)uu0(1.24)ijiji,j=1引理1.1若定义1.2给出的矩阵算子G是半正定的，则存在着1个非负特征值九和t互相正交的单位特征向量v，使得tK(x,x)=九vvi,j=1,2.,m(1.25)ijttitjt=1证明：由于G是对称的，所以存在着正交矩阵V=(v,v,v)和对角矩阵121A=diag(九，九,九)，使得121(1.26)这里v(v,v,v)T是矩阵G的第t个特征向量，它对应的特征值是九。因为G是半tt1t2tlt正定的，所以所有特征值均为非负数。于是由(1.
10、26)推知K(x,x),v九v二,入vv(127)ijtittjttitjt1t1引理1.2若引理1.1的结论成立，则存在着从X到Ri的映射，使得K(x,x)(x)(x)i,j1,2,i(1.28)ijij其中()是特征空间Ri的内积。因而K(,)是一个核函数。证明：定义映射：x(x)=(入v,入v,，入v)TRl(1.29)ii11i22iiii直接验证可知引理1.2成立。引理1.3若引理1.2的结论成立，则矩阵G是半正定的。证明：设G不是半正定的，则一定存在着与一个负特征值九相对应的单位特征向量sv。定义Rl中的向量zsz=(x),(x),，(x)v(1.30)12is则有00是矩阵tG=
11、(K(x,x)i(1.33)iji,j=1的特征值，v=(v,v,，v)T为对应于X的特征向量，也等价于K(x,z)是一个核函数,tt1t2tit即K(x,x)=(x)(x),其中映射由式(1.29)定义。ijij2半正定积分算子的特征展开设输入集合为Rn中的紧集X，并设K(x,z)是XX的连续对称函数。我们要研究的问题是，当K(x,z)满足什么条件时，它是一个核函数。定义1.5(积分算子T)定义积分算子T为按下式确定的在L(x)上的积分算子KK2TfTf()J(,z)f(z)dz,f&L(x)(1.34)KK2X定义1.6(特征值和特征函数)考虑定义1.5给出的积分算子T，称九为它的特征K值
12、，*为相应的特征函数，如果T*冷(1.35)K定义1.7(半正定性)考虑定义1.5给出的积分算子T。称它是半正定的，如果对K,fgL(x)，有2JK(x,z)f(x)f(z)dxdz0(1.36)XX引理1.4若定义1.5给出的积分算子T是半正定的，则存在着可数个非负特征值九Kt和相应的互相正交的单位特征函数*(x)，使得K(,)可表示为XX上的一致收敛的级数tK(x,z)为九*(x)*(z)(1.37)tttt1弓I理1.5若引理1.4的结论成立，则存在着XgRn到Hilbert空间l的映射，使得2K(x,z)(x)(z)，x,zgX(1.38)其中()是l上的内积。因而K(,)是一个核函数
13、。2证明：定义映射:x(x)(九*(x),九*(x),)t(1.39)1122则可验证引理1.5成立。引理1.6若引理1.5的结论成立则积分算子T是半正定的。k定理1.4(Mercer定理)令X是R”上的一个紧集，K(x,z)是XX上的连续实值对称函数。则由定义1.5给出的积分算子T半正定kJK(x,z)f(x)f(z)dxdz0，fgL(x)(1.40)2X，X等价于K(-,)可表示为X,X的一致收敛序列K(x,z)=为甲(x)叩(z)(1.41)ttti-1其中0是T的特征值，9gL(x)是对应的特征函数。它也等价于K(x,z)是一个tkt2t核函数K(x,z)=(x)(z)(1.42)其中映射由式(1.39)定义，而()是Hilbert空间l上的内积。2定义1.8(Mercer核)称函数
