SVM推導過程

最近在學習關於SVM的相關知識，偶然看了看李航的《統計學習方法》，茅塞頓開，驚為天人。在此記下一些步驟。

對於超平面 ，先有幾個定義：

1、函數間隔(functional margin)：

對於每個樣本點而言，函數間隔為

對於所有樣本點而言，它們的函數間隔為

2、幾何間隔(geometric margin)：

對於每個樣本點而言，幾何間隔為

對於所有樣本點而言，它們的幾何間隔為

SVM的目的是得到一個超平面，可以使所有樣本點分類正確，並使該平面對所有樣本點的幾何間隔最大，即：

再根據幾何間隔和函數間隔的關係，問題可以轉化成：

這時用到一個技巧。若將 等比例放縮為 ，會形成一個新的問題，可以明顯地看出在新的問題中，取 ，則可以證明這兩個問題的優化目標和條件其實是一致的，也就是說新的問題和原問題是等價的。從幾何的角度理解，想像一個超平面將若干樣本點分離開，這時若將 等比例放縮為 ，超平面仍然不變，樣本點也依舊不變，只有函數間隔 變化了，變成了 。這就說明可以通過等比例放縮 將函數間隔 調整成任意值，且保持該優化問題的結果（即所求超平面，因為是等比例放縮）不變。所以對於 ，都可以通過等比例放縮 來使得 ，並保持所求超平面不變。所以上述問題又可以轉化成：

因為在機器學習的任務中，我們常常是最小化某個量，所以將上式等價於：

這就是我們最終的優化目標。

另外，可以證明滿足上述優化目標的結果是存在且唯一的。

1.存在性：

由於假設了所有樣本點線性可分，故一定存在滿足限制條件的平面。另外， 存在下界，故滿足上述優化目標的結果一定存在。

2.唯一性：

假設有多個超平面滿足上述優化目標。任取其二，不妨分別設為 、 。由於它們均滿足目標函數是最小的，故：

即：

這時用到一個技巧來證明 ：令 。再設 。根據優化目標可知 ，所以就有

所以

根據三角不等式的等式成立條件，可以得到

又由於 ，所以 。若 ，此時 ，由 形成的超平面顯然不滿足優化條件，故捨去，所以 ，即：

下面接著證 ：令超平面 這時用到一個技巧——取向量機。設 分別是使得 的約束條件在超平面一側取等號的樣本點。則有：

又因為 是樣本點之一，所以一定滿足 的優化條件，故有：

所以有

同理，根據

所以有

故

所以

由上述證明可以看出，滿足優化條件的結果只有一個超平面。

再介紹一下關於拉格朗日對偶性。

假設現有原始問題：

引入廣義拉格朗日函數：

可以看出，若不滿足原始問題的限制條件

即 或 ，都會使得 。

但是如果滿足原始問題的限制條件，可以發現

因為要使得 最大，而 ，可以令 ，使得 達到最大。

根據上面的結論，原始問題可以等價轉化成拉格朗日極小極大問題：

我們再看極小極大問題的對偶問題——極大極小問題：

注意此處對 的限制條件仍然沒變。

下面給出幾個定理，討論極小極大問題與其對偶問題之間的關係。

定理1：如果函數 是凸函數， 是仿射函數，並且不等式約束 是嚴格可行的，即存在 ，對所有 有 ，那麼存在 ，使 是原始問題的解， 是對偶問題的解。

定理2：如果函數 是凸函數， 是仿射函數，並且不等式約束 是嚴格可行的，即存在 ，對所有 有 ，那麼 和 分別是原始問題和對偶問題的解的充分必要條件是 滿足KKT條件：

根據上述定理，就可以通過求解對偶問題來解出拉格朗日極小極大問題。

現在我們開始求解問題：

把該優化問題看成原始問題，得到廣義拉格朗日函數：

原始問題便可轉化成等價問題：

要求解該問題，可先求解對偶問題：

先求 ，即

要求極小值點，讓目標函數對各個變數偏導為零，有：

可得

代入上式得：

接著再求出 即可。

這裡用到了SMO演算法。

推薦閱讀：