本文參考整理了Coursera上由NTU的林軒田講授的《機(jī)器學(xué)習(xí)技法》課程的第二章的內(nèi)容容握，主要介紹了Hard Margin SVM Dual的基本概念和求解方法叼屠、支撐向量的幾何含義等，文中的圖片都是截取自在線課程的講義侦高。
歡迎到我的博客跟蹤最新的內(nèi)容變化鳖昌。
如果有任何錯(cuò)誤或者建議，歡迎指出计盒，感激不盡！
對(duì)偶問(wèn)題的動(dòng)機(jī)
原來(lái)的SVM如果要進(jìn)行非線性變換芽丹，需要在轉(zhuǎn)換后的Z空間(假設(shè)為d~維度)內(nèi)進(jìn)行l(wèi)inear SVM的求解北启，則在Z空間里的線性分類對(duì)應(yīng)到原來(lái)的X空間可能就是一個(gè)non-linear的復(fù)雜邊界。
問(wèn)題：Z空間的QP問(wèn)題有d+1個(gè)變量拔第、N個(gè)約束咕村。如果d非常大甚至無(wú)窮大，就很難甚至不可能求解蚊俺。
目標(biāo)：讓SVM模型的求解不再依賴轉(zhuǎn)換后的空間維度d~懈涛，以能夠使用非常多的、非常復(fù)雜的特征轉(zhuǎn)換泳猬。
將original問(wèn)題轉(zhuǎn)換為dual(對(duì)偶)問(wèn)題批钠，該問(wèn)題與原問(wèn)題等價(jià)即可。
基本工具: Lagrange Multipliers
將Lagrange Multipliers當(dāng)做變量求解得封，SVM中的每一個(gè)條件都會(huì)對(duì)應(yīng)一個(gè)Lagrange Multiplier埋心，所以共有N個(gè)變量。
注意:在SVM的文獻(xiàn)中通常把Lagrange Multipliers的λ叫做α忙上。
出發(fā)點(diǎn)
將有約束優(yōu)化問(wèn)題轉(zhuǎn)換為無(wú)約束的優(yōu)化問(wèn)題拷呆。
原始問(wèn)題：
定義Lagrange Function:
則原始問(wèn)題等價(jià)于
如何證明兩個(gè)問(wèn)題的解一樣？
考慮兩種情況：
- 如果某個(gè)(b,W)不滿足原始問(wèn)題的N個(gè)條件之一晨横，即某個(gè)1-yn(W’Zn+b)＞0洋腮，則內(nèi)部的Max操作會(huì)將αn推向無(wú)窮大，在min操作中會(huì)被淘汰手形。
- 如果某個(gè)(b,W)滿足原始問(wèn)題的所有約束啥供，則內(nèi)部Max將所有的αi都推向0，即內(nèi)部的max結(jié)果就是目標(biāo)的1/2W’W的值库糠，在外部的min操作中就會(huì)取得滿足條件的(b,W)中目標(biāo)函數(shù)最小的組合伙狐，和原始問(wèn)題一樣。
本質(zhì)上就是把條件藏在了max操作里面瞬欧，不滿足條件的(b,W)一定不會(huì)被選擇贷屎。
現(xiàn)在我們有了新的問(wèn)題，它有哪些性質(zhì)呢艘虎？
對(duì)于任何確定的α'【滿足每一個(gè)元素α'n>=0】唉侄，則有
因?yàn)閷?duì)于某一個(gè)(b,W)，內(nèi)部的max(L)始終大于等于L野建，則左邊的最低點(diǎn)也一定大于等于右邊的最低點(diǎn)属划。
簡(jiǎn)單地說(shuō)恬叹，因?yàn)閙ax>=any。
因?yàn)閷?duì)于任何α'都有上式成立同眯，所以
因?yàn)樽畲蟮氖侨我獾摩?中的某一個(gè)绽昼。
觀察發(fā)現(xiàn)，只不過(guò)是把min和max操作交換了順序须蜗，稱該問(wèn)題為L(zhǎng)agrange對(duì)偶問(wèn)題硅确。
只要我們解決了Lagrange Dual Problem，就得到了original problem的一個(gè)下限明肮。
對(duì)偶性的強(qiáng)弱
- '>='：弱對(duì)偶性(weak duality)
- '=': 強(qiáng)對(duì)偶性(strong duality)
由最優(yōu)化理論可得：
對(duì)于QP問(wèn)題菱农，如果滿足：
- 原始問(wèn)題是凸型的 convex primal
- 原始問(wèn)題是有解的(如果Φ轉(zhuǎn)換后數(shù)據(jù)點(diǎn)是線性可分的，則成立) feasible primal
- 線性約束條件
稱為 '條件資格' (constraint qualification)晤愧。
則對(duì)偶問(wèn)題是強(qiáng)對(duì)偶問(wèn)題大莫，即存在原始-對(duì)偶最優(yōu)解(b,W,α)在兩側(cè)都能最優(yōu)。
化簡(jiǎn)對(duì)偶問(wèn)題
inner problem：里面的問(wèn)題官份，即min操作，是沒(méi)有條件約束的烙丛，因此在最優(yōu)點(diǎn)上舅巷，滿足：
因此，加上該條件的最優(yōu)解不變河咽。
加上該條件钠右，可以把變量b消去。
同理忘蟹，對(duì)W進(jìn)行類似的處理：
把最優(yōu)解的條件加在對(duì)偶問(wèn)題上：
求解b和W
現(xiàn)在最佳化問(wèn)題只有變量α了飒房，其他變量b和W根據(jù)和α的關(guān)系被α所表示。
求得α后媚值，再根據(jù)這些關(guān)系求出b和W狠毯。
這些關(guān)系，我們一般叫做KKT最優(yōu)條件(KKT Optimality Conditions)
KKT是三個(gè)做最優(yōu)化的研究者的名字首字母(Karush-Kuhn-Tucker)褥芒。
如果原始-對(duì)偶最優(yōu)解(b,W,α)：
其中第4個(gè)條件嚼松，一般稱為互補(bǔ)松弛條件(complementary slackness)
以上的推導(dǎo)說(shuō)明KKT條件是最優(yōu)解的必要條件[necessary]，但也可以證明對(duì)于我們的問(wèn)題來(lái)說(shuō)锰扶，它也是充分的[sufficient]献酗。
因此我們可以利用KKT條件根據(jù)最優(yōu)的α來(lái)求解(b,W)。
Standard Hard-Margin SVM dual
再做一些微小的改寫：
該問(wèn)題稱為“標(biāo)準(zhǔn)硬邊界SVM的對(duì)偶問(wèn)題”坷牛。
該問(wèn)題仍然是一個(gè)QP凸問(wèn)題罕偎，有N個(gè)變量(α1..N)，N+1個(gè)條件(一個(gè)=0京闰，N個(gè)>=0)颜及。
仍然使用QP Solver求解甩苛。
QP系數(shù)
注意：很多QP程序可以很方便的直接特殊處理等式(A>=、A<=)或者邊界類條件(an>=0)器予，這樣可以保證它們的數(shù)值穩(wěn)定性
Q矩陣中的元素q(n,m)一般非0浪藻，是稠密矩陣(dense)，且N大時(shí)乾翔，Q矩陣很大爱葵。
因此需要特殊的求解QP的程序(專門為SVM設(shè)計(jì)的)，不存儲(chǔ)整個(gè)Q矩陣反浓，或者利用SVM的一些特殊條件來(lái)加速求解萌丈。
因此在實(shí)踐中，我們通常最好使用特別為SVM設(shè)計(jì)的QP求解算法雷则。
獲得b和W
利用KKT條件：
得到W:
得到b:
和b有關(guān)的約束
只能告訴我們一個(gè)b的范圍
如果某個(gè)αn>0 ==> (1 - yn(W’Zn + b)) = 0
兩邊都乘上yn辆雾，得
(yn - (W’Zn + b)) = 0
即
b = yn - W’Zn
上式告訴我們 yn(W’Zn + b) = 1，說(shuō)明該點(diǎn)在胖胖的邊界上月劈，即是一個(gè)支撐向量(Support Vector)度迂。
支撐向量的確切定義
我們把αn>0的點(diǎn)(Zn,yn)叫做support vectors，即支撐向量猜揪。
它一定在胖胖的邊界上惭墓，但不是所有在胖胖的邊界上的點(diǎn)都是SV，它們都是support vectors candidate而姐。
即
SV的性質(zhì)
計(jì)算W和b時(shí)腊凶，只需要用到支撐向量SV的點(diǎn)。
所以SVM是一種利用求解對(duì)偶問(wèn)題的最優(yōu)解拴念，找出支撐向量來(lái)學(xué)習(xí)出最胖的分隔超平面的過(guò)程钧萍。
最胖分隔超平面的表示形式
即W是ynZn的線性組合。
這對(duì)于當(dāng)W0=0時(shí)政鼠，使用GD/SGD的LogReg或者LinReg也成立风瘦。
稱作 W 能夠被 數(shù)據(jù)點(diǎn) 所表示(represented)。
SVM: 只需要SV就可以線性表示出W缔俄。
PLA: 只需要犯錯(cuò)的點(diǎn)就可以線性表示W(wǎng)弛秋。
Hard-Margin SVM的兩種形式
兩者最終都是得到最優(yōu)的假設(shè)函數(shù)：
我們真的做到脫離d~了嗎？
其實(shí)沒(méi)有俐载，計(jì)算Q矩陣時(shí)蟹略，每個(gè)q(n,m)都需要計(jì)算Zn'Zm，這是一個(gè)在R(d)空間中的兩個(gè)向量的內(nèi)積遏佣，需要時(shí)間至少為O(d)挖炬。
因此我們要想辦法避開(kāi)計(jì)算轉(zhuǎn)換后的高維空間中向量的內(nèi)積。
這部分內(nèi)容需要利用kernel function的威力状婶，我們?cè)谙乱恢v進(jìn)行探討意敛。
Mind Map Summary
有關(guān)Kernel SVM及更多機(jī)器學(xué)習(xí)算法相關(guān)的內(nèi)容將在日后的幾篇文章中分別給出馅巷，敬請(qǐng)關(guān)注！
