iT邦幫忙

2019 iT 邦幫忙鐵人賽

DAY 6
0

雖然標題是說"標準" SVM,不過模型這種東西從來就沒有什麼標準,有的不過是變體。

所以這篇是要跟大家總結一下我們一般在用的 SVM 模型的預設值是長什麼樣子。

我們前面從 maximum-margin classifier 出發,尋找最大 margin 的分類器。

接著,為了解決非線性跟計算效能問題,引進了 kernel trick。

最後,為了避免 overfitting,我們放寬了 margin 成為 soft-margin。

這些都是標準 SVM 的預設配備。

當然還有為了解決計算效能問題,使用了 Lagrange multiplier,由於背後的數學太過煩雜就不介紹了。

簡單來說,Lagrange multiplier 的使用,讓原本的問題(primal problem)可以有另外的對偶問題(dual problem)。

我們只要解了對偶問題,我們就可以解掉原本的問題,雖然有時候會碰到一些限制。

原本問題的陳述是這樣的:

https://chart.googleapis.com/chart?cht=tx&chl=%5Cbegin%7Balign%7D%20%5Carg%5Cmin_%7B%5Cmathbf%7Bw%7D%2C%20b%2C%20%5Cboldsymbol%7B%5Cxi%7D%7D%20%26%5C%20%5C%20%5C%20%5C%20%20%20%20%20%20%5Cfrac%7B1%7D%7B2%7D%20%5Cmathbf%7Bw%7D%5ET%5Cmathbf%7Bw%7D%20%2B%20C%20%5Csum%20_%7Bn%3D1%7D%5EN%20%5Cxi_n%20%5C%5C%5C%5C%20%5Cend%7Balign%7D

https://chart.googleapis.com/chart?cht=tx&chl=%5Cbegin%7Balign%7D%20%5Ctext%7Bsubject%20to%7D%20%26%5C%20%5C%20%5C%20%5C%20%20%20%20%20%20%5Cforall%20i%2C%20y_i%20(%5Cmathbf%7Bw%7D%5ET%5Cmathbf%7Bx_i%7D%20%2B%20b)%20%5Cge%201%20-%20%5Cxi_n%20%5C%5C%5C%5C%20%5Cend%7Balign%7D

https://chart.googleapis.com/chart?cht=tx&chl=%5Cbegin%7Balign%7D%20%5Ctext%7B%20%7D%20%26%5C%20%5C%20%5C%20%5C%20%20%20%20%20%20%5Cforall%20n%2C%20%5Cxi_n%20%5Cge%200%20%5Cend%7Balign%7D

轉變成對偶問題然後簡化後的陳述是這樣的:

https://chart.googleapis.com/chart?cht=tx&chl=%5Cbegin%7Balign%7D%20%5Carg%5Cmin_%7B%5Cboldsymbol%7B%5Calpha%7D%7D%20%26%5C%20%5C%20%5C%20%5C%20%20%20%20%20%20%5Cfrac%7B1%7D%7B2%7D%20%5Csum%20_%7Bn%3D1%7D%5E%7BN%7D%20%5Csum%20_%7Bm%3D1%7D%5E%7BN%7D%20%5Calpha_n%20%5Calpha_m%20y_n%20y_m%20%5Cmathbf%7Bz_n%7D%5ET%5Cmathbf%7Bz_m%7D%20-%20%5Csum%20_%7Bn%3D1%7D%5EN%20%5Calpha_n%20%5C%5C%5C%5C%20%5Cend%7Balign%7D

https://chart.googleapis.com/chart?cht=tx&chl=%5Cbegin%7Balign%7D%20%5Ctext%7Bsubject%20to%7D%20%26%5C%20%5C%20%5C%20%5C%20%20%20%20%20%20%5Csum_%7Bn%3D1%7D%5E%7BN%7D%20%5Calpha_n%20y_n%20%3D%200%2C%200%20%5Cle%20%5Calpha_n%20%5Cle%20C%20%5C%5C%5C%5C%20%5Cend%7Balign%7D

https://chart.googleapis.com/chart?cht=tx&chl=%5Cbegin%7Balign%7D%20%5Ctext%7B%20%7D%20%26%5C%20%5C%20%5C%20%5C%20%20%20%20%20%20%5Cmathbf%7Bw%7D%20%3D%20%5Csum_%7Bn%3D1%7D%5E%7BN%7D%20%5Calpha_n%20y_n%20%5Cmathbf%7Bz_n%7D%20%5Cend%7Balign%7D

不要問我怎麼來的,你一問我就要開始另一篇數學了,你會怕。

解完上面的問題,我們可以得到一些資訊,我們可以從 https://chart.googleapis.com/chart?cht=tx&chl=%5Calpha_n 的數值範圍來得知一個資料點他是不是 support vector。

只要他的值在 https://chart.googleapis.com/chart?cht=tx&chl=0%20%3C%20%5Calpha_n%20%3C%20C 這個範圍,他就是 support vector。

我們最後在形成整個 SVM 模型的時候其實只需要這些 support vector 就可以了。

https://chart.googleapis.com/chart?cht=tx&chl=SVM(%5Cmathbf%7Bx%7D)%20%3D%20sign(%5Csum_%7BSV%7D%20%5Calpha_n%20y_n%20K(%5Cmathbf%7Bx_n%7D%2C%20%5Cmathbf%7Bx%7D)%20%2B%20b)


上一篇
06 從 hard-margin SVM 到 soft-margin SVM
下一篇
08 l2-regularized 線性模型
系列文
機器學習模型圖書館:從傳統模型到深度學習31

尚未有邦友留言

立即登入留言