1、機器學習-核函數基本概念1多項式空間和多項式核函數定義(核或正定核)設X是Rn中的一個子集，稱定義在XX上的函數(x,z)是核函數，如果存在一個從X到Hilbert空間H的映射:x(x)H使得對任意的x,zX，(x,z)(x)(z)都成立。其中()表示Hilbert空間H中的內積。定義(d階多項式)設x(xi，x2，,xn)TRn,則稱乘積兇讓犯2仄兒為x的一個d階多項式，其中j1,j2,jd1,2,n。1.有序齊次多項式空間考慮2維空間中(xRn)的模式x(x1,x2)T，其所有的2階單項式為x12，x22，x1x2，x2x1注意，在表達式中，我們把xix2和x2xi看成兩個不同的單項式，所

2、以稱式()中的單項式為有序單項式。這4個有序單項式張成的是一個4維特征空間，稱為2階有序齊次多2項式空間，記為H。相應地可建立從原空間R到多項式空間H的非線性映射C2:x(x1,x2)TC2(x)(x12,x22,x1x2,x2x1)TH同理，從Rn到d階有序齊次多項式空間H的映射可表示為Cd:x(x1,x2,xn)TCd(x)(xj1xj2xjd|j1,j2,jd1,2,n)TH這樣的有序單項式xj1xj2xjd的個數為nd，即多項式空間H的維數nHnd。如果在H中進行內積運算Cd(x)Cd(z)，當n和d都不太小時，多項式空間H的維數nHnd會相當大。如當n200，d5時，維數可達到上億維

3、。顯然，在多項式空間H中直接進行內積運算將會引起“維數災難”問題，那么，如何處理這個問題呢？我們先來考查nd2的情況，計算多項式空間H中兩個向量的內積22222(C2(x)C2(z)x12z12x22z22x1x2z1z2x2x1z2z1(xz)2若定義函數2(x,z)(xz)則有(C2(x)C2(z)(x,z)即4維多項式空間H上的向量內積可以轉化為原始2維空間上的向量內積的平方。對于一般的從Rn到d階有序多項式空間H的映射()也有類似的結論。定理考慮由式()定義的從Rn到多項式空間H的映射Cd(x),則在空間H上的(Cd (x) Cd(z)(x,z)d(x, z) (x z)內積(Cd(x

4、)Cd(z)可表為其中證明：直接計算可得nn(Cd(x)Cd(z)立丁落卜j11jd1岡1jl 1zjixjd zjdjd 1ndd(xjzj)(xz)j1上述定理表明，我們并不需要在高維的多項式空間H中直接做內積運算(Cd(x) Cd(z),而利用式(給出的輸入空間Rn上的二元函數(x,z)來計算高維多項式空間中的內積。2.有序多項式空間在式()定義的映射中，多項式空間H的分量由所有的d階有序單項式組成。如果把該多項式空間的分量擴充為所有不超過d階的有序單項式，便得到從Rn到有序多項式空間的映射CdCd：x(岡1,風，風)TCd(x)(風1xjd，d岡1xjd，,d岡，dxn,1|j1,j2

5、,jd1,2,r)T對于這個映射，我們有如下的定理：定理考慮有式()定義的從Rn到多項式空間H的映射Cd,則空間H上的內積(Cd(x)Cd(z)可表為空間Rn上的內積(xz)的函數(xz)1)d,即若定義兩個變量x和z的函數(x,z)(xz)1)d則有(Cd(x)Cd(z)(x,z)上述有序多項式空間的一個簡單的例子是T22TC2：x(xi,x2)C2(x)(xi,x2,xix2,x2xi,&岡，&x2,1)3.無序多項式空間2如果我們把式()中的xix2和x2xi看作相同的單項式，那么我們就可以把從R到4維多項式空間H的映射()簡化為從R2到3維多項式空間的映射(xix2)T(x2,x2,x

6、ix2)T將映射()調整為2(x)2(xi,x2)(x2，x2,v2xix2)則相應的多項式空間稱為2階無序多項式空間，并且有(2(x)2(z)(xz)2對式()所示的變換Cd(x)按下述方式操作：把Cd(x)中次序不同但因子相同的各分量合并為一個分量，并在該分量前增加一個系數，這個系數取為相應次序不同但因子相同的分量在Cd(x)中出現次數的平方根。這樣得到的從Rn到d階無序多項式空間的變換d(x)仍滿足關系式(d(x)d(z)(x,z)其中(x,z)(xz)d根據定義，我們稱()和()分別為d階多項式核函數和d階齊次多項式核函數。比較式()定義的變換C2(x)和式()定義的2(x)可以發現，

7、它們所映射到的多項式空間是不同的。前者是一個4維多項式空間，后者為一個3維多項式空間。但是內積是相同的，它們都可以表示為內積的函數(x,z)(xz)2。這說明：多項式空間不是由核函數唯一確定的。2Mercer核1.半正定矩陣的特征展開給定向量集合Xxi,X2,x,其中XiRn,i1,2,l。設(x,z)是XX上的對稱函數，我們定義GijK(xi,xj),i,j1,2,l則稱G(Gj)是(x,z)關于X的Gram矩陣。我們首先要研究的問題是：當Gram矩陣G滿足什么條件時，函數K(,)是一個核函數。定義(矩陣算子)定義在Rl上的矩陣算子G：對u(u1,u2,ul)TRl，Gu的分量由下式確定lG

8、uiK(xi,xj)uj,i1,2,lj1定義(特征值和特征向量)考慮定義給出的矩陣算子G。稱R為它的特征值，并稱v為相應的特征向量，如果Gvv且v0定義(半正定性)考慮定義給出的矩陣算子G。稱它是半正定的，如果對u(u1,u2,ul)TRl，有luTGuK(xi,xj)uiuj0i,j1引理若定義給出的矩陣算子G是半正定的，則存在著l個非負特征值t和互相正交的單位特征向量vt，使得lK(xi,xj)tvtivtj,i,j1,2,K,mt1證明：由于G是對稱的，所以存在著正交矩陣V(v1,v2,vl)和對角矩陣diag(1,2,l)，使得GVVT這里vt(vt1,vt2,vtl)T是矩陣G的第

9、t個特征向量，它對應的特征值是t。因為G是半正定的，所以所有特征值均為非負數。于是由()推知lK(xi , xj )vtit1lt vtjtvti vtjt1引理若引理的結論成立，則存在著從X到Rl的映射，使得2i)(為)(Xj),i,j1,2,l其中()是特征空間Rl的內積。因而K(,)是一個核函數。證明：定義映射:X(Xi)(.1%,.2v2i,lvli)TRl直接驗證可知引理成立。引理若引理的結論成立，則矩陣G是半正定的。證明：設G不是半正定的，則一定存在著與一個負特征值s相對應的單位特征向量vs。定義Rl中的向量zz(Xi),(X2),(xl)vs則有0IIZI2vS(Xi),(x)T

10、(Xi),(xl)vsvSKvss|vs|2S顯然，這與s是負特征值相矛盾。因此K必須是半正定的。定理設X是有限集合XX1,x2,Xl,K(x,z)是定義在XX上的對稱函數。則由定義給出的矩陣算子G半正定，等價于K(,)可表示為lK(Xi,Xj)tvtivtjt1其中t0是矩陣G(K(Xi,Xj)i,ji的特征值，vt(vti,vt2,vtl)T為對應于t的特征向量，也等價于K(x,z)是一個核函數，即K(Xi,Xj)(Xi)(Xj),其中映射由式()定義。2.半正定積分算子的特征展開設輸入集合為Rn中的緊集X,并設K(x,z)是XX的連續對稱函數。我們要研究的問題是，當K(x,z)滿足什么條

11、件時，它是一個核函數。定義(積分算子Tk)定義積分算子Tk為按下式確定的在L2(x)上的積分算子TKfTk”)(，z)f(z)dz,fL2(x)X定義(特征值和特征函數)考慮定義給出的積分算子TK，稱為它的特征值，為相應的特征函數，如果Tk定義(半正定性)考慮定義給出的積分算子Tk。稱它是半正定的，如果對fL2(x),有K(x,z)f(x)f(z)dxdz0XX引理若定義給出的積分算子Tk是半正定的，則存在著可數個非負特征值t和相應的互相正交的單位特征函數t(x),使得K(,)可表示為XX上的一致收斂的級數K(x,z)tt(x)t(z)t1引理若引理的結論成立，則存在著XRn到Hilbert空

12、間l2的映射，使得K(x,z)(x)(z),x,zX其中()是l2上的內積。因而K(,)是一個核函數。證明：定義映射:x(x)(,11(x),-122(x),)則可驗證引理成立。引理若引理的結論成立則積分算子Tk是半正定的。定理(Mercer定理)令X是Rn上的一個緊集，K(x,z)是XX上的連續實值對稱函數。則由定義給出的積分算子Tk半正定K(x,z)f(x)f(z)dxdz0,fL2(x)XX等價于K(,)可表示為XX的一致收斂序列K(x,z)tt(x)t(z)i1其中。是Tk的特征值,L2 (x)是對應t的特征函數。它也等價于K (x, z)是一個核函數K(x,z)(x)(z)其中映射由

13、式()定義，而()是Hilbert空間12上的內積。定義(Mercer核)稱函數K(x,z)為Mercer核，如果K(x,z)是定義在XX上的連續對稱函數，其中X是Rn的緊集，且由定義給出的積分算子是半正定的。定理設X為Rn上的緊集，(x,z)是XX上的連續對稱函數，則積分算子Tk半正定的充要條件是(x,z)關于任意的x1,x2,xlX的Gram矩陣半正定。3正定核定理設X是Rn的子集。若(x,z)是定義在XX上的正定核，則對Xi,X2,XiX,函數(x,z)關于Xi,X2,Xi的Gram矩陣都是半正定的。證明：(x,z)是定義在XX上的正定核，因此存在著從射，使得X到Hilbert空間H的映

14、K(x,z)(x)(z)任取x1,X2,XiX，構造(,)關于X1,X2,Xi的Gram矩陣(j)i,j1(K(Xi,Xj)l.j1。顯然，根據由式()可以斷言，對Ci,C2,ClR,我們CiCj(xi,xj)CiCj(x)i.ji,j(Xj)(Ci(Xi)Cj(Xj)2Cj(x)這表明(x,z)關于Xi,X2,Xl的Gram矩陣是半正定的。引理若集合S由所有的下列元素組成lf()i(,Xi)i1其中l為任意的正整數,nVVV1,2,lR,X1,X2,XlX，則S為一個向量空間。S構成一個向量空間。證明：由于集合S中的元素對于加法和數乘封閉，所以引理若S中的兩元素定義運算并由此定義在SS上的函

15、數(f,g)f矩陣都是半正定的。證明：由flfi.j1j(Xi,Xj)若任意選取f1,f2,flS陣。由（）可知對這表明Gram矩B$(fifj)i.j引理證明:lf()ii1(,Xi)和g()g,則該函數關于。知:(,Xj)f1,f2,(Xi,Xj)fl的Gram記函數相應的Gram矩陣為（fi,C1R有:lCiCj(fii.j11是半正定的。fj)l(Cifi)i1在引理中定義的運算具有如下性質:對于f,g2(ff)任取f,gS,則關于f,g的Gram矩陣為fj)i.j1Cjfj)S,(g顯然它是對稱矩g)(f,f)(g,f)(f,g)(g,g)因為（f,g）（g,f）,所以由引理可知：矩

16、陣（）是半正定的，其行列式非負。由此可(f,f)(g,g)(f,g)(g,f)0引理引理中定義的運算(f,g)2(f,f)，、(g,g)是S上的內積運算，因而可記為(ff)(gg)證明：直接驗證可知該運算具有內積運算應滿足的如下性質：對(fg)f,g,hS和c,dR有ff0f0ff0(cfdg)hc(fh)d(gh)fggf只需證明：若ff0,則有f0。事實上，若lf()i(,Xi)i1則按運算規則()知，對xX,有(,X)ff(X)由于2(,X)f|(,x)(,x)(ff)(x,x)(ff)所以_2_f(x)(,x)(ff)此式意味著當ff0時，對x,都有f(x)0,即f(x)為零元素。引理

17、若H是引理中的集合S在引理中定義的內積運算意義下的閉包，則H是一個Hilbert空間。定理設(x,z)是定義在XX上的對稱函數。若對x1,x2,xlX,函數(x,z)關于x1，x2,xi的Gram矩陣都是半正定的，則(x,z)是一個正定核。證明：定義映射:x(,x)由引理和知，該映射是從X到某一Hilbert空間的映射。由式()可得到(,x)(,z)(x,z)由引理知引理中定義的運算是內積運算。利用式()可得到(x,z)(x)(z)由定義知(x,z)是正定核。定義(正定核的等價定義)設X是Rn的子集。稱定義在XX上的對稱函數(x,z)為一個正定核，如果對Xi,X2,XiX,(,)相對于Xi,X

18、2,Xi的Gram矩陣都是半正定的。f定義的Hilbert 空間。稱H定義(再生核的Hilbert空間)令X是一個非空的集合，H是一個由函數f：XR組成的，內積由式()定義以及范數由|f|是一個再生核Hilbert空間(簡稱RKHS，如果存在：XXR滿足如下性質(1) K具有再生性，即對fH,有(f(x,)f(X)特別地(X,)(,z)(X,z)(2) K張成空間H,即Hspan(x,)|xX其中A表示集合A的閉包。若函數K是Mercer核，則對cRm,有1 i2Gg(x,Xj)C(x)(Xj)Ci(Xi)0i.ji.ji因此，K一定是一個正定核。因為Mercer是正定的，所以它是再生核。4核

19、函數的構造根據正定核的等價定義，我們可以從簡單的核來構造復雜的核。定理設3(,)是RlR1上的核。若(X)是從XRn到R的映射，則(x,z)3(X),(z)是RnRn上的核。特別地，若nn矩陣B是半正定的，則(x,z)xTBz是RnRn的核。證明：任取x1,x2,xlX,則(x,z)3(x),(z)相應的Gram矩陣為(Xi,Xj)l,ji(3(Xi),(Xj)i,j1記(Xt)t,t1,2,l,則有(Xi,Xj)i,j1(3(i,j)i,j1由3(,)是RlRl上的正定核可知：上式右端矩陣是半正定的。從而左端矩陣半正定。所以(x,z)3(x),(z是正定核。當B為半正定矩陣時，它可分解為BVTV(x,z)3( (x), (z)定義RlRl上的核3(,)(,)，令(x)Vx，則有(x)T(z)xTVT.VzxTBz0從而(x,z)xTBz是正定核。定理若f ()是定義在XRn上的實值函數，則(x,z) f (x) f(z)是正定核。證明:只需把雙線性形式重寫如下(xi,xj)j f(xi) f (xj)j f(xj)llif(xi)i1j1l(if(xi)20i1定理設K1和K2是X X上的核，XRn 。設常數a 0，則下面的函數均是核:(1) (x,z)K1(x,z)K2(x,z)(2) (x,z)aK(x,z)(3) (x,z)K1(x,