融合權(quán)重機制和改進(jìn)SDIM的偏標(biāo)記分類算法

張慧婷，謝紅薇，周 輝，張 昊

1.太原理工大學(xué) 軟件學(xué)院，太原030024

2.太原理工大學(xué) 信息與計算機學(xué)院，太原030024

機器學(xué)習(xí)分為監(jiān)督學(xué)習(xí)、半監(jiān)督學(xué)習(xí)、無監(jiān)督學(xué)習(xí)三大類。在監(jiān)督學(xué)習(xí)中，每個示例都必須有完善的標(biāo)記信息，需要科研人員花費大量時間設(shè)定標(biāo)記，過程較為繁瑣；而在無監(jiān)督學(xué)習(xí)中，標(biāo)記的稀缺性使得學(xué)習(xí)效果較差，所以半監(jiān)督學(xué)習(xí)作為監(jiān)督學(xué)習(xí)和無監(jiān)督學(xué)習(xí)之間的平衡點，無疑是未來機器學(xué)習(xí)的重要研究方向。

偏標(biāo)記學(xué)習(xí)作為半監(jiān)督學(xué)習(xí)中的一種，由Hüllermeier[1]、NamNguyen[2]、Cour[3]提出。目前應(yīng)用于醫(yī)療診斷[4]、人臉自動識別[5]、Web挖掘[6]等領(lǐng)域。與偏標(biāo)記學(xué)習(xí)較為相似的有多標(biāo)記學(xué)習(xí)，不同之處在于多標(biāo)記學(xué)習(xí)中一個示例的所有標(biāo)記都是正確的，但偏標(biāo)記學(xué)習(xí)中一個示例的候選標(biāo)記集中卻只有一個標(biāo)記是正確的。目前多標(biāo)記學(xué)習(xí)廣泛應(yīng)用于文本分類[7]、三維模型標(biāo)注[8]、無人機定位[9]等領(lǐng)域。

進(jìn)行偏標(biāo)記學(xué)習(xí)的核心在于消歧，現(xiàn)有的消歧方法分為兩種：基于平均的消歧的和基于辨識的消歧。基于平均的消歧一般為候選標(biāo)記設(shè)置相同的置信度，通過學(xué)習(xí)模型對各候選標(biāo)記的輸出進(jìn)行置信度更新實現(xiàn)消歧[10]?，F(xiàn)有方法中基于平均的消歧的有：陳鴻昶等人[10]提出一種候選標(biāo)記感知的偏標(biāo)記學(xué)習(xí)算法，通過對示例之間以及候選標(biāo)記集之間的相似度進(jìn)行考量，然后構(gòu)建相似圖，最后再對相似圖進(jìn)行學(xué)習(xí)以達(dá)到消歧目的。Zhang等人[11]通過引入糾錯輸出碼（ECOC），將候選標(biāo)記集作為一個整體進(jìn)行消歧，提出了一種簡單而有效的基于平均的消歧的PL-ECOC方法。Zhang等人[12]利用特征空間的流形結(jié)構(gòu)生成候選標(biāo)記集上的歸一化標(biāo)記置信度，再對生成的標(biāo)記置信度進(jìn)行正則化多輸出回歸，建立預(yù)測模型，提出了一種基于特征感知消歧的偏標(biāo)記學(xué)習(xí)方法?；诒孀R的消歧將真實標(biāo)記作為一個隱變量，通過優(yōu)化隱變量的目標(biāo)函數(shù)進(jìn)行消歧?；诒孀R的消歧最近的研究成果主要有：Zhang等人[13]提出了一種基于示例的IPAL方法，通過迭代標(biāo)記傳播過程直接確定示例的真實標(biāo)記，最后基于小誤差分類。Yu等人[14]通過交替的優(yōu)化過程將偏標(biāo)記信息整合到傳統(tǒng)的基于邊緣的分類學(xué)習(xí)框架中，通過解決凸二次優(yōu)化問題學(xué)習(xí)真實標(biāo)記。Tang等人[15]和Wu等人[16]通過將偏標(biāo)記學(xué)習(xí)問題轉(zhuǎn)化為分類問題，將基分類器進(jìn)行集成學(xué)習(xí)，提出了Boosting式的偏標(biāo)記學(xué)習(xí)方法。Ren等人[17]提出的PLE方法，將實體、文本特性和實體類型共同嵌入到相同的低維空間中，利用一個低維空間中語義上相近的對象具有相似特性的性質(zhì)獲取示例相關(guān)性，從而得到真實標(biāo)記。Wang等人[18]闡述了一種SSPL方法，通過在偏標(biāo)記示例和未標(biāo)記示例之間進(jìn)行迭代標(biāo)記傳播，消除偏標(biāo)記示例候選標(biāo)記集的歧義，并為未標(biāo)記示例分配有效標(biāo)記，最后實現(xiàn)對所有示例真實標(biāo)記的預(yù)測。此方法的提出使偏標(biāo)記學(xué)習(xí)有了更加廣泛的應(yīng)用范圍。Feng等人[19]提出了SDIM方法，主張以最大化不同類別示例間的語義差異為理論基礎(chǔ)進(jìn)行模型訓(xùn)練，利用不同類別的示例之間的差異性進(jìn)行消歧，最終預(yù)測出真實標(biāo)記。

上述傳統(tǒng)算法只對示例之間的相似性或者差異性進(jìn)行單方面考量，而一個數(shù)據(jù)集中必然不會只存在相似性或者只存在差異性，因此本文將示例相似性與差異性進(jìn)行綜合考量，對SDIM方法做出改進(jìn)，提出了融合權(quán)重機制和改進(jìn)SDIM的偏標(biāo)記學(xué)習(xí)算法（Fusing the weight mechanism and improving the partial label learning algorithm of SDIM），以下簡稱為WSDIM。本文算法首先對不同類別的示例進(jìn)行語義差異最大化；然后通過求解相關(guān)系數(shù)最大化問題計算相似示例的權(quán)重；最后將判定為同類別的示例按照各自權(quán)重縮小其之間的歐幾里德距離；最終得到更新后的置信矩陣，實現(xiàn)對具有差異性的不同類別的示例和具有相似性的同類別示例的分情況處理，最終預(yù)測出示例的真實標(biāo)記。在UCI數(shù)據(jù)集與真實數(shù)據(jù)集上的實驗結(jié)果顯示，本文算法表現(xiàn)出更高的分類準(zhǔn)確率。

1 SDIM算法

SDIM算法由Feng等[19]提出，針對兩個候選標(biāo)記集完全不同的示例不可能具有相同的真實標(biāo)記這一理論，從標(biāo)記空間出發(fā)通過訓(xùn)練模型的方式擴大真實標(biāo)記必定不同的兩個示例之間的語義差異，最終學(xué)習(xí)到示例的真實標(biāo)記。以下對SDIM算法的介紹將從模型參數(shù)定義、模型訓(xùn)練兩方面進(jìn)行。

1.1 模型參數(shù)定義

遵循傳統(tǒng)的標(biāo)記習(xí)慣，將示例的特征矩陣記為X=[x1,x2,…,xm]T∈Rm×n，標(biāo) 記 矩 陣 記 作：Y=[y1,代表第j個標(biāo)記是第i個示例的候選標(biāo)記，即j∈Si；Yij=0則代表第j個標(biāo)記不是第i個示例的候選標(biāo)記，即j?Si。Si為xi的候選標(biāo)記集，且滿足Si?Y。引入一個偏標(biāo)記置信矩陣P=(p1,p2,…,pm)T∈[0,1]m×l，pi表示示例xi的標(biāo)簽置信度。Pij的大小代表第j個標(biāo)記作為第i個示例的真實標(biāo)記的置信度，且滿足約束假設(shè)Si中有a個候選標(biāo)記，則每個候選標(biāo)記成為示例xi的真實標(biāo)記的初始概率為，即其初始置信度為

1.2 模型訓(xùn)練

定義yi和yj分別為示例xi和示例xj的標(biāo)記向量，則SDIM算法對于不同類別的示例的判定條件為例如對于示例xi和示例xj其對應(yīng)的標(biāo)記向量為，滿足的條件，因為二者的標(biāo)記向量中并沒有共同的標(biāo)記，所以其真實標(biāo)記是絕對不同的[19]。

SDIM的實質(zhì)為擴大兩個不同類別的示例之間的歐幾里德距離，其初始模型如下[19]：表示了示例xi和示例xj之間的歐幾里德距離。對初始模型進(jìn)行整合轉(zhuǎn)化，公式（1）可變形為：

L代表拉普拉斯矩陣，tr代表矩陣的跡。上述公式旨在最大化凸目標(biāo)。對上述公式進(jìn)行模型整合以及變形，可以將其轉(zhuǎn)化為最小化凸目標(biāo)的函數(shù)：其中，E∈Rn×l是模型參數(shù)，之后的學(xué)習(xí)過程將對參數(shù)矩陣E與置信矩陣P進(jìn)行交替優(yōu)化，以得到最優(yōu)解。

控制P為一個常量，對模型參數(shù)E進(jìn)行迭代更新，上式要解決的問題轉(zhuǎn)化為：

將示例x映射到希爾伯特空間為φ(x)，則用φ(x)的線性組合將E表示為E=φ(x)TG，其中G是一個矩陣，且滿足gij∈Rm×l。定義核函數(shù)K=φ(x)φ(x)T，在此處使用高斯核函數(shù)為兩個示例之間的平均歐幾里德距離。所以：

因此式（4）可以表示為：

問題轉(zhuǎn)化為有關(guān)G最小化的問題之后，可求解得：G為對E迭代后的結(jié)果，其中V∈Rn×n是一個單位矩陣。

控制模型參數(shù)E為常量，對P進(jìn)行迭代更新，則式（3）轉(zhuǎn)化為：將E與P進(jìn)行交替優(yōu)化之后得到對測試實例x*的預(yù)測標(biāo)記為：

綜上，原SDIM方法通過對初始模型進(jìn)行整合以及對模型參數(shù)進(jìn)行交替優(yōu)化等一系列操作，實現(xiàn)對模型的迭代更新，最終得到更新后的置信矩陣P，從而預(yù)測出示例x的真實標(biāo)記。

2 改進(jìn)的SDIM算法

SDIM算法作為基于辨識的消歧學(xué)習(xí)的一種，利用不同類別的示例之間的差異性進(jìn)行消歧，但由于缺乏對同類別示例之間相似性的學(xué)習(xí)，以及未能對示例的重要程度予以個性化的考量，因此存在分類準(zhǔn)確率不高的問題。本文針對上述問題在對不同類別的示例進(jìn)行語義差異最大化操作的同時，增加了針對同類別示例縮小其之間語義差異的操作，且通過加入權(quán)重機制對每個示例進(jìn)行不同程度的重要性考量，提出了改進(jìn)后的SDIM算法。其實現(xiàn)的具體方式為：通過相關(guān)系數(shù)最大化計算相似示例的權(quán)重；然后基于計算出的示例權(quán)重判定兩示例是否滿足同類別判定條件；最后將滿足條件的示例定義為同類示例并縮小其間歐幾里德距離，最終得到更新后的置信矩陣并實現(xiàn)對示例的真實標(biāo)記的預(yù)測。

2.1 計算示例權(quán)重

Cij表示示例xi和示例xj之間的協(xié)方差矩陣，Cii和Cjj分別表示示例xi和示例xj的方差矩陣。接下來利用拉格朗日乘數(shù)法對式（10）進(jìn)行求解：

令λi=λj=λ，假設(shè)Cjj可逆，得到：

此時求解廣義特征值即可得到ωi，因此分別得到ωi和ωj的值，即求得了示例xi和示例xj在縮小語義差異時各自應(yīng)當(dāng)賦予的權(quán)重。

2.2 按權(quán)重縮小類內(nèi)距離

經(jīng)過上一節(jié)相關(guān)系數(shù)最大化操作的類是否真正屬于同一類還需進(jìn)一步驗證，以下對示例xj對xi的影響程度進(jìn)行估計，若影響達(dá)到臨界值，則認(rèn)為二者同類，其影響程度用impi,j表示。根據(jù)實驗的調(diào)參最終確定類間距離縮小操作的限定條件為impi,j≥e0.0768，當(dāng)其值大于e0.0768時，認(rèn)定xj與xi屬于同一類別。其公式表示如下：

將所有滿足impi,j≥e0.0768的示例集和記為Ns(xi)，Ns(xi)=[xi1,xi2,…,xia]，集合中的示例分別應(yīng)當(dāng)賦予的權(quán)值，記作Wi=[ωi1,ωi2,…,ωia]T，因此縮小同類示例之間的歐幾里德距離公式為：

其中J=(D-W)T(D-W)，通過特征值分解可得P。本文算法的偽代碼如下所示：

算法1縮小類內(nèi)距離算法偽代碼

最后對于未見示例x*的預(yù)測進(jìn)程進(jìn)行分析。對于未見示例x*的同類別示例集合記作N(x*)，N(x*)中的示例的權(quán)重矩陣為為了表示方便，對于示例的候選標(biāo)記集換一種方式表示為Ti=[ti,1,ti,2,…,ti,n]，當(dāng)ti,n∈Si時，ti,n=1，否則ti,n=0。則x*的預(yù)測標(biāo)記為：

其中，Ⅱ(?)是示性函數(shù)，當(dāng)條件滿足時取1，否則取0。

經(jīng)過上述針對示例之間的差異性進(jìn)行的類間距離擴大，以及針對示例之間的相似性進(jìn)行的類內(nèi)距離縮小操作，已經(jīng)對不同情形下的示例進(jìn)行了有針對性的區(qū)別學(xué)習(xí)，因此本文算法的適用范圍也更加廣泛。最后可以得到對于未見示例x*，其預(yù)測標(biāo)記為：

3 實驗

為驗證本文算法的有效性，將對本文提出的WSDIM與現(xiàn)階段著名的SDIM、IPAL、PL-KNN、CLPL、PL-SVM五種方法進(jìn)行對比。實驗采用公開的UCI數(shù)據(jù)集與真實數(shù)據(jù)集，以下分別對兩種數(shù)據(jù)集上的實驗進(jìn)行對比與分析。本文算法擴大語義差異的模型訓(xùn)練過程中需要選擇最佳的α和β參數(shù)以進(jìn)行模型訓(xùn)練，β大小代表了擴大語義差異在學(xué)習(xí)過程中的重要性，α控制了模型的擬合程度。因為在訓(xùn)練過程中要避免模型欠擬合或過擬合，因此經(jīng)驗證最后選取最佳參數(shù)α=5e-2.48,β=5e-4.76，迭代次數(shù)t∈[20,30]。

3.1 基于真實數(shù)據(jù)集的實驗

實驗采用的真實數(shù)據(jù)集分別來自于人臉標(biāo)注領(lǐng)域的Lost、Soccer Player、Yahoo！News，鳥鳴分類領(lǐng)域的BirdSong，以及目標(biāo)檢測領(lǐng)域的MSRCv2。數(shù)據(jù)集的基本屬性分別為樣本數(shù)、特征數(shù)、類標(biāo)記數(shù)以及平均候選標(biāo)記數(shù)，其具體屬性值如表1所示。

表1 真實偏標(biāo)記數(shù)據(jù)集屬性Table 1 Characteristics of real-world partial label datasets

在真實數(shù)據(jù)集上的實驗結(jié)果如表2所示，本文實驗采用了五折交叉驗證法，其評價指標(biāo)為分類準(zhǔn)確率，本文算法優(yōu)于其他算法的情形以粗體加●表示?？梢钥吹奖疚奶岢龅腤SDIM方法性能優(yōu)于其他方法的比例占到了80%以上。相較于SDIM算法，本文算法在Bird-Song、Soccer Player以及Yahoo!News這三個數(shù)據(jù)集上的表現(xiàn)并未超越原算法。分析這三個數(shù)據(jù)集的特征發(fā)現(xiàn)，此三者共有的特征為其平均候選標(biāo)記數(shù)較小，而本文算法的創(chuàng)新點為增加了最小化同類別示例之間語義差異的操作，且本文判斷兩示例相似的條件為yiTyj≠0，因此當(dāng)示例的平均候選標(biāo)記數(shù)較多的時候，對于本文來說將更易于將其判定為相似，進(jìn)而進(jìn)行類內(nèi)距離縮小的操作。且由于本文算法加入了按權(quán)重縮小類內(nèi)距離的機制，因此對于候選標(biāo)記較多的情況，可以按照不同的情況分別進(jìn)行學(xué)習(xí)，從而使偏標(biāo)記學(xué)習(xí)的學(xué)習(xí)效果更好。所以在一定范圍內(nèi)，隨著平均候選標(biāo)記數(shù)增多，雖然假陽性標(biāo)記也在增多，但本文算法卻更容易進(jìn)行類內(nèi)距離縮小的操作，并且將示例按照不同情況分別進(jìn)行有效充分的學(xué)習(xí)，因此最終的學(xué)習(xí)效果將好于SDIM算法；相反，平均候選標(biāo)記數(shù)相對較低的時候，本文算法的優(yōu)勢將難以顯現(xiàn)，所以會出現(xiàn)學(xué)習(xí)效果略次于原SDIM算法的情形。因此本文算法在Bird-Song、Soccer Player以及Yahoo!News這三個數(shù)據(jù)集上的實驗效果并不及原SDIM算法。接下來對以上三個數(shù)據(jù)集進(jìn)行處理，通過增加示例的假陽性標(biāo)記來實現(xiàn)其平均候選標(biāo)記數(shù)的增加，并將SDIM算法和本文提出的WSDIM算法在經(jīng)過處理后的數(shù)據(jù)集上進(jìn)行實驗，以分類準(zhǔn)確率為評價指標(biāo)驗證本文算法的有效性，實驗結(jié)果如圖1所示。

表2 在真實數(shù)據(jù)集上各算法分類準(zhǔn)確率對比（●|○分別表示好于或次于對比方法）Table 2 Classifification accuracy of each algorithm on real-world datasets

圖1 SDIM和WSDIM在處理后的數(shù)據(jù)集上的性能對比Fig.1 Performance comparison of SDIM and WSDIM on processed data sets

經(jīng)在新數(shù)據(jù)集上的驗證，可以看到在一定范圍內(nèi)隨著平均候選標(biāo)記數(shù)增加，WSDIM算法的學(xué)習(xí)性能顯著提升并達(dá)到峰值，且逐漸超越SDIM算法?？梢?，在候選標(biāo)記數(shù)較高的時候，本文算法可以取得較好的學(xué)習(xí)效果。

3.2 基于合成數(shù)據(jù)集的實驗

合成數(shù)據(jù)集分別來自于UCI數(shù)據(jù)集中的大腸桿菌（ecoli）、車輛（vehicle）以及皮膚病學(xué)（dermatology），其具體屬性如表4所示。以下分別對參數(shù)p和參數(shù)r控制進(jìn)行實驗，p代表了偏標(biāo)記樣本的比例，使其值依次為0.1、0.2、0.3、0.4、0.5、0.6、0.7，r代表除去真實標(biāo)記后平均候選標(biāo)記的數(shù)量，在圖2、圖3、圖4中分別令r=1，r=2，r=3來對各算法的分類準(zhǔn)確率進(jìn)行對比。

圖2 r=1時各算法在三個數(shù)據(jù)集上的性能對比Fig.2 Performance comparison of each algorithm on three data sets(r=1)

圖3 r=2時各算法在三個數(shù)據(jù)集上的性能對比Fig.3 Performance comparison of eachalgorithm on three data sets(r=2)

圖4 r=3時各算法在三個數(shù)據(jù)集上的性能對比Fig.4 Performance comparison of eachalgorithm on three data sets(r=3)

表4 UCI合成數(shù)據(jù)集屬性Table 4 Characteristics of controlled UCI datasets

可以看到在和傳統(tǒng)算法的比較中，本文提出的WSDIM方法在96%的情形中都優(yōu)于傳統(tǒng)算法。當(dāng)r一定時，在ecoli、vehicle以及dermatology三個數(shù)據(jù)集上，當(dāng)p∈[0.1,0.5]，分類準(zhǔn)確率隨著p的增大而上升并達(dá)到一個峰值，同傳統(tǒng)IPAL、CLPL、PLKNN、PLSVM、SDIM算法相比，本文提出的WSDIM算法的峰值表現(xiàn)更高，也意味著當(dāng)p位于最佳值時，WSDIM擁有更高的分類準(zhǔn)確率；和SDIM算法相比，因為加入了按照權(quán)重縮小類內(nèi)距離的創(chuàng)新點，所以當(dāng)p∈[0.5,0.7]時，即面對擁有偏標(biāo)記的示例變多的時候，本文算法也可以根據(jù)不同示例具有的相似性或者差異性做出不同的學(xué)習(xí)策略，因此本文提出的WSDIM算法在偏標(biāo)記數(shù)量增多時表現(xiàn)出一定的穩(wěn)定性，且與SDIM算法相比提升了0.535%~3.718%的分類準(zhǔn)確率。以上實驗以偏標(biāo)記樣本比例p為自變量，展示了隨著參數(shù)p的上升，本文算法與其他傳統(tǒng)算法的分類準(zhǔn)確率的對比，解釋了本文算法的有效性。為了更直觀地展示隨著候選標(biāo)記數(shù)上升，傳統(tǒng)算法的學(xué)習(xí)表現(xiàn)以及本文算法對原SDIM算法做出改進(jìn)后的效果，以下將分別以分類準(zhǔn)確率和消歧準(zhǔn)確率為評價指標(biāo)，以假陽性標(biāo)記數(shù)r的值為自變量進(jìn)行實驗，實驗結(jié)果如圖5、6所示。

圖5 各算法的消歧準(zhǔn)確率隨參數(shù)r的變化Fig.5 Disambiguation accuracy of each algorithm varies with parameter r

圖6 各算法的分類準(zhǔn)確率隨參數(shù)r的變化Fig.6 Classification accuracy of each algorithm varies with parameter r

圖5 、6分別展示了各算法的消歧準(zhǔn)確率和分類準(zhǔn)確率隨r值變化的情況。由于傳統(tǒng)算法只對示例之間的相似性或差異性進(jìn)行了單方面考量，所以其學(xué)習(xí)到的信息有限，因此隨著r值的增大，算法將難以辨別被淹沒在假陽性標(biāo)記中的真實標(biāo)記，最終導(dǎo)致當(dāng)r值上升時，算法的消歧準(zhǔn)確率以及分類準(zhǔn)確率明顯下降。相較而言，因為本文算法對示例的相似性和差異性均進(jìn)行了有效學(xué)習(xí)，所以在r值增大的情況下，仍可以在消歧和分類方面穩(wěn)定表現(xiàn)。和傳統(tǒng)算法相比，當(dāng)r∈[1,5]時本文算法的消歧準(zhǔn)確率提升了0.211%~12.613%，分類準(zhǔn)確率提升了0.287%~25.695%。由以上實驗結(jié)果可知，本文算法在面對偏標(biāo)記樣本比例較高、假陽性標(biāo)記數(shù)較多等不利情況時也能取得較好的學(xué)習(xí)效果，具有廣泛的應(yīng)用情形。

4 結(jié)論

本文提出的WSDIM方法，解決了傳統(tǒng)方法只從示例差異性或者相似性學(xué)習(xí)的片面性，旨在從類間關(guān)系和類內(nèi)距離出發(fā)，分別進(jìn)行語義差異最大化和最小化的操作，且在學(xué)習(xí)過程中加入了權(quán)重機制，有利于對不同示例進(jìn)行不同程度的重要性考量，在UCI數(shù)據(jù)集和真實數(shù)據(jù)集上取得了較好的學(xué)習(xí)性能。但本文算法仍有不足之處，比如未能對學(xué)習(xí)的優(yōu)先級進(jìn)行設(shè)定以更好利用先驗信息。因此下一步將著重對偏標(biāo)記學(xué)習(xí)的優(yōu)先級進(jìn)行研究，以提高學(xué)習(xí)效率。