融合權重機制和改進SDIM的偏標記分類算法

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

1.太原理工大學 軟件學院，太原030024

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

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

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

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

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

1 SDIM算法

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

1.1 模型參數定義

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

1.2 模型訓練

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

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

L代表拉普拉斯矩陣，tr代表矩陣的跡。上述公式旨在最大化凸目標。對上述公式進行模型整合以及變形，可以將其轉化為最小化凸目標的函數：其中，E∈Rn×l是模型參數，之后的學習過程將對參數矩陣E與置信矩陣P進行交替優化，以得到最優解。

控制P為一個常量，對模型參數E進行迭代更新，上式要解決的問題轉化為：

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

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

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

控制模型參數E為常量，對P進行迭代更新，則式（3）轉化為：將E與P進行交替優化之后得到對測試實例x*的預測標記為：

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

2 改進的SDIM算法

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

2.1 計算示例權重

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

令λi=λj=λ，假設Cjj可逆，得到：

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

2.2 按權重縮小類內距離

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

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

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

算法1縮小類內距離算法偽代碼

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

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

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

3 實驗

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

3.1 基于真實數據集的實驗

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

表1 真實偏標記數據集屬性Table 1 Characteristics of real-world partial label datasets

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

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

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

經在新數據集上的驗證，可以看到在一定范圍內隨著平均候選標記數增加，WSDIM算法的學習性能顯著提升并達到峰值，且逐漸超越SDIM算法。可見，在候選標記數較高的時候，本文算法可以取得較好的學習效果。

3.2 基于合成數據集的實驗

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

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

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

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

表4 UCI合成數據集屬性Table 4 Characteristics of controlled UCI datasets

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

圖5 各算法的消歧準確率隨參數r的變化Fig.5 Disambiguation accuracy of each algorithm varies with parameter r

圖6 各算法的分類準確率隨參數r的變化Fig.6 Classification accuracy of each algorithm varies with parameter r

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

4 結論

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