孫 濤，周志華

南京大學(xué) 計算機(jī)軟件新技術(shù)國家重點實驗室，南京 210023

1 引言

集成學(xué)習(xí)（ensemble learning）[1]是一類著名的機(jī)器學(xué)習(xí)[2]方法，通過構(gòu)建并結(jié)合多個學(xué)習(xí)器來完成學(xué)習(xí)任務(wù)，常可獲得比單一學(xué)習(xí)器顯著優(yōu)越的泛化性能。要構(gòu)建一個泛化性能好的集成，一方面需要考慮集成中個體學(xué)習(xí)器的性能，另一方面更重要的是考慮學(xué)習(xí)器之間的差異性，即集成多樣性（ensemblediversity）[1,3-5]。

如何理解和度量多樣性是集成學(xué)習(xí)中非?；A(chǔ)但尚未解決的問題[1,3]。傳統(tǒng)方法考慮學(xué)習(xí)器在數(shù)據(jù)集上預(yù)測結(jié)果之間的差異，相應(yīng)地提出了很多多樣性度量指標(biāo)，例如不合度[6]、κ-統(tǒng)計量[7]、K-W 方差[8]等，但這些度量的有效性存在質(zhì)疑[5,9]；Sun和Zhou[10]提出應(yīng)同時考慮學(xué)習(xí)器預(yù)測結(jié)果和學(xué)習(xí)器結(jié)構(gòu)的差異；Brown[11]最早從信息論角度探討了集成多樣性，揭示了集成多樣性中復(fù)雜的高階相關(guān)性。

多元信息多樣性（multi-information diversity）[12]基于信息論來刻畫集成多樣性，其在實際中面臨的困難是高階信息通常難以估計，需要做低階近似。聯(lián)結(jié)樹是圖模型推斷[13]中一種廣泛有效的方法，利用聯(lián)結(jié)樹可以尋找高維分布的最優(yōu)低維近似[14-15]。本文基于k階t-cherry聯(lián)結(jié)樹[15-16]提出了新的多元信息多樣性的低階近似方法，合成數(shù)據(jù)和真實數(shù)據(jù)上的實驗驗證了同階近似下，該近似估計方法優(yōu)于現(xiàn)有方法。

本文組織結(jié)構(gòu)如下：第2章簡要介紹研究背景；第3章提出基于聯(lián)結(jié)樹的多元信息多樣性近似估計方法；第4章對近似估計方法進(jìn)行實驗測試；第5章是結(jié)束語。

2 研究背景

2.1 信息論基本概念

信息論[17-18]的基礎(chǔ)是隨機(jī)變量的熵，對于變量X，熵度量了其分布的不確定程度。兩個變量X和Y之間的相關(guān)性可以通過互信息刻畫。多個變量之間的“互信息”有多種不同的定義方式，使用X1:n表示變量X1,X2,…,Xn，多元信息（multi-information）[19-20]定義為：

互作用信息（interactioninformation）[21]遞歸定義為：

類似地，可以定義條件多元信息和條件互作用信息。兩種多元“互信息”都可以用于度量多個變量共有的信息量，但它們度量的對象不同。多元信息總是非負(fù)，但互作用信息正負(fù)都有可能。

2.2 信息理論多樣性

Brown[11]最早從信息論的角度探討了集成多樣性。給定一組分類器輸出X1:m={X1,X2,…,Xm}和目標(biāo)類別Y，根據(jù)X1:m預(yù)測Y的誤差被如下兩個緊的界限制住[22-23]：

其中，I(X1:m；Y)越大，則誤差下界越小，預(yù)測函數(shù)g可能取得的實際誤差越低。Brown給出如下分解式：

其中，相關(guān)性（relevancy）項度量了分類器和類別標(biāo)簽之間的相關(guān)程度，冗余性（redundancy）項度量了分類器之間的冗余程度，條件冗余性（conditional redundancy）項度量了給定類別標(biāo)簽下分類器之間的冗余程度。條件冗余性與冗余性的差被稱為信息理論多樣性（information theoretic diversity），兩者分別按照變量互作用的階數(shù)展開。高階互作用信息通常難以估計，Brown采取的策略是只保留二階互作用信息，但在實際中由于集成中分類器通常比較相似，高階互作用信息的幅值通常不能忽略，其項數(shù)也隨著階數(shù)指數(shù)增長。

2.3 多元信息多樣性

Zhou和Li[12]基于多元信息提出了一個分解式：

他們證明了式（4）和式（5）在數(shù)學(xué)上是等價的，但后者將多樣性更加簡潔地表達(dá)為兩個多元信息的差，并按照分類器依次展開。I(Xi；X1:i-1|Y)和I(Xi；X1:i-1)分別度量了當(dāng)前分類器Xi和已有分類器X1:i-1的條件冗余性和冗余性，兩者的差值度量了其對集成多樣性的貢獻(xiàn)值。

多元信息多樣性的估計可以通過分別估計冗余性和條件冗余性得到。對于冗余性，可以估計每一個分量I(Xi；X1:i-1)，但當(dāng)i比較大時，X1:i-1對應(yīng)分布的維度較高，直接估計互信息會面臨高維離散變量分布估計難題[24]，Zhou和Li提出的MTIk方法采取的策略是對高階互信息做低階近似，具體地，其中Ωk是集合大小為k的子集。令，則，其中KL[?||?]是 Kullback-Leibler距離。該近似值總是不大于真實值，容易證明k越大則越接近真實值。I(Xi；Ωk)可以直接從數(shù)據(jù)集中估計得到，同理可以得到條件冗余性和多元信息多樣性的近似估計。

2.4 k階t-cherry聯(lián)結(jié)樹

概率圖模型（probabilistic graphical models）[13]使用圖來表示變量之間的關(guān)系。N個變量X1,X2,…,XN存在聯(lián)合分布p(X1,X2,…,XN)，當(dāng)N很大時，直接計算該聯(lián)合分布代價很高。聯(lián)結(jié)樹（junction tree）算法使用一些隨機(jī)變量子集的邊緣分布來近似聯(lián)合分布，可以降低計算量[14-15]。對于一棵定義在X={X1,X2,…,XN}上的聯(lián)結(jié)樹，其每個結(jié)點對應(yīng)X的一個子集XC，稱為一個簇，每條邊對應(yīng)相鄰兩個結(jié)點上簇的交集，稱為一個分離集，并滿足連接包含同一個隨機(jī)變量的兩個簇的路徑上的所有簇都包含該變量，所有簇的并集是X。聯(lián)結(jié)樹定義了X的一個概率分布：

其中，νS是包含S中所有變量的結(jié)點個數(shù)。容易證明該近似分布和真實分布的KL距離為：

故權(quán)重項（weight）越大則近似誤差越小。

k階t-cherry聯(lián)結(jié)樹是一種特殊的聯(lián)結(jié)樹[15-16]，其每個簇包含k個變量，每個分離集包含k-1個變量。在所有結(jié)點至多包含k個變量的聯(lián)結(jié)樹中，具有最大權(quán)重值的k階t-cherry聯(lián)結(jié)樹是真實分布的最優(yōu)近似[15]。構(gòu)建具有最大權(quán)重值的樹是NP-hard問題[15]。算法1給出了一種貪心構(gòu)建算法[16]，其中表T列出了所有對可能的簇-分離集組合，假設(shè)第i項對應(yīng)簇C'和分離集S'，則其3個分量分別為T(i,1)=C'S',T(i,2)=S',T(i,3)=I(XC')-I(XS')，V用于標(biāo)識一個變量是否存在于已經(jīng)構(gòu)建的簇中。表T中的所有項根據(jù)每一項第3個分量，即權(quán)重值，從大到小排序。

算法1k階t-cherry聯(lián)結(jié)樹貪心構(gòu)建算法

3 基于聯(lián)結(jié)樹的近似多元信息

多元信息多樣性估計的困難之處在于其高階信息涉及高階分布通常難以直接估計。本文提出基于聯(lián)結(jié)樹對高階分布做低階近似，從而實現(xiàn)對多元信息及其分量的近似估計。本章后續(xù)主要討論冗余性I(X1:m)的近似估計，條件冗余性I(X1:m|Y)和多元信息多樣性I(X1:m|Y)-I(X1:m)可以很自然地采用類似的方法近似估計。

3.1 直接近似估計多元信息

考慮基于聯(lián)結(jié)樹直接近似估計多元信息I(X1:m)。假設(shè)真實的聯(lián)合分布為p(X1:m)，基于聯(lián)結(jié)樹定義的聯(lián)合分布為pJT(X1:m)，使用基于聯(lián)結(jié)樹定義的聯(lián)合分布替代真實的聯(lián)合分布得到近似多元信息IJT(X1:m)，其近似誤差為：

故近似值IJT(X1:m)總是不大于真實值I(X1:m)。將式（6）和式（7）代入上式，從而：

式中，權(quán)重項（weight）越大，則近似多元信息IJT(X1:m)越接近真實的多元信息I(X1:m)。注意到式（8）中，近似多元信息IJT(X1:m)中的對數(shù)項仍然是關(guān)于真實分布p(X1:m)求期望的，相應(yīng)式（9）中得到的I(XC)和I(XS)通?？梢詮臄?shù)據(jù)集中直接估計得到。

為了得到更準(zhǔn)確的估計值，使用算法1構(gòu)建一棵權(quán)重值盡可能大的k階t-cherry聯(lián)結(jié)樹并得到近似聯(lián)合分布pJT(X1:m)，相應(yīng)的多元信息近似估計方法簡記為CTk-1，其中變量的最大相關(guān)性階數(shù)為k。因為一棵k-1階t-cherry聯(lián)結(jié)樹可以轉(zhuǎn)化成一棵k階tcherry聯(lián)結(jié)樹，且轉(zhuǎn)化之后權(quán)重值不降[15-16]，CTk-1的估計值通常隨著k增大而更接近真實值。

注意到在 MTIk方法中，I(Xi；Ωk)=I(Xi?Ωk)-I(Ωk)，剛好相當(dāng)于采用貪心策略最大化式(9)中的權(quán)重，但區(qū)別在于當(dāng)k≥2時，最優(yōu)的Ωk并不一定滿足聯(lián)結(jié)樹中分離集的要求，因而該方法并不一定對應(yīng)一種合法的近似聯(lián)合分布形式。相同k階變量相關(guān)性條件下，MTIk-1共計比較了個量，CTk-1共計比較了個量，比較的量的個數(shù)相當(dāng)，但后者得到的估計值通常更優(yōu)。

3.2 近似估計多元信息分量

考慮基于聯(lián)結(jié)樹近似估計每一個分量I(Xi；X1:i-1)。假設(shè)真實的聯(lián)合分布為p(X1:i-1)，條件聯(lián)合分布為p(X1:i-1|Xi)，基于聯(lián)結(jié)樹定義的聯(lián)合分布為pJT(X1:i-1)，條件聯(lián)合分布為pJT(X1:i-1|Xi)。使用基于聯(lián)結(jié)樹定義的分布替代真實分布得到近似分量IJT(Xi；X1:i-1)，其近似誤差為：

下面討論該近似誤差的正負(fù)性?；诼?lián)結(jié)樹的性質(zhì)，pJT(X1:i-1)可以表示為：

其中，σ是[1,2,…,j-1]的某種排列，Ωσj?{X1:σj-1}。例如p(X1,2)p(X2,3)/p(X2)=p(X2)p(X1|X2)p(X3|X2)。同理，pJT(X1:i-1|Xi)可以表示為：

將式（11）～式（14）代入式（10），得到：

考慮第j項，寫成期望形式：

基于上文分析，為了得到更接近真實值的估計結(jié)果，在使用算法1對每個分量構(gòu)建k階t-cherry聯(lián)結(jié)樹時，將表T的權(quán)重項設(shè)置為T(i,3)=H(XC')-H(XS')-H(XC'|Xi)+H(XS'|Xi)，并按照權(quán)重值由小到大排序，相應(yīng)的多元信息近似估計方法簡記為CTSk。類似于MTIk，給定變量Xi其余變量的最大相關(guān)性階數(shù)為k，完整分布的最大相關(guān)性階數(shù)為k+1。

3.3 兩種近似估計方法分析

多元信息可以表示為：

對于基于聯(lián)結(jié)樹直接近似估計多元信息方法，不失一般性地（否則重新定義變量的序號），設(shè)得到的聯(lián)合分布可以表示為：

相應(yīng)的多元信息近似為：

可以看出，該方法是使用p(xi|ωi)近似p(xi|x1:i-1)，因為條件變量減少可能會導(dǎo)致條件熵增加，相應(yīng)的多元信息估計值可能會小于真實值。

對于基于聯(lián)結(jié)樹近似估計多元信息分量方法，相應(yīng)的多元信息估計為：

可以看出，該方法是使用pJT(x1:i-1|xi)近似p(x1:i-1|xi)，使用pJT(x1:i-1)近似p(x1:i-1)，根據(jù)上一節(jié)的分析，相應(yīng)的多元信息近似值通常大于真實值。分子和分母上兩個分布同時做了近似，但無法保證兩者的近似誤差可以抵消。

計算Xi和X1:i-1之間互信息I(Xi；X1:i-1)，即Xi的熵和X1:i-1的熵的公共部分，困難之處在于X1:i-1中各個變量存在相關(guān)性，其熵并不簡單地是i-1個變量的熵的和。兩種方法都是在試圖近似X1:i-1的熵，前一種方法是試圖從下界近似，更適合X1:i-1中變量相關(guān)性較強(qiáng)的情況，此時只需要較少的變量Ωi就可以比較好地近似X1:i-1的熵；而后一種方法是試圖從上界近似，更適合X1:i-1中變量相關(guān)性較弱的情況，此時使用pJT(x1:i-1|xi)近似p(x1:i-1|xi)和使用pJT(x1:i-1)近似p(x1:i-1)的誤差相對較低。為了得到更準(zhǔn)確的估計結(jié)果，可以結(jié)合兩種方法，利用構(gòu)建的聯(lián)結(jié)樹分析X1:i-1中變量的相關(guān)程度，并選擇更合適的近似估計方法。

4 實驗測試

4.1 合成數(shù)據(jù)

為了對比不同的近似估計方法，首先在合成數(shù)據(jù)上比較各種方法對多元信息的近似估計值與真實值的差別。假設(shè)a、b和c是三個獨立均勻分布的0-1隨機(jī)變量，生成第一組變量：

因為a和b只有四種不同組合，所以X1:4最多只有四種可能取值。以2為對數(shù)函數(shù)底數(shù)，容易算出真實的I(X1:4)=H(X1)+H(X2)+H(X3)+H(X4)-H(X1:4)=1.811 3。MTI1近似估計值為0.331 3，MTI2為1.811 3，CT1為0.933 8，CT2為1.811 3，CTS2為2.311 3，Brown1為0.933 8，Brown2為2.500 0?？梢钥闯?，MTI2和 CT2均得到了正確的結(jié)果，CTS2的估計值大于真實值。

生成第二組變量：

因為a、b和c只有八種不同組合，所以Y1:5最多只有八種可能取值。以2為對數(shù)函數(shù)底數(shù)，容易算出真實的I(Y1:5)=1.666 1。MTI1近似估計值為0.916 1，MTI2為1.571 8，CT1為1.227 4，CT2為1.666 1，CTS2為1.571 8，Brown1為1.870 6，Brown2為1.739 9?？梢钥闯?，只有CT2得到了正確的結(jié)果，實驗中條件互作用信息出現(xiàn)為正的情況，導(dǎo)致CTS2估計值小于真實值。與第一組變量相比，第二組變量有三個自由分量，變量之間的關(guān)系也更加復(fù)雜。

4.2 真實數(shù)據(jù)

使用真實的UCI breast-cancer數(shù)據(jù)集構(gòu)建分類器集成，并用于比較不同方法對多元信息多樣性的近似估計結(jié)果。將數(shù)據(jù)集劃分為2/3訓(xùn)練集和1/3測試集，重復(fù)50次不同劃分，選擇決策樹樁作為基分類器，使用Bagging和Boosting算法分別在訓(xùn)練集上構(gòu)建大小為31的集成，并在測試集樣本上計算集成中分類器的輸出結(jié)果。

表1列出了不同近似估計方法對集成冗余性的平均估計值?？梢钥闯鯩TI、CT和CTS的估計值很接近，Brown的估計發(fā)散，原因是當(dāng)分類器性能接近時，Brown方法中的高階互作用信息項幅值并不能忽略，并且其項數(shù)隨著相關(guān)變量階數(shù)增大而指數(shù)增加。CT的估計值略高于MTI，CTS的估計值略高于MTI和CT，與之前MTI和CT對多元信息的估計值通常小于真實值，CTS對多元信息的估計值通常大于真實值的分析結(jié)論相符。

Table 1 Average redundancy by compared estimation methods表1 不同近似估計方法對冗余性的平均估計值

表2列出了不同近似估計方法對集成多元信息多樣性的平均估計值。多元信息多樣性是條件冗余性和冗余性兩個多元信息的差值，可以看出類似集成冗余性，MTI、CT和CTS的估計值很接近，Brown的估計值發(fā)散。

Table 2 Average multi-information diversity by compared estimation methods表2 不同近似估計方法對多元信息多樣性的平均估計值

Fig.1 Curves of test error,relevancy and diversity of Bagging圖1 Bagging集成測試誤差、相關(guān)性和多樣性變化曲線

Fig.2 Curves of test error,relevancy and diversity of Boosting圖2 Boosting集成測試誤差、相關(guān)性和多樣性變化曲線

將集成大小設(shè)為3到21，圖1和圖2分別繪出了Bagging和Boosting算法生成集成的測試誤差、相關(guān)性和三種近似估計方法得到的平均多元信息多樣性隨集成大小變化曲線。為了對比不同的集成大小，圖中的相關(guān)性項已經(jīng)除過集成大小m，多樣性項Brown1除過m×(m-1)/2，CT1和 CTS2除過m-1。從圖中可以看出，Bagging生成的集成具有較高的相關(guān)性和較低的多樣性；Boosting生成的集成隨著集成大小增大，相關(guān)性在下降，平均多樣性在上升，三種近似估計方法得到的近似結(jié)果變化趨勢一致。

5 結(jié)束語

本文提出了一種基于聯(lián)結(jié)樹的多元信息多樣性近似估計方法，合成數(shù)據(jù)和真實數(shù)據(jù)上的實驗表明，同階近似下該估計方法優(yōu)于現(xiàn)有估計方法。

聯(lián)結(jié)樹的構(gòu)建使用了貪心策略，對于更高階近似，算法的時間開銷比較大。一種可能的方案是利用得到的聯(lián)結(jié)樹對分類器進(jìn)行聚類，分析簇內(nèi)和簇間的多樣性以降低問題的復(fù)雜度，這是本文的一個未來工作。