一種基于置信度差異代價(jià)敏感的主動(dòng)學(xué)習(xí)算法

武永成

(荊楚理工學(xué)院 計(jì)算機(jī)工程學(xué)院，湖北 荊門(mén) 448000)

一種基于置信度差異代價(jià)敏感的主動(dòng)學(xué)習(xí)算法

武永成

(荊楚理工學(xué)院 計(jì)算機(jī)工程學(xué)院，湖北 荊門(mén) 448000)

主動(dòng)學(xué)習(xí)時(shí)向?qū)＜也樵兊玫降臉?biāo)注如果帶有噪聲，將會(huì)影響學(xué)習(xí)的性能。為減少噪聲，人們提出了基于“少數(shù)服從多數(shù)”的多專家主動(dòng)學(xué)習(xí)算法，但該算法的缺點(diǎn)是代價(jià)往往太高。文章采用了一種自我訓(xùn)練(self-training)方法，對(duì)某些平均置信度高的樣本，直接確定其分類標(biāo)注，不必向?qū)＜也樵儯怨?jié)省學(xué)習(xí)代價(jià)。同時(shí)，使用置信度差異作為度量標(biāo)準(zhǔn)，選取那些最不確定的樣本向?qū)＜也樵儯岣吡藢W(xué)習(xí)效率。在UCI數(shù)據(jù)集上驗(yàn)證了本文算法的有效性。

主動(dòng)學(xué)習(xí)；噪聲數(shù)據(jù)；置信度差異；自我訓(xùn)練

在監(jiān)督學(xué)習(xí)中，為獲得準(zhǔn)確性高的分類模型，需要大量有標(biāo)注(即分類類型)的樣例。現(xiàn)實(shí)世界中，通常存在大量未標(biāo)注樣例，而有標(biāo)注樣例則往往較少。例如，在計(jì)算機(jī)輔助醫(yī)學(xué)圖像分析中，可以從醫(yī)院獲得大量的醫(yī)學(xué)圖像作為訓(xùn)練集，但如果要求醫(yī)學(xué)專家把這些圖像中的病灶都標(biāo)注出來(lái)，往往是不現(xiàn)實(shí)的。

主動(dòng)學(xué)習(xí)主要是解決在標(biāo)注樣本缺少情況下的一種有效方法。通過(guò)選取那些最具代表性的無(wú)標(biāo)注數(shù)據(jù)讓專家去標(biāo)注，從而使專家的標(biāo)注任務(wù)量最小化。將專家標(biāo)注后的樣例加入有標(biāo)注數(shù)據(jù)集，使其得到擴(kuò)充。在擴(kuò)充后的有標(biāo)注樣例集上進(jìn)行相應(yīng)的監(jiān)督學(xué)習(xí)，使其性能(如分類的準(zhǔn)確性)進(jìn)一步提高。

多數(shù)主動(dòng)學(xué)習(xí)算法在設(shè)計(jì)時(shí)假設(shè)專家的標(biāo)注都是對(duì)的，專家是一個(gè)“完美的神諭”(perfect oracle)。現(xiàn)實(shí)生活中，專家也有出錯(cuò)的時(shí)候。當(dāng)主動(dòng)學(xué)習(xí)向?qū)＜也樵兊玫降臉?biāo)注帶有噪聲時(shí)，將會(huì)影響學(xué)習(xí)的性能[1]。

解決標(biāo)注噪聲最常見(jiàn)的一種策略是對(duì)樣本進(jìn)行多個(gè)標(biāo)注，然后采用“少數(shù)服從多數(shù)”的投票方法，決定出對(duì)樣本最終的標(biāo)注結(jié)果。這種方法的一個(gè)主要缺點(diǎn)是對(duì)每個(gè)需要標(biāo)注的樣本進(jìn)行多次標(biāo)注的次數(shù)都相同。從代價(jià)敏感(cost-sensitive)的角度來(lái)講，這樣代價(jià)往往太高。

本文的貢獻(xiàn)在于：(1)在選擇那些需要專家標(biāo)注的無(wú)標(biāo)注數(shù)據(jù)時(shí)，使用集成學(xué)習(xí)方法和置信度差異度量方法，以有效減少標(biāo)注噪聲對(duì)學(xué)習(xí)性能的影響；(2)采用一種自我訓(xùn)練方法(self-training)[2]，將那些置信度高的數(shù)據(jù)，直接加入有標(biāo)記數(shù)據(jù)集中，無(wú)需向?qū)＜易稍儯瑥亩?jié)省了學(xué)習(xí)代價(jià)(cost)，使得在相同代價(jià)情況下，主動(dòng)學(xué)習(xí)取得更好的效果。

1 相關(guān)工作

當(dāng)前，根據(jù)獲得未標(biāo)注樣例的方式不同，主動(dòng)學(xué)習(xí)分為兩類：基于池的主動(dòng)學(xué)習(xí)(pool-based)和基于流的主動(dòng)學(xué)習(xí)(stream-based)[1]。基于流的主動(dòng)學(xué)習(xí)，未標(biāo)注樣例只能一個(gè)一個(gè)地進(jìn)入到學(xué)習(xí)系統(tǒng)，系統(tǒng)要么決定查詢它，要么直接拋棄它。在基于池的主動(dòng)學(xué)習(xí)系統(tǒng)中，始終維護(hù)著一個(gè)較大的未標(biāo)注樣例的集合，并從中選取那些最具代表性的樣例向?qū)＜疫M(jìn)行查詢。在本文中，最具代表性的樣例是集成學(xué)習(xí)得到的多個(gè)分類器對(duì)樣本進(jìn)行分類時(shí)，分類置信度差異值最大的樣本，即分類器意見(jiàn)最不一致的樣本[3]。本文針對(duì)基于池的主動(dòng)學(xué)習(xí)展開(kāi)。

在機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘領(lǐng)域，將代價(jià)考慮進(jìn)去，被稱之為代價(jià)敏感學(xué)習(xí)(cost-sensitive learning)[4]，目前引起了人們的廣泛關(guān)注。在文獻(xiàn)[4]中，列出的代價(jià)有很多種，但最重要并在實(shí)際生活中廣泛存在的是誤判代價(jià)(misclassification cost)和檢測(cè)代價(jià)(test cost)。為簡(jiǎn)化問(wèn)題，本文只考慮檢測(cè)代價(jià)。

自我訓(xùn)練的方法self-training[2]是一種研究半監(jiān)督學(xué)習(xí)的算法。它的主要思想是：在已有的有標(biāo)注樣本集合上，訓(xùn)練得到相應(yīng)的分類器。利用這些分類器，對(duì)未標(biāo)注樣本進(jìn)行分類，那些分類置信度高的未標(biāo)注樣本，連同它們的預(yù)測(cè)標(biāo)注，加入到已標(biāo)注樣本集合中。在這個(gè)新的有標(biāo)注樣本集合上，重新訓(xùn)練得到相應(yīng)的分類器，循環(huán)該過(guò)程，直到滿足相應(yīng)的終止條件停止。

2 置信度差異代價(jià)敏感的主動(dòng)學(xué)習(xí)算法

設(shè)X={x1,…,xN}表示無(wú)標(biāo)注數(shù)據(jù)集。從X中隨機(jī)選取部分?jǐn)?shù)據(jù)組成集合L，|L|通常是|X|的10%。對(duì)L中的數(shù)據(jù)，要求專家對(duì)其進(jìn)行標(biāo)注。假設(shè)專家標(biāo)注時(shí)，如果標(biāo)注出錯(cuò)，其概率p∈(0,0.5)。在標(biāo)注后的集合L上，利用bootstrap[5]重抽樣技術(shù)，產(chǎn)生K個(gè)樣本集。在這K個(gè)樣本集上，利用支持向量機(jī)SVMs，集成學(xué)習(xí)得到K個(gè)分類器H={h1, …,hK}。

對(duì)X中除L外剩余的無(wú)標(biāo)注樣本XL中的每個(gè)無(wú)標(biāo)記樣本(設(shè)為xi)，利用分類器H對(duì)其進(jìn)行分類，分類的置信度記為cj(xi)，j∈(1, …,K)。設(shè)K個(gè)分類器對(duì)xi進(jìn)行分類時(shí)，分類的置信度的平均值為α(xi,H)，則：

(1)

當(dāng)分類置信度的平均值α(xi,H)大于某一設(shè)定的門(mén)限值，如0.75時(shí)，則直接利用“少數(shù)服從多數(shù)投票法”，確定xi的分類標(biāo)注，而不必向?qū)＜疫M(jìn)行咨詢，這樣可以節(jié)省分類的代價(jià)(cost)。

當(dāng)分類置信度的平均值α(xi,H)小于規(guī)定的門(mén)限值θ(如0.75)時(shí)，對(duì)其分類置信度差異值d(xi,H)進(jìn)行計(jì)算：

d(xi)=cmax(xi)-cmin(xi)

(2)

式(2)中，cmax(xi)是K個(gè)分類器H={h1, …,hK}分別對(duì)xi分類時(shí)，最高的分類置信度值,cmin(xi)則是K個(gè)分類器中分類置信度的最低值。d(xi)的值越大，表明K個(gè)分類器對(duì)xi分類時(shí)，分歧越大，這樣的樣本是最需要向?qū)＜疫M(jìn)行查詢的。

在向?qū)＜易稍僒次(本文中T=50)，對(duì)T個(gè)無(wú)標(biāo)注樣本進(jìn)行標(biāo)注后，將這T個(gè)樣本加入有標(biāo)記樣本集合中，在這個(gè)擴(kuò)充了的有標(biāo)注樣本集合上，重新利用bootstrap取樣技術(shù)，重新訓(xùn)練生成H={h1, …,hK}，依次循環(huán)。

算法中預(yù)設(shè)一個(gè)總預(yù)算代價(jià)B，每次向?qū)＜易稍円淮危珺就減去一個(gè)標(biāo)注成本cost(xi)，從而實(shí)現(xiàn)代價(jià)敏感(cost-sensitive)。

表1 基于置信度差異代價(jià)敏感的主動(dòng)學(xué)習(xí)算法

本文的置信度差異代價(jià)敏感的主動(dòng)學(xué)習(xí)算法，完整描述如表1所示。

3 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)中使用UCI數(shù)據(jù)集[6]mushroom和spambase驗(yàn)證本文算法有效性。數(shù)據(jù)集spambase本來(lái)有4601個(gè)樣本，每個(gè)樣本包含56個(gè)屬性。我們使用PCA將56個(gè)屬性降維到20。數(shù)據(jù)集mushroom包含8124個(gè)樣本，每個(gè)樣本包含23個(gè)屬性。

將本文提出的算法與Tong & Koller算法[7]進(jìn)行對(duì)比。每條曲線都是獨(dú)立運(yùn)行50次后的平均值。算法開(kāi)始時(shí)|L|的大小為200，樣本中加入的標(biāo)準(zhǔn)噪聲率分別為{0.1,0.2}。圖1是實(shí)驗(yàn)的結(jié)果。圖1中，Ours代表本文提出的算法。Tongs代表Tong & Koller算法。從圖1可以看出，在不同的噪聲率下，在兩個(gè)數(shù)據(jù)集上，在向?qū)＜也樵兿嗤拇螖?shù)的情況下，相對(duì)于Tong & Koller算法，本文提出的算法都能得到更低的分類錯(cuò)誤率，從而提高了該主動(dòng)學(xué)習(xí)算法的效率。

(a)spambase在10%噪聲率的結(jié)果

(b)spambase在10%噪聲率的結(jié)果

(c)mushroom在10%噪聲率的結(jié)果

(d)mushroom在10%噪聲率的結(jié)果

4 結(jié)束語(yǔ)

本文提出了一種在較小的代價(jià)下，應(yīng)對(duì)標(biāo)注噪聲的主動(dòng)學(xué)習(xí)算法。該算法通過(guò)利用集成學(xué)習(xí)時(shí)分類置信度的差異性最大化，選出那些最富信息性的無(wú)標(biāo)注數(shù)據(jù)。在決定是否向?qū)＜易稍儠r(shí)，又使用了一種自我訓(xùn)練(self-training)方法，從而節(jié)省了代價(jià)。使得本算法既有多專家系統(tǒng)的抗標(biāo)注噪聲功能，又不會(huì)使得代價(jià)太高。由于主動(dòng)學(xué)習(xí)后形成的有標(biāo)注樣本集的分布可能與整個(gè)樣本集的分布不一致，最終形成的分類器可能存在偏差(bias)。如何使得主動(dòng)學(xué)習(xí)后形成的有標(biāo)注樣本能代表整個(gè)樣本集的分布，是下一步研究的重點(diǎn)。

[1] Settles B .Active Learning Literature Survey[R].University of Wisconsin-Madison, 2010.

[2] Zhu X.Semi-supervised learning literature survey[R].University of Wisconsin-Madison, 2005.

[3] Zhou Z H,Li M.Semi-supervised learning by disagreement[J].Knowledge and Information Systems,2010,24(3):415-439.

[4] Turney P D.Types of cost in inductive concept learning[C]// Proceedings of the Workshop on Cost-Sensitive Learning at the Seventeenth International Conference on Machine Learning,2000:15-21.

[5] Efron B,Tibshirani R. An introduction to the Bootstrap[M].CRC Press, 1994：8-10.

[6] Blake C,Keogh E,Merz C J.UCI repository of machine learning databases[EB/OL].http://www.ics.uci.edu/mlearn/MLRepository.html.

[7] Tong S,Koller D.Support vector machine active learning with applications to text classification[J].Journal of Machine Learning Research, 2001, 2:45-66.

(責(zé)任編輯：張凱兵)

ActiveLearningAlgorithmBasedonConfidenceDiversityCostSensitivity

Wu Yongcheng

(SchoolofComputerEngineering,JingchuUniversityofTechnology,Jingmen,Hubei448000,China)

It is known that the noise in labels deteriorates the performance of active learning. To reduce the inverse effect of the noise, many algorithms based on multiple experts have been proposed. The drawback of these algorithms lies in that it costs too much. This paper proposes a self-training method which can directly determine the labels of some unlabeled instances without consulting the experts so as to reduce the cost of learning. Simultaniously, to improve learning efficiency, confidence diversity as a measure is employed and uncertain instances are selected to be labeled without consulting experts. The experimental results on UCI data sets validated the effectiveness of the proposed method．

active learning; noisy data; confidence diversity; self-training

TP391. 41

A

2095-4824(2013)06-0016-04

2013-10-05

武永成(1971- )，男，湖北仙桃人，荊楚理工學(xué)院計(jì)算機(jī)工程學(xué)院講師，碩士。