SVM學(xué)習(xí)的對偶算法.docx

《SVM學(xué)習(xí)的對偶算法.docx》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、SVM學(xué)習(xí)的對偶算法2013.3.23最近課上要求講一講關(guān)于SVM的內(nèi)容，我被分到了對偶算法這一塊，就順便把這部分知識整理了一下，并加上了一些個人的理解。至于SVM有多重要，曾經(jīng)的研究有多么熱這里就不再重提了。一、問題的引出SVM的目的非常直接：分類的間隔最大化。由此，得到了非常簡潔的最優(yōu)化模型（這里僅以線性可分SVM為例）：min1

2、

3、w

4、

5、22w,bs.t.yi(w×x+b)31,i=1,2,...,N在這個問題中，x和y是輸入的樣本點，都是已知的數(shù)據(jù)，并不是未知數(shù)。實際的自變量是w，目標(biāo)函數(shù)是w的二次函數(shù)，所有的約束條件都是關(guān)于w的線性函數(shù)，這

6、種規(guī)劃問題叫做二次規(guī)劃（QuadraticProgramming，QP），而且由于它的可行域是一個凸集，因此它是一個凸二次規(guī)劃。對于一個規(guī)劃問題，我們最喜歡問的問題就是：“是不是有解？如果有解，是否能找到？”而這樣的問題一般很難回答。但是，對于凸二次規(guī)劃問題，可以證明，總是有唯一的最優(yōu)解，即全局最優(yōu)解。然而，有解不等于容易求出來。在這個問題中，雖然目標(biāo)函數(shù)是極其簡單的二次函數(shù)，但是約束條件并不簡單，特別是將N個線性約束條件加上去之后可行域邊界極其復(fù)雜，直接求解幾乎是不可能的。那么，我們該如何處理呢？帶約束的優(yōu)化問題，我們一般的求解策略就是將其轉(zhuǎn)化為無

7、約束優(yōu)化問題，這讓我們很容易想到Lagrange乘子法：L(w,b,a)=1

8、

9、w

10、

11、2+?Nai[yi(w×xi+b)-1]2i=1令L對其3個參數(shù)的偏導(dǎo)數(shù)值分別等于0，得到的解便是最優(yōu)解。問題似乎輕而易舉地解決了。但是仔細(xì)想想，Lagrange乘子法中要求約束條件是等式，而這里是不等式，所以這種解法并不正確。雖然這么做不正確，但是多少也給了我們一點啟發(fā)，至少這種轉(zhuǎn)化的方向應(yīng)該是對的。所以，就有人提出了利用Lagrange對偶性進(jìn)行求解的算法。二、Lagrange對偶性為了便于更好地描述Lagrange對偶性的原理，我們先把上面的問題放在一邊，看一

12、個最典型的凸優(yōu)化模型：minf(x)x?Rns.t.gi(x)￡0,i=1,2,...,khj(x)=0,j=1,2,...,l這里我們對這個模型做一些限制：1）f(x)和gi(x)，i=1,2,...,k均為凸函數(shù)；2）hj(x),j=1,2,...,l均為仿射函數(shù)，即有Ax+b的形式。第一個限制不難理解，但是為什么要求hj(x)是仿射函數(shù)呢？事實上，為了統(tǒng)一凸優(yōu)化問題的形式，我們可以這樣表述約束條件：gi(x)￡0,i=1,2,...,khj(x)￡0,j=1,2,...,l-hj(x)￡0,j=1,2,...,l即全部的約束條件都能寫成小于等于

13、0的形式。同時，還要求它們?nèi)渴峭购瘮?shù)。這樣一來，hj(x)和-hj(x)都是凸函數(shù)，那只能取直線（直線也是一種比較特殊的凸函數(shù)）了，高維空間的直線，其表示形式就是仿射函數(shù)。明確了模型的要求之后，我們可以仿照之前的Lagrange乘子法也寫出這樣的形式klL(x,a,b)=f(x)+?aigi(x)+?bjhj(x),ai30,i=1,2,...,ki=1j=1這里的ai和bj都是拉格朗日乘子。如果我們對這個L求最小值，馬上就會發(fā)現(xiàn)，在可行域內(nèi)，hj(x)=0,j=1,2,...,l，第三項等于零，不會對結(jié)果產(chǎn)生影響，而gi(x)￡0,i=1,2,.

14、..,k和ai30,i=1,2,...,k決定了第二項不會是正數(shù)，要想取得L的最小值，我們令某個gi(x)<0對應(yīng)的ai取正無窮，那么顯然L就會取到負(fù)無窮，可是在求最小值的時候得到了負(fù)無窮，毫無意義。這就提醒我們，這里的ai和bj并不是完全隨意取的，至少要保證在對L取最小值k時與f(x)的最小值是相等的。為了達(dá)到這一點，只能讓?aigi(x)這個非正數(shù)不要產(chǎn)生影i=1響，即讓它等于零，也就是取到它的最大值（這時候每一對gi(x)與ai至少有一個為零）。所以，我們定義qP(x)=maxL(x,a,b)a,b;ai30其中P表示原問題。顯然在可行域內(nèi)qP

15、(x)=f(x)或者寫作qPìf(x)如果x滿足原問題的約束(x)=í?￥else條件else表示，如果出現(xiàn)gi(x)>0或者h(yuǎn)j(x)10的情況，只需令對應(yīng)的乘子取無窮大，qP(x)就可以取到無窮大，以此來表明超出了可行域范圍。既然有上面的關(guān)系，那么自然就有minf(x)=minqP(x)=minmaxL(x,a,b)xxxa,b;ai30這個問題稱為廣義Lagrange函數(shù)的極小極大問題。記p*=minqP(x)x為原始問題的最優(yōu)值毫無疑問，此時的最優(yōu)解與原始問題的解相同，但是：1、這個“新”的問題僅僅是原始問題在形式上的一個重寫，本質(zhì)上并沒有轉(zhuǎn)

16、換成新的問題，仍是原始問題；2、正因如此，這個形式上的新問題，并沒有給問題的求解帶來更大的便利，而且Lagr