學(xué)習(xí)模型中的學(xué)習(xí)算法

學(xué)習(xí)模型中的學(xué)習(xí)算法

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