libsvm最新源代碼（版本3.21）了解解析（二）一、回顧二、SMO算法三、KKT條件四、工作集的選擇五、和的更新

一、回顧

上節，我們介紹到了SMO的總體過程，本節對SMO的三個難點結合代碼進行詳細分析。

二、SMO算法

（1）設定拉格朗日乘子α=(α[1]...α[i]...α[l])的初始值（一般設為全0），并設定疊代次數計數器k=1。

（2）如果α向量已經收斂（符合KKT達到停止條件），停止循環，傳回結果；否則，找出工作集B=(i,j)，實際上就是找出所要更新的兩個α（α[i],α[j]）的下标，另外定義剩下的α的下标标号為N，即N=(1,2...l)\B（\表示去掉B中元素），并定義B所對應的α為

，N所對對應的α為

。

（3）若

，解決如下問題：

否則，解決下面問題：

實際上都是關于α的更新方式，至于如何解決這兩個問題以及α的詳細計算公式會在後面介紹。

4）用新的α[i]，α[j]替換原來的α[i]，α[j]，疊代計數器k=k+1，跳到第二步，繼續循環。

三、KKT條件

在上一篇部落格說過，上述SMO算法存在三個難點：

（1）如何判斷α收斂，即如何停止循環，達到KKT條件。

（2）如何找出工作集B=(i,j)，即如何選出兩個要更新的α=(α[i],α[j])；

（3）如何更新工作集中的α，即如何更新α[i]，α[j]。

下面我們來看如何解決第一個問題。

那麼什麼是KKT條件呢？

假設我們要解決的是含有等式和不等式限制的最優化問題：

其中，p為等式限制條件的數量，q為不等式限制條件的數量。

f(x)在達到最優值（最小值）時必須滿足KKT條件，即：

這就是所謂的KKT條件，也就是等式的拉格朗日乘子λ不能為0，不等式（必須是小于号）的拉格朗日乘子μ必須大于0且與不等式g(x)的乘積等于0，同時拉格朗日函數對未知數α的導數等于0（上述2式）。

下面，我們看支援向量機的優化問題：

上述優化問題經過整理可得：

包含兩個不等式集合（分别為l個）和一個等式限制集合（l個）。

該優化問題的拉格朗日函數如下：

其中，b,λ,ξ均為拉格朗日乘子，進而可得KKT條件為：

即：

        其中，

。

當

<C時，C-α>0，ξ(C-α)=0，那麼ξ=0，又因為λ>=0，是以由14式得：

>=0

同理，可得當

>0，因為λα=0，是以λ=0,因為ξ>=0，是以由14式得： 

<=0。

綜上所知，得：

因為，y取+1或者-1，将15式左右乘以yi，又可以分兩種情況，比如

>C時，如果

=+1，那麼

=

+b>=0；當

=-1時，兩面乘以

，得-

=-

-b>=0,即

+b<=0，同理可分析當

>0和

=+1和-1的情況，最後可得一個關于b的不等式：

實際上，上式就是15式對

=+1和-1兩種情況的讨論結果。這意味着，滿足KKT條件就得滿足上式，也就是：

當然，在現實中，我們不這麼嚴密，常采取以下的條件，即：

ε被稱為容忍因子。

是以，當我們檢測17式就可以當作SMO循環結束的條件，LIBSVM中也是這麼做的。

四、工作集的選擇

在第三節中，我們讨論了SMO的一個難點就是SMO循環結束的停止條件，接下來我們讨論如何選取工作集B=(i,j)，也就是如何選取所要更新的

和

。至于原理性的内容，論文Working Set Selection Using Second Order Information for Training Support Vector Machines（http://www.csie.ntu.edu.tw/~cjlin/papers/quadworkset.pdf）進行了詳細介紹，挺難了解的，本人目前也未了解，後續可能對原理性繼續進行闡述。本文主要對選擇過程進行描述。

工作集B=(i,j)的選擇過程如下：

（1）計算

和

（2）若

>0，則

=

，否則

=

，

是自行設定的一個很小的正數。即：

（3）接下來選擇i和j，通過選擇最大離散對。首先選擇i，

通過計算

，找出集合

中使得

最大的那個t（t屬于

），将其值賦給i。

找出i後，根據i值尋找j:

上式的意思是在一個集合中計算

值，找出使該值最小的t，賦給j,這個t屬于的集合滿足兩個條件：首先t屬于集合

，同時，還得滿足

，這裡的i為第一步中選出的i。

過程稍微比較繞，但是了解了後就是兩步，第一步找出i，然後根據i找出j。

（4）将i和j傳回。

五、

和

的更新

在第四節中我們找出了α的标号i和j,也就是工作集i和j，那麼接下來就是更新

和

。

在開頭我們介紹的SMO算法流程中，介紹了α的更新要根據

是否大于0來解決兩個問題，這兩個問題的詳細解決過程在論文LIBSVM: A Library for Support Vector Machines（http://www.csie.ntu.edu.tw/~cjlin/papers/libsvm.pdf）進行了介紹，本文隻講述結果。

經過論文中的轉換和計算，最終

和

的計算公式如下：

其中，

和

為舊值，

和

為所對應的樣本标簽值，

時，

，

時

，

。

因為

和

可能同号也可能異号，是以42式又可以分為兩種情況，這裡我們拿異号讨論一下，同号可類似。

當

和

異号時：

将

帶入42式得：

同時，因為

和

還有0<=α<=C的限制。假設，我們将

對應的懲罰因子記為

，

對應的懲罰因子記為

（上篇博文中我們說過，為了應對不平衡資料，不同符合的α可能采取不同的懲罰因子C），那麼綜合考慮，α的更新如下：

這個圖将α的更新的各種限制分為4個區域。因為

（因為SMO更新兩個α，其它不變，所有的α滿足y1α1+y2α2+...ylαl=常數，即yiαi+yjαj=常數，帶入y就可得，減号是因為yi和yj異号），我們拿region I當作例子分析一下：

超過了界限

，是以

取最大值

，由于

，是以綜上所知，可得：

同樣，當處于region II等其它區域時，可類似分析。

這樣，α得更新就介紹完畢了，完整僞代碼如下：  

if (y[i] != y[j])
{
	double quad_coef = Q_i[i] + Q_j[j] + 2 * Q_i[j];
	if (quad_coef <= 0)quad_coef = TAU;
	double delta = (-G[i] - G[j]) / quad_coef;
	double diff = alpha[i] - alpha[j];
	alpha[i] += delta;
	alpha[j] += delta;
	if (diff > 0)
	{
		if (alpha[j] < 0) // in region III
		{
			alpha[j] = 0;
			alpha[i] = diff;
		}
	}
	else
	{
		if (alpha[i] < 0) // in region IV
		{
			alpha[i] = 0;
			alpha[j] = -diff;
		}
	}
	if (diff > C_i - C_j)
	{
		if (alpha[i] > C_i) // in region I
		{
			alpha[i] = C_i;
			alpha[j] = C_i - diff;
		}
	}
	else
	{
		if (alpha[j] > C_j) // in region II
		{
			alpha[j] = C_j;
			alpha[i] = C_j + diff;
		}
	}
}
If yi = yj, the derivation is the same.
           

六、總結

本文詳細介紹了LIBSVM中SMO算法最重要得三個難點，結合代碼的分析将在以後進行介紹。