[編輯]flydreamGG的公告
[編輯]文章分類
存檔
2009年08月(6)
公告： CSDN招聘.NET開發(fā)工程師 [意見反饋][官方博客] LibSVM學(xué)習(xí)（四）——逐步深入LibSVM 收藏
其實(shí)，在之前上海交大模式分析與機(jī)器智能實(shí)驗(yàn)室對(duì)2.6版本的svm.cpp做了部分注解，（在哪里？google一下你就知道）。但是，這個(gè)注釋只是針對(duì)代碼而注釋，整篇看下來(lái)，你會(huì)發(fā)現(xiàn)除了理解幾個(gè)參數(shù)的含義，還是會(huì)對(duì)libsvm一頭霧水。當(dāng)然作為理解程序的輔助材料，還是有很大用處的。特別是，對(duì)幾個(gè)結(jié)構(gòu)體的說(shuō)明，比較清楚。但是要清楚程序具體做了什么，還是要追蹤程序中去。
由于svm涉及的數(shù)學(xué)知識(shí)比較多，我們這篇只是講一些基本的思路，所以就從最基本的C-SVC型svm，核函數(shù)采用常用的RBF函數(shù)。LibSVM就采用2.6版本的好了，因?yàn)楹罄m(xù)的版本作者又加了很多內(nèi)容，不易理解作者最初的思路。我是做模式識(shí)別，主要從分類的角度來(lái)解析函數(shù)的調(diào)用過(guò)程，我們從svmtrain.c看起，其調(diào)用的函數(shù)過(guò)程如下：
上圖是整個(gè)C-SVC的計(jì)算過(guò)程，下面對(duì)一些重要的內(nèi)容進(jìn)行具體說(shuō)明:
1. svm_group_class
在2.6版中沒有此函數(shù)的，其功能直接在svm_train實(shí)現(xiàn)，為了增強(qiáng)可讀性，2.89版中設(shè)置了這個(gè)函數(shù)，其實(shí)所作的工作都是一樣的。需要說(shuō)明的是其重新排列后perm中只存儲(chǔ)的是各個(gè)樣本在原始位置的序號(hào)，而非數(shù)據(jù)。這樣做的好處有兩個(gè)：
1）不必破壞原始數(shù)據(jù)（也就是讀進(jìn)來(lái)的x的數(shù)據(jù)）；
2）檢索起來(lái)方便，只需要L維的數(shù)據(jù)檢索，得到序號(hào)后，然后定位到原始數(shù)據(jù)中相應(yīng)的位置就可以。
perm是中各類的排列順序是按照原始樣本中各類出現(xiàn)的先后順序排列的，不一定是按照你原始樣本的label序號(hào)排列，假如原始樣本的label是{-1，0，1}，而最先出現(xiàn)的label為1的樣本，那么perm中就把label為1的作為類0最先排列。而start中記錄的是各類的起始序號(hào)，而這個(gè)序號(hào)是在perm中的序號(hào)。
2. 多類判別的one-against-one
svm做判別是用的分界線(面)，兩類之間只有一個(gè)分界線(面)，因此分類器也只有1種，要么是1類要么是2類。但是對(duì)于多類，分類方式就有多種。目前，存在的方法主要有：
1）1-V-R方式
對(duì)于k類問(wèn)題，把其中某一類的n個(gè)訓(xùn)練樣本視為一類，所有其他類別歸為另一類，因此共有k個(gè)分類器。最后預(yù)測(cè)時(shí)，判別式使用競(jìng)爭(zhēng)方式，也就是哪個(gè)類得票多就屬于那個(gè)類。
2）1-V-1方式
也就是我們所說(shuō)的one-against-one方式。這種方法把其中的任意兩類構(gòu)造一個(gè)分類器，共有(k-1)×k/2個(gè)分類器。最后預(yù)測(cè)也采用競(jìng)爭(zhēng)方式。
3）有向無(wú)環(huán)圖（DAG-SVM）
該方法在訓(xùn)練階段采用1-V-1方式，而判別階段采用一種兩向有向無(wú)環(huán)圖的方式。
LibSVM采用的是1-V-1方式，因?yàn)檫@種方式思路簡(jiǎn)單，并且許多實(shí)踐證實(shí)效果比1-V-R方式要好。
上圖是一個(gè)5類1-V-1組合的示意圖，紅色是0類和其他類的組合，紫色是1類和剩余類的組合，綠色是2類與右端兩類的組合，藍(lán)色只有3和4的組合。因此，對(duì)于nr_class個(gè)類的組合方式為：
for(i = 0; i < nr_class; i ++)
{
for(j = i+1; i < nr_class; j ++)
{ 類 i –V – 類 j }
}
3. hessian矩陣的內(nèi)存處理
因?yàn)閟vm是基于結(jié)構(gòu)風(fēng)險(xiǎn)最小的，因此在分類識(shí)別方式具有較傳統(tǒng)的基于經(jīng)驗(yàn)風(fēng)險(xiǎn)最小的方式有優(yōu)勢(shì)。但是svm也有一個(gè)致命的缺陷，因?yàn)橐?jì)算hessian矩陣Qij所耗的內(nèi)存巨大，不利于實(shí)踐中應(yīng)用。目前，怎么減小內(nèi)存的使用依舊是SVM的研究的課題。LibSVM對(duì)hessian矩陣處理的策略是定義了一個(gè)內(nèi)存處理類Cache類，預(yù)先認(rèn)為分配一定的內(nèi)存，存儲(chǔ)計(jì)算好的Qij，其序號(hào)的檢索采用雙向鏈表的方式，加快了檢索速度。其最重要的函數(shù)為：
int Cache::get_data(const int index, Qfloat **data, int len)
//len 是 data 的長(zhǎng)度，data為返回的內(nèi)存首地址，index為Qij的行。
每次都要查找鏈表中行為index的Qi，假如已經(jīng)計(jì)算過(guò)了，就返回計(jì)算過(guò)的內(nèi)存地址，并把儲(chǔ)存首地址的鏈表節(jié)點(diǎn)插入到鏈表尾部。假如沒計(jì)算過(guò)，就分配內(nèi)存并進(jìn)行計(jì)算，當(dāng)剩余的內(nèi)存不夠時(shí)，就要回收鏈表頭指向的內(nèi)存。這里，可能有人會(huì)問(wèn)，難道以前計(jì)算的就沒有用了嗎？？其實(shí)，是因?yàn)镼ij是稀疏矩陣，在訓(xùn)練過(guò)程中只要其對(duì)應(yīng)的alpha[i]不再變動(dòng)（這時(shí)alpha[i]=0或者alpha[i]=C），其對(duì)應(yīng)的Qi就不會(huì)被選到來(lái)訓(xùn)練，因此原來(lái)計(jì)算的Qi就沒有用了。其實(shí)，鏈表的順序代表了別選到的頻率，最頭部的是最不可能被選到，因?yàn)檫@時(shí)alpha[i]=0或者alpha[i]=C，而最尾部的最容易被選到。
4. 數(shù)據(jù)選擇select_working_set(i,j)
對(duì)于樣本數(shù)量比較多的時(shí)候（幾千個(gè)），SVM所需要的內(nèi)存是計(jì)算機(jī)所不能承受的。目前，對(duì)于這個(gè)問(wèn)題的解決方法主要有兩種：塊算法和分解算法。這里，libSVM采用的是分解算法中的SMO(串行最小化)方法，其每次訓(xùn)練都只選擇兩個(gè)樣本。我們不對(duì)SMO做具體的討論，要想深入了解可以查閱相關(guān)的資料，這里只談?wù)労统绦蛴嘘P(guān)的知識(shí)。
一般SVM的對(duì)偶問(wèn)題為：
S.t. （4.1）
SVM收斂的充分必要條件是KKT條件，其表現(xiàn)為：
（4.2）
由4.1式求導(dǎo)可得：
（4.3）
進(jìn)一步推導(dǎo)可知：
（4.4）
也就是說(shuō)，只要所有的樣本都滿足4.4式，那么得到解就是最優(yōu)值。因此，在每輪訓(xùn)練中，每次只要選擇兩個(gè)樣本(序號(hào)為i和j)，是最違反KKT條件（也就是4.4式）的樣本，就能保證其他樣本也滿足KKT條件。序號(hào)i和j的選擇方式如下：
（4.5）
5. 停止準(zhǔn)則
LibSVM程序中，停止準(zhǔn)則蘊(yùn)含在了函數(shù)select_working_set(i,j)返回值中。也就是，當(dāng)找不到符合4.5式的樣本時(shí)，那么理論上就達(dá)到了最優(yōu)解。但是，實(shí)際編程時(shí)，由于KKT條件還是蠻苛刻的，要進(jìn)行適當(dāng)?shù)姆潘伞Ａ睿?
（4.6）
由4.4式可知，當(dāng)所有樣本都滿足KKT條件時(shí)，gi ≤ -gj
加一個(gè)適當(dāng)?shù)膶捤煞秶?#949;，也就是程序中的eps，默認(rèn)為0.001，那么最終的停止準(zhǔn)則為：
gi ≤ -gj +ε → gi + gj ≤ε （4.7）
6. 因子α的更新
由于SMO每次都只選擇2個(gè)樣本，那么4.1式的等式約束可以轉(zhuǎn)化為直線約束：
（4.8）
轉(zhuǎn)化為圖形表示為：
把4.8式中α1由α2 表示，即：，結(jié)合上圖由解析幾何可得α2的取值范圍：
（4.9）
經(jīng)過(guò)一系列變換，可以得到的α2更新值α2new：
（4.10）
結(jié)合4.9和4.10式得到α2new最終表達(dá)式：
（4.11）
得到α2new后，就可以由4.8式求α1new。
這里，具體操作的時(shí)候，把選擇后的序號(hào)i和j代替這里的1和2就可以了。當(dāng)然，編程時(shí)，這些公式還是太抽象。對(duì)于4.9式，還需要具體細(xì)分。比如，對(duì)于y1 y2 = -1時(shí)的L = max(0,α2 - α1)，是0大還α2 - α1是大的問(wèn)題?？偣残枰?種情況。
7. 數(shù)據(jù)縮放do_shrinking()
上面說(shuō)到SVM用到的內(nèi)存巨大，另一個(gè)缺陷就是計(jì)算速度，因?yàn)閿?shù)據(jù)大了，計(jì)算量也就大，很顯然計(jì)算速度就會(huì)下降。因此，一個(gè)好的方式就是在計(jì)算過(guò)程中逐步去掉不參與計(jì)算的數(shù)據(jù)。因?yàn)椋瑢?shí)踐證明，在訓(xùn)練過(guò)程中，alpha[i]一旦達(dá)到邊界（alpha[i]=0或者alpha[i]=C），alpha[i]值就不會(huì)變，隨著訓(xùn)練的進(jìn)行，參與運(yùn)算的樣本會(huì)越來(lái)越少，SVM最終結(jié)果的支持向量（0<alpha[i]<C）往往占很少部分。
LibSVM采用的策略是在計(jì)算過(guò)程中，檢測(cè)active_size中的alpha[i]值，如果alpha[i]到了邊界，那么就應(yīng)該把相應(yīng)的樣本去掉（變成inactived），并放到棧的尾部，從而逐步縮小active_size的大小。
8. 截距b的計(jì)算
b計(jì)算的基本公式為：
（4.12）
理論上，b的值是不定的。當(dāng)程序達(dá)到最優(yōu)后，只要用任意一個(gè)標(biāo)準(zhǔn)支持向量機(jī)（0<alpha[i]<C）的樣本帶入4.12式，得到的b值都是可以的。目前，求b的方法也有很多種。在libSVM中，分別對(duì)y=+1和y=-1的兩類所有支持向量求b，然后取平均值：
（4.13）
至此，libSVM的整個(gè)思路我們簡(jiǎn)單的過(guò)了一遍，里面涉及到很到理論知識(shí)，許多細(xì)節(jié)需要查看相關(guān)的SVM的書籍。說(shuō)實(shí)話，筆者也是新手，有些理論也沒弄很清楚，我只能把我知道的盡量的講出來(lái)。希望對(duì)一些想要了解SVM的有所幫助。
