機器學習技法筆記2：對偶支持向量機

02-27

如果需要特徵轉換

上節課我們主要介紹了線性支持向量機（Linear Support Vector Machine）。Linear SVM的目標是找出最「胖」的分割線進行正負類的分離，方法是使用二次規劃來求出分類線。本節課將從另一個方面入手，研究對偶支持向量機（Dual Support Vector Machine），嘗試從新的角度計算得出分類線，推廣SVM的應用範圍。

對於非線性SVM，我們通常可以使用非線性變換將變數從x域轉換到z域中。然後，在z域中，使用線性SVM解決問題即可。特徵轉換下，求解QP問題在z域中的維度設為d^+1，如果模型越複雜，則d^+1越大，相應求解這個QP問題也變得很困難。通常，這個z域的維度會比較大。當d^無限大的時候，問題將會變得難以求解，所以我們設計一種方法使SVM的求解過程不依賴d^。我們把問題轉化為對偶問題（Equivalent SVM），同樣是二次規劃，只不過變數個數變成N個，有N+1個限制條件，移除計算上對d的依賴。

帶有特徵轉換的求解步驟如下：

對偶支持向量機

對偶：將原始svm的與d有關轉換為與d無關只與N有關。

原始svm和現在svm的比較：

只與訓練集的數量有關，與轉換到的空間無關。兩者有個相對應的關係，所以叫對偶問題

如何把問題轉化為對偶問題，林大佬說了，其中的數學推導非常複雜，不做詳細數學論證，但是會從概念和原理上進行簡單的推導。

首先，先回憶一下正則化時的計算方法是將有條件下的min轉換成無條件下的min：

從而得到的最優解為：

在正則化問題中，λ是已知常量，求解過程變得容易。那麼，對於dual SVM問題，可以引入λ，將條件問題轉換為非條件問題，因為svm有N個條件，所以λ是未知參數，個數是N，需要對其進行求解。

如何將有條件轉換為無條件呢？

我們令拉格朗日因子為 $alpha_n$ ，構造出函數

函數第一項是SVM的目標，第二項是SVM的條件和拉格朗日因子αn的乘積之和。這個函數稱為拉格朗日函數，其中包含三個參數：b，w，α，於是我們將svm目標轉換成：

原始svm

對偶svm

下面證明此函數的正確性和可行性：

對偶svm函數的意義是：對每一對固定的b和w，我們調試出一個 $alpha$ （>=0），使得滿足括弧中的最大值，對所有的b和w，我們都能計算出一個最大值，然後在這些最大值中選擇一個最小值。即先對a做最大化，再對(b,w)做最小化。
每一對(b，w)，都有可能是好的或者壞的。壞的情況即是不滿足原始svm的條件限制。對於一個壞的(b，w)， $1/2w^Tw+sum_{n=1}^{N}{alpha_n (1-y_n(w^Tz_n+b))}$ 最大值是 $infty$ ，因為 $1-y_n(w^Tz_n+b)$ 為正，而只要 $alpha_n$ $infty$ ，則值 $infty$
對於好的（b，w）， $1/2w^Tw+sum_{n=1}^{N}{alpha_n (1-y_n(w^Tz_n+b))}$ 的最大值是 $alpha_n$ =0時取得，即max=1/2wTw
而max= $infty$ 時的值會被接下來的min過濾掉

下圖為一個直觀的理解：

喝口水，繼續說。

現在，我們已經將SVM問題轉化為與拉格朗日因子αn有關的最大最小值形式。已知αn≥0，那麼對於任何固定的α′，且α′n≥0，一定有如下不等式成立：

那麼，對於所有的αn≥0，取最大化，

等式兩邊可以看到 min和max交換，所以這個稱作拉格朗日對偶問題。

在二次規劃QP問題中，如果滿足函數是凸的、函數有解、條件是線性的，不等式關係就變成強對偶關係，≥變成=，即一定存在滿足條件的解(b,w,α)，使等式左邊和右邊都成立，SVM的解就轉化為右邊的形式。svm對偶問題的解已經轉化為無條件的形式：

則L的最小值是在谷底，即梯度為0的點，梯度為0我們則有：

我們代入以上可以消去b，則有：

繼續，我們計算對w的偏微分：

我們把 $w=sum_{n-1}^{N}{alpha_ny_nz_n}$ 再代入消去係數（ $alpha_ny_n(w^Tz_n)=w^T(alpha_ny_nz_n)=w^Tw$ ），然後再消去w，最後能消去min，則有：

這是一個只有 $alpha$ 的最大化問題

總結一個這個最大化問題的所有限制條件（稱為KKT條件）：

求解對偶svm

最後，我們最後一次簡化上面的公式，得到一個二次規劃問題：

N個條件對應N個 $alpha$ ，所以有N個變數，N+1個條件，現在求解標準二次規劃問題的係數：

注意的是，qn,m=ynymznzm，大部分值是非零的，稱為dense（稠密矩陣）。當N很大的時候，對應的Q的計算量將會很大，存儲空間也很大。所以一般情況下，對dual SVM問題的矩陣Q，需要使用svm定製的二次規劃庫求解。

求出 $alpha$ 後，我們根據KKT條件反推出w和b：

$w=sum_{n=1}^{N}{alpha_ny_nz_n}$
根據條件 $alpha_n(1-y_n(w^Tz_n+b))=0$ ，我們找出一個不等於0 的 $alpha_n$ 即可求出b
滿足αn>0的點即表示 $1-y_n(w^Tz_n+b)=0$ ，所以一定落在胖胖的邊界上，這些點就是支撐向量。

一些雜話

w和b只跟支持向量有關，也即證實了之前說分解面只由支持向量決定

我們現在介紹了兩種形式的SVM，一種是原始SVM，另一種是對偶SVM。原始SVM有d^+1個參數，有N個限制條件。當d^+1很大時，求解困難。而對偶SVM有N個參數，有N+1個限制條件。當數據量N很大時，也同樣會增大計算難度。兩種形式都能得到w和b，求得最優超平面。通常情況下，如果N不是很大，一般使用對偶SVM來解決問題。
其實對偶SVM的目的是為了避免計算過程中對d^的依賴，而只與N有關。但是，對偶SVM是否真的消除了對d^的依賴呢？其實並沒有。因為在計算 $q_{n,m}=y_ny_mz_n^Tz_m$ 的過程中，由z向量引入了d^，實際上複雜度已經隱藏在計算過程中了。所以我們的目標並沒有實現。要進一步避開這個計算的解決辦法請見下回分解。
數學太牛b了，昨天今天的推導里我驚嘆了n次的媽賣批。

題圖：xxxx 2017年11月9日17:57:18