關(guān)于adaboost的一些說明上學(xué)期拿出一部分時間來做adaboost，做的時候做了一些筆記。論壇上也有一些正在讀程序研究算法的人。我就把這份粗糙的筆記拿出來與大家分享一下吧?？隙ㄓ绣e誤的地方，也有不妥當(dāng)?shù)牡胤?，大家不要太相信?/p>

還有這個地方不能貼公式，不能貼圖片，還有我很懶，就挑了幾幅重要的貼了，其他的大家去看文章吧

排版不好看，也許寫得也不明白，大家多包涵，希望大家可以完善這個文檔。讓后來者少走些彎路。

不用發(fā)論壇消息問我，發(fā)在這里讓更多人看見，更多人解答，然后也可以讓更多的人知道，更好些

第一部分:算法的產(chǎn)生

1996年YoavFreund在ExperimentswithaNewBoostingAlgorithm中提出了AdaBoost.M1和AdaBoost.M2兩種算法.其中,AdaBoost.M1是我們通常所說的DiscreteAdaBoost;而AdaBoost.M2是M1的泛化形式.該文的一個結(jié)論是:當(dāng)弱分類器算法使用簡單的分類方法時,boosting的效果明顯地統(tǒng)一地比bagging要好.當(dāng)弱分類器算法使用C4.5時,boosting比bagging較好,但是沒有前者的比較來得明顯.

文獻(xiàn)中記錄的.M1算法

初始

1.獲得一組樣本(X)和它的分類(Y)和一個分類器(weaklearn).

2.賦予平均的權(quán)值分布D(i)

進(jìn)入循環(huán):T次

1.賦予弱分類器權(quán)值D(i),使用弱分類器獲得樣本(X)到分類(Y)上的一個映射.(就是把某個X歸到某個Y類中去)

2.計算這個映射的誤差e.e=各個歸類錯誤的樣本權(quán)值之和.如果e>1/2那么弱分類器訓(xùn)練失敗,挑出循環(huán),訓(xùn)練結(jié)束(這在二值檢測中是不會發(fā)生的,而多值的情況就要看分類器夠不夠強(qiáng)健了)

3.設(shè)B=e/(1-e).用于調(diào)整權(quán)值.因為e<1/2.因此0<B<1

4.如果某樣本分類正確,該樣本的權(quán)值就乘以B讓權(quán)值變小;如果分類錯誤,就讓該樣本的權(quán)值乘以B^-1或者不變,這樣就讓分類正確的樣本權(quán)值降低,分類錯誤的樣本權(quán)值升高,加強(qiáng)了對較難分類樣本的分類能力

5.權(quán)值均衡化

循環(huán)結(jié)束

1.最終的分類器是,當(dāng)一個X進(jìn)入時,遍歷所有Y,尋找使(h(x)=y的情況下,log(1/B)之和)最大者即是輸出分類y

M2相比于M1的改進(jìn)是允許弱分類器輸出多個分類結(jié)果,并輸出這幾個分類結(jié)果的可能性(注意,這里不是概率)

.M2的流程是

1.獲得一組樣本(X)和它的分類(Y)和一個分類器(weaklearn).

2.對于某個樣本Xi將它的分類歸為一個正確分類Yi和其他不正確分類Yb

3.樣本權(quán)值進(jìn)行如下分布首先每個樣本分到1/m的權(quán)值,然后每個不正確分類分到(1/m)/Yb的個數(shù).也就是說樣本權(quán)值是分到了每個不正確的分類上

進(jìn)入循環(huán)

1.求每個樣本的權(quán)值,即每個樣本所有不正確的分類的權(quán)值和,再求每個樣本錯誤分類的權(quán)值,即不正確分類的權(quán)值除以該樣本的權(quán)值.最后將每個樣本的權(quán)值歸一化

2.將樣本權(quán)值和某樣本的不正確分類的權(quán)值輸入到weaklearn,獲得弱分類器的輸出為各個分類的可能值

3.計算偽錯誤率:公式見上

4.更新權(quán)值

退出循環(huán)

最終的強(qiáng)分類器:圖貼不出來了...

1999年,ROBERTE.SCHAPIRE和YORAMSINGER,于MachineLearning發(fā)表論文:ImprovedBoostingAlgorithmsUsingConfidence-ratedPredictions.提出了更具一般性的AdaBoost形式.提出了自信率以改善AdaBoost的性能.并提出了解決多標(biāo)簽問題的AdaBoost.MH和AdaBoost.MR算法,其中AdaBoost.MH算法的一種形式又被稱為RealBoost算法.

事實上:DiscreteAdaBoost是指,弱分類器的輸出值限定在{-1,+1}，和與之相應(yīng)的權(quán)值調(diào)整，強(qiáng)分類器生成的AdaBoost算法；RealAdaBoost是指，弱分類器輸出一個可能度，該值的范圍是整個R,和與之相應(yīng)的權(quán)值調(diào)整，強(qiáng)分類器生成的AdaBoost算法。事實上，Discrete到Real的轉(zhuǎn)變體現(xiàn)了古典集合到模糊集合轉(zhuǎn)變的思想

至于GentleAdaBoost.考慮到(AdaBoost對”不像”的正樣本權(quán)值調(diào)整很高,而導(dǎo)致了分類器的效率下降),而產(chǎn)生的變種算法.它較少地強(qiáng)調(diào)難以分類的樣本.

RainerLienhart,AlexanderKuranov,VadimPisarevsky在論文EmpiricalAnalysisofDetectionCascadesofBoostedClassifiersforRapidObjectDetection中提出在stump弱分類器(即每個弱分類器使用一個特征進(jìn)行分類)上進(jìn)行的對比試驗中,Gentle的結(jié)果明顯好于Real和Discrete.大牛已經(jīng)做出試驗了,我就不懷疑它了.

和上篇論文流程大體相同.作者還討論了alpha(t)的取法:

算法去看文章吧...這里不能直接貼圖

文獻(xiàn)中記錄的AdaBoost.MH算法

算法的運(yùn)算流程:

1.得到一組樣本(m個)和樣本相應(yīng)的分類,這個分類是由K個是和否的標(biāo)簽組成.某一個樣本可以有多個是標(biāo)簽.

*****************還有一篇巨大量負(fù)樣本的速度提高方法找不到了……

第三部分,OpenCv中AdaBoost訓(xùn)練程序略解

這里只介紹一個大概的情況,具體的都寫在代碼的注釋里了.

1.結(jié)構(gòu):

程序的總體結(jié)構(gòu)是一棵多叉樹,每個節(jié)點多少個叉由初始設(shè)定的maxtreesplits決定

樹節(jié)點結(jié)構(gòu):

typedefstructCvTreeCascadeNode

{

CvStageHaarClassifier*stage;//指向該節(jié)點stage強(qiáng)分類器的指針

structCvTreeCascadeNode*next;//指向同層下一個節(jié)點的指針

structCvTreeCascadeNode*child;//指向子節(jié)點的指針

structCvTreeCascadeNode*parent;//指向父節(jié)點的指針

structCvTreeCascadeNode*next_same_level;//最后一層葉節(jié)點之間的連接

structCvTreeCascadeNode*child_eval;//用于連接最終分類的葉節(jié)點和根節(jié)點

intidx;//表示該節(jié)點是第幾個節(jié)點

intleaf;//從來沒有用到過的參數(shù)

}CvTreeCascadeNode;

這里需要說明的是child_eval這個指針，雖說人臉檢測是一個單分類問題，程序中的maxtreesplits的設(shè)置值為0，沒有分叉，但是樹本身是解決多分類問題的，它有多個葉節(jié)點，也就有多個最終的分類結(jié)果。但是我們使用的時候，雖然是一個多分類的樹，也可能我們只需要判斷是或者不是某一類。于是我們就用root_eval和child_eval把這個分類上的節(jié)點索引出來，更方便地使用樹結(jié)構(gòu)。當(dāng)然，這一點在本程序中是沒有體現(xiàn)的。

分類器結(jié)構(gòu)：

每個樹節(jié)點中都包含了一個CvStageHaarClassifier強(qiáng)分類器，而每個CvStageHaarClassifier包含了多個CvIntHaarClassifier弱分類器。當(dāng)CvIntHaarClassifier被使用的時候，被轉(zhuǎn)化為CvCARTHaarClassifier，也就是分類樹與衰減數(shù)分類器作為一個弱分類器。

typedefstructCvCARTHaarClassifier

{

CV_INT_HAAR_CLASSIFIER_FIELDS()

intcount;/*在決策樹中的節(jié)點數(shù)numberofnodesinthedecisiontree*/

int*compidx;//特征序號

CvTHaarFeature*feature;//選出的特征。數(shù)組

CvFastHaarFeature*fastfeature;

float*threshold;/*arrayofdecisionthresholds*/

int*left;/*arrayofleft-branchindices*/

int*right;/*arrayofright-branchindices*/

float*val;/*arrayofoutputvalues*/

}CvCARTHaarClassifier;

CvCARTHaarClassifier結(jié)構(gòu)中包含了弱分類器的左值右值閾值等數(shù)組，在我們的程序中CART只選用了一個特征進(jìn)行分類，即退化成了stump。這里的數(shù)組里面就只存有一個元了

那么這里為什么要使用一個如此復(fù)雜的結(jié)構(gòu)呢。大體來說有兩個好處：

1、方便弱分類器之間的切換，當(dāng)我們不選用CART而是其他的弱分類器結(jié)構(gòu)的時候，就可以調(diào)用CvIntHaarClassifier時轉(zhuǎn)換成其他的指針

2、這樣方便了Haar訓(xùn)練的過程和Boost過程的銜接。

特征的結(jié)構(gòu)：

2.OpenCV的HaarTraining程序中一種常用的編程方法：

在這個程序中，函數(shù)指針是一種很常用的手法。函數(shù)指針的轉(zhuǎn)換使讀程序的人更難把握程序的脈絡(luò)，在這里舉一個最極端的例子，來說明程序中這種手法的應(yīng)用。

我們在cvBoost.cpp文件中的cvCreateMTStumpClassifier函數(shù)（這是一個生成多閾值(Multi-threshold)stump分類器的函數(shù)）下看到了一個這樣的調(diào)用：

findStumpThreshold_16s[stumperror]（……….）

這里對應(yīng)的stumperror值是2

在cvboost.cpp中我們找到了一個這樣的數(shù)組

CvFindThresholdFuncfindStumpThreshold_16s[4]={

icvFindStumpThreshold_misc_16s,

icvFindStumpThreshold_gini_16s,

icvFindStumpThreshold_entropy_16s,

icvFindStumpThreshold_sq_16s

};

這個數(shù)組的類型是一個類型定義過的函數(shù)指針typedefint(*CvFindThresholdFunc)（…..）

因此這個數(shù)組中的四項就是四個指針，我們在cvCreateMTStumpClassifier中調(diào)用的也就是其中的第三項icvFindStumpThreshold_entropy_16s。

然后我們發(fā)現(xiàn)這個函數(shù)指針沒有直接的顯性的實現(xiàn)。那么問題出在哪里呢？

它是通過宏實現(xiàn)的：

程序中定義了一個這樣的宏：

#defineICV_DEF_FIND_STUMP_THRESHOLD_SQ(suffix,type)

ICV_DEF_FIND_STUMP_THRESHOLD(sq_##suffix,type,

/*calculateerror(sumofsquares)*/

/*err=sum(w*(y-left(rigt)Val)^2)*/

curlerror=wyyl+curleft*curleft*wl-2.0F*curleft*wyl;

currerror=(*sumwyy)-wyyl+curright*curright*wr-2.0F*curright*wyr;

)

和一個這樣的宏：

#defineICV_DEF_FIND_STUMP_THRESHOLD(suffix,type,error)

CV_BOOST_IMPLinticvFindStumpThreshold_##suffix(…..)

{

……..

}

這兩個宏中，后者是函數(shù)的主體部分，而函數(shù)的定義通過前者完成。即：

ICV_DEF_FIND_STUMP_THRESHOLD_ENTROPY(16s,short)，這樣的形式完成。這相當(dāng)于給前者的宏傳遞了兩個參數(shù)，前者的宏將第一個參數(shù)轉(zhuǎn)換成sq_16s后和第二個參數(shù)一起傳到后者的宏。（##是把前后兩個string連接到一起，string是可變的兩，在這里suffix就放入了16s和sq_結(jié)合成了sq_16s）

后者的宏接收到參數(shù)以后就進(jìn)行了函數(shù)的定義：

CV_BOOST_IMPLinticvFindStumpThreshold_sq_16s

這樣icvFindStumpThreshold_sq_16s就被定義了。這樣做的好處是，12個非常相似的函數(shù)可以通過兩個宏和12個宏的調(diào)用來實現(xiàn)，而不需要直接定義12個函數(shù)。

3.訓(xùn)練結(jié)果中數(shù)據(jù)的含義：

-<feature>

-<rects>

<_>64129-1.</_>

//矩陣。前四個數(shù)值是矩陣四個點的位置，最后一個數(shù)值是矩陣像素和的權(quán)值

<_>671233.</_>

//矩陣。前四個數(shù)值是矩陣四個點的位置，最后一個是像素和的權(quán)值，這樣兩個矩陣就形成了一個Haar特征

</rects>

<tilted>0</tilted>//是否是傾斜的Haar特征

</feature>

<threshold>-0.0315119996666908</threshold>//閾值

<left_val>2.0875380039215088</left_val>//小于閾值時取左值

<right_val>-2.2172100543975830</right_val>//大于閾值時取右值

4.訓(xùn)練過程中使用的算法

這里主要講弱分類器算法

?矩形特征值：Value[i][j],1≤i≤n代表所有的Haar特征，1≤j≤m代表所有的樣本

?FAULT=(curlerror+currerror)表示當(dāng)前分類器的錯誤率的最小值，初始設(shè)置：curlerrorcurrerror=1000000000000000000000000000000000000000000000000(反正給個暴力大的數(shù)值就對了)

幾種adaboos算法的區(qū)別事實上:DiscreteAdaBoost是指,弱分類器的輸出值限定在{-1,+1}，和與之相應(yīng)的權(quán)值調(diào)整，強(qiáng)分類器生成的AdaBoost算法；RealAdaBoost是指，弱分類器輸出一個可能度，該值的范圍是整個R,和與之相應(yīng)的權(quán)值調(diào)整，強(qiáng)分類器生成的AdaBoost算法。事實上，Discrete到Real的轉(zhuǎn)變體現(xiàn)了古典集合到模糊集合轉(zhuǎn)變的思想

Logit和Gentle算法是由同一個人提出的，他認(rèn)為adaboost實際上是一個尋優(yōu)過程，然后用運(yùn)籌學(xué)里的兩種不同的尋優(yōu)方法提出了logit和gentle，logit是自適應(yīng)的牛頓法，gentle是用的牛頓步長法。作者認(rèn)為，logitAdaBoost在每一輪中都使目標(biāo)最優(yōu),會使訓(xùn)練樣本的代表性下降。然后這位作者的這篇文章被幾位大牛批了一遍...具體見DiscussionofthePaperAdditiveLogisticRegressionAStatisticalViewofBoostingbyJeromeFriedman,TrevorHastieandRobertTibshirani

另外，值得一提的是

1、2004年,BoWU&HaizhouAI&ChangHUANG&ShihongLAO在ComputerSociety上發(fā)表文章FastRotationInvariantMulti-ViewFaceDetectionBasedonRealAdaBoost.提出了使用RealBoost檢測旋轉(zhuǎn)人臉，獲得了很好的效果

2、2002年,RainerLienhart&AlexanderKuranov&VadimPisarevsky在MRLTechnicalReport上發(fā)表EmpiricalAnalysisofDetectionCascadesofBoostedClassifiersforRapidObjectDetection.通過試驗得出結(jié)論,在人臉檢測上GentleAdaBoost的效果要好于Discrete和Real。這也是Opencv里為什么要用Gentle的原因吧Gentleboost算法的人物檢測方法,利用人物的身體碎片以及這些碎片相對于身體中心的相對位置作為特征,用Gentleboost算法訓(xùn)練的分類器來對人體進(jìn)行分類。為了提高分類器的學(xué)習(xí)效率,解決復(fù)雜場景中人體檢測的難題,提出了一種利用線性回歸末端作為弱分類器的方法,從正、負(fù)兩個方面對預(yù)測模型進(jìn)行加權(quán),改變了原來的僅從正預(yù)測進(jìn)行加權(quán)的方法1.2Gentleboost算法及其操作步驟本文采用的Gentleboost算法是AdaBoosting算法的進(jìn)一步改進(jìn),它比AdaBoost收斂的要快而且對于物體檢測執(zhí)行的也比較好[1],針對人體比較復(fù)雜,有關(guān)節(jié)相連,容易發(fā)生變形,而且所處的環(huán)境復(fù)雜多變,檢測困難的特點,對原來的Gentleboost算法作了進(jìn)一步的改進(jìn)。假如X表示樣本集,Rn表示樣本空間,Y表示類別標(biāo)識集合,由于人物檢測是二值分類問題,此時Y={1,-1},分別對應(yīng)樣本的正和負(fù)。對于N個被標(biāo)注的樣例數(shù)列[(x1,y1),?,(xN,yN)],這里xi∈Rn,yi∈Y±1。(1)首先,初始化權(quán)值w=1,而不是以前的wi=1/N,這樣使執(zhí)行起來比較方