1噪径、線性可分到線性不可分
前面我們介紹了線性情況下的支持向量機，它通過尋找一個線性的超平面來達到對數(shù)據(jù)進行分類的目的肤频。不過粪摘，由于是線性方法瀑晒，所以對非線性的數(shù)據(jù)就沒有辦法處理了。例如圖中的兩類數(shù)據(jù)徘意，分別分布為兩個圓圈的形狀瑰妄，不論是任何高級的分類器，只要它是線性的映砖，就沒法處理间坐，SVM 也不行。因為這樣的數(shù)據(jù)本身就是線性不可分的邑退。
上面的數(shù)據(jù)集生成它的時候就是用兩個半徑不同的圓圈加上了少量的噪音得到的竹宋，所以，一個理想的分界應(yīng)該是一個“圓圈”而不是一條線（超平面）地技。那么上面的兩條二次曲線由下面的公式產(chǎn)生：
我們想要在二維空間中找到一條線將數(shù)據(jù)分開蜈七，是不可能的，但假如我們做如下的變換： 令Z1=X1^2, Z2=X2^2, Z3=X2,我們就能把現(xiàn)在的數(shù)據(jù)點從二維空間中映射到高維空間中莫矗，那么上面的方程在映射后可以轉(zhuǎn)換為如下的形式（5應(yīng)該改為3）：
不難看出飒硅，在映射之后我們的數(shù)據(jù)變成線性可分的了砂缩，如果將三維空間中的數(shù)據(jù)點畫出，它大概是下面的樣子三娩，我們可以看到庵芭，能夠找到一個超平面，將兩類數(shù)據(jù)點準確分開：
現(xiàn)在讓我們再回到 SVM 的情形雀监，假設(shè)原始的數(shù)據(jù)時非線性的双吆，我們通過一個映射 ?(?) 將其映射到一個高維空間中，數(shù)據(jù)變得線性可分了会前，這個時候好乐，我們就可以使用原來的推導(dǎo)來進行計算，只是所有的推導(dǎo)現(xiàn)在是在新的空間瓦宜，而不是原始空間中進行蔚万。當然，推導(dǎo)過程也并不是可以簡單地直接類比的临庇，例如反璃，原本我們要求超平面的法向量 w ，但是如果映射之后得到的新空間的維度是無窮維的（確實會出現(xiàn)這樣的情況苔巨，比如后面會提到的 Gaussian Kernel ）版扩，要表示一個無窮維的向量描述起來就比較麻煩废离。于是我們不妨先忽略過這些細節(jié)侄泽，直接從最終的結(jié)論來分析，回憶一下蜻韭，我們上一次得到的最終的分類函數(shù)是這樣的：
現(xiàn)在則是在映射過后的空間悼尾，即：
而其中的 α 也是通過求解如下 dual 問題而得到的：
2、核函數(shù)(Kernel Function)
這樣一來問題就解決了嗎肖方？似乎是的：拿到非線性數(shù)據(jù)闺魏，就找一個映射 ?(?) ，然后一股腦把原來的數(shù)據(jù)映射到新空間中俯画，再做線性 SVM 即可析桥。其實剛才的方法稍想一下就會發(fā)現(xiàn)有問題：在最初的例子里，我們對一個二維空間做映射艰垂，選擇的新空間是原始空間的所有一階和二階的組合泡仗，得到了五個維度；如果原始空間是三維猜憎，那么我們會得到 19 維的新空間娩怎，這個數(shù)目是呈爆炸性增長的，這給 ?(?) 的計算帶來了非常大的困難胰柑，而且如果遇到無窮維的情況截亦，就根本無從計算了爬泥。所以就需要 Kernel 出馬了。
假設(shè)我們現(xiàn)在的二次曲線的方程為：
此時我們需要構(gòu)造一個五維空間進行映射崩瓤，令Z1=X1, Z2=X1^2, Z3=X2, Z4=X2^2, Z5=X1X2袍啡，假設(shè)此時有兩個數(shù)據(jù)點：x1=(η1,η2)T 和 x2=(ξ1,ξ2)T ，而 ?(?) 即是到前面說的五維空間的映射谷遂，因此映射過后的內(nèi)積為：
另外葬馋，我們注意到有這么一個公式：
二者有很多相似的地方，實際上肾扰，我們只要把某幾個維度線性縮放一下畴嘶，然后再加上一個常數(shù)維度，具體來說集晚，如果將映射的方式改變一下窗悯，變?yōu)橄旅娴男问剑儆嬎銉?nèi)積的時候偷拔，得到的結(jié)構(gòu)就與上面的式子相同：
可以看到上面兩種方法得到了同樣的結(jié)果蒋院，但區(qū)別是什么呢，一個是先將低維空間中的數(shù)據(jù)點映射到了高維空間中莲绰，另一種方式是直接在原來的地位空間中進行運算欺旧，對運算結(jié)果又進行了一定的處理「蚯回憶剛才提到的映射的維度爆炸辞友，在前一種方法已經(jīng)無法計算的情況下，后一種方法卻依舊能從容處理震肮，甚至是無窮維度的情況也沒有問題称龙。
我們把這里的計算兩個向量在映射過后的空間中的內(nèi)積的函數(shù)叫做核函數(shù) (Kernel Function) ，例如戳晌，在剛才的例子中鲫尊，我們的核函數(shù)為：
核函數(shù)能簡化映射空間中的內(nèi)積運算——剛好“碰巧”的是，在我們的 SVM 里需要計算的地方數(shù)據(jù)向量總是以內(nèi)積的形式出現(xiàn)的沦偎。對比剛才我們寫出來的式子疫向，現(xiàn)在我們的分類函數(shù)為：
而求解α的規(guī)劃問題變?yōu)椋?br>
這樣一來計算的問題就算解決了，避開了直接在高維空間中進行計算豪嚎，而結(jié)果卻是等價的搔驼，實在是一件非常美妙的事情！當然疙渣，因為我們這里的例子非常簡單匙奴，所以我可以手工構(gòu)造出對應(yīng)于 φ(?) 的核函數(shù)出來，如果對于任意一個映射妄荔，想要構(gòu)造出對應(yīng)的核函數(shù)就很困難了泼菌。
最理想的情況下谍肤，我們希望知道數(shù)據(jù)的具體形狀和分布，從而得到一個剛好可以將數(shù)據(jù)映射成線性可分的 ?(?) 哗伯，然后通過這個 ?(?) 得出對應(yīng)的 κ(?,?) 進行內(nèi)積計算荒揣。然而，第二步通常是非常困難甚至完全沒法做的焊刹。不過系任，由于第一步也是幾乎無法做到，因為對于任意的數(shù)據(jù)分析其形狀找到合適的映射本身就不是什么容易的事情虐块，所以俩滥，人們通常都是“胡亂”選擇映射的，所以贺奠，根本沒有必要精確地找出對應(yīng)于映射的那個核函數(shù)霜旧，而只需要“胡亂”選擇一個核函數(shù)即可——我們知道它對應(yīng)了某個映射，雖然我們不知道這個映射具體是什么儡率。由于我們的計算只需要核函數(shù)即可挂据，所以我們也并不關(guān)心也沒有必要求出所對應(yīng)的映射的具體形式。
當然儿普，說是“胡亂”選擇崎逃，其實是夸張的說法，通常人們會從一些常用的核函數(shù)中選擇（根據(jù)問題和數(shù)據(jù)的不同眉孩，選擇不同的參數(shù)个绍，實際上就是得到了不同的核函數(shù)），例如：
最后勺像，總結(jié)一下：對于非線性的情況障贸，SVM 的處理方法是選擇一個核函數(shù) κ(?,?) 错森，通過將數(shù)據(jù)映射到高維空間吟宦，來解決在原始空間中線性不可分的問題。由于核函數(shù)的優(yōu)良品質(zhì)涩维，這樣的非線性擴展在計算量上并沒有比原來復(fù)雜多少殃姓，這一點是非常難得的。當然，這要歸功于核方法——除了 SVM 之外，任何將計算表示為數(shù)據(jù)點的內(nèi)積的方法节值，都可以使用核方法進行非線性擴展鸣戴。
3、核函數(shù)的選擇問題
之前在面試今日頭條算法工程師的時候近顷，被問到了常用的核函數(shù)如何選擇的問題，根據(jù)網(wǎng)上的答案，總結(jié)如下：
在選取核函數(shù)解決實際問題時该面，通常采用的方法有：一是利用專家的先驗知識預(yù)先選定核函數(shù)夭苗；二是采用Cross-Validation方法，即在進行核函數(shù)選取時隔缀，分別試用不同的核函數(shù)题造，歸納誤差最小的核函數(shù)就是最好的核函數(shù)．如針對傅立葉核、RBF核猾瘸，結(jié)合信號處理問題中的函數(shù)回歸問題界赔，通過仿真實驗，對比分析了在相同數(shù)據(jù)條件下牵触，采用傅立葉核的SVM要比采用RBF核的SVM誤差小很多淮悼。
在我的研究做實驗過程中，最常用的是Linear核與RBF核揽思。
1）. Linear核：主要用于線性可分的情形敛惊。參數(shù)少，速度快绰更，對于一般數(shù)據(jù)瞧挤，分類效果已經(jīng)很理想了。
2）. RBF核（高斯核）：主要用于線性不可分的情形儡湾。參數(shù)多特恬，分類結(jié)果非常依賴于參數(shù)。有很多人是通過訓(xùn)練數(shù)據(jù)的交叉驗證來尋找合適的參數(shù)徐钠，不過這個過程比較耗時癌刽。我個人的體會是：使用libsvm，默認參數(shù)尝丐，RBF核比Linear核效果稍差显拜。通過進行大量參數(shù)的嘗試，一般能找到比linear核更好的效果爹袁。
