boosting原理及主要應(yīng)用

1、Boosting原理及在分類上的應(yīng)用,,Outline,背景Boosting原理Boosting算法Boosting應(yīng)用總結(jié),背景,游戲理論（Game theory）R P S錘子 布 剪子錘子½ 1 0 布0 ½ 1剪子 1 0 ½ 游戲者1（row player)：

2、RSPPSRS… （損失最小化）游戲者2（column player）： SRRPSRP… （損失最大化）,背景,在線學(xué)習(xí)（On-line learning) 馬以往的表現(xiàn)馬當(dāng)前的狀態(tài)馬的主人場(chǎng)地安排……..以上種種因素，如何綜合考慮？,? ??? ?? ?? ??? ?? ??? ???.^^,背景,Boosting思想源于三個(gè)臭皮匠，勝過諸葛

3、亮Finding many rough rules of thumb can be a lot easier and more effective than finding a single, highly prediction rule.,原理引入,天氣預(yù)報(bào)預(yù)測(cè)明天是晴是雨？傳統(tǒng)觀念：依賴于專家系統(tǒng)（A perfect Expert),原理引入,A perfect expert,X,X,X,原理引入,Boo

4、sting：based on “Nobody is perfect”，combine common reporter to obtain perfect expert更加符合自然界的現(xiàn)實(shí),原理引入,3,7/4,X,X,2,1,X,X,Boosting—concepts(1),機(jī)器學(xué)習(xí)（Machine Learning)：將一些已知的并已被成功解決的問題作為范例輸入計(jì)算機(jī),機(jī)器通過學(xué)習(xí)這些范例總結(jié)并生成相應(yīng)的規(guī)則,這些規(guī)

5、則具有通用性,使用它們可以解決某一類的問題 。人臉識(shí)別 文本分類 網(wǎng)絡(luò)安全 生物信息工程學(xué)習(xí)機(jī)（learner)：機(jī)器學(xué)習(xí)得到的規(guī)則或者模型。樣本：所研究問題的實(shí)例一張人臉圖像，一篇文章，一個(gè)病毒代碼，一個(gè)生物的遺傳編碼訓(xùn)練：采用某種方法，用已知屬性的樣本作為輸入，得到相應(yīng)規(guī)則的過程。訓(xùn)練集：由已知屬性的樣本組成的集合，作為訓(xùn)練過程的輸入數(shù)據(jù)。測(cè)試集：由已知屬性的樣本組成的集合，作為測(cè)試過程的輸入數(shù)據(jù)。假

6、設(shè)：學(xué)習(xí)機(jī)對(duì)樣本做出的判斷，即是否符合需要判定的事實(shí)。 某張臉是否是張三的，某篇文章是否屬于新聞?lì)悇e,Boosting—concepts(2),特征選?。簭膶?shí)際數(shù)據(jù)中抽取反映其本質(zhì)規(guī)律的屬性。 人臉圖像向量做PCA變換得到特征向量的投影系數(shù) 對(duì)文本進(jìn)行語(yǔ)法分析后表示成關(guān)于詞的特征向量機(jī)器學(xué)習(xí)系統(tǒng)結(jié)構(gòu)表示,Boosting—concepts(3),弱學(xué)習(xí)機(jī)（weak learner): 對(duì)一定分布的訓(xùn)練樣

7、本給出弱假設(shè)（僅僅強(qiáng)于隨機(jī)猜測(cè)）根據(jù)有云猜測(cè)可能會(huì)下雨強(qiáng)學(xué)習(xí)機(jī)（strong learner): 根據(jù)得到的弱學(xué)習(xí)機(jī)和相應(yīng)的權(quán)重給出強(qiáng)假設(shè)（最大程度上符合實(shí)際情況：almost perfect expert)根據(jù)CNN,ABC,CBS以往的預(yù)測(cè)表現(xiàn)及實(shí)際天氣情況作出綜合準(zhǔn)確的天氣預(yù)測(cè)弱學(xué)習(xí)機(jī) 強(qiáng)學(xué)習(xí)機(jī),Boosting流程(loop1),強(qiáng)學(xué)

8、習(xí)機(jī),弱學(xué)習(xí)機(jī),,,,原始訓(xùn)練集,加權(quán)后的訓(xùn)練集,,,,,加權(quán)后的假設(shè),X>1?1:-1,弱假設(shè),Boosting流程(loop2),強(qiáng)學(xué)習(xí)機(jī),弱學(xué)習(xí)機(jī),,,,原始訓(xùn)練集,加權(quán)后的訓(xùn)練集,,,,,加權(quán)后的假設(shè),Y>3?1:-1,弱假設(shè),,Boosting流程(loop3),強(qiáng)學(xué)習(xí)機(jī),弱學(xué)習(xí)機(jī),,,,原始訓(xùn)練集,加權(quán)后的訓(xùn)練集,,,,,加權(quán)后的假設(shè),Z>7?1:-1,弱假設(shè),,,流程描述,Step1: 原始訓(xùn)練集輸入，帶

9、有原始分布Step2: 給出訓(xùn)練集中各樣本的權(quán)重Step3: 將改變分布后的訓(xùn)練集輸入已知的弱學(xué)習(xí)機(jī)，弱學(xué)習(xí)機(jī)對(duì)每個(gè)樣本給出假設(shè)Step4: 對(duì)此次的弱學(xué)習(xí)機(jī)給出權(quán)重Step5: 轉(zhuǎn)到Step2, 直到循環(huán)到達(dá)一定次數(shù)或者某度量標(biāo)準(zhǔn)符合要求Step6: 將弱學(xué)習(xí)機(jī)按其相應(yīng)的權(quán)重加權(quán)組合形成強(qiáng)學(xué)習(xí)機(jī),核心思想,樣本的權(quán)重沒有先驗(yàn)知識(shí)的情況下，初始的分布應(yīng)為等概分布，也就是訓(xùn)練集如果有N個(gè)樣本，每個(gè)樣本的分布概率為1/N每次循

10、環(huán)一后提高錯(cuò)誤樣本的分布概率，分錯(cuò)樣本在訓(xùn)練集中所占權(quán)重增大， 使得下一次循環(huán)的弱學(xué)習(xí)機(jī)能夠集中力量對(duì)這些錯(cuò)誤樣本進(jìn)行判斷。弱學(xué)習(xí)機(jī)的權(quán)重準(zhǔn)確率越高的弱學(xué)習(xí)機(jī)權(quán)重越高循環(huán)控制：損失函數(shù)達(dá)到最小在強(qiáng)學(xué)習(xí)機(jī)的組合中增加一個(gè)加權(quán)的弱學(xué)習(xí)機(jī)，使準(zhǔn)確率提高，損失函數(shù)值減小。,簡(jiǎn)單問題演示（Boosting訓(xùn)練過程）,算法—問題描述,訓(xùn)練集 { (x1,y1), (x2,y2),…, (xN,yN) }xi ?Rm, yi? {

11、-1,+1}Dt 為第t次循環(huán)時(shí)的訓(xùn)練樣本分布（每個(gè)樣本在訓(xùn)練集中所占的概率， Dt總和應(yīng)該為1）ht:X?{-1,+1} 為第t次循環(huán)時(shí)的Weak learner，對(duì)每個(gè)樣本給出相應(yīng)的假設(shè)，應(yīng)該滿足強(qiáng)于隨機(jī)猜測(cè)：wt為ht的權(quán)重 為t次循環(huán)得到的Strong learner,算法—樣本權(quán)重,思想：提高分錯(cuò)樣本的權(quán)重

12、 反映了strong learner對(duì)樣本的假設(shè)是否正確采用什么樣的函數(shù)形式？,算法—弱學(xué)習(xí)機(jī)權(quán)重,思想：錯(cuò)誤率越低，該學(xué)習(xí)機(jī)的權(quán)重應(yīng)該越大 為學(xué)習(xí)機(jī)的錯(cuò)誤概率采用什么樣的函數(shù)形式？ 和指數(shù)函數(shù)遙相呼應(yīng)：,算法--Adaboost,理論分析--最優(yōu)化,如何求弱學(xué)習(xí)機(jī)的權(quán)重？ 最基本的損失函數(shù)表

13、達(dá)形式為了便于計(jì)算，采用以下的目標(biāo)函數(shù)Boosting的循環(huán)過程就是沿著損失函數(shù)的負(fù)梯度方向進(jìn)行最優(yōu)化的過程。通過調(diào)整樣本的分布Dt和選擇弱學(xué)習(xí)機(jī)的權(quán)重wt來達(dá)到這個(gè)目的。每循環(huán)一次，增加一項(xiàng) ，使損失函數(shù)以最快速度下降。,理論分析—熵映射,給定當(dāng)前分布和選定的弱學(xué)習(xí)機(jī)，如何求下一次的分布？ Boosting的設(shè)計(jì)思想：改變分布，提高錯(cuò)誤樣本概率，使下一次的弱學(xué)習(xí)機(jī)能夠集中精力針對(duì)那些困難樣本。調(diào)整

14、分布后的訓(xùn)練集對(duì)當(dāng)前學(xué)習(xí)機(jī)具有最大的隨機(jī)性，正確率50%（恰好為隨機(jī)猜測(cè)）,理論分析—熵映射,相對(duì)熵原理（最小鑒別信息原理） 已知隨機(jī)變量X（樣本集）的先驗(yàn)分布（Dt），并且已知所求未知分布Dt+1滿足條件 ( Dt+1*Ut = 0 )，那么所求得的未知分布估計(jì)值具有如下形式： 物理意義：在只掌握部分信息的情況下要對(duì)分布作出判斷時(shí)，應(yīng)該選取符合約束條

15、件但熵值取得最大的概率分布。從先驗(yàn)分布到未知分布的計(jì)算應(yīng)該取滿足已知條件，不確定度（熵）變化最小的解。,應(yīng)用—人臉識(shí)別,應(yīng)用—人臉識(shí)別,應(yīng)用—文本分類,應(yīng)用—文本分類,總結(jié),Boosting的思想源泉：三個(gè)臭皮匠，勝過諸葛亮將一系列粗略的規(guī)則加權(quán)組合起來得到高度精確的規(guī)則。Boosting的數(shù)學(xué)實(shí)質(zhì)：對(duì)目標(biāo)函數(shù)（損失函數(shù)）的最優(yōu)化問題。損失函數(shù)形式不同，優(yōu)化方法不同Boosting的理論聯(lián)系：熵映射對(duì)數(shù)回歸Boosti

16、ng的應(yīng)用人臉識(shí)別文本分類,參考資料,Internet站點(diǎn)www.boosting.orghttp://mathworld.wolfram.com推薦論文A Brief Introduction to BoostingExperiments with a New Boosting AlgorithmAdditive Logistic Regression: a Statistical View of Boost

17、ingThe Boosting Approach to Machine Learning: an overviewGame Theory, On-line Prediction and BoostingBoosting as Entropy ProjectionLogistic Regression, AdaBoost and Bregman Distances以上論文均可在www.boosting.org下載,End ?,T