張 琳,姜高霞,王文劍
(山西大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院, 山西 太原 030006)
機(jī)器學(xué)習(xí)是現(xiàn)代計(jì)算機(jī)快速發(fā)展的領(lǐng)域之一,涉及各個(gè)領(lǐng)域的應(yīng)用。目前,研究人員在深度學(xué)習(xí)方面取得了很多成果,但其可解釋性依然是難以解決的問題。因此,人在機(jī)器學(xué)習(xí)中的作用依然不可忽視。眾所周知,傳統(tǒng)的數(shù)據(jù)注釋依賴于領(lǐng)域?qū)<遥杀靖咔液臅r(shí)長(zhǎng),其限制了標(biāo)簽數(shù)據(jù)集的獲得。而隨著眾包系統(tǒng)的快速發(fā)展,標(biāo)簽數(shù)據(jù)的獲取變得比較容易,但由于收集的標(biāo)簽中存在噪聲,眾包數(shù)據(jù)訓(xùn)練的學(xué)習(xí)模型質(zhì)量通常低于專家標(biāo)記數(shù)據(jù)訓(xùn)練的模型。直觀上,學(xué)習(xí)模型的質(zhì)量與標(biāo)簽的質(zhì)量密切相關(guān),因此提高標(biāo)簽質(zhì)量是提高學(xué)習(xí)模型質(zhì)量的一個(gè)直接途徑。
在眾包平臺(tái)獲取帶噪聲的標(biāo)簽數(shù)據(jù)集后,通過設(shè)計(jì)算法,從多個(gè)標(biāo)簽集合中歸納出一個(gè)完整的標(biāo)簽,這些算法被稱為真相推理算法(ground truth inference algorithms)。在不知道某實(shí)例真實(shí)標(biāo)簽的情況下,一般使用真相推理算法推斷其真實(shí)標(biāo)簽,但單純的推理算法的學(xué)習(xí)是相對(duì)困難的。因此,利用實(shí)例數(shù)據(jù)分布信息幫助推理算法推斷真實(shí)標(biāo)簽十分重要,且希望每個(gè)實(shí)例的集成標(biāo)簽為其真實(shí)標(biāo)簽。
使用重復(fù)標(biāo)簽來提高標(biāo)簽質(zhì)量可以追溯到20多年前,Smyth等在1994年使用極大似然估計(jì)算法和重復(fù)標(biāo)記去解決金星圖像標(biāo)記的不確定性[1]。多人投票機(jī)制(majority vote,MV)是一種最簡(jiǎn)單高效的方法,除了MV算法,近幾年還提出了一些其他的推理算法。這些推理算法可以根據(jù)其數(shù)學(xué)方法分為兩類:基于機(jī)器學(xué)習(xí)的算法和基于線性代數(shù)的方法?;跈C(jī)器學(xué)習(xí)的方法是當(dāng)前研究的主流,早在1979年,Dawid等提出了一種基于最大似然估計(jì)的真相推理算法(Dawid-Skene model,DS)[2],除了為每個(gè)例子推斷出集成標(biāo)簽外,DS還為每個(gè)貼標(biāo)簽者估計(jì)了混淆矩陣;Demartini等提出的ZenCrowd[3]算法通過對(duì)標(biāo)記者質(zhì)量建模來確定每個(gè)樣本屬于特定類的概率,但其沒有關(guān)注任務(wù)難度;而Whitehill等提出的GLAD[4]算法則在此基礎(chǔ)上,對(duì)任務(wù)難度建模,將此結(jié)果應(yīng)用到對(duì)標(biāo)記者質(zhì)量的建模中,使推斷結(jié)果具有更高的準(zhǔn)確性,但導(dǎo)致其代碼運(yùn)行迭代過程十分緩慢。Sheng等和Ipeirotis等分別于2008年和2014年在研究了MV算法后,提出了簡(jiǎn)單的概率模型來描述單樣本的標(biāo)簽質(zhì)量[5-6],但其假設(shè)每個(gè)標(biāo)簽的質(zhì)量均相同。Jung等在2011年針對(duì)實(shí)例,提出了一種利用評(píng)分機(jī)制和權(quán)重提高M(jìn)V精度的方法[7],其中推理模型通常是基于概率圖形模型,在概率圖形模型中進(jìn)行推理的一種重要的主流通用方法是期望最大化(expectation-maximization,EM)算法。2014年Li等在DS模型下推導(dǎo)了具有任意有限標(biāo)記者和項(xiàng)目數(shù)的一般類型聚合規(guī)則的錯(cuò)誤率邊界[8],可用于設(shè)計(jì)最優(yōu)加權(quán)多數(shù)投票。Khetan等在2016年也分析了廣義DS模型下眾包的可靠性[9]。在基于DS改進(jìn)的模型中,當(dāng)類的數(shù)量較大而標(biāo)簽的數(shù)量較少時(shí),會(huì)造成混淆矩陣十分稀疏。
眾包通?;趦蓚€(gè)基本的共同假設(shè):貼標(biāo)簽者有不同的可靠性,并且獨(dú)立做決定。一些推理算法只遵循這些假設(shè),例如DS和ZenCrowd。而Raykar等[10]還基于標(biāo)簽標(biāo)記者在提供標(biāo)簽時(shí)的偏見,IEThresh[11]則是基于了學(xué)習(xí)者的經(jīng)驗(yàn),正標(biāo)簽閾值(positive label frequency threshold,PLAT)[12]方法假設(shè)標(biāo)簽者對(duì)消極和積極的例子有不同的校正率,LC-ME[13]算法假設(shè)每個(gè)項(xiàng)都屬于一個(gè)潛在類,標(biāo)簽程序?qū)ν活惖捻?xiàng)具有一致的視圖,但對(duì)不同類的項(xiàng)具有不一致的視圖。
由于僅根據(jù)帶噪音的標(biāo)簽推斷實(shí)例的真實(shí)標(biāo)簽比較困難,因此除了一般的真相推理算法外,近幾年一些學(xué)者提出了根據(jù)實(shí)例特征和標(biāo)記者影響等因素去提高標(biāo)簽集成效果的方法。Tian等在2018年提出了M3V算法[14],Ruiz等在2018年提出了一種通過變分高斯過程從眾包中學(xué)習(xí)正確標(biāo)簽的方法[15]。還有一些學(xué)者提出不學(xué)習(xí)真相推理算法,而直接根據(jù)帶噪音的標(biāo)簽集學(xué)習(xí)分類算法。另一些學(xué)者利用多任務(wù)學(xué)習(xí)方法去處理眾包標(biāo)簽噪音,也取得了不錯(cuò)的效果。目前來看,利用其他信息提高眾包標(biāo)簽集的集成算法效果是可行的。但現(xiàn)有的算法在多分類問題中的表現(xiàn)相對(duì)較差,且在眾包系統(tǒng)中獲取標(biāo)簽時(shí),標(biāo)記者越少代價(jià)越小,因此希望可以在獲取的眾包標(biāo)簽數(shù)較少的情況下得到較優(yōu)的標(biāo)簽推斷結(jié)果。由此考慮使用聚類算法研究眾包噪音標(biāo)簽過濾問題。本文提出的算法主要通過對(duì)實(shí)例特征聚類及分析標(biāo)記者相似性兩部分來提高標(biāo)簽推斷的準(zhǔn)確率。
由于提高集成標(biāo)簽的質(zhì)量面臨巨大的挑戰(zhàn),許多研究人員試圖在標(biāo)簽聚合過程中引入更多的先驗(yàn)信息,這些方法違反了通用標(biāo)簽聚合的不可知前提,即除了收集的噪聲標(biāo)簽外,不能使用任何先驗(yàn)知識(shí)。實(shí)例的特征攜帶有價(jià)值的信息,如果可以應(yīng)用適當(dāng)?shù)臋C(jī)器學(xué)習(xí)方法,這些特征可以幫助識(shí)別和分類這些項(xiàng)目。因此,在標(biāo)簽推斷過程中完全忽略實(shí)例的特征是不明智的,且應(yīng)用特征并不違反不可知論的先決條件。
本文算法主要通過設(shè)置標(biāo)記者置信度推斷實(shí)例的集成標(biāo)簽。標(biāo)記者置信度由兩部分確定:第一部分是通過聚類算法將實(shí)例的特征部分聚類,再根據(jù)聚類結(jié)果和標(biāo)記者提供的標(biāo)簽,確定每位標(biāo)記者的正確率,從而得到標(biāo)記者置信度的第一部分基于數(shù)據(jù)分布特征的置信度;第二部分通過計(jì)算標(biāo)記者提供的標(biāo)簽間的相似度得到基于標(biāo)記信息的置信度,若某位標(biāo)記者與其他標(biāo)記者提供的結(jié)果越相似,則其置信度越高。將兩部分置信度合并,由此得到完整的標(biāo)記者置信度。
1.2.1 基于數(shù)據(jù)分布特征的置信度
通過對(duì)數(shù)據(jù)特征執(zhí)行聚類算法得到基于數(shù)據(jù)分布特征的置信度。通常數(shù)據(jù)集中大多數(shù)的數(shù)據(jù)標(biāo)記問題是較為簡(jiǎn)單的,標(biāo)記者可以較容易地為這些問題打出正確的標(biāo)簽,而對(duì)于較為困難的一部分?jǐn)?shù)據(jù),標(biāo)記者所提供的標(biāo)簽很有可能是錯(cuò)誤的,這時(shí)可以通過聚類結(jié)果與某一組標(biāo)簽的一致性來確定某個(gè)標(biāo)記者的置信度,從而提高標(biāo)簽推斷結(jié)果的準(zhǔn)確率。
圖1通過一個(gè)簡(jiǎn)單的例子來說明聚類置信度的可行性。圖中圓形、正方形、三角形分別表示3類數(shù)據(jù),圖1(a)表示數(shù)據(jù)的真實(shí)分布情況,圖2(b)表示標(biāo)記者w1提供的數(shù)據(jù)劃分結(jié)果,圖1(c)表示另一標(biāo)記者w2提供的數(shù)據(jù)劃分結(jié)果,圖1(d)表示將原始數(shù)據(jù)進(jìn)行聚類得到的分類結(jié)果。
圖1中兩位標(biāo)記者在為眾包數(shù)據(jù)提供標(biāo)簽時(shí)均存在錯(cuò)誤標(biāo)簽,而此時(shí)有較為可靠的聚類結(jié)果,則可利用這一結(jié)果幫助確定標(biāo)記者的置信度。
由于采用了聚類算法,因此聚類結(jié)果與眾包標(biāo)記結(jié)果的相似性采用常見的聚類評(píng)價(jià)指標(biāo)Rand Index系數(shù)表示,將其作為標(biāo)記者的第一部分置信度:
(1)
式中:Tp表示在聚類結(jié)果和標(biāo)記者提供的標(biāo)簽中均屬于同一類的實(shí)例數(shù);Tn表示在聚類結(jié)果和標(biāo)記者提供的標(biāo)簽中均不屬于同一類的實(shí)例數(shù);Fp表示聚類結(jié)果屬于一類,而標(biāo)記者提供的標(biāo)簽不屬于一類的實(shí)例數(shù);Fn表示聚類結(jié)果不屬于一類,而標(biāo)記者提供的標(biāo)簽屬于一類的實(shí)例數(shù);n表示實(shí)例數(shù)。
1.2.2 基于標(biāo)簽信息的置信度
在眾包數(shù)據(jù)中,某位標(biāo)記者與其他標(biāo)記者所提供的標(biāo)簽信息越相似,則這位標(biāo)記者提供的標(biāo)簽越可信。因此,將標(biāo)記者之間的相似性作為標(biāo)記者置信度的一部分,用以計(jì)算完整的置信度。
用pab表示標(biāo)記者a與標(biāo)記者b所提供的標(biāo)簽信息間的相似度,pa表示標(biāo)記者a與其他標(biāo)記者的平均相似度,a,b∈(1,m)。
(2)
(3)
根據(jù)上文分別得到基于數(shù)據(jù)分布特征和標(biāo)簽信息的置信度v1和v2,v1,v2∈(0,1),計(jì)算兩者的幾何平均值V,即標(biāo)記者置信度,其中V∈(0,1)。
(4)
圖2所示為標(biāo)記者置信度V隨v1、v2變化的趨勢(shì)圖。由圖可知,v1、v2均對(duì)V有整體的影響。
(a) 原始數(shù)據(jù)的分布(a) Original data distribution
(b) w1的數(shù)據(jù)劃分結(jié)果(b) Data partitioning results of w1
(c) w2的數(shù)據(jù)劃分結(jié)果(c) Data partitioning results of w2
(d) 數(shù)據(jù)聚類結(jié)果(d) Data clustering results圖1 數(shù)據(jù)標(biāo)記Fig.1 Data labeling
若使用算數(shù)平均值,則當(dāng)其中一個(gè)變量不變時(shí),另一變量對(duì)其整體的影響有限,不能充分表現(xiàn)變量較小時(shí)對(duì)整體權(quán)重的影響。
圖2 置信度的變化情況Fig.2 Variation of confidence
根據(jù)得到的標(biāo)記者置信度推斷得出實(shí)例的真實(shí)標(biāo)簽:
(5)
式中,p(li)表示實(shí)例推斷標(biāo)簽為li的可能性,i∈(1,k)。
雙重置信度推斷(double confidence inference,DC)算法的步驟如算法1所示。
算法1 雙重置信度推斷算法
本文算法在每個(gè)數(shù)據(jù)集上的每種標(biāo)記數(shù)下的計(jì)算復(fù)雜度O(n)=n·p·l,其主要由算法1的第5步推斷實(shí)例的真實(shí)標(biāo)簽過程產(chǎn)生。其中:n為數(shù)據(jù)集實(shí)例數(shù);p表示標(biāo)記數(shù),即為該實(shí)例提供標(biāo)簽的人數(shù);l為數(shù)據(jù)集的類數(shù)。
本節(jié)對(duì)表1所示的10個(gè)真實(shí)世界數(shù)據(jù)集進(jìn)行實(shí)驗(yàn),并與4種經(jīng)典的方法MV、DS、GLAD、ZC算法在標(biāo)簽推斷準(zhǔn)確率和時(shí)間效率兩方面進(jìn)行了比較。
表1 實(shí)驗(yàn)數(shù)據(jù)集
使用的數(shù)據(jù)集均為UCI數(shù)據(jù)集,參照文獻(xiàn)[16]中所示方法模擬生成眾包數(shù)據(jù)。首先為每位標(biāo)記者隨機(jī)生成標(biāo)記準(zhǔn)確率t,t∈(0.3,0.9);再根據(jù)每位標(biāo)記者的準(zhǔn)確率對(duì)原數(shù)據(jù)集隨機(jī)抽樣,樣本數(shù)據(jù)按照準(zhǔn)確率t被賦予正確標(biāo)簽,其他數(shù)據(jù)均被隨機(jī)賦予錯(cuò)誤標(biāo)簽,由此生成標(biāo)簽數(shù)據(jù)集。實(shí)驗(yàn)為每個(gè)數(shù)據(jù)集生成了標(biāo)記者數(shù)分別為1~10的標(biāo)簽數(shù)據(jù)集,為保證實(shí)驗(yàn)結(jié)果可信,每次的標(biāo)簽生成過程重復(fù)5次。
考慮數(shù)據(jù)分布的多樣性,實(shí)驗(yàn)中采用的是經(jīng)典的噪聲環(huán)境下基于密度的聚類(density-based spatial clustering of applications with noise,DBSCAN)算法。DBSCAN算法包含3個(gè)參數(shù),分別是X、ε、mp。其中:X為數(shù)據(jù)集的特征;ε表示樣本間的最小距離,即若兩樣本間距離小于ε,則樣本互為鄰域;mp表示形成簇類所需的最小樣本個(gè)數(shù),將mp設(shè)定為特征數(shù)的2倍。ε和mp的計(jì)算方法分別為:
ε=d(0.005l(d))
(6)
mp=2dx
(7)
其中,d表示排序后的數(shù)據(jù)特征的距離向量,ε為該向量千分之五處的值,l(·)表示計(jì)算向量長(zhǎng)度的函數(shù),dx表示數(shù)據(jù)集的特征數(shù)。
為驗(yàn)證本文算法的有效性,從時(shí)間效率及標(biāo)簽推測(cè)準(zhǔn)確性兩方面考慮方法效率。時(shí)間效率為各個(gè)算法在每個(gè)數(shù)據(jù)集上的5次實(shí)驗(yàn)的平均運(yùn)行時(shí)間,標(biāo)簽準(zhǔn)確率如式(8)所示。
(8)
2.2.1 不同標(biāo)簽數(shù)對(duì)準(zhǔn)確率的影響
圖3所示為5種算法在10個(gè)數(shù)據(jù)集上實(shí)例被標(biāo)記次數(shù)為2~10的準(zhǔn)確率。由圖3可知,5種方法的實(shí)驗(yàn)準(zhǔn)確率均隨標(biāo)簽數(shù)的增多而提高。標(biāo)簽數(shù)為1時(shí)的實(shí)驗(yàn)結(jié)果參考性不大,因此圖中未表示出來。在標(biāo)簽數(shù)為2時(shí),MV算法與GLAD算法的實(shí)驗(yàn)效果均較差,DS算法的表現(xiàn)也差強(qiáng)人意。在大部分?jǐn)?shù)據(jù)集上,當(dāng)標(biāo)簽數(shù)多于2時(shí),各個(gè)算法的準(zhǔn)確率均隨著標(biāo)簽數(shù)的增多快速提升,當(dāng)每個(gè)實(shí)例的標(biāo)簽數(shù)多于7時(shí),各個(gè)算法的準(zhǔn)確率均趨于1,效果相差較小,且?guī)缀醪辉匐S著標(biāo)簽數(shù)的增多而有所提高。
(a) Svmguide2
(b) Svmguide4
(c) Vehicle
(d) Phishing
(e) Steel Plates Faults
(f) Segment
(g) Satimage
(h) Letter
(i) Australian
(j) Breast_cancer 圖3 不同標(biāo)記者數(shù)目在各數(shù)據(jù)集下的算法準(zhǔn)確率Fig. 3 Accuracy of the algorithm for the number of different markers in each data set
在真實(shí)眾包數(shù)據(jù)中,每個(gè)樣本的標(biāo)簽數(shù)均大于7的可能性較小,因此主要分析標(biāo)簽數(shù)為4~7的實(shí)驗(yàn)結(jié)果。顯而易見,在大部分?jǐn)?shù)據(jù)集上,當(dāng)標(biāo)簽數(shù)為4~7時(shí),DC算法的實(shí)驗(yàn)效果略優(yōu)于其他4種算法,其他情況時(shí)與另外4種算法的實(shí)驗(yàn)效果相近,而在實(shí)際的標(biāo)注中,得到的標(biāo)簽數(shù)據(jù)往往沒有很多,因此DC算法相較其他方法有一定優(yōu)勢(shì)。DS算法及ZC算法在二分類問題中的實(shí)驗(yàn)效果比MV、GLAD、DC算法好,而在多分類問題中GLAD、DC算法的效果較其在二分類中的效果有明顯的提升。
圖4給出了各算法在標(biāo)簽數(shù)分別為4~7時(shí)準(zhǔn)確率的臨界差異(critical difference,CD)圖。CD圖是基于統(tǒng)計(jì)顯著性差異的算法對(duì)比模式,可以給出不同算法的排名。圖4中算法排名越小表示算法效果越好。在標(biāo)簽數(shù)為4~7時(shí),DC算法準(zhǔn)確率均高于其他4種算法。圖中算法的平均排名基于10個(gè)數(shù)據(jù)集和10種標(biāo)簽數(shù)量。
(a) 標(biāo)簽數(shù)為4(a) Number of labels is 4
(b) 標(biāo)簽數(shù)為5(b) Number of labels is 5
(c) 標(biāo)簽數(shù)為6(c) Number of labels is 6
(d) 標(biāo)簽數(shù)為7(d) Number of labels is 7圖4 臨界差異圖Fig. 4 Critical difference diagram
2.2.2 與其他算法的比較分析
表2所示為5種方法分別在標(biāo)簽數(shù)為1~10時(shí)的實(shí)驗(yàn)數(shù)據(jù)均值的比較。由表2所示可知,DC算法在8個(gè)數(shù)據(jù)集上的表現(xiàn)最優(yōu),相比最差的實(shí)驗(yàn)數(shù)據(jù)分別提高了1.9%、2.23%、1.52%、2.14%、1.62%、1.45%、3.86%、5.39%;相比其他4種算法平均提高了1.12%、1.52%、0.65%、1.11%、1.06%、0.72%、1.68%、2.26%。在Segment和Satimage數(shù)據(jù)集上的表現(xiàn)也僅次于最好的算法結(jié)果,且分別相差1.03%、0.79%。這是由于數(shù)據(jù)集的類別數(shù)增多,噪音分散嚴(yán)重。
在各個(gè)數(shù)據(jù)集中,由于標(biāo)記者的準(zhǔn)確率隨機(jī)給出,且絕大部分標(biāo)記者的準(zhǔn)確率高于0.5,因此MV算法的準(zhǔn)確率隨著標(biāo)簽數(shù)的增多而提高,而在真實(shí)數(shù)據(jù)集中,標(biāo)記者的準(zhǔn)確率并沒有隨機(jī)給出的準(zhǔn)確率高,導(dǎo)致MV算法的準(zhǔn)確率其實(shí)并沒有實(shí)驗(yàn)所示的那么高。又因?yàn)闃?biāo)簽數(shù)據(jù)中的噪音是根據(jù)給定的標(biāo)記者的準(zhǔn)確率隨機(jī)給出,所以多分類噪音沒有二分類問題中的噪音結(jié)果集中,而是被分散到了所有可能的標(biāo)簽上,這樣就導(dǎo)致MV算法在多分類問題中的準(zhǔn)確率更高,其他4種算法也受此影響。
當(dāng)標(biāo)記者準(zhǔn)確率較低時(shí),GLAD算法相較其他算法在各個(gè)數(shù)據(jù)集中的實(shí)驗(yàn)效果較優(yōu),但該算法的迭代時(shí)間相較其他算法過長(zhǎng);DS算法使用的基本算法是EM算法,其實(shí)驗(yàn)效果受初值影響較大,DC算法結(jié)果為運(yùn)行效果最好的結(jié)果;ZC算法在各數(shù)據(jù)集上的表現(xiàn)相對(duì)MV、DS、GLAD算法是最好的。DC算法在大部分?jǐn)?shù)據(jù)集上的實(shí)驗(yàn)效果相較其他4種算法均為最優(yōu)的。
表2 各算法在各數(shù)據(jù)集中的平均準(zhǔn)確率
圖5為5種算法在10個(gè)數(shù)據(jù)集上的平均運(yùn)行時(shí)間,由于GLAD算法的運(yùn)行時(shí)間相較其他4種算法長(zhǎng)很多,因此圖中所示的GLAD算法的運(yùn)行時(shí)間為真實(shí)運(yùn)行時(shí)間的1%。5種算法的運(yùn)行時(shí)間均隨數(shù)據(jù)集數(shù)目的增大而變長(zhǎng),其中:MV算法的運(yùn)行時(shí)間最短;ZC算法與DS算法耗時(shí)相近;DC算法實(shí)驗(yàn)過程中要運(yùn)行聚類算法,因此耗時(shí)較DS、ZC、MV算法略長(zhǎng)。
圖5 算法運(yùn)行時(shí)間Fig.5 Running time of algorithms
本文考慮了數(shù)據(jù)分布和標(biāo)簽信息兩方面的置信度,首先根據(jù)DBSCAN聚類算法將樣本數(shù)據(jù)聚類,由此結(jié)果得到標(biāo)記者置信度的第一部分,再由標(biāo)記者相似性計(jì)算得到置信度的第二部分,最后根據(jù)標(biāo)記者置信度推斷實(shí)例的真實(shí)標(biāo)簽。實(shí)驗(yàn)結(jié)果表明,DC算法在標(biāo)簽數(shù)處于3~7的情況時(shí),效果優(yōu)于其他算法。
由于DC算法使用了聚類方法,考慮到聚類結(jié)果的準(zhǔn)確性可能對(duì)實(shí)驗(yàn)結(jié)果有一定影響,因此未來工作將針對(duì)聚類算法對(duì)實(shí)驗(yàn)結(jié)果的影響以及糾正聚類結(jié)果的準(zhǔn)確性這兩部分展開,以提高標(biāo)簽推斷算法的準(zhǔn)確性。