[編輯]flydreamGG的公告
[編輯]文章分類(lèi)
存檔
2009年08月(6)
公告： CSDN招聘.NET開(kāi)發(fā)工程師 [意見(jiàn)反饋][官方博客]   LibSVM學(xué)習(xí)（四）——逐步深入LibSVM 收藏
    其實(shí)，在之前上海交大模式分析與機(jī)器智能實(shí)驗(yàn)室對(duì)2.6版本的svm.cpp做了部分注解，（在哪里？google一下你就知道）。但是，這個(gè)注釋只是針對(duì)代碼而注釋?zhuān)聪聛?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)的角度來(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版中沒(méi)有此函數(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是中各類(lèi)的排列順序是按照原始樣本中各類(lèi)出現(xiàn)的先后順序排列的，不一定是按照你原始樣本的label序號(hào)排列，假如原始樣本的label是{-1，0，1}，而最先出現(xiàn)的label為1的樣本，那么perm中就把label為1的作為類(lèi)0最先排列。而start中記錄的是各類(lèi)的起始序號(hào)，而這個(gè)序號(hào)是在perm中的序號(hào)。

 

2. 多類(lèi)判別的one-against-one

      svm做判別是用的分界線(面)，兩類(lèi)之間只有一個(gè)分界線(面)，因此分類(lèi)器也只有1種，要么是1類(lèi)要么是2類(lèi)。但是對(duì)于多類(lèi)，分類(lèi)方式就有多種。目前，存在的方法主要有：

       1）1-V-R方式

       對(duì)于k類(lèi)問(wèn)題，把其中某一類(lèi)的n個(gè)訓(xùn)練樣本視為一類(lèi)，所有其他類(lèi)別歸為另一類(lèi)，因此共有k個(gè)分類(lèi)器。最后預(yù)測(cè)時(shí)，判別式使用競(jìng)爭(zhēng)方式，也就是哪個(gè)類(lèi)得票多就屬于那個(gè)類(lèi)。

       2）1-V-1方式

       也就是我們所說(shuō)的one-against-one方式。這種方法把其中的任意兩類(lèi)構(gòu)造一個(gè)分類(lèi)器，共有(k-1)×k/2個(gè)分類(lèi)器。最后預(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類(lèi)1-V-1組合的示意圖，紅色是0類(lèi)和其他類(lèi)的組合，紫色是1類(lèi)和剩余類(lèi)的組合，綠色是2類(lèi)與右端兩類(lèi)的組合，藍(lán)色只有3和4的組合。因此，對(duì)于nr_class個(gè)類(lèi)的組合方式為：

                                                        for(i = 0; i < nr_class; i ++)

                                                        {

                                                               for(j = i+1; i < nr_class; j ++)     

                                                               { 類(lèi) i –V – 類(lèi) j }

                                                        }

 

3. hessian矩陣的內(nèi)存處理        

      因?yàn)閟vm是基于結(jié)構(gòu)風(fēng)險(xiǎn)最小的，因此在分類(lèi)識(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)存處理類(lèi)Cache類(lèi)，預(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)插入到鏈表尾部。假如沒(méi)計(jì)算過(guò)，就分配內(nèi)存并進(jìn)行計(jì)算，當(dāng)剩余的內(nèi)存不夠時(shí)，就要回收鏈表頭指向的內(nèi)存。這里，可能有人會(huì)問(wèn)，難道以前計(jì)算的就沒(méi)有用了嗎？？其實(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就沒(méi)有用了。其實(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的兩類(lèi)所有支持向量求b，然后取平均值：

                                                                      （4.13）

 

    至此，libSVM的整個(gè)思路我們簡(jiǎn)單的過(guò)了一遍，里面涉及到很到理論知識(shí)，許多細(xì)節(jié)需要查看相關(guān)的SVM的書(shū)籍。說(shuō)實(shí)話，筆者也是新手，有些理論也沒(méi)弄很清楚，我只能把我知道的盡量的講出來(lái)。希望對(duì)一些想要了解SVM的有所幫助。

   

本文來(lái)自CSDN博客，轉(zhuǎn)載請(qǐng)標(biāo)明出處：http://blog.csdn.net/flydreamGG/archive/2009/08/21/4470121.aspx