Linear Support Vector Machine

Large-Margin Separating Hyperplane

當訓練資料線性可分時，我們有以下三條線可以把資料分對，哪一條線更好？

如果用 PLA 來看的話，每次有錯誤分類就會修改一下線的方向，并沒有偏好，答案是隨機的；如果用 VC Bound 來看的話，$E_{out} (w) \leq E_{in}(w)+\Omega(H)​$Eout​(w)≤Ein​(w)+Ω(H)​，因為三條線對訓練數據都分對了，所以$E_{in}(w)=0​$Ein​(w)=0​，而$\Omega(H)​$Ω(H)​是複雜度，複雜度與$d_{vc}=d+1​$dvc​=d+1​有關，d是資料維度，所以這三條線也分不出高下；但如果我們來看的話，大多數人會選最右邊的那條線。

為什麼右邊那條線最好呢？訓練資料標在圖上，之後會有一些測試資料，測試資料與訓練資料會有一些差異（可能由於測量誤差或本來分佈上的差異等），假設測試資料和訓練資料有一些 Gaussian noise ，我們希望我們的這條線在面對測試資料的時候也能像面對訓練資料時分得一樣好。那訓練資料離線越遠的話，也就能容忍更多雜訊，雜訊是造成overfitting的主要原因，所以訓練資料離線越遠，也就更能避免發生 overfitting 。從線的角度來看，線到離它最近的訓練資料的距離越大，那線對雜訊容忍度就越高，這條線就魯棒性更好。所以最右邊的線離最近的訓練資料的距離越大，它的魯棒性最好。

上圖的灰色圓圈就表示了對測量誤差的容忍度，下圖的灰色區域表示了線到離它最近的訓練資料的距離，灰色區域越胖就是魯棒性越好。我們的目標就是找到一條線，這條線能分對所有的訓練資料，並且這條線的灰色區域最胖（離最近的訓練資料的距離越大），這條線的術語就是 Large-Margin Separating Hyperplane 。

Standard Large-Margin Problem

我們把 hypothesis 寫成$h(x)=sign(w^Tx+b)​$h(x)=sign(wTx+b)​ (b就是以前的$w_0​$w0​​)，然後利用一些關係求出點到平面的距離。

化簡：先去掉絕對值。對於每個訓練資料都要正確，有$y_n(w^T x_n+b)>0​$yn​(wTxn​+b)>0​，於是得到$margin(b,w)= min_{n=1,..,N}\frac{1}{||w||}y_n(w^T x_n+b)​$margin(b,w)=minn=1,..,N​∣∣w∣∣1​yn​(wTxn​+b)​

所以找 Large-Margin Separating Hyperplane 也就是找

為了式子更簡單，我們假設$min_{n=1,..,N} y_n(w^T x_n+b)=1​$minn=1,..,N​yn​(wTxn​+b)=1​，同時這個假設也滿足第一個條件$y_n(w^T x_n+b)>0​$yn​(wTxn​+b)>0​，即化簡為
$min_{n=1,..,N} y_n(w^T x_n+b)=1​$minn=1,..,N​yn​(wTxn​+b)=1​ 這個假設可以改寫成 $y_n(w^T x_n+b)\geq1​$yn​(wTxn​+b)≥1​ for all $n​$n​

這樣推廣后，我們還是可以保證最優解滿足$min_{n=1,..,N} y_n(w^T x_n+b)=1​$minn=1,..,N​yn​(wTxn​+b)=1​ 。證明如下：

假設$min_{n=1,..,N} y_n(w^T x_n+b)=a(設為1.126)>1$minn=1,..,N​yn​(wTxn​+b)=a(設為1.126)>1 ，即$y_n(w^T x_n+b)\geq1.126$yn​(wTxn​+b)≥1.126 for all $n$n。對於 hyperplane 的方程 $w^T x+b=0$wTx+b=0，乘以任何係數表示的是同一個 hyperplane。假設最優解為$(b,w)$(b,w)，我們可以縮放最優解 $(b,w)$(b,w)，得到$(b',w')=(\frac{b}{1.126},\frac{w}{1.126})$(b′,w′)=(1.126b​,1.126w​)，滿足$min_{n=1,..,N} y_n(w'^T x_n+b')=1$minn=1,..,N​yn​(w′Txn​+b′)=1，而$(b',w')$(b′,w′)表示的依舊是最優解 hyperplane 的方程。所以當條件推廣為$y_n(w^T x_n+b)\geq1$yn​(wTxn​+b)≥1時，我們可以通過縮放$(b,w)$(b,w)來滿足$min_{n=1,..,N} y_n(w^T x_n+b)=1$minn=1,..,N​yn​(wTxn​+b)=1，並且不影響最優解。

為了把式子表示成熟悉的最佳化問題的形式，我們將這個式子再進行一些變換，得到下式：

Support Vector Machine

SVM 支撐向量機這個術語是什麼意思呢？

找出最胖的平面時，在邊界上的點確定了最胖平面的位置，其他的點對於平面位置確定是沒有影響的，所以我們就把在邊界上的資料點稱為 support vector 支撐向量（的候選人）。所以 SVM 支撐向量機就是利用支撐向量找到最胖平面的方法。

那要怎麼解決普遍的 SVM 問題呢？幸運的是，我們可以用凸函數最佳化中的二次規劃 (Quadratic Programming, QP)來解決這類問題。我們只要把 SVM 的表達式改寫成 QP 問題的標準形式，再利用一些可解決 QP 問題的工具就可找到 SVM 的最佳解了。


於是我們就得到了 Linear Hard-Margin SVM Algorithm ， Hard-Margin 指對每個訓練資料都是正確分類的。線性是指資料線性可分，如果要處理非線性資料，就先將資料做轉換，保證資料在新的空間中線性可分。

Reasons behind Large-Margin Hyperplane

將 SVM 與之前學的 regularization 比較，regularization 是要最小化$E_{in}$Ein​，但為了避免 overfitting ，對$w$w的長度加了約束條件； SVM 則是在保證$E_{in}=0$Ein​=0 的情況下，最小化$w$w長度。兩者做的是類似的事情，所以 SVM 也是一種 regularization。

另外一種解釋是從 VC dim 角度出發。我們考慮一個 SVM 算法，它對線的胖瘦有要求，這樣它能表示的 dichotomies 因為受限制會更少些，如下圖在單位圓上的三個點，任意兩點間的距離小於 $\sqrt{3}$3​ ，如果要求$\rho>\frac{\sqrt{3}}{2}$ρ>23​​的話，就無法 shatter 3個點。 所以 Large-Margin Algorithm 的 VC dim 是和資料有關的，可以理解成它的有效 VC dim 更小（當訓練資料在半徑為R的圓上，$d_{vc}$dvc​就是下圖的式子），那 $E_{in}$Ein​ 和 $E_{out}​$Eout​​ 就會更接近。

Hyperplanes + feature transform 能得到複雜（彎彎曲曲）的邊界，可正確分類比較複雜的資料，但同時 VC dim 比較大，而 large-margin hyperplanes 的有效 VC dim 比較小，但邊界簡單，對複雜資料不一定表現好，所以我們就結合這兩者的優點，利用非線性 SVM ，既可使模型複雜度低，又可得到複雜邊界，對複雜資料表現較好。

Summary