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

機(jī)器學(xué)習(xí)-核函數(shù)基本概念機(jī)器學(xué)習(xí)-核函數(shù)基本概念§1多項(xiàng)式空間和多項(xiàng)式核函數(shù)定義1.1(核或正定核)設(shè)是中的一個(gè)子集，稱定義在上的函數(shù)是核函數(shù)，如果存在一個(gè)從到Hilbert空間的映射(1.1)使得對(duì)任意的，(1.2)都成立。其中表示Hilbert空間中的內(nèi)積。定義1.2（d階多項(xiàng)式）設(shè)，則稱乘積為的一個(gè)d階多項(xiàng)式，其中。有序齊次多項(xiàng)式空間考慮2維空間中（）的模式，其所有的2階單項(xiàng)式為，，，(1.3)注意，在表達(dá)式(1.3)中，我們把和看成兩個(gè)不同的單項(xiàng)式，所以稱式（1.3）中的單項(xiàng)式為有序單項(xiàng)式。這4個(gè)有序單項(xiàng)式張成的是一個(gè)4維特征空間，稱為2階有序齊次多項(xiàng)式空間，記為。相應(yīng)地可建立從原空間到多項(xiàng)式空間的非線性映射(1.4)同理，從到階有序齊次多項(xiàng)式空間的映射可表示為(1.5)這樣的有序單項(xiàng)式的個(gè)數(shù)為，即多項(xiàng)式空間的維數(shù)。如果在中進(jìn)行內(nèi)積運(yùn)算，當(dāng)和都不太小時(shí)，多項(xiàng)式空間的維數(shù)會(huì)相當(dāng)大。如當(dāng)，時(shí)，維數(shù)可達(dá)到上億維。顯然，在多項(xiàng)式空間中直接進(jìn)行內(nèi)積運(yùn)算將會(huì)引起“維數(shù)災(zāi)難”問題，那么，如何處理這個(gè)問題呢？我們先來考查的情況，計(jì)算多項(xiàng)式空間中兩個(gè)向量的內(nèi)積(1.6)若定義函數(shù)取為相應(yīng)次序不同但因子相同的分量在中出現(xiàn)次數(shù)的平方根。這樣得到的從到階無序多項(xiàng)式空間的變換仍滿足關(guān)系式(1.19)其中(1.20)根據(jù)定義1.1，我們稱（1.13）和（1.20）分別為階多項(xiàng)式核函數(shù)和階齊次多項(xiàng)式核函數(shù)。比較式（1.4）定義的變換和式（1.17）定義的可以發(fā)現(xiàn)，它們所映射到的多項(xiàng)式空間是不同的。前者是一個(gè)4維多項(xiàng)式空間，后者為一個(gè)3維多項(xiàng)式空間。但是內(nèi)積是相同的，它們都可以表示為內(nèi)積的函數(shù)。這說明：多項(xiàng)式空間不是由核函數(shù)唯一確定的。§2Mercer核1.半正定矩陣的特征展開給定向量集合，其中。設(shè)是上的對(duì)稱函數(shù)，我們定義(1.21)則稱是關(guān)于的Gram矩陣。我們首先要研究的問題是：當(dāng)Gram矩陣滿足什么條件時(shí)，函數(shù)是一個(gè)核函數(shù)。定義1.2（矩陣算子）定義在上的矩陣算子：對(duì)，的分量由下式確定(1.22)定義1.3（特征值和特征向量）考慮定義1.2給出的矩陣算子。稱為它的特征值，并稱為相應(yīng)的特征向量，如果且(1.23)定義1.4（半正定性）考慮定義1.2給出的矩陣算子。稱它是半正定的，如果對(duì)，有(1.24)引理1.1若定義1.2給出的矩陣算子是半正定的，則存在著個(gè)非負(fù)特征值和互相正交的單位特征向量，使得,(1.25)證明：由于是對(duì)稱的，所以存在著正交矩陣和對(duì)角矩陣，使得(1.26)這里是矩陣的第t個(gè)特征向量，它對(duì)應(yīng)的特征值是。因?yàn)槭前胝ǖ模运刑卣髦稻鶠榉秦?fù)數(shù)。于是由（1.26）推知(1.27)引理1.2若引理1.1的結(jié)論成立，則存在著從到的映射，使得(1.28)其中是特征空間的內(nèi)積。因而是一個(gè)核函數(shù)。證明：定義映射(1.29)直接驗(yàn)證可知引理1.2成立。引理1.3若引理1.2的結(jié)論成立，則矩陣是半正定的。證明：設(shè)不是半正定的，則一定存在著與一個(gè)負(fù)特征值相對(duì)應(yīng)的單位特征向量。定義中的向量z(1.30)則有(1.31)顯然，這與是負(fù)特征值相矛盾。因此K必須是半正定的。定理1.3設(shè)是有限集合，是定義在上的對(duì)稱函數(shù)。則由定義1.2給出的矩陣算子半正定，等價(jià)于可表示為(1.32)其中是矩陣(1.33)的特征值，為對(duì)應(yīng)于的特征向量，也等價(jià)于是一個(gè)核函數(shù)，即，其中映射由式（1.29）定義。2.半正定積分算子的特征展開設(shè)輸入集合為中的緊集，并設(shè)是的連續(xù)對(duì)稱函數(shù)。我們要研究的問題是，當(dāng)滿足什么條件時(shí)，它是一個(gè)核函數(shù)。定義1.5（積分算子）定義積分算子為按下式確定的在上的積分算子(1.34)定義1.6（特征值和特征函數(shù)）考慮定義1.5給出的積分算子，稱為它的特征值，為相應(yīng)的特征函數(shù)，如果(1.35)定義1.7（半正定性）考慮定義1.5給出的積分算子。稱它是半正定的，如果對(duì)，有(1.36)引理1.4若定義1.5給出的積分算子是半正定的，則存在著可數(shù)個(gè)非負(fù)特征值和相應(yīng)的互相正交的單位特征函數(shù)，使得可表示為上的一致收斂的級(jí)數(shù)(1.37)引理1.5若引理1.4的結(jié)論成立，則存在著到Hilbert空間的映射，使得，(1.38)其中是上的內(nèi)積。因而是一個(gè)核函數(shù)。證明：定義映射(1.39)則可驗(yàn)證引理1.5成立。引理1.6若引理1.5的結(jié)論成立則積分算子是半正定的。定理1.4（Mercer定理）令是上的一個(gè)緊集，是上的連續(xù)實(shí)值對(duì)稱函數(shù)。則由定義1.5給出的積分算子半正定，(1.40)等價(jià)于可表示為的一致收斂序列(1.41)其中是的特征值，是對(duì)應(yīng)的特征函數(shù)。它也等價(jià)于是一個(gè)核函數(shù)(1.42)其中映射由式（1.39）定義，而是Hilbert空間上的內(nèi)積。定義1.8（Mercer核）稱函數(shù)為Mercer核，如果是定義在上的連續(xù)對(duì)稱函數(shù)，其中是的緊集，且由定義1.5給出的積分算子是半正定的。定理1.5設(shè)為上的緊集，是上的連續(xù)對(duì)稱函數(shù)，則積分算子半正定的充要條件是關(guān)于任意的的Gram矩陣半正定?！?正定核定理1.6設(shè)是的子集。若是定義在上的正定核，則對(duì)，函數(shù)關(guān)于的Gram矩陣都是半正定的。證明：是定義在上的正定核，因此存在著從X到Hilbert空間H的映射，使得(1.43)任取，構(gòu)造關(guān)于的Gram矩陣。顯然，根據(jù)由式（1.43）可以斷言，對(duì),我們有(1.44)這表明關(guān)于的Gram矩陣是半正定的。引理1.7若集合S由所有的下列元素組成(1.45)其中為任意的正整數(shù)，,,則S為一個(gè)向量空間。證明：由于集合S中的元素對(duì)于加法和數(shù)乘封閉，所以S構(gòu)成一個(gè)向量空間。引理1.8若對(duì)S中的兩元素和(1.46)定義運(yùn)算(1.47)并由此定義在上的函數(shù)，則該函數(shù)關(guān)于的Gram矩陣都是半正定的。證明：由知：若任意選取，記函數(shù)相應(yīng)的Gram矩陣為。顯然它是對(duì)稱矩陣。由（1.47）可知對(duì)有：(1.48)這表明Gram矩陣是半正定的。引理1.9在引理1.8中定義的運(yùn)算具有如下性質(zhì)：對(duì)于，有(1.49)證明：任取,則關(guān)于的Gram矩陣為(1.50)因?yàn)?，所以由引?.8可知：矩陣（1.50）是半正定的，其行列式非負(fù)。由此可知(1.51)引理1.10引理1.8中定義的運(yùn)算是S上的內(nèi)積運(yùn)算，因而可記為(1.52)證明：直接驗(yàn)證可知該運(yùn)算具有內(nèi)積運(yùn)算應(yīng)滿足的如下性質(zhì)：對(duì)和有(1.53)(1.54)(1.55)(1.56)只需證明：若，則有。事實(shí)上，若(1.57)則按運(yùn)算規(guī)則（1.47）知，對(duì)，有(1.58)由于(1.59)所以(1.60)此式意味著當(dāng)時(shí)，對(duì)，都有，即為零元素。引理1.11若H是引理1.7中的集合S在引理1.8中定義的內(nèi)積運(yùn)算意義下的閉包，則H是一個(gè)Hilbert空間。定理1.7設(shè)是定義在上的對(duì)稱函數(shù)。若對(duì)，函數(shù)關(guān)于的Gram矩陣都是半正定的，則是一個(gè)正定核。證明：定義映射(1.61)由引理1.7和1.11知，該映射是從X到某一Hilbert空間的映射。由式（1.58）可得到(1.62)由引理1.10知引理1.8中定義的運(yùn)算是內(nèi)積運(yùn)算。利用式（1.61）可得到(1.63)由定義1.1知是正定核。定義1.12（正定核的等價(jià)定義）設(shè)是的子集。稱定義在上的對(duì)稱函數(shù)為一個(gè)正定核，如果對(duì)，相對(duì)于的Gram矩陣都是半正定的。定義1.13（再生核的Hilbert空間）令是一個(gè)非空的集合，是一個(gè)由函數(shù)組成的，內(nèi)積由式（1.47）定義以及范數(shù)由定義的Hilbert空間。稱是一個(gè)再生核Hilbert空間（簡(jiǎn)稱RKHS）,如果存在滿足如下性質(zhì)具有再生性，即對(duì)，有(1.64)特別地(1.65)張成空間，即(1.66)其中表示集合A的閉包。若函數(shù)是Mercer核，則對(duì)，有因此，一定是一個(gè)正定核。因?yàn)镸ercer是正定的，所以它是再生核?！?核函數(shù)的構(gòu)造根據(jù)正定核的等價(jià)定義，我們可以從簡(jiǎn)單的核來構(gòu)造復(fù)雜的核。定理1.8設(shè)是上的核。若是從到的映射，則是上的核。特別地，若矩陣B是半正定的，則是的核。證明：任取，則相應(yīng)的Gram矩陣為(1.67)記，，則有(1.68)由是上的正定核可知：上式右端矩陣是半正定的。從而左端矩陣半正定。所以是正定核。當(dāng)B為半正定矩陣時(shí)，它可分解為(1.69)定義上的核，令，則有(1.70)從而是正定核。定理1.9若是定義在上的實(shí)值函數(shù)，則是正定核。證明：只需把雙線性形式重寫如下(1.71)定理1.10設(shè)和是上的核，。設(shè)常數(shù)，則下面的函數(shù)均是核：（1）(1.72)（2）(1.73)（3）(1.74)證明:對(duì)給定的一個(gè)有限集合，令和分別是和相對(duì)于這個(gè)集合的Gram矩陣。對(duì),有(1.75)所以是半正定的，因而是核函數(shù)。（2）是核函數(shù)。（3）設(shè)為對(duì)應(yīng)于的Gram矩陣，則的元素是和對(duì)應(yīng)元素的乘積