機器學習-核函數(shù)根本概念§1多項式空間和多項式核函數(shù)(核或正定核)設是中的一個子集，稱定義在上的函數(shù)是核函數(shù)，如果存在一個從到Hilbert空間的映射()使得對任意的，()都成立。其中表示Hilbert空間中的內(nèi)積。定義〔d階多項式〕設，那么稱乘積為的一個d階多項式，其中。有序齊次多項式空間考慮2維空間中〔〕的模式，其所有的2階單項式為，，，(1.3)注意，在表達式(1.3)中，我們把和看成兩個不同的單項式，所以稱式〔1.3〕中的單項式為有序單項式。這4個有序單項式張成的是一個4維特征空間，稱為2階有序齊次多項式空間，記為。相應地可建立從原空間到多項式空間的非線性映射(1.4)同理，從到階有序齊次多項式空間的映射可表示為(1.5)這樣的有序單項式的個數(shù)為，即多項式空間的維數(shù)。如果在中進行內(nèi)積運算，當和都不太小時，多項式空間的維數(shù)會相當大。如當，時，維數(shù)可到達上億維。顯然，在多項式空間中直接進行內(nèi)積運算將會引起“維數(shù)災難”問題，那么，如何處理這個問題呢？我們先來考查的情況，計算多項式空間中兩個向量的內(nèi)積(1.6)假設定義函數(shù)(1.7)那么有(1.8)即4維多項式空間上的向量內(nèi)積可以轉(zhuǎn)化為原始2維空間上的向量內(nèi)積的平方。對于一般的從到階有序多項式空間的映射〔1.5〕也有類似的結論?？紤]由式〔1.5〕定義的從到多項式空間的映射，那么在空間上的內(nèi)積可表為(1.9)其中(1.10)證明：直接計算可得(1.11)上述定理說明，我們并不需要在高維的多項式空間中直接做內(nèi)積運算，而利用式〔1.10)給出的輸入空間上的二元函數(shù)來計算高維多項式空間中的內(nèi)積。2.有序多項式空間在式〔1.5〕定義的映射中，多項式空間的分量由所有的階有序單項式組成。如果把該多項式空間的分量擴充為所有不超過階的有序單項式，便得到從到有序多項式空間的映射(1.12)對于這個映射，我們有如下的定理：定理1.2考慮有式〔1.12〕定義的從到多項式空間的映射，那么空間上的內(nèi)積可表為空間上的內(nèi)積的函數(shù)，即假設定義兩個變量和的函數(shù)(1.13)那么有(1.14)上述有序多項式空間的一個簡單的例子是(1.15)3.無序多項式空間如果我們把式〔1.4〕中的和看作相同的單項式，那么我們就可以把從到4維多項式空間的映射〔1.4〕簡化為從到3維多項式空間的映射(1.16)將映射〔1.16〕調(diào)整為(1.17)那么相應的多項式空間稱為2階無序多項式空間，并且有(1.18)對式〔1.5〕所示的變換按下述方式操作：把中次序不同但因子相同的各分量合并為一個分量，并在該分量前增加一個系數(shù)，這個系數(shù)取為相應次序不同但因子相同的分量在中出現(xiàn)次數(shù)的平方根。這樣得到的從到階無序多項式空間的變換仍滿足關系式(1.19)其中(1.20)根據(jù)定義1.1，我們稱〔1.13〕和〔1.20〕分別為階多項式核函數(shù)和階齊次多項式核函數(shù)。比擬式〔1.4〕定義的變換和式〔1.17〕定義的可以發(fā)現(xiàn)，它們所映射到的多項式空間是不同的。前者是一個4維多項式空間，后者為一個3維多項式空間。但是內(nèi)積是相同的，它們都可以表示為內(nèi)積的函數(shù)。這說明：多項式空間不是由核函數(shù)唯一確定的。§2Mercer核1.半正定矩陣的特征展開給定向量集合，其中。設是上的對稱函數(shù)，我們定義(1.21)那么稱是關于的Gram矩陣。我們首先要研究的問題是：當Gram矩陣滿足什么條件時，函數(shù)是一個核函數(shù)。〔矩陣算子〕定義在上的矩陣算子：對，的分量由下式確定(1.22)定義1.3〔特征值和特征向量〕。稱為它的特征值，并稱為相應的特征向量，如果且(1.23)定義〔半正定性〕。稱它是半正定的，如果對，有(1.24)假設定義是半正定的，那么存在著個非負特征值和互相正交的單位特征向量，使得,5)證明：由于是對稱的，所以存在著正交矩陣和對角矩陣，使得6)這里是矩陣的第t個特征向量，它對應的特征值是。因為是半正定的，所以所有特征值均為非負數(shù)。于是由〔6〕推知7)引理1.2假設引理1.1的結論成立，那么存在著從到的映射，使得8)其中是特征空間的內(nèi)積。因而是一個核函數(shù)。證明：定義映射(1.29)直接驗證可知引理1.2成立。引理1.3假設引理1.2的結論成立，那么矩陣是半正定的。證明：設不是半正定的，那么一定存在著與一個負特征值相對應的單位特征向量。定義中的向量z(1.30)那么有(1.31)顯然，這與是負特征值相矛盾。因此K必須是半正定的。設是有限集合，是定義在半正定，等價于可表示為(1.32)其中是矩陣(1.33)的特征值，為對應于的特征向量，也等價于是一個核函數(shù)，即，其中映射由式〔1.29〕定義。2.半正定積分算子的特征展開設輸入集合為中的緊集，并設是的連續(xù)對稱函數(shù)。我們要研究的問題是，當滿足什么條件時，它是一個核函數(shù)?！卜e分算子〕定義積分算子為按下式確定的在上的積分算子(1.34)〔特征值和特征函數(shù)，稱為它的特征值，為相應的特征函數(shù)，如果(1.35)定義1.7〔半正定性。稱它是半正定的，如果對，有(1.36)引理1.4假設定義是半正定的，那么存在著可數(shù)個非負特征值和相應的互相正交的單位特征函數(shù)，使得可表示為上的一致收斂的級數(shù)(1.37)假設引理1.4的結論成立，那么存在著到Hilbert空間的映射，使得，(1.38)其中是上的內(nèi)積。因而是一個核函數(shù)。證明：定義映射(1.39)那么可驗證引理1.5成立。引理那么積分算子是半正定的?！睲ercer定理〕令是上的一個緊集，是半正定，(1.40)等價于可表示為的一致收斂序列(1.41)其中是的特征值，是對應的特征函數(shù)。它也等價于是一個核函數(shù)(1.42)其中映射由式〔〕定義，而是Hilbert空間上的內(nèi)積。〔Mercer核〕稱函數(shù)為Mercer核，如果是定義在上的連續(xù)對稱函數(shù)，其中是的緊集，且由定義1.5給出的積分算子是半正定的。設為上的緊集，是上的連續(xù)對稱函數(shù)，那么積分算子半正定的充要條件是關于任意的的Gram矩陣半正定?！?正定核定理1.6設是的子集。假設是定義在上的正定核，那么對，函數(shù)關于的Gram矩陣都是半正定的。證明：是定義在上的正定核，因此存在著從X到Hilbert空間H的映射，使得(1.43)任取，構造關于的Gram矩陣。顯然，根據(jù)由式〔1.43〕可以斷言，對,我們有(1.44)這說明關于的Gram矩陣是半正定的。假設集合S由所有的以下元素組成(1.45)其中為任意的正整數(shù)，,,那么S為一個向量空間。證明：由于集合S中的元素對于加法和數(shù)乘封閉，所以S構成一個向量空間。假設對S中的兩元素和(1.46)定義運算(1.47)并由此定義在上的函數(shù)，那么該函數(shù)關于的Gram矩陣都是半正定的。證明：由知：假設任意選取，記函數(shù)相應的Gram矩陣為。顯然它是對稱矩陣。由〔1.47〕可知對有：(1.48)這說明Gram矩陣是半正定的。具有如下性質(zhì)：對于，有(1.49)證明：任取,那么關于的Gram矩陣為(1.50)因為可知：0〕是半正定的，其行列式非負。由此可知(1.51)引理1.10是S上的內(nèi)積運算，因而可記為(1.52)證明：直接驗證可知該運算具有內(nèi)積運算應滿足的如下性質(zhì)：對和有(1.53)(1.54)(1.55)(1.56)只需證明：假設，那么有。事實上，假設(1.57)那么按運算規(guī)那么〔1.47〕知，對，有(1.58)由于(1.59)所以(1.60)此式意味著當時，對，都有，即為零元素。假設H是引理1.7中的集合S在引理1.8中定義的內(nèi)積運算意義下的閉包，那么H是一個Hilbert空間。定理1.7設是定義在上的對稱函數(shù)。假設對，函數(shù)關于的Gram矩陣都是半正定的，那么是一個正定核。證明：定義映射(1.61)由引理1.7和1.11知，該映射是從X到某一Hilbert空間的映射。由式〔1.58〕可得到(1.62)是內(nèi)積運算。利用式〔1.61〕可得到(1.63)是正定核?！舱ê说牡葍r定義〕設是的子集。稱定義在上的對稱函數(shù)為一個正定核，如果對，相對于的Gram矩陣都是半正定的?！苍偕说腍ilbert空間〕令是一個非空的集合，是一個由函數(shù)組成的，內(nèi)積由式〔1.47〕定義以及范數(shù)由定義的Hilbert空間。稱是一個再生核Hilbert空間〔簡稱RKHS〕,如果存在滿足如下性質(zhì)具有再生性，即對，有(1.64)特別地(1.65)張成空間，即(1.66)其中表示集合A的閉包。假設函數(shù)是Mercer核，那么對，有因此，一定是一個正定核。因為Mercer是正定的，所以它是再生核。§4核函數(shù)的構造根據(jù)正定核的等價定義，我們可以從簡單的核來構造復雜的核。定理1.8設是上的核。假設是從到的映射，那么是上的核。特別地，假設矩陣B是半正定的，那么是的核。證明：任取，那么相應的Gram矩陣為(1.67)記，，那么有(1.68)由是上的正定核可知：上式右端矩陣是半正定的。從而左端矩陣半正定。所以是正定核。當B為半正定矩陣時，它可分解為(1.69)定義上的核，令，那么有(1.70)從而是正定核。定理1.9假設是定義在上的實值函數(shù)，那么是正定核。證明：只需把雙線性形式重寫如下1)0設和是上的核，。設常數(shù)，那么下面的函數(shù)均是核：〔1〕2)〔2〕3)〔3〕4)證明:對給定的一個有限集合，令和分別是和相對于這個集合的Gram矩陣。對,有5)所以是半正定的，因而是核函數(shù)?！?〕是核函數(shù)。〔3〕設為對應于的Gram矩陣，那么的元素是和對應元素的乘積6)現(xiàn)證明是半正定矩陣。令,，那么7)1設是上的核。又設是系數(shù)全為正數(shù)的多項式。那么下面的函數(shù)均是核。〔1〕8)〔2〕