EdX-Columbia機器學習課第11講筆記：最大間隔分類器和SVM

05-14

（按1：其實這個系列很早就寫好了，畢竟是這門課第一期學員……但是從作業部落往這兒搬太費勁，知乎專欄不支持markdown有點讓人抓狂，公式一點點轉很麻煩……有沒有簡便方法）

（按2：這一講很精彩。白大哥從凸包的角度引入最大間隔簡直是耳目一新。當初記筆記的時候沒有放圖，這一章結合圖看效果更佳）

最大間隔分類器

感知機只選擇第一個完全分離開樣本的超平面（如果樣本線性可分）。所有可以分離開樣本的超平面對於感知機來講都是同樣好的。而最大間隔分類器的目標是減少預測誤差，使得每個類別中離超平面最近的那個點與超平面的距離盡量大。這個距離叫做間隔（margin）。如果我們知道兩個類別應該滿足什麼分布，那麼可以使用貝葉斯分類器；但是如果我們不對分布進行任何假設，那麼最大間隔分類器應該是最好的

最大間隔分類器實際上只由數據集中最「靠外」的點決定，內部點不能決定。從幾何角度看，可以用一個**最小凸集**把每個類中的所有點包含起來。這個最小凸集稱作**凸包**。實際上，對凸包內（包括邊界上）的任何一個點 $x_0$ ，該點都可以被表示成該數據集所有點的一個加權平均數，即假設 $x_1, ldots, x_n$ 為已知的數據點，有

$x_0 = sum_{i=1}^n alpha_i x_i, alpha_i ge 0, sum_{i=1}^n alpha_i = 1$

分類超平面 $H$ 的間隔是它到任何類中任意一點距離的最小值（也就是它到任何類其所對應的凸包距離的最小值）。如果我們最大化這個間隔，那麼實際上就是把 $H$ 放在了兩個凸包的正中間。問題是，如何找到滿足要求的這個 $H$

SVM

SVM的問題實際上就是，對於 $n$ 個線性可分的點 $(x_1, y_1), ldots, (x_n, y_n)$ ，且 $y_i in {pm 1}$ ，求解

$egin{aligned}min_{w,w_0} & frac{1}{2}|!|w|!|^2 \{ m subject to} & y_i(x_i^Tw + w_0) ge 1 { m for} i = 1,ldots, nend{aligned}$

仍然是從幾何的意義上講，滿足要求的 $H$ 可以這麼尋找：由之前所述，兩個類的數據點實際上形成了兩個凸包。可以從這兩個凸包上各找一個點，使得它們之間的距離最短。將這兩個點用線連接，在線的中點處做一個超平面垂直於這條線，這個超平面就是最優的 $H$ 。考慮之前凸包上和凸包內所有點都可以用已知數據集所有點的加和表示，記兩個凸包分別為 $S_0$ 和 $S_1$ ，則實際上我們是要找到兩個權重向量 $alpha_0$ 和 $alpha_1$ 以最小化

$left|!left|left(sum_{x_i in S_1}alpha_{1i}x_i ight) - left(sum_{x_i in S_0}alpha_{0i}x_i ight) ight|! ight|_2$

之前引入的問題稱為原始問題，可以引入拉格朗日乘子 $alpha_i > 0, i = 1, ldots, n$ ，則有

$egin{aligned}mathcal{L} &= frac{1}{2} |!|w|!|^2 - sum_{i=1}^n alpha_i (y_i(x_i^Tw + w_0) - 1) \&= frac{1}{2} |!|w|!|^2 - sum_{i=1}^n alpha_i y_i(x_i^Tw + w_0) + sum_{i=1}^n alpha_iend{aligned}$

目標是對 $w$ 和 $w_0$ 最小化，對 $alpha_i$ 最大化 $mathcal{L}$

因此有

$egin{aligned} abla_w mathcal{L} = w - sum_{i=1}^n alpha_iy_ix_i = 0 &Rightarrow w = sum_{i=1}^n alpha_iy_ix_i \frac{partial mathcal{L}}{partial w_0} = -sum_{i=1}^n alpha_i y_i = 0 &Rightarrow sum_{i=1}^n alpha_i y_i = 0end{aligned}$

將這些值代回到原式，可以得到對偶問題：

$egin{aligned}max_{alpha_1, ldots, alpha_n} & mathcal{L} = sum_{i=1}^n alpha_i - frac{1}{2}sum_{i=1}^n sum_{j=1}^n alpha_i alpha_j y_i y_j (x_i^Tx_j) \{ m subject to} &sum_{i=1}^n alpha_iy_i = 0, alpha_i ge 0 { m for} i= 1, ldots, nend{aligned}$

現在要對 $alpha$ 最大化上式（凸優化問題不做進一步討論）

在得到 $alpha_i$ 以後，我們需要將其代回原式求解 $w$ 和 $w_0$ ，這樣對新的 $x_0$ 才能預測其對應的 $y_0$ ，即 $y_0 = { m sign}(x_0^Tw + w_0)$ 。對 $w$ ，由 $abla_w mathcal{L} = 0$ 可知 $w = sum_{i=1}^n alpha_iy_ix_i$

而由於對所有 $i$ 有 $alpha_i (y_i(x_i^Tw + w_0) - 1) = 0$ ，而 $alpha_i ge 0$ ， $y_i(x_i^Tw + w_0) - 1 ge 0$ ，如果對某個 $i$ 有這兩個值同時大於0，則 $mathcal{L}$ 可以更小，與 $w, w_0$ 取得了最小的 $mathcal{L}$ 相矛盾，因此這兩個裡面最多只能有一個大於0。因此，只需要找到使 $alpha_i>0$ 的某個 $i$ ，然後用剛才得出的 $w$ 求解 $y_i(x_i^Tw + w_0) - 1 = 0$ 就可以（所有滿足條件的 $i$ 都能給出同樣的解）

下面進一步理解對偶問題。由於 $y_i in {-1, +1}$ ，因此由約束條件 $sum_{i=1}^n alpha_i y_i = 0$ ，可以知道對應於 $y_i = 1$ 的 $alpha_i$ 的和，應該等於對應於 $y_j = -1$ 的 $alpha_j$ 的和，即 $sum_{i in S_1} alpha_i = sum_{j in S_0} alpha_j$ 。記這個和為 $C$ ，因此有

$sum_{i=1}^n sum_{j=1}^n alpha_i alpha_j y_i y_j (x_i^Tx_j) = left|!left|sum_{i=1}^n alpha_i y_i x_i ight|! ight|^2 = left|!left|sum_{i in S_1} alpha_i x_i - sum_{j in S_0} alpha_j x_j ight|! ight|^2 = C^2 left|!left|sum_{i in S_1} frac{alpha_i}{C} x_i - sum_{j in S_0} frac{alpha_j}{C} x_j ight|! ight|^2$

因此對偶問題可以寫作

$egin{aligned}max_{alpha_1, ldots, alpha_n} & mathcal{L} = 2C - frac{1}{2}C^2 left|!left|sum_{i in S_1} frac{alpha_i}{C} x_i - sum_{j in S_0} frac{alpha_j}{C} x_j ight|! ight|^2 \{ m subject to} &C := sum_{i in S_1} alpha_i = sum_{j in S_0} alpha_j, alpha_i ge 0end{aligned}$

可以看到，優化目標和前面講的求凸包最近兩個點之間的最小距離一致

由於 $w$ 垂直於 $H$ ，與凸包間最近兩點連線方向一致（更嚴謹地，在一條直線上，但是方向指向由正類樣本決定），因此實際上最小化 $|!|u-v|!|^2, u in S_1, v in S_0$ 也是在最小化 $|!|w|!|^2$ 。此外，由前面的推導，也有

$w = sum_{i=1}^n alpha_iy_ix_i = C left(sum_{i in S_1} frac{alpha_i}{C} x_i - sum_{j in S_0} frac{alpha_j}{C} x_j ight)$

軟間隔SVM與核SVM

如果數據不是完全線性可分的怎麼辦？這個時候我們可以通過允許訓練數據在分類超平面「錯的」一邊來放鬆之前的限制（不過需要付出一定的代價）。因此我們可以引入**鬆弛變數** $xi_i$ ，約束條件變為

$y_i(x_i^Tw+w_0) ge 1 - xi_i$

當 $0 < xi_i < 1$ 時，該點比支持向量（這裡沒講但是概念懂的）更靠近超平面；當 $xi > 1$ 時，該點在超平面的另一邊

再引入對高維空間的映射函數 $phi(x_i)$ ，則新的求解問題變成了

$egin{aligned}min_{w,w_0,xi_1, ldots, xi_n} &frac{1}{2}|!|w|!|^2 + lambda sum_{i=1}^n xi_i\{ m subject to} &y_i(phi(x_i)^Tw + w_0) ge 1 - xi_i { m for} i = 1,ldots, n \& xi_i ge 0, { m for} i=1,ldots, nend{aligned}$

如果 $lambda ightarrow 0$ ，則對錯分的容忍度變大，反之則表示不允許錯分，因為 $lambda ightarrow infty$ 意味著 $xi_i ightarrow 0$ （通常使用交叉驗證來選擇）

其對偶問題為，以每個 $(alpha_i, mu_i)$ 最大化，以 $w,w_0, xi_1, ldots, xi_n$ 最小化

$mathcal{L} = frac{1}{2}|!|w|!|^2 + lambda sum_{i=1}^n xi_i - sum_{i=1}^n alpha_i(y_i(phi(x_i)^Tw+w_0)-1+xi_i) - sum_{i=1}^n mu_ixi_i \{ m subject to} alpha_i ge 0, mu_i ge 0, y_i(phi(x_i)^Tw+w_0)-1+xi_i ge 0$

可以解得

$w = sum_{i=1}^n alpha_iy_iphi(x_i), sum_{i=1}^n alpha_iy_i = 0, lambda - alpha_i - mu_i = 0$

將 $w$ 和 $mu_i = lambda - alpha_i$ 代回，可知對偶問題為

$egin{aligned}max_{alpha_1, ldots, alpha_n} &mathcal{L} = sum_{i=1}^n alpha_i- frac{1}{2}sum_{i=1}^nsum_{j=1}^n alpha_ialpha_jy_iy_jphi(x_i)^Tphi(x_j) \{ m subject to} &sum_{i=1}^n alpha_iy_i = 0, 0 le alpha_i le lambdaend{aligned}$

其中 $phi(x_i)^Tphi(x_j)$ 可以用核函數 $K(x_i, x_j)$ 替換

分類預測變為求

${ m sign}left(sum_{i=1}^n alpha_iy_i K(x_0, x_i) + w_0 ight)$

注意到對於大多數 $i$ ，有 $alpha_i = 0$ ，因此實際上預測的時候只會用到那些 $alpha_i$ 不為0的點，稱這些點為**支持向量**