支持向量機SVM總結之核方法

05-17

支持向量機SVM總結之核方法

來自專欄我的ai之路

上一章節最後提到了三個問題：

1、計算樣本x之間的內積，計算量還是很大的，有沒有什麼方法減小計算量呢？

2、若大部分樣本數據在當前維度上不是線性可分的怎麼辦？

3、如果出現少量異常點怎麼辦？

本章著重總結支持向量機中如何使用核方法來解決前面兩個問題。注意，核方法本身與支持向量機沒有強相關的關係，是兩個獨立的知識。核方法本身是一種解決非線性模式分析問題的一種方法，而SVM通過使用核方法，能夠對一些在某維空間上不是線性可分的數據點進行分類。由於核方法的知識點很龐大，因此本文只是結合SVM，總結SVM中使用到的核方法的知識，有關於核方法的本質以及其相關知識體系待以後有餘力再總結。

前一章節中，我們推導得到SVM的對偶問題形式，如下：

上式中，只用到了原始的特徵集X，但是現實情況下，為了表示數據的一些複雜的屬性和特徵，可能要對一些特徵做線性的組合，比如使用諸如 $x^2,x^3$ 這樣的高次多項式作為高級特徵，與原來的原始特徵x組合在一起，組成新的特徵集，然後代替原來的原始特徵到計算式中，即我們定義 $phi$ 為一個特徵映射，表示原始特徵到新特徵的具體映射關係，如：

將 $phi$ 代替x，代入到SVM中的對偶問題形式，得到：

我們定義內積 $<phi(x),phi(z)>$ 為kernel（核）K：

繼而可以使用核K(x,z)來代替對偶問題中的所有特徵數據的內積。現在，只要給定映射 $phi$ ，我們可以很容易得計算出K，而且計算K的成本通常都比較小，即使在 $phi(x)$ 本身由於維數很高的情況下計算量龐大時，K的計算成本也小於單獨計算 $phi(x)$ 。因此，只要在給定映射 $phi$ 的形式，但是不需要計算 $phi(x)$ ，只要演算法能夠有效率得去計算K，那麼就可以讓我們的SVM演算法即使在高維特徵數據下也能有很好的性能，同時模型學習能力也能得到保證。

舉例說明：給定 $x,z inRe^n$ ,有二階多項式核函數：

為什麼稱為多項式核方法？我們可以將該核函數拆開，重新組合，得到：

因為

因此映射 $phi$ 顯而易見是原始特徵的兩兩線性組合的形式，如下：

可以知道直接計算 $phi(x)$ 需要的計算量為 $O(n^2)$ ,而計算

只需要 $O(n)$ 的計算量。

上述例子只是多項式核函數的一個特例，若核函數再帶一個常數項c，則得到如下核函數：

它對應的映射 $phi$ 應當是除了特徵之間的兩兩組合外，還有單獨的特徵的常數倍數，以及常數c，具體如下：

將上述核函數推廣到一般情況，即 $K(x,z)=(x^Tz+c)^d$ ，即d階多項式核函數，可以將原始特徵映射到更高維的特徵空間中，同時不需要去計算 $phi(x)$ ，而是直接計算K的值（計算成本與特徵維數n成線性關係），就可以讓模型得到充分學習。

有一種對核方法的在SVM中的應用的理解，即核方法能夠間接表達出兩個特徵之間的相似度，即兩個特徵如何非常相似，即對應的特徵映射 $phi(x)$ 也非常接近，在向量空間中表示為兩個向量非常接近，因此其內積應當比較大，從而得到K也應當比較大，反之亦然。因此可以說核函數再一定程度上反映了特徵之間的相似度。下面介紹一種非線性的核方法，能夠在一定程度上衡量出特徵之間的相似度。

有核方法如下：

可以看到這個核方法（其實就是sklearn中SVM核方法裡面的RBF，Radial Basis Function）有以下特點：

與之前的線性核方法不同，這個是非線性的核方法，加入了自然底數e的轉換
通過一個距離的度量 $||x-z||^2$ ,表示兩個特徵之間的相似度。當兩個特徵不相似，即離得很遠，則exp()內部應當趨向於負無窮，因此K趨向於0；當兩個特徵相似時，即離得近，exp()內部應當趨向於0，因此K趨向於1。
很明顯，這個核方法的表示方法與概率統計中的高斯分布很相似，因此該核方法又稱為高斯核。
這個核函數能夠將原始特徵映射到無限維的特徵空間。

上面講了幾個核函數，到底什麼樣的函數才能作為核函數呢？換個說法，即怎麼判斷一個kernel是有效的？

首先，定義一個kernel matrix，其中，矩陣元素 $K_{ij}=K(x^{(i)},x^{(j)})$ 。核矩陣表示了每個樣本對應的核。假設當前的核函數是有效的，那麼有如下等式：

可以得到，核矩陣首先是一個對稱矩陣。其次定義 $phi_{k}(x)$ 為向量 $phi(x)$ 的第k維元素。對於任意向量z，有如下式子：

由半正定矩陣定義可知，核矩陣同樣是一個半正定的矩陣（若沒有等號的話，則是嚴格正定）。因此一個核函數如果是有效的，那麼他對應樣本的核矩陣應當是對稱的且是半正定的。這是一個必要條件。其實他也是一個充分條件，這個充分必要條件由一個定理給出，即mercer定理。關於mercer定理的完全證明，其實還要用到L2範數，以及再生希爾伯特空間等相關的凸優化理論中的知識，具體可看維基百科中的內容：Mercers theorem（其實我也不太會證明，如果有大牛可以清晰的推導的話，請告知我，無比感謝！）

其實在實際運用中，我們通常先使用線性的核函數對數據進行處理，線性核通常計算速度會快一點，能夠得到一個baseline，然後再可以使用一些非線性的核比如RBF，它能夠應對數據邊界不是規則的數據。有關核函數解決數據線性不可分的效果，可以看如下截圖：

可以看到本身二維中的兩種不同數據，無法用直接進行分隔，而通過映射到三維中，可以找到一個平面將兩種數據分隔。

reference:

cs229 notes

機器學習有很多關於核函數的說法，核函數的定義和作用是什麼？?

www.zhihu.com核函數的有效性判定 - CSDN博客?

blog.csdn.net

其實遇到數據線性不可分的問題，或者說存在一些異常點和噪點不能完美分隔時，還有一種方法，即引入懲罰項（相當於regularization），使得我們的模型不是以完美分隔所有數據為目標，而是允許有一些點可以分錯。此時SVM有hard模式轉變為soft模式，相當於更懂得變通。下一章將重點總結這個模型。