Adaboost算法的前世今生

引言

眾所周知，模式識別的方法可以按照參與識別特征的屬性來區分，可以分為兩大類：一、使用定量特征(可度量)如物體長度、寬度等，來描述的各種模式，這一類主要是指決策理論，有匹配、統計、神經網絡等方法；二、使用定性特征如特征結構、排列順序等，來描繪的各種模式，這一類主要是指結構判別，主要有串和樹的匹配等方法。

模式識別的完整的流程順序是：傳感器——分割組織——特征提取——分類器——后處理。其中分類器的設計部分，可以使用的理論有很多，目前主要包括：基于統計理論的方法(貝葉斯理論)、線性判別函數、神經網絡的方法、隨機方法(對于復雜的問題)、非度量方法(定性結構特征)

分類器得到的模型不僅要很好擬合輸入數據，還要能夠正確地預測未知樣本的類標號。因此，訓練算法的主要目標就是要建立具有很好的泛化能力模型，即建立能夠準確地預測未知樣本類標號的模型。

通常我們用“方差”和“偏差”來測量學習算法與給定分類問題的“匹配”和“校準”程度。“偏差”度量的是匹配的“準確性”和“質量”：一個高的偏差意味著一個壞的匹配，“方差”度量的是匹配的“精確性”和“特定性”：一個高的方差意味著一個弱的匹配。

研究表明，使用重采樣技術可以提高分類器的準確率，而boosting算法就是涉及分類器設計中的重采樣技術。其思想內涵在于：從給定的數據集中抽取多個數據子集，使得有可能計算任意統計量的值及其范圍。

說道boosting，不得不說Arcing(adaptive reweighting and

combining)自適應的權值重置和組合：重新使用和選擇數據，以期達到改善分類器性能的目的。最簡單的arcing版本就是bagging算法。

Bagging一個多分類器系統

bagging算法的基本思想:

給定一個弱學習算法，和一個訓練集；單個弱學習算法準確率不高；將該學習算法使用多次，得出預測函數序列，進行投票，最后結果準確率將得到提高。

步驟1：從大小為n的原始數據集D中，分別獨立隨機的抽取n’個數據(n’

步驟2：每一個自助數據集都被獨立的用于訓練一個“分量分類器”。

步驟3、最終的分類判決由這些“分量分類器”各自的判決結果投票決定。

Bagging算法是第一個多分類器系統，后面還有(組合分類器系統)。

算法:

For t = 1,

2, …, T Do

從數據集S中取樣(放回選樣)

訓練得到模型Ht

對未知樣本X分類時,每個模型Ht都得出一個分類，得票最高的即為未知樣本X的分類，也

可通過得票的平均值用于連續值的預測 。

Bagging 和boosting的區別

訓練集:

預測函數

準確性

使用要求

Bagging

隨機選擇,各輪訓練集相互獨立

沒有權重;可以并行生成

在有些數據集中，boosting會引起退化

要求“不穩定”的分類方法

Boosting

各輪訓練集并不獨立,它的選擇與前輪的學習結果有關

有權重;只能順序生成

在大多數數據集中，boosting的準確性比bagging高

要求“不穩定”的分類方法

訓練集的小變動能夠使得分類模型顯著變動

Bagging是一個純粹的降低相關度的方法，如果樹的節點具有很高的相關性，bagging就會有好的結果。早期的AdaBoost在第二步的時候采用重采樣方法，即使某些樣本權重增加。這種方法與bagging存在某種關聯。它也是Boost的成功之處中降低相關度方面的重要部分。

AdaBoost在第二步中如果使用加權的tree-growing算法，而不是重采樣算法,效果會更好。可以使用stumps作為弱分類器

最初的boosting算法

1989年Kearns and Valiant研究了PAC學習模型中弱學習算法和強學習算法兩者間的等價問題，即任意給定僅僅比隨機猜測稍好(準確率大于0.5)的弱學習算法，是否可以被提升為強學習算法？若兩者等價，則我們只需尋找一個比隨機猜測稍好的弱學習算法，然后將其提升為強學習算法，從而不必費很大力氣去直接尋找強學習算法。就此問題，Schapire于1990年首次給出了肯定的答案。他主持這樣一個觀點：任一弱學習算法可以通過加強提升到一個任意正確率的強學習算法，并通過構造一種多項式級的算法來實現這一加強過程，這就是最初的Boosting算法的原型。

主要思想是，根據已有的訓練樣本集設計一個分類器，要求其準確率要比平均性能好，然后依次順序加入多個分量分類器系統，最后形成一個總體分類器。

以一個二類問題舉例。

步驟1：從大小為n的原始樣本集D中隨機選取n1 個樣本點(不放回)，組成樣本集D1。根據D1訓練出第一個分類器C1。

步驟2：構造第二個樣本集D2，它是根據C1最富信息的那些樣本點組成的。在最后產生的D2集合中將有一半的樣本被C1正確分類，而另一半的樣本被C1錯誤分類。

步驟3：繼續構造第三個樣本集D3，方法：在D中剩余的樣本中選取樣本點，并且用C1和C2進行分類，如果C1和C2判決結果不同，那么就把樣本加入D3，否則就忽略這個樣本。然后用D3訓練新分類器C3。

步驟4：用這3個分類器對新樣本x進行分類，如果C1和C2的判決結果相同，則表為一類，不同則表為另一類。

Boosting方法有許多不同的變形，其中最流行的一種就是adaboost。這個名詞是“adaptive boosting”的縮寫。這個方法允許設計者不斷的加入新的“弱分類器”，直到達到某個預定的最小錯誤率。

1995年Freund and Schapire提出

AdaBoost算法。

1996年Yoav Freund在Experiments with a New Boosting

Algorithm中提出了AdaBoost.M1和AdaBoost.M2兩種算法。其中，AdaBoost.M1是我們通常所說的Discrete AdaBoost：而AdaBoost.M2是M1的泛化形式。該文的一個結論是:當弱分類器算法使用簡單的分類方法時，boosting的效果明顯地統一地比bagging要好。當弱分類器算法使用C4.5時，boosting比bagging較好，但是沒有前者的比較來得明顯。

AdaBoost.M1 Discrete

AdaBoost：

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

2.賦予平均的權值分布D(i)進入循環:T次1. 賦予弱分類器權值D(i),使用弱分類器獲得樣本(X)到分類(Y)上的一個映射.(就是把某個X歸到某個Y類中去)

2. 計算這個映射的誤差e，e=各個歸類錯誤的樣本權值之和.如果e>1/2那么弱分類器訓練失敗,跳出循環,

訓練結束(這在二值檢測中是不會發生的,而多值的情況就要看分類器夠不夠強健了)

3. 設beta B = e / ( 1 - e

).用于調整權值.因為e<1/2.因此0

4. 如果某樣本分類正確,該樣本的權值就乘以B讓權值變小;如果分類錯誤,就讓該樣本的權值乘以B^-1或者不變,這樣就讓分類正確的樣本權值降低,分類錯誤的樣本權值升高,加強了對較難分類樣本的分類能力5. 權值均衡化循環結束1. 最終的分類器是,當一個X進入時,遍歷所有Y,尋找使(h(x)=y的情況下,log(1/B)之和)最大者即是輸出分類y

書上版本

具體算法：

每個樣本都賦予一個權重，T次迭代，每次迭代后，對分類錯誤的樣本加大權重，使得下一次的迭代更加關注這些樣本。

輸入:(X1,Y1),

(X2,Y2),…(Xn,Yn)

Xi∈X, Yi∈Y={+1,-1}

初始化權值:D1(i)=1/n

For t=1,…,T

在Dt下訓練,

得到弱的假設ht:

X->{-1,+1},

錯誤率:Εt=ΣDt(i)

[ht(Xi)≠Yi]

選擇αt=1/2 ln (

(1- Εt)/

Εt ),

更改權值:

if ht(Xi)≠Yi , Dt+1(i)=Dt(i)* eαt /Zt

if ht(Xi)=Yi , Dt+1(i)=Dt(i)* e

-αt /Zt

輸出:H(X)=sign( ∑

αtht(X) )

帶圖版本(程序版本)：

初始賦予每個樣本相等的權重1/N

；

For t = 1, 2, …, T Do

學習得到分類法Ct；

計算該分類法的錯誤率Et

Et=所有被錯誤分類的樣本的權重和；

βt= Et/(1 - Et)

根據錯誤率更新樣本的權重；

正確分類的樣本： Wnew= Wold*

βt

錯誤分類的樣本： Wnew=

Wold

調整使得權重和為1；

每個分類法Ct的投票價值為log [ 1 / βt

]

最大錯誤率問題：

將γt=1/2-Et ;

Freund and Schapire 證明:

最大錯誤率為:

即訓練錯誤率隨γt的增大呈指數級的減小.

最大總誤差:

m : 樣本個數

d : VC維

T : 訓練輪數

Pr: 對訓練集的經驗概率

如果T值太大,Boosting會導致過適應(overfit)

《模式分類》386頁

AdaBoost.M2是M1的泛化形式

.M2的流程是

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

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

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

進入循環1. 求每個樣本的權值,即每個樣本所有不正確的分類的權值和,再求每個樣本錯誤分類的權值,即不正確分類的權值除以該樣本的權值.最后將每個樣本的權值歸一化2. 將樣本權值和某樣本的不正確分類的權值輸入到weaklearn,獲得弱分類器的輸出為各個分類的可能值3. 計算偽錯誤率:

4. 更新權值退出循環

1999年，ROBERT E. SCHAPIRE和YORAM SINGER，于Machine Learning發表論文：

Improved Boosting Algorithms Using

Confidence-rated Predictions。提出了更具一般性的AdaBoost形式。提出了自信率以改善AdaBoost的性能。并提出了解決多標簽問題的AdaBoost.MH和AdaBoost.MR算法，其中AdaBoost.MH算法的一種形式又被稱為Real Boost算法。事實上：Discrete AdaBoost是指，弱分類器的輸出值限定在{-1,+1}，和與之相應的權值調整，強分類器生成的AdaBoost算法；Real AdaBoost是指，弱分類器輸出一個可能度，該值的范圍是整個R，和與之相應的權值調整，強分類器生成的AdaBoost算法。

事實上，Discrete到Real的轉變體現了古典集合到模糊集合轉變的思想。

至于Gentle

AdaBoost?？紤]到(AdaBoost對”不像”的正樣本權值調整很高,而導致了分類器的效率下降)，而產生的變種算法。它較少地強調難以分類的樣本。Rainer Lienhart，

Alexander

Kuranov，

Vadim

Pisarevsky在論文Empirical Analysis of Detection Cascades of

Boosted Classifiers for Rapid Object Detection中提出在stump弱分類器(即每個弱分類器使用一個特征進行分類)上進行的對比試驗中，Gentle的結果明顯好于Real和Discrete。

AdaBoost.MH(real)

算法的運算流程:

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

2. 均分權值:1/mk進入循環:

1. 由弱分類器獲得各樣本針對各標簽的是或否結果(給出離散值或連續值)

2. 獲得alpha(t)3. 調整權值.大概是,弱分類器判斷l標簽的是或否,若判斷正確乘以1,錯誤乘以-1,再乘以 ,然后…

4. 權值歸一化跳出循環輸出強分類器

Logit和Gentle算法的提出過程大致是這樣的

1. 驗證Boosting

algorithms是一種擬合一個additive logistic regression

model(加性的邏輯回歸模型)的階段式估計過程。它有最優一個指數判據,這個判據由第二定理與二項式對數似然判據是等價的。

2. 作者證明Discrete是使用adaptive Newton updates擬合一個additive logistic regression

model來最小化Ee^(-yF(x))的過程，其中F(x)=求和fm(x),而fm(x)就是各層分類器的結果。

3. 作者證明Real是使用層級最優的方法來擬合一個additive logistic regression model.

4. 作者說明了為什么要選擇Ee^(-yF(x))作為目標:因為大家都用這個

5. 作者證明了當(blabla一個很復雜的公式，貼不出來)時Ee^(-yF(x))最小

6. 作者證明了每次權值更新以后,最近一次訓練出的弱分類器錯誤率為50%.

7. 作者證明了對于最優的F(x),樣本的分類乘以權值的和應該為0.

于是作者用80年代興起的邏輯回歸的尋優方法中提煉出了LogitBoost(我終于找到logitBoost的logic了)

logitBoost

自適應的牛頓法,擬合加性logistic回歸模型1. 獲得樣本,(x,y)序列.將分類y*=(y+1)/2

2. 設置初值,F(x)=0,p(xi)=1/2進入循環1. 依式計算zi,wi.

2. 通過加權最小二乘的方式擬合函數fm(x).由zi擬合xi,權重為wi

3. 更新F(x),p(x) 退出循環輸出分類器sign[F(x)].作者提出,logitAdaBoost在每一輪中都使Ee^(-y(F(x)+f(x)))最優,會使訓練樣本的代表性下降,于是提出了Gentle

AdaBoost(牛頓步長法)

Gentle AdaBoost(matlab版)for It = 1 : Max_Iter

nodes =

train(WeakLrn, Data, Labels, distr);

for i =

1:length(nodes)

curr_tr = nodes{i};

step_out = calc_output(curr_tr, Data);

s1 = sum( (Labels == 1) .* (step_out) .*

distr);

s2 = sum( (Labels == -1) .* (step_out) .* distr);

if(s1 == 0 && s2 == 0)

continue;

end

Alpha = (s1 - s2) / (s1 + s2);%注意alpha的不同Alpha =

0.5*log((s1 + eps) / (s2+eps));real版

Weights(end+1) = Alpha;

Learners{end+1} = curr_tr;

final_hyp = final_hyp + step_out .* Alpha;

end

Z = sum(abs(Labels .*

final_hyp));

if(Z == 0)

Z = 1;

end

distr = exp(- 1 *

(Labels .* final_hyp) / Z);

Z =

sum(distr);

distr = distr /

Z;

end

ModestAdaBoost

for i = 1:length(nodes)

curr_tr = nodes{i};

step_out = calc_output(curr_tr, Data);

s1 = sum( (Labels == 1) .* (step_out) .*

distr);

s2 = sum( (Labels == -1) .* (step_out) .* distr);

s1_rev = sum( (Labels == 1) .* (step_out) .*

rev_distr);

s2_rev = sum( (Labels == -1) .* (step_out) .*

rev_distr);

Alpha = s1 * (1 - s1_rev) - s2 * (1 -

s2_rev);

其中的fm即為alpha

AdaBoost算法針對不同的訓練集訓練同一個基本分類器(弱分類器)，然后把這些在不同訓練集上得到的分類器集合起來，構成一個更強的最終的分類器(強分類器)。理論證明，只要每個弱分類器分類能力比隨機猜測要好，當其個數趨向于無窮個數時，強分類器的錯誤率將趨向于零。

AdaBoost算法中不同的訓練集是通過調整每個樣本對應的權重實現的。最開始的時候，每個樣本對應的權重是相同的，在此樣本分布下訓練出一個基本分類器h1(x)。對于h1(x)錯分的樣本，則增加其對應樣本的權重；而對于正確分類的樣本，則降低其權重。這樣可以使得錯分的樣本突出出來，并得到一個新的樣本分布。同時，根據錯分的情況賦予h1(x)一個權重，表示該基本分類器的重要程度，錯分得越少權重越大。在新的樣本分布下，再次對基本分類器進行訓練，得到基本分類器h2(x)及其權重。依次類推，經過T次這樣的循環，就得到了T個基本分類器，以及T個對應的權重。最后把這T個基本分類器按一定權重累加起來，就得到了最終所期望的強分類器。

一些改進的算法

1、級聯ad

一種改進的AdaBoost算法——AD_AdaBoost。Viola提出的級聯結構的分類器是指一組

串行的分類器。在對待識樣本進行分類時，只有被前面一級的分類器判決為正的樣本才被送入后面的分類器繼續處理，反之則被認為是負樣本直接輸出。最后，只有那些被每一級的分類器都判決為正的樣本才作為正樣本輸出。在級聯結構的分類器中，Viola和jones采用

Ad aBoost 算法來對每一級的分類器進行訓練。

2、一種用于不平衡數據分類的改進

Ad a B o o s t

算法

3、基于雙閾值的增強型AdaBoost_快速算法

總結

以上是生活随笔為你收集整理的adaboost mh matlab,Adaboost算法的前世今生的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。