# 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，并列舉了各自的優缺點并做了比較。對于不同的問題，應該選擇合適的核函數進行求解，以達到最佳的分類效果。 **_注明：_** 文章中所有的圖片均來自臺灣大學林軒田《機器學習技法》課程