基于信息熵抽樣估計的統(tǒng)計學(xué)習(xí)查詢策略

曲豫賓，陳 翔

傳統(tǒng)有監(jiān)督學(xué)習(xí)是使用標(biāo)記數(shù)據(jù)集訓(xùn)練模型，然而標(biāo)記數(shù)據(jù)集有時候需要花費(fèi)大量時間與成本，主動學(xué)習(xí)［1］框架通過在未標(biāo)注數(shù)據(jù)集中選擇少量示例進(jìn)行標(biāo)注，達(dá)到較好的分類效果.基于池的主動學(xué)習(xí)查詢策略大致可以劃分為基于異構(gòu)標(biāo)準(zhǔn)的樣例選擇策略、基于性能的樣例選擇策略、混合選擇策略等［2］.基于異構(gòu)標(biāo)準(zhǔn)的樣例選擇策略包括Uncertainty Sampling，Query-By-Committee，Expected Model Change［1］等；基于性能的樣例選擇策略包括ExpectedErrorReduction，Variance Reduction；混合選擇策略包括Density-Weighted Methods，QUIRE等幾種.常見用于分類的模型包括樸素貝葉斯、隨機(jī)森林、支持向量機(jī)等.

本文重點(diǎn)關(guān)注基于統(tǒng)計學(xué)習(xí)的主動學(xué)習(xí)查詢策略，該類策略是從影響主動學(xué)習(xí)的分類性能出發(fā)選擇標(biāo)注樣例.同時關(guān)注基于信息異構(gòu)的主動學(xué)習(xí)查詢策略.

Uncertainty Sampling基于不確定度的角度來選擇未標(biāo)注樣例，實(shí)踐中發(fā)現(xiàn)該策略具有較強(qiáng)的魯棒性，但是存在異常點(diǎn)選擇的問題；Query-By-Committee維護(hù)分類器集合，根據(jù)不同分類器的不一致性作為選擇未標(biāo)注樣例的標(biāo)準(zhǔn)，常見的評價標(biāo)準(zhǔn)包括VoteEntropy，Killback-Leibler divergence［1］等，該策略本質(zhì)上是一種通過對假設(shè)空間的收縮來實(shí)現(xiàn)樣例選擇；Expected Model Change策略使用決策信息論的方法選擇對模型影響最大的未標(biāo)注實(shí)例；Expected Error Reduction是基于統(tǒng)計學(xué)習(xí)理論直接計算未標(biāo)注樣例的不同標(biāo)注帶來的期望風(fēng)險，根據(jù)期望風(fēng)險最小化準(zhǔn)則來選擇未標(biāo)注樣例，該策略優(yōu)點(diǎn)是根據(jù)樣例直接計算優(yōu)化損失函數(shù)，但存在計算復(fù)雜度較高的問題；Variance Reduction策略不是通過直接優(yōu)化期望風(fēng)險，而是間接地減少輸出方差實(shí)現(xiàn)對未標(biāo)注樣例選擇；Density-Weighted Methods在考慮未標(biāo)注樣例信息量的同時考慮未標(biāo)注樣例的代表性，對信息量與代表性施以不同的權(quán)重，根據(jù)權(quán)重值選擇樣例.HUANG S J等人［3］結(jié)合支持向量機(jī)提出的QUIRE算法也屬于此類，在多個領(lǐng)域具有較好的分類效果，然而存在計算復(fù)雜度較高的問題.

使用統(tǒng)計學(xué)習(xí)的方法選擇未標(biāo)注樣例得到了深入的研究.MACKAY D、COHN D A等人［4-5］提出使用統(tǒng)計學(xué)習(xí)的方法來優(yōu)化目標(biāo)函數(shù)，使用前饋神經(jīng)網(wǎng)絡(luò)等分類器來創(chuàng)建模型.ROY N等人［6］提出直接使用最小化期望風(fēng)險函數(shù)的統(tǒng)計學(xué)習(xí)方法來選擇未標(biāo)注樣例，但該方法仍然存在計算信息量較大的問題.WANG Z等人［7］通過極小化經(jīng)驗(yàn)風(fēng)險選擇信息量大及有代表性的未標(biāo)注樣例.TANG Y P等人［8］引入自步學(xué)習(xí)選擇易分類的未標(biāo)注實(shí)例，同時選擇符合信息量大等特征，有潛在價值的未標(biāo)注實(shí)例，取得了較好的分類效果.

目前，ZHU X J等人［9-10］提出了使用概率圖模型優(yōu)化期望風(fēng)險函數(shù)，在優(yōu)化的同時使用半監(jiān)督學(xué)習(xí)來減少標(biāo)注量，取得了不錯的分類效果.GAD E E等人［11］從標(biāo)注數(shù)據(jù)集中引入先驗(yàn)信息，使用概率圖模型做樣例選擇.這些查詢策略從概率圖模型角度去選擇樣例，為主動學(xué)習(xí)研究提供了新的視角.

為了解決隨機(jī)采樣的性能不穩(wěn)定問題，以及計算復(fù)雜度過高等問題，本文提出使用信息熵作為衡量標(biāo)準(zhǔn)對未標(biāo)注樣例進(jìn)行選擇，對選擇的樣例子集合計算平均期望風(fēng)險，選擇使得平均期望風(fēng)險最小的樣例進(jìn)行標(biāo)注.在真實(shí)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明該策略與基準(zhǔn)策略相比，時間復(fù)雜度較低，有效性較高.

1 基于信息熵的期望誤差減少抽樣估計的主動學(xué)習(xí)查詢策略

基于信息熵的期望誤差減少抽樣估計的主動學(xué)習(xí)（Active Learning through sampling estimation of Expected Error Reduction based on Information Entropy，ALEERIE），該主動學(xué)習(xí)查詢策略的提出是基于看待數(shù)據(jù)的角度不同，使用期望誤差減小的統(tǒng)計模型選擇查詢樣例偏向于整體數(shù)據(jù)分布，而信息熵關(guān)注的是單獨(dú)樣例的信息量.基于信息熵的不確定度采樣策略在選擇特定樣例過程中要有較強(qiáng)的有效性和魯棒性，因此可以結(jié)合兩種策略制定混合式的主動學(xué)習(xí)查詢策略.

基于統(tǒng)計學(xué)習(xí)的學(xué)習(xí)策略需要循環(huán)遍歷整個未標(biāo)注數(shù)據(jù)集，因此存在計算復(fù)雜度比較高的問題，具體復(fù)雜度是O(N2)，而在基于信息熵的期望誤差減少抽樣估計的主動學(xué)習(xí)中，使用基于信息熵的抽樣估計以后，復(fù)雜度可以降低為O(Q×N).N表示未標(biāo)注樣例的總數(shù)，Q表示使用信息熵進(jìn)行抽樣估計的數(shù)目.

ROY N等人［6］提出使用統(tǒng)計學(xué)習(xí)中最小化期望風(fēng)險的辦法來選擇未標(biāo)注樣例.使用主動學(xué)習(xí)框架建立的最佳分類器應(yīng)該是選擇未標(biāo)注實(shí)例以后，人工標(biāo)注實(shí)例并將其加入到訓(xùn)練數(shù)據(jù)集，在該訓(xùn)練數(shù)據(jù)集訓(xùn)練模型時能夠減少期望風(fēng)險，具有最佳的泛化能力.

設(shè)訓(xùn)練樣例x∈D=Rn，實(shí)例的標(biāo)記為y∈Y={y1,y2,…,yk}，對訓(xùn)練樣例x的條件概率分布為P(y|x)，該分布未知.已標(biāo)注樣例集合D采用獨(dú)立同分布采樣，其聯(lián)合概率分布P(x,y)=P(y|x)P(x)，對輸入樣例x，則生成后驗(yàn)概率(y|x)，因此基于統(tǒng)計學(xué)習(xí)的期望風(fēng)險為

損失函數(shù)L用于衡量樣本(x,y)的真實(shí)概率分布P(x,y)與后驗(yàn)概率估計分布(x,y)的差值.本方法采用的損失函數(shù)為對數(shù)損失函數(shù)，

期望風(fēng)險EP?D優(yōu)化的目標(biāo)為選擇最優(yōu)未標(biāo)注樣本序列k={x1,x2,x3,…,xk}，其中k表示從未標(biāo)注樣本中采樣的次數(shù)，對于樣本序列k中的每個未標(biāo)注樣例(x*,y*)，

本策略針對基于未標(biāo)注樣例池M進(jìn)行學(xué)習(xí)，因此學(xué)習(xí)的范圍確定，對于未標(biāo)注樣例有確定的估計P(x).定義將未標(biāo)注樣例(x*,y*)加入已標(biāo)注樣例集合D產(chǎn)生的新的標(biāo)注集為D*=D+(x*,y*)，新的標(biāo)注樣例集D*的分布函數(shù)未知，為了能夠有效地計算公式（2），采用已標(biāo)注樣例集的概率分布來估計當(dāng)前未標(biāo)注樣例(x*,y*)，則當(dāng)前分類器的經(jīng)驗(yàn)風(fēng)險為

E計算出未標(biāo)注樣例x*，在y*∈Y情況下期望風(fēng)險值，y*的真實(shí)值是未知的，可以使用已知的概率分布P(x,y)，計算估計概率分布值，將不同的概率分布作為權(quán)值，計算最終期望值

該策略存在計算量過大，復(fù)雜度較高等問題.最優(yōu)未標(biāo)注樣本序列k的建立過程實(shí)際是在對未知分布進(jìn)行有選擇抽樣過程.簡單的抽樣策略是每次在未標(biāo)注實(shí)例集M循環(huán)遍歷每一個樣例，其時間復(fù)雜度為O(|M|2).可以選擇隨機(jī)采樣，或者預(yù)先過濾異常點(diǎn)等方法減少未標(biāo)注樣例的選擇范圍.

信息熵可以用于衡量未標(biāo)注樣例的不確定性，作為主動學(xué)習(xí)的策略具有較強(qiáng)的魯棒性.基于信息熵可以對集合M進(jìn)行采樣，采樣的過程是計算每個樣例的不確定度，從中選擇不確定度最高的Q個樣例.

xu,max表示從集合M中選擇的信息熵最高的樣例，以已標(biāo)注樣例結(jié)合D來計算樣例的信息熵值.根據(jù)信息熵，選擇不確定度最高的Q個樣例，對Q個樣例計算響應(yīng)的期望風(fēng)險，并選擇期望風(fēng)險值最小的樣例進(jìn)行手工標(biāo)注.算法過程如圖1所示.

圖1 基于信息熵的期望誤差減少抽樣估計的主動學(xué)習(xí)查詢策略

算法流程如下：

算法 基于信息熵抽樣估計的統(tǒng)計學(xué)習(xí)查詢策略.

①Input：初始化標(biāo)記數(shù)據(jù)集D={x1，…,xl}，未標(biāo)記數(shù)據(jù)集M={xl+1，…,xl+u}，數(shù)據(jù)標(biāo)記y1,…,yl，最大循環(huán)次數(shù)Umax.

⑥在標(biāo)記數(shù)據(jù)集上訓(xùn)練模型.

⑦在未標(biāo)記訓(xùn)練集M依據(jù)公式（6）計算相應(yīng)信息熵.

⑧選擇信息熵最大的Q個樣例.

⑨forj=1 toQdo：

⑩對樣例使用集合Y中的類別進(jìn)行標(biāo)注，分別加入到訓(xùn)練集中，重新訓(xùn)練模型，依據(jù)公式（2）計算相應(yīng)的損失函數(shù).

太和醫(yī)院始建于1965年，如今已然成長為四?。ㄊ校┙唤绲鼐C合實(shí)力最強(qiáng)的一家三級甲等醫(yī)院，醫(yī)院服務(wù)能力輻射周邊40多個縣市區(qū)。

?依據(jù)公式（4）計算相應(yīng)的經(jīng)驗(yàn)風(fēng)險函數(shù).

?根據(jù)類別的不同，依據(jù)公式（5）計算期望風(fēng)險函數(shù)的期望值.

?選擇使得期望值最小的樣例，進(jìn)行手工標(biāo)注.

?end while.

?return 條件概率分布

2 實(shí)驗(yàn)設(shè)計

為了驗(yàn)證基于信息熵抽樣估計的統(tǒng)計主動學(xué)習(xí)策略的有效性，與隨機(jī)采樣過程在多個數(shù)據(jù)集上進(jìn)行了對比.隨機(jī)采樣過程從未標(biāo)記實(shí)例中隨機(jī)選擇若干樣例，選擇使得期望風(fēng)險最小的樣例進(jìn)行手工標(biāo)注.

實(shí)驗(yàn)數(shù)據(jù)來自于加州大學(xué)歐文分校提出的用于機(jī)器學(xué)習(xí)的數(shù)據(jù)集.選擇其中的tic-tac-toe、transfusion、kr-vs-kp、diagnosis、breast-cancer用于二分類的數(shù)據(jù)集，該部分?jǐn)?shù)據(jù)集經(jīng)常用于主動學(xué)習(xí)查詢策略的研究［8］，具體的數(shù)據(jù)集描述見表1.

表1 實(shí)驗(yàn)中用到的數(shù)據(jù)集

實(shí)驗(yàn)數(shù)據(jù)采用分層抽樣對數(shù)據(jù)集進(jìn)行劃分，50%用于訓(xùn)練數(shù)據(jù)，50%用于測試數(shù)據(jù)，從訓(xùn)練數(shù)據(jù)中取出10%作為初始標(biāo)注數(shù)據(jù)集，用于建立模型.實(shí)驗(yàn)隨機(jī)重復(fù)執(zhí)行5次，采用交叉驗(yàn)證，因此數(shù)據(jù)集產(chǎn)生5×2組數(shù)據(jù)，取所有數(shù)據(jù)的平均值為該標(biāo)注數(shù)據(jù)點(diǎn)的預(yù)測結(jié)果.

實(shí)驗(yàn)過程中使用sklearn工具包，分類器選擇隨機(jī)森林分類器與logistics回歸分類器，參數(shù)使用系統(tǒng)默認(rèn)參數(shù).分類器的超參數(shù)優(yōu)化對學(xué)習(xí)策略的影響在后期的工作中會繼續(xù)研究.UCI數(shù)據(jù)集中的類別數(shù)據(jù)轉(zhuǎn)換通過sklearn的LabelEncoder類來實(shí)現(xiàn)類標(biāo)的編碼，將屬性轉(zhuǎn)換為對應(yīng)的整數(shù)值.從未標(biāo)注實(shí)例中選擇子集需要設(shè)定超參數(shù)Q，超參數(shù)Q表示從未標(biāo)注實(shí)例集中抽樣的數(shù)目，在本策略中，設(shè)定Q為20.

算法的評價指標(biāo)采用ACCURACY，表示真正例與真負(fù)例與所有樣例總和的比值.常見的性能評價指標(biāo)還有AUC、F1-Measure等，此次實(shí)驗(yàn)選擇的數(shù)據(jù)集，不存在明顯的類不平衡問題，因此主要在ACCURACY指標(biāo)上做性能評價.分類結(jié)果的混淆矩陣如表2所示［12］.

表2 分類結(jié)果混淆矩陣

ACCURACY表示分類模型總體判斷的準(zhǔn)確率，是涵蓋了所有分類的總體準(zhǔn)確率.

3 結(jié)果分析

3.1 標(biāo)記實(shí)例的數(shù)量對策略性能的影響

在數(shù)據(jù)集tic-tac-toe、transfusion、kr-vs-kp、diagnosis、breast-cancer中兩種待比較算法隨著標(biāo)注樣例的增加性能變化如圖（2）、圖（3）、圖（4）、圖（5）、圖（6）所示.采用隨機(jī)森林作為數(shù)據(jù)集的分類模型，隨后將會考慮其他分類器，以驗(yàn)證所提的主動學(xué)習(xí)策略的有效性是否具有一般性.

圖2 數(shù)據(jù)集tic-tac-toe的ACCURACY性能變化

圖3 數(shù)據(jù)集transfusion的ACCURACY性能變化

圖4 數(shù)據(jù)集kr-vs-kp的ACCURACY性能變化

圖5 數(shù)據(jù)集diagnosis的ACCURACY性能變化

圖6 數(shù)據(jù)集breast-cancer的ACCURACY性能變化

為了深入研究所提出策略的有效性，在標(biāo)注數(shù)據(jù)比例為20%、40%、60%、80%、100%的情況下對兩個算法的結(jié)果作win/draw/loss分析.win/draw/loss分析用于描述不同算法對于同一數(shù)據(jù)集的算法差異.比如標(biāo)注數(shù)據(jù)比例為20%時候，在數(shù)據(jù)集tic-tac-toe上信息熵采樣策略的分類器ACCURACY均值記為Aie，在數(shù)據(jù)集tictac-toe上隨機(jī)采樣策略的分類器ACCURACY均值記為Ar，如果Aie＞Ar，那么win=1，如果Aie=Ar，那么draw=1，如果Aie＜Ar，那么loss=1.表3展示了基于信息熵采樣策略與隨機(jī)策略對比的win/draw/loss.

表3 基于信息熵采樣策略與隨機(jī)策略的win/draw/loss分析

從以上圖表展示結(jié)果可以看出，基于信息熵的抽樣策略比隨機(jī)策略在大多數(shù)情況下都能達(dá)到較好的分類效果，充分說明了基于信息熵策略的有效性.同時也說明了在進(jìn)行基于統(tǒng)計學(xué)習(xí)的子抽樣時候，面向個體信息量的選擇優(yōu)于隨機(jī)的選擇.隨著標(biāo)注樣例數(shù)目的增加，主動學(xué)習(xí)的兩個采樣策略依據(jù)不同角度進(jìn)行抽樣，分類算法的精度都得到了提高，也說明了主動學(xué)習(xí)方法框架的有效性.但是在數(shù)據(jù)集diagnosis上也有不同的表現(xiàn)，基于信息熵的策略隨著標(biāo)注樣例的增加，快速達(dá)到較好的分類效果；而隨機(jī)采樣策略不但沒有達(dá)到較好的分類效果，甚至分類性能出現(xiàn)了較大的波動.這樣說明基于信息熵的策略更加有利于提升模型的分類器精度.從數(shù)據(jù)集transfusion的性能走勢可以看出，隨著標(biāo)注樣例的增多，算法性能得到了較快的增長，并且收斂于比較穩(wěn)定的分類效果，而隨機(jī)采樣的策略在達(dá)到較好的分類效果以后甚至出現(xiàn)了性能下降的情況.

3.2 基于不同分類器上采樣策略的性能對比

為了充分研究不同采樣策略的性能變化情況，選擇使用其他的分類器對數(shù)據(jù)集進(jìn)行建模，通過不同分類器上不同采樣策略的性能對比，為了節(jié)省空間，僅僅描述標(biāo)注數(shù)據(jù)比例為20%、40%、60%、80%、100%的情況下性能對比情況.表4展示了不同分類器上不同采樣策略的性能對比.

從表4的結(jié)果可以看出，不管是采用隨機(jī)森林分類器（RF）還是采用邏輯斯蒂回歸分類器（LR），本文提出的基于信息熵的抽樣估計策略大部分情況下都取得了最優(yōu)的效果，即使在部分情況下沒有達(dá)到最優(yōu)，也并不弱于最優(yōu)性能很多.由此可以說明，針對不同的分類器或者不同的標(biāo)注實(shí)例比例的情況下，本文提出的基于信息熵的抽樣策略都能有穩(wěn)定的性能提升.

另外從兩種不同分類器的性能比較情況還可以看出，基于信息熵進(jìn)行抽樣估計的策略擁有更加穩(wěn)定的表現(xiàn)，隨著標(biāo)注樣例的增多，分類性能穩(wěn)步提升直至收斂到最佳水準(zhǔn).而隨機(jī)采樣策略明顯表現(xiàn)出比較強(qiáng)的隨機(jī)性與性能的不穩(wěn)定性.

表4 基于配對t檢驗(yàn)的采樣策略對比試驗(yàn)

4 結(jié)論

本論文提出了在使用基于統(tǒng)計學(xué)習(xí)的面向期望風(fēng)險減小的主動學(xué)習(xí)策略中，通過使用信息熵來進(jìn)行子抽樣.基于統(tǒng)計學(xué)習(xí)的選擇策略是從宏觀上選擇期望風(fēng)險最小的樣例進(jìn)行標(biāo)注；而基于信息熵的樣例選擇策略則是從樣例的微觀角度選擇樣例，充分利用樣例本身的信息量，對兩者進(jìn)行充分的結(jié)合有助于選擇既能滿足樣例信息量較高又能滿足期望損失最小的樣例.同時選擇策略有效降低了基于統(tǒng)計學(xué)習(xí)選擇策略的計算復(fù)雜度.在機(jī)器學(xué)習(xí)的常見數(shù)據(jù)集上的實(shí)驗(yàn)表明，該策略能夠有效地從未標(biāo)注實(shí)例中選擇需要人工標(biāo)注的實(shí)例.后期的研究從其他的子抽樣策略入手，對比研究不同的子抽樣策略對于基于統(tǒng)計學(xué)習(xí)的主動學(xué)習(xí)查詢策略的影響.當(dāng)前研究的數(shù)據(jù)集采用的都是二分類的數(shù)據(jù)集，后面可以研究當(dāng)前策略在多分類數(shù)據(jù)集上性能的變化情況.除了圖像處理應(yīng)用領(lǐng)域，未來也可以嘗試將該查詢策略應(yīng)用于智慧農(nóng)業(yè)等機(jī)器學(xué)習(xí)廣泛應(yīng)用的領(lǐng)域［13］，從而有效減少數(shù)據(jù)集的標(biāo)注成本.