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

本文內容：

SVM對偶問題的KKT條件
關於，SMO的停機條件

前文從原問題的角度推導了SVM的KKT條件：支持向量機原理詳解(四): KKT條件(Part I)。

本文將推導SVM對偶問題的KKT條件(也是SMO演算法的停機條件)。

9. SVM對偶問題的KKT條件

SVM的對偶問題為：

$egin{align} min_{mathbf alpha}{frac{1}{2}mathbf{alpha^T Q alpha} -mathbf{1^Talpha}}\ s.t. mathbf 0 preceq mathbf alpha preceq Ccdot mathbf 1 ag{1-1}\ mathbf {alpha^T y} = 0 ag{1-2}\ end{align} ag{I}$

其中，目標函數為二次函數，優化變數為維向量，為訓練集的樣本數；為階對稱矩陣，對於線性SVM，其行列的元素為 $mathbf {Q_{ij}} = y_i y_j mathbf{x_i^T} mathbf{x_j}$ ；對於非線性SVM， $mathbf {Q_{ij}} = y_i y_j kleft( mathbf{x_i}, mathbf{x_j} ight)$ ，為核函數。

問題中的目標函數是用矩陣和向量表示的，為了方便理解求梯度，將其展開寫成標量的和，其中

$egin{align} mathbf {alpha^T Q alpha} &= left[ sum_{i=1}^{N}{alpha_i mathbf{Q_{i1}}}, sum_{i=1}^{N}{alpha_i mathbf{Q_{i2}}}, ldots, sum_{i=1}^{N}{alpha_i mathbf{Q_{iN}}} ight] alpha\ &= sum_{i=1}^{N}{sum_{j=1}^{N}{alpha_i alpha_j mathbf{Q_{ij}}}}\ &= sum_{i=1}^{N}{sum_{j=1}^{N}{alpha_i alpha_j y_i y_j kleft( mathbf{x_i}, mathbf{x_j} ight)}}\ end{align}\ ag{2}$

所以問題又可寫成如下標準形式：

$egin{align} min_{mathbf alpha}{frac{1}{2}sum_{i=1}^{N}{sum_{j=1}^{N}{y_iy_jkleft( mathbf{x_i}, mathbf{x_j} ight)alpha_ialpha_j}} -sum_{j=1}^{N}{alpha_i}}\ s.t. -alpha_i leq 0, i=1,ldots,N ag{3-1}\ alpha_i - C leq 0, i=1,ldots,N ag{3-2}\ sum_{i=1}^{N}{y_i alpha_i} = 0 ag{3-3}\ end{align} ag{II}$

其中，不等式約束(3-1)和(3-2)即(1-1)，等式約束(3-3)即(1-2)。

<對偶問題為凸優化問題？>

這個問題看起來似乎有點多餘，但是我們不妨考慮一下。

問題是否是凸優化問題，關係到KKT條件是否是其最優解的充要條件。

結論是：當為正定核時，問題是凸優化問題([4], 第124頁)。

個人認為，可以從兩個角度來理解：

1. 無論原問題是否是凸優化問題，拉格朗日對偶函數都是凹函數，拉格朗日對偶問題都是凸優化問題(max一個凹函數)([1] Convex Optimization, page 223)。

需要注意的是，我們是直接在對偶問題中引入核函數，進而將SVM擴展到非線性可分數據集的。換句話說，我們直接將線性SVM的對偶問題中的向量點積替換為核函數，得到了對偶問題，而沒有從非線性SVM的原問題開始推導。

為確保對偶問題是合理的，現在我們考慮一下非線性SVM的原問題：

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

在問題中，將維輸入空間中的樣本 $mathbf {x_i}$ 映射為維特徵空間中的 $phileft( mathbf {x_i} ight)$ ，同時變為維向量，得到非線性SVM的原問題；如果 $kleft( mathbf{x_i}, mathbf{x_j} ight)=phi( mathbf{x_i})^T phi(mathbf{x_j})$ 是成立的( 是正定核)，那麼對偶問題不出意外應該是問題，所以作為對偶問題應該是凸優化問題。

2. 目標函數為二次函數，若為半正定矩陣(記做 )，則目標函數是凸函數；當正定時(記做 )，目標函數嚴格凸。([1] Convex Optimization, page 71。)

根據定義，要證明為半正定矩陣，需證明 $mathbf {alpha^T Q alpha} geq 0$ 對任意都成立。

，有

$egin{align} mathbf {alpha^T Q alpha} &= sum_{i=1}^{N}{sum_{j=1}^{N}{alpha_i alpha_j y_i y_j kleft( mathbf{x_i}, mathbf{x_j} ight)}}\ end{align}$

若定義一個新的向量，則

$egin{align} mathbf {alpha^T Q alpha} = sum_{i=1}^{N}{sum_{j=1}^{N}{(alpha_i y_i) (alpha_j y_j) kleft( mathbf{x_i}, mathbf{x_j} ight)}} =mathbf {z^T K z} end{align}$

上式類似於將(2)式倒過來推。其中，矩陣為核函數的Gram矩陣，其行列的元素 $mathbf{K_{ij}} = kleft( mathbf{x_i}, mathbf{x_j} ight)$ ；若為正定核，則半正定，也就是說

$mathbf {alpha^T Q alpha} =mathbf {z^T K z} geq 0$

所以當為正定核時，為半正定矩陣，目標函數為凸函數，又因為不等式約束函數均為仿射函數，所以對偶問題是凸二次規劃問題。

另一種證明方法：

若為正定核，則 $kleft( mathbf{x_i}, mathbf{x_j} ight)=phi( mathbf{x_i})^T phi(mathbf{x_j})$ ，所以

$egin{align} mathbf {alpha^T Q alpha} &= sum_{i=1}^{N}{sum_{j=1}^{N}{alpha_i alpha_j y_i y_j kleft( mathbf{x_i}, mathbf{x_j} ight)}}\ &= sum_{i=1}^{N}{sum_{j=1}^{N}{alpha_i alpha_j y_i y_j phi( mathbf{x_i})^T phi(mathbf{x_j})}}\ &= left[ sum_{i=1}^{N}{alpha_i y_i phi(mathbf{x_i})} ight]^T left[ sum_{j=1}^{N}{alpha_j y_j phi(mathbf{x_j})} ight]\ &= leftVert sum_{i=1}^{N}{alpha_i y_i phi(mathbf{x_i})} ightVert_2^2 geq 0 end{align}$

所以為半正定矩陣。

<對偶問題的KKT條件>

凸優化問題的目標函數(二次函數)和約束函數(仿射函數)可微，所以KKT條件是最優解的充要條件。(Slaters condition應該是滿足的，存在嚴格可行點。)

拉格朗日函數為：

$Lleft(mathbf alpha, mathbf lambda, mathbf mu, u ight)=frac{1}{2}sum_{i=1}^{N}{sum_{j=1}^{N}{y_iy_jkleft( mathbf{x_i}, mathbf{x_j} ight)alpha_ialpha_j}} -sum_{j=1}^{N}{alpha_i}-sum_{i=1}^{N}{lambda_i alpha_i}+sum_{i=1}^{N}{mu_i left( alpha_i-C ight)}+ u sum_{i=1}^{N}{y_ialpha_i}$

其中，分別為不等式約束(3-1)和(3-2)的拉格朗日乘子，為等式約束(3-3)的拉格朗日乘子。此處拉格朗日乘子所用的字母與前文無關。

KKT條件中梯度為的條件：

$egin{align} frac{partial L}{partial alpha_i}&=sum_{j=1}^{N}{y_iy_jkleft( mathbf{x_i}, mathbf{x_j} ight)alpha_j} -1-lambda_i +mu_i + u y_i\ &= y_i left[ sum_{j=1}^{N}{y_j alpha_j kleft( mathbf{x_i}, mathbf{x_j} ight)} + u ight] -1-lambda_i +mu_i \ &=0 end{align}$

為簡單表示，記 $d_i=sum_{j=1}^{N}{y_j alpha_j kleft( mathbf{x_j}, mathbf{x_i} ight)} + u$ ，則

$frac{partial L}{partial alpha_i}= y_i d_i - 1 - lambda_i + mu_i = 0 ag{4}$

這裡表示函數 $dleft( mathbf x ight)=sum_{j=1}^{N}{y_j alpha_j kleft( mathbf{x_j}, mathbf{x} ight)} + u$ 對樣本 $mathbf{x_i}$ 的輸出。

[個人理解：可類比，而可理解為特徵空間中樣本 $phi (mathbf{x_i})$ 到分離超平面的函數間隔。]

列出問題的KKT條件如下：

$egin{align} 0 leq alpha_i &leq C, i=1,ldots,N ag{5-1}\ sum_{i=1}^{N}{y_i alpha_i} &= 0 ag{5-2}\ lambda_i &geq 0, i=1,ldots,N ag{5-3}\ mu_i &geq 0, i=1,ldots, N ag{5-4}\ lambda_i alpha_i &= 0, i=1,ldots,N ag{5-5}\ mu_i left( alpha_i - C ight) &= 0, i=1,ldots,N ag{5-6}\ y_i d_i - 1 - lambda_i + mu_i &= 0, i=1,ldots,N ag{5-7}\ end{align}\$

為簡化表示，這裡最優解未加星號。

其中，

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

<關於，SMO的停機條件>

John Platt於1998年提出了序列最小最優化(sequential minimal optimization, SMO)演算法(見參考文獻[5]，後文會介紹)，用於在數據集較大時訓練SVM。

SMO演算法的停機條件之一是：

$egin{align} alpha_i = 0 &Leftrightarrow y_id_igeq 1\ 0< alpha_i < C &Leftrightarrow y_id_i = 1\ alpha_i = C &Leftrightarrow y_id_ileq 1\ end{align}\ ag{6}$

然而，

Platt並沒有在這篇文章中解釋(6)式的由來，尤其是這個等價符號；可能是因為作者認為非常簡單，不需要解釋。。。原文是The KKT conditions for the QP problem (...) are particularly simple...
同樣，文獻[4](李航，統計學習方法)第128頁給出了這個條件，也沒有具體推導；
文獻[6]第330頁，將(6)式作為停機準則，不過並沒有採用等價符號。

下面我們來對(6)式進行簡單的推導。

KKT條件(5-1)~(5-7)式是問題的最優解的充要條件。當最優解取值不同時，的取值也不同，分三種情況討論：

(1)若，則

$egin{align} alpha_i = 0\ (5-3)&Rightarrow lambda_i geq 0\ (5-6) &Rightarrow mu_i=0\ (5-7)&Rightarrow y_i d_i = 1 + lambda_i - mu_igeq 1\ end{align}$

不過Platt的文章中使用的是等價符號，所以我們反過來推導試試：

若，則。(這裡可能不太嚴謹。)

也就是說，。

(2)若，則

$egin{align} 0< alpha_i < C\ (5-5)&Rightarrow lambda_i = 0\ (5-6) &Rightarrow mu_i=0\ (5-7)&Rightarrow y_i d_i = 1 + lambda_i - mu_i=1\ end{align}$

反之，若，則。(這裡倒是沒問題。)

也就是說，。

(3)若，則

$egin{align} alpha_i = C\ (5-5)&Rightarrow lambda_i = 0\ (5-6) &Rightarrow mu_igeq 0\ (5-7)&Rightarrow y_i d_i = 1 + lambda_i - mu_ileq 1\ end{align}$

反之，若，則。(這裡同樣可能不太嚴謹。)

也就是說，。

綜上即得到(6)式。

後續將詳細介紹用於訓練SVM的SMO演算法。

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] John C. Platt. Sequential minimal optimization: A fast algorithm for training support vector machines. Technical Report MSR-TR-98-14, Microsoft Research, 1998.

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