我所理解的 SVM 2——核函數的應用

01-26

這是 SVM 系列的第二篇，上一篇文章 ?? 我所理解的 SVM（支持向量機）1 ?? 介紹了 SVM 的主要思想以及推導過程，這一篇將會在此基礎上介紹核函數(kernel)，這也是 SVM 最為重要的部分之一。

接著上一篇文章

恩是的，我終於回來更新了，非常抱歉這篇 SVM-2 在 SVM-1 後一個多月才填坑，~~因為期間我又去搞別的東西了~~，話不多說，讓我們進入正題。

上面這幅圖是不是很眼熟，在 SVM-1 中我幾乎靠著這一張圖說完了支持向量機的主要思想，不知道你們注意到沒有，在推導 SVM 之前，我的措辭是相當嚴謹的——「圖中的兩組數據，顯然它們是線性可分（linear separable）的」，一切的推導都建立在線性可區分的基礎上，然而實際的很多問題都並非如此，如果我在上面的圖上再加一個點：

無論是 $a,b,c$ 都無法完美地把兩種數據區分出來，實際上也不存在一條直線能完全區分出兩種數據，這種情況就是不可線性區分的，核函數或許可以幫我們解決這個問題。

4. Kernel Trick

上一篇文章的最後我們通過乘數法得到了 $sum_{k=1}^malpha _iy^{(i)}=0, w =sum_{k=1}^malpha _iy^{(i)}x^{(i)}$ ，現在我們把它們回帶到分界線 $y=w^Tx+b$ :

$egin{split}y&=sum_{k=1}^malpha _iy^{(i)}x^{(i)}x+b\&=sum_{k=1}^malpha _iy^{(i)}<x^{(i)},x>+b\end{split}$

如果我們已經求得 $alpha_i$ 和 $b$ ，那麼 $y$ 可以寫成僅依賴於 $x^{(i)}$ 和 $x^{(j)}$ 的矢量積形式，這一點非常關鍵。很多時候我們需要從數據中挖掘新的特徵來進行訓練，而不是簡單粗暴地用原始數據，比如我從 $x$ 中挖掘出新的特徵 $x^2$ ，我們需要再一步一步重新推導 $y$ 的表達式嗎？只需要將 $<x^{(i)}, x>$ 換成 $<(x^{(i)})^2,x^2>$ 即可，更一般的：

如果存在一種映射關係 $phi(x)$ ，將 $x$ 映射到另一空間中，已知 $y=sum_{k=1}^malpha _iy^{(i)}<x^{(i)},x>+b$ ，那麼新空間中的 $y=sum_{k=1}^malpha _iy^{(i)}<phi(x^{(i)}),phi(x)>+b$ 。

整個過程非常的順溜， $phi(x)$ 可以將數據從低維空間映射到高維空間中，為分類提供了新的視角，如下圖所示，一維空間中的數據點 X 和 O 互相交雜，在一維空間中我們無法找到一個分界點進行劃分，但是通過 $phi(x)=(x,0.5x^2+2)$ 映射到二維空間後，很容易找到分界線將這些不同類型的點區分開來。

映射函數 $phi$ 通常將低維的數據（ $m$ ）映射到更高維的空間（ $n$ ）中，使得線性區分變為了可能，考慮到 $m<<n$ ，這引起的一個問題就是計算量隨著維數的增加快速增大，但是我們又知道矢量點積的結果是一個數，怎麼來簡化這個操作呢？

在這裡引入核函數（Kernel Function） $K(x^{(i)},x^{(j)})=phi(x^{(i)})cdot phi(x^{(j)})$ ，此時：

$y=sum_{k=1}^malpha _iy^{(i)}K(x^{(i)},x)+b$

好像有點亂，讓我們先來捋一捋：

$x^{(i)}cdot x^{(j)}longrightarrow phi(x^{(i)})cdot phi(x^{(j)}) =K(x^{(i)},x^{(j)})$

映射函數 $phi$ 的作用是將低維空間的數據映射到高維空間中，核函數 $K$ 表示的是映射之後高維空間中兩個矢量的點積。

通過映射函數，我們能從原始數據中（低維空間）抽象出所需的特徵（高維空間），由低維空間向高維空間的轉化很多時候非常的麻煩，有意思的是，無論是1維、10維、100維還是更高維的空間，其矢量點積的結果都是一個常數，那麼有沒有什麼捷徑，可以跳過維度轉換的過程，通過相對簡單的計算直接得到矢量積？答案就是核函數，還是舉一個例子來說明吧：

令 $x=[x_1, x_2, x_3]^T,y=[y_1, y_2, y_3]^T$ ，我們定義 $phi(x)=[x_1x_1,x_1x_2,x_1x_3,x_2x_1,x_2x_2,x_2x_3,x_3x_1,x_3x_2,x_3x_3]$ 將原始數據從三維空間映射到九維空間中，讓我們來計算 $phi(1,2,3) cdot phi(4,5,6)$ ：

$egin{split}phi(1,2,3)&=[1,2,3,2,4,6,3,6,9]^T\phi(4,5,6)&=[16,20,24,20,25,30,24,30,36]^T\phi(1,2,3) cdot phi(4,5,6) &=1 imes16+2 imes 20 + 3 imes 24 + 2 imes 20 + 4 imes 25 + 6 imes 30 + 3 imes 24 + 6 imes 30 + 9 imes 36\&=16+40+72+40+100+180+72+180+324\&=1024end{split}$

可以看出計算相當繁瑣，嗯，我們來嘗試找找對應的核函數：

$egin{split}phi(x)cdot phi(y)&=[x_1x_1,x_1x_2,x_1x_3,x_2x_1,x_2x_2,x_2x_3,x_3x_1,x_3x_2,x_3x_3]^Tcdot [y_1y_1,y_1y_2,y_1y_3,y_2y_1,y_2y_2,y_2y_3,y_3y_1,y_3y_2,y_3y_3] \&= x_1y_1x_1y_1+x_1y_1x_2y_2+x_1y_1x_3y_3+x_2y_2x_1y_1+x_2y_2x_2y_2+x_2y_2x_3y_3\&+x_3y_3x_1y_1+x_3y_3x_2y_2+x_3y_3x_3y_3\&=(x_1y_1+x_2y_2+x_3y_3)^2\&=(x^Ty)^2\&=K(x,y)end{split}$

通過上面的推導，我們發現雖然維度轉化的過程較為繁瑣複雜，但是矢量點積的結果確實相當簡潔，這一次我們直接用核函數計算：

$egin{split}K(x,y)=K((1,2,3),(4,5,6))=(1 imes 4 + 2 imes 5 + 3 imes 6)^2=(32)^2=1024end{split}$

相比於從低維映射到高維空間再進行矢量積運算，核函數大大簡化了計算的過程，使得向更高維轉化變為了可能，我們不需要知道低維空間的數據是怎樣映射到高維空間的，我們只需要知道結果是怎麼計算出來的。

5. 介紹兩種核函數

在支持向量機中常用的幾種核函數是多項式型核（Polynomial Kernel）、徑向基函數核(Radial basis function kernel，又叫高斯核，簡稱 RBF）以及邏輯核（ Sigmoid Kernel）。

- 多項式型

$egin{split}K(mathbf{x},mathbf{y})&=(mathbf{x}^Tmathbf{y}+c)^d\end{split}$

如果 $mathbf{x},mathbf{y}$ 本身是 $k$ 維空間的向量，多項式展開後可知該核函數對應的空間維度為 $binom{k+d}{d}=mathrm{C}^{k+d}_d=O(k^d)$ ，計算複雜度隨著維數增加呈指數爆炸，但是用核函數進行計算的複雜度為 $O(k)$ 。

維數越高，偏差（bias）越低，方差（variance）越高，容易出現過擬合的情況，相反維數越低，偏差就會越大，但是方差會隨之減小，一般不宜選擇過高的維度，最適合的維度需要通過交叉驗證（cross validation）等方法來確定，關於方差和偏差的分析，可以看看這篇博文?? Understanding the Bias-Variance Tradeoff ??

- RBF

$K(mathbf {x} ,mathbf {y} )=e^{-{frac {||mathbf {x} -mathbf {y} ||^{2}}{2sigma^2}}}$

也可以寫成這樣的形式：

$K(mathbf {x} ,mathbf {y} )=e^{-gamma||mathbf {x} -mathbf {y} ||^{2}}$

高斯核是一個對應於無限空間的核函數，證明的方法非常簡單，對 $e^x$ 進行泰勒級數展開即可，為了書寫上的方便，這裡令 $sigma^2=1$ ：

$egin{split}K(mathbf {x} ,mathbf {y} )&=e^ {-{frac {||mathbf {x} -mathbf {y} ||^{2}}{2}}}\&=e^ {-{frac {||mathbf {x} ||^{2}}{2}}}e^ {-{frac {||mathbf {y} ||^{2}}{2}}}e^ {mathbf {x^Ty} }\&=e^ {-{frac {||mathbf {x} ||^{2}}{2}}}e^ {-{frac {||mathbf {y} ||^{2}}{2}}}sum_{n=0}^infty frac{ (mathbf {x^Ty})^n}{n!} \end{split}$

實際上我們無法給出映射到無限空間的函數 $phi$ ，更沒有辦法對兩個無限維度的矢量進行點乘運算，但是我們卻可以通過高斯核直接給出無限空間矢量積表達式，厲害了我的核！！！

高斯核的偏差和方差通過 $sigma^2$ 來控制， $sigma^2$ 越大偏差越大，方差越小，在下一部分相似度里進行解釋好像更加直觀。

6. 相似度：核函數的另一種理解

核函數還可以理解為兩個數據點的相似程度，兩個向量的點乘其實就是將其中一個向量投影到另一個向量上，重疊的長度越大，相似度越大，向量點乘的結果也越大。以高斯核為例， $K(mathbf {x} ,mathbf {y} )=e^{-{frac {||mathbf {x} -mathbf {y} ||^{2}}{2sigma^2}}}$ 衡量的是向量 $mathbf{x}$ 和 $mathbf{y}$ 在無限空間的相似度，當 $mathbf{x} =mathbf{y}$ 時， $K(mathbf {x} ,mathbf {y} )=1$ ，表示兩個向量完全重合，當 $||mathbf{x} -mathbf{y}|| oinfty$ 時， $K(mathbf {x} ,mathbf {y} )=0$ ，兩個向量之間的相似度很小；另一方面，當 $sigma^2$ 的值很小時，核函數的值越有可能趨向於0，向量 $mathbf{x}$ 和 $mathbf{y}$ 只有在相當接近的情況下才會被判別為相似，也就是說只有在 $mathbf{y}$ 鄰域相當小的範圍內才會被認為是相似於它的向量，這樣嚴苛的條件確保了高精度（低偏差）但是卻很容易過擬合（高方差）。

選擇合適的核函數並不是一件容易的事情，因為評估數據點之間的相似度往往需要專業領域的知識，幸運的是大多數情況下高斯核都能取得不錯的結果。核函數並不是支持向量機專用的技巧，任何演算法只要能寫成向量相乘的形式就可以運用核函數進行優化。

7. 怎麼構造核函數

一個正確的核函數對於數據相似度有著正確的描述，兩個矢量越接近重合，相似度越大，越接近正交相似度越小，多項式型核和高斯核都是正確的核函數，那麼對於核函數正確與否的一般標準是什麼呢？讓我們引入核矩陣。

定義一個 $m imes m$ 的矩陣 $K$

$K_{ij}=K(x^{(i)},x^{(j)})=phi(x^{(i)})cdot phi(x^{(j)})$

根據矢量點積的性質易得 $K(i,j)=K(j,i)$，顯然這是一個對稱矩陣，接下來我們證明它是一個半正定的對稱矩陣，對於任意的向量 $mathbf{z}$：

$egin{split}z^TKz&=sum_{i=1}^msum_{j=1}^mz_iK_{ij}z_j\&=sum_{i=1}^msum_{j=1}^mz_iphi(x^{(i)})^Tphi(x^{(j)})z_j\&=left(sum_{i=1}^m z_iphi(x^{(i)}) ight)^Tleft(sum_{j=1}^mz_jphi(x^{(j)}) ight)\&=left(sum_{i=1}^mz_iphi(x^{(i)}) ight)^2\&geqslant0end{split}$

我們證明了核函數的一個必要條件是對應的核矩陣為半正定對稱矩陣，事實上這個條件是充分且必要的，也就是 Mercer"s theorem：

一個核函數 $K: mathbb{R}^n imes mathbb{R}^n omathbb{R}$ 成立的充要條件為，對於任意的 $[x^{(1)},x^{(2)},x^{(3)}cdots x^{(m)}]$ ，其對應的核矩陣為半正定對稱矩陣。

關於 Mercer"s theorem 的證明超出了這篇文章的範疇，有興趣的同學可以自己查找相關資料或者戳這裡 CLT2008S-lecture18.pdf 了解如何證明其充分性。

8. 再說一點

原本想在這篇文章里寫完 SVM 的核函數和正則化的，但是第一篇和第二篇之間間隔太長，很多東西都得重新看一遍，寫核函數部分花了太長時間，還有一些東西尚未提及，比如正則項、不完美分割，當初是計劃在SVM 的第三篇介紹 SMO 演算法的，現在看來得重新規劃一下了??????。