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

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

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

4、minf ( x)xRns.t .g i ( x ) 0,i =1, 2,., kh j ( x ) = 0,j =1, 2,., l這里我們對這個模型做一些限制：1） f ( x )和g i ( x )，i =1, 2,., k均為凸函數(shù) ；2） h j ( x ), j =1, 2,., l 均為仿射函數(shù)，即有 Ax +b 的形式。第一個限制不難理解，但是為什么要求 h j ( x) 是仿射函數(shù)呢？事實上，為了統(tǒng)一凸優(yōu)化問題的形式，我們可以這樣表述約束條件：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 的形式。同時，還要求它們?nèi)渴峭购瘮?shù)。這樣一來， 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 都是拉格朗日乘子。如果我們對這個 L 求最小值，馬上就會發(fā)現(xiàn)，在可行域內(nèi)，h j

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

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

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

9、原始問題與對偶問題是否完全等價呢？形式上，它們只是交換了求極大和極小的順序，那么本質(zhì)上是否如此呢？很遺憾，答案是否定的，這是因為L ( 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ì)心的朋友可能就會發(fā)現(xiàn)，兩個解是有可能取到等號的，我們?nèi)绻苷页鋈〉葪l件，那么，

10、當(dāng)滿足這個條件時，相等關(guān)系恒成立，那么不就是我們最想要的結(jié)果嗎？那么，我們就來看看是否存在這樣的取等條件。假設(shè) ( x* , a * , b* ) 是對偶問題的最優(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)解時，上式得等號成立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與原始問題的最優(yōu)解 p* = f ( x* ) 相比，差了后面kl a i* g i ( x * ) + b*j h j ( x* )i =1j =1這兩項。由于最優(yōu)解 x*肯定在可行域內(nèi)，h j ( x* ) = 0, j =1, 2,., l ，所以關(guān)于 b * 的那一個求和項全部為零，現(xiàn)在，只差關(guān)于a* 這個求和項了，我們只要能讓它等

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而求和項中每一項都是非正數(shù)，求和結(jié)果為零，那么只能是ai* g i ( x* ) = 0，i =1, 2,., k這就是著名的互補(bǔ)對偶條件。有了它，我們就可以放心地去求解對偶問題了。在開始求解之前，可能有人會有疑問，這個互補(bǔ)對偶條件的意義是什么？我們可以換種寫法a i* 0, g i ( x* ) = 0g i ( x

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

14、a j 對應(yīng)的 j 計算 b；5、得到分離超平面和分類決策函數(shù)；這樣，我們就完美地解決了線性可分 SVM 的求解問題。四、軟間隔 SVM 的對偶問題從原始問題到對偶問題的轉(zhuǎ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)，可以消去。直接給出該問題的 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ǔ)對偶條件)最終求解出的參數(shù)與線性可分 SVM 的對偶問題完全相同（這樣說不完全準(zhǔn)確，因此此時的b*取值不唯一，需要采取特定的措施確定），可以參照第三部分，此處不予列出。根據(jù) KKT 條件可以得出軟間隔的支持向量的分布情況五、利用對偶問題進(jìn)行求解的優(yōu)點(diǎn)經(jīng)過上面的證明和推導(dǎo)，我們發(fā)現(xiàn)利用對偶問題對 SVM 問題進(jìn)行求解有很多優(yōu)點(diǎn)，主要幾點(diǎn)如下;1、原始問題中復(fù)雜的約束條件在對偶問題中變得簡單，并且仍是凸優(yōu)化問題從下面的關(guān)系圖可以看出，線性可分 SVM 和軟間隔 SVM 在變成對偶問題之后約束條件都變簡單了，特別是，在原始問題形式下，軟間隔問題要復(fù)雜很多，但是在對偶問題形