非線性分類問題
遇到分類問題的時(shí)候，最理想的狀態(tài)，當(dāng)然是樣本在向量空間中都是線性可分的却舀，我們可以清晰無誤地把它們分隔成不同的類別——線性可分 SVM虫几。
如果實(shí)在不行，我們可以容忍少數(shù)不能被正確劃分禁筏，只要大多數(shù)線性可分就好——線性 SVM持钉。
可是，如果我們面對(duì)的分類問題篱昔，根本就是非線性的呢每强？比如像下面這樣：
圖中紅色的點(diǎn)是正類樣本，藍(lán)色的點(diǎn)是負(fù)類樣本州刽。通過我們的觀察可知空执，它們之間的界限是很分明的，用圖中綠色的圈本來可以把它們完全分開穗椅。
很可惜辨绊，“圓圈”在二維空間里無法用線性函數(shù)表示，也就是說這些樣本在二維空間里根本線性不可分匹表。所以门坷，無論是線性可分 SVM 還是線性 SVM，都無法在這些樣本上良好工作袍镀。
這可怎么辦呢默蚌？難道，這種情況我們就處理不了了苇羡？
并不是绸吸！
我們可以想個(gè)辦法，讓這些在二維空間中線性不可分的樣本设江，在更高維度的空間里線性可分锦茁。
比如說，如果我們能把上圖中那些正負(fù)類的樣本映射到三維空間中叉存，并且依據(jù)不同的類別給它們賦予不一樣的高度值——z 軸取值（就像下圖這樣）码俩，那么不就線性可分了嘛。
如此一來鹉胖，在二維空間團(tuán)團(tuán)轉(zhuǎn)的正負(fù)例握玛，在三維空間中分為兩層，中間用一個(gè)超平面甫菠，就可以完美分隔了。
非線性 SVM
非線性 SVM 分隔超平面
對(duì)于在有限維度向量空間中線性不可分的樣本冕屯，我們將其映射到更高維度的向量空間里寂诱，再通過間隔最大化的方式，學(xué)習(xí)得到支持向量機(jī)安聘，就是非線性 SVM痰洒。
我們將樣本映射到的這個(gè)更高維度的新空間叫做特征空間瓢棒。
注意：如果是理想狀態(tài)，樣本從原始空間映射到特征空間后直接就成為線性可分的丘喻，那么接下來的學(xué)習(xí)是可以通過硬間隔最大化的方式來學(xué)的脯宿。
不過，一般的情況總沒有那么理想泉粉，因此连霉，通常情況下，我們還是按照軟間隔最大化嗡靡，在特征空間中學(xué)習(xí) SVM跺撼。
簡單理解就是：非線性 SVM = 核技巧 + 線性 SVM。
我們用向量 x 表示位于原始空間中的樣本讨彼，?(x) 表示 x 映射到特征空間之后的新向量歉井。
則非線性 SVM對(duì)應(yīng)的分隔超平面為：f(x)=w?(x)+b。
非線性 SVM 的對(duì)偶問題
套用上一篇線性 SVM 的對(duì)偶問題哈误，此處非線性 SVM 的對(duì)偶問題就變成了：
min(12∑mi=1∑mj=1αiαjyiyj?(xi)??(xj)?∑mi=1αi)
s.t.∑mi=1αiyi=0
0?αi?C,i=1,2,...,m
大家可以看到哩至，和線性 SVM 唯一的不同就是：之前的 xi 與 xj 的內(nèi)積（點(diǎn)乘） 變成了 ?(xi) 與 ?(xj) 的內(nèi)積。
核函數(shù)
對(duì)于有限維的原始空間蜜自，一定存在更高維度的空間菩貌，使得前者中的樣本映射到新空間后可分。但是新空間（特征空間）的維度也許很大袁辈，甚至可能是無限維的菜谣。這樣的話，直接計(jì)算 ?(xi)??(xj) 就會(huì)很困難晚缩。
為了避免計(jì)算 ?(xi) 和 ?(xj) 的內(nèi)積尾膊，我們需要設(shè)置一個(gè)新的函數(shù)——k(xi,xj)：
k(xi,xj)=?(xi)??(xj)
原始空間中的兩個(gè)樣本 xi 和 xj 經(jīng)過 k(?,?) 函數(shù)計(jì)算所得出的結(jié)果，是它們?cè)谔卣骺臻g中映射成的新向量的內(nèi)積荞彼。
如此一來冈敛，我們就不必真的計(jì)算出 ?(xi) 點(diǎn)乘 ?(xj) 的結(jié)果，而可以直接用 k(?,?) 函數(shù)代替它們鸣皂。
我們把這個(gè) k(?,?) 函數(shù)叫做核函數(shù)∽デ矗現(xiàn)在我們給出它的正式定義：
設(shè) X 為原始空間（又稱輸入空間），H 為特征空間（特征空間是一個(gè)帶有內(nèi)積的完備向量空間寞缝，又稱完備內(nèi)積空間或希爾伯特空間）癌压。
如果存在一個(gè)映射： X×X ，使得對(duì)所有 xi,xj∈X荆陆，函數(shù) k(xi,xj) 滿足條件：k(xi,xj)=?(xi)??(xj)滩届，即 k(?,?) 函數(shù)為輸入空間中任意兩個(gè)向量映射到特征空間后的內(nèi)積。則稱 k(?,?) 為核函數(shù)被啼，?(?) 為映射函數(shù)帜消。
運(yùn)用核技巧求解非線性 SVM 的對(duì)偶問題
有了核函數(shù)棠枉，我們就可以將非線性 SVM 的對(duì)偶問題寫成：
min(12∑mi=1∑mj=1αiαjyiyjk(xi,xj)?∑mi=1αi)
s.t.∑mi=1αiyi=0
0?αi?C,i=1,2,...,m
之后的求解過程與線性 SVM 一致：先根據(jù)對(duì)偶問題求解 α，再根據(jù) α 的結(jié)果計(jì)算 w泡挺，然后根據(jù)支持向量求解 b辈讶，在此就不贅述了。
相應(yīng)地娄猫，最終求出的非線性 SVM 在特征空間的最大分隔超平面也就成了：
f(x)=w?(x)+b=∑mi=1αiyi?(xi)??(x)+b=∑mi=1αiyik(x,xi)+b
上述運(yùn)用核函數(shù)求解的過程贱除，稱為核技巧。
核函數(shù)的性質(zhì)
如果我們已經(jīng)知道了映射函數(shù)是什么稚新，當(dāng)然可以通過兩個(gè)向量映射后的內(nèi)積直接求得核函數(shù)勘伺。
但是，在我們還不知道映射函數(shù)本身是什么的時(shí)候褂删，有沒有可能直接判斷一個(gè)函數(shù)是不是核函數(shù)呢飞醉？
換句話說，一個(gè)函數(shù)需要具備怎樣的性質(zhì)屯阀，才是一個(gè)核函數(shù)缅帘？
以下是函數(shù) k(?,?) 可以作為核函數(shù)的充分必要條件：
設(shè) X 是輸入空間，k(?,?) 是定義在 X×X 上的對(duì)稱函數(shù)难衰，當(dāng)且僅當(dāng)任意 x1,x2,...,xm∈X钦无， 核矩陣 K（如下所示）總是半正定時(shí)，k(?,?) 就可以作為核函數(shù)使用盖袭。
核矩陣：
注意：下面是幾個(gè)線性代數(shù)的基礎(chǔ)概念失暂。
對(duì)稱函數(shù)：函數(shù)的輸出值不隨輸入變量的順序改變而改變的函數(shù)叫做對(duì)稱函數(shù)。
因?yàn)檩斎肟臻g中的 xi和xj 是向量鳄虱，特征空間中的 ?(xi)和?(xj) 也是向量弟塞，k(xi,xj) 表示特征空間向量的內(nèi)積，而兩個(gè)向量的內(nèi)積并不因?yàn)槠漤樞蜃兓兓疽选Ｒ虼司黾牵琸(xi,xj)=k（xj,xi)，即 k(?,?) 為對(duì)稱函數(shù)倍踪。
相應(yīng)地系宫，核矩陣 K 為對(duì)稱矩陣。
半正定矩陣：一個(gè) n×n 的實(shí)對(duì)稱矩陣 M 為半正定建车，當(dāng)且僅當(dāng)對(duì)于所有非零實(shí)系數(shù)向量 z扩借，均有： zTMz?0。
其中“非零實(shí)系數(shù)向量”的含義是：一個(gè)向量中所有元素均為實(shí)數(shù)缤至，且其中至少有一個(gè)元素值非零往枷。
核函數(shù)的種類
要知道，非線性 SVM 的關(guān)鍵在于將輸入空間中線性不可分的樣本映射到線性可分的特征空間中去凄杯。特征空間的好壞直接影響到了 SVM 的效果错洁。
****如何選擇核函數(shù)也就成了一個(gè)關(guān)鍵性的問題。
雖然我們已經(jīng)學(xué)習(xí)了核函數(shù)的定義和性質(zhì)戒突，但讓我們憑空去自己構(gòu)建一個(gè)核函數(shù)出來屯碴，還是一個(gè)非常困難的任務(wù)。
即使真得構(gòu)造出來了膊存，這個(gè)核函數(shù)在具體問題上的效果如何导而，還需要通過大量測(cè)試來證明，很可能費(fèi)了好大勁隔崎，最后效果還不理想今艺。
好在前人已經(jīng)給我們留下來一些經(jīng)歷了長久磨練的常用核函數(shù)，讓我們可以直接拿來用爵卒。接下來虚缎，我們分別看下這些核函數(shù)。
線性核（Linear Kernel）
k(xi,xj)=xTixj
使用時(shí)無須指定參數(shù)（Parameter）钓株，它直接計(jì)算兩個(gè)輸入向量的內(nèi)積实牡。經(jīng)過線性核函數(shù)轉(zhuǎn)換的樣本，特征空間與輸入空間重合轴合，相當(dāng)于并沒有將樣本映射到更高維度的空間里去创坞。
很顯然這是最簡單的核函數(shù)，實(shí)際訓(xùn)練受葛、使用 SVM 的時(shí)候题涨，在不知道用什么核的情況下，可以先試試線性核的效果总滩。
多項(xiàng)式核（Polynomial Kernel）
k(xi,xj)=(γxTixj+r)d,γ>0,d?1
需要指定三個(gè)參數(shù)：γ纲堵、r 和 d。
這是一個(gè)不平穩(wěn)的核咳秉，適用于數(shù)據(jù)做了歸一化（Normalization婉支，參見本文最后一節(jié)）的情況。
RBF 核（Radial Basis Function Kernel）
k(xi,xj)=exp(?γ||xi?xj||2),γ>0
RBF 核又名高斯核 （Gaussian Kernel）澜建，是一個(gè)核函數(shù)家族向挖。它會(huì)將輸入空間的樣本以非線性的方式映射到更高維度的空間（特征空間）里去，因此它可以處理類標(biāo)簽和樣本屬性之間是非線性關(guān)系的狀況炕舵。
它有一個(gè)參數(shù)：γ何之，這個(gè)參數(shù)的設(shè)置非常關(guān)鍵！
如果設(shè)置過大咽筋，則整個(gè) RBF 核會(huì)向線性核方向退化溶推，向更高維度非線性投影的能力就會(huì)減弱；但如果設(shè)置過小，則會(huì)使得樣本中噪音的影響加大蒜危，從而干擾最終 SVM 的有效性虱痕。
不過相對(duì)于多項(xiàng)式核的3個(gè)參數(shù)，RBF 核只有一個(gè)參數(shù)需要調(diào)辐赞，還是相對(duì)簡單的。
當(dāng)線性核效果不是很好時(shí)响委，可以用 RBF 試試新思〖星簦或者，很多情況下可以直接使用 RBF荸哟。
著名的 LIBSVM（臺(tái)灣大學(xué)林智仁/Lin Chih-Jen 教授等設(shè)計(jì)開發(fā)的一款簡單、易用蛔翅、快速有效的 SVM/SVR 支持包）的默認(rèn)核函數(shù)，就是 RBF 核山析。
Sigmoid 核（Sigmoid Kernel）
k(xi,xj)=tanh(γxTixj+r)
有兩個(gè)參數(shù)，γ 和 r笋轨，在某些參數(shù)設(shè)置之下，Sigmoid 核矩陣可能不是半正定的爵政，此時(shí) Sigmoid 核也就不是有效的核函數(shù)了。因此參數(shù)設(shè)置要非常小心钾挟。
整體而言洁灵，Sigmoid 核并不比線性核或者 RBF 核更好。但是掺出，當(dāng)參數(shù)設(shè)置適宜時(shí)徽千，它會(huì)有不俗的表現(xiàn)。
在具體應(yīng)用核函數(shù)時(shí)汤锨，最好針對(duì)具體問題參照前人的經(jīng)驗(yàn)双抽。
構(gòu)建自己的核函數(shù)
除了常見的核函數(shù)，我們還可以根據(jù)以下規(guī)律進(jìn)行核函數(shù)的組合闲礼。
與正數(shù)相乘： k(?,?) 是核函數(shù)牍汹，對(duì)于任意正數(shù)（標(biāo)量）α?0,αk(?,?) 也是核函數(shù)铐维。
與正數(shù)相加： k(?,?) 是核函數(shù)，對(duì)于任意正數(shù)（標(biāo)量）α?0,α+k(?,?) 也是核函數(shù)慎菲。
線性組合： k(?,?) 是核函數(shù)嫁蛇，則如下線性組合也是核函數(shù)：∑ni=1αiki(?,?),αi?0。
乘積： k1(?,?) 和 k2(?,?) 都是核函數(shù)钧嘶，則它們的乘積——k1(?,?)k2(?,?)——也是核函數(shù)棠众。
正系數(shù)多項(xiàng)式函數(shù)： 設(shè) P 為實(shí)數(shù)域內(nèi)的正系數(shù)多項(xiàng)式函數(shù)，k(?,?) 是核函數(shù)有决，則 P(k(?,?)) 也是核函數(shù)。
指數(shù)函數(shù)： k(?,?) 是核函數(shù)空盼，則 exp(k(?,?)) 也是核函數(shù)书幕。
掌握了這些規(guī)律，我們也可以嘗試根據(jù)需要構(gòu)建自己的核函數(shù)揽趾。
數(shù)據(jù)歸一化（Data Normalization）
數(shù)據(jù)歸一化是一種數(shù)據(jù)處理方法台汇，具體所做的就是對(duì)取值范疇不同的數(shù)據(jù)進(jìn)行歸一化處理，使它們處在同一數(shù)量級(jí)上篱瞎。
最常見的苟呐，就是把各種數(shù)據(jù)都變成 (０,１) 之間的小數(shù)。
上圖是一個(gè)歸一化過程在二維中的直觀顯示俐筋。
大家可以看到牵素， “扁長”的數(shù)據(jù)分布，經(jīng)過歸一化處理之后澄者，變成了一個(gè)“正圓”笆呆。
常用的歸一化算法有：
(1)線性轉(zhuǎn)換
x′=(x?min)(max?min)
(2)標(biāo)準(zhǔn)分
x′=(x–μ)γ
原本的 x 符合正態(tài)分布，μ 為其分布的均值粱挡，而 γ 為分布的方差赠幕。
