前面的文章講述的都是將SVM用于線性可分或者近似線性可分的情況，對(duì)于非線性可分的情況，正是本文要討論的內(nèi)容。

核技巧

線性不可分問(wèn)題是指不能用一個(gè)超平面將數(shù)據(jù)劃分成兩個(gè)部分，如下圖所示：

但是如果我們對(duì)原始數(shù)據(jù)進(jìn)行非線性變換，則有可能將原始數(shù)據(jù)映射到能夠線性可分的空間中：

對(duì)于上面這樣的數(shù)據(jù)，如何實(shí)現(xiàn)這樣的變換？

設(shè)原始特征空間為：$\mathcal{X}?R^2，x=(x^{(1)},x^{(2)}{)}^T\in \mathcal{X}$，新的特征空間為：$\mathcal{Z}?R^2，z=(z^{(1)},z^{(2)}{)}^T\in \mathcal{Z}$。

定義原空間到新空間的映射為：
$$z=?(x)=((x^{(1)}{)}^2,(x^{(2)}{)}^2{)}^T$$
則原空間的橢圓：
$$w_1(x^{(1)}{)}^2+w_2(x^{(2)}{)}^2+b=0$$
變?yōu)榱诵驴臻g的直線：
$$w_1{z}^{(1)}+w_2{z}^{(2)}+b=0$$
于是，只要把所有的樣本都映射到新的空間中，就可以用線性可分SVM完成分類了。我們稱這樣的變換思想為核技巧。

核技巧的基本想法是：通過(guò)一個(gè)非線性變換將輸入空間對(duì)應(yīng)于一個(gè)特征空間，使得輸入空間$R^n$中的超曲面對(duì)應(yīng)于特征空間$\mathcal{H}$的超平面。這樣，分類問(wèn)題的學(xué)習(xí)任務(wù)通過(guò)在特征空間中求解線性SVM就可以完成。

核函數(shù)

假設(shè)映射$?(x):\mathcal{X}\to \mathcal{H}$是一個(gè)從低維的輸入空間$\chi$（歐式空間的子集或者離散集合）到高維的希爾伯特空間的$\mathcal{H}$映射。那么如果存在函數(shù)$K(x,z)$，對(duì)于任意$x,z\in \chi$，都有：
$$K(x,z)=?(x)??(z)$$
則稱$K(x,z)$為核函數(shù)。其中$?(x)??(z)$表示x與z的內(nèi)積，結(jié)果是一個(gè)常數(shù)。

為什么要引入核函數(shù)呢？

通常映射$?$需要將低維的輸入空間映射到更高維度的空間才可以線性可分(例如對(duì)異或進(jìn)行分類)，那么分別計(jì)算$?(x)，?(z)$的話，運(yùn)算量比較大。如果存在K(x, z)可以等效的計(jì)算$?(x)??(z)$，則可以極大的減少運(yùn)算量。

舉個(gè)例子：

假設(shè)輸入空間是${\mathbb{R}}^2$，有$x=(x^{(1)},x^{(2)})，z=(z^{(1)},z^{(2)})，K(x,z)=(x?z{)}^2$，可以取：
$$\mathcal{H}={\mathbb{R}}^4,?(x)=((x^{(1)}{)}^2,x^{(1)}{x}^{(2)},x^{(1)}{x}^{(2)},(x^{(2)}{)}^2{)}^T$$
可以得到：
$$?(x)??(z)=K(x,z)=(x?z{)}^2$$
也就是說(shuō)二者結(jié)果相同，但是可以明顯發(fā)現(xiàn)$?(x)??(z)$的計(jì)算復(fù)雜度要高得多。不過(guò)映射函數(shù)不唯一，下面的映射也能達(dá)到相同的效果：
$$\mathcal{H}={\mathbb{R}}^3,?(x)=((x^{(1)}{)}^2,\sqrt{2}{x}^{(1)}{x}^{(2)},(x^{(2)}{)}^2{)}^T$$
核函數(shù)的價(jià)值在于它雖然也是將特征進(jìn)行從低維到高維的轉(zhuǎn)換，但核函數(shù)好在它在低維上進(jìn)行計(jì)算，而將實(shí)質(zhì)上的分類效果表現(xiàn)在了高維上，這樣避免了直接在高維空間中的復(fù)雜計(jì)算。

正定核

已知映射函數(shù)$?$，可以通過(guò)$?(x)$和$?(z)$的內(nèi)積求得核函數(shù)$K(x,z)$。不構(gòu)造$?$能否直接判斷某個(gè)函數(shù)$K(x,z)$是核函數(shù)？

一般核函數(shù)指的是正定核函數(shù)，充要條件是：假設(shè)$K(x,z)$是對(duì)稱函數(shù)，對(duì)于任意的$x_i \in \chi ， i=1,2,3…m $, $K(x_i,x_j)$對(duì)應(yīng)的Gram矩陣$K=[K(x_i,x_j){]}_{m\times m}$ 是半正定矩陣，則$K(x,z)$是正定核函數(shù)，此時(shí)$K(x,z)$是核函數(shù)。 也就是說(shuō)，一個(gè)函數(shù)要想成為正定核函數(shù)，必須滿足任何點(diǎn)的集合形成的Gram矩陣是半正定的。

基于上面的充要條件，可以檢驗(yàn)是否是核函數(shù)，但是實(shí)際計(jì)算過(guò)程并不容易。一般我們都直接用現(xiàn)成的已經(jīng)證明好的核函數(shù)。

常用核函數(shù)

1，線性核函數(shù)(Linear Kernel)

就是最普通的線性可分SVM，表達(dá)式為：
$$K(x,z)=x?z$$

2，多項(xiàng)式核函數(shù)(Polynomial Kernel)

是線性不可分常用的核函數(shù)之一，表達(dá)式為：
$$K(x,z)=(x?z+1{)}^p$$
對(duì)應(yīng)的支持向量機(jī)是一個(gè)p次多項(xiàng)式分類器。

3，高斯核函數(shù)(Gaussian Kernel)

在SVM中也稱為徑向基核函數(shù)(Radial Basis Function,RBF)，是非線性SVM最主流的核函數(shù)，libsvm默認(rèn)的核函數(shù)就是它。表達(dá)式為：
$$K(x,z)=exp(?\gamma ||x?z|{|}^2)$$
其中$\gamma >0$是需要指定的超參數(shù)。

4，Sigmoid核函數(shù)(Sigmoid Kernel)

也是線性不可分SVM常用的核函數(shù)之一，表達(dá)式為：
$$K(x,z)=tanh（\gamma x?z+r)$$
其中$\gamma ,r$是需要指定的超參數(shù)。

這么多核函數(shù)，各自都有什么特點(diǎn)，面對(duì)實(shí)際問(wèn)題要如何選擇，效果如何，這里先挖個(gè)坑，等到將sklearn的SVM調(diào)參時(shí)一起說(shuō)。

核函數(shù)在SVM中的應(yīng)用

回顧之前文章學(xué)習(xí)的SVM對(duì)偶問(wèn)題：
$$\begin{array}{rl}\underset{\alpha }{\min }& \frac{1}{2}\sum _{i=1}^m\sum _{j=1}^m{\alpha }_i{\alpha }_j{y}_i{y}_j(x_i?x_j)?\sum _{i=1}^m{\alpha }_i\\ s.t.& \sum _{i=1}^m{\alpha }_i{y}_i=0\\ & 0?{\alpha }_i?C,i=1,2,\dots ,m\end{array}$$
將要優(yōu)化的函數(shù)中的內(nèi)積$x_i?x_j$用核函數(shù)$K(x_i,x_j)=?(x_i)??(x_j)$來(lái)代替。此時(shí)對(duì)偶問(wèn)題的目標(biāo)問(wèn)題以及分類決策函數(shù)變?yōu)?#xff1a;
$$\begin{gathered} \underset{\alpha }{\min }\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_{j}K(x_i,x_j)?\sum _{i=1}^N{\alpha }_i \\ f(x)=sign\left(\sum _{i=1}^{N_s}{\alpha }_i^{?}{y}_i?(x_i)??(x)+b^{?}\right)=sign\left(\sum _{i=1}^{N_s}{\alpha }_i^{?}{y}_{i}K(x_i,x)+b^{?}\right) \end{gathered}$$
這意味著我們甚至不需要指定映射函數(shù)$?$，就可以隱式的借助核函數(shù)等價(jià)的將輸入空間映射到高維空間，進(jìn)而在更高維的空間中找到劃分超平面。在實(shí)際應(yīng)用中，需要結(jié)合領(lǐng)域知識(shí)來(lái)選擇合適的核函數(shù)。

非線性SVM算法流程

輸入：訓(xùn)練集$T=(x_1,y_1),(x_2,y_2),...,(x_m,y_m)$，其中x為n維特征向量，$y\in \{?1,1\}$。

輸出：分離超平面的參數(shù)$w^{?},b^{?}$以及分類決策函數(shù)。

算法流程：

(1) 選擇適當(dāng)?shù)暮撕瘮?shù)$K(x,z)$和一個(gè)懲罰系數(shù)$C>0$, 構(gòu)造約束優(yōu)化問(wèn)題
$$\underset{\alpha }{\min }\frac{1}{2}\sum _{i=1,j=1}^m{\alpha }_i{\alpha }_j{y}_i{y}_{j}K(x_i,x_j)?\sum _{i=1}^m{\alpha }_i$$

$$\begin{gathered} s.t.\sum _{i=1}^m{\alpha }_i{y}_i=0 \\ 0\le {\alpha }_i\le C \end{gathered}$$

(2) 利用SMO算法求出最優(yōu)解 ${\alpha }^{?}=({\alpha }_1^{?},{\alpha }_2^{?},...,{\alpha }_m^{?}{)}^T$

(3) 找出所有滿足$0<{\alpha }_s<C$對(duì)應(yīng)的的S個(gè)支持向量，對(duì)支持向量集合中的每個(gè)樣本$(x_s,y_s)$，通過(guò)：
$$y_s(\sum _{i=1}^m{\alpha }_i{y}_{i}K(x_i,x_s)+b)=1$$
計(jì)算出每個(gè)支持向量$(x_s,y_s)$對(duì)應(yīng)的$b_s^{?}$，即：
$$b_s^{?}=y_s?\sum _{i=1}^m{\alpha }_i{y}_{i}K(x_i,x_s)$$
所有的$b_s^{?}$對(duì)應(yīng)的平均值即為最終的$b^{?}$：
$$b^{?}=\frac{1}{S}\sum _{i=1}^S{b}_s^{?}$$
(4) 構(gòu)造決策函數(shù)：
$$f(x)=sign(\sum _{i=1}^m{\alpha }_i^{?}{y}_{i}K(x,x_i)+b^{?})$$

參考鏈接：

《統(tǒng)計(jì)學(xué)習(xí)方法 第二版》

支持向量機(jī)原理(三)線性不可分支持向量機(jī)與核函數(shù)

李航-統(tǒng)計(jì)學(xué)習(xí)方法-筆記-7：支持向量機(jī)- PilgrimHui - 博客園

總結(jié)

以上是生活随笔為你收集整理的SVM 核函数相关知识的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。