Boosting原理及在分類(lèi)上的應(yīng)用

Boosting原理及在分類(lèi)上的應(yīng)用電子工程系劉輝2002年12月9日Boosting原理及在分類(lèi)上的應(yīng)用共32頁(yè)，您現(xiàn)在瀏覽的是第1頁(yè)!Outline背景Boosting原理Boosting算法Boosting應(yīng)用總結(jié)Boosting原理及在分類(lèi)上的應(yīng)用共32頁(yè)，您現(xiàn)在瀏覽的是第2頁(yè)!背景游戲理論（Gametheory）

R P S 錘子布剪子

錘子 ? 10布 0 ?1 剪子 1 0 ? 游戲者1（rowplayer)： RSPPSRS…（損失最小化） 游戲者2（columnplayer）：SRRPSRP…（損失最大化）Boosting原理及在分類(lèi)上的應(yīng)用共32頁(yè)，您現(xiàn)在瀏覽的是第3頁(yè)!背景Boosting思想源于三個(gè)臭皮匠，勝過(guò)諸葛亮

Findingmanyroughrulesofthumbcanbealoteasierandmoreeffectivethanfindingasingle,highlypredictionrule.Boosting原理及在分類(lèi)上的應(yīng)用共32頁(yè)，您現(xiàn)在瀏覽的是第4頁(yè)!原理引入AperfectexpertRealityCNN(Perfect!)ABCCBSXXXBoosting原理及在分類(lèi)上的應(yīng)用共32頁(yè)，您現(xiàn)在瀏覽的是第5頁(yè)!原理引入MONTUEWEDTHUREALITYMAJORITYCNNABCCBSFOXTOTAL32/828/826/815/837/4XXXXXXX11111/211111/41/211/41/21/8121XXBoosting原理及在分類(lèi)上的應(yīng)用共32頁(yè)，您現(xiàn)在瀏覽的是第6頁(yè)!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原理及在分類(lèi)上的應(yīng)用共32頁(yè)，您現(xiàn)在瀏覽的是第7頁(yè)!Boosting流程(loop1)強(qiáng)學(xué)習(xí)機(jī)弱學(xué)習(xí)機(jī)原始訓(xùn)練集加權(quán)后的訓(xùn)練集加權(quán)后的假設(shè)X>1?1:-1弱假設(shè)Boosting原理及在分類(lèi)上的應(yīng)用共32頁(yè)，您現(xiàn)在瀏覽的是第8頁(yè)!Boosting流程(loop3)強(qiáng)學(xué)習(xí)機(jī)弱學(xué)習(xí)機(jī)原始訓(xùn)練集加權(quán)后的訓(xùn)練集加權(quán)后的假設(shè)Z>7?1:-1弱假設(shè)Boosting原理及在分類(lèi)上的應(yīng)用共32頁(yè)，您現(xiàn)在瀏覽的是第9頁(yè)!核心思想樣本的權(quán)重沒(méi)有先驗(yàn)知識(shí)的情況下，初始的分布應(yīng)為等概分布，也就是訓(xùn)練集如果有N個(gè)樣本，每個(gè)樣本的分布概率為1/N每次循環(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ù)值減小。Boosting原理及在分類(lèi)上的應(yīng)用共32頁(yè)，您現(xiàn)在瀏覽的是第10頁(yè)!算法—問(wèn)題描述訓(xùn)練集{(x1,y1),(x2,y2),…,(xN,yN)}xiRm,yi{-1,+1}Dt

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

為t次循環(huán)得到的StronglearnerBoosting原理及在分類(lèi)上的應(yīng)用共32頁(yè)，您現(xiàn)在瀏覽的是第11頁(yè)!算法—弱學(xué)習(xí)機(jī)權(quán)重思想：錯(cuò)誤率越低，該學(xué)習(xí)機(jī)的權(quán)重應(yīng)該越大為學(xué)習(xí)機(jī)的錯(cuò)誤概率采用什么樣的函數(shù)形式？

和指數(shù)函數(shù)遙相呼應(yīng)：Boosting原理及在分類(lèi)上的應(yīng)用共32頁(yè)，您現(xiàn)在瀏覽的是第12頁(yè)!理論分析--最優(yōu)化如何求弱學(xué)習(xí)機(jī)的權(quán)重？最基本的損失函數(shù)表達(dá)形式為了便于計(jì)算，采用以下的目標(biāo)函數(shù)Boosting的循環(huán)過(guò)程就是沿著損失函數(shù)的負(fù)梯度方向進(jìn)行最優(yōu)化的過(guò)程。通過(guò)調(diào)整樣本的分布Dt和選擇弱學(xué)習(xí)機(jī)的權(quán)重wt來(lái)達(dá)到這個(gè)目的。每循環(huán)一次，增加一項(xiàng)，使損失函數(shù)以最快速度下降。Boosting原理及在分類(lèi)上的應(yīng)用共32頁(yè)，您現(xiàn)在瀏覽的是第13頁(yè)!理論分析—熵映射相對(duì)熵原理（最小鑒別信息原理）

已知隨機(jī)變量X（樣本集）的先驗(yàn)分布（Dt），并且已知所求未知分布Dt+1滿足條件(Dt+1*Ut=0)，那么所求得的未知分布估計(jì)值具有如下形式：

物理意義：在只掌握部分信息的情況下要對(duì)分布作出判斷時(shí)，應(yīng)該選取符合約束條件但熵值取得最大的概率分布。從先驗(yàn)分布到未知分布的計(jì)算應(yīng)該取滿足已知條件，不確定度（熵）變化最小的解。Boosting原理及在分類(lèi)上的應(yīng)用共32頁(yè)，您現(xiàn)在瀏覽的是第14頁(yè)!應(yīng)用—人臉識(shí)別Boosting原理及在分類(lèi)上的應(yīng)用共32頁(yè)，您現(xiàn)在瀏覽的是第15頁(yè)!應(yīng)用—文本分類(lèi)Boosting原理及在分類(lèi)上的應(yīng)用共32頁(yè)，您現(xiàn)在瀏覽的是第16頁(yè)!參考資料Internet站點(diǎn).

mathworld.wolfram.

推薦論文ABriefIntroductiontoBoostingExperimentswithaNewBoostingAlgorithmAdditiveLogisticRegression:aStatisticalViewofBoostingTheBoostingApproachtoMachineLearning:anoverviewGameTheory,On-linePredictionandBoostingBoostingasEntropyProjectionLogisticRegression,AdaBoostandBregmanDistances以上論文均可在.下載Boosting原理及在分類(lèi)上的應(yīng)用共32頁(yè)，您現(xiàn)在瀏覽的是第17頁(yè)!背景在線學(xué)習(xí)（On-linelearning)

馬以往的表現(xiàn) 馬當(dāng)前的狀態(tài) 馬的主人 場(chǎng)地安排

……..

以上種種因素，如何綜合考慮？選哪個(gè)呢？Boosting原理及在分類(lèi)上的應(yīng)用共32頁(yè)，您現(xiàn)在瀏覽的是第18頁(yè)!原理引入天氣預(yù)報(bào) 預(yù)測(cè)明天是晴是雨？ 傳統(tǒng)觀念：依賴于專(zhuān)家系統(tǒng)（AperfectExpert)Boosting原理及在分類(lèi)上的應(yīng)用共32頁(yè)，您現(xiàn)在瀏覽的是第19頁(yè)!原理引入Boosting：basedon“Nobodyisperfect”，binemonreportertoobtainperfectexpert更加符合自然界的現(xiàn)實(shí)CNNABCCBSRealityXXXXXBoosting原理及在分類(lèi)上的應(yīng)用共32頁(yè)，您現(xiàn)在瀏覽的是第20頁(yè)!Boosting—concepts(1)機(jī)器學(xué)習(xí)（MachineLearning)：將一些已知的并已被成功解決的問(wèn)題作為范例輸入計(jì)算機(jī),機(jī)器通過(guò)學(xué)習(xí)這些范例總結(jié)并生成相應(yīng)的規(guī)則,這些規(guī)則具有通用性,使用它們可以解決某一類(lèi)的問(wèn)題。

人臉識(shí)別文本分類(lèi)網(wǎng)絡(luò)安全生物信息工程學(xué)習(xí)機(jī)（learner)：機(jī)器學(xué)習(xí)得到的規(guī)則或者模型。樣本：所研究問(wèn)題的實(shí)例，一般在訓(xùn)練集中包括正樣本和負(fù)樣本。

一張人臉圖像，一篇文章，一個(gè)病毒代碼，一個(gè)生物的遺傳編碼訓(xùn)練：采用某種方法，用已知屬性的樣本作為輸入，得到相應(yīng)規(guī)則的過(guò)程。訓(xùn)練集：由已知屬性的樣本組成的集合，作為訓(xùn)練過(guò)程的輸入數(shù)據(jù)。測(cè)試集：由已知屬性的樣本組成的集合，作為測(cè)試過(guò)程的輸入數(shù)據(jù)。假設(shè)：學(xué)習(xí)機(jī)對(duì)樣本做出的判斷，即是否符合需要判定的事實(shí)。

某張臉是否是張三的，某篇文章是否屬于新聞?lì)悇eBoosting原理及在分類(lèi)上的應(yīng)用共32頁(yè)，您現(xiàn)在瀏覽的是第21頁(yè)!Boosting—concepts(3)弱學(xué)習(xí)機(jī)（weaklearner):對(duì)一定分布的訓(xùn)練樣本給出假設(shè)（僅僅強(qiáng)于隨機(jī)猜測(cè)）

根據(jù)有云猜測(cè)可能會(huì)下雨強(qiáng)學(xué)習(xí)機(jī)（stronglearner):根據(jù)得到的弱學(xué)習(xí)機(jī)和相應(yīng)的權(quán)重給出假設(shè)（最大程度上符合實(shí)際情況：almostperfectexpert)

根據(jù)CNN,ABC,CBS以往的預(yù)測(cè)表現(xiàn)及實(shí)際天氣情況作出綜合準(zhǔn)確的天氣預(yù)測(cè)弱學(xué)習(xí)機(jī)強(qiáng)學(xué)習(xí)機(jī)BoostingBoosting原理及在分類(lèi)上的應(yīng)用共32頁(yè)，您現(xiàn)在瀏覽的是第22頁(yè)!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原理及在分類(lèi)上的應(yīng)用共32頁(yè)，您現(xiàn)在瀏覽的是第23頁(yè)!流程描述Step1:原始訓(xùn)練集輸入，帶有原始分布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ī)Boosting原理及在分類(lèi)上的應(yīng)用共32頁(yè)，您現(xiàn)在瀏覽的是第24頁(yè)!簡(jiǎn)單問(wèn)題演示（Boosting訓(xùn)練過(guò)程）Boosting原理及在分類(lèi)上的應(yīng)用共32頁(yè)，您現(xiàn)在瀏覽的是第25頁(yè)!算法—樣本權(quán)重思想：提高分錯(cuò)樣本的權(quán)重反映了stronglearner對(duì)樣本的假設(shè)是否正確采用什么樣的函數(shù)形式？

Boosting原理及在分類(lèi)上的應(yīng)用共32頁(yè)，您現(xiàn)在瀏覽的是第26頁(yè)!算法--AdaboostBoosting原理及在分類(lèi)上的應(yīng)用共32頁(yè)，您現(xiàn)在瀏覽的是第27頁(yè)!理論分析—熵映射給定當(dāng)前分布和選定的弱學(xué)習(xí)機(jī)，如何求下一次的分布？

Boosting的設(shè)計(jì)思想：改變分布，提高錯(cuò)誤樣本概率，使下一次的弱學(xué)習(xí)機(jī)能夠集中精力針對(duì)那些困難樣本。調(diào)整分布后的訓(xùn)練集對(duì)當(dāng)前學(xué)習(xí)機(jī)具有最大的隨機(jī)性，正確率50%（恰好為隨機(jī)猜測(cè)）

Boosting原理及在分類(lèi)上的應(yīng)用共32頁(yè)，您現(xiàn)在瀏覽的是第28頁(yè)!應(yīng)用—人臉識(shí)別Boosting原理及在分類(lèi)上的應(yīng)用共32頁(yè)，您現(xiàn)在瀏覽的是第29頁(yè)!應(yīng)用—文本分類(lèi)Boosting原理及在分類(lèi)上的應(yīng)用共32頁(yè)，您現(xiàn)在瀏