一種通用的集成學(xué)習算法

一種通用的集成學(xué)習算法

在機械學(xué)習領(lǐng)域，schapire等人提出的adaboost算法無疑是最受關(guān)注和研究的算法之一。該算法是一種基于valint提出的pac（可執(zhí)行微鎖）的學(xué)習模型。根據(jù)keean提出的模型學(xué)習和valint提出的弱學(xué)習概念，具體實現(xiàn)弱學(xué)習算法向強學(xué)習算法的轉(zhuǎn)變的可操作算法。adaboost算法、realadaboost算法和gentreavobst算法已在許多領(lǐng)域得到應(yīng)用。這是目前檢測面部特征的最佳方法之一?；赼daboost算法的技術(shù)和思想，許多研究人員在制定該算法方面解決了多分類、價格復(fù)雜分類、不平衡分類、模糊分類等問題。然而，在推廣這項算法時，幾乎需要不同的處理方法，尤其是弱學(xué)習算法的結(jié)構(gòu)。弱學(xué)習算法的泛化能力決定了集成學(xué)習算法的泛化能力。在實現(xiàn)訓(xùn)練錯誤（或錯分）最小化的模式評價功能時，為了確保不出現(xiàn)學(xué)習，現(xiàn)有的許多集成學(xué)習算法都存在相應(yīng)的分析不足。如果能對二分類、多分類、代價敏感分類、不平衡分類、多標簽分類等眾多分類預(yù)測問題的集成學(xué)習算法進行統(tǒng)一,包括對弱分類器的構(gòu)造的統(tǒng)一必然是一件好事.集成學(xué)習算法的構(gòu)造一般要求體現(xiàn)弱學(xué)習定理的思想,即算法能將弱學(xué)習算法提升為強學(xué)習算法,這并非易事.首先,弱學(xué)習定理成立的條件是弱學(xué)習算法要比隨機猜測略好,這在二分類問題中容易實現(xiàn),如果錯誤率大于0.5時,互換分類結(jié)果即可.但在多分類、代價敏感分類、不平衡分類等問題中,構(gòu)造滿足該條件的弱分類器是困難的,如果還要求統(tǒng)一的構(gòu)造方法就更難.其次,算法需確保組合預(yù)測函數(shù)比單個簡單預(yù)測函數(shù)的預(yù)測效果更好,這就要求算法不僅有低的訓(xùn)練錯誤率,還應(yīng)該有好的泛化能力.泛化能力不僅涉及到簡單預(yù)測函數(shù)的組合方式,還涉及到簡單預(yù)測函數(shù)的構(gòu)造方法.最理想的集成學(xué)習算法應(yīng)該是既可以很好擬合樣本(訓(xùn)練錯誤率可以趨于0)又不易出現(xiàn)過學(xué)習的算法.本文圍繞boosting集成學(xué)習算法的統(tǒng)一和泛化能力的保證進行了較深入的研究,得到了一種通用的集成學(xué)習算法,其可以衍生出一系列具體的集成學(xué)習算法,包括經(jīng)典的RealAdaBoost算法、多分類AdaBoost算法、GentleAdaBoost算法,多標簽分類集成學(xué)習算法、代價敏感分類集成學(xué)習算法等,理論上這些算法還能實現(xiàn)學(xué)習錯誤任意小.為了算法的統(tǒng)一和好的泛化能力,本文指出簡單預(yù)測函數(shù)可以統(tǒng)一基于單個特征來構(gòu)造,對其不易出現(xiàn)過學(xué)習重要特性進行了分析與實驗驗證.1根據(jù)lx,l所作的1/3.設(shè)有預(yù)測函數(shù)f:X→RK,X為示例空間,f為X到K維空間RK的映射,所有X到RK的映射函數(shù)集記為Φ.示例x∈X的標識為K維空間RK中的向量Y=(y1,…,yK),并假設(shè)yk≥0(k=1,…,K),預(yù)測函數(shù)f(x)輸出值為(f(x,1),…,f(x,K)).考慮如下的預(yù)測問題:如果(f(x,1),…,f(x,K))與(y1,…,yK)各分量的大小順序一樣,則稱f(x)正確預(yù)測了x.對于這種只關(guān)注分量大小順序的預(yù)測問題,首先需要定義其學(xué)習錯誤,以便基于該學(xué)習錯誤的最小化來構(gòu)造集成學(xué)習算法.對f(x)輸出值按式(1)進行乘積歸一化處理后記為F(x):F(x,k)=exp(f(x,k)-ˉf(x))?(1)其中ˉf(x)=1ΚΚ∑k=1f(x,k),并且Κ∏l=1F(x,l)=1,且(F(x,1),…,F(x,K))與(f(x,1),…,f(x,K))各分量的大小順序完全一致.如果(F(x,1),…,F(x,K))與x在K維空間RK中的標識向量(y1,…,yK)的對應(yīng)分量成比例,即?l∈{1,…,K}有yl=cF(x,l),c>0,則f(x)就正確預(yù)測了x.于是定義如下的學(xué)習錯誤:ε=Ex∈X[Κ∑l=1(yl×(F(x,l))-1)].(2)因為Κ∑l=1(yl(F(x,l))-1)≥ΚΚ∏l=1(yl(F(x,l))-1)1/Κ=ΚΚ∏l=1(yl)1/Κ?注意到該式的右邊與f(x)無關(guān),并當且僅當yl×(F(x,l))-1=c(常數(shù)),即yl=cF(x,l)時,Κ∑l=1(yl×(F(x,l))-1)取到極小值.集成學(xué)習算法可基于最小化ε來構(gòu)造,即minf∈Φε=minf∈ΦEx∈X[Κ∑l=1(yl×(F(x,l))-1)].先不用關(guān)心示例x∈X的標識向量Y=(y1,…,yK)究竟是什么,后面的分析會指出,不同的賦值可得不同的學(xué)習算法.至于為何不直接采用(f(x,1),…,f(x,K))而用(F(x,1),…,F(x,K))來擬合(y1,…,yK),由前面的分析已經(jīng)看出,如果沒有乘積歸一化條件,式(2)的極小值點無法保證yl=cF(x,l).后面的分析還會發(fā)現(xiàn),采用指數(shù)函數(shù)對預(yù)測函數(shù)進行處理是為了在集成學(xué)習算法中形成遞推公式.設(shè)訓(xùn)練樣本集S={x1,…,xm},xi∈X的標識為K維空間RK中的向量Yi=(yi,1,…,yi,K),仍假設(shè)yi,k≥0(k=1,…,K),則上述預(yù)測函數(shù)的學(xué)習問題便轉(zhuǎn)變成尋找f(x),使得式(3)取到極小值:ε=m∑i=1(ωiΚ∑l=1yi,l×(F(xi,l))-1)?(3)其中{ωi}i=1,…,m為樣本的概率分布,在沒有其他先驗條件下一般令ωi=1/m.考慮f(x)為多個簡單預(yù)測函數(shù)ht(x)的組合,即f(x,l)=Τ∑t=1ht(x,l)?ht(x)輸出值為(ht(x,1),…,ht(x,K)),t=1,…,T.令ˉht(x)=1ΚΚ∑k=1ht(x,k),則ˉf(x)=Τ∑t=1ˉht(x),此時式(3)變?yōu)棣?m∑i=1(ωiΚ∑l=1yi,lexp(-f(xi,l)+ˉf(xi)))=Ζ0m∑i=1Κ∑l=1(ω1i,lΤ∏t=1exp(-ht(xi,l)+ˉht(xi)))?(4)其中,ω1i,l=ωiyi,l/Z0,Z0為歸一化因子:Ζ0=m∑i=1Κ∑l=1ωiyi,l.根據(jù)式(4)就可以形成遞推公式,比如提取出包含h1(x)的項,令:Ζ1=m∑i=1Κ∑l=1(ω1i,lexp(-h1(xi,l)+ˉh1(xi))),(5)ω2i,l=ω1i,lΖ1exp(-h1(xi,l)+ˉh1(xi))?(6)則式(4)變?yōu)棣?Ζ0Ζ1m∑i=1Κ∑l=1(ω2i,lΤ∏t=2exp(-ht(xi,l)+ˉht(xi))).(7)式(7)和式(4)類似,式(7)中t=2,…,T,而式(4)中t=1,…,T,容易形成遞推公式.可見采用指數(shù)函數(shù)對預(yù)測函數(shù)進行處理是為了形成遞推公式.我們可以先基于最小化Z1來構(gòu)造h1(x),得到h1(x)后根據(jù)式(6)計算ω2i,l,式(7)與式(4)類似,可以采用類似的方法構(gòu)造h2(x),h3(x),…,于是可得到如下的通用集成學(xué)習算法.算法1.通用集成學(xué)習算法.Step1.初始化權(quán)值:ω1i,l=ωiyi,l/Z0,i=1,…,m,l=1,…,K,Z0為歸一化因子;Step2.DoFort=1,…,T.1)在權(quán)值為ωti,l的S上訓(xùn)練預(yù)測函數(shù)ht(x):基于最小化Zt來構(gòu)造ht(x),其中:Ζt=m∑i=1Κ∑l=1(ωti,lexp(-ht(xi,l)+1ΚΚ∑k=1ht(xi,k)))；2)調(diào)整權(quán)值:ωt+1i,l=ωti,lΖtexp(-ht(xi,l)+1ΚΚ∑k=1ht(xi,k));Step3.組合預(yù)測函數(shù)f(x)輸出(f(x,1),…,f(x,K)),其中:f(x,l)=∑t=1Τht(x,l).在算法1中,最小化Zt時采用不同的方法來構(gòu)造ht(x)就能得到不同的集成學(xué)習算法,給(yi,1,…,yi,K)不同的賦值,可得到能解決不同問題的集成學(xué)習算法.由算法的構(gòu)造過程可得到如下定理:定理1.對算法1得到的組合預(yù)測函數(shù)f(x),由式(3)定義的ε滿足:ε=∏t=0ΤΖt.根據(jù)定理1,只要滿足Zt≤1(Z0除外)并且一般情況下Zt<1,則算法1就具有如下性質(zhì):ε將隨著預(yù)測函數(shù)個數(shù)T逐漸增加而逐漸減小.組合預(yù)測函數(shù)比單個簡單預(yù)測函數(shù)更有效時稱算法是有效的,于是,當算法滿足條件:Zt≤1且一般情況下Zt<1,則算法是有效的.由于Z0不涉及到預(yù)測函數(shù)的構(gòu)造,因此以下談及Zt時一般不包括Z0.2簡單預(yù)測函數(shù)算法1是非常通用的集成學(xué)習算法,其指出了簡單預(yù)測函數(shù)的組合方式和一種可自適應(yīng)的權(quán)值調(diào)整策略,許多具體集成學(xué)習算法可基于算法1來構(gòu)造.為此,先對簡單預(yù)測函數(shù)的構(gòu)造進行說明.從分類的角度,ht(x)無外乎是可對示例空間X實現(xiàn)某種分割的一種劃分,對位于不同劃分段內(nèi)的示例輸出不同的值,位于同一劃分段內(nèi)的示例輸出相同值.下面的集成學(xué)習算法的簡單預(yù)測函數(shù)主要考慮能對X實現(xiàn)某種劃分的預(yù)測函數(shù).具體如何構(gòu)造這種預(yù)測函數(shù)也有多種方法,其中最簡單的方法便是基于樣本的單個特征來劃分X,如果特征是數(shù)字的則可以采用閾值法來劃分.一個閾值可對X實現(xiàn)兩段劃分,n個閾值可對X實現(xiàn)n+1段劃分.2.1基于htx的學(xué)習算法設(shè)ht(x)對X實現(xiàn)nt段劃分,該劃分對樣本集S也有一個分割S=S1t∪…∪Sntt,當i≠j時,Sit∩Stj=?.當xi∈Sjt時,ht(xi)輸出值為(ht(xi,1),…,ht(xi,K)),其顯然與j有關(guān),可記為(αtj,1,…,αtj,Κ),j=1,…,nt.由于同一劃分段內(nèi)ht(x)輸出值一樣,合并Zt中相同項,并記ptj,l=∑i:(xi∈Sjt)ωi,lt,l=1,…,K,j=1,…,nt,可得:Ζt=∑i=1m∑l=1Κ(ωi,ltexp(-ht(xi,l)+htˉ(xi)))=∑j=1nt∑l=1Κ(ptj,lexp(-αtj,l+1Κ∑k=1Καtj,k))≥Κ∑j=1nt(∏l=1Κ(ptj,l)1/Κ).(8)根據(jù)算術(shù)平均大于等于幾何平均及等號成立條件,當αtj,l=ln(ptj,l),Zt取到極小值:Ζt=Κ∑j=1nt(∏l=1Κ(ptj,l)1/Κ)?訓(xùn)練ht(x)就轉(zhuǎn)變成尋找可使Zt取到極小值的某個劃分S=S1t∪…∪Sntt,在該劃分上,ht(x)輸出定義為x∈Sjt時,ht(x,l)=ln(ptj,l).于是由算法1可得如下的系列化集成學(xué)習算法.算法2.RealAdaBoost系列算法.Step1.初始化權(quán)值:ωi,l1=ωiyi,l/Z0,i=1,…,m,l=1,…,K,Z0為歸一化因子;Step2.DoFort=1,…,T1)在權(quán)值為ωi,lt的S上訓(xùn)練預(yù)測函數(shù)ht(x):①對劃分S=S1t∪…∪Sntt,計算ptj,l=∑i:(xi∈Sjt)ωi,lt；②定義ht(x):x∈Sjt時,ht(x,l)=ln(ptj,l),j=1,…,nt;③選取ht(x):最小化Ζt=Κ∑j=1nt(∏l=1Κ(ptj,l)1/Κ)?選取ht(x).2)調(diào)整權(quán)值:ωi,lt+1=ωi,ltΖtexp(-ht(xi,l)+1Κ∑k=1Κht(xi,k));Step3.組合預(yù)測函數(shù)f(x),輸出(f(x,1),…,f(x,K)),其中f(x,l)=∑t=1Τht(x,l).因為Ζt=Κ∑j=1nt(∏l=1Κ(ptj,l)1/Κ)≤∑j=1nt∑l=1Κptj,l=∑i=1m∑l=1Κωi,lt=1,并且僅當ptj,k=ptj,l對所有k,l=1,…,K,j=1,…,nt都成立才會有Zt=1,算法2滿足條件:Zt≤1,并且一般情況下Zt<1,因此算法2是有效的.之所以稱算法2是系列化集成學(xué)習算法,是因為算法2仍然具有通用性,xi的標識(yi,1,…,yi,K)仍然是可變的,對其進行不同賦值可得到不同算法.如采用下述方式賦值,便得到一種K分類集成學(xué)習算法.對K分類問題,設(shè)xi的類別標簽為li∈{1,…,K},用K維向量(yi,1,…,yi,K)來標識xi,令yi,li=1,其余yi,l=0(l≠li),即xi的類別標簽對應(yīng)分量為1其余分量為0的向量來標識xi.得到f(x)后輸出(f(x,1),…,f(x,K))中最大分量對應(yīng)標簽Η(x)=argmaxlf(x,l),則算法2便是已有的多分類RealAdaBoost算法.特別地,當K=2,H(x)≠l與-f(x,l)+fˉ(x)>0等價,此時式(3)定義的學(xué)習錯誤ε正是訓(xùn)練錯誤率εtri的一個上界:εtri=1m∑i=1m〖Η(xi)≠li〗≤1m∑i=1m∑l=12yi,l(F(xi,l))-1.(9)由定理1可得:εtri≤∏t=1Τ(2∑j=1ntptj,1ptj,22).(10)當所有nt=2,即ht(x)采取二段劃分時,式(10)與文獻的結(jié)論完全一致,但此處的算法2可以是多段劃分,并且可以直接處理多分類問題.2.2訓(xùn)練預(yù)測函數(shù)的性質(zhì)算法2是通過求式(8)的極小值點來得到ht(x)的輸出值αtj,l=ln(ptj,l).前面的分析已經(jīng)指出,只要能保證Zt≤1,并且一般情況下Zt<1,便能保證集成學(xué)習算法的有效性.分析發(fā)現(xiàn)(隨后證明),αtj,l=ptj,l/∑k=1Κptj,k也能滿足條件,于是可得到如下的系列化集成學(xué)習算法.算法3.GentleAdaBoost系列算法.Step1.初始化權(quán)值:ωi,l1=ωiyi,l/Z0,i=1,…,m,l=1,…,K,Z0為歸一化因子;Step2.DoFort=1,…,T1)在權(quán)值為ωi,lt的S上訓(xùn)練預(yù)測函數(shù)ht(x):①對劃分S=S1t∪…∪Sntt,計算ptj,l=∑i:(xi∈Sjt)ωi,lt；②定義ht(x):x∈Sjt時,ht(x,l)=ptj,l/∑k=1Κptj,k?j=1,?,nt；③選取ht(x):最小化Zt選取ht(x),其中Ζt=∑j=1nt∑l=1Κ(ptj,lexp(-ptj,l/∑k=1Κptj,k))exp(1/Κ).2)調(diào)整權(quán)值:ωi,lt+1=ωi,ltΖtexp(-ht(xi,l)+1Κ∑k=1Κht(xi,k)).Step3.組合預(yù)測函數(shù)f(x),輸出(f(x,1),…,f(x,K)),其中f(x,l)=∑t=1Τht(x,l).類似地,對示例的標識采取不同的賦值方法可以得到不同的集成學(xué)習算法.針對K分類問題,用(yi,1,…,yi,K)來標識xi,令yi,li=1,其余yi,l=0(l≠li),li是xi的類標簽.得到f(x)后輸出標簽Η(x)=argmaxlf(x,l),則算法3就是一種多分類GentleAdaBoost算法.算法3的有效性可證明如下:考察∑l=1Κ(αtj,lexp(-αtj,l)),注意到∑l=1Καtj,l=1.當x∈,函數(shù)g(x)=xexp(-x)的一階導(dǎo)數(shù)g′(x)>0,且二階導(dǎo)數(shù)g″(x)<0,這表明g(x)是一個上凸函數(shù),于是:∑l=1Κ1Κ(αtj,lexp(-αtj,l))≤(∑l=1Κ1Καtj,l)exp(-∑l=1Κ1Καtj,l)=1Κexp(-1Κ).(11)由此可得Zt≤∑j=1nt∑l=1Κ(ptj,l)=∑i=1m∑l=1Κωi,lt=1.由g(x)的嚴格凸函數(shù)性質(zhì),一般情況下Zt<1,故算法3是有效的.2.3結(jié)構(gòu)化集成學(xué)習算法正如不少文獻分析指出:AdaBoost和RealAdaBoost(見算法2)的權(quán)值調(diào)整,將使調(diào)整后的各類樣本的權(quán)值一樣(均勻分布),即使已知類的先驗分布,RealAdaBoost算法也只有在訓(xùn)練h1(x)時利用到該分布,即訓(xùn)練h1(x)時是針對不平衡的樣本空間,而后的訓(xùn)練皆是基于分布均勻的樣本空間進行的.對不平衡分類問題(類分布極度不平衡)應(yīng)該有不一樣的學(xué)習算法.根據(jù)前面的分析,在整個訓(xùn)練過程中,如果可以保持類分布不變,并且還能保證Zt≤1,并且一般情況下Zt<1就可以構(gòu)造出不平衡分類問題的集成學(xué)習算法.設(shè)初始類分布為{P1,…,PK},分析發(fā)現(xiàn)(隨后證明),取αtj,l=ln(ptj,l/Pl)時也滿足條件,于是可得如下的不平衡分類問題的系列化集成學(xué)習算法.算法4.不平衡分類問題的系列集成學(xué)習算法.Step1.初始化權(quán)值:ωi,l1=ωiyi,l/Z0,i=1,…,m,l=1,…,K,Z0為歸一化因子;Step2.DoFort=1,…,T1)在權(quán)值為ωi,lt的S上訓(xùn)練預(yù)測函數(shù)ht(x):①對劃分S=S1t∪…∪Sntt,計算pj,lt=∑i:(xi∈Sjt)ωi,lt;②定義ht(x):x∈Sjt,ht(x,l)=ln(ptj,l/Pl),j=1,…,nt;③選取ht(x):最小化Ζt=∑j=1nt(∏l=1Κ(ptj,l/Ρl)1/Κ)?選取ht(x).2)調(diào)整權(quán)值:ωi,lt+1=ωi,ltΖtexp(-ht(xi,l)+1Κ∑k=1Κht(xi,k)).Step3.組合預(yù)測函數(shù)f(x)輸出,(f(x,1),…,f(x,K)),其中f(x,l)=∑t=1Τht(x,l).該算法與文獻中的算法不同.類似地,對K分類問題,用(yi,1,…,yi,K)來標識xi,令yi,li=1,其余yi,l=0(l≠li),li是xi的類標簽.得到f(x)后輸出標簽Η(x)=argmaxlf(x,l),就得到一種具體的適用于不平衡分類問題的集成學(xué)習算法.當然,既然考慮了類分布,一種更合理的標識向量可以是:令yi,li=Pli,其余yi,l=0(l≠li).容易驗證,每一輪權(quán)值調(diào)整后l類樣本的權(quán)值之和為PlZt,即算法始終保持了類分布不變.算法4的有效性可證明如下:Ζt=∑j=1nt(∏l=1Κ(ptj,l/Ρl)1/Κ)≤1Κ∑j=1nt(∑l=1Κptj,l/Ρl)=1Κ∑l=1Κ(∑j=1ntptj,l)1Ρl.(12)注意到∑j=1ntptj,l=Pl,因此有Zt≤1,并且只有當ptj,k/Pk=ptj,l/Pl對所有k,l=1,…,K,j=1,…,nt都成立才有Zt=1,一般情況Zt<1,因此算法4是有效的.上面根據(jù)不同的簡單預(yù)測函數(shù)構(gòu)造策略,得到了不同的集成學(xué)習算法,其中一些正是已有的一些經(jīng)典算法.算法2～4本身仍然具有一定的通用性,故也稱它們?yōu)橄盗谢蓪W(xué)習算法.xi的標識(yi,1,…,yi,K)給不同的賦值,將得到不同的具體算法.前面只針對最常用的K分類問題指出了對示例標識的賦值方法,針對不同的問題如何給示例標識賦值,本文后面還會專門介紹.2.4有條件下,2有2.上述集成學(xué)習算法對簡單預(yù)測函數(shù)的構(gòu)造并沒有要求“比隨機猜測略好”這一限制條件,是否這一限制條件被轉(zhuǎn)換成“Zt≤1,并且一般情況下Zt<1”呢?答案是否定的.以算法2得到的RealAdaBoost算法的二分類問題(K=2),并采取二段劃分(nt=2)為例,分析如下:記εt為ht(x)的訓(xùn)練錯誤率,則εt=pt1,1+pt2,2或者εt=pt1,2+pt2,1(注意pt1,2+pt2,1+pt1,1+pt2,2=1).ht(x)比隨機猜測略好表示正確率1-εt要大于錯誤率εt,至少不能出現(xiàn)1-εt=εt,即(pt1,1+pt2,2)=(pt1,2+pt2,1).Ζt=2pt1,1pt1,2+2pt2,1pt2,2,當且僅當pt1,1=pt1,2,并且pt2,1=pt2,2時,Zt=1.顯然,如果Zt=1,則(pt1,1+pt2,2)=(pt1,2+pt2,1),而(pt1,1+pt2,2)=(pt1,2+pt2,1)不能得出Zt=1.所以算法2的有效性條件限制比“比隨機猜測略好”條件更容易滿足.更進一步,在算法2中,還允許部分Zt=1,只要一般情況下Zt<1即可,太多的Zt=1無外乎是訓(xùn)練錯誤率逐漸減小的速度慢一些而已.因此,通用集成學(xué)習算法1并不嚴格受制于弱學(xué)習定理中的“弱學(xué)習算法比隨機猜測略好”限制條件.算法1的時間復(fù)雜度與簡單預(yù)測函數(shù)的構(gòu)造方法有關(guān),如果構(gòu)造簡單預(yù)測函數(shù)的時間復(fù)雜度為O(D),則算法1的時間復(fù)雜度為O(mTD),因此,只要構(gòu)造簡單預(yù)測函數(shù)的時間復(fù)雜度不高,本文算法就是一種較快的算法.比如基于單個特征采用閾值法來構(gòu)造簡單預(yù)測函數(shù)時,算法時間復(fù)雜度就為O(mdT),其中m為訓(xùn)練樣本數(shù),d為樣本特征個數(shù),T為弱分類器的個數(shù).上述時間復(fù)雜度為學(xué)習階段的時間復(fù)雜度,而測試(預(yù)測)階段的時間復(fù)雜性顯然也直接依賴于簡單預(yù)測函數(shù).同樣,當基于單個特征采用閾值法來構(gòu)造簡單預(yù)測函數(shù)時,預(yù)測時間復(fù)雜度就為O(T).3示例標識賦值方法前面提到,對x∈X的標識Y=(y1,…,yK)給不同的賦值可得不同的學(xué)習算法.針對不同的實際需求,下面來分析如何給示例標識賦值.在構(gòu)造算法2～4時,針對K分類問題,指出了一種標識賦值方法,并由算法2得到K分類RealAdaBoost,由算法3得到K分類GentleAdaBoost,由算法4得到不平衡分類問題的集成學(xué)習算法.要清楚怎樣給示例的標識賦值,首先需要明白通用集成學(xué)習算法1的學(xué)習目的.算法1的學(xué)習目的是:希望學(xué)習所得f(x)輸出值(f(x,1),…,f(x,K))與x的標識向量(y1,…,yK)各分量大小順序一致.理解該學(xué)習目的就容易給示例標識賦值.下面介紹一些針對不同問題要求的示例標識賦值方法.3.1反擬合k分類算法設(shè)xi的類標簽為li∈{1,…,K},與前面RealAdaBoost算法相反,用(yi,1,…,yi,K)來標識xi,令yi,li=0,其余yi,l=1(l≠li).得到f(x)后輸出標簽由Η(x)=argmaxlf(x,l)改為Η(x)=argminlf(x,l),便得到一種反擬合K分類連續(xù)AdaBoost算法.由于此時H(x)≠l,當且僅當存在k∈{1,…,K}(k≠l)滿足-f(x,k)+fˉ(x)>0,于是訓(xùn)練錯誤εtri滿足:εtri=1m∑i=1m〖Η(xi)≠li〗≤1m∑i=1m∑l=1Κyi,l(F(xi,l))-1.(13)根據(jù)定理1,算法2～4都可得到相應(yīng)的訓(xùn)練錯誤率估計.比如對應(yīng)算法2的訓(xùn)練錯誤率估計為εtri≤Ζ0∏t=1Τ(Κ∑j=1nt(∏k=1Κ(ptj,k)1/Κ))?(14)其中Z0=(K-1).不難驗證,K=2時,式(14)與式(10)一樣.3.2輸出標簽算子hx對K類多標簽分類問題,設(shè)xi的類別為一個標簽子集Yi?{1,…,K},定義xi的標識向量(yi,1,…,yi,K),僅當l∈Yi時,yi,l=1,而其余yi,l=0(l?Yi),得到f(x)后輸出標簽子集H(x)={l:f(x,l)≥fˉ(x)}.也可反過來,僅當l∈Yi時yi,l=0,而其余yi,l=1(l?Yi),得到f(x)后輸出標簽子集H(x)={l:f(x,l)≤fˉ(x)}.對前者其相當于最小化訓(xùn)練錯誤:εtri=1m∑i=1m|Yi-Η(xi)|≤1m∑i=1m∑l=1Κyi,l(F(xi,l))-1?(15)此時的學(xué)習算法把本該有但沒有預(yù)測到的一個標簽算一個錯誤,可以稱之為“欠預(yù)測最小化的多標簽分類算法”.對后者,其相當于最小化訓(xùn)練錯誤:εtri=1m∑i=1m|Η(xi)-Yi|≤1m∑i=1m∑l=1Κyi,l(F(xi,l))-1?(16)此時的學(xué)習算法把過多預(yù)測的每個標簽算一個錯誤,可以稱之為“過預(yù)測最小化的多標簽分類算法”.兩種算法都可根據(jù)定理1得到訓(xùn)練錯誤率估計公式.3.3平均錯分代價估計對K類代價敏感分類問題,xi的實際標簽為li,設(shè)c(i,j)為i類被錯誤分為j類的代價損失,c(i,j)≥0,c(i,i)=0.定義xi的標識向量(yi,1,…,yi,K),其中yi,l=c(li,l),得到f(x)后輸出標簽Η(x)=argminlf(x,l).則一種平均錯分代價ccs滿足:ccs=1m∑i=1m(∑l=1Κyi,l〖Η(xi)=l〗)≤1m∑i=1m(∑l=1Κyi,l(Η(xi,l))-1).(17)根據(jù)定理1,算法2～4都可以得到相應(yīng)的平均錯分代價估計.比如算法2對應(yīng)的平均錯分代價估計為εcs≤Ζ0∏t=1Τ(Κ∑j=1nt(∏k=1Κ(ptj,k)1/Κ))?(18)其中,Ζ0=1m∑i=1Κ∑j=1Κc(i,j).根據(jù)前面的分析有如下結(jié)論:平均錯分代價εcs將隨ht(x)個數(shù)增加而減小.上述代價敏感集成學(xué)習算法屬于真正意義上的平均錯分代價最小化集成學(xué)習算法.目前已有的代價敏感集成學(xué)習算法通常把多分類問題轉(zhuǎn)換成二分類問題來處理,或者考慮其被錯分的總代價,兩者都無法區(qū)分被錯分成不同類別的代價,而真正的平均錯分代價最小化算法應(yīng)具有如下性質(zhì):即使被錯誤分類,也需分為錯分代價較小的類,即當H(xi)≠li時,希望輸出類H(xi)滿足c(li,H(xi))較小.3.4k維向量zx,1,1此處的模糊分類問題是指所有示例(包含樣本自身)具有模糊性的分類問題.xi屬于類標簽l的置信度為yi,l,則直接用K維向量(yi,1,…,yi,K)來標識xi,得到f(x)后的輸出仍然是模糊的,輸出為(f(x,1),…,f(x,K))或歸一化的(f′(x,1),…,f′(x,K)),其中f′(x,l)=f(x,l)/(Κfˉ(x))?l=1,?,Κ.4基于單特征閾值法構(gòu)造簡單預(yù)測函數(shù)算法1對簡單預(yù)測函數(shù)的構(gòu)造沒有特殊限制,在構(gòu)造算法2～4時,對能實現(xiàn)示例空間某種劃分的預(yù)測函數(shù),算法給出了簡單預(yù)測函數(shù)的輸出公式.下面分析這種簡單預(yù)測函數(shù)的構(gòu)造方法.由于組合預(yù)測函數(shù)的泛化能力與簡單預(yù)測函數(shù)密切相關(guān),只要滿足“Zt≤1,并且一般情況下Zt<1”條件,簡單預(yù)測函數(shù)應(yīng)該是越簡單越好.設(shè)x∈X有d個特征,當特征為數(shù)字型,可采用閾值法來劃分示例空間,單閾值可實現(xiàn)兩段劃分,n個閾值可實現(xiàn)n+1段劃分.于是,構(gòu)造簡單預(yù)測函數(shù)就變?yōu)闃?gòu)造劃分閾值,而“基于最小化Zt選取ht(x)”就變?yōu)樵赿個特征中,選擇可以使Zt取到最小值的特征對應(yīng)的劃分.因每一輪訓(xùn)練后樣本權(quán)值都會作調(diào)整,在計算劃分閾值時一般需引入權(quán)值.于是,有如下的簡單預(yù)測函數(shù)構(gòu)造方法(對K分類問題):計算K類樣本的均值(以樣本的權(quán)值為加權(quán)系數(shù)的加權(quán)均值),以兩兩相鄰均值之平均值作為分段閾值(共有K-1個)對示例實現(xiàn)K段劃分,在滿足“Zt≤1并且一般情況下Zt<1”條件下定義簡單預(yù)測函數(shù)的輸出值.上述方法突破了簡單預(yù)測函數(shù)個數(shù)限制,如果不引入權(quán)值,d個特征只能得到d個簡單預(yù)測函數(shù).計算K類樣本的均值方法:以樣本標識向量的第K個分量為加權(quán)系數(shù)進行加權(quán)平均.需注意劃分段數(shù)可以是任意的,K分類問題的劃分段數(shù)可不等于K.組合函數(shù)f(x,l)=∑t=1Τht(x,l),ht(x)按照上述方法來構(gòu)造時,本文算法與支持向量機(supportvectormachine,SVM)在形式上非常相似.對訓(xùn)練樣本為xi(i=1,…,m)、標簽為yi∈{1,-1}的分類問題,SVM得到的分類函數(shù)為sgn(yi(wxi+b)),這相當于先通過學(xué)習得到特征的組合系數(shù)w=(w1,…,wd)和分類閾值b,然后構(gòu)造分類函數(shù)sgn(yi(wxi+b)).而本文算法則是先學(xué)習單個特征的分類閾值得到預(yù)測函數(shù)ht(x),然后再進行組合.顯然,當示例的特征是非數(shù)字型的,SVM的先進行特征組合后構(gòu)造分類器將無法操作,而本文的先構(gòu)造分類器后進行組合則是可行的,因為對非數(shù)字型特征,依據(jù)單個特征可容易實現(xiàn)示例空間的劃分.基于單特征閾值法構(gòu)造的簡單預(yù)測函數(shù),其組合預(yù)測函數(shù)不易出現(xiàn)過學(xué)習,具體分析如下:首先來分析組合預(yù)測函數(shù)對示例空間是如何分割的.考慮d=2、示例為二維空間的點.單特征閾值法構(gòu)造簡單預(yù)測函數(shù)相當于將示例向各個坐標軸進行投影,基于投影后的示例計算閾值來構(gòu)造簡單預(yù)測函數(shù).因此,簡單預(yù)測函數(shù)將用垂直于坐標的一條直線(2段劃分)或多條直線(多段劃分)分割整個二維空間,而組合預(yù)測函數(shù)將把二維空間劃分為一些不重疊的矩形區(qū)域(邊界矩形區(qū)域的長或?qū)捒蔀闊o窮大),并且矩形邊平行于坐標軸.組合預(yù)測函數(shù)對同一矩形區(qū)域內(nèi)的示例輸出相同值,對分類問題,相當于對各矩形區(qū)域進行分類.d>2的高維空間的劃分就對應(yīng)為高維空間的“矩形區(qū)域”.先從預(yù)測函數(shù)的穩(wěn)定性來分析.組合預(yù)測函數(shù)對示例空間的劃分是邊平行于坐標的矩形區(qū)域,當示例的某些特征值發(fā)生變化時,只要這種變化不會導(dǎo)致其落入另一矩形區(qū)域,則組合預(yù)測函數(shù)輸出值都是不變的.除正好位于矩形區(qū)域邊界上的示例外(相對整個空間非常少),幾乎所有示例的特征值發(fā)生小的變化都不會影響組合預(yù)測函數(shù)的輸出,而且矩形區(qū)域特性決定了允許多個特征同時有小的變化而不改變輸出結(jié)果,這表明組合預(yù)測函數(shù)的輸出是很穩(wěn)定的,輸出穩(wěn)定的預(yù)測函數(shù)是不易出現(xiàn)過學(xué)習的.還可以從VC維來分析.考慮二分類問題,簡單預(yù)測函數(shù)采取二段劃分,則每個簡單預(yù)測函數(shù)將把示例空間分割成兩部分,簡單預(yù)測函數(shù)最多能打散2個樣本.如果基于每個特征最多構(gòu)造一個簡單預(yù)測函數(shù),組合分類器f(x)最多能打散d+1個樣本,按照VC維的定義,f(x)的VC維將小于d+1.我們知道,d維實數(shù)空間的線性分類器的VC維為d+1,因此,基于單特征閾值法構(gòu)造簡單預(yù)測函數(shù)時,f(x)的VC維數(shù)一般情況下并不比線性分類器的VC維數(shù)大.SVM具有較強的泛化能力,屬于一種線性分類器,因此單特征閾值法構(gòu)造簡單預(yù)測函數(shù)時,其組合預(yù)測函數(shù)應(yīng)該有較強泛化能力,即不易出現(xiàn)過學(xué)習.需要指出的是,算法1對簡單預(yù)測函數(shù)的構(gòu)造并無特殊限制,可以基于SVM方法、神經(jīng)網(wǎng)絡(luò)方法、特征組合方法等.從使用簡單和好的泛化能力考慮,可統(tǒng)一基于單個特征的簡單劃分法來構(gòu)造簡單預(yù)測函數(shù),而通過增加簡單預(yù)測函數(shù)個數(shù)來降低訓(xùn)練錯誤率,這樣就又不必耽心出現(xiàn)過學(xué)習現(xiàn)象.5實驗與分析5.1實驗數(shù)據(jù)與結(jié)果分析本文提出的算法更多地體現(xiàn)在對一大類AdaBoost系列算法進行統(tǒng)一,而AdaBoost系列算法早已得到成功應(yīng)用,因此,實驗主要集中在對以下問題進行驗證:1)不平衡分類問題集成學(xué)習算法是否更有效;2)提出的集成學(xué)習算法是否不易出現(xiàn)過學(xué)習;3)反擬合K分類連續(xù)AdaBoost算法是否有效,K分類GentleAdaBoost算法是否有效.實驗數(shù)據(jù)一般應(yīng)來自于公共實驗數(shù)據(jù)集,因每個實驗數(shù)據(jù)都具有其特定的數(shù)據(jù)規(guī)律,不管基于多少數(shù)據(jù)實驗,都只能得到一種統(tǒng)計意義上的結(jié)論.基于此,本文實驗除采用公共UCI的Ionosphere(2類)和Wine(3類)數(shù)據(jù)外,采用了一種隨機數(shù)據(jù)集,隨機數(shù)據(jù)一般具有更強的代表性.實驗數(shù)據(jù)如表1所示:Ionosphere:采取減少前n個樣本(1類和2類同時被減少)來調(diào)整類分布以模擬不平衡分類.Wine:采取減少第3類樣本(第1類和第2類始終不變)來調(diào)整類分布以模擬不平衡分類.Random1:由取值于的隨機函數(shù)生成,隨機賦予類標簽,調(diào)整類比率來模擬不平衡分類.Random2:類似Random1隨機生成,但對1～3類樣本各分量分別乘以1,2,3.同比例(60:40)對實驗數(shù)據(jù)集進行隨機劃分得到訓(xùn)練集和測試集,基于訓(xùn)練集訓(xùn)練得到組合預(yù)測函數(shù)后對測試集進行測試并統(tǒng)計錯誤率.為驗證算法的適應(yīng)性,采取多次實驗(20次)統(tǒng)計平均錯誤率.二分類問題的弱分類器采用2段劃分,三分類問題的弱分類器采取5段劃分:第4節(jié)介紹的方法得到2個劃分閾值和3個類均值后,統(tǒng)計其兩兩相鄰值之平均得4個值,以此為閾值可實現(xiàn)5段劃分.對RealAdaBoost系列算法的邊界處理方式見文獻,即對Zt用1+ptj,l代替ptj,l.對二分類問題還采用xi的類別標簽對應(yīng)分量為其初始類分布概率(比率),其余分量為0的向量來標識xi.實驗結(jié)果如表2～6所示:5.2不平衡分類問題的集成學(xué)習算法更有效先分析表2數(shù)據(jù).看第1個實驗數(shù)據(jù),P1=0.641,P2=0.359,T=30,A1,A2的測試錯誤率分別為0.1893,0.1825