學習模型中的學習算法

學習模型中的學習算法

1kearns的識別算法在機械學習領域，重要的問題是如何使用觀測數(shù)據(jù)來獲得準確的評估。目前,隨著計算機硬件技術(shù)的迅猛發(fā)展,學習準確率比運算速度顯得更為重要。但是,在實際應用領域中,構(gòu)造一個高精度的估計幾乎是不可能的。Boosting是一種提高任意給定學習算法準確度的方法。它的思想起源于Valiant提出的PAC(ProbablyApproximatelyCorrect)學習模型。Valiant和Kearns提出了弱學習和強學習的概念,識別錯誤率小于1/2,也即準確率僅比隨機猜測略高的學習算法稱為弱學習算法;識別準確率很高并能在多項式時間內(nèi)完成的學習算法稱為強學習算法。同時,Valiant和Kearns首次提出了PAC學習模型中弱學習算法和強學習算法的等價性問題,即任意給定僅比隨機猜測略好的弱學習算法,是否可以將其提升為強學習算法?如果二者等價,那么只需找到一個比隨機猜測略好的弱學習算法就可以將其提升為強學習算法,而不必尋找很難獲得的強學習算法。1990年,Schapire最先構(gòu)造出一種多項式級的算法,對該問題做了肯定的證明,這就是最初的Boosting算法。一年后,Freund提出了一種效率更高的Boosting算法。但是,這兩種算法存在共同的實踐上的缺陷,那就是都要求事先知道弱學習算法學習正確率的下限。1995年,Freund和schapire改進了Boosting算法,提出了AdaBoost(AdaptiveBoosting)算法,該算法效率和Freund于1991年提出的Boosting算法幾乎相同,但不需要任何關(guān)于弱學習器的先驗知識,因而更容易應用到實際問題當中。之后,Freund和schapire進一步提出了改變Boosting投票權(quán)重的AdaBoost.M1,AdaBoost.M2等算法,在機器學習領域受到了極大的關(guān)注。2adabolst算法AdaBoost算法是Boosting家族最具代表性的算法,之后出現(xiàn)的各種Boosting算法都是在AdaBoost算法的基礎之上發(fā)展而來的。對AdaBoost算法的研究應用大多集中在分類問題中,近年來也出現(xiàn)了一些在回歸問題上的研究。本文以AdaBoost算法在分類問題中的應用為例做一個簡單介紹。AdaBoost算法的基本思想是:首先給出任意一個弱學習算法和訓練集(x1,y1),(x2,y2),…,(xm,ym),此處,xi∈X,X表示某個域或?qū)嵗臻g,在分類問題中是一個帶類別標志的集合,yi∈Y={+1,-1}。初始化時,Adaboost為訓練集指定分布為1/m,即每個訓練例的權(quán)重都相同為1/m。接著,調(diào)用弱學習算法進行T次迭代,每次迭代后,按照訓練結(jié)果更新訓練集上的分布,對于訓練失敗的訓練例賦予較大的權(quán)重,使得下一次迭代更加關(guān)注這些訓練例,從而得到一個預測函數(shù)序列h1,h2,…,ht,每個預測函數(shù)ht也賦予一個權(quán)重,預測效果好的,相應的權(quán)重越大。T次迭代之后,在分類問題中最終的預測函數(shù)H采用帶權(quán)重的投票法產(chǎn)生。單個弱學習器的學習準確率不高,經(jīng)過運用Boosting算法之后,最終結(jié)果準確率將得到提高。每個樣本都賦予一個權(quán)重,T次迭代,每次迭代后,對分類錯誤的樣本加大權(quán)重,AdaBoost的算法描述如下:3泛化誤差分析Schapire,Singer和Freund首先從理論上推導出最終預測函數(shù)的訓練誤差:定義f(x)=∑tαtht(x)f(x)=∑tαtht(x),則有H(X)=sign(f(x)),進而推導出訓練誤差的邊界為:1m1m{i:H(xi)≠yt}≤1m∑texp(?yif(xi))=∏tTZt(1)≤1m∑texp(-yif(xi))=∏tΤΖt(1)從(1)式中我們可以看出,可以通過選擇每一輪中的αt和ht來最小化Zt,使得訓練誤差迅速減小。Schapire和Freund還證明了最終預測函數(shù)H的最大錯誤率為:H=?tΗ=?t2εt(1?εt)????????√2εt(1-εt)=∏t1?4γt2???????√≤exp(?2∑tγt2)(2)=∏t1-4γt2≤exp(-2∑tγt2)(2)在(2)中,γt=1/2-εt,其中εt為訓練誤差。從該式中可以看出,只要我們選擇的弱學習算法略好于隨機猜想,訓練誤差將隨t以指數(shù)級下降。AdaBoost算法出現(xiàn)之前的Boosting算法也有類似的性質(zhì),但學習之前需要事先知道λt的下限,這在實際當中是很難獲得的。而AdaBoost可以在每輪訓練中調(diào)整預測函數(shù)的錯誤率,體現(xiàn)出它的自適應性,因此不存在這樣的問題。在此基礎上,Schapire和Freund用VC維從訓練誤差的角度對Boosting算法的泛化誤差進行了分析。VC維是學習算法復雜度及其學習能力的度量。推導出其泛化誤差的上限為:P?r(H(x)≠y)+O?(Tdm???√)(3)Ρ^r(Η(x)≠y)+Ο^(Τdm)(3)其中,m為訓練例個數(shù),d為學習算法的VC維,T為訓練輪數(shù),P?r(?)Ρ^r(?)表示對訓練集的經(jīng)驗概率。式(3)表明,若訓練輪數(shù)T過大,將導致過適應。但大量的試驗表明,Boosting不但能夠提高學習精度,而且在訓練了幾千輪之后也不會發(fā)生過適應現(xiàn)象,而且其泛化誤差在訓練誤差已經(jīng)降到零后仍會繼續(xù)降低。Schapire和Freund在文獻中用BoostingC4.5對UCI中的“l(fā)etter”樣本集進行分類,圖1是得出的相對于迭代次數(shù)T的誤差曲線。圖1中,上面一條曲線是泛化誤差,下面一條曲線是訓練誤差。從圖中我們可以看出,在訓練誤差已經(jīng)達到零后,Boosting仍能繼續(xù)降低泛化誤差,而不會因此出現(xiàn)泛化誤差惡化的現(xiàn)象。為了解釋這一現(xiàn)象,Schapire等從邊界的角度對泛化誤差作了分析,樣本(x,y)的邊界margin(x,y)定義如下:margin(x,y)=y∑tαtht(x)(4)margin(x,y)=y∑tαtht(x)(4)式(4)中αt=1/2ln((1-et)/et),margin的值屬于[-1,+1]之間,其值可以被看作是對預測函數(shù)H預測結(jié)果的可信度。較大的正邊界表示可信度高的正確的預測,較大的負邊界表示可信度高的錯誤的預測。圖2反映出Boosting對邊界的影響。當訓練誤差降為零后,Boosting仍然會繼續(xù)提高訓練樣本的邊界值,從而增大了最小邊界,使分類的可靠性增加,使得泛化誤差也能夠繼續(xù)下降。Schapire給出了泛化誤差的上限:P?r(margin(x,y)≤θ)+O?(dmθ2???√)(5)Ρ^r(margin(x,y)≤θ)+Ο^(dmθ2)(5)從式(5)可以看出,泛化誤差與訓練輪數(shù)T無關(guān),也就是說泛化誤差不受訓練輪數(shù)影響,這也解釋了圖1中的現(xiàn)象。Grove指出用Schapire提出的邊界理論解釋Boosting的泛化問題存在一定局限,并在文獻中構(gòu)造了LPBoost算法。LPBoost算法可以找到更大的最小邊界的最大值,但其泛化性能卻比Boosting要差,Grove指出僅僅提高最小邊界的最大值并不能作為提高泛化性能的依據(jù),有時反而會增大泛化誤差。之后,越來越多的文獻也指出,Boosting算法對噪聲敏感,在不存在噪聲的前提下,Boosting算法有較好的泛化性能。4uping試驗自從Boosting算法出現(xiàn)以來,在機器學習領域備受關(guān)注,得到了很多的應用。Quinlan將C4.5決策樹作為弱學習器,以UCI的27個數(shù)據(jù)庫為數(shù)據(jù)集,選擇迭代次數(shù)為10次。試驗結(jié)果表明,使用單個決策樹,其平均誤差為15.66%,使用Boosting能夠使平均誤差降低到13.36%。Boosting能夠使泛化誤差明顯降低,但Quinlan指出,Boosting在有些情況下會出現(xiàn)過適應。Schwenk和bengio采用兩層前向神經(jīng)網(wǎng)絡作為弱學習器,進行手寫體字符識別,對UCI中的字符數(shù)據(jù)集進行測試,結(jié)果表明誤差降低到1.4%。Boosting在實際當中也得到了很多應用,例如,語音識別、醫(yī)療診斷等。文獻將高斯模型作為弱分類器應用于音頻識別。文獻將Boosting用于人臉檢測。文獻將Boosting與Stumps結(jié)合用于進行文本分類。文獻將Boosting方法和遺傳算法結(jié)合進行滾動軸承的故障診斷。5算法的選擇Boosting算法的簡單高效受到了人們的很多關(guān)注。它使得在實際應用中,我們不必費力地尋找預測精度很高的算法,而只需找到一個比隨機猜測略好的弱學習算法,就可以通過Boosting將其提升為強學習算法,從而也相應地達到提高預測精度的目的。Boosting要求“不穩(wěn)定”的分類方法,例如:決策樹、神經(jīng)網(wǎng)絡算法等。所謂不穩(wěn)定指的是數(shù)據(jù)集的小的變動能夠使得分類結(jié)果顯著地變動。Boosting算法具有很多優(yōu)點,它有較高的正確率,不需要先驗知識,只需要選擇合適的迭代次數(shù)等。但是它速度慢,在一定程度上依賴于訓練數(shù)據(jù)集合和弱學習器的選擇,訓練數(shù)據(jù)不充足或者弱學習器太過“弱”,都將導致其訓練精度的下降。另外,Boosting易受到噪聲的影響,這是因為它在迭代過程中總是給噪聲分配較大的權(quán)重,使得這些噪聲在以后的迭代中受到更多的關(guān)注。目前,B