楊文柱，田瀟瀟，王思樂，張錫忠

(1.河北大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，河北 保定 071002；2.河北省保定市教育考試院 信息處,河北 保定 071002)

?

主動學(xué)習(xí)算法研究進(jìn)展

楊文柱1，田瀟瀟1，王思樂1，張錫忠2

(1.河北大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，河北 保定 071002；2.河北省保定市教育考試院 信息處,河北 保定 071002)

主動學(xué)習(xí)的主要目的是在保證分類器精度不降低的前提下盡量降低人工標(biāo)注的成本.主動學(xué)習(xí)算法通過迭代方式在原始樣例集中挑選可以提升模型性能的樣例進(jìn)行專家標(biāo)注，并將其補(bǔ)充到已有的訓(xùn)練集中，使被訓(xùn)練的分類器在較低的標(biāo)注成本下獲得較強(qiáng)的泛化能力.首先對主動學(xué)習(xí)算法中3個關(guān)鍵步驟的研究進(jìn)展情況進(jìn)行了分析：1)初始訓(xùn)練樣例集的構(gòu)建方法及其改進(jìn)；2)樣例選擇策略及其改進(jìn)；3)算法終止條件的設(shè)定及其改進(jìn)；然后對傳統(tǒng)主動學(xué)習(xí)算法面臨的問題及改進(jìn)措施進(jìn)行了深入剖析；最后展望了主動學(xué)習(xí)需進(jìn)一步研究的內(nèi)容.

主動學(xué)習(xí)；初始訓(xùn)練集；樣例選擇策略；終止條件

機(jī)器學(xué)習(xí)研究在人工智能領(lǐng)域方興未艾，其目的是為了實現(xiàn)機(jī)器的智能化.監(jiān)督學(xué)習(xí)、無監(jiān)督學(xué)習(xí)以及目前備受關(guān)注的半監(jiān)督學(xué)習(xí)是機(jī)器學(xué)習(xí)中最常見的學(xué)習(xí)模式.監(jiān)督學(xué)習(xí)模型的基本思想是利用帶有類標(biāo)的訓(xùn)練樣例集通過示教模式來不斷調(diào)整分類器的參數(shù)以提升其性能.因此，傳統(tǒng)的監(jiān)督學(xué)習(xí)模型需要大量有類標(biāo)的訓(xùn)練樣例作為支撐條件才能得到預(yù)期的分類精度.即便在當(dāng)前的大數(shù)據(jù)時代，訓(xùn)練樣例問題依然存在：1)樣例總量少，比如在油田探井應(yīng)用中，探井?dāng)?shù)據(jù)必須通過昂貴的人工誘發(fā)地震獲取，數(shù)量少成本高；2)特定類別樣例少，如信用卡詐騙檢測應(yīng)用中，相對于正常交易數(shù)量，信用卡詐欺數(shù)量占比很少；3)有標(biāo)記樣本少，如軟件缺陷檢測應(yīng)用中，被程序員標(biāo)注為缺陷的軟件數(shù)量很少，等等[1].沒有大訓(xùn)練樣例集支撐，傳統(tǒng)的監(jiān)督學(xué)習(xí)模型很難達(dá)到較高的分類精度.然而，無監(jiān)督學(xué)習(xí)模型不需要標(biāo)注樣例，可通過發(fā)掘樣例集自身的特性進(jìn)行學(xué)習(xí)，且無類標(biāo)樣例通常比帶類標(biāo)樣例容易獲取，但通常其學(xué)習(xí)性能略遜于監(jiān)督學(xué)習(xí)[2].如何利用眾多未標(biāo)注樣例，從中挑選出對訓(xùn)練貢獻(xiàn)度高的樣例，標(biāo)注后補(bǔ)充到訓(xùn)練集中來提升分類器性能，是機(jī)器學(xué)習(xí)的研究方向之一.

半監(jiān)督學(xué)習(xí)和主動學(xué)習(xí)都是從未標(biāo)記樣例中挑選部分價值量高的樣例標(biāo)注后補(bǔ)充到已標(biāo)記樣例集中來提高分類器精度，降低領(lǐng)域?qū)＜业墓ぷ髁?，但二者的學(xué)習(xí)方式不同：半監(jiān)督學(xué)習(xí)一般不需要人工參與，是通過具有一定分類精度的基準(zhǔn)分類器實現(xiàn)對未標(biāo)注樣例的自動標(biāo)注；而主動學(xué)習(xí)有別于半監(jiān)督學(xué)習(xí)的特點之一就是需要將挑選出的高價值樣例進(jìn)行人工準(zhǔn)確標(biāo)注[3-4].半監(jiān)督學(xué)習(xí)通過用計算機(jī)進(jìn)行自動或半自動標(biāo)注代替人工標(biāo)注，雖然有效降低了標(biāo)注代價，但其標(biāo)注結(jié)果依賴于用部分已標(biāo)注樣例訓(xùn)練出的基準(zhǔn)分類器的分類精度，因此并不能保證標(biāo)注結(jié)果完全正確.相比而言，主動學(xué)習(xí)挑選樣例后是人工標(biāo)注，不會引入錯誤類標(biāo).由此看來，如何在缺乏足夠有類標(biāo)訓(xùn)練樣例的情況下，以低標(biāo)注代價獲得高精度分類器成為主動學(xué)習(xí)的研究熱點.本文對主動學(xué)習(xí)算法的最新研究進(jìn)展情況進(jìn)行了綜合分析，介紹了主動學(xué)習(xí)算法的關(guān)鍵步驟、面臨的主要問題及改進(jìn)措施，并展望了主動學(xué)習(xí)未來的研究工作.

1 主動學(xué)習(xí)算法關(guān)鍵步驟

對于監(jiān)督學(xué)習(xí)模型，足夠多的已標(biāo)注樣例是獲得高精度分類器的前提條件.隨著傳感器技術(shù)的迅猛發(fā)展，數(shù)據(jù)采集變得越來越容易，同時也導(dǎo)致未知樣例在總樣例中占比較大，而人工標(biāo)注未知樣例成本昂貴.另外，過多的低質(zhì)量訓(xùn)練樣例反而會降低分類器的魯棒性，甚至導(dǎo)致“過學(xué)習(xí)”問題.因此，需要控制訓(xùn)練樣例集的數(shù)量和質(zhì)量.如何高效地選出具有高分類貢獻(xiàn)度的無類標(biāo)樣例進(jìn)行標(biāo)注并補(bǔ)充到已有訓(xùn)練集中逐步提高分類器精度與魯棒性是主動學(xué)習(xí)亟待解決的關(guān)鍵問題.

主動學(xué)習(xí)模型從未標(biāo)注樣例集中根據(jù)設(shè)定的規(guī)則挑選樣例交由人工標(biāo)注，需同時考慮選出的樣例質(zhì)量和樣例數(shù)量以及由此產(chǎn)生的標(biāo)注成本.低標(biāo)注成本、高質(zhì)量樣例是優(yōu)化主動學(xué)習(xí)算法的主要目標(biāo).主動學(xué)習(xí)算法一般包含2個重要模塊：學(xué)習(xí)模塊和選擇模塊.學(xué)習(xí)模塊本質(zhì)上就是訓(xùn)練分類器的過程，即通過示教學(xué)習(xí)逐漸提高分類器的分類精度與魯棒性；而選擇模塊的終極目標(biāo)是生成高質(zhì)量的訓(xùn)練樣例集，以提高樣例集的代表性和廣泛性.學(xué)習(xí)模塊和選擇模塊循環(huán)交替工作，當(dāng)滿足終止條件時循環(huán)終止.可以看出，主動學(xué)習(xí)算法涉及3個關(guān)鍵問題：如何構(gòu)建初始訓(xùn)練樣例集、采取何種樣例選擇策略、設(shè)置何種終止條件.

1.1 構(gòu)建初始訓(xùn)練樣例集

學(xué)習(xí)模塊中維護(hù)的基準(zhǔn)分類器必須具備一定的分類精度，因此在開始主動學(xué)習(xí)之前必須對基準(zhǔn)分類器進(jìn)行初始訓(xùn)練，問題的關(guān)鍵是如何構(gòu)建高效能的初始訓(xùn)練樣例集.一般隨機(jī)挑選的初始訓(xùn)練集不具有代表性，而由代表性樣例組成的初始訓(xùn)練集是訓(xùn)練較高精度基準(zhǔn)分類器的前提，也更能有效加快主動學(xué)習(xí)進(jìn)程.基于聚類[5]或距離相似性度量的方法是選擇代表性樣例的常用方法，如徐艷等[6]采用劃分聚類算法(K-Medoids)構(gòu)造初始訓(xùn)練集；金良等[7]將初始階段的隨機(jī)樣例選擇更換為分層聚類樣例選擇，這些措施都不同程度地加快了主動學(xué)習(xí)的進(jìn)程；趙秋煥等[8]則通過挖掘并利用未標(biāo)記樣例的概率分布信息，使基準(zhǔn)分類器的分類面一開始就與真實分類面相差不遠(yuǎn)，避免了分類面長期停留在錯誤方位的情況發(fā)生.

1.2 樣例選擇策略

為了使分類器達(dá)到預(yù)期精度，學(xué)習(xí)模塊需要不斷地選擇出分類貢獻(xiàn)率高的樣例交給領(lǐng)域?qū)＜疫M(jìn)行標(biāo)注并補(bǔ)充到已有訓(xùn)練集中.由此可知，選挑樣例的“優(yōu)”、“劣”將直接影響分類器性能.但現(xiàn)實中，描述樣例特征的信息存在大量冗余，如何利用這些特征信息真正選出對分類貢獻(xiàn)度大的樣例成為了主動學(xué)習(xí)成功的關(guān)鍵.評價樣例價值量的方法有很多，相應(yīng)地提出了不同的樣例選擇策略.

目前，國內(nèi)外的一些研究機(jī)構(gòu)或組織已經(jīng)開始針對主動學(xué)習(xí)中的樣例選擇策略進(jìn)行了深入研究，并提出了很多行之有效的樣例選擇策略.按照獲取優(yōu)質(zhì)樣例工作方式的不同可將樣例選擇分為基于流(stream-based)和基于池(pool-based)的策略.

1.2.1 基于流的樣例選擇策略

基于流的策略依次從未標(biāo)注樣例池中取出一個樣例輸入到選擇模塊，若滿足預(yù)設(shè)的選中條件則對其進(jìn)行準(zhǔn)確的人工標(biāo)注，反之直接舍棄.該學(xué)習(xí)過程需要處理所有未標(biāo)記樣例，查詢成本高昂.另外，由于基于流的樣例選擇策略需要預(yù)設(shè)一個樣例標(biāo)注條件，但該條件往往需要根據(jù)不同的任務(wù)進(jìn)行適當(dāng)調(diào)整，因此很難將其作為一種通用方法普遍使用[9].

1.2.2 基于池的樣例選擇策略

基于池的方法每次從系統(tǒng)維護(hù)的未標(biāo)注的樣例池中按預(yù)設(shè)的選擇規(guī)則選取一個樣例交給基準(zhǔn)分類器進(jìn)行識別，當(dāng)基準(zhǔn)分類器對其識別出現(xiàn)錯誤時進(jìn)行人工標(biāo)注.相較基于流的方法，基于池的方法每次都可選出當(dāng)前樣例池中對分類貢獻(xiàn)度最高的樣例，這既降低了查詢樣例成本，也降低了標(biāo)注代價，這使得基于池的樣例選擇策略廣泛使用.基于池的樣例選擇標(biāo)準(zhǔn)主要包括：不確定性標(biāo)準(zhǔn)、版本空間縮減標(biāo)準(zhǔn)、泛化誤差縮減標(biāo)準(zhǔn)等.

1)不確定性標(biāo)準(zhǔn)

① 用概率表示不確定性程度

基于概率的啟發(fā)式方法建立在樣例的后驗概率分布基礎(chǔ)之上，由此運算速度最快.樣例后驗概率為50%在二分類器中是最難分的，對其進(jìn)行人工標(biāo)注后加入訓(xùn)練集能顯著提高分類器精度，但該方法僅考慮了樣例最可能所屬的類，忽略了屬于其他類的比重.

在多類分類問題中，挑選最低置信度的方法是最常用的不確定性度量方法，可表示為

(1)

為了解決上述問題，出現(xiàn)了margin sampling[10]方法，在考慮了樣例最可能所屬類的同時還考慮了第二可能所屬類.該margin sampling方法可表示為

(2)

基于熵的不確定表示方法是用樣例的信息熵作為評價其信息量多少的標(biāo)準(zhǔn)，即：樣例的信息熵越大則其所含信息量也越大，對當(dāng)前分類器來說也就是最不能確定其所屬類別的樣例.信息熵的定義如下:

(3)

其中，p(yi|x)表示在給定樣例x情況下其標(biāo)簽屬于yi的可能性.

② 用距離表示不確定性程度

考慮2類分類問題，任意樣例點xi到SVM分類面的距離可表示為

(4)

其中，K(xj,xi)為核函數(shù)，用于計算候選樣例xi與支持向量xj之間的相似度.樣例點到分類面的距離可用于表示候選樣例的不確定程度，其值越大則樣例的不確定性越高.

對于多類分類問題，若采用一對一策略構(gòu)造多類分類器，可利用邊緣抽樣最小化公式進(jìn)行樣例選擇[11]：

(5)

其中，|f(xi,w)|是樣例點到分類面距離.距分類面越近的樣例，分類器越不能確定其所屬類別，樣例的不確定性越高，該方法稱為邊緣抽樣方法(MS算法).

在解決多分類問題時，有學(xué)者還提出了基于多層次的不確定性樣例選擇方法(MCLU算法)，該方法也是基于邊緣抽樣最小化的方法，但同時考慮了樣例到不同類間的距離差[12]，具體形式如下：

(6)

在該方法中，結(jié)果值越大，待選擇樣例屬于某類別的不確定性越小.MCLU算法將某樣例離分類超平面最遠(yuǎn)的2個類的距離差作為不確定指標(biāo)，而MS算法僅根據(jù)該樣例到單個分類超平面的距離作為樣例選擇標(biāo)準(zhǔn)，因此在針對多類分類的樣例選擇時效果遠(yuǎn)超過MS算法.

2)版本空間縮減標(biāo)準(zhǔn)

基于版本空間縮減的樣例選擇應(yīng)使選出的樣例能最大限度地縮減樣本的版本空間.所謂版本空間指的是一系列不同類型基準(zhǔn)分類器的組合.委員會查詢(QBC，query-by-committee)是基于該標(biāo)準(zhǔn)的典型算法，該算法先用已標(biāo)注樣例對2個及以上不同類型的基準(zhǔn)分類器進(jìn)行預(yù)訓(xùn)練，將其組成“評審委員會”，然后用該委員會成員對待測樣例進(jìn)行判別，選出各個委員對待標(biāo)注樣例判別結(jié)果最不一致的樣例進(jìn)行人工標(biāo)注.

構(gòu)建高效的QBC算法需要解決3個關(guān)鍵問題：①如何選擇高質(zhì)量的委員會成員構(gòu)建高效的評審委員會；②委員會成員的個數(shù)多少最佳；③怎樣評價委員會判別結(jié)果的優(yōu)劣.評價標(biāo)準(zhǔn)主要有：KL散度(Kullback-Leibler divergence)、投票熵、JS(Jensen-Shannon)分歧度等.在構(gòu)建評審委員會時，關(guān)鍵問題是確保委員會成員的高品質(zhì)及成員間的高差異.

梁延峰等基于改進(jìn)的Decorate算法，通過同時計算已標(biāo)注和未標(biāo)注樣例的均值和方差使產(chǎn)生的樣例分布不斷接近實際的樣例分布，設(shè)計了一個基于粒子群選擇集成的QBC主動學(xué)習(xí)算法[13].

3)泛化誤差縮減標(biāo)準(zhǔn)

分類器的泛化誤差是評價其魯棒性的常用指標(biāo).最大程度地降低分類器的泛化誤差，是基于該標(biāo)準(zhǔn)樣例選擇算法的最終目標(biāo).關(guān)鍵步驟描述如下：

首先估算樣例的分類誤差率，公式表示為

μ(x)=∫xE[(yx(x)-y(x))2|x]p(x)dx,

(7)

其中，y(x)表示樣例x的真實類標(biāo)，yx(x)表示分類器輸出的樣例x的類標(biāo)，p(x)是樣例x的概率密度函數(shù).

而后依次評估若將一個新樣例加入到訓(xùn)練集可能會給分類器帶來的泛化誤差變化，并最終選出能使泛化誤差縮減程度最大的樣例進(jìn)行人工標(biāo)注.基于該策略的算法具有出色的樣例選擇性能，但仍需關(guān)注如下問題：①時間復(fù)雜度高：針對每個侯選的未標(biāo)注樣例，都要評估其加入訓(xùn)練集后引起的分類器泛化誤差變化.②應(yīng)用面窄：鑒于其較高的時間復(fù)雜度，一般只適用于解決二類分類問題.③性價比低：訓(xùn)練樣本集每增加1個樣例，都需要對分類器進(jìn)行重新訓(xùn)練，因此分類器的性能提升與訓(xùn)練成本不成正比，且分類器容易出現(xiàn)過擬合現(xiàn)象.

1.3 終止條件的設(shè)定

主動學(xué)習(xí)就是通過迭代的方式，主動挑選價值量高的樣例不斷補(bǔ)充到已有訓(xùn)練樣例集中，進(jìn)而不斷提升分類器性能.在此迭代過程中，何時終止迭代是關(guān)鍵.設(shè)計終止標(biāo)準(zhǔn)一般需考慮2點[14]：1)達(dá)標(biāo)即可：對于以指定分類精度為目標(biāo)的應(yīng)用，主動學(xué)習(xí)的訓(xùn)練過程只需使分類器達(dá)到預(yù)期的分類正確率即可，無需再補(bǔ)充樣例繼續(xù)訓(xùn)練.2)高性價比：對于以追求高分類精度為目標(biāo)的應(yīng)用，若繼續(xù)學(xué)習(xí)給分類器帶來的性能提升與繼續(xù)學(xué)習(xí)成本相比，已經(jīng)可以忽略不計，則應(yīng)停止迭代.

主動學(xué)習(xí)注重所選訓(xùn)練樣例的優(yōu)劣，學(xué)習(xí)過程力求達(dá)到樣例標(biāo)注代價和分類器性能間的均衡[15].一般的主動學(xué)習(xí)終止標(biāo)準(zhǔn)是達(dá)到了某個規(guī)定的閾值，即當(dāng)分類器的訓(xùn)練精度或挑選的樣例數(shù)量達(dá)標(biāo)時迭代終止.但對于多類分類問題，標(biāo)注代價和分類器精度并不總是正相關(guān)，亦即并非挑選的樣例越多，所訓(xùn)練出的分類器精度越高，如圖1所示.

圖1 分類器精度與訓(xùn)練樣例數(shù)的關(guān)系曲線實例[16]Fig.1 An example of relationships between classifier accuracy and number of training samples

圖1是文獻(xiàn)[16]所提方法的實驗結(jié)果，可以看出：①將所有樣例進(jìn)行標(biāo)注加入訓(xùn)練集時，所得分類器精度不是最高的.②挑選樣例個數(shù)的增加與分類器性能的提升并非呈線性增長.由此可知，如何權(quán)衡分類器性能的提升與標(biāo)注代價的增加是主動學(xué)習(xí)算法設(shè)置終止條件時需認(rèn)真考慮的問題.

針對上述問題，可采用雙停止條件[17]，也可在分類器精度提升緩慢時相對減少標(biāo)注樣例個數(shù)[18]，這些措施都產(chǎn)生了一定的效果.根據(jù)分類精度變化調(diào)整標(biāo)注樣例數(shù)的約束條件定義為

|η(i)-η(i-1)|=δ，

(8)

(9)

其中，η(i)表示分類器在第i次迭代時的分類精度，δ為分類精度之差，T為設(shè)定的閾值，t為標(biāo)注樣例個數(shù).

2 傳統(tǒng)主動學(xué)習(xí)算法面臨的問題及改進(jìn)措施

傳統(tǒng)的主動學(xué)習(xí)算法在遇到多類分類、孤立點、訓(xùn)練集樣例冗余、不平衡數(shù)據(jù)等問題時往往顯得力不從心.如何應(yīng)對上述挑戰(zhàn)，不斷提高主動學(xué)習(xí)算法的性能和魯棒性，是目前尚未完全解決的難題.

2.1 多類分類問題

多類分類問題給主動學(xué)習(xí)算法帶來了巨大的挑戰(zhàn).在處理多類分類問題時，基于Margin Sampling的樣例選擇標(biāo)準(zhǔn)忽略了樣例可能屬于其他類別的信息，因此所選樣例質(zhì)量較差.基于熵的方法雖考慮了樣例從屬于每個類別的概率，但在多類分類問題中，樣例的熵也會受到那些不重要類別的干擾.如圖2所示，圖2b中的第4類雖比圖2a中第4類的熵值大，但其不確定性更小，使用基于熵的樣例選擇方法將得到錯誤的選擇結(jié)果.為此，Joshi等[19]提出了一種更為準(zhǔn)確的主動學(xué)習(xí)樣例選擇準(zhǔn)則，稱為BvSB準(zhǔn)則.設(shè)樣例xi屬于最優(yōu)類標(biāo)和次優(yōu)類標(biāo)的條件概率分別為yBest|xi和ySecond-Best|xi，則該BvSB準(zhǔn)則可表示為

BvSB*=arg min((p(yBest|xi)-p(ySecond-Best|xi))).

(10)

由于BvSB準(zhǔn)則只考慮樣例所屬概率最高的前2個類別，忽略剩余類別對樣例選擇標(biāo)準(zhǔn)產(chǎn)生的干擾，因此在針對多類分類問題時，其樣例選擇質(zhì)量明顯優(yōu)于基于信息熵的樣例選擇[20].陳榮等[21]將基于最優(yōu)標(biāo)號和次優(yōu)標(biāo)號(bestvssecond-best,BvSB)的主動學(xué)習(xí)和帶約束的自學(xué)習(xí)(constrainedself-training,CST)引入到基于SVM的圖像分類中，顯著提高了分類精度.

2.2 孤立點問題

不確定性高的樣例是當(dāng)前分類器容易分錯的樣例，而樣例的不確定性通?？捎闷湫畔㈧乇硎?，一般熵越大越難正確分類.盡管基于不確定性的方法在多數(shù)分類問題上效果優(yōu)于隨機(jī)選擇方法，但忽略了信息熵較大的孤立點對分類器性能的影響.若能綜合考慮樣例的先驗分布，則是對基于不確定性方法的有益補(bǔ)充.

圖2 多類問題中樣例的熵不能正確反映類別不確定性的例子Fig.2 An example of the entropy of a sample can not correctly reflect its category uncertainty in multi-class problem

樣例的先驗分布知識通?？赏ㄟ^對樣本進(jìn)行聚類分析或樣本密度分布分析等獲得.處于聚類中心或密度質(zhì)心的樣例是代表性樣例.若選擇樣例時能綜合考慮樣其代表性和不確定性，通常可避免采集到孤立點.如文獻(xiàn)[22]中提出了一種綜合利用聚類信息和分類間隔的樣例選擇方法；文獻(xiàn)[23]提出了一種利用預(yù)聚類協(xié)助選擇代表性樣例的主動學(xué)習(xí)方法，如圖3所示；文獻(xiàn)[24]利用樣例的不確定性及其先驗分布密度進(jìn)行樣例選擇以獲取優(yōu)質(zhì)樣例；文獻(xiàn)[25]將樣例的分布密度作為度量樣例代表性的指標(biāo)，結(jié)合以熵作為不確定性指標(biāo)，提出了一種基于密度熵的樣例選擇策略，有效解決了孤立點問題給樣例選擇質(zhì)量造成的影響.

圖3 采用預(yù)聚類的主動學(xué)習(xí)[23]Fig.3 Active learning using pre-clustering

2.3 訓(xùn)練集樣例冗余問題

在主動學(xué)習(xí)中，每次迭代挑選多少個樣例標(biāo)注補(bǔ)充到訓(xùn)練集中也是值得研究的問題.為提高學(xué)習(xí)效率，主動學(xué)習(xí)的每次迭代一般采取批模式而非單個模式進(jìn)行.然而，批量選擇樣例容易出現(xiàn)樣例相似度高的問題，比如在基于BvSB的主動學(xué)習(xí)模型中，由于選擇樣例時僅考慮了其分類不確定性，未綜合考慮其代表性，因此容易導(dǎo)冗余樣例的出現(xiàn)，如圖4所示.

由圖4可以看出，新的訓(xùn)練樣本中樣例1與分類超平面的距離比樣例2近，根據(jù)BvSB準(zhǔn)則應(yīng)當(dāng)挑選樣例1進(jìn)行標(biāo)注并補(bǔ)充到訓(xùn)練集中；但緊挨著樣例1的綠色樣例a已經(jīng)在訓(xùn)練集中，此時若再加入樣例1則對分類界面影響甚微.相比而言，將樣例2補(bǔ)充到訓(xùn)練集中，對當(dāng)前分類模型的訓(xùn)練貢獻(xiàn)度更大.

通過上述分析可知，主動學(xué)習(xí)中的樣例選擇度量主要分為2種：1)不確定性度量;2)差異性度量或代表性度量.樣例的不確定性一般可通過計算其信息熵獲得，樣例的代表性通?？筛鶕?jù)其是否在聚類中心判斷[26]，而樣例的差異性則可通過計算余弦相似度[27]或用高斯核函數(shù)[28]獲得.余弦相似度定義為

(11)

其中，a、b分別為欲進(jìn)行相似度計算的2個樣例，值越大表示這2個樣例的相似度越高.

圖4 樣例冗余問題舉例Fig.4 An example of sample redundancy problem

2.4 不平衡數(shù)據(jù)問題

當(dāng)訓(xùn)練集中不同類別的樣例數(shù)量嚴(yán)重失衡時，對于基于SVM的主動學(xué)習(xí)模型，其訓(xùn)練出的分類器往往出現(xiàn)分類正確率不均衡的現(xiàn)象，即在訓(xùn)練集中占比低的類別相較占比高的類別，其被錯分的概率明顯偏高.因此，對于給定的任意樣例集，如何保證在選出的訓(xùn)練集中每類樣例的占比基本均衡是解決此問題的關(guān)鍵.

為解決上述不平衡數(shù)據(jù)給主動學(xué)習(xí)模型造成的影響，KSVMactive主動學(xué)習(xí)算法[29]、改進(jìn)的加權(quán)支持向量機(jī)模型[30]、基于SVM超平面位置校正的主動學(xué)習(xí)算法[31]等各種解決方案應(yīng)運而生，這些措施都在一定程度上提高了主動學(xué)習(xí)效率，并最終提高了分類器的精度和魯棒性.

3 展望

主動學(xué)習(xí)的理論研究已經(jīng)取得了豐碩成果，在很多領(lǐng)域中也進(jìn)行了成功應(yīng)用，但仍存在一些值得深入研究的問題[32-35]：1)如何將不確定性、代表性、多樣性準(zhǔn)則以及各類樣例在數(shù)據(jù)集中的先驗分布知識進(jìn)行有機(jī)融合，設(shè)計出魯棒性更好的樣例選擇算法，是主動學(xué)習(xí)尚未完全解決的問題；2)針對實際應(yīng)用中不斷出現(xiàn)的新增樣例，如何實現(xiàn)主動學(xué)習(xí)與在線學(xué)習(xí)的有機(jī)結(jié)合，保持分類器不斷進(jìn)化，是目前的研究熱點；3)深度學(xué)習(xí)模型是處理復(fù)雜分類問題的有效工具，如何借助深度學(xué)習(xí)模型提高主動學(xué)習(xí)算法的分類能力，是值得深入研究的問題；4)目前的主動學(xué)習(xí)研究主要基于封閉的靜態(tài)環(huán)境，即影響模型學(xué)習(xí)的因素都是確定的；但環(huán)境因素具有時空變異性，這使得開放環(huán)境下的主動學(xué)習(xí)研究成為新的挑戰(zhàn).

[1] 何清，李寧，羅文娟，等.大數(shù)據(jù)下的機(jī)器學(xué)習(xí)算法綜述[J].模式識別與人工智能，2014，27(4)：327-334. HE Q,LI N,LUO W J，et al.A survey of machine learning algorithms for Big Data[J].Pattern Recognition and Artificial Intellegence, 2014,27(4):327-334.

[2] KAREM F,DHIBI M,MARTIN A.Combination of supervised and unsupervised classification using the theory of belief functions[M].Belief Functions:Theory and Applications,Springer Berlin Heidelberg,2012:85-92.DOI:10.1007/978-3-642-29461-7_10.

[3] 翟俊海，張素芳，徐正夫，等.粗糙集與決策樹比較研究[J].河北大學(xué)學(xué)報(自然科學(xué)版),2012,32(4):421-428. ZHAI J H,ZHANG S F,XU Z F,et al.Comparative study on rough sets and decision trees[J].Journal of Hebei University(Natural Science Edition),2012,32(4):421-428.

[4] FORESTIER G,WEMMERT C.Semi-supervised learning using multiple clusterings with limited labeled data[J].Information Sciences,2016,361:48-65.

[5] ZHU J,WANG H,TSOU B K,et al.Active learning with sampling by uncertainty and density for data annotations[J].IEEE Transactions on Audio Speech & Language Processing,2010,18(6):1323-1331.DOI:10.1109/TASL.2009.2033421

[6] 徐艷.基于主動學(xué)習(xí)的圖像標(biāo)注方法研究[D].遼寧：遼寧工業(yè)大學(xué)，2014. XU Y.Research on image annotation based active learning[D].Liaoning:Liaoning University of Technology,2014.

[7] 金良，曹永鋒，蘇彩霞，等.基于HS樣例選擇和BvSB反饋的多類圖像分類[J].貴州師范大學(xué)學(xué)報(自然科學(xué)版)，2014，32(04):56-61.DOI:10.16614/j.cnki.issn1004-5570.2014.04.013. JIN L，CAO Y F，SU C X，et al.Multi-class image classification based on HS sample selection and BvSB feedback[J].Guizhou Normal University(Natural Science Edition)，2014,32(04):56-61.DOI:10.16614/j.cnki.issn1004-5570.2014.04.013.

[8] 趙秋煥.兩種主動學(xué)習(xí)方法[D].保定：河北大學(xué)，2010. ZHAO Q H.Two kinds of active learning methods[D].Baoding：Hebei University,2010.

[9] 龍軍，殷建平，祝恩,等.主動學(xué)習(xí)研究綜述[J].計算機(jī)研究與發(fā)展，2008，45(s1)：300-304. LONG J,YIN J P,ZHU E,et al.A survey of active learning[J].Journal of Computer Research and Development,2008，45(s1)：300-304.

[10] CAMPBELLl C,CRISTIANINI N,SMOLA A.A query learning with large margin classifiers[Z].The 17th Int l Conf on Machine Learning,San Francisco:Morgan Kaufmann,2000.

[11] 韓冰，高新波，姬紅兵.一種基于選擇性集成SVM的新聞音頻自動分類方法[J].模式識別與人工智能，2006，19(5)：634-639. HAN B,GAO X B ,JI H B.Automatic news audio classification method based on selective ensemble SVMS[J].PR&AI,2006，19(5)：634-639.

[12] 劉康，錢旭，王自強(qiáng).主動學(xué)習(xí)算法綜述[J].計算機(jī)工程與應(yīng)用，2012，48(34)：1-4.DOI:10.3778/j.issn.1002-8331.1205-0149. LIU K,QIAN X,WANG Z Q .Overview of active learning algorithms[J].Computer Engineering and Applications,2012，48(34)：1-4.DOI:10.3778/j.issn.1002-8331.1205-0149.

[13] ZHAO Y,XU C,CAO Y.Research on query-by-committee method of active learning and application[J].Computer Engineering,2006,4093(24):985-991.DOI:10.1007/11811305_107.

[14] 劉峰濤.基于樣例池類標(biāo)改變率的主動學(xué)習(xí)算法終止準(zhǔn)則研究[D].保定：河北大學(xué),2011. LIU F T.Research on change-rate-based stop criteria of active learning algorithms[D].Baoding：Hebei Vniversity,2011.

[15] ZHU J,WANG H,HOVY E,et al.Confidence-based stopping criteria for active learning for data annotation[J].Acm Transactions on Speech & Language Processing,2010,6(3):1-24.DOI:10.1145/1753783.1753784.

[16] WANG X Z,DONG L C,YAN J H.Maximum ambiguity-based sample selection in fuzzy decision tree induction[J].IEEE Transactions on Knowledge & Data Engineering，2012,24(8):1491-1505.DOI:10.1109/TKDE.2011.67.

[17] 白龍飛.基于支持向量機(jī)的主動學(xué)習(xí)方法研究[D].山西：山西大學(xué)，2012. BAI L F.Research on active learning approach based on support vector machines[D].Shanxi：University of Shanxi,2012.

[18] LIU J,YU H,YANG W,et al.Combining active learning and semi-supervised learning based on extreme learning machine for multi-class image classification[M]// Intelligence Science and Big DataEngineering,Image and Video Data Engineering.Springer International Publishing,2015.DOI:2015.10.1007/978-3-319-23989-7_18.

[19] JOSHI A J,PORIKLI F,PAPANIKOLOPOULOS N.Multi-class active learning for image classification[Z].Computer Society Conference on Computer Vision and Pattern Recognition,Miami,FL,2009.

[20] 王珍鈺.基于不確定性的主動學(xué)習(xí)算法研究[D].保定：河北大學(xué)，2011. WANG Z Y.Study of active learning algorithms based on uncertainty[D].Baoding：Hebei University,2011.

[21] 陳榮，曹永鋒，孫洪.基于主動學(xué)習(xí)和半監(jiān)督學(xué)習(xí)的多類圖像分類[J].自動化學(xué)報,2011，37(8)：954-962.DOI :10.3724/SP.J.1004.2011.00954. CHEN R,CAO Y F,SUN H.Multi-class image classification with active learning and semi-supervised learning[J].Acta Automatica Sinica,2011，37(8)：954-962.DOI :10.3724/SP.J.1004.2011.00954.

[22] HUANG S J,JIN R,ZHOU Z H.Active learning by querying infor-mative and representative examples[Z].The 24th Annual Conference on Neural Information Processing Systems,Va-ncouver,British Columbia,Canada:NIPS,2010.DOI:10.1109/TPAMI.2014.2307881.

[23] FRIEDMAN A,STEINBERG D,PIZARRO O,et al.Active learning using a Variational Dirichlet Process model for pre-clustering and classification of underwater stereo imagery[C]//Ieee/rsj International Conference on Intelligent Robots and Systems,Ieee/rsj International Conference on Intelligent Robots and Systems,2011:1533-1539.DOI:10.1109/IROS.2011.6095178.

[24] DONMWZ P,CARBONELL J G,BENNETT P N.Dual strategy active learning[C]//Proceedings of the 18th European Conference on Machine Learning.Springer-Verlag:Springer,2007:116-127.DOI:10.1007/978-3-540-74958-5_14.

[25] 胡正平，高文濤， 萬春艷.基于樣本不確定性和代表性相結(jié)合的可控主動學(xué)習(xí)算法研究[J].燕山大學(xué)學(xué)報，2009，33(4)：341-346. HU Z P,GAO W T,WAN C Y.Research on controlled active learning algorithm based on the combination of sample uncertainty and representation[J].Journal of Yanshan University,2009，33(4)：341-346.

[26] 曹永鋒，陳榮，孫洪.基于BvSBHC的主動學(xué)習(xí)多類分類算法[J].計算機(jī)科學(xué)，2013，40(8)：309-312. CAO Y F,CHEN R,SUN H.Multi-class image classification with best vs.second-best active learning and hierarchical clustering[J].Computer Science,2013，40(8)：309-312.

[27] 吳偉寧，劉揚(yáng)，郭茂祖，等.基于采樣策略的主動學(xué)習(xí)算法研究進(jìn)展[J].計算機(jī)研究與發(fā)展，2012，49(6)：1162-1173. WU W N,LIU Y,GUO M Z，et al．Advances in active learning algorithms based on sampling strategy[J].Journal of Computer Research and Development,2012，49(6)：1162-1173.

[28] 陳昀，畢海巖.基于多特征融合的中文評論情感分類算法[J].河北大學(xué)學(xué)報(自然科學(xué)版)，2015，35(6):651-656.DOI:10.3969/j.issn1000-1565.2015.06.016. CHEN Y，BI H Y.A sentiment classification algorithm of Chinese comments based on multi features fusion[J].Journal of Hebei University(Natural Science Edition),2015，35(6):651-656.DOI:10.3969/j.issn1000-1565.2015.06.016.

[29] 韓光，趙春霞，胡雪蕾.一種新的SVM主動學(xué)習(xí)算法及其在障礙物檢測中的應(yīng)用[J].計算機(jī)研究與發(fā)展，2009，46(11)：1934-1941. HAN G,ZHAN C X,HU X L.An SVM active learning algorithm and its application in obstacle detection[J].Journal of Computer Research and Development,2009，46(11)：1934-1941.

[30] 鮑翠梅.基于主動學(xué)習(xí)的加權(quán)支持向量機(jī)的分類[J].計算機(jī)工程與設(shè)計，2009，30(4)：966-970.DOI:10.16208/j.issn1000-7024.2009.04.071. BAO C M.Classification of weighted support vector machine based on active learning[J].Computer Engineering and Design,2009，30(4)：966-970.DOI:10.16208/j.issn1000-7024.2009.04.071.

[31] 梁延峰.基于專家委員會的主動學(xué)習(xí)算法研究[D].青島：中國海洋大學(xué)，2010. LIANG Y F.Research of query-by-committee method of active learning[D].Qingdao：Chinese Marine University,2010.

[32] 高成，陳秀新，于重重，等.基于主動學(xué)習(xí)的圖半監(jiān)督分類算法[J].計算機(jī)工程與設(shè)計,2015(7):1871-1875.DOI:10.16208/j.issn1000-7024.2015.07.037. GAO C,CHEN X X,YU C C，et al.Graph-based semi-supervised classification algorithm based on active learning[J].Computer engineering and design,2015(7):1871-1875 DOI:10.16208/j.issn1000-7024.2015.07.037.

[33] 白龍飛，王文劍，郭虎升.一種新的支持向量機(jī)主動學(xué)習(xí)策略[J].南京大學(xué)學(xué)報(自然科學(xué))，2012，48(2)：182-189.DOI:10.13232/j.cnki.jnju.2012.02.008. BAI L F,WANG W J ,GUO H S.A novel support vector machine active learning strategy[J].Journal of Nanjingl University(Natural Sciences)，2012，48(2):182-189.DOI:10.13232/j.cnki.jnju.2012.02.008.

[34] 徐美香,孫福明,李豪杰.主動學(xué)習(xí)的多標(biāo)簽圖像在線分類[J].中國圖象圖形學(xué)報，2015，20(2)：237-244.DOI:10.11834 /jig．20150210. XU M X,SUN F M,LI H J.Online multi-label image classification with active learning[J].Journal of image and Graphics,2015,20(2)：237-244.DOI:10.11834 /jig.20150210.

[35] 李海峰，李純果.深度學(xué)習(xí)結(jié)構(gòu)和算法比較分析[J].河北大學(xué)學(xué)報(自然科學(xué)版),2012,32(5):538-544. LI H F,LI C G.Note on deep architecture and deep learning algorithms[J].Journal of Hebei University(Natural Science Edition),2012,32(5):538-544.

(責(zé)任編輯：孟素蘭)

Recent advances in active learning algorithms

YANG Wenzhu1,TIAN Xiaoxiao1,WANG Sile1,ZHANG Xizhong2

(1.School of Computer Science and Technology,Hebei University,Baoding 071002,China；2.Institute of Information Technology,Baoding Education Examinations Authority,Baoding 071000,China)

Active learning mainly aims at reducing the cost of manual annotation without decreasing the accuracy of the classifier.Active learning algorithm gets high quality training sample set by selecting the informative unlabeled samples which are labeled by domain experts later.The selected sample set is used to train the classifier.This improves the generalization ability of trained classifier while minimizes the cost of the labeling.Firstly,the recent advances in the three key steps in active learning algorithm was summarized,including：1)the method for constructing the initial training sample set and its improvement；2)the sample selection strategy and its improvement；3)the termination condition and its improvement.Then,the problems in active learning were analyzed and the corresponding countermeasures were presented.Finally,the future works in active learning were addressed.

active learning；initial training sample set；sample selection strategy；termination condition

10.3969/j.issn.1000-1565.2017.02.017

2016-10-11

河北省自然科學(xué)基金資助項目(F2015201033);國家科技支撐計劃項目(2013BAK07B04);河北大學(xué)研究生創(chuàng)新項目(X2016057)

楊文柱(1968—)，男，河北保定人，河北大學(xué)教授，博士，主要從事機(jī)器視覺與智能系統(tǒng)研究. E-mail：wenzhuyang@163.com

張錫忠(1966—)，男，河北衡水人，保定市教育考試院高級工程師，主要從事云計算與大數(shù)據(jù)研究. E-mail：zxz@bhu.edu.cn

TP181

A

1000-1565(2017)02-0216-09