本文參考整理了Coursera上由NTU的林軒田講授的《機(jī)器學(xué)習(xí)技法》課程的第四章的內(nèi)容，主要介紹了Soft-Margin SVM和它的對(duì)偶問題的基本推導(dǎo)過程，主要介紹了Soft-Margin引入的動(dòng)機(jī)、dual problem、αn的物理意義(包括bounded SV、free SV、non SV)及SVM中模型和參數(shù)如何選擇等內(nèi)容，文中的圖片都是截取自在線課程的講義。
歡迎到我的博客跟蹤最新的內(nèi)容變化。
如果有任何錯(cuò)誤或者建議，歡迎指出，感激不盡！
--
本系列文章已發(fā)四章，前三章的地址如下：
- 一、線性SVM
- 二、SVM的對(duì)偶問題
- 三、Kernel SVM
引入Soft Margin的動(dòng)機(jī)
利用上一章所講的Kernel，我們可以利用很多復(fù)雜的模型，比如Gaussian Kernel允許我們進(jìn)行無限多維度的特征轉(zhuǎn)換，雖然有Large Margin的控制來減少VC維度，但還是可能Overfitting。產(chǎn)生過擬合的原因，一方面是因?yàn)槲覀兊哪Ｐ蛯?shí)在太powerful，另一方面與我們堅(jiān)持要求分隔界限必須完美劃分OO和XX的Hard Margin要求也密不可分，如果我們能夠放松要求，允許一些點(diǎn)被劃分錯(cuò)誤，也可能會(huì)少fit一些Noise，減少一些Overfitting的可能。
Give Up On Some Examples
在《機(jī)器學(xué)習(xí)基石》中，我們學(xué)到的第一個(gè)模型是Pocket，它的思想是當(dāng)沒有辦法完美分開OO和XX時(shí)，我們找一條犯錯(cuò)誤最少的線就好。
再看Hard-Margin SVM的要求，它的要求更加苛刻，除了要全劃分對(duì)，還要選W最短的，即
類似的，我們將兩者相結(jié)合
系數(shù)C用來衡量Large-Margin和犯錯(cuò)誤之間的相對(duì)重要性。
該問題就是我們的新問題，即Soft-Margin SVM。
化簡(jiǎn)Soft Margin SVM
將正確分類的點(diǎn)的要求和錯(cuò)誤分類的點(diǎn)的要求寫成一個(gè)式子，如下
注意這里有個(gè)問題，這里的運(yùn)算包含一個(gè)[[]]布爾操作，它不是線性約束，所以問題也不再是QP問題，也不再能用之前所推導(dǎo)的對(duì)偶問題、Kernel Trick等技法。
而且，這里也沒辦法區(qū)分錯(cuò)誤的大小，到底錯(cuò)誤點(diǎn)的偏離程度有多大。
下面用一個(gè)新式子來表達(dá)這種帶有錯(cuò)誤衡量的Soft Margin SVM問題，而且該問題還是一個(gè)QP的形式。
我們用ξn來代表(Xn,yn)離正確分類的yn一側(cè)的胖胖的邊界線的錯(cuò)誤偏離程度。即如果是正確的點(diǎn)，應(yīng)該滿足yn(W’Zn+b)>=1，且左側(cè)的值越大，則點(diǎn)離線W’Zn+b=0越遠(yuǎn)，最近的點(diǎn)，即margin上的點(diǎn)，滿足yn(W’Zn+b)=1；而錯(cuò)誤的進(jìn)入了軟性的margin內(nèi)，甚至到達(dá)反向的對(duì)側(cè)的點(diǎn)，yn(W’Zn+b)肯定都嚴(yán)格小于1，且越小偏離越遠(yuǎn)，我們用一個(gè)ξn來衡量這種偏離度，即使得yn(W’Zn+b)>=1-ξn一直成立，同時(shí)要求ξn>=0盡可能小，這樣對(duì)于正確的點(diǎn)，本來就大于1，ξn自然為0；而錯(cuò)誤的點(diǎn)則需要1-正數(shù)ξ來糾正偏離，ξn就衡量了點(diǎn)犯錯(cuò)誤的大小程度。我們之前的式子，用犯錯(cuò)的點(diǎn)的總個(gè)數(shù)來衡量錯(cuò)誤，現(xiàn)在的式子用每個(gè)點(diǎn)的犯錯(cuò)程度的總和來衡量，而且形式也是一個(gè)二次規(guī)劃QP的形式，新的式子如下：
參數(shù)C：large margin和margin violation的trade-off
- C很大：margin-violation的懲罰很大，盡可能少犯錯(cuò)誤
- C很?。簃argin大一點(diǎn)，很多點(diǎn)犯錯(cuò)沒什么大關(guān)系，因?yàn)閼土P很小
該QP問題有d+1+N個(gè)變量，其中d+1是之前的W和b，增加的N個(gè)是記錄每個(gè)點(diǎn)的犯錯(cuò)程度的ξn；有2N個(gè)約束，增加的N個(gè)約束是ξn>=0。
下一步，我們將仿照之前推導(dǎo)Dual SVM的方法，重新推導(dǎo)Soft Margin SVM的對(duì)偶問題，并嘗試?yán)胟ernel trick移除對(duì)d~的依賴。
Soft Margin SVM的對(duì)偶問題
原始問題：
原來變量的約束還是用αn來代表其lagrange multipliers，我們用βn來代表新增加的變量約束ξn>=0的lagrange multipliers，得到Lagrange Function如下：
其對(duì)應(yīng)的Lagrange Dual問題如下：
代入Lagrange Function，如下
對(duì)變量ξn偏微分，
所以，我們可以把βn換成C-αn，再滿足條件βn>=0，則有αn<=C，加上原來的條件αn>=0，則得到0<=αn<=C，這樣就完全不用考慮β了。
用C-αn消去β后，化簡(jiǎn)后如下
發(fā)現(xiàn)，所有的ξn也被消掉了，就像之前在Hard-Margin SVM Dual的問題中，把b消去一樣。
式子變簡(jiǎn)單了，如下
發(fā)現(xiàn)這個(gè)式子和之前Hard Margin SVM的Lagrange Dual基本一樣，只是多了αn<=C的條件，接下來按照之前的步驟化簡(jiǎn)，對(duì)b微分，消去b,對(duì)W微分，用αn對(duì)ynZn的線性表示替換W，變成只有一個(gè)變量α的最優(yōu)化問題，比較簡(jiǎn)單，請(qǐng)參考前面推導(dǎo)Hard Margin SVM Dual的過程。
最終會(huì)得到Soft Margin SVM Dual的標(biāo)準(zhǔn)形式。
Standard Soft-Margin SVM Dual
唯一的差別就是增加了條件αn<=C和隱式的βn=C-αn的條件。
這是另外一個(gè)QP問題，有N個(gè)變量，2N+1個(gè)條件，它也是個(gè)convex的問題。
Kernel Soft-Margin SVM
基本過程
基本和Hard-Margin一樣，但是比Hard-Margin更加靈活，因?yàn)榭梢钥刂茀?shù)C。
而且Soft-Margin不論是Primal還是Dual總是有解，而不像Hard-Margin的問題需要數(shù)據(jù)linear-separable，因此在實(shí)踐中Soft-Margin經(jīng)常使用。
如何算b?
對(duì)于Hard-Margin SVM，我們利用互補(bǔ)松弛條件和一個(gè)SV就可以算出b
對(duì)于Soft-Margin SVM，也有類似的complementary slackness條件
所以，要解出唯一的b，需要找一個(gè)自由支撐向量(Xs,ys)，即0<αs<C，則
如果沒有free SV（極少數(shù)的情況下），則b只能被一堆不等式所表示，只要不等式范圍內(nèi)的b滿足所有的KKT條件，則這些b都是可以的。
實(shí)際的Soft-Margin Gaussian SVM
灰色的部分代表margin內(nèi)部，越大的C，對(duì)錯(cuò)誤的懲罰就越大，就盡可能少犯錯(cuò)，就越可能fit Noise，對(duì)Noise的容忍度就越小，就越可能Overfit。
注意：如果參數(shù)調(diào)節(jié)不好，就算是Soft-Margin SVM還是有可能產(chǎn)生Overfit的!
因此，對(duì)于Soft-Margin Gaussian SVM，我們需要仔細(xì)地選擇參數(shù)(γ,C)。
αn的物理含義
哈利波特條件(Complementary Slackness):
之所以叫哈利波特條件，是因?yàn)樽筮叺膬蓚€(gè)括號(hào)，如果一個(gè)不為0，另一個(gè)一定為0，就像哈利波特和伏地魔兩者至少必有一個(gè)死亡。
可以把點(diǎn)分成3類：
- free SV：0 < αn < C，ξn = 0，可以用來確定b，可以算出yn(W’Zn+b)=1，意味著點(diǎn)(Xs,ys)在胖胖的邊界上，在上圖中用□代表。
- non SV：αn = 0，ξn = 0，意味著沒有犯錯(cuò)，大部分可能落在胖胖的邊界的正確一側(cè)的外面，極少數(shù)可能剛剛好落在胖胖的邊界上，在上圖中它們就是不用□或者△圈出的點(diǎn)。
- bounded SV：αn = C，則ξn = 1 - y(W’Zn+b)，即ξn = violation amount，在上圖中用△代表。極少數(shù)的情形，點(diǎn)剛剛好在邊界上，大部分來說，只要看到αn=C，就意味著它違反了胖胖的邊界。
注意：violation有兩種，一種是小小的違反，只是進(jìn)入margin而沒有跨過中線，雖然有小小的違反，但是沒有造成我們的分類錯(cuò)誤；還有一種是大大的違反，已經(jīng)跨過中線，造成分類錯(cuò)誤。
因此，利用αn可以幫助我們進(jìn)行數(shù)據(jù)的分析。
bounded SV是唯一可能造成Ein錯(cuò)誤的點(diǎn)，如果ξn>=1，意味著這種violation造成了0/1分類錯(cuò)誤，如果0<=ξn<1，就不會(huì)造成0/1分類錯(cuò)誤。因此，Ein的可能范圍在0.0000<=Ein(gsvm)<=#(bounded SVs)/N
實(shí)踐需要：模型選擇
上圖9個(gè)全部都是Soft-Margin Gaussian SVM，橫軸是使用了不同的參數(shù)C，縱軸是使用了不同的參數(shù)γ。
如何選擇哪組參數(shù)對(duì)應(yīng)的模型最好呢?
之前《機(jī)器學(xué)習(xí)基石》課程告訴我們最簡(jiǎn)單好用的工具就是Validation。
V折交叉驗(yàn)證
利用Cross Validation的值選擇
我們能不能做最優(yōu)化？
不能。因?yàn)閷?duì)于每個(gè)(C,γ)，Ecv(C,γ)不是(C,γ)的平滑函數(shù)，很難最優(yōu)化，通常只能送進(jìn)去幾個(gè)不同的(C,γ)值，看看哪一個(gè)最好。
我么可以用V-fold cross Validation在幾個(gè)不同的(C,γ)上選擇最合適的model。
對(duì)于SVM來說，Cross Validation是一個(gè)非常常用的方式來選擇適當(dāng)?shù)膮?shù)。
Leave-One-Out CV
V-fold的極限：E(loocv) = E(cv) with N folds
LOO在SVM有一個(gè)有趣的結(jié)果：
證明：對(duì)于點(diǎn)(Xn,yn)，如果剛好最優(yōu)αn=0，即說明該點(diǎn)不是SV，則對(duì)于去掉點(diǎn)(Xn,yn)后的數(shù)據(jù)集，(α1，α2，α3....αn-1，αn+1,...,αN)這一組α仍然是去掉點(diǎn)后的數(shù)據(jù)集的最優(yōu)解，假設(shè)不是最優(yōu)解，存在更好的解，把αn=0加回去，則構(gòu)造了最開始數(shù)據(jù)集的一個(gè)更優(yōu)解，矛盾。
則對(duì)SVM來說,g-=g（當(dāng)去掉一個(gè)non-SV點(diǎn)后）
而e(SV) <= 1
則不難得到以上bound，即E(loocv) <= #SV/N
所以，我們可以近似用這個(gè)做模型的選擇
利用#SV做模型的選擇
數(shù)字是SV的數(shù)量。
注意：#SV只是一個(gè)上限，并不代表真正的loocv。
常用#SV來排除一些危險(xiǎn)的模型，再做cross validation選擇一個(gè)最適合的參數(shù)。即#SV常用來做安全檢查(safety-check)，如果計(jì)算Ecv太過于耗時(shí)。
Mind Map Summary
我們從最開始的Linear Hard-Margin SVM開始推導(dǎo)，研究了它的Dual Problem，并利用Kernel Trick簡(jiǎn)化了transform + inner product的運(yùn)算，這一講又討論了在實(shí)踐中最常用的Soft-Margin SVM的問題，但這些都是在做最基本的binary classification，下一講我們將把學(xué)過的SVM模型應(yīng)用到更多的問題上，比如soft binary classification，即logistic regression問題，敬請(qǐng)關(guān)注。
