介紹boosting算法的資源：

1. 視頻講義,，介紹boosting算法，主要介紹AdaBoosing http:///mlss05us_schapire_b/

2. 在這個網(wǎng)站的資源項里列出了對于boosting算法來源介紹的幾篇文章,，可以下載： http://www./tutorials

3. 一個博客介紹了許多視覺中常用算法,，作者的實驗和理解，這里附錄的鏈接是關(guān)于使用opencv進行人臉檢測的過程和代碼,，可以幫助理解訓練過程是如何完成的：

4. 這里是一個臺灣的電子期刊上關(guān)于AdaBoost的介紹: http://140.113.87.114/cvrc/edm/vol_6/tech1.htm

1 Jackknife,，Bootstraping, bagging, boosting, AdaBoosting, Rand forest 和 gradient boosting

這些術(shù)語，我經(jīng)常搞混淆,，現(xiàn)在把它們放在一起,，以示區(qū)別。(部分文字來自網(wǎng)絡(luò),，由于是之前記的筆記,，忘記來源了，特此向作者抱歉）

Bootstraping: 名字來自成語“pull up by your own bootstraps”,，意思是依靠你自己的資源,，稱為自助法,，它是一種有放回的抽樣方法，它是非參數(shù)統(tǒng)計中一種重要的估計統(tǒng)計量方差進而進行區(qū)間估計的統(tǒng)計方法,。其核心思想和基本步驟如下：

（1） 采用重抽樣技術(shù)從原始樣本中抽取一定數(shù)量（自己給定）的樣本,，此過程允許重復(fù)抽樣。
（2） 根據(jù)抽出的樣本計算給定的統(tǒng)計量T,。
（3） 重復(fù)上述N次（一般大于1000）,，得到N個統(tǒng)計量T。
（4） 計算上述N個統(tǒng)計量T的樣本方差,，得到統(tǒng)計量的方差,。

應(yīng)該說Bootstrap是現(xiàn)代統(tǒng)計學較為流行的一種統(tǒng)計方法，在小樣本時效果很好,。通過方差的估計可以構(gòu)造置信區(qū)間等,，其運用范圍得到進一步延伸。

Jackknife： 和上面要介紹的Bootstrap功能類似,，只是有一點細節(jié)不一樣,，即每次從樣本中抽樣時候只是去除幾個樣本（而不是抽樣），就像小刀一樣割去一部分,。

==============================================================

下列方法都是上述Bootstraping思想的一種應(yīng)用,。

bagging：bootstrap aggregating的縮寫。讓該學習算法訓練多輪,，每輪的訓練集由從初始的訓練集中隨機取出的n個訓練樣本組成,，某個初始訓練樣本在某輪訓練集中可以出現(xiàn)多次或根本不出現(xiàn)，訓練之后可得到一個預(yù)測函數(shù)序列h_1,，? ?h_n ,，最終的預(yù)測函數(shù)H對分類問題采用投票方式，對回歸問題采用簡單平均方法對新示例進行判別,。

[訓練R個分類器f_i,，分類器之間其他相同就是參數(shù)不同。其中f_i是通過從訓練集合中(N篇文檔)隨機取(取后放回)N次文檔構(gòu)成的訓練集合訓練得到的,。對于新文檔d,，用這R個分類器去分類，得到的最多的那個類別作為d的最終類別,。]

boosting: 其中主要的是AdaBoost（Adaptive Boosting）,。初始化時對每一個訓練例賦相等的權(quán)重1／n，然后用該學算法對訓練集訓練t輪,，每次訓練后，對訓練失敗的訓練例賦以較大的權(quán)重,，也就是讓學習算法在后續(xù)的學習中集中對比較難的訓練例進行學習,，從而得到一個預(yù)測函數(shù)序列h_1,?, h_m , 其中h_i也有一定的權(quán)重,，預(yù)測效果好的預(yù)測函數(shù)權(quán)重較大，反之較小,。最終的預(yù)測函數(shù)H對分類問題采用有權(quán)重的投票方式,，對回歸問題采用加權(quán)平均的方法對新示例進行判別。
（類似Bagging方法,，但是訓練是串行進行的,，第k個分類器訓練時關(guān)注對前k-1分類器中錯分的文檔，即不是隨機取,，而是加大取這些文檔的概率,。)

Bagging與Boosting的區(qū)別：二者的主要區(qū)別是取樣方式不同。Bagging采用均勻取樣,，而Boosting根據(jù)錯誤率來取樣,，因此Boosting的分類精度要優(yōu)于Bagging。Bagging的訓練集的選擇是隨機的,，各輪訓練集之間相互獨立,，而Boostlng的各輪訓練集的選擇與前面各輪的學習結(jié)果有關(guān)；Bagging的各個預(yù)測函數(shù)沒有權(quán)重,，而Boosting是有權(quán)重的,；Bagging的各個預(yù)測函數(shù)可以并行生成，而Boosting的各個預(yù)測函數(shù)只能順序生成,。對于象神經(jīng)網(wǎng)絡(luò)這樣極為耗時的學習方法,。Bagging可通過并行訓練節(jié)省大量時間開銷。
bagging和boosting都可以有效地提高分類的準確性,。在大多數(shù)數(shù)據(jù)集中,，boosting的準確性比bagging高。在有些數(shù)據(jù)集中,，boosting會引起退化— Overfit,。
Boosting思想的一種改進型AdaBoost方法在郵件過濾、文本分類方面都有很好的性能,。

gradient boosting（又叫Mart, Treenet)：Boosting是一種思想,，Gradient Boosting是一種實現(xiàn)Boosting的方法，它主要的思想是,，每一次建立模型是在之前建立模型損失函數(shù)的梯度下降方向,。損失函數(shù)(loss function)描述的是模型的不靠譜程度，損失函數(shù)越大,，則說明模型越容易出錯,。如果我們的模型能夠讓損失函數(shù)持續(xù)的下降，則說明我們的模型在不停的改進,，而最好的方式就是讓損失函數(shù)在其梯度（Gradient)的方向上下降,。

Rand forest： 隨機森林,，顧名思義，是用隨機的方式建立一個森林,，森林里面有很多的決策樹組成,，隨機森林的每一棵決策樹之間是沒有關(guān)聯(lián)的。在得到森林之后,，當有一個新的輸入樣本進入的時候,，就讓森林中的每一棵決策樹分別進行一下判斷，看看這個樣本應(yīng)該屬于哪一類（對于分類算法）,，然后看看哪一類被選擇最多,，就預(yù)測這個樣本為那一類。 在建立每一棵決策樹的過程中,，有兩點需要注意 – 采樣與完全分裂,。首先是兩個隨機采樣的過程，random forest對輸入的數(shù)據(jù)要進行行,、列的采樣,。對于行采樣，采用有放回的方式,，也就是在采樣得到的樣本集合中,，可能有重復(fù)的樣本。假設(shè)輸入樣本為N個,，那么采樣的樣本也為N個,。這樣使得在訓練的時候，每一棵樹的輸入樣本都不是全部的樣本,，使得相對不容易出現(xiàn)over-fitting,。然后進行列采樣，從M個feature中,，選擇m個(m << M),。之后就是對采樣之后的數(shù)據(jù)使用完全分裂的方式建立出決策樹，這樣決策樹的某一個葉子節(jié)點要么是無法繼續(xù)分裂的,，要么里面的所有樣本的都是指向的同一個分類,。一般很多的決策樹算法都一個重要的步驟 – 剪枝，但是這里不這樣干,，由于之前的兩個隨機采樣的過程保證了隨機性,，所以就算不剪枝，也不會出現(xiàn)over-fitting,。 按這種算法得到的隨機森林中的每一棵都是很弱的,，但是大家組合起來就很厲害了。可以這樣比喻隨機森林算法：每一棵決策樹就是一個精通于某一個窄領(lǐng)域的專家（因為我們從M個feature中選擇m讓每一棵決策樹進行學習）,，這樣在隨機森林中就有了很多個精通不同領(lǐng)域的專家,，對一個新的問題（新的輸入數(shù)據(jù)），可以用不同的角度去看待它,，最終由各個專家，投票得到結(jié)果,。

Rand forest與bagging的區(qū)別：
1）Rand forest是選與輸入樣本的數(shù)目相同多的次數(shù)（可能一個樣本會被選取多次,，同時也會造成一些樣本不會被選取到），而bagging一般選取比輸入樣本的數(shù)目少的樣本,；
2）bagging是用全部特征來得到分類器,，而rand forest是需要從全部特征中選取其中的一部分來訓練得到分類器； 一般Rand forest效果比bagging效果好,！

2 bootstrps bagging boosting

bootstrps bagging boosting這幾個概念經(jīng)常用到,，現(xiàn)仔細學習了一下：
他們都屬于集成學習方法，(如：Bagging,，Boosting,，Stacking)，將訓練的學習器集成在一起,原理來源于PAC學習模型（ProbablyApproximately CorrectK）,。Kearns和Valiant指出,，在PAC學習模型中，若存在一個多項式級的學習算法來識別一組概念,，并且識別正確率很高,，那么這組概念是強可學習的；而如果學習算法識別一組概念的正確率僅比隨機猜測略好,，那么這組概念是弱可學習的,。他們提出了弱學習算法與強學習算法的等價性問題，即是否可以將弱學習算法提升成強學習算法,。如果兩者等價,，那么在學習概念時，只要找到一個比隨機猜測略好的弱學習算法,，就可以將其提升為強學習算法,，而不必直接去找通常情況下很難獲得的強學習算法。

bootstraps:名字來自成語“pull up by your ownbootstraps”,，意思是依靠你自己的資源,，它是一種有放回的抽樣方法，學習中還發(fā)現(xiàn)有種叫jackknife的方法,，它是每一次移除一個樣本,。

bagging:bootstrapaggregating的縮寫。讓該學習算法訓練多輪，每輪的訓練集由從初始的訓練集中隨機取出的n個訓練倒組成,，初始訓練例在某輪訓練集中可以出現(xiàn)多次或根本不出現(xiàn)訓練之后可得到一個預(yù)測函數(shù)序列h．,，??h 最終的預(yù)測函數(shù)H對分類問題采用投票方式，對回歸問題采用簡單平均方法對新示例進行判別,。
–(訓練R個分類器fi,，分類器之間其他相同就是參數(shù)不同。其中fi是通過從訓練集合中(N篇文檔)隨機取(取后放回)N次文檔構(gòu)成的訓練集合訓練得到的,。–對于新文檔d,，用這R個分類器去分類，得到的最多的那個類別作為d的最終類別.)

boosting:其中主要的是AdaBoost（Adaptive Boosting）,。初始化時對每一個訓練例賦相等的權(quán)重1／n,，然后用該學算法對訓練集訓練t輪，每次訓練后,，對訓練失敗的訓練例賦以較大的權(quán)重,，也就是讓學習算法在后續(xù)的學習中集中對比較難的訓練鍘進行學習，從而得到一個預(yù)測函數(shù)序列h一?h其中h．也有一定的權(quán)重,，預(yù)測效果好的預(yù)測函數(shù)權(quán)重較大,，反之較小。最終的預(yù)測函數(shù)H對分類問題采用有權(quán)重的投票方式,，對回歸問題采用加權(quán)平均的方法對新示例進行判別,。(類似Bagging方法，但是訓練是串行進行的,，第k個分類器訓練時關(guān)注對前k-1分類器中錯分的文檔,，即不是隨機取，而是加大取這些文檔的概率).

Bagging與Boosting的區(qū)別：在于Bagging的訓練集的選擇是隨機的,，各輪訓練集之間相互獨立,，而Boostlng的訓練集的選擇是獨立的，各輪訓練集的選擇與前面各輪的學習結(jié)果有關(guān),；Bagging的各個預(yù)測函數(shù)沒有權(quán)重,，而Boosting是有權(quán)重的；Bagging的各個預(yù)測函數(shù)可以并行生成,，而Boosting的各個預(yù)測函數(shù)只能順序生成,。對于象神經(jīng)網(wǎng)絡(luò)這樣極為耗時的學習方法。Bagging可通過并行訓練節(jié)省大量時間開銷,?！　　?/p>

bagging和boosting都可以有效地提高分類的準確性。在大多數(shù)數(shù)據(jù)集中,，boosting的準確性比bagging高,。在有些數(shù)據(jù)集中，boosting會引起退化?！狾verfit

文本分類中使用的投票方法（Voting,，也叫組合分類器）就是一種典型的集成機器學習方法。它通過組合多個弱分類器來得到一個強分類器,，包括Bagging和Boosting兩種方式,，二者的主要區(qū)別是取樣方式不同。Bagging采用均勻取樣,，而Boosting根據(jù)錯誤率來取樣,，因此Boosting的分類精度要優(yōu)于Bagging。投票分類方法雖然分類精度較高,，但訓練時間較長。Boosting思想的一種改進型AdaBoost方法在郵件過濾,、文本分類方面都有很好的性能,。

參考文獻：
1. http://blog.sina.com.cn/s/blog_5dd2e9270100c8ko.html
2.
3. http://www./1200532.html