SVM學(xué)習(xí)的對(duì)偶算法

1、SVM 學(xué)習(xí)的對(duì)偶算法2013.3.23最近課上要求講一講關(guān)于 SVM 的內(nèi)容，我被分到了對(duì)偶算法這一塊，就順便把這部分知識(shí)整理了一下，并加上了一些個(gè)人的理解。至于 SVM 有多重要，曾經(jīng)的研究有多么熱這里就不再重提了。一、 問(wèn)題的引出SVM 的目的非常直接：分類的間隔最大化。由此，得到了非常簡(jiǎn)潔的最優(yōu)化模型（這里僅以線性可分 SVM 為例）：min1| w |22w , bs.t .yi ( w x + b ) 1, i =1, 2,., N在這個(gè)問(wèn)題中，x 和 y 是輸入的樣本點(diǎn)，都是已知的數(shù)據(jù)，并不是未知數(shù)。實(shí)際的自變量是w，目標(biāo)函數(shù)是 w 的二次函數(shù)，所有的約束條件都是關(guān)于 w 的線性

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

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

4、minf ( x)xRns.t .g i ( x ) 0,i =1, 2,., kh j ( x ) = 0,j =1, 2,., l這里我們對(duì)這個(gè)模型做一些限制：1） f ( x )和g i ( x )，i =1, 2,., k均為凸函數(shù) ；2） h j ( x ), j =1, 2,., l 均為仿射函數(shù)，即有 Ax +b 的形式。第一個(gè)限制不難理解，但是為什么要求 h j ( x) 是仿射函數(shù)呢？事實(shí)上，為了統(tǒng)一凸優(yōu)化問(wèn)題的形式，我們可以這樣表述約束條件：g i ( x ) 0,i =1, 2,., kh j ( x ) 0,j =1, 2,., l- h j ( x ) 0,j =1,

5、 2,., l即全部的約束條件都能寫成小于等于 0 的形式。同時(shí)，還要求它們?nèi)渴峭购瘮?shù)。這樣一來(lái)， h j ( x )和-h j ( x) 都是凸函數(shù)，那只能取直線（直線也是一種比較特殊的凸函數(shù)）了，高維空間的直線，其表示形式就是仿射函數(shù)。明確了模型的要求之后，我們可以仿照之前的 Lagrange 乘子法也寫出這樣的形式klL ( x, a , b ) = f ( x ) + a i g i ( x ) + b j h j ( x ),ai 0, i =1, 2,., ki =1j =1這里的a i 和b j 都是拉格朗日乘子。如果我們對(duì)這個(gè) L 求最小值，馬上就會(huì)發(fā)現(xiàn)，在可行域內(nèi)，h j

6、( x ) = 0, j =1, 2,., l ，第三項(xiàng)等于零，不會(huì)對(duì)結(jié)果產(chǎn)生影響，而 g i ( x ) 0, i =1, 2,., k 和ai 0, i =1, 2,., k 決定了第二項(xiàng)不會(huì)是正數(shù)，要想取得 L 的最小值，我們令某個(gè) g i ( x) 0或者h(yuǎn) j ( x) 0 的情況，只需令對(duì)應(yīng)的乘子取無(wú)窮大，qP ( x) 就可以取到無(wú)窮大，以此來(lái)表明超出了可行域范圍。既然有上面的關(guān)系，那么自然就有min f ( x ) = min q P ( x) = min max L( x, a , b)xxxa , b ;ai 0這個(gè)問(wèn)題稱為廣義 Lagrange 函數(shù)的極小極大問(wèn)題。記p

7、* = min qP ( x)x為原始問(wèn)題的最優(yōu)值毫無(wú)疑問(wèn)，此時(shí)的最優(yōu)解與原始問(wèn)題的解相同，但是：1、這個(gè)“新”的問(wèn)題僅僅是原始問(wèn)題在形式上的一個(gè)重寫，本質(zhì)上并沒(méi)有轉(zhuǎn)換成新的問(wèn)題，仍是原始問(wèn)題；2、正因如此，這個(gè)形式上的新問(wèn)題，并沒(méi)有給問(wèn)題的求解帶來(lái)更大的便利，而且 Lagrange 乘子有兩組，其中關(guān)于的約束仍為不等式，特別是，復(fù)雜度沒(méi)有降低不說(shuō)，一旦試著求解一下就會(huì)發(fā)現(xiàn)，求完極大值之后又回到原來(lái)的問(wèn)題了，徒勞一場(chǎng)。極小極大問(wèn)題給了我們一個(gè)提示，可否嘗試著換成極大極小的形式，而且能得到相同的解？下面，我們就來(lái)看一下這種思路是否可行。定義q D (a , b ) = min L ( x, a

8、, b )x其中 D 表示對(duì)偶問(wèn)題。再對(duì)結(jié)果關(guān)于，求極大值，得到max q D (a , b ) = max min L ( x, a , b )a , ba , bxs.t .ai 0 , i =1, 2,., k這個(gè)問(wèn)題叫做廣義 Lagrange 函數(shù)的極大極小問(wèn)題，這里我們稱它為原始問(wèn)題的對(duì)偶問(wèn)題，記d * = min qD ( x)x為對(duì)偶問(wèn)題的最優(yōu)值?，F(xiàn)在，我們將問(wèn)題轉(zhuǎn)化成先將a i 和b j 看作固定值，關(guān)于 x 求無(wú)約束的極小值，然后再對(duì)a i 和b j 求極大值?？梢钥闯?，此時(shí)問(wèn)題的約束條件變得簡(jiǎn)單了，極有可能更容易求解一些，所以我們可能更愿意處理這樣的問(wèn)題?，F(xiàn)在急需明確的是，

9、原始問(wèn)題與對(duì)偶問(wèn)題是否完全等價(jià)呢？形式上，它們只是交換了求極大和極小的順序，那么本質(zhì)上是否如此呢？很遺憾，答案是否定的，這是因?yàn)長(zhǎng) ( x , a , b ) min L ( x, a , b ) = qD ( x)xL ( x , a , b ) maxL ( x, a , b ) = qP ( x)a , b ;ai 0所以q D ( x ) qP ( x)繼而d * = max qD( x ) min qP( x) = p*a , b ;ai 0x即它們的最優(yōu)解存在著不等關(guān)系，而不是我們期望的相等關(guān)系。但是，細(xì)心的朋友可能就會(huì)發(fā)現(xiàn)，兩個(gè)解是有可能取到等號(hào)的，我們?nèi)绻苷页鋈〉葪l件，那么，

10、當(dāng)滿足這個(gè)條件時(shí)，相等關(guān)系恒成立，那么不就是我們最想要的結(jié)果嗎？那么，我們就來(lái)看看是否存在這樣的取等條件。假設(shè) ( x* , a * , b* ) 是對(duì)偶問(wèn)題的最優(yōu)解，那么d * = q D (a * , b * ) = min L ( x, a * , b * )x= min f ( x ) + a i* g i ( x ) + b *j h j ( x)x i =1j =1kl顯然klklmin f ( x ) + a i* g i ( x ) + b *j h j ( x ) f ( x ) + a i* g i ( x ) + b*j h j ( x)xi=1j =1i =1j =1當(dāng)

11、 x*是最優(yōu)解時(shí)，上式得等號(hào)成立klklmin f ( x ) + a i* g i ( x ) + b *j h j ( x ) = f ( x * ) + a i* g i ( x * ) + b*j h j ( x* )xi =1j=1i =1j =1與原始問(wèn)題的最優(yōu)解 p* = f ( x* ) 相比，差了后面kl a i* g i ( x * ) + b*j h j ( x* )i =1j =1這兩項(xiàng)。由于最優(yōu)解 x*肯定在可行域內(nèi)，h j ( x* ) = 0, j =1, 2,., l ，所以關(guān)于 b * 的那一個(gè)求和項(xiàng)全部為零，現(xiàn)在，只差關(guān)于a* 這個(gè)求和項(xiàng)了，我們只要能讓它等

12、于零，那么就有f ( x * ) + a i* g i ( x * ) + b*j h j ( x * ) = f ( x* )kli =1j =1這樣就得到了我們想要的 d * = p* 了！所以，上面提到的我們最想看到的取等條件就是kai* g i ( x* ) = 0i=1而求和項(xiàng)中每一項(xiàng)都是非正數(shù)，求和結(jié)果為零，那么只能是ai* g i ( x* ) = 0，i =1, 2,., k這就是著名的互補(bǔ)對(duì)偶條件。有了它，我們就可以放心地去求解對(duì)偶問(wèn)題了。在開始求解之前，可能有人會(huì)有疑問(wèn)，這個(gè)互補(bǔ)對(duì)偶條件的意義是什么？我們可以換種寫法a i* 0, g i ( x* ) = 0g i ( x

13、 * ) 0 時(shí)，必須有 g i ( x* ) = 0 ；當(dāng) g i ( x* ) 0 的樣本點(diǎn)，分離超平面只是這樣的點(diǎn)支持的，故稱這樣的樣本點(diǎn)為支持向量。換個(gè)角度來(lái)看，根據(jù) KKT 條件，ai yi ( w xi + b) - 1 = 0，i=1,2,.,N對(duì)于ai* 0的樣本點(diǎn)，一定有yi ( w* xi + b* ) -1=0即w* xi + b* = 1由此可知，這樣的樣本點(diǎn)都在間隔邊界上，同樣說(shuō)明訓(xùn)練數(shù)據(jù)中ai 0 的樣本點(diǎn)是支持向量。至此，可以總結(jié)出利用對(duì)偶問(wèn)題求解一般流程：1、構(gòu)造優(yōu)化問(wèn)題的對(duì)偶形式；2、求解對(duì)偶問(wèn)題（具體求解用到了 SMO 算法）；3、計(jì)算 w；4、選擇不為零的

14、a j 對(duì)應(yīng)的 j 計(jì)算 b；5、得到分離超平面和分類決策函數(shù)；這樣，我們就完美地解決了線性可分 SVM 的求解問(wèn)題。四、軟間隔 SVM 的對(duì)偶問(wèn)題從原始問(wèn)題到對(duì)偶問(wèn)題的轉(zhuǎn)化與前面的處理基本一致，得到對(duì)偶問(wèn)題N1NNmaxa a i-a ia j yi y j ( xi x j )i =12 i =1j =1Ns.t .ai yi = 0i=10 ai C ,i = 1, 2,., N其中,由于mi 與C和ai線性相關(guān)，可以消去。直接給出該問(wèn)題的 KKT 條件： w L ( w* , b* , x * , a * , m * ) = w* - ai* yi xi = 0i=1NN b L (

15、w* , b* , x * , a * , m * ) = ai* yi = 0i=1 x L ( w* , b* , x * , a * , m * ) = C - a * - m* = 0yi ( w* xi + b* ) - 1 + xi* 0，i=1,2,.,Nxi* 0，i=1,2,.,Na i* yi ( w* xi + b* ) - 1 = 0，i=1,2,.,N mi*xi* =0，i=1,2,.,N (互補(bǔ)對(duì)偶條件)最終求解出的參數(shù)與線性可分 SVM 的對(duì)偶問(wèn)題完全相同（這樣說(shuō)不完全準(zhǔn)確，因此此時(shí)的b*取值不唯一，需要采取特定的措施確定），可以參照第三部分，此處不予列出。根據(jù) KKT 條件可以得出軟間隔的支持向量的分布情況五、利用對(duì)偶問(wèn)題進(jìn)行求解的優(yōu)點(diǎn)經(jīng)過(guò)上面的證明和推導(dǎo)，我們發(fā)現(xiàn)利用對(duì)偶問(wèn)題對(duì) SVM 問(wèn)題進(jìn)行求解有很多優(yōu)點(diǎn)，主要幾點(diǎn)如下;1、原始問(wèn)題中復(fù)雜的約束條件在對(duì)偶問(wèn)題中變得簡(jiǎn)單，并且仍是凸優(yōu)化問(wèn)題從下面的關(guān)系圖可以看出，線性可分 SVM 和軟間隔 SVM 在變成對(duì)偶問(wèn)題之后約束條件都變簡(jiǎn)單了，特別是，在原始問(wèn)題形式下，軟間隔問(wèn)題要復(fù)雜很多，但是在對(duì)偶問(wèn)題形