【文章內(nèi)容簡(jiǎn)介】 、歸納、演繹信息，構(gòu)造出對(duì)目標(biāo)的表示，為新信息提供進(jìn)一步學(xué)習(xí)的指導(dǎo)。這就是學(xué)習(xí)的過(guò)程。我們所用到的機(jī)器學(xué)習(xí)是一種歸納學(xué)習(xí)，即對(duì)已分類的數(shù)據(jù)，通過(guò)歸納其分類的原因，產(chǎn)生一些概念性描述作為學(xué)習(xí)的結(jié)果。例如，通過(guò)對(duì)溫度，濕度，有無(wú)風(fēng)等觀測(cè)結(jié)果的分析來(lái)判斷是否適于打高爾夫。由歸納學(xué)習(xí)的一種算法一決策樹算法，利用溫度，濕度，有無(wú)風(fēng)等探索性信息計(jì)算生成決策樹，然后將其變換成分類準(zhǔn)則的集合。這些分類準(zhǔn)則即為學(xué)習(xí)的結(jié)果。在第1部分介紹的許多學(xué)習(xí)算法，它們的準(zhǔn)確率各不相同。我們希望每個(gè)學(xué)習(xí)算法都有較高的準(zhǔn)確率，但這在實(shí)際中不易做到。Boosting算法是提高預(yù)測(cè)學(xué)習(xí)系統(tǒng)能力的有效工具，在POS[18]和文本分類[22]中得到成功應(yīng)用。Boosting算法的主要思想是把多個(gè)不太準(zhǔn)確的弱規(guī)則合并為一個(gè)高精度的分類規(guī)則，弱規(guī)則由弱學(xué)習(xí)器（Weak Learner）產(chǎn)生，這些弱規(guī)則組合得到最終規(guī)則，即通過(guò)學(xué)習(xí)得到的分類規(guī)則。 基本概念1) 學(xué)習(xí)算法對(duì)已知數(shù)據(jù)信息通過(guò)分析、歸納其被分類的原因，生成數(shù)據(jù)特征的描述作為學(xué)習(xí)的結(jié)論。用來(lái)完成這種過(guò)程的計(jì)算機(jī)算法稱為學(xué)習(xí)算法。我們把需要用Boosting方法進(jìn)行改進(jìn)的精度不高的算法稱為弱學(xué)習(xí)算法（Weak Learner），也稱為弱學(xué)習(xí)器。2) 訓(xùn)練集訓(xùn)練集（Training set）是已知的數(shù)據(jù)信息，即所謂弱學(xué)習(xí)算法用于獲得學(xué)習(xí)結(jié)論的樣本集合。它包含 N 個(gè)樣本，每個(gè)樣本有觀測(cè)值和標(biāo)識(shí)值組成，其中是屬性值(多元指標(biāo))的一個(gè)向量，屬于樣本空間X；每個(gè)為的類別標(biāo)識(shí)，屬于一個(gè)有限標(biāo)識(shí)空間Y。3) 假設(shè)學(xué)習(xí)的目的是構(gòu)造對(duì)目標(biāo)的表示作為學(xué)習(xí)的結(jié)論，在這里即產(chǎn)生一個(gè)函數(shù)。此函數(shù)通過(guò)作用在訓(xùn)練集的觀測(cè)值上而產(chǎn)生一個(gè)標(biāo)識(shí)，這樣的函數(shù)稱為假設(shè)，記為在Boosting中，每次學(xué)習(xí)都產(chǎn)生一個(gè)假設(shè)，我們稱為弱假設(shè)。最終聯(lián)合所有弱假設(shè)而得到的判別函數(shù)稱為最終假設(shè)或最終判別準(zhǔn)則，記為H(x)。4) 分布Boosting方法的第 t 次循環(huán)中提供給弱學(xué)習(xí)算法的關(guān)于訓(xùn)練集樣本的分布，記為。5) 誤判率由第 t 次弱學(xué)習(xí)而得弱假設(shè)的錯(cuò)判概率稱為誤判率，這里此誤判率(error)定義如下： （） AdaBoost算法背景AdaBoost的前身是Boosting算法。Boosting作為一種通用的學(xué)習(xí)算法，可以提高任一給定算法的性能。Boosting根源于研究機(jī)器學(xué)習(xí)的理論框架 ——“PAC”學(xué)習(xí)模型（由Valiant提出的關(guān)于可學(xué)習(xí)性的理論：Probably、Approximately、Correct）。Kearns and Valiant最先指出，在“PAC”學(xué)習(xí)模型中，若存在一個(gè)多項(xiàng)式級(jí)的學(xué)習(xí)算法來(lái)識(shí)別一組概念，并且識(shí)別率很高，那么這組概念是強(qiáng)可學(xué)習(xí)的；而如果學(xué)習(xí)算法識(shí)別一組概念的正確率僅比隨機(jī)猜測(cè)的略好，那么這組概念是弱可學(xué)習(xí)的。如果能將一個(gè)弱學(xué)習(xí)算法提升為強(qiáng)學(xué)習(xí)算法，那么在學(xué)習(xí)概念時(shí)，只要找到一個(gè)比隨機(jī)猜測(cè)略好的弱學(xué)習(xí)算法，就可以將其提升為強(qiáng)學(xué)習(xí)算法，而不必直接去找通常情況下很難獲得的強(qiáng)學(xué)習(xí)算法。[18]1989年Schapire[18]提出了第一個(gè)可證的具有多項(xiàng)式復(fù)雜度的Boosting算法。他的主要方法如下：1） 通過(guò)對(duì)N個(gè)訓(xùn)練樣本的學(xué)習(xí)，得出初始判別G1；2） 判別G2是對(duì)新的N個(gè)樣本學(xué)習(xí)的結(jié)果，此N個(gè)樣本中的半數(shù)為被G1錯(cuò)判的；3） G3的訓(xùn)練集為由G1, G2作出不同判斷的N個(gè)樣本組成；4） 由Boosting作出最終判別準(zhǔn)則： GB = 多數(shù)意見(jiàn)(G1, G2, G3)。在這篇文章中，Schapire在理論上證明了最終判別準(zhǔn)則GB對(duì)G1判別準(zhǔn)確率的提高。但由于此方法實(shí)施起來(lái)需要大量的時(shí)間、存儲(chǔ)空間及樣本，因此使用起來(lái)極不方便。一年之后，F(xiàn)reund[19]開發(fā)了一個(gè)更有效的Boosting算法，即“投票方式Boosting方法”。這種相對(duì)簡(jiǎn)單、行之有效的方法通過(guò)平行地作多次學(xué)習(xí)，再對(duì)各次學(xué)習(xí)的弱假設(shè)以多數(shù)意見(jiàn)來(lái)作為最后的判別準(zhǔn)則。盡管此算法在某種程度上說(shuō)是理想的，但還是存在某種實(shí)際的缺陷。這兩種方法都是通過(guò)多次運(yùn)行弱學(xué)習(xí)算法，每次將其應(yīng)用于樣本空間的不同分布上，得出多個(gè)弱學(xué)習(xí)所產(chǎn)生的弱假設(shè)，最后采用多數(shù)投票的原則綜合所有弱假設(shè)給出一個(gè)簡(jiǎn)單的最終的判別準(zhǔn)則，從而達(dá)到提高弱學(xué)習(xí)算法的準(zhǔn)確率的目的。兩種算法都是通過(guò)不斷加大樣本中難以判別的樣本的權(quán)重，迫使弱學(xué)習(xí)算法得出在這些樣本上犯更少錯(cuò)誤的假設(shè)。Drucher，Schapire和Simard[20]首次在OCR項(xiàng)目中對(duì)這些早期Boosting算法進(jìn)行了實(shí)驗(yàn)。兩種算法在理論上都要求弱學(xué)習(xí)算法有固定的誤判率，實(shí)際上，這是很難做到的。這使得人們迫切地想找到一種更具適應(yīng)性和實(shí)用性的算法。AdaBoost算法于1995年由Freund和Schapire[21]提出，解決了許多早期Boosting算法的實(shí)際困難。它的最終判別準(zhǔn)則的精確度是依賴所有弱學(xué)習(xí)過(guò)程得出的弱假設(shè)的，因而更能全面地挖掘弱學(xué)習(xí)算法的能力。也正是由于此種原因而得名“Adaptive Boosting”，簡(jiǎn)稱AdaBoost（“Ada”是“adaptive”的縮寫）。同時(shí)，它也是應(yīng)用于實(shí)際問(wèn)題的一個(gè)有效的方法。 AdaBoost算法基本思想AdaBoost算法的輸入是一個(gè)訓(xùn)練集其中屬于某個(gè)域或?qū)嵗臻g， Y為有限的表示空間。AdaBoost在一系列的迭代中重復(fù)調(diào)用給定的弱或基本學(xué)習(xí)算法。算法的主要思想是維持訓(xùn)練集上的一個(gè)分布或權(quán)重集（表示為）。初始狀態(tài)下，分布D的權(quán)值是相同的。在每次迭代中，運(yùn)用表中的調(diào)整公式調(diào)整每個(gè)樣本的權(quán)值，使每次輸入弱學(xué)習(xí)器的樣本集具有不同的權(quán)重，讓弱學(xué)習(xí)器集中學(xué)習(xí)那些使用前一規(guī)則最難以預(yù)測(cè)的樣本上。弱規(guī)則的作用是用來(lái)產(chǎn)生一個(gè)弱假設(shè)：。弱假設(shè)的好壞由錯(cuò)誤率來(lái)（）衡量，而且誤差的測(cè)量是與學(xué)習(xí)器被訓(xùn)練的分布相關(guān)的。在實(shí)際用用中，弱學(xué)習(xí)器的算法可以是作用于訓(xùn)練實(shí)例的權(quán)重分布，也可以是取樣于分布的某一訓(xùn)練子集（未賦權(quán)重）[21]。 AdaBoost算法描述輸入： 其中，且初始化：訓(xùn)練過(guò)程：For t = 1，… ，T：a) 把傳給并調(diào)用弱規(guī)則學(xué)習(xí)器；b) 獲得的弱規(guī)則 c) 選擇d) 利用調(diào)整公式調(diào)整矩陣D的權(quán)值 其中是正規(guī)化因子輸出：最終假設(shè)得到弱假設(shè)后，AdaBoost需要選擇一個(gè)參數(shù)（）。測(cè)量了的重要性，如果（這種情況下，可以認(rèn)為沒(méi)有總誤差），而且。規(guī)則的作用是增加被錯(cuò)分的實(shí)例權(quán)重，減少正確分類的實(shí)例的權(quán)重。因此，權(quán)重趨向于難以分類的實(shí)例上。最終規(guī)則H是T個(gè)弱假設(shè)（是賦給的權(quán)重）的占絕大部分的投票。 Schapire和Singer[23]闡述了如何將AdaBoost及其分析擴(kuò)展到處理輸出值為實(shí)值或置信預(yù)測(cè)的弱假設(shè)上的。也就是說(shuō)，對(duì)每個(gè)實(shí)例x，弱假設(shè)輸出一個(gè)預(yù)測(cè)，其標(biāo)記是預(yù)測(cè)標(biāo)簽（1或+1），梯度 || 給出了預(yù)測(cè)的置信度。 AdaBoost 算法的數(shù)據(jù)流程圖Fig. Data flow diagram of AdaBoost algorithm AdaBoost算法誤差的分析AdaBoost最基本的理論特性是它減少總誤差的能力。對(duì)于二值問(wèn)題，隨機(jī)猜測(cè)任意實(shí)例類別的錯(cuò)誤率為50%。記的誤差為，其中測(cè)量了的預(yù)測(cè)比隨機(jī)測(cè)量好的程度。Freund和Schapire[18]證明最終假設(shè)H的訓(xùn)練誤差（訓(xùn)練集中錯(cuò)誤比例）上限為： （）上式表明，對(duì)于某一 ，只要每個(gè)弱假設(shè)的預(yù)測(cè)能力比隨機(jī)猜測(cè)好一些，訓(xùn)練誤差就會(huì)成指數(shù)級(jí)的下降。先前的Boosting算法也具有類似的特性，但是在它開始學(xué)習(xí)之前需要獲得一個(gè)更低的類間距。通常這樣的類間距是很難獲得的。AdaBoost適應(yīng)于每個(gè)單獨(dú)弱假設(shè)的錯(cuò)誤率，因此它是自適應(yīng)的。Freund和Schapire[21]闡述了如何根據(jù)訓(xùn)練誤差、樣例的大小m，弱假設(shè)空間的VC維度d和Boosting的迭代次數(shù)T來(lái)限制最終假設(shè)的總誤差。而且還利用Baum和Haussler的技術(shù)闡明了高概率地情況下，總誤差至多為： （）其中表示訓(xùn)練樣本的經(jīng)驗(yàn)概率。這個(gè)邊界表示如果迭代次數(shù)過(guò)多Boosting會(huì)發(fā)生過(guò)適應(yīng)。在實(shí)際實(shí)驗(yàn)中，有時(shí)的確如此，然而，在早期的大部分實(shí)驗(yàn)中，一些作者[22，24]得到的經(jīng)驗(yàn)結(jié)論卻是：Boosting經(jīng)常不會(huì)發(fā)生過(guò)適應(yīng)，甚至在迭代上千次的情況下。而且在訓(xùn)練誤差降到0之后，AdaBoost有時(shí)會(huì)繼續(xù)降低總誤差，這明顯違背上面的邊界。[25]，得到的相對(duì)于迭代次數(shù)T的誤差曲線和類間距分布圖。左圖中上面一根曲線表示泛化誤差，下面一根曲線表示訓(xùn)練誤差。Fig. Error curves and the margin distribution graph從左圖中可以看到，當(dāng)訓(xùn)練誤差達(dá)到零后，Boosting仍然會(huì)繼續(xù)降低泛化誤差，并沒(méi)有因?yàn)榈螖?shù)的增多出現(xiàn)泛化變差的情景。這個(gè)現(xiàn)象與機(jī)器學(xué)習(xí)中通常所遵循的“Occam39。s Razor39。，原則相違背?；谶@些經(jīng)驗(yàn)發(fā)現(xiàn)，Schapire et al.[25]在Bartlett工作的基礎(chǔ)上，給出了一個(gè)關(guān)于訓(xùn)練實(shí)例類間距的另一可選分析。實(shí)例的類間距被定義為： （）其值在[1，+1]，僅當(dāng)H正確的劃分實(shí)例時(shí)是正的。而且，類間距的梯度可被解釋為對(duì)置信度的一種預(yù)測(cè)。Schapire et 。具體地，對(duì)任意的，總誤差至多為： （）的概率是很高的。其中，邊界是完全獨(dú)立于T的。公式（）中給出總誤差的邊界，結(jié)合公式（）中給出的訓(xùn)練誤差的邊界，證明了在給定足夠數(shù)據(jù)的情況下，AdaBoost能有效的轉(zhuǎn)換弱學(xué)習(xí)算法到一個(gè)強(qiáng)學(xué)習(xí)算法。從這層意義上來(lái)說(shuō)，AdaBoost是一種真正意義上的Boosting算法。 多類分類問(wèn)題有幾種擴(kuò)展AdaBoost到多類情況的方法。，此算法只要在弱學(xué)習(xí)器強(qiáng)壯到能獲得令人滿意的足夠高的準(zhǔn)確率的情況下，得到的效果是令人滿意的，甚至在那些AdaBoost產(chǎn)生的難以預(yù)測(cè)的分布上。然而，一旦在這些難以預(yù)測(cè)的分布上弱學(xué)習(xí)器不能獲得至少50%的正確率，那么這種方法就會(huì)失敗。針對(duì)后面這種情況，產(chǎn)生了一些更復(fù)雜的方法。它們的共通工作是把多類問(wèn)題減少到大的二值分類問(wèn)題。但是，這些方法需要在設(shè)計(jì)弱學(xué)習(xí)算法方面的額外工作。對(duì)每個(gè)實(shí)例x和每個(gè)可能的標(biāo)簽y，作這樣的處理：對(duì)實(shí)例x，標(biāo)簽y是正確的還是其它標(biāo)簽中的一個(gè)是正確的？（）沒(méi)有創(chuàng)建二值集合，對(duì)任意的實(shí)例x具有正確的標(biāo)簽y和不正確的標(biāo)簽y39。，作如下處理：對(duì)實(shí)例x，標(biāo)簽y是正確的還是y39。是正確的？這些方法需要在設(shè)計(jì)弱學(xué)習(xí)算法方面的額外工作。不同的技術(shù)，包括Dietterich和Bakiri的errorcorrecting output codes的方法，但是可同任意能夠處理二值數(shù)據(jù)的弱學(xué)習(xí)算法一起使用。Schapire和Singer給出了另一種合并Boosting和errorcorrecting output codes的方法。 AdaBoost算法的優(yōu)缺點(diǎn)AdaBoost具有很多優(yōu)點(diǎn)：1）快速、簡(jiǎn)單并且易于編程；2）除了迭代次數(shù)T外，沒(méi)有參數(shù)需要調(diào)整；3）不需要關(guān)于弱學(xué)習(xí)器的先前知識(shí)，可以很容易地與任何發(fā)現(xiàn)弱假設(shè)方法合并；4）只要給定足夠的數(shù)據(jù)和一個(gè)能可靠地提供中度正確的弱假設(shè)的弱學(xué)習(xí)器，它就獲得了理論上的保證。這對(duì)于學(xué)習(xí)系統(tǒng)的設(shè)計(jì)方面這是一個(gè)思想上的轉(zhuǎn)變，即不試圖去設(shè)計(jì)在整個(gè)空間上都正確的學(xué)習(xí)算法，而是集中發(fā)現(xiàn)僅僅比隨機(jī)選擇好一些的弱學(xué)習(xí)算法。另一方面，AdaBoost算法也具有一定的缺點(diǎn)。AdaBoost在實(shí)際問(wèn)題上的實(shí)際性能明顯地依賴于數(shù)據(jù)和弱學(xué)習(xí)算法。AdaBoost在給定的數(shù)據(jù)不充分、弱假設(shè)過(guò)度復(fù)雜或弱假設(shè)太弱的情況下，不能表現(xiàn)出很好的性能，這一點(diǎn)與理論一致。AdaBoost似乎特別受噪音的影響[26]。在另外一些實(shí)驗(yàn)中，Schapire和Singer[22]在文本分類中使用Boosting。在這些任務(wù)中，弱假設(shè)被用來(lái)測(cè)試詞或短語(yǔ)的出現(xiàn)或不存在。大體上從所有的這些實(shí)驗(yàn)和對(duì)所有的被測(cè)試的性能來(lái)說(shuō)，Boosting表現(xiàn)地同樣或更好于其他的被測(cè)試的方法。Boosting還被應(yīng)用在文本過(guò)濾和劃分問(wèn)題。[31] Schapire and Singer[21]。對(duì)于WSD，由于在每個(gè)給定的上下文中多義詞的詞義是唯一確定的，因此WSD只是單標(biāo)簽的分類問(wèn)題。，該算法對(duì)簡(jiǎn)單決策樹產(chǎn)生的分類規(guī)則進(jìn)行加強(qiáng)，經(jīng)過(guò)若干次迭代后，最終得到一個(gè)準(zhǔn)確度更高的分類規(guī)則，即為最終的消歧模型。設(shè)樣本集，其中，X為訓(xùn)練集，；，Y為詞義標(biāo)簽集，記。樣本為單一實(shí)例x和該實(shí)例對(duì)應(yīng)的詞義標(biāo)簽y。，初始狀態(tài)下，分布D的權(quán)值是相同的。令為第t次迭代后的分布，為分布上獲得的弱規(guī)則，該規(guī)則由弱學(xué)習(xí)器產(chǎn)生。表示對(duì)詞義標(biāo)簽是否應(yīng)該賦給實(shí)例x的一種預(yù)測(cè)，其值||反映了這種預(yù)測(cè)的可信度。弱規(guī)則的產(chǎn)生是一個(gè)序列式的學(xué)習(xí)過(guò)程。在每次迭代中，運(yùn)用下面的調(diào)整公式調(diào)整每個(gè)樣本的權(quán)值，使每次輸入弱學(xué)習(xí)器的樣本集具有不同的權(quán)重，讓弱學(xué)習(xí)器集中學(xué)習(xí)那些使用前一規(guī)則最難以預(yù)測(cè)的樣本上。給定，引入符號(hào)，若與標(biāo)簽l一致，的值為1，否則的值為 1，調(diào)整公式定義如下： （）其中，為歸一化因子，Schapire and Singer[21]已經(jīng)證明，算法誤差的最大值為：（T為總的弱規(guī)則數(shù)），因此為減少總誤差，在選取時(shí)應(yīng)使其最小化。從公式中可以看出，若的預(yù)測(cè)可信度較好，則的值是增加的，反之，的值是減少的，且的調(diào)整幅度與||成比例。由于WSD為單標(biāo)簽分類，因此最終形成的合并假設(shè)為唯一的標(biāo)簽l，而且這個(gè)標(biāo)簽滿足最大化。 輸入：樣本集 初始化：訓(xùn)練過(guò)程：For t