【機器學習 05】Support Vector Machine — Part 1 — Linear Support Vector Machine & Dual Support Vector Machine
今天我們來介紹 linear support vector machine 和 dual support vector machine。
Linear support vector machine
為什麼想要 Large-Margin？
在一個散布圖中，通常會有非常多種能夠分割的畫線方式，要怎麼知道哪一條線最適合？
我們希望這條線和最靠近的 data 的距離最大，因為 testing data 和 training data 可能有誤差，如果 xₙ（離最近的點）和 hyperplane 的距離越遠，就能夠容忍更多誤差 noise，並且更 robust to overfitting
目標：找到離最遠的 separating hyperplane
如何計算和 hyperplane 之間的距離？
請見以下的推導過程。
目前的最佳化問題可寫成：
但是，我們不喜歡不等式，因為不好解，因此會經過如下圖的步驟以簡化。
以上即為 SVM 的最佳化式子，我們的目標是找到在最胖的邊界以及邊界上的點，其他點都不重要，而在邊界上的點稱為 support vectors。
要如何解出上面的最佳化式子？直接用手動計算不容易，因此使用二次規劃方法解決（quadratic programming, QP）。在這邊我們不深入探討 QP 方法，總之只要按照 QP 的標準形式填入即可。
按照這些步驟得到的 SVM，會是 hard-margin & linear。
- hard-margin：沒有任何違反邊界的例子
- linear：xₙ
雖然 linear SVM 已經夠好了，還是希望能夠找到 non-linear SVM，讓 boundary sophisticated → 將 x 做非線性轉換。
究竟要如何做到呢？讓我們繼續看下去吧。
Dual Support Vector Machine
如果想要將 x 轉換到更多維度的空間，解二次規劃問題時會受到 dimension d 的影響，但是我們不想要被 d 限制。
目標：SVM without dependence on d
以上目標等同於解 based on some dual problem of Original SVM，可利用在 regularization 介紹過的 Lagrange multipliers 幫助，只是在這裡不寫 λ，而用 α 代替。
但是和 regularization 不同之處是，在 regularization 將 λ 視為已知參數，而 dual SVM 則是將 λ 視為未知變數，再求解。
那要如何求解呢？請見以下推導步驟。
經過以上步驟，我們得到 Lagrange dual problem 的最佳化式子，喘口氣後，讓我們一起繼續解下去吧。
最後，利用 KKT (Karush-Kuhn-Tucker, KKT, conditions) 解出最佳化的 α，再求 b 和 w。
由 optimal b 可知，當 αₙ > 0，這些點就是在邊界上的 support vectors。其他點不重要，重要的只有在邊界上的點，就可以算出 b 和 w。
想要更深入了解的話，別忘了去最上面的目錄看其他章的課程筆記！
喜歡這篇文章或是對你有幫助的話，別忘了拍手給我鼓勵哦 👏🏻參考資料
- 林軒田，機器學習基石與技法：https://www.youtube.com/c/hsuantien/playlists
