支持向量機原理詳解(四): KKT條件(Part I)

本文內容：

KKT條件
SVM原問題的KKT條件
，支持向量
對偶問題中最優解的計算

對於有等式約束的優化問題，可以由拉格朗日乘子法得到極值點。那麼對於有不等式約束的優化問題，最優解應該滿足什麼樣的條件呢？

這就是本文要介紹的KKT條件，也是後續要介紹的序列最小最優化(sequential minimal optimization, SMO)演算法的前提。

關於SVM形成的優化問題和對偶問題等，可參考前文：

支持向量機原理詳解(一): 間隔最大化，支持向量

支持向量機原理詳解(二): 拉格朗日對偶函數，SVM的對偶問題

支持向量機原理詳解(三): 核函數與非線性SVM

<對前文的補充>

前文提到，當原問題為凸優化問題且滿足一定的約束準則時，強對偶性成立。Convex Optimization一書的5.3.2節給出了證明過程。

此外，Convex Optimization的5.4節還從多個角度給出了拉格朗日對偶的解釋，其中，5.4.1節的極大極小描述(max-min characterization)也是李航的《統計學習方法》附錄C所採用的描述。

7. KKT條件(Karush–Kuhn–Tucker conditions, KKT conditions)

在優化問題中，KKT條件非常重要。現參考Convex Optimization的5.5.2和5.5.3節來介紹KKT條件。

記標準優化問題(原問題)：

$egin{align} min_{mathbf x} f_0left(mathbf x ight) \ s.t. f_ileft( mathbf x ight) &leq 0, i=1, ldots, m ag{1-1}\ h_ileft( mathbf x ight) &= 0, i=1, ldots, p ag{1-2}\ end{align}\ ag{I}$

假設目標函數和約束函數都是可微(differentiable)的(定義域為開集，這一點很重要)。(暫不假設原問題 為凸優化問題。)

拉格朗日函數：

$Lleft( mathbf x, mathbf lambda, mathbf u ight)=f_0left( mathbf x ight)+sum_{i=1}^{m}{lambda_i f_ileft( mathbf x ight)}+sum_{i=1}^{p}{ u_i h_ileft( mathbf x ight)}$

其中，分別為不等式約束和等式約束的拉格朗日乘子；相應地，向量和稱為問題的對偶變數或拉格朗日乘子向量。

拉格朗日對偶函數：

$gleft(mathbf lambda, mathbf u ight)=inf_{mathbf xin mathcal D}{Lleft( mathbf x, mathbf lambda, mathbf u ight)}$

對偶問題：

$max_{mathbf lambda, mathbf u}{gleft(mathbf lambda, mathbf u ight)}\ ag{II} s.t. mathbf lambdasucceq mathbf 0$

記和分別是原問題和對偶問題的一對最優解；假設強對偶性成立(原對偶問題有相同的最優值)，則有如下一組重要的結論：

$egin{align} f_ileft( mathbf x^star ight) &leq 0, i=1, ldots, m ag{2-1}\ h_ileft( mathbf x^star ight) &= 0, i=1, ldots, p ag{2-2}\ lambda_i^star &geq 0, i=1, ldots, m ag{2-3}\ lambda_i^star f_ileft( mathbf x^star ight)&= 0, i=1, ldots, m ag{2-4}\ abla f_0left( mathbf x^star ight) + sum_{i=1}^{m}{lambda_i^star abla f_ileft( mathbf x^star ight)} + sum_{i=1}^{p}{ u_i^star abla h_ileft( mathbf x^star ight)} &= mathbf 0 ag{2-5}\ end{align}$

(2-1)~(2-5)式稱為KKT條件(Karush–Kuhn–Tucker conditions, KKT conditions)。

下面對這5個條件逐個進行解釋。

首先，式(2-1)和(2-2)分別是原問題的不等式約束和等式約束，最優解當然應該滿足；

式(2-3)是對偶問題的不等式約束，稱為對偶可行。(當時，，對偶函數才能給出原問題最優值的下界。)

式(2-4)稱為互補鬆弛性(complementary slackness)，其推導過程如下：

$egin{align} f_0left( mathbf x^star ight) &= gleft( mathbf lambda^star, u^star ight) ag{3-1}\ &= min_{mathbf xin mathcal D}{left(f_0left( mathbf x ight) + sum_{i=1}^{m}{lambda_i^star f_ileft( mathbf x ight)} + sum_{i=1}^{p}{ u_i^star h_ileft( mathbf x ight)} ight)} ag{3-2} \ &leq f_0left( mathbf x^star ight) + sum_{i=1}^{m}{lambda_i^star f_ileft( mathbf x^star ight)} + sum_{i=1}^{p}{ u_i^star h_ileft( mathbf x^star ight)} ag{3-3}\ &leq f_0left( mathbf x^star ight) ag{3-4}\ end{align}$

其中，

(3-1)：因為強對偶性成立，對偶間隙為0；
(3-2)：拉格朗日對偶函數在處的取值；拉格朗日對偶函數為拉格朗日函數對取最小值(嚴格來說是下確界 )；
(3-3)：因為函數的最小值當然不會超過其定義域內任意一點的函數值，所以也就不超過處的函數值；
(3-4)：因為有(2-1)和(2-2)成立，所以(3-3)式的後面兩個求和項都不會超過0，也就有(3-4)成立。

顯然，因為，所以(3-3)和(3-4)中的兩個不等號都應該取等號，由此可以得到以下兩個重要的結論：

其一，由(3-3)=(3-4)，即

$f_0left( mathbf x^star ight) + sum_{i=1}^{m}{lambda_i^star f_ileft( mathbf x^star ight)} + sum_{i=1}^{p}{ u_i^star h_ileft( mathbf x^star ight)} = f_0left( mathbf x^star ight)$

因為，所以有

$sum_{i=1}^{m}{lambda_i^star f_ileft( mathbf x^star ight)} = 0\ ag{4}$

又因為，，所以，即(4)中求和的每一項都小於等於0，所以每一項都應該等於0，即有

也就是互補鬆弛性(2-4)。這意味著，如果，則；如果，則。

其二，由(2-3)=(2-4)，即

$min_{mathbf x}{left(f_0left( mathbf x ight) + sum_{i=1}^{m}{lambda_i^star f_ileft( mathbf x ight)} + sum_{i=1}^{p}{ u_i^star h_ileft( mathbf x ight)} ight)} = f_0left( mathbf x^star ight) + sum_{i=1}^{m}{lambda_i^star f_ileft( mathbf x^star ight)} + sum_{i=1}^{p}{ u_i^star h_ileft( mathbf x^star ight)}$

說明是的最小值點。因此，在處的梯度必須為 (定義域為開集)，也就得到(2-5)式：

$abla f_0left( mathbf x^star ight) + sum_{i=1}^{m}{lambda_i^star abla f_ileft( mathbf x^star ight)} + sum_{i=1}^{p}{ u_i^star abla h_ileft( mathbf x^star ight)} = mathbf 0$

至此，(2-1)~(2-5)式的由來已解釋。

對目標函數和約束函數可微，且強對偶性成立的優化問題(無論原問題是否是凸優化問題)，KKT條件是最優解的必要條件，即原對偶問題的任意一對最優解都必須滿足KKT條件。

<凸優化問題的KKT條件>

凸優化問題指問題中目標函數和不等式約束函數為凸函數，等式約束函數為仿射函數。

若原問題為凸優化問題，且目標函數和約束函數可微，則滿足KKT條件的點也是原對偶最優解；也就是說，此時KKT條件不僅是必要條件，同時也是最優解的充分條件。

即，若和滿足KKT條件：

$egin{align} f_ileft(mathbf { ilde x} ight) &leq 0, i=1, ldots, m ag{5-1}\ h_ileft(mathbf { ilde x} ight) &= 0, i=1, ldots, p ag{5-2}\ ilde lambda_i &geq 0, i=1, ldots, m ag{5-3}\ ilde lambda_i f_ileft(mathbf { ilde x} ight)&= 0, i=1, ldots, m ag{5-4}\ abla f_0left(mathbf { ilde x} ight) + sum_{i=1}^{m}{ ilde lambda_i abla f_ileft(mathbf { ilde x} ight)} + sum_{i=1}^{p}{ ilde u_i abla h_ileft(mathbf { ilde x} ight)} &= mathbf 0 ag{5-5}\ end{align}$

則和分別是原問題和對偶問題的一對最優解，對偶間隙為0。

必要性前面已證，下面來看充分性。

(5-1)和(5-2)分別為原問題的不等式約束和等式約束，保證解可行；
(5-3)為對偶可行條件；因為目標函數和不等式約束為凸函數，而等式約束為仿射函數(既凸又凹)，所以拉格朗日函數可看作一組凸函數的非負加權和，因此也是凸函數；
(5-4)為互補鬆弛條件；
(5-5)為梯度為零的條件：在處的梯度為；因為是可微凸函數，所以是其最小值點(Convex Optimization 4.2.3節)。

所以有

$egin{align} gleft( mathbf { ilde lambda}, mathbf { ilde u} ight) &= Lleft( mathbf { ilde x}, mathbf { ilde lambda}, mathbf { ilde u} ight) ag{6-1}\ &=f_0left( mathbf { ilde x} ight) + sum_{i=1}^{m}{ ilde lambda_i f_ileft(mathbf { ilde x} ight)} + sum_{i=1}^{p}{ ilde u_i h_ileft( mathbf { ilde x} ight)} ag{6-2}\ &= f_0left(mathbf { ilde x} ight) ag{6-3}\ end{align}$

其中，

式(6-1)是拉格朗日對偶函數在處的取值；
式(6-2)是拉格朗日函數的定義；
式(6-3)是因為互補鬆弛條件和等式約束。

(6-1)~(6-3)式說明對偶間隙為0，所以和分別是原對偶問題的一對最優解。

<另一種表述>

若原問題為凸優化問題，目標函數和約束函數可微，且滿足Slaters condition，則KKT條件是最優性的充要條件。

[註：結論和之前的結論在表述上有點區別，可能是因為這裡假設事先不知道有點滿足KKT條件，所以需要Slaters condition來保證最優解可以達到。]

8. SVM原問題的KKT條件

在介紹完KKT條件後，讓我們先從原問題的角度來看SVM的KKT條件。

線性SVM形成的優化問題(原問題)為：

$egin{align} min_{mathbf w, b, mathbf xi}{frac{1}{2}mathbf{w^Tw}}+Csum_{i=1}^{N}{xi_i}\ s. t. y_i left( mathbf{w^Tx_i}+b ight)-1+xi_igeq 0, i=1,ldots, N ag{7-1}\ xi_igeq 0, i=1,ldots, N ag{7-2}\ end{align}\ ag{III}$

其中，優化變數為。只有不等式約束，沒有等式約束。

原問題是凸優化問題(凸二次規劃)，所以KKT條件是最優解的充要條件。

拉格朗日函數為：

$Lleft( mathbf w,b, mathbf xi, mathbf alpha, mathbf mu ight)={frac{1}{2}mathbf{w^Tw}}+Csum_{i=1}^{N}{xi_i}-sum_{i=1}^{N}{alpha_i left[ y_i left( mathbf{w^Tx_i}+b ight)-1+xi_i ight]}-sum_{i=1}^{N}{mu_i xi_i}$

由(2-1)~(2-5)式，列出問題的KKT條件為：

$egin{align} y_i left( mathbf{w^Tx_i}+b ight)-1+xi_i &geq 0, i=1,ldots, N ag{8-1}\ xi_i &geq 0, i=1,ldots, N ag{8-2}\ alpha_i &geq 0, i=1,ldots, N ag{8-3}\ mu_i &geq 0, i=1,ldots, N ag{8-4}\ alpha_i left[ y_i left( mathbf{w^Tx_i}+b ight)-1+xi_i ight]&=0, i=1,ldots, N ag{8-5}\ mu_i xi_i &= 0, i=1,ldots, N ag{8-6}\ frac{partial L}{partialmathbf w} =mathbf{w}-sum_{i=1}^{N}{alpha_i y_i mathbf{x_i}} &=mathbf 0 ag{8-7}\ frac{partial L}{partialmathbf xi} = Ccdot mathbf 1 - mathbf alpha - mathbf mu &= mathbf 0 ag{8-8}\ frac{partial L}{partial b} =sum_{i=1}^{N}{alpha_i y_i}=mathbf {alpha^T y} &= 0 ag{8-9}\ end{align}$

式(8-1)~(8-9)是問題的最優解的充要條件。為簡化表示，這裡最優解未加星號。

其中，

(8-1)和(8-2)分別為原問題的不等式約束(7-1)和(7-2)；
(8-3)和(8-4)為對偶可行條件；
(8-5)和(8-6)為互補鬆弛條件；
(8-7), (8-8)和(8-9)為梯度為零的條件。

<關於，支持向量>

前文講到，線性SVM的決策函數為：

$y_{new} = signleft(sum_{support \ vectors}{alpha_i^star y_i mathbf{x_i^T x_{new}}} +b^star ight)$

SVM訓練完成後，只需保留的樣本(所謂的支持向量)的特徵和標籤，即可用於新數據的分類。現在，我們從SVM的KKT條件來看看不同的取值分別對應哪些樣本，哪些向量是支持向量。

假設解優化問題得到原對偶問題的最優解分別為和，為了方便，以下省掉星號，簡記為和，則最優解滿足KKT條件(8-1)~(8-9)式。當取值不同時，和 $y_i left( mathbf{w^Tx_i}+b ight)$ 的取值也不同，具體可分為以下三種情況來討論：

(1)若，則

$egin{align} alpha_i = 0\ (8-5)&Rightarrow y_i left( mathbf{w^Tx_i}+b ight)-1+xi_i geq 0 \ (8-8)&Rightarrow mu_i=C-alpha_i =C eq0 \ (8-6) &Rightarrow xi_i=0\ (8-5)&Rightarrow y_i left( mathbf{w^Tx_i}+b ight) geq 1 \ end{align}\ ag{9}$

說明樣本 $left( mathbf{x_i}, y_i ight)$ 到分離超平面的函數間隔不小於1。

(2)若，則

$egin{align} 0lt alpha_ilt C\ (8-5)&Rightarrow y_i left( mathbf{w^Tx_i}+b ight)-1+xi_i= 0 \ (8-8)&Rightarrow mu_i=C-alpha_i eq0\ (8-6)&Rightarrow xi_i=0 \ (8-5)&Rightarrow y_i left( mathbf{w^Tx_i}+b ight)= 1\ end{align}\ ag{10}$

說明樣本 $left( mathbf{x_i}, y_i ight)$ 到分離超平面的函數間隔等於1，樣本位於間隔邊界上。

(2)若，則

$egin{align} alpha_i = C\ (8-5)&Rightarrow y_i left( mathbf{w^Tx_i}+b ight)-1+xi_i= 0 \ (8-8)&Rightarrow mu_i=C-alpha_i=0 \ (8-6)&Rightarrow xi_igeq 0 \ (8-5)&Rightarrow y_i left( mathbf{w^Tx_i}+b ight)=1-xi_ileq 1\ end{align}\ ag{11}$

說明樣本 $left( mathbf{x_i}, y_i ight)$ 到分離超平面的函數間隔不超過1。當的取值不同時，樣本的函數間隔 $y_i left( mathbf{w^Tx_i}+b ight)$ 的取值也不同，具體地：

當時， $y_i left( mathbf{w^Tx_i}+b ight)=1$ ，對應間隔邊界上的樣本；
當時， $0 lt y_i left( mathbf{w^Tx_i}+b ight) lt 1$ ，對應和分離超平面函數間隔小於1的樣本；
當時， $y_i left( mathbf{w^Tx_i}+b ight) = 0$ ，對應位於分離超平面上的樣本；
當時， $y_i left( mathbf{w^Tx_i}+b ight) < 0$ ，對應被誤分類的樣本。

注意到式中各步其實倒過來推也成立，所以實際上是充要條件(此處類似於文獻[6], page 5關於對偶問題的相應結論)：

$egin{align} alpha_i = 0 &Leftrightarrow y_i left( mathbf{w^Tx_i}+b ight) geq 1\ 0lt alpha_ilt C &Leftrightarrow y_i left( mathbf{w^Tx_i}+b ight) = 1\ alpha_i =C &Leftrightarrow y_i left( mathbf{w^Tx_i}+b ight) leq 1\ end{align}$

支持向量即和的樣本。相對於整個數據集而言，支持向量往往只佔一小部分。

<對偶問題中最優解的計算>

記原對偶問題的最優解分別為和，則通過對偶問題解SVM，得到分離超平面的法向量的最優解為[見KKT條件(8-7)]：

$mathbf{w^star}=sum_{support \ vectors}{alpha_i^star y_i mathbf{x_i}} ag{12}$

選擇所有的樣本(支持向量)，可由(12)式計算 $mathbf{w^star}$ 。但是關於的計算我們還沒有討論過。現在在KKT條件的基礎上，來看看對偶問題中的計算。

由前面的推導可知，對於的樣本，有 $y_j left( mathbf{w^{star T} x_j}+b^star ight)-1= 0$ 成立。又因為，所以有

$egin{align} & y_j left( mathbf{w^{star T} x_j}+b^star ight)=1\ &Rightarrow mathbf{w^{star T} x_j}+b^star=y_j \ &Rightarrow b^star = y_j - mathbf{w^{star T} x_j} \ &Rightarrow b^star = y_j - sum_{support \ vectors}{alpha_i^star y_i mathbf{x_i^T x_j}} ag{13}\ end{align}$

這告訴我們，任選一的樣本，即可由(13)式計算。在實際計算中，往往對所有的樣本計算，然後取平均值(參考文獻[3], page 136)。

(參考文獻[4], pages 109, 112：原問題對 $mathbf{w^star}$ 的解唯一，但對的解並不唯一，存在於一個區間，所以需要取平均值。關於原問題對的解可能不唯一，參考文獻[5] 5.3.1節, page 175開始，給出了證明。)

需要注意的是，優化問題 是基於線性SVM得到的；對於非線性SVM，需要在對偶問題中引入核函數。後續，我們將從SVM對偶問題的角度再來看KKT條件。

To be continued...

參考文獻

[1] Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004.

中文譯本：凸優化。 Stephen Boyd and Lieven Vandenberghe 著。王書寧，許鋆，黃曉霖譯。清華大學出版社，北京，2013年。

[2] C. Cortes and V. Vapnik. Support-Vector Networks. Machine Learning, 20:273–297, 1995.

[3] Christopher J. C. Burges. A Tutorial on Support Vector Machines for Pattern Recognition. Data Mining and Knowledge Discovery, 2, 121-167, 1998.

[4] 李航，統計學習方法，清華大學出版社，北京，2012年。第7章。

[5] 鄧乃揚，田英傑，數據挖掘中的新方法——支持向量機，科學出版社，北京，2004年。

[6] John C. Platt. Sequential minimal optimization: A fast algorithm for training support vector machines. Technical Report MSR-TR-98-14, Microsoft Research, 1998.