攀登傳統機器學習的珠峰-SVM (下)

05-23

攀登傳統機器學習的珠峰-SVM (下)

來自專欄人工智慧隨筆

本節是SVM系列三部曲的最後一部分。主要講了SMO演算法，SVR演算法，sklearn中SVM演算法的參數介紹和調參建議。網上有很多SMO演算法的文章，有的要麼講解的比較淺顯，要麼就是一堆公式的堆砌，讓人看完之後會有各種疑問，比如：SMO演算法和EM演算法有什麼異同點？坐標上升(下降)法與梯度下降(上升)法有什麼異同點？什麼時候用坐標上升(降法)？什麼時候用梯度下降法(上升)？SMO為什麼採用兩個變數迭代，而不是一個，三個，四個或者更多？SMO演算法兩個變數的選擇是怎麼來的？SMO演算法的基本步驟是什麼？以及SVR和SVC都有哪些具體的區別？有沒有詳細的物理直觀的解釋和公式比較？

針對以上問題，本文都已經詳細作答，希望閱讀完本SVM三部曲的朋友能夠對SVM有更深的了解和認識。文章中夾雜著很多自己的思考和理解，如有不正確的地方，請多多指正，也希望志同道合之士能夠多多交流。

SMO (序列最小優化) 演算法原理

友情提示：前方高能，公式推導特別多！！！

1. 回顧SVM優化目標

我們首先回顧下SVM的目標函數：

$underbrace{ min }_{alpha} frac{1}{2}sumlimits_{i=1}^{m} sumlimits_{j=1}^{m} alpha_ialpha_jy_iy_jK(x_i,x_j) - sumlimits_{i=1}^{m}alpha_i \ s.t. ; sumlimits_{i=1}^{m}alpha_iy_i = 0 \ 0 leq alpha_i leq C ; , ; ; i=1,2,cdots,m$

向量 $α$ 是拉格朗日運算元，每個樣本 $(x_i, y_i)$ 都對應一個向量分量 $alpha_i$ 。

根據上節課的我們需要先求解 $α$ ，然後根據 $alpha$ 再求解分類決策函數的參數 $w$ 和 $b$ 。SMO演算法的作用就是高效求解參數向量 $α$ 的值 $α^? = (α^? _1,α^? _2,cdots, α^? _m)$ 。

KKT約束條件（回想一下上節課的那一幅圖）：

$alpha_{i}^{*} = 0 Rightarrow y_ih(x_i) geq 1 \ 0 < alpha_{i}^{*} < C Rightarrow y_ih(x_i) = 1 \ alpha_{i}^{*}= C Rightarrow y_ih(x_i) leq 1$

其中 $h(x) = w^{*} ullet phi(x) + b =sumlimits_{j=1}^{m}alpha_j^{*}y_jK(x, x_j)+ b^{*}$ 為預測值。

2. SMO演算法的基本思想

SMO 是微軟研究院的 John C. Platt 在《Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines》一文中提出的，其基本思想是：把含有 m 個參數的原始問題分解成多個子問題分別求解，每個子問題只需要求解兩個參數，這樣SMO演算法就將一個複雜的優化問題轉化為一個比較簡單的兩變數優化問題。每次啟發式選擇兩個變數進行優化，不斷循環，直到達到函數最優值。

什麼意思呢？下面我們具體講解一下。

假設第一次迭代所選的兩個變數是 $alpha_{i1}, alpha_{j1}$ ，則 $alpha_1,cdots,alpha_{i1-1}, alpha_{i1+1}, cdots,alpha_{j1-1}, alpha_{j1+1}, cdots, alpha_m$ 視為常數。
通過極小目標函數求解 $alpha_{i1} = alpha_{i1}^{(1)}, alpha_{j1} = alpha_{j1}^{(1)}$ ，更新參數向量的 $alpha$ 的值為 $alpha_1,cdots,alpha_{i1}^{(1)}, cdots,alpha_{j1}^{(1)}, cdots, alpha_m$ 。
更新假設函數的參數 $b$ 。
進入第二輪迭代，選擇兩個變數為 $alpha_{i2}, alpha_{j2}$ ，則 $alpha_1,cdots,alpha_{i2-1}, alpha_{i2+1}, cdots,alpha_{j2-1}, alpha_{j2+1}, cdots, alpha_m$ 視為常數。
通過極小目標函數求解 $alpha_{i2} = alpha_{i2}^{(2)}, alpha_{j2} = alpha_{j2}^{(2)}$ ，更新參數向量的 $alpha$ 的值為 $alpha_1,cdots,alpha_{i2}^{(2)}, cdots,alpha_{j2}^{(2)}, cdots, alpha_m$ 。
更新假設函數的參數 $b$ 。
不斷循環迭代，直到達到目標函數最優值。

Q1：之前有沒有學過類似的迭代演算法，他們的異同點是什麼？

梯度下降演算法，每次循環只更新一次參數；EM演算法（坐標上升法），每個循環更新兩次參數。而SMO演算法屬於坐標上升法，和EM演算法更加親密 (這句話好像也似曾相識，在哪兒見到過？回憶一下攀登傳統機器學習的珠峰-SVM (上))。

後面我們會詳細分析三者的區別與聯繫。

Q2：為什麼要轉化為兩變數的優化問題？為什麼不採用一個變數，三個變數，四個變數，...？（後面會講到為什麼不用梯度下降法）

假如採用一個變數，比如說 $alpha_1$ ，即意味著其他 m-1 個參數視為常數，可以看成關於 $alpha_1$ 的一元函數求解。但是由於約束條件 $sumlimits_{i=1}^{m}alpha_iy_i = 0$ , 當其他m-1 個參數為常數時，參數 $alpha_1= -y_1sumlimits_{i=2}^{m}y_ialpha_i$ 也被固定，意味著 m 個參數均視為常數，因此不能採用一個變數。

採用兩個變數，比如 $alpha_1$ 和 $alpha_2$ ，其他 m-2 個參數參數視為常數，那麼根據 $sumlimits_{i=1}^{m}alpha_iy_i = 0$ 可以用 $alpha_1$ 來表示 $alpha_2$ ，即 $alpha_1 = y_1 sumlimits_{i=3}^{m}alpha_iy_i-alpha_2y_1y_2$ ，將一個二變數 ( $alpha_1, alpha_2$ ) 的優化轉化為單變數 ( $alpha_2$ ) 的優化問題，從而簡化問題。

假如採用三個變數，四個變數，本身就是一個多變數優化問題，轉化之後還是一個多變數優化問題，問題的複雜度還是很大。

以上我們了解了SMO演算法的基本思想，SMO的第一步需要選擇兩個變數，那麼怎樣選擇這兩個變數呢？

3. SMO演算法兩個變數的選擇

和梯度下降類似，SMO演算法選擇變數的原則是使得目標函數下降的最快。具體該怎樣操作呢？

3.1 第一個變數的選擇　

第一個變數 $alpha_1$ 的選擇也稱為外循環，這個變數需要選擇對目標函數影響最大且距離真實值最離譜的變數 $alpha_1$ ，也就是違反 KKT 約束條件最嚴重的樣本點。

對於每個樣本點，要滿足的 KKT 條件我們上一節已經講到了：

$alpha_{i}^{*} = 0 Rightarrow y_ig(x_i) geq 1 \ 0 < alpha_{i}^{*} < C Rightarrow y_ig(x_i) = 1 \ alpha_{i}^{*}= C Rightarrow y_ig(x_i) leq 1$

Q3:對於樣本種的任意一個點，都有可能違反上訴三個條件中的任意一個條件，我們應該首先以違反哪個條件的 $alpha_i$ 為主呢？也就是違反三個條件中的哪個條件更離譜呢？

對 SVM 決策超平面結果影響最大的是支持向量，因此我們首先應該選擇違反 $0 < alpha_{i}^{*} < C Rightarrow y_ig(x_i) =1$ 這個條件的點。如果這些支持向量都滿足KKT條件，再選擇違反其他條件的點。

3.2 第二個變數的選擇

第二個變數 $alpha_2$ 的選擇也稱為內層循環，假設我們在外層循環已經找到了 $alpha_1$ , $alpha_2$ 的選擇標準需要滿足 $alpha_2$ 變化最大，即最大 $|E_1?E_2|$ 對應的 $alpha_2$ （其中 $E_i = hat y_i-y_i$ ，即預測值和真實值之間的差值）。

Q4：為什麼選擇 $|E_1?E_2|$ 最大化作為標準？怎樣理解選擇 $|E_1?E_2|$ 足夠大變化對應的變數 $alpha_2$

更新兩個誤差很大的樣本點對應的變數，比起量誤差相似的樣本點對應的變數，會帶給目標函數更大的變化。下面的公式推導會說明， $alpha_2$ 的變化幅度恰好與 $|E_1?E_2|$ 成正比。

由於 $alpha_1$ 定了的時候， $E_1$ 也確定了，所以要想 $|E_1?E_2|$ 最大，只需要在 $E_1$ 為正時，選擇最小的 $E_i$ 作為 $E_2$ ，在 $E_1$ 為負時，選擇最大的 $E_i$ 作為 $E_2$ ，可以將所有的 $E_i$ 保存下來加快迭代。

如果內存循環找到的點不能讓目標函數有足夠的下降，可以採用以下步驟：

遍歷支持向量點來做 $alpha_2$ , 直到目標函數有足夠的下降；
如果所有的支持向量做 $alpha_2$ 都不能讓目標函數有足夠的下降，可以在整個樣本集上選擇 $alpha_2$ ；
如果整個樣本集依然不存在，則跳回外層循環重新選擇 $alpha_1$ 。

4. SMO演算法優化求解

假設我們通過上述方法得到了兩個變數 $alpha_1$ 和 $alpha_2$ 那麼

$sumlimits_{i=1}^{m}alpha_iy_i = 0 Rightarrow alpha_1y_1 + alpha_2y_2 = -sumlimits_{i=3}^{m}y_ialpha_i = varsigma$

這樣我們目標優化函數變為：

$;underbrace{ min }_{alpha_1, alpha_1} frac{1}{2}K_{11}alpha_1^2 + frac{1}{2}K_{22}alpha_2^2 +y_1y_2K_{12}alpha_1 alpha_2 -(alpha_1 + alpha_2) +y_1alpha_1sumlimits_{i=3}^{m}y_ialpha_iK_{i1} + y_2alpha_2sumlimits_{i=3}^{m}y_ialpha_iK_{i2} + ext{Const} \ s.t. ;;alpha_1y_1 + alpha_2y_2 = -sumlimits_{i=3}^{m}y_ialpha_i = varsigma \ 0 leq alpha_i leq C ;; i =1,2$

以上為有約束條件的的優化問題。傳統的方法是採用拉格朗日乘子法進行求解轉化為無約束的優化問題進行求解。這裡我們採用一種更為自然的方法：

由於 $alpha_1, alpha_2$ 滿足 $alpha_1y_1 + alpha_2y_2 = varsigma$ ，得到 $alpha_1 = y_1 varsigma-alpha_2y_1y_2$ ，兩變數的優化問題可以轉化為單變數的優化問題。
對無約束條件下的單變數優化問題進行求導。求得該變數的值。
根據約束條件對得到的該變數的值進行修正。

假設我們上一輪迭代得到的解是 $alpha_1^{old}, alpha_2^{old}$ ，單變數求導 (未考慮約束條件) 得到的解是 $alpha_1^{new,unc}, alpha_2^{new,unc}$ ，考慮約束條件之後的解為 $alpha_1^{new}, alpha_2^{new}$ 。下面我們詳細講解一下求解流程。

4.1 求解無約束的優化問題

求解無約束的優化問題非常簡單，對目標函數求導即可。但在求導之前，最好能夠對目標函數進行一下化簡。

4.1.1 化簡為單變數優化問題

令：

$v_i= sumlimits_{j=3}^{m}y_jalpha_jK(x_i,x_j) = h(x_i) - sumlimits_{j=1}^{2}y_jalpha_jK(x_i,x_j) -b$

其中 $h(x_i) = w ullet phi(x_i) + b =sumlimits_{j=1}^{m}alpha_jy_jK(x_i, x_j)+ b$ 。

這樣我們的優化目標函數簡化為：

$W(alpha_1,alpha_2) = frac{1}{2}K_{11}alpha_1^2 + frac{1}{2}K_{22}alpha_2^2 +y_1y_2K_{12}alpha_1 alpha_2 -(alpha_1 + alpha_2) +y_1alpha_1v_1 + y_2alpha_2v_2$

由於 $alpha_1y_1 + alpha_2y_2 = varsigma$ ，並且 $y_i^2 = 1$ ，可以得到 $alpha_1$ 用 $alpha_2$ 表達的式子為：

$alpha_1 = y_1(varsigma - alpha_2y_2)$

將上式帶入我們的目標優化函數，得到僅僅包含 $alpha_2$ 的單變數函數：

$W(alpha_2) = frac{1}{2}K_{11}(varsigma - alpha_2y_2)^2 + frac{1}{2}K_{22}alpha_2^2 +y_2K_{12}(varsigma - alpha_2y_2) alpha_2 -(alpha_1 + alpha_2) +(varsigma - alpha_2y_2)v_1 + y_2alpha_2v_2$

4.1.2 求解單變數無約束問題

現在我們開始通過求偏導數來得到 $alpha_2^{new,unc}$ 。

$frac{partial W}{partial alpha_2} = K_{11}alpha_2 + K_{22}alpha_2 -2K_{12}alpha_2 - K_{11}varsigma y_2 + K_{12}varsigma y_2 +y_1y_2 -1 -v_1y_2 +y_2v_2 = 0$

整理上式有：

$(K_{11} +K_{22}-2K_{12})alpha_2 = y_2(y_2-y_1 + varsigma K_{11} - varsigma K_{12} + v_1 - v_2) \ = y_2(y_2-y_1 + varsigma K_{11} - varsigma K_{12} + (h(x_1) - sumlimits_{j=1}^{2}y_jalpha_jK_{1j} -b ) -(h(x_2) - sumlimits_{j=1}^{2}y_jalpha_jK_{2j} -b))$

我們令:

$E_i = h(x_i)-y_i = sumlimits_{j=1}^{m}alpha_j^{*}y_jK_{ij}+ b - y_i$

其中 $h(x) = w ullet phi(x) + b =sumlimits_{j=1}^{m}alpha_jy_jK(x, x_j)+ b$ 為假設函數。

將 $varsigma = alpha_1^{old}y_1 + alpha_2^{old}y_2$ 帶入上式，我們有：

$(K_{11} +K_{22}-2K_{12})alpha_2^{new,unc} = y_2((K_{11} +K_{22}-2K_{12})alpha_2^{old}y_2 +y_2-y_1 +h(x_1) - h(x_2)) \ ;;;; = (K_{11} +K_{22}-2K_{12}) alpha_2^{old} + y_2(E_1-E_2)$

我們終於得到了 $alpha_2^{new,unc}$ 的表達式：

$alpha_2^{new,unc} = alpha_2^{old} + frac{y_2(E_1-E_2)}{K_{11} +K_{22}-2K_{12}}$

4.2 約束條件修正變數結果

下面我們考慮約束條件：

$alpha_1y_1 + alpha_2y_2 = varsigma \ \ 0 leq alpha_i leq C ;; i =1,2$

Q5：請在坐標軸中畫出上述約束條件的幾何表示

$0 leq alpha_i leq C$ 將兩變數限制在 $[0, C] imes [0, C]$ 的矩形中， $alpha_1y_1 + alpha_2y_2 = varsigma$ 將兩個變數限制在矩形中平行於對角線的線段上。左圖為 $y_1,y_2$ 異號的情況，右圖為 $y_1,y_2$ 同號的情況。

由於 $alpha_2^{new}$ 必須要在方框內且在直線上取得。假設 L 和 H 分別是上圖中 $alpha_2^{new}$ 所在的線段的邊界。那麼：

$L leq alpha_2^{new} leq H$

對於上面左圖中的情況 $y_1 eq y_2$ ，則

$L = max(0, alpha_2^{old}-alpha_1^{old}) ;;;H = min(C, C+alpha_2^{old}-alpha_1^{old})$

對於上面右圖中的情況 $y_1= y_2$ ，有：

$L = max(0, alpha_2^{old}+alpha_1^{old}-C) ;;; H = min(C, alpha_2^{old}+alpha_1^{old})$

假如我們通過求導得到的 $alpha_2^{new,unc}$ ，則最終的 $alpha_2^{new}$ 應該為：

$alpha_2^{new}= egin{cases} H& { alpha_2^{new,unc} > H}\ alpha_2^{new,unc}& {L leq alpha_2^{new,unc} leq H}\ L& {alpha_2^{new,unc} < L} end{cases}$

利用上面講到的 $alpha_2^{new,unc}$ 和 $alpha_2^{new}$ 的關係式，我們就可以得到我們新的 $alpha_2^{new}$ 了。

由於其他 m-2 個變數固定，因此：

$alpha_1^{old}y_1+alpha_2^{old}y_2=alpha_1^{new}y_1+alpha_2^{new}y_2$

求得：

$alpha_1^{new}=alpha_1^{old}+y_1y_2(alpha_2^{old}-alpha_2^{new})$

4.3 計算 b

在每次完成兩個變數的優化之後，需要重新計算閾值 b。當 $0 < alpha_{1}^{new} < C$ 時，我們有

$y_1 - sumlimits_{i=1}^{m}alpha_iy_iK_{i1} -b_1 = 0$

於是新的 $b_1^{new}$ 為：

$b_1^{new} = y_1 - sumlimits_{i=3}^{m}alpha_iy_iK_{i1} - alpha_{1}^{new}y_1K_{11} - alpha_{2}^{new}y_2K_{21}$

計算出 $E_1$ 為：

$E_1 = h(x_1) - y_1 = sumlimits_{i=3}^{m}alpha_iy_iK_{i1} + alpha_{1}^{old}y_1K_{11} + alpha_{2}^{old}y_2K_{21} + b^{old} -y_1$

將 $b_1^{new}$ 用 $E_1$ 表示為：

$b_1^{new} = -E_1 -y_1K_{11}(alpha_{1}^{new} - alpha_{1}^{old}) -y_2K_{21}(alpha_{2}^{new} - alpha_{2}^{old}) + b^{old}$

同樣的，如果 $0 < alpha_{2}^{new} < C$ , 那麼有：

$b_2^{new} = -E_2 -y_1K_{12}(alpha_{1}^{new} - alpha_{1}^{old}) -y_2K_{22}(alpha_{2}^{new} - alpha_{2}^{old}) + b^{old}$

最終的 $b^{new}$ 為：

$b^{new} = egin{cases} frac{b_1^{new} + b_2^{new}}{2} ;; 假如alpha_2對於的樣本點是支持向量 \ b_1^{new} ;;;;;;;; 假如alpha_2對應的樣本點不是支持向量 end{cases}$

得到了 $b^{new}$ 為我們需要更新 $E_i$ :

$E_i^{new} = sumlimits_{S}y_jalpha_jK(x_i,x_j) + b^{new} -y_i$

其中，S 是所有支持向量 $x_j$ 的集合，利用 $b^{new}$ 和 $E_i^{new}$ 選擇新的變數進行循環迭代。

5. SMO演算法總結

輸入是 m 個線性可分的樣本 ${(x_1,y_1), (x_2,y_2), ..., (x_m,y_m),}$

其中 x 為 n 維特徵向量。y 為二元分類結果 1 或 -1, 精度 $epsilon$ 。

輸出是近似解 $alpha$ 。

演算法過程如下：

1）取初始值 $alpha^{0} = 0, k =0$ 。

2) 選擇 $α_1^k, α_2^k$ ，求出新的 $alpha_2^{new,unc}$ :

$alpha_2^{new,unc} = alpha_2^{k} + frac{y_2(E_1-E_2)}{K_{11} +K_{22}-2K_{12}}$

3) 按照下式求出 $alpha_2^{k+1}$ ：

$alpha_2^{k+1}= egin{cases} H& {L leq alpha_2^{new,unc} > H}\ alpha_2^{new,unc}& {L leq alpha_2^{new,unc} leq H}\ L& {alpha_2^{new,unc} < L} end{cases}$

4) 利用 $alpha_2^{k+1}$ 和 $alpha_1^{k+1}$ 的關係求出 $alpha_1^{k+1}$ 。

5) 計算 $b^{k+1}$ 和 $E_i$ 。

6）在精度 $epsilon$ 範圍內是否滿足如下的終止條件：

$sumlimits_{i=1}^{m}alpha_iy_i = 0 \ 0 leq alpha_i leq C, i =1,2...m \ alpha_{i}^{*} = 0 Rightarrow y_ih(x_i) geq 1 \ 0 < alpha_{i}^{*} < C Rightarrow y_ih(x_i) = 1 \ alpha_{i}^{*}= C Rightarrow y_ih(x_i) leq 1$

7) 如果滿足則結束，返回 $α^{k+1}$ ,否則轉到步驟2。

6. 迭代優化演算法小結

目前我們已經學到兩種基本的迭代優化演算法，三種應用。下面我用更加直觀的方式一一說明。

梯度下降 (或上升)法：沿函數值增幅最大 (即梯度方向) 的反方向走，就能使函數值減小 (或增大) 幅度越大。主要應用在邏輯回歸演算法，深度學習等演算法中。如下圖所示：

2. 坐標上升 (或下降法) 法：每次只選擇一個維度，將原始的問題變成一個一元函數，然後針對這個一元函數求極值，如此反覆輪換不同的維度進行迭代。主要應用包括EM演算法和SMO演算法。

對於EM演算法，顯然是一個二變數迭代的坐標上升問題，其特點是兩個維度輪換迭代。難點是怎樣連接迭代步驟中的E步和M步（ Jensen 不等式，將 log 中的累加函數提取到log外面）。如下圖所示：

對於 SMO 演算法則是一個 m-1 (m表示樣本量) 維度的坐標下降問題，難點在於該選擇哪個坐標作為下一個循環的迭代，同時還需要對求導得到的變數值進行約束條件限制。（暫時無法可視化高維圖像，故此處沒有示意圖）

Q6：SMO演算法中 $alpha$ 的維度是 m，為什麼坐標下降演算法中坐標的維度變成了m-1？

由於約束條件 $sumlimits_{i=1}^{m}alpha_iy_i = 0$ 的存在，我們可以判斷，一直任意 m-1 個變數的值，那麼另一個變數的值也就確定了，即 $sumlimits_{i=1}^{m}alpha_iy_i = 0$

Q7：為什麼EM演算法和 SMO演算法不能直接用梯度下降 (或上升) 進行求解？

回憶一下EM演算法中的似然函數：

$heta, z = arg max limits_{ heta,z}L( heta, z) = arg max limits_{ heta,z}sumlimits_{i=1}^m logsumlimits_{z^{(i)}}P(x^{(i)}， z^{(i)}| heta)$

由於 $logP(x^{(i)}| heta)$ 是 $P(x^{(i)}， z^{(i)}| heta)$ 邊緣概率，轉化為 $logP(x^{(i)}| heta)$ 求導後形式會非常複雜（可以想像下 $log(f_1(x)+ f_2(x)+…$ 複合函數的求導) ，所以很難直接通過梯度下降法求解得到 $z$ 和 $heta$ 。

對於SMO演算法，其優化函數為：

對於任意一個 $alpha_i$ 求導得到 $frac{1}{2} sumlimits_{j=1}^{m} alpha_ialpha_jy_iy_jK(x_i,x_j) - 1$ , 顯然它的係數會包含其他所有的變數，每一個方程中還是包含 m 個變數，每次迭代需要計算 m 個帶有核函數的 m 元方程，方程的個數等於樣本量的個數，對於大樣本量的問題而言，計算量很大。因此一般不會採用梯度下降法。

總結一下：梯度下降 (或上升) 法是機器學習優化演算法中最簡單的，也是最常用的。當問題複雜，梯度下降演算法無法求出最優解或者計算量巨大時，我們可以考慮採用坐標下降 (或上升) 法。與梯度下降法相比，坐標上升需要更多的迭代次數來收斂。

SVM 回歸模型（又稱為SVR）

1. SVR模型的損失函數度量

回顧下我們SVM分類模型 (SVC)，傳統的分類模型通常直接基於模型輸出 $h(x)$ 和真實類別 $y$ 之間的差別來定義損失，每個樣本點都對應一個損失，當 $h(x)$ 與 $y$ 的符號相同，距離決策邊界越近，損失越大，對於誤分類的點，距離決策邊界越遠，損失越大。而 SVM 分類僅僅關心決策邊界附近易混淆或誤分類的樣本點，即當且僅當樣本點與決策邊界的距離小於 $epsilon = 1$ 時，才計算損失，相當於以 $f(x)$ 為中心，構建了一個寬度為 2 的間隔帶，間隔帶外面正確分類的點都是沒有損失的，誤分的點和間隔帶裡面的點是有損失的。

下圖對比邏輯回歸損失函數和SVC損失函數之間的區別：

再來看SVR, 傳統的回歸模型通常直接基於模型輸出 $h(x)$ 和真實輸出 $y$ 之間的差別來定義損失，當且僅當 $h(x)$ 與 $y$ 完全相同時，損失才為 0。而 SVR 僅僅關係距離擬合模型距離較遠的樣本點，即當且僅當 $f(x)$ 與 $y$ 直接的差別大於 $epsilon$ (不敏感損失) 時，才計算損失，這就相當於以 $f(x)$ 為中心，構建了一個寬度為 $2epsilon$ 的間隔帶，間隔帶裡面的點都是沒有損失的，外面的點的是有損失的。

由上節課我們知道 SVC 的損失函數為：

${ min} ;; frac1msumlimits_{i=1}^m max{0,1-y_i hat y_i} + frac lambda 2||w||_2^2$

我們可以得到 SVR 的損失函數為：

${ min} ;; frac1msumlimits_{i=1}^m max{0, |y_i hat y_i| - epsilon} + frac lambda 2||w||_2^2$

下圖對比 SVR 損失函數和lr均方差損失函數之間的區別：

Q8：對比 SVC 和 SVR 的代價函數，有什麼區別？為什麼會有這種區別？

SVC 和 SVR 之間的區別主要體現在 $1-y_i hat y_i$ 和 $|y_i hat y_i| - epsilon$ ，具體說來有三個區別：

SVR 用的是 $epsilon$ 而 SVC 用的是 1。即 SVC 採用相對距離（還記得怎麼推導的吧？），而 SVR 採用的是絕對距離。這是因為對於最終結果來說，SVC 只需要考慮到決策邊界的相對距離，距離的實際大小並沒有意義。而 SVR 最後要得到實際值的大小，不能隨便縮放。
SVR 是 $|y_i hat y_i|$ ，而 SVC 是 $y_i hat y_i$ ，SVR 多了個絕對值，這是因為 SVR 只需要考慮樣本點到擬合模型的絕對距離大小，而不需要考慮樣本點在擬合模型的哪一側。SVC 則需要考慮誤分類點的情況，對於誤分類的點 $y_i hat y_i <0$ , 對於正確分類的點 $y_i hat y_i > 0$ ，因此可以理解為 SVC 考慮的是有向距離。
SVC 中常數為被除數，SVR 中常數是除數，類似於相反數的關係。這是由於 SVC 中間隔帶內的樣本點和誤分類的點才有損失，即對於 $y_i hat y_i <1$ 的樣本點，損失不可能為負，所以只可能是 $1-y_i hat y_i$ 而不是 $y_i hat y_i - 1$ ，即損失為 $max{0,1-y_i hat y_i}$ 。而SVR中間隔帶外的樣本點才有損失，即對於 $|y_i hat y_i| >epsilon$ 的樣本點，損失不可能為負，所以只可能是 $|y_i hat y_i| - epsilon$ ，即損失為 $max{0, |y_i hat y_i| - epsilon}$ 。

2. SVR目標函數的原始形式

上一節我們已經得到了我們的損失函數的度量，現在可以可以定義我們的目標函數如下：

$min;; frac{1}{2}||w||_2^2 ;; s.t ;; |y_i - w ullet phi(x_i ) -b| leq epsilon ;; (i =1,2,...m)$

SVR 中加入鬆弛變數 $xi_i$ 之後變為：

$min;; frac{1}{2}||w||_2^2 + Csumlimits_{i=1}^{m}(xi_i^{lor}+ xi_i^{land}) \ s.t. ;;; -epsilon - xi_i^{lor} leq y_i - w ullet phi(x_i ) -b leq epsilon + xi_i^{land} \ xi_i^{lor} geq 0, ;; xi_i^{land} geq 0 ;(i = 1,2,..., m)$

用拉格朗日函數將目標優化函數變成無約束的形式：

$L(w,b,alpha^{lor}, alpha^{land}, xi_i^{lor}, xi_i^{land}, mu^{lor}, mu^{land}) = frac{1}{2}||w||_2^2 + Csumlimits_{i=1}^{m}(xi_i^{lor}+ xi_i^{land}) + sumlimits_{i=1}^{m}alpha^{lor}(-epsilon - xi_i^{lor} -y_i + w ullet phi(x_i) + b) \+ sumlimits_{i=1}^{m}alpha^{land}(y_i - w ullet phi(x_i ) - b -epsilon - xi_i^{land}) - sumlimits_{i=1}^{m}mu^{lor}xi_i^{lor} - sumlimits_{i=1}^{m}mu^{land}xi_i^{land}$

其中 $mu^{lor} geq 0, mu^{land} geq 0, alpha_i^{lor} geq 0, alpha_i^{land} geq 0$ ，均為拉格朗日係數。

從上面的公式我們發現，由於絕對值的存在， SVR 中的變數比 SVC 中多了一倍。

3. SVR目標函數的對偶形式

上一節我們講到了SVM回歸模型的目標函數的原始形式,我們的目標是：

$underbrace{min}_{w,b,xi_i^{lor}, xi_i^{land}};underbrace{max}_{mu^{lor} geq 0, mu^{land} geq 0, alpha_i^{lor} geq 0, alpha_i^{land} geq 0}L(w,b,alpha^{lor}, alpha^{land}, xi_i^{lor}, xi_i^{land}, mu^{lor}, mu^{land})$

和SVM分類模型一樣，這個優化目標也滿足KKT條件，也就是說，我們可以通過拉格朗日對偶將我們的優化問題轉化為等價的對偶問題來求解如下：

$underbrace{max}_{mu^{lor} geq 0, mu^{land} geq 0, alpha_i^{lor} geq 0, alpha_i^{land} geq 0} ;underbrace{min}_{w,b,xi_i^{lor}, xi_i^{land}};L(w,b,alpha^{lor}, alpha^{land}, xi_i^{lor}, xi_i^{land}, mu^{lor}, mu^{land})$

我們可以先求優化函數對於 $w,b,xi_i^{lor}, xi_i^{land}$ 的極小值, 接著再求拉格朗日乘子 $alpha^{lor}, alpha^{land}, mu^{lor}, mu^{land}$ 的極大值。

首先我們來求優化函數對於 $w,b,xi_i^{lor}, xi_i^{land}$ 的極小值，這個可以通過求偏導數求得：

$frac{partial L}{partial w} = 0 ;Rightarrow w = sumlimits_{i=1}^{m}(alpha_i^{land} - alpha_i^{lor})phi(x_i) \ frac{partial L}{partial b} = 0 ;Rightarrow sumlimits_{i=1}^{m}(alpha_i^{land} - alpha_i^{lor}) = 0 \ frac{partial L}{partial xi_i^{lor}} = 0 ;Rightarrow C-alpha^{lor}-mu^{lor} = 0 \ frac{partial L}{partial xi_i^{land}} = 0 ;Rightarrow C-alpha^{land}-mu^{land} = 0$

好了，我們可以把上面4個式子帶入 $L(w,b,alpha^{lor}, alpha^{land}, xi_i^{lor}, xi_i^{land}, mu^{lor}, mu^{land})$ 去消去 $w,b,xi_i^{lor}, xi_i^{land}$ 了。

最終得到的對偶形式為：

$underbrace{ min}_{alpha^{lor}, alpha^{land}}; frac{1}{2}sumlimits_{i=1,j=1}^{m}(alpha_i^{land} - alpha_i^{lor})(alpha_j^{land} - alpha_j^{lor})K_{ij} + sumlimits_{i=1}^{m}(epsilon-y_i)alpha_i^{land}+ (epsilon+y_i)alpha_i^{lor} \ s.t. ; sumlimits_{i=1}^{m}(alpha_i^{land} - alpha_i^{lor}) = 0 \ 0 < alpha_i^{lor} < C ; (i =1,2,...m) \ 0 < alpha_i^{land} < C ; (i =1,2,...m)$