Boosting原理及在分類上的應用

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

R P S 錘子布剪子

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

Findingmanyroughrulesofthumbcanbealoteasierandmoreeffectivethanfindingasingle,highlypredictionrule.Boosting原理及在分類上的應用共32頁，您現(xiàn)在瀏覽的是第4頁!原理引入AperfectexpertRealityCNN(Perfect!)ABCCBSXXXBoosting原理及在分類上的應用共32頁，您現(xiàn)在瀏覽的是第5頁!原理引入MONTUEWEDTHUREALITYMAJORITYCNNABCCBSFOXTOTAL32/828/826/815/837/4XXXXXXX11111/211111/41/211/41/21/8121XXBoosting原理及在分類上的應用共32頁，您現(xiàn)在瀏覽的是第6頁!Boosting—concepts(2)特征選?。簭膶嶋H數(shù)據(jù)中抽取反映其本質(zhì)規(guī)律的屬性。

人臉圖像向量做PCA變換得到特征向量的投影系數(shù) 對文本進行語法分析后表示成關(guān)于詞的特征向量機器學習系統(tǒng)結(jié)構(gòu)表示Boosting原理及在分類上的應用共32頁，您現(xiàn)在瀏覽的是第7頁!Boosting流程(loop1)強學習機弱學習機原始訓練集加權(quán)后的訓練集加權(quán)后的假設(shè)X>1?1:-1弱假設(shè)Boosting原理及在分類上的應用共32頁，您現(xiàn)在瀏覽的是第8頁!Boosting流程(loop3)強學習機弱學習機原始訓練集加權(quán)后的訓練集加權(quán)后的假設(shè)Z>7?1:-1弱假設(shè)Boosting原理及在分類上的應用共32頁，您現(xiàn)在瀏覽的是第9頁!核心思想樣本的權(quán)重沒有先驗知識的情況下，初始的分布應為等概分布，也就是訓練集如果有N個樣本，每個樣本的分布概率為1/N每次循環(huán)一后提高錯誤樣本的分布概率，分錯樣本在訓練集中所占權(quán)重增大，使得下一次循環(huán)的弱學習機能夠集中力量對這些錯誤樣本進行判斷。弱學習機的權(quán)重準確率越高的弱學習機權(quán)重越高循環(huán)控制：損失函數(shù)達到最小在強學習機的組合中增加一個加權(quán)的弱學習機，使準確率提高，損失函數(shù)值減小。Boosting原理及在分類上的應用共32頁，您現(xiàn)在瀏覽的是第10頁!算法—問題描述訓練集{(x1,y1),(x2,y2),…,(xN,yN)}xiRm,yi{-1,+1}Dt

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

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

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

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

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

mathworld.wolfram.

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

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

……..

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

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

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

某張臉是否是張三的，某篇文章是否屬于新聞類別Boosting原理及在分類上的應用共32頁，您現(xiàn)在瀏覽的是第21頁!Boosting—concepts(3)弱學習機（weaklearner):對一定分布的訓練樣本給出假設(shè)（僅僅強于隨機猜測）

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

根據(jù)CNN,ABC,CBS以往的預測表現(xiàn)及實際天氣情況作出綜合準確的天氣預測弱學習機強學習機BoostingBoosting原理及在分類上的應用共32頁，您現(xiàn)在瀏覽的是第22頁!Boosting流程(loop2)強學習機弱學習機原始訓練集加權(quán)后的訓練集加權(quán)后的假設(shè)Y>3?1:-1弱假設(shè)Boosting原理及在分類上的應用共32頁，您現(xiàn)在瀏覽的是第23頁!流程描述Step1:原始訓練集輸入，帶有原始分布Step2:給出訓練集中各樣本的權(quán)重Step3:將改變分布后的訓練集輸入已知的弱學習機，弱學習機對每個樣本給出假設(shè)Step4:對此次的弱學習機給出權(quán)重Step5:轉(zhuǎn)到Step2,直到循環(huán)到達一定次數(shù)或者某度量標準符合要求Step6:將弱學習機按其相應的權(quán)重加權(quán)組合形成強學習機Boosting原理及在分類上的應用共32頁，您現(xiàn)在瀏覽的是第24頁!簡單問題演示（Boosting訓練過程）Boosting原理及在分類上的應用共32頁，您現(xiàn)在瀏覽的是第25頁!算法—樣本權(quán)重思想：提高分錯樣本的權(quán)重反映了stronglearner對樣本的假設(shè)是否正確采用什么樣的函數(shù)形式？

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

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

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