台灣大學林軒田機器學習技法課程學習筆記3 -- Kernel Support Vector Machine

01-27

上節課我們主要介紹了SVM的對偶形式，即dual SVM。Dual SVM也是一個二次規劃問題，可以用QP來進行求解。之所以要推導SVM的對偶形式是因為：首先，它展示了SVM的幾何意義；然後，從計算上，求解過程「好像」與所在維度 $hat d$ 無關，規避了 $hat d$ 很大時難以求解的情況。但是，上節課的最後，我們也提到dual SVM的計算過程其實跟d^還是有關係的。那麼，能不能完全擺脫對 $hat d$ 的依賴，從而減少SVM計算量呢？這就是我們本節課所要講的主要內容。

Kernel Trick

我們上節課推導的dual SVM是如下形式：

其中 $alpha$ 是拉格朗日因子，共N個，這是我們要求解的，而條件共有N+1個。我們來看向量QD中的 $q_{n,m}=y_ny_mz_n^Tz_m$ ，看似這個計算與 $hat d$ 無關，但是 $z_n^Tz_m$ 的內積中不得不引入 $hat d$ 。也就是說，如果 $hat d$ 很大，計算 $z_n^Tz_m$ 的複雜度也會很高，同樣會影響QP問題的計算效率。可以說， $q_{n,m}=y_ny_mz_n^Tz_m$ 這一步是計算的瓶頸所在。

其實問題的關鍵在於zTnzm內積求解上。我們知道，z是由x經過特徵轉換而來：

$z_n^Tz_m=Phi(x_n)Phi(x_m)$

如果從x空間來看的話， $z_n^Tz_m$ 分為兩個步驟：1. 進行特徵轉換 $Phi(x_n)$ 和 $Phi(x_m)$ ；2. 計算 $Phi(x_n)$ 與 $Phi(x_m)$ 的內積。這種先轉換再計算內積的方式，必然會引入 $hat d$ 參數，從而在 $hat d$ 很大的時候影響計算速度。那麼，若把這兩個步驟聯合起來，是否可以有效地減小計算量，提高計算速度呢？

我們先來看一個簡單的例子，對於二階多項式轉換，各種排列組合為：

這裡提一下，為了簡單起見，我們把 $x_0=1$ 包含進來，同時將二次項 $x_1x_2$ 和 $x_2x_1$ 也包含進來。轉換之後再做內積並進行推導，得到：

其中 $x^Tx$ 是x空間中特徵向量的內積。所以， $Phi_2(x)$ 與 $Phi_2(x)$ 的內積的複雜度由原來的 $O(d^2)$ 變成 $O(d)$ ，只與x空間的維度d有關，而與z空間的維度 $hat d$ 無關，這正是我們想要的！

至此，我們發現如果把特徵轉換和z空間計算內積這兩個步驟合併起來，有可能會簡化計算。因為我們只是推導了二階多項式會提高運算速度，這個特例並不具有一般推論性。但是，我們還是看到了希望。

我們把合併特徵轉換和計算內積這兩個步驟的操作叫做Kernel Function，用大寫字母K表示。例如剛剛講的二階多項式例子，它的kernel function為：

$K_{Phi}(x,x)=Phi(x)^TPhi(x)$

$K_{Phi_2}(x,x)=1+(x^Tx)+(x^Tx)^2$

有了kernel function之後，我們來看看它在SVM裡面如何使用。在dual SVM中，二次項係數 $q_{n,m}$ 中有z的內積計算，就可以用kernel function替換：

$q_{n,m}=y_ny_mz_n^Tz_m=y_ny_mK(x_n,x_m)$

所以，直接計算出 $K(x_n,x_m)$ ，再代入上式，就能得到 $q_{n,m}$ 的值。

$q_{n,m}$ 值計算之後，就能通過QP得到拉格朗日因子 $alpha_n$ 。然後，下一步就是計算b（取 $alpha_n$ >0的點，即SV），b的表達式中包含z，可以作如下推導：

$b=y_s-w^Tz_s=y_s-(sum_{n=1}^Nalpha_ny_nz_n)^Tz_s=y_s-sum_{n=1}^Nalpha_ny_n(K(x_n,x_s))$

這樣得到的b就可以用kernel function表示，而與z空間無關。

最終我們要求的矩 $g_{SVM}$ 可以作如下推導：

$g_{SVM}(x)=sign(w^TPhi(x)+b)=sign((sum_{n=1}^Nalpha_ny_nz_n)^Tz+b)=sign(sum_{n=1}^Nalpha_ny_n(K(x_n,x))+b)$

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

那麼總結一下，引入kernel funtion後，SVM演算法變成：

分析每個步驟的時間複雜度為：

我們把這種引入kernel function的SVM稱為kernel SVM，它是基於dual SVM推導而來的。kernel SVM同樣只用SV（ $alpha_n$ >0）就能得到最佳分類面，而且整個計算過程中擺脫了 $hat d$ 的影響，大大提高了計算速度。

Polynomial Kernel

我們剛剛通過一個特殊的二次多項式導出了相對應的kernel，其實二次多項式的kernel形式是多種的。例如，相應係數的放縮構成完全平方公式等。下面列舉了幾種常用的二次多項式kernel形式：

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

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

通過改變不同的係數，得到不同的SVM margin和SV，如何選擇正確的kernel，非常重要。

歸納一下，引入 $zetageq 0$ 和 $gamma>0$ ，對於Q次多項式一般的kernel形式可表示為：

所以，使用高階的多項式kernel有兩個優點：

得到最大SVM margin，SV數量不會太多，分類面不會太複雜，防止過擬合，減少複雜度
計算過程避免了對 $hat d$ 的依賴，大大簡化了計算量。

順便提一下，當多項式階數Q=1時，那麼對應的kernel就是線性的，即本系列課程第一節課所介紹的內容。對於linear kernel，計算方法是簡單的，而且也是我們解決SVM問題的首選。還記得機器學習基石課程中介紹的奧卡姆剃刀定律（Occam』s Razor）嗎？

Gaussian Kernel

剛剛我們介紹的Q階多項式kernel的階數是有限的，即特徵轉換的 $hat d$ 是有限的。但是，如果是無限多維的轉換 $Phi(x)$ ，是否還能通過kernel的思想，來簡化SVM的計算呢？答案是肯定的。

先舉個例子，簡單起見，假設原空間是一維的，只有一個特徵x，我們構造一個kernel function為高斯函數：

$K(x,x)=e^{-(x-x)^2}$

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

將構造的K(x,x』)推導展開為兩個 $Phi(x)$ 和 $Phi(x)$ 的乘積，其中：

$Phi(x)=e^{-x^2}cdot (1,sqrt frac{2}{1!}x,sqrt frac{2^2}{2!}x^2,cdots)$

通過反推，我們得到了 $Phi(x)$ ， $Phi(x)$ 是無限多維的，它就可以當成特徵轉換的函數，且 $hat d$ 是無限的。這種 $Phi(x)$ 得到的核函數即為Gaussian kernel。

更一般地，對於原空間不止一維的情況（d>1），引入縮放因子 $gamma>0$ >0，它對應的Gaussian kernel表達式為：

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

那麼引入了高斯核函數，將有限維度的特徵轉換拓展到無限的特徵轉換中。根據本節課上一小節的內容，由K，計算得到 $alpha_n$ 和b，進而得到矩 $g_{SVM}$ 。將其中的核函數K用高斯核函數代替，得到：

$g_{SVM}(x)=sign(sum_{SV}alpha_ny_nK(x_n,x)+b)=sign(sum_{SV}alpha_ny_ne^{(-gamma||x-x_n||^2)}+b)$

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

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

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

從圖中可以看出，當 $gamma$ 比較小的時候，分類線比較光滑，當 $gamma$ 越來越大的時候，分類線變得越來越複雜和扭曲，直到最後，分類線變成一個個獨立的小區域，像小島一樣將每個樣本單獨包起來了。為什麼會出現這種區別呢？這是因為 $gamma$ 越大，其對應的高斯核函數越尖瘦，那麼有限個高斯核函數的線性組合就比較離散，分類效果並不好。所以，SVM也會出現過擬合現象， $gamma$ 的正確選擇尤為重要，不能太大。

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。首先，我們將特徵轉換和計算內積的操作合併到一起，消除了 $hat d$ 的影響，提高了計算速度。然後，分別推導了Polynomial Kernel和Gaussian Kernel，並列舉了各自的優缺點並做了比較。對於不同的問題，應該選擇合適的核函數進行求解，以達到最佳的分類效果。

註明：

文章中所有的圖片均來自台灣大學林軒田《機器學習技法》課程

我的CSDN博客地址：

台灣大學林軒田機器學習技法課程學習筆記3 -- Kernel Support Vector Machine