ML-軟間隔(slack)的 SVM

帶松弛的svm推導

Why Slack?

為了處理異常值(outlier).

前面推導的svm形式, 是要求嚴格地全部分對, 基于該情況下, 在margin 的邊界線 線上的點, 隻能是支援向量.

\(min_w \ \frac {1}{2} ||w||^2 \\ s.t. \ y_i(w^Tx_i + b) >= 1\)

而現實生活中, 往往資料是沒有那麼完美. 于是這樣嚴格找到的 margin 可能就因為異常值 而 不是最優的(非最優就是沒有 很好地 将2波資料給分開).則相應的處理方式,就是适當允許一些點(異常點)在 margin 之間.

更進一步說明該問題的本質, 就是關于線性不可分.(比如有些點完全分布在另一邊去了, "身在漢營,心在曹", 幽默一下). 這時候, 必須要放松限制了呀, 不然就沒有辦法找到 margin 了. 另外一種方式就是大家談爛大街的核變換(Kernel trick), 升維到高維空間就能分開了.

還是先回到 slack.

Slack svm 數學模型

感覺我現在是越來越喜歡數學語言,數學模型了, 雖然絕大多數時候都是看不懂的. 其明顯的好處是能将自然語言化的想法,通過符号化, 邏輯性的語言來表示, 這種好處, 我真正認識到它的美妙, 有3次高峰體檢, 初一 那年, 通過三角形相似的方法,推導出了勾股定律; 高三那年, 完全自然語言角度引入, 然後從零推導橢圓方程;

其實中間, 還有很多的美妙之處, 不過都被應試教育而自我懷疑和扼殺了, 更流行分數排名才是優秀, 然後就放棄了, 事實證明, 我菜是有原因的, 因為一開始我就已經自我放棄了.

真正再次喚醒是大三, 有門課是<<财務管理>>, 老師盧大神, 完全将财務理論展開來講, 真的是把 高數, 線代, 機率論, 數理統計.. 全部整了一遍, 還讓我們看頂級文獻... 那一刻我才真正明白, 要真正認識我們的世界, 就是要從現象->理論->現象->理論, 這樣的一個循環的認識過程. 這個過程艱難而有美妙.

艱難可能是生活工作上的現實問題很拮據吧,目前. 美妙..不說了吧, 看到知乎上有句話很貼心: "你懂得越多, 懂你的越少.

算是一種境界吧, 嗯, 終極來講, 借用"老子''所追求的道境: "緻虛極, 守靜笃, 萬物并作, 吾以觀複".

不扯了, 還是進入正題. 關于 Primal 問題:

\(min_{w,b} = \frac {1}{2} ||w||^2 + C \sum \limits _{i=1}^n \xi_i \\ s.t.\)

$ \ y_i(w^Tx_i + b) >= 1- \xi_i \ \xi_i >= 0$

• \(\xi_i\)
• 将松弛限定在 min 中, C 是超參數, 通過調整C的大小,進而調整放松程度

Dual 問題:

\(max_w \ W(a) = \sum \limits _{i=1}^n a_i - \frac {1}{2} \sum \limits_{i=1}^n \sum \limits_{j=1}^n y_i y_j a_i a_j <x_i, x_j> \\ s.t.\)

\(0<= a_i \le C \\ \sum \limits_{i=1}^n a_i y_i = 0\)

推導帶松弛的 svm 的 lagrange (跟之前是一樣的)

\(L(w,b,a, \xi, \lambda) = \frac {1}{2}w^Tw + C \sum \limits_i \xi_i + \sum\limits_j a_i(1- \xi_i - y_i(w^Tx_i + b)) - \sum \limits _i \lambda_i \xi _i\)

同樣分别對 w, b, xi 求偏導, 令其=0:

• \(\nabla _w = 0 = w - \sum \limits _i a_i y_i x_i \rightarrow \ w = \sum a_i y_i x_i\)
• \(\nabla _b= 0 \rightarrow \ \sum \limits _i a_i y_i =0\)
• $\nabla _\xi = 0 \ \rightarrow \ C - a_i - \lambda_i = 0 $

将其分别反代回 \(L(w,b,a,\xi, \lambda)\):

\(L(a, \xi, \lambda) = \sum _i a_i - \frac{1}{2} \sum_i \sum_j a_i a_j y_i y_j <x_i, x_j> + \sum_i \xi_i (C-a_i)\)

對偶也就是:

\(max_a \sum _i a_i - \frac{1}{2} \sum_i \sum_j a_i a_j y_i y_j \ x^Tx \\ s.t\)

\(\sum_i a_i y_i = 0 \\ C-a_i - \lambda_i = 0\)

\(\lambda\) 是拉格朗日乘子,是以 \(\lambda \ge 0\) , 對于 \(C - a_i - \lambda_i = 0\) 即 \(a_i + \lambda_i = C\)

\(a_i <= C\)

決策:

\(h(x) = sign(w^tx + b)\) , 不用關心值大小, 值關注最中的 正負号.

• 帶松弛, 其實就是 a 同 C 關聯上了呀
• \(\sum \limits_{i=1}^n a_i y_i = 0\)

此時的 Dual 的KTT 條件下的 complementarity 條件為:

• \(a_i = 0, \ \rightarrow y_i(w^Tx_i + b) \ge 1\)
• \(a_i = C, \ \rightarrow y_i(w^Tx_i + b) \le 1\)
• \(0 \le a_i \le C, \ \rightarrow y_i(w^Tx_i + b) \ge 1\)

從 Hinge Loss 來了解 slack

這樣做是為了友善計算求導, 直接在原問題上整, 不同轉為Dual.

回顧之前定義松弛變量: \(\xi\)

\(y_i (w^Tx_i + b) \ge 1- \xi_i , \ 其中 \xi_i \ge 0)\)

得出:

\(\xi _i \ge 1- y_i (w^Tx_i + b)\)

合并一波(兩個大于, 國中學過, 同大取大), 即:

\(\xi _i = max(0, 1-y_i(w^Tx_i + b))\)

怎麼來了解呢, 令 \(z = y_i(w^Tx_i + b)\)

\(\xi_i = max (0, 1-z)\)

\(\xi _i\)

當 z < 1 的時候, 是遞增的

與邏輯回歸的 Loss 相比

• LR 即便是正确分類, 也要計入 Loss, (LR 始終保持一個懷疑的态度,對異常值非常敏感)
• Hinge 則不同, 會更有容忍度, 隻要達到線, 就認為是正确 (對異常值不敏感)

Hinge Loss 的特點

\(\xi_i = max (0, 1-z), 其中 \ z = y_i(w^Tx_i + b\)

• Convex (凸函數), 比較容易優化
• 在 z<0 的部分, 梯度較小, 對錯誤分類的容錯較小
• 在 z >= 1 的部分值為0, 隻要分類正确,就不用再優化了.(對異常值不敏感)
• 在z = 0 不可導, 可以分段求導
• 優化時,隻有支援向量會參與确定分界線, 支援向量遠小于訓練樣本

總體來說, 會發現 svm 的美妙在于, 對異常值不敏感, KKT條件也降低了運算複雜度, 這我感覺算是其流行的一大原因了吧.

了解 SVM 的優化函數

算是再對SVM的dual進行強化認知一波, 主要是為了了解哪個 Lagrange 公式, 因為後面的 Kernel 技巧 和 求解的SMO 是要基于如下的公式的.(ps: 不了解公式,根本寫不出代碼來哦)

\(max_a \sum _i a_i - \frac{1}{2} \sum_i \sum_j a_i a_j y_i y_j \ x^Tx \\ s.t\)

\(\sum_i a_i y_i = 0 \\ C-a_i - \lambda_i = 0\)

了解

• \(y_i y_j\) 表示 if 兩個樣本如果屬于同一類别(y 隻能取 +1 或 -1) 值就增大, else 值減少
• \(x_i ^T x_j\) 表示兩個樣本(行)之間的相似度, 因其 \(= ||x_i|| ||x_j||cos \theta\), 很相似的話就意味着夾角很小, 内積接近最大, 從實體的做功來了解内積是很形象的哦.
• \(\sum \limits _i ^n a_i y_i = 0\) 表示不同資料點的權重 a_i 是不一樣的(比如向量的點的權重高), 但不同類别的權重是一樣的