機器學習_學習筆記系列(19)：軟性邊界對偶支撐向量機(Soft-Margin Dual Support Vector Machine)
上一篇我們講到Soft-Margin SVM，其允許一些點分類錯誤，來降低模型複雜度，並提高泛化能力，但是在Soft-Margin中，我們一樣會碰到特徵轉換後，維度過高難以用QP求解的情況。但是對於此，我們一樣可以把Primal轉為Dual來做運算。
Soft-Margin Dual Support Vector Machine
在一開此我們回顧一下Soft-Margin Primal SVM的最佳化問題
所以這裡比照Hard-Margin中Primal轉Dual的方法
對於Soft-Margin我們也先寫下我們的Lagrange Function
這裡一樣比照Hard-Margin，寫出我們的最佳化問題
同樣的，我們知道
其中左邊的為Primal最佳化問題，右邊的為Dual最佳化問題。所以如果要讓大於等於的關係變成等於，必須符合KKT condition，接下來一樣也是超複雜的推倒。原本的最佳化問題為
首先針對zeta
所以說，因為β≥0，可以推出C≥α≥0。之後帶入上面的關係式，我們可以改寫成
我們到這裡可以發現，其就和我們Hard-Margin的最佳化問題
非常接近了。所以對w和b的微分，我們可以比照Hard-Margin那篇，求出我們最後的最佳化方程式
也就是說
所以我們可以看到他和Hard-Margin不一樣的地方就在，其對α多加上了一個限制C。而在意義上，我們知道在Hard-Margin中α>0的話就是我們的support vector(SV)，α等於0的話代表不是SV。
所以在Soft-Margin中多加一個C，代表在Primal中滿足
而我們也知道在Hard-Margin中，代表在Primal中滿足
這裡我們可以用一點小邏輯推出，其意思就是今天我們知道α=0為margin以外的數據點，所以對於margin以內的數據點(α≠0)，如果zeta為0，代表其滿足
所以也就是說如果數據點的zeta=0且α≠0，代表說他剛好落在margin line上，也就是我們的Bounded SV。
另一方面，如果zeta≠0且α≠0，代表C一定要等於α，而且其使得
他剛好落在margin line內部，也就是我們的Free SV。
這裡總結一下
QP with Kernel Trick
接下來就是進入二次規劃的求解
這裡設有N筆資料，然後一樣對特徵進行Kernel Trick。而我們現在變成有N個變數，2N+1個限制，所以
一樣套入二次規劃中
就可以計算出我們的分割線
其中
接下來我們實際用Python把他視覺化(黑色底：Bounded SV / 紫色底：Free SV)
Polynomial Kernel (次方:10 / Gamma:1 / Zeta=1)
Gaussian Kernel (Gamma:1)
我們可以發現，當C越大，他的分類線會越來越複雜，趨近於Hard-Margin。
Python Sample Code:
Github:
Reference:
[1] Coursera, 機器學習技法, 林軒田 教授
