機(jī)器學(xué)習(xí)——核函數(shù)講義

1、第一章 核函數(shù)§1 多項式空間和多項式核函數(shù)定義 1.1 (核或正定核) 設(shè)是中的一個子集，稱定義在上的函數(shù)是核函數(shù)，如果存在一個從到Hilbert空間的映射 (1.1)使得對任意的， (1.2)都成立。其中表示Hilbert空間中的內(nèi)積。定義1.2 （d階多項式）設(shè)，則稱乘積為的一個d階多項式，其中。1. 有序齊次多項式空間考慮2維空間中（）的模式，其所有的2階單項式為 ， (1.3)注意，在表達(dá)式(1.3)中，我們把和看成兩個不同的單項式，所以稱式（1.3）中的單項式為有序單項式。這4個有序單項式張成的是一個4維特征空間，稱為2階有序齊次多項式空間，記為。相應(yīng)地可建立從原空間到多

2、項式空間的非線性映射 (1.4)同理，從到階有序齊次多項式空間的映射可表示為(1.5)這樣的有序單項式的個數(shù)為，即多項式空間的維數(shù)。如果在中進(jìn)行內(nèi)積運(yùn)算，當(dāng)和都不太小時，多項式空間的維數(shù)會相當(dāng)大。如當(dāng)，時，維數(shù)可達(dá)到上億維。顯然，在多項式空間中直接進(jìn)行內(nèi)積運(yùn)算將會引起“維數(shù)災(zāi)難”問題，那么，如何處理這個問題呢？我們先來考查的情況，計算多項式空間中兩個向量的內(nèi)積 (1.6)若定義函數(shù) (1.7)則有 (1.8)即4維多項式空間上的向量內(nèi)積可以轉(zhuǎn)化為原始2維空間上的向量內(nèi)積的平方。對于一般的從到階有序多項式空間的映射（1.5）也有類似的結(jié)論。 定理1.1 考慮由式（1.5）定義的從到多項式空間的映

3、射，則在空間上的內(nèi)積可表為 (1.9)其中 (1.10) 證明：直接計算可得 (1.11) 上述定理表明，我們并不需要在高維的多項式空間中直接做內(nèi)積運(yùn)算， 而利用式（1.10)給出的輸入空間上的二元函數(shù)來計算高維多項式空間中的內(nèi)積。 2. 有序多項式空間在式（1.5）定義的映射中，多項式空間的分量由所有的階有序單項式組成。如果把該多項式空間的分量擴(kuò)充為所有不超過階的有序單項式，便得到從到有序多項式空間的映射(1.12)對于這個映射，我們有如下的定理：定理1.2 考慮有式（1.12）定義的從到多項式空間的映射，則空間上的內(nèi)積可表為空間上的內(nèi)積的函數(shù)，即若定義兩個變量和的函數(shù) (1.13)則有 (

4、1.14)上述有序多項式空間的一個簡單的例子是(1.15)3. 無序多項式空間 如果我們把式（1.4）中的和看作相同的單項式，那么我們就可以把從到4維多項式空間的映射（1.4）簡化為從到3維多項式空間的映射 (1.16)將映射（1.16）調(diào)整為 (1.17)則相應(yīng)的多項式空間稱為2階無序多項式空間，并且有 (1.18)對式（1.5）所示的變換按下述方式操作：把中次序不同但因子相同的各分量合并為一個分量，并在該分量前增加一個系數(shù)，這個系數(shù)取為相應(yīng)次序不同但因子相同的分量在中出現(xiàn)次數(shù)的平方根。這樣得到的從到階無序多項式空間的變換仍滿足關(guān)系式 (1.19)其中 (1.20) 根據(jù)定義1.1，我們稱（

5、1.13）和（1.20）分別為階多項式核函數(shù)和階齊次多項式核函數(shù)。比較式（1.4）定義的變換和式（1.17）定義的可以發(fā)現(xiàn)，它們所映射到的多項式空間是不同的。前者是一個4維多項式空間，后者為一個3維多項式空間。但是內(nèi)積是相同的，它們都可以表示為內(nèi)積的函數(shù)。這說明：多項式空間不是由核函數(shù)唯一確定的。§2 Mercer 核1.半正定矩陣的特征展開給定向量集合，其中 。設(shè)是上的對稱函數(shù)，我們定義 (1.21)則稱是關(guān)于的Gram矩陣。我們首先要研究的問題是：當(dāng)Gram矩陣滿足什么條件時，函數(shù)是一個核函數(shù)。定義 1.2 （矩陣算子）定義在上的矩陣算子：對，的分量由下式確定 (1.22)定義1

6、.3 （特征值和特征向量）考慮定義1.2給出的矩陣算子。稱為它的特征值，并稱為相應(yīng)的特征向量，如果 且 (1.23)定義 1.4（半正定性） 考慮定義1.2給出的矩陣算子。稱它是半正定的，如果對，有 (1.24)引理 1.1 若定義1.2給出的矩陣算子是半正定的，則存在著個非負(fù)特征值和互相正交的單位特征向量，使得 , (1.25)證明： 由于是對稱的，所以存在著正交矩陣和對角矩陣，使得 (1.26)這里是矩陣的第t個特征向量，它對應(yīng)的特征值是。因為是半正定的，所以所有特征值均為非負(fù)數(shù)。于是由（1.26）推知 (1.27) 引理 1.2 若引理1.1的結(jié)論成立，則存在著從到的映射，使得 (1.2

7、8)其中是特征空間的內(nèi)積。因而是一個核函數(shù)。 證明： 定義映射 (1.29)直接驗證可知引理1.2成立。 引理 1.3 若引理1.2的結(jié)論成立，則矩陣是半正定的。 證明： 設(shè)不是半正定的，則一定存在著與一個負(fù)特征值相對應(yīng)的單位特征向量。定義中的向量z (1.30)則有 (1.31)顯然，這與是負(fù)特征值相矛盾。因此K必須是半正定的。 定理 1.3 設(shè)是有限集合，是定義在上的對稱函數(shù)。則由定義1.2給出的矩陣算子半正定，等價于可表示為 (1.32)其中是矩陣 (1.33)的特征值，為對應(yīng)于的特征向量，也等價于是一個核函數(shù)，即，其中映射由式（1.29）定義。2. 半正定積分算子的特征展開設(shè)輸入集合為

8、中的緊集，并設(shè)是的連續(xù)對稱函數(shù)。我們要研究的問題是，當(dāng)滿足什么條件時，它是一個核函數(shù)。 定義 1.5 （積分算子） 定義積分算子為按下式確定的在上的積分算子 (1.34) 定義 1.6 （特征值和特征函數(shù)） 考慮定義1.5給出的積分算子，稱為它的特征值，為相應(yīng)的特征函數(shù)，如果 (1.35) 定義 1.7 （半正定性）考慮定義1.5給出的積分算子。稱它是半正定的，如果對，有 (1.36) 引理 1.4 若定義1.5給出的積分算子是半正定的，則存在著可數(shù)個非負(fù)特征值和相應(yīng)的互相正交的單位特征函數(shù)，使得可表示為上的一致收斂的級數(shù) (1.37)引理 1.5 若引理1.4的結(jié)論成立，則存在著到Hilbe

9、rt空間的映射，使得 ， (1.38)其中是上的內(nèi)積。因而是一個核函數(shù)。證明： 定義映射 (1.39)則可驗證引理1.5成立。引理 1.6 若引理1.5的結(jié)論成立則積分算子是半正定的。定理 1.4（Mercer 定理） 令是上的一個緊集，是上的連續(xù)實(shí)值對稱函數(shù)。則由定義1.5給出的積分算子半正定 ， (1.40)等價于可表示為的一致收斂序列 (1.41)其中是的特征值，是對應(yīng)的特征函數(shù)。它也等價于是一個核函數(shù) (1.42)其中映射由式（1.39）定義，而是Hilbert空間上的內(nèi)積。定義 1.8 （Mercer 核） 稱函數(shù)為Mercer 核，如果是定義在上的連續(xù)對稱函數(shù)，其中是的緊集，且由定

10、義1.5給出的積分算子是半正定的。定理 1.5 設(shè)為上的緊集，是上的連續(xù)對稱函數(shù)，則積分算子半正定的充要條件是關(guān)于任意的的Gram矩陣半正定。§3 正定核定理 1.6 設(shè)是的子集。若是定義在上的正定核，則對，函數(shù)關(guān)于的Gram矩陣都是半正定的。證明： 是定義在上的正定核，因此存在著從X到Hilbert空間H的映射，使得 (1.43)任取，構(gòu)造關(guān)于的Gram矩陣。顯然，根據(jù)由式（1.43）可以斷言，對,我們有 (1.44)這表明關(guān)于的Gram矩陣是半正定的。引理 1.7 若集合S由所有的下列元素組成 (1.45)其中為任意的正整數(shù)，,則S為一個向量空間。 證明： 由于集合S中的元素對于

11、加法和數(shù)乘封閉，所以S構(gòu)成一個向量空間。 引理 1.8 若對S中的兩元素 和 (1.46)定義運(yùn)算 (1.47)并由此定義在上的函數(shù)，則該函數(shù)關(guān)于的Gram矩陣都是半正定的。 證明： 由知：若任意選取，記函數(shù)相應(yīng)的Gram矩陣為。顯然它是對稱矩陣。由（1.47）可知對有： (1.48)這表明Gram矩陣是半正定的。 引理 1.9 在引理1.8中定義的運(yùn)算具有如下性質(zhì)：對于，有 (1.49) 證明： 任取,則關(guān)于的Gram矩陣為 (1.50)因為，所以由引理1.8可知：矩陣（1.50）是半正定的，其行列式非負(fù)。由此可知 (1.51)引理 1.10 引理1.8中定義的運(yùn)算是S上的內(nèi)積運(yùn)算，因而可記

12、為 (1.52)證明： 直接驗證可知該運(yùn)算具有內(nèi)積運(yùn)算應(yīng)滿足的如下性質(zhì)：對和有 (1.53) (1.54) (1.55) (1.56)只需證明：若，則有。事實(shí)上，若 (1.57)則按運(yùn)算規(guī)則（1.47）知，對，有 (1.58)由于 (1.59)所以 (1.60)此式意味著當(dāng)時，對，都有，即為零元素。 引理 1.11 若H是引理1.7中的集合S在引理1.8中定義的內(nèi)積運(yùn)算意義下的閉包，則H是一個Hilbert空間。 定理 1.7 設(shè)是定義在上的對稱函數(shù)。若對，函數(shù)關(guān)于的Gram矩陣都是半正定的，則是一個正定核。 證明： 定義映射 (1.61)由引理1.7和1.11知，該映射是從X到某一Hilbe

13、rt空間的映射。由式（1.58）可得到 (1.62)由引理1.10知引理1.8中定義的運(yùn)算是內(nèi)積運(yùn)算。利用式（1.61）可得到 (1.63)由定義1.1知是正定核。 定義 1.12 （正定核的等價定義） 設(shè)是的子集。稱定義在上的對稱函數(shù)為一個正定核，如果對，相對于的Gram矩陣都是半正定的。 定義 1.13 （再生核的Hilbert空間） 令是一個非空的集合，是一個由函數(shù)組成的，內(nèi)積由式（1.47）定義以及范數(shù)由定義的Hilbert空間。稱是一個再生核Hilbert空間（簡稱RKHS）,如果存在滿足如下性質(zhì)（1） 具有再生性，即對，有 (1.64) 特別地 (1.65)（2） 張成空間，即 (

14、1.66)其中表示集合A的閉包。若函數(shù)是Mercer核，則對，有 因此，一定是一個正定核。因為Mercer是正定的，所以它是再生核。§4 核函數(shù)的構(gòu)造根據(jù)正定核的等價定義，我們可以從簡單的核來構(gòu)造復(fù)雜的核。定理 1.8 設(shè)是上的核。若是從到的映射，則是上的核。特別地，若矩陣B是半正定的，則是的核。證明： 任取，則相應(yīng)的Gram矩陣為 (1.67)記，則有 (1.68)由是上的正定核可知：上式右端矩陣是半正定的。從而左端矩陣半正定。所以是正定核。 當(dāng)B為半正定矩陣時，它可分解為 (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) 證明: 對給定的一個有限集合，令和分別是和相對于這個集合的Gram矩陣。（1） 對,有 (1.75)所以是半正定的，因而是核函數(shù)。 （2）是核函數(shù)。 （3） 設(shè)為對應(yīng)于的Gram矩陣，則的元素是和對應(yīng)元素的乘積 (1.76)現(xiàn)證明是半正定矩陣。令,，則 (1.77) 定理 1.11 設(shè)是上的核。又設(shè)是系數(shù)全為正數(shù)