知識星球
（點選上方公眾號，可快速關註）
轉自：jerrylead
http://www.cnblogs.com/jerrylead/archive/2011/03/18/1988406.html
核函式（Kernels）
考慮我們最初在“線性回歸”中提出的問題，特徵是房子的面積x，這裡的x是實數，結果y是房子的價格。
假設我們從樣本點的分佈中看到x和y符合3次曲線，那麼我們希望使用x的三次多項式來逼近這些樣本點。
那麼首先需要將特徵x擴充套件到三維
，然後尋找特徵和結果之間的模型。我們將這種特徵變換稱作特徵對映（feature mapping）。對映函式稱作
，在這個例子中
我們希望將得到的特徵對映後的特徵應用於SVM分類，而不是最初的特徵。這樣，我們需要將前面
公式中的內積從
，對映到
。
至於為什麼需要對映後的特徵而不是最初的特徵來參與計算，上面提到的（為了更好地擬合）是其中一個原因，另外的一個重要原因是樣例可能存線上性不可分的情況，而將特徵對映到高維空間後，往往就可分了。（在《資料挖掘導論》Pang-Ning Tan等人著的《支援向量機》那一章有個很好的例子說明）
將核函式形式化定義，如果原始特徵內積是
，對映後為
，那麼定義核函式（Kernel）為
到這裡，我們可以得出結論，如果要實現該節開頭的效果，只需先計算
，然後計算
即可，然而這種計算方式是非常低效的。
比如最初的特徵是n維的，我們將其對映到
維，然後再計算，這樣需要
的時間。那麼我們能不能想辦法減少計算時間呢？
先看一個例子，假設x和z都是n維的，
展開後，得
這個時候發現我們可以只計算原始特徵x和z內積的平方（時間複雜度是O(n)），就等價與計算對映後特徵的內積。也就是說我們不需要花時間了。
現在看一下對映函式（n=3時），根據上面的公式，得到
也就是說核函式
只能在選擇這樣的作為對映函式時才能夠等價於對映後特徵的內積。
再看一個核函式
對應的對映函式（n=3時）是
更一般地，核函式
對應的對映後特徵維度為
。
由於計算的是內積，我們可以想到IR中的餘弦相似度，如果x和z向量夾角越小，那麼核函式值越大，反之，越小。因此，核函式值是和
的相似度。
再看另外一個核函式
這時，如果x和z很相近（
），那麼核函式值為1，如果x和z相差很大（
），那麼核函式值約等於0。
由於這個函式類似於高斯分佈，因此稱為高斯核函式，也叫做徑向基函式(Radial Basis Function 簡稱RBF)。它能夠把原始特徵對映到無窮維。
既然高斯核函式能夠比較x和z的相似度，並對映到0到1，回想logistic回歸，sigmoid函式可以，因此還有sigmoid核函式等等。
下麵有張圖說明在低維線性不可分時，對映到高維後就可分了，使用高斯核函式。
來自Eric Xing的slides
註意，使用核函式後，怎麼分類新來的樣本呢？線性的時候我們使用SVM學習出w和b，新來樣本x的話，我們使用
來判斷，如果值大於等於1，那麼是正類，小於等於是負類。
在兩者之間，認為無法確定。如果使用了核函式後，就變成了
，是否先要找到
，然後再預測？答案肯定不是了，找很麻煩，回想我們之前說過的
只需將
替換成
，然後值的判斷同上。
核函式有效性判定
問題：給定一個函式K，我們能否使用K來替代計算，也就說，是否能夠找出一個
，使得對於所有的x和z，都有？
比如給出了
，是否能夠認為K是一個有效的核函式。
下麵來解決這個問題，給定m個訓練樣本
，每一個
對應一個特徵向量。
那麼，我們可以將任意兩個和
帶入K中，計算得到
。I可以從1到m，j可以從1到m，這樣可以計算出m*m的核函式矩陣（Kernel Matrix）。
為了方便，我們將核函式矩陣和
都使用K來表示。
如果假設K是有效地核函式，那麼根據核函式定義
可見，矩陣K應該是個對稱陣。讓我們得出一個更強的結論，首先使用符號
來表示對映函式的第k維屬性值。那麼對於任意向量z，得
最後一步和前面計算時類似。從這個公式我們可以看出，如果K是個有效的核函式（即和
等價），那麼，在訓練集上得到的核函式矩陣K應該是半正定的（
）
這樣我們得到一個核函式的必要條件：
K是有效的核函式 ==> 核函式矩陣K是對稱半正定的。
可幸的是，這個條件也是充分的，由Mercer定理來表達。
|
Mercer定理： 如果函式K是 |
Mercer定理表明為了證明K是有效的核函式，那麼我們不用去尋找，而只需要在訓練集上求出各個
，然後判斷矩陣K是否是半正定（使用左上角主子式大於等於零等方法）即可。
許多其他的教科書在Mercer定理證明過程中使用了
範數和再生希爾伯特空間等概念，但在特徵是n維的情況下，這裡給出的證明是等價的。
核函式不僅僅用在SVM上，但凡在一個模型後演演算法中出現了
，我們都可以常使用去替換，這可能能夠很好地改善我們的演演算法。
覺得本文有幫助？請分享給更多人
關註「演演算法愛好者」，修煉程式設計內功
