支持向量機(jī)(三)核函數(shù)

1、支持向量機(jī)（三）核函數(shù) 7 核函數(shù)（Kernels） 考慮我們最初在“線性回歸”中提出的問題，特征是房子的面積x，這里的x是實(shí)數(shù)，結(jié)果y是房子的價(jià)格。假設(shè)我們從樣本點(diǎn)的分布中看到x和y符合3次曲線，那么我們希望使用x的三次多項(xiàng)式來逼近這些樣本點(diǎn)。那么首先需要將特征x擴(kuò)展到三維，然后尋找特征和結(jié)果之間的模型。我們將這種特征變換稱作特征映射（feature mapping）。映射函數(shù)稱作，在這個(gè)例子中 我們希望將得到的特征映射后的特征應(yīng)用于SVM分類，而不是最初的特征。這樣，我們需要將前面公式中的內(nèi)積從，映射到。 至于為什么需要映射后的特征而不是最初的特征來參與計(jì)算，上面提到的（為了更好地?cái)M合）是

2、其中一個(gè)原因，另外的一個(gè)重要原因是樣例可能存在線性不可分的情況，而將特征映射到高維空間后，往往就可分了。（在數(shù)據(jù)挖掘?qū)д揚(yáng)ang-Ning Tan等人著的支持向量機(jī)那一章有個(gè)很好的例子說明） 將核函數(shù)形式化定義，如果原始特征內(nèi)積是，映射后為，那么定義核函數(shù)（Kernel）為 到這里，我們可以得出結(jié)論，如果要實(shí)現(xiàn)該節(jié)開頭的效果，只需先計(jì)算，然后計(jì)算即可，然而這種計(jì)算方式是非常低效的。比如最初的特征是n維的，我們將其映射到維，然后再計(jì)算，這樣需要的時(shí)間。那么我們能不能想辦法減少計(jì)算時(shí)間呢？ 先看一個(gè)例子，假設(shè)x和z都是n維的， 展開后，得 這個(gè)時(shí)候發(fā)現(xiàn)我們可以只計(jì)算原始特征x和z內(nèi)積的平方（時(shí)間復(fù)

3、雜度是O(n)），就等價(jià)與計(jì)算映射后特征的內(nèi)積。也就是說我們不需要花時(shí)間了。 現(xiàn)在看一下映射函數(shù)（n=3時(shí)），根據(jù)上面的公式，得到 也就是說核函數(shù)只能在選擇這樣的作為映射函數(shù)時(shí)才能夠等價(jià)于映射后特征的內(nèi)積。 再看一個(gè)核函數(shù) 對應(yīng)的映射函數(shù)（n=3時(shí)）是 更一般地，核函數(shù)對應(yīng)的映射后特征維度為。（求解方法參見/question/16706714.html）。 由于計(jì)算的是內(nèi)積，我們可以想到IR中的余弦相似度，如果x和z向量夾角越小，那么核函數(shù)值越大，反之，越小。因此，核函數(shù)值是和的相似度。 再看另外一個(gè)核函數(shù) 這時(shí)，如果x和z很相近（），那么核函數(shù)值為

4、1，如果x和z相差很大（），那么核函數(shù)值約等于0。由于這個(gè)函數(shù)類似于高斯分布，因此稱為高斯核函數(shù)，也叫做徑向基函數(shù)(Radial Basis Function 簡稱RBF)。它能夠把原始特征映射到無窮維。 既然高斯核函數(shù)能夠比較x和z的相似度，并映射到0到1，回想logistic回歸，sigmoid函數(shù)可以，因此還有sigmoid核函數(shù)等等。 下面有張圖說明在低維線性不可分時(shí)，映射到高維后就可分了，使用高斯核函數(shù)。 來自Eric Xing的slides 注意，使用核函數(shù)后，怎么分類新來的樣本呢？線性的時(shí)候我們使用SVM學(xué)習(xí)出w和b，新來樣本x的話，我們使用來判斷，如果值大于等于1，那么是正類，

5、小于等于是負(fù)類。在兩者之間，認(rèn)為無法確定。如果使用了核函數(shù)后，就變成了，是否先要找到，然后再預(yù)測？答案肯定不是了，找很麻煩，回想我們之前說過的 只需將替換成，然后值的判斷同上。 8 核函數(shù)有效性判定 問題：給定一個(gè)函數(shù)K，我們能否使用K來替代計(jì)算，也就說，是否能夠找出一個(gè)，使得對于所有的x和z，都有？ 比如給出了，是否能夠認(rèn)為K是一個(gè)有效的核函數(shù)。 下面來解決這個(gè)問題，給定m個(gè)訓(xùn)練樣本，每一個(gè)對應(yīng)一個(gè)特征向量。那么，我們可以將任意兩個(gè)和帶入K中，計(jì)算得到。I可以從1到m，j可以從1到m，這樣可以計(jì)算出m*m的核函數(shù)矩陣（Kernel Matrix）。為了方便，我們將核函數(shù)矩陣和都使用K來表示。

6、 如果假設(shè)K是有效地核函數(shù)，那么根據(jù)核函數(shù)定義 可見，矩陣K應(yīng)該是個(gè)對稱陣。讓我們得出一個(gè)更強(qiáng)的結(jié)論，首先使用符號來表示映射函數(shù)的第k維屬性值。那么對于任意向量z，得 最后一步和前面計(jì)算時(shí)類似。從這個(gè)公式我們可以看出，如果K是個(gè)有效的核函數(shù)（即和等價(jià)），那么，在訓(xùn)練集上得到的核函數(shù)矩陣K應(yīng)該是半正定的（） 這樣我們得到一個(gè)核函數(shù)的必要條件： K是有效的核函數(shù) = 核函數(shù)矩陣K是對稱半正定的。 可幸的是，這個(gè)條件也是充分的，由Mercer定理來表達(dá)。 Mercer定理： 如果函數(shù)K是上的映射（也就是從兩個(gè)n維向量映射到實(shí)數(shù)域）。那么如果K是一個(gè)有效核函數(shù)（也稱為Mercer核函數(shù)），那么當(dāng)且僅當(dāng)對于訓(xùn)練樣例，其相應(yīng)的核函數(shù)矩陣是對稱半正定的。Mercer定理表明為了證明K是有效的核函數(shù)，那么我們不用去尋找，而只需要在訓(xùn)練集上求出各個(gè)，然后判斷矩陣K是否是半正定（使用左上角主子式大于等于零等方法）即可。 許多其他的教科書在Mercer定理證明過