機器學習技法筆記3：核函數SVM

02-28

從上篇可知，對偶SVM展示了SVM的幾何意義，同時求解過程「好像」與所在維度d^無關，規避了d^很大時難以求解的情況，但是在最終的推導式中我們發現其實在計算Qnm時任然沒有擺脫對d^的依賴。

關鍵是 $q_{n,m}=y_ny_mz_n^Tz_n$ 這一步的計算，而這一步的關鍵又是在Zn內積的求解上。

z由x經過特徵轉換而來，即 $z_n^Tz_n=Phi(x_n)Phi(x_m)$ ，求解過程又分為兩步：先轉換再內積。現在為了提高計算速度，我們想辦法將這兩步聯合起來。

核函數

對於一個二次多項式的轉換，各種組合為（為了簡單起見，我們把x0=1包含進來，同時將二次項x1x2和x2x1也包含進來）

轉換之後做內積並進行推導得出：

其中 $x^Tx$ 是x空間中特徵向量的內積。所以，Φ2(x)與Φ2(x′)的內積的複雜度由原來的O( $d^2$ )變成O(d)？？？，只與x空間的維度d有關，而與z空間的維度d^（複習一下z空間的維度）無關。至此，我們發現如果把特徵轉換和z空間計算內積這兩個步驟合併起來，有可能會簡化計算。（何為合併，何為不合併：沒有真正轉換成z）

我們把合併特徵轉換和計算內積這兩個步驟的操作叫做Kernel Function（核函數），核函數與二次多項式的核函數公式如下：

所以，對偶svm中求Qn,m的一步可以表示為：

進而，對b的求解也可以與z無關：

最終， $g_{SVM}$ 可以表示為：

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

更高次的核函數

二次多項式的kernel形式是多種的，相應係數 $gamma$ （自由度）的放縮可以構成完全平方公式。如下常用的二次多項式kernel形式：

這三種不同的二次核函數從某種角度說其實是一樣的。因為都是二次轉換，對應到同一個z空間。但是，它們係數不同，內積也就不同，所以距離也就不同，就會得到不同的寬邊，也就會得到不同的SVM分界線。通常，第三種Φ2(x)（綠色標記）簡單一些，更加常用：

對於Q次多項式的一般核函數形式可以表示為：

注意的是，當多項式階數Q=1時，那麼對應的kernel就是線性的，即技法1所介紹的內容。對於線性核函數，計算簡單，也是我們解決SVM問題的首選。

高斯核函數

先說一下，前面的論述可看成從轉換推導至核函數，其實，我們可以從核函數推導至轉換 $Phi(x)$ 。現在我們以這個思路，推導出一個無限維度的轉換和核函數。

假設原空間是一維空間，構造一個核函數為高斯函數：

從此核函數反推證明是無限維度的轉換（巧妙運用了泰勒展開的無限項類比成無限維度）：

同樣，對於多維的原空間，我們引入縮放因子 $gamma$ >0，則核函數可以表示為

我們將此核函數代入 $g_{SVM}$ 表達式有：

gSVM有n個高斯函數線性組合而成，其中n是支持向量的個數。每個高斯函數的中心都是對應的SV。我們也把高斯核函數稱為徑向基函數（Radial Basis Function, RBF）。

總結：kernel SVM可以獲得寬邊界的超平面，並且可以通過高階的特徵轉換使Ein儘可能小。核函數的引入大大簡化了對偶SVM的計算量。而且高斯核函數能將特徵轉換擴展到無限維，並使用有限個SV(支持向量) 的高斯函數構造出矩gSVM。

三種核函數的比較

線性核函數，最基本的核函數，平面上的直線，三維的面，多維的超平面，可以使用對偶svm利用二次規劃庫直接計算。這是我們第一個需要考慮的，簡單有效，但是如果是線性不可分的訓練集則無法使用。

多項式核函數，優點是階數Q可以靈活設置；缺點是當Q很大時，K的數值範圍波動很大，而且參數個數較多，難以選擇合適的值，超平面是多項式的曲面
高斯核函數，優點是邊界更加複雜多樣，能最準確地區分數據樣本，數值計算K值波動較小，而且只有一個參數，容易選擇；缺點是由於特徵轉換到無限維度中，w沒有求解出來，而且可能會發生過擬合。

實際上核函數代表的是兩個樣本x和x』，特徵變換後的相似性即內積。

我們可以自己構造一個核函數，但是往往比較複雜，因為我們要證明k是對稱的、K是半正定的這兩個充分必要條件。所以，我們往往是用已經有的有效的核函數去解決問題。

題圖：xxx