2拉格朗日對(duì)偶(Lagrangeduality)先拋開上面的二次規(guī)劃問題，先來看看存在等式約束的極值問題求法，比如下面的最優(yōu)化問題：mi%/(w)s.t.h^w)=0,電=L…，I,目標(biāo)函數(shù)是f(w)，下面是等式約束。通常解法是引入拉格朗日算子，這里使用來表示算子，得到拉格朗日公式為1=/(w)-￡月冼加)L是等式約束的個(gè)數(shù)。然后分別對(duì)w和求偏導(dǎo)，使得偏導(dǎo)數(shù)等于0，然后解出w和六。至于為什么引入拉格朗日算子可以求出極值，原因是f(w)的dw變化方向受其他不等式的約束，dw的變化方向與f(w)的梯度垂直時(shí)才能獲得極值，而且在極值處，f(w)的梯度與其他等式梯度的線性組合平行，因此他們之間存在線性關(guān)系。(參考《最優(yōu)化與KKT條件》)然后我們探討有不等式約束的極值問題求法，問題如下：mi%f(w)s.t.(w)<0,i—1,...,fc=0.2=1,.—,/,我們定義一般化的拉格朗日公式kI￡(wq目)=f(w)+￡o■攻(u，)+￡/Jihi(w').i=1i=l這里的Q和阡都是拉格朗日算子。如果按這個(gè)公式求解，會(huì)出現(xiàn)問題，因?yàn)槲覀兦蠼獾氖亲钚≈?，而這里的必"、‘已經(jīng)不是0了，我們可以將Q調(diào)整成很大的正值，來使最后的函數(shù)結(jié)果是負(fù)無窮。因此我們需要排除這種情況，我們定義下面的函數(shù)：Hp(ic)=maxC(w.a,/3).:Qi>0這里的P代表primal。假設(shè)或者'='-，那么我們總是可以調(diào)整心和「'?：來使得有最大值為正無窮。而只有g(shù)和h滿足約束時(shí)，「‘??雄以為f(w)。這個(gè)函數(shù)的精妙之處在于""，而且求極大值。因此我們可以寫作/(w)ifwsatisfiesprimalconstraintsocotherwise.這樣我們?cè)瓉硪蟮膍inf(w)可以轉(zhuǎn)換成求□二二了。minHp(ic)=minmaxC(w./?),我們使用'來表示二。如果直接求解，首先面對(duì)的是兩個(gè)參數(shù)，而，?:也是不等式約束，然后再在w上求最小值。這個(gè)過程不容易做，那么怎么辦呢？目)=血11￡(叫皿8).我們先考慮另外一個(gè)問題--D的意思是對(duì)偶，'項(xiàng)"將問題轉(zhuǎn)化為先求拉格朗日關(guān)于w的最小值，將和看%(%0)作是固定值。之后在-求最大值的話：maxff)=maxmin￡(w,a.3).a.,(3:Qj>0:ctj>0w這個(gè)問題是原問題的對(duì)偶問題，相對(duì)于原問題只是更換了min和max的順序，而一般更換順序的結(jié)果是MaxMin(X)<=MinMax(X)。然而在這里兩者相等。用…來表示對(duì)偶問題如下：d*—maxnii)ia./3)<minmax饑=p*,:ctj>0'—ii1口歸：cti>0下面解釋在什么條件下兩者會(huì)等價(jià)。假設(shè)f和g都是凸函數(shù)，h是仿射的(affine，11，-T1?：.：.*?：」-■■■：■■■：=■■■.'-：■：)。并且存在w使得對(duì)于所有的i，：：‘。在這種假設(shè)下，一定存在''"‘『使得如是原問題的解，?是對(duì)偶問題的解。還有：二::=另外;""”『滿足庫恩-塔克條件（Karush-Kuhn-Tucker,KKTcondition），該條件如下：二￡0儼）OWj=o,1…=0,4=1-=o,0=1…⑸佛伽*）<0,0=1…a>0,1=1^⑦所以如果"'戶'滿足了庫恩-塔克條件，那么他們就是原問題和對(duì)偶問題的解。讓我們?cè)俅螌徱暪剑?），這個(gè)條件稱作是KKTdualcomplementarity條件。這個(gè)條件隱含了如果n七那么,"「'■='。也就是說；'，'='時(shí)，w處于可行域的邊界上，這時(shí)才是起作用的約束。而其他位于可行域內(nèi)部（.”?"：」的）點(diǎn)都是不起作用的約束，其='。這個(gè)KKT雙重補(bǔ)足條件會(huì)用來解釋支持向量和SMO的收斂測(cè)試。這部分內(nèi)容思路比較凌亂，還需要先研究下《非線性規(guī)劃》中的約束極值問題，再回頭看看。KKT的總體思想是將極值會(huì)在可行域邊界上取得，也就是不等式為0或等式約束里取得，而最優(yōu)下降方向一般是這些等式的線性組合，其中每個(gè)元素要么是不等式為0的約束，要么是等式約束。對(duì)于在可行域邊界內(nèi)的點(diǎn)，對(duì)最優(yōu)解不起作用，因此前面的系數(shù)為0。最優(yōu)間隔分類器（optimalmarginclassifier）重新回到SVM的優(yōu)化問題：（w丁富⑴+6）>1,i=lm我們將約束條件改寫為：步愆）=—夕⑴（it，工⑴-F6）+1<0.從KKT條件得知只有函數(shù)間隔是1（離超平面最近的點(diǎn)）的線性約束式前面的系數(shù)=*。，也就是說這些約束式七對(duì)于其他的不在線上的點(diǎn)『技"：'），極值不會(huì)在他們所在的范圍內(nèi)取得，因此前面的系數(shù)N='.注意每一個(gè)約束式實(shí)際就是一個(gè)訓(xùn)練樣本。看下面的圖：實(shí)線是最大間隔超平面，假設(shè)X號(hào)的是正例，圓圈的是負(fù)例。在虛線上的點(diǎn)就是函數(shù)間隔是1的點(diǎn)，那么他們前面的系數(shù)"；"氣其他點(diǎn)都是='。這三個(gè)點(diǎn)稱作支持向量。構(gòu)造拉格朗日函數(shù)如下：1m=弓|壯『一￡皿⑴+b)—I.i=l注意到這里只有心沒有是因?yàn)樵瓎栴}中沒有等式約束，只有不等式約束。下面我們按照對(duì)偶問題的求解步驟來一步步進(jìn)行，(T=maxminct,/3)皿日：皿蘭。w首先求解Z''的最小值，對(duì)于固定的"?：，’'’’—的最小值只與w和b有關(guān)。對(duì)w和b分別求偏導(dǎo)數(shù)。m6.Q)=邸一口謂⑴技司=01=11=1并得到mW=皿舟W⑴.i=t將上式帶回到拉格朗日函數(shù)中得到，此時(shí)得到的是該函數(shù)的最小值（目標(biāo)函數(shù)是凸函數(shù)）代入后，化簡(jiǎn)過程如下：1以w,b,oc)=云||w||2-2ci][y①(w「必+b)-1]i=lTOC\o"1-5"\h\z1mmm=-wrw—￡aiy^wrx^—｝a(y^b+>%:=1i=li=：l1mmmm=^w「>—2佐尹板丁工①—aty^b+｝缶i=lz=li=li=lmmmm=§w「.時(shí)⑴；t?—的y?W—｝aty^b+>缶i=li=li=l1mmm=-5>%y｛。耕)—￡a^y^b+>恥Z=1t=lt=l1mmm=—-WT2ff.y(OxW—b>WiV⑥+2(Ie

i=li=li=l/m\Tmi=l=-!(Y叫并或))Y叫W")-b弋時(shí)①+￡㈤^i=l/t=li=li=lmmmm=-江")(x"))T｝叫y①;t“)一&>住")+>產(chǎn)i=li=li=li=l1mmm=-5>%y｛。耕)—￡a^y^b+>恥Z=1t=lt=l1mmm=—-WT2ff.y(OxW—b>WiV⑥+2(Ie

i=li=li=l/m\Tm最后得到TOC\o"1-5"\h\zmimm￡（叫*）=Qt--舟護(hù)）皿的（弒司）71那）一i=l\o"CurrentDocument"i=]ij=\i=l由于最后一項(xiàng)是0,因此簡(jiǎn)化為T71j771bq）=^2皿一弓V"W皿。JW）「工⑴\o"CurrentDocument"i=lij=1這里我們將向量?jī)?nèi)積表示為'此時(shí)的拉格朗日函數(shù)只包含了變量心。然而我們求出了”；才能得到w和b。（T=maxinin￡（w,a.B）接著是極大化的過程?二上：=冬匚"''-m十mmax^W(q)=皿—5$2小心W、i=1.ij=1s.t.ctj>07i—L...,mm/】mg—j1=1前面提到過對(duì)偶問題和原問題滿足的幾個(gè)條件，首先由于目標(biāo)函數(shù)和線性約束都是凸函數(shù)，而且這里不存在等式約束h。存在w使得對(duì)于所有的i，?，:"'*'氣因此，一定存在”使得如是原問題的解，淇是對(duì)偶問題的解。在這里，求E就是求疽了。w—』/'盤1如果求出了：【，根據(jù)"即可求出w（也是，原問題的解）。然后max^.y（0=_1-min^.y（0=iw*Tx{t}b=2即可求出b。即離超平面最近的正的函數(shù)間隔要等于離超平面最近的負(fù)的函數(shù)間隔。關(guān)于上面的對(duì)偶問題如何求解，將留給下一篇中的SMO算法來闡明。這里考慮另外一個(gè)問題，由于前面求解中得到mW=￡理少每掃日[=1我們通篇考慮問題的出發(fā)點(diǎn)是:?,根據(jù)求解得到的心，我們代入前式得到也就是說，以前新來的要分類的樣本首先根據(jù)w和b做一次線性運(yùn)算，然后看求的結(jié)果是大于0還是小于0,來判斷正例還是負(fù)例?，F(xiàn)