機(jī)器學(xué)習(xí)核函數(shù)基本概念

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

19、函數(shù)的構(gòu)造根據(jù)正定核的等價(jià)定義，我們可以從簡(jiǎn)單的核來構(gòu)造復(fù)雜的核。定理設(shè)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)相應(yīng)的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是正定核。當(dāng)B為半正定矩陣時(shí)，它可分解為BVTV(x,z)3( (x), (z)定義RlRl上的核3(,)(,)，令(x)Vx，則有(x)T(z)xTVT.VzxTBz0從而(x,z)xTBz是正定核。定理若f ()是定義在XRn上的實(shí)值函數(shù)，則(x,z) f (x) f(z)是正定核。證明:只需把雙線性形式重寫如下(xi,xj)j f(xi) f (xj)j f(xj)llif(xi)i1j1l(if(xi)20i1定理設(shè)K1和K2是X X上的核，XRn 。設(shè)常數(shù)a 0，則下面的函數(shù)均是核:(1) (x,z)K1(x,z)K2(x,z)(2) (x,z)aK(x,z)(3) (x,z)K1(x,