# 3 -- Kernel Support Vector Machine
上節課我們主要介紹了SVM的對偶形式,即dual SVM。Dual SVM也是一個二次規劃問題,可以用QP來進行求解。之所以要推導SVM的對偶形式是因為:首先,它展示了SVM的幾何意義;然后,從計算上,求解過程“好像”與所在維度無關,規避了很大時難以求解的情況。但是,上節課的最后,我們也提到dual SVM的計算過程其實跟還是有關系的。那么,能不能完全擺脫對的依賴,從而減少SVM計算量呢?這就是我們本節課所要講的主要內容。
### **Kernel Trick**
我們上節課推導的dual SVM是如下形式:

其中是拉格朗日因子,共N個,這是我們要求解的,而條件共有N+1個。我們來看向量中的,看似這個計算與無關,但是的內積中不得不引入。也就是說,如果很大,計算的復雜度也會很高,同樣會影響QP問題的計算效率。可以說,這一步是計算的瓶頸所在。
其實問題的關鍵在于內積求解上。我們知道,z是由x經過特征轉換而來:

如果從x空間來看的話,分為兩個步驟:1\. 進行特征轉換和;2\. 計算與的內積。這種先轉換再計算內積的方式,必然會引入參數,從而在很大的時候影響計算速度。那么,若把這兩個步驟聯合起來,是否可以有效地減小計算量,提高計算速度呢?
我們先來看一個簡單的例子,對于二階多項式轉換,各種排列組合為:

這里提一下,為了簡單起見,我們把包含進來,同時將二次項和也包含進來。轉換之后再做內積并進行推導,得到:

其中是x空間中特征向量的內積。所以,與的內積的復雜度由原來的變成,只與x空間的維度d有關,而與z空間的維度無關,這正是我們想要的!
至此,我們發現如果把特征轉換和z空間計算內積這兩個步驟合并起來,有可能會簡化計算。因為我們只是推導了二階多項式會提高運算速度,這個特例并不具有一般推論性。但是,我們還是看到了希望。
我們把合并特征轉換和計算內積這兩個步驟的操作叫做Kernel Function,用大寫字母K表示。例如剛剛講的二階多項式例子,它的kernel function為:


有了kernel function之后,我們來看看它在SVM里面如何使用。在dual SVM中,二次項系數中有z的內積計算,就可以用kernel function替換:

所以,直接計算出,再代入上式,就能得到的值。
值計算之后,就能通過QP得到拉格朗日因子。然后,下一步就是計算b(取>0的點,即SV),b的表達式中包含z,可以作如下推導:

這樣得到的b就可以用kernel function表示,而與z空間無關。
最終我們要求的矩可以作如下推導:

至此,dual SVM中我們所有需要求解的參數都已經得到了,而且整個計算過程中都沒有在z空間作內積,即與z無關。我們把這個過程稱為kernel trick,也就是把特征轉換和計算內積兩個步驟結合起來,用kernel function來避免計算過程中受的影響,從而提高運算速度。

那么總結一下,引入kernel funtion后,SVM算法變成:

分析每個步驟的時間復雜度為:

我們把這種引入kernel function的SVM稱為kernel SVM,它是基于dual SVM推導而來的。kernel SVM同樣只用SV(>0)就能得到最佳分類面,而且整個計算過程中擺脫了的影響,大大提高了計算速度。
### **Polynomial Kernel**
我們剛剛通過一個特殊的二次多項式導出了相對應的kernel,其實二次多項式的kernel形式是多種的。例如,相應系數的放縮構成完全平方公式等。下面列舉了幾種常用的二次多項式kernel形式:

比較一下,第一種(藍色標記)和第三種(綠色標記)從某種角度來說是一樣的,因為都是二次轉換,對應到同一個z空間。但是,它們系數不同,內積就會有差異,那么就代表有不同的距離,最終可能會得到不同的SVM margin。所以,系數不同,可能會得到不同的SVM分界線。通常情況下,第三種(綠色標記)簡單一些,更加常用。

不同的轉換,對應到不同的幾何距離,得到不同的距離,這是什么意思呢?舉個例子,對于我們之前介紹的一般的二次多項式kernel,它的SVM margin和對應的SV如下圖(中)所示。對于上面介紹的完全平方公式形式,自由度,它的SVM margin和對應的SV如下圖(左)所示。比較發現,這種SVM margin比較簡單一些。對于自由度,它的SVM margin和對應的SV如下圖(右)所示。與前兩種比較,margin和SV都有所不同。

通過改變不同的系數,得到不同的SVM margin和SV,如何選擇正確的kernel,非常重要。
歸納一下,引入和,對于Q次多項式一般的kernel形式可表示為:

所以,使用高階的多項式kernel有兩個優點:
* **得到最大SVM margin,SV數量不會太多,分類面不會太復雜,防止過擬合,減少復雜度**
* **計算過程避免了對的依賴,大大簡化了計算量。**

順便提一下,當多項式階數Q=1時,那么對應的kernel就是線性的,即本系列課程第一節課所介紹的內容。對于linear kernel,計算方法是簡單的,而且也是我們解決SVM問題的首選。還記得機器學習基石課程中介紹的奧卡姆剃刀定律(Occam’s Razor)嗎?
### **Gaussian Kernel**
剛剛我們介紹的Q階多項式kernel的階數是有限的,即特征轉換的是有限的。但是,如果是無限多維的轉換,是否還能通過kernel的思想,來簡化SVM的計算呢?答案是肯定的。
先舉個例子,簡單起見,假設原空間是一維的,只有一個特征x,我們構造一個kernel function為高斯函數:

構造的過程正好與二次多項式kernel的相反,利用反推法,先將上式分解并做泰勒展開:

將構造的K(x,x’)推導展開為兩個和的乘積,其中:

通過反推,我們得到了,是無限多維的,它就可以當成特征轉換的函數,且是無限的。這種得到的核函數即為Gaussian kernel。
更一般地,對于原空間不止一維的情況(d>1),引入縮放因子,它對應的Gaussian kernel表達式為:

那么引入了高斯核函數,將有限維度的特征轉換拓展到無限的特征轉換中。根據本節課上一小節的內容,由K,計算得到和b,進而得到矩。將其中的核函數K用高斯核函數代替,得到:

通過上式可以看出,有n個高斯函數線性組合而成,其中n是SV的個數。而且,每個高斯函數的中心都是對應的SV。通常我們也把高斯核函數稱為徑向基函數(Radial Basis Function, RBF)。

總結一下,kernel SVM可以獲得large-margin的hyperplanes,并且可以通過高階的特征轉換使盡可能地小。kernel的引入大大簡化了dual SVM的計算量。而且,Gaussian kernel能將特征轉換擴展到無限維,并使用有限個SV數量的高斯函數構造出矩。

值得注意的是,縮放因子取值不同,會得到不同的高斯核函數,hyperplanes不同,分類效果也有很大的差異。舉個例子,分別取1, 10, 100時對應的分類效果如下:

從圖中可以看出,當比較小的時候,分類線比較光滑,當越來越大的時候,分類線變得越來越復雜和扭曲,直到最后,分類線變成一個個獨立的小區域,像小島一樣將每個樣本單獨包起來了。為什么會出現這種區別呢?這是因為越大,其對應的高斯核函數越尖瘦,那么有限個高斯核函數的線性組合就比較離散,分類效果并不好。所以,SVM也會出現過擬合現象,的正確選擇尤為重要,不能太大。
### **Comparison of Kernels**
目前為止,我們已經介紹了幾種kernel,下面來對幾種kernel進行比較。
首先,Linear Kernel是最簡單最基本的核,平面上對應一條直線,三維空間里對應一個平面。Linear Kernel可以使用上一節課介紹的Dual SVM中的QP直接計算得到。

Linear Kernel的優點是計算簡單、快速,可以直接使用QP快速得到參數值,而且從視覺上分類效果非常直觀,便于理解;缺點是如果數據不是線性可分的情況,Linear Kernel就不能使用了。

然后,Polynomial Kernel的hyperplanes是由多項式曲線構成。

Polynomial Kernel的優點是階數Q可以靈活設置,相比linear kernel限制更少,更貼近實際樣本分布;缺點是當Q很大時,K的數值范圍波動很大,而且參數個數較多,難以選擇合適的值。

對于Gaussian Kernel,表示為高斯函數形式。

Gaussian Kernel的優點是邊界更加復雜多樣,能最準確地區分數據樣本,數值計算K值波動較小,而且只有一個參數,容易選擇;缺點是由于特征轉換到無限維度中,w沒有求解出來,計算速度要低于linear kernel,而且可能會發生過擬合。

除了這三種kernel之外,我們還可以使用其它形式的kernel。首先,我們考慮kernel是什么?實際上kernel代表的是兩筆資料x和x’,特征變換后的相似性即內積。但是不能說任何計算相似性的函數都可以是kernel。有效的kernel還需滿足幾個條件:
* **K是對稱的**
* **K是半正定的**
這兩個條件不僅是必要條件,同時也是充分條件。所以,只要我們構造的K同時滿足這兩個條件,那它就是一個有效的kernel。這被稱為Mercer 定理。事實上,構造一個有效的kernel是比較困難的。

### **總結**
本節課主要介紹了Kernel Support Vector Machine。首先,我們將特征轉換和計算內積的操作合并到一起,消除了的影響,提高了計算速度。然后,分別推導了Polynomial Kernel和Gaussian Kernel,并列舉了各自的優缺點并做了比較。對于不同的問題,應該選擇合適的核函數進行求解,以達到最佳的分類效果。
**_注明:_**
文章中所有的圖片均來自臺灣大學林軒田《機器學習技法》課程
- 臺灣大學林軒田機器學習筆記
- 機器學習基石
- 1 -- The Learning Problem
- 2 -- Learning to Answer Yes/No
- 3 -- Types of Learning
- 4 -- Feasibility of Learning
- 5 -- Training versus Testing
- 6 -- Theory of Generalization
- 7 -- The VC Dimension
- 8 -- Noise and Error
- 9 -- Linear Regression
- 10 -- Logistic Regression
- 11 -- Linear Models for Classification
- 12 -- Nonlinear Transformation
- 13 -- Hazard of Overfitting
- 14 -- Regularization
- 15 -- Validation
- 16 -- Three Learning Principles
- 機器學習技法
- 1 -- Linear Support Vector Machine
- 2 -- Dual Support Vector Machine
- 3 -- Kernel Support Vector Machine
- 4 -- Soft-Margin Support Vector Machine
- 5 -- Kernel Logistic Regression
- 6 -- Support Vector Regression
- 7 -- Blending and Bagging
- 8 -- Adaptive Boosting
- 9 -- Decision Tree
- 10 -- Random Forest
- 11 -- Gradient Boosted Decision Tree
- 12 -- Neural Network
- 13 -- Deep Learning
- 14 -- Radial Basis Function Network
- 15 -- Matrix Factorization
- 16(完結) -- Finale