1、Boosting and bagging算法,1 Boosting 算法,Boosting 算法是近十年最有效的算法之一，其主要代表算法有Adaboost算法和 AdaBoost算法改進等。（記單詞） AdaBoost算法基本思想： 對同一個訓練集使用不同的特征訓練出不同的弱分類器 ， 然后將這些弱分類器組合起來 ， 提升為一個分類能力更強的強分類器 。 算法是通過數(shù)據(jù)分布的改變來實現(xiàn)的，根據(jù)每次弱分類器訓練集中每個樣本的分類正確與否，及上次總體分類的準確率，對每個樣本的權(quán)值進行調(diào)整，降低弱分類器中分類正確的樣本的權(quán)值，提高弱分類器分類錯誤的樣本的權(quán)值。修改過權(quán)值的新數(shù)據(jù)表集作為下層分類器的訓

2、練集，經(jīng)過多次迭代得到相應(yīng)的弱分類器，對訓練得到的這些弱分類器進行融合 ， 得到最終的強分類器 。,1.1 AdaBoost系列,應(yīng)用AdaBoost系列主要解決了：兩類問題、多類單標簽問題、多類多標簽問題、大類單標簽問題，回歸問題。它用全部的訓練樣本進行學習。 注：一般無特別說明，boosting都是指AdaBoost算法,The AdaBoost算法,圖像,正樣本 =1 負樣本=-1,Step 1: 訓練集,Step 2: 初始化權(quán)值,For t = 1, , T 1. 歸一化權(quán)值, 2. 對于第j個特征,在給定權(quán)值條件下訓練弱分類器 hj ，弱分類器的分類錯誤率為： 3. 更新權(quán)值: E

3、nd 最終的強分類器：,AdaBoost 人臉檢測,原始圖像,特征提取,Haar Basis Functions,Haar Basis Functions,Haar Basis Functions,特征計算,Ada Boost 訓練,特征選擇,大量的特征,小部分特征訓練,級聯(lián)結(jié)構(gòu),AdaBoost 學習算法 用于特征選擇,AdaBoost 應(yīng)用于分類,學習處理,特征集,訓練集 +1 正樣本 -1 負樣本,各種各樣的特征,人臉,非人臉,最終的強分類器,大約有180,000 個矩形特征,24,24,弱分類器訓練圖示說明,X (訓練集),ex,臉部圖像,非臉部圖像,如果 fj(x) X 是臉部圖像,

4、訓練集,弱分類器訓練 圖示說明,特征,每幅圖像大約有180,000 個特征,歸一化權(quán)重,級聯(lián) AdaBoost,AdaBoost,特征集,Feature Select & Classifier,1,False,非人臉,100% Detection Rate 50% False Positive,離散AdaBoost-AdaBoost.M1,AdaBoost.M1 和 AdaBoost.M2 是用來解決多分類單標簽問題,AdaBoost.M1算法,Step 1: 訓練集,Step 2: 初始化權(quán)值,For t = 1, , T 1. 歸一化權(quán)值, 2. 對于第j個特征,在給定權(quán)值條件下訓練若分類

5、器 hj ，若分類器的分類錯誤率為： 3. 更新權(quán)值: End 最終的強分類器：,Floatboost 算法,向前增加一個弱分類器之后，就需要向后回饋r。r的取值取決于當前分類性能的穩(wěn)定性。這種弱分類器選擇的方法相對于前向搜索來說具有更大的靈活性，因此，增加弱分類器組合的多樣性，相比AdaBoost中的單調(diào)搜索有更優(yōu)的解集合。,The AdaBoost算法,圖像,正樣本 =1 負樣本=-1,Step 1: 訓練集,Step 2: 初始化權(quán)值,For t = 1, , T 1. 每個弱分類器h,在權(quán)值下進行訓練，得到預測函數(shù) ht . 2. 計算誤判率，選取參數(shù)at： 3. 更新權(quán)值: 4. 最

6、終的預測函數(shù)：,Step 3: 弱分類器訓練,2 bagging算法,Bagging算法的主要思想： 給定訓練集 和弱學習算法，對該學習算法進行T次調(diào)用，每次調(diào)用時只使用訓練集S中的某個子集作為當前訓練集，每一個訓練例在某輪訓練集中可以多次或根本不出現(xiàn)。經(jīng)過T次調(diào)用后，可得到T個不同的分類器啊，當對于一個測試實例工進行分類時，分別調(diào)用這T個分類器，得到T個分類結(jié)果。最后對分類問題把這T個分類結(jié)果中出現(xiàn)次數(shù)多的類賦予測試實例x。,Bagging算法,Step 1: 訓練,Step 2: 初始化權(quán)值,For t = 1, , T 1. S 為從給定訓練集S中，隨機抽樣（有放回）. 2. 在S 上訓練弱學習器，得到第t 輪的預測函數(shù) ht . 3. t = t + 1 . End 最終輸出： 對未知樣本X分類時，每個模型 ht 得到一個分類器， 得票最高的未知樣本x 的分類,Bagging 和 AdaBoost 區(qū)別,Bagging的訓練集是隨機的，各訓練集是獨的，而Boosting訓練集的選擇不是獨立的，每一次選擇的訓練集都依賴于上一次學習的結(jié)果。 Bagging的每個預測函數(shù)(即弱假設(shè))沒有權(quán)重，而Boosting