【機器學習 06】Support Vector Machine — Part 2— Kernel Support Vector Machine & Soft-Margin Support Vector Machine

上篇介紹的 dual SVM 之目的是要讓 SVM 的計算上不需要仰賴 dimension d。然而，我們只完成一半，因為在算二次規劃問題時，還是需要計算被轉換維度後的內積，如果 dimension 很大的話就要算很久。

解 dual SVM 需要計算 qₙ,ₘ = yₙyₘZₙᵗZₘ
-> 需要計算轉換為度後的內積

那我們是否能夠先算內積之後再轉換？

答案是可以的！

而這其實就是所謂的 kernel function，以下是三種常見的 kernel functions：

• Linear kernel
• Polynomial kernel
• Gaussian kernel = RBF kernel

三者的比較請見下面的表格：

Soft-Margin Support Vector Machine

之前我們介紹的 SVM 都是 hard-margin，而此種型態的 SVM 有一個缺點，就是容易 overfit。因為我們堅持要 separable，所以可能會因為 noisy examples 而造成 overfitting。

解法：放棄一些 noisy examples，結合 pocket （犯最少錯誤）和 hard-margin SVM，用 C 來調節 large margin & noise tolerance 的 trade-off。

以下是 soft-margin SVM 的推導過程，從 hard-margin 出發，用 εₙ 代替 margin violation 那一項，最後產生兩項限制條件 αₙ 和 βₙ。

推導完後，會發現其實和 hard-margin 很相似，唯一的區別是 αₙ 有上限：
0 ≤ αₙ ≤ C。

• large C：想要比較少的 margin violation
• small C：想要比較大的 margin

hard-margin 也能夠用 kernel 帶入。

最後，讓我們來看 αₙ 的 physical meaning，利用 complementary slackness 會產生三種 support vectors：

1. Non SV：αₙ = 0、εₙ = 0，沒有違反，不在邊界上
2. Free SV：0 < αₙ < C、εₙ = 0，在邊界上
3. Bounded SV：αₙ = C、εₙ ≠ 0，違反邊界的點

想要更深入了解的話，別忘了去最上面的目錄看其他章的課程筆記！

喜歡這篇文章或是對你有幫助的話，別忘了拍手給我鼓勵哦 👏🏻

參考資料

1. 林軒田，機器學習基石與技法：https://www.youtube.com/c/hsuantien/playlists