一種通用的集成學習算法

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