基于標記感知消歧的偏標記學習算法

殷建華,劉振丙,魏黃瞾

(桂林電子科技大學 計算機與信息安全學院,廣西 桂林 541004)

在機器學習中,監督學習是研究最廣泛的一種單標記學習框架。在該學習框架中,每個訓練示例都必須有準確的標記信息。而在很多現實場景中,由于標記需要耗費大量的人力和時間且標記信息存在不確定性和模糊性,導致完全正確且標記唯一的監督數據難以收集。因此,如何利用更符合實際場景的弱監督數據進行學習,已經成為當前機器學習的一個熱門課題[1-3]。

偏標記學習是弱監督學習框架中的一個重要分支,在偏標記學習數據集中,每個訓練示例對應一組候選標記集合,其中只有一個是真實標記,且不能由學習算法直接獲取。偏標記學習的關鍵在于利用有限的監督信息學習一個多分類模型,并有效地預測未見示例的標記。在現實世界中,具有冗余標簽信息的數據比具有顯式標簽信息的數據更容易獲得,而偏標記學習為模糊數據的學習提供了一種有效的解決方案,并被廣泛應用到許多現實生活場景。例如,在醫學診斷任務中[4],醫生可以排除某些疾病的可能性,但通常很難從幾種癥狀相似的疾病中做出診斷。又如,在人臉自動標注中[5],給定一張包含多個面孔的圖片和對應的標題,通過標題可以很容易地獲取圖片中各面孔的語義信息,但是在圖片中,某個特定人臉的語義信息就很難被匹配。此外,偏標記學習在人體動作識別[6]、Web 挖掘[7]、生態信息學[8]、在線標注[9]和自然語言處理[10]等場景也得了實際應用。

偏標記學習的目的是從偏標記訓練數據集中訓練一個分類模型,可以形式化為:給定訓練數據集D={(xi,Si)|1≤i≤m},其中每個偏標記示例xi是一個d維的特征向量,Si為示例xi對應的候選標記集合。yi∈Si為訓練示例xi的真實標記,最終目標是基于數據集D學習一個映射函數?:x→y。

1 標記感知消歧方法

解決偏標記學習問題的關鍵是對候選標記進行消歧,而現有的偏標記學習算法主要通過挖掘樣本的標記空間信息對候選標記進行消歧,忽略了特征信息對消歧過程的促進作用,且在衡量示例相似度時都側重于對特征空間的處理,缺乏對標記空間信息的利用,這些均可能導致方法不是最優的。針對上述存在的缺陷,提出一種基于標記感知消歧的偏標記學習算法(partial label learning algorithm based on label-aware disambiguation,簡稱PL-LAD),該算法更全面地刻畫了示例的相似關系,并將示例的相似關系與標記消歧過程融合,以提高偏標記學習的消歧結果。算法包括3個過程,分別為構建示例相似度矩陣、框架形成、交替優化。

1.1 構建示例相似度矩陣

由于描述訓練示例的相似度矩陣對提高學習模型的消歧能力起著重要的作用,如何充分挖掘示例之間的關系至關重要。PL-LAD算法考慮到包含相同候選標記的訓練示例應該具有更高的相似性這一假設,采用協同特征空間和標記空間的判別信息來計算相似度矩陣W。具體來說,PL-LAD 先為每個類別標記λl,構造了一個基向量,基向量是由標記λl所對應正例與負例均值的差異確定的,其表達式為

其中:Pl和Nl分別為標記λl對應的正樣本集和負樣本集;si是與示例xi相關的標記向量。式(1)中的統計量可以反映類別標記的整體標記分布,且已經被證明有利于在特征空間中對判別信息進行編碼[11]。因此,可以利用組合基cl中的信息來刻畫示例特征空間的相似度。根據對應組合基之間的余弦相似度來計算示例特征空間的相似度矩陣E=[elk]q×q:

為更加全面地刻畫偏標記示例之間的關系,定義一個用于描述標記空間相似度關系的矩陣B=,

其中,blk對應同時包含標記λl和λk的訓練樣本。這里的blk≠bkl,即標記之間的關系是非對稱的。最后,PL-LAD通過整合特征空間和標記空間來計算最終的相似度矩陣W=[wij]m×m,

其中,系數α∈(0,1)用來平衡特征空間和標記空間在計算相似度矩陣中的相對貢獻。

1.2 框架形成

以往偏標記學習算法在模型訓練過程中通常會忽略不同候選標記對消歧過程做出的貢獻不同,即將所有候選標記同等對待,這將導致模型的泛化性能不佳。為此,PL-LAD考慮到示例的相似關系也應保持在標記空間這一流形假設,利用相似度矩陣W和標記空間中的重構誤差來實現候選標記的消歧過程。此外,PL-LAD算法基于最小二乘損失提出一個統一框架,該框架在充分考慮流形假設和模型輸出的情況下,將真實標記分布作為潛在標記置信度矩陣P∈Rm×q,同時進行模型訓練與標記消歧過程,具體表達式為

式(5)中的第1項為損失函數,利用最小二乘損失對預測模型進行優化,第2項確保了標記置信度矩陣P的最優估計,第3項表示模型復雜度。第1個約束項保證了在標記傳播過程中分配給每個訓練示例的標記分布是一致的。第2個約束項則確保了標記只在候選標記之間傳播,且真實標記嚴格地出現在候選標記集合中,且每個非候選標記的置信度必須置零。

1.3 交替優化

式(5)中的優化問題是一個雙凸優化問題[12],PL-LAD算法采用交替迭代優化的方法來解決這個問題。該方法先通過固定變量P來優化更新模型參數Θ和b,然后在固定變量Θ和b的基礎上優化更新變量P。不斷迭代重復這個過程,直到算法收斂或達到最大迭代次數。

根據變量P當前的值優化模型參數Θ和b,在固定變量P的基礎上,利用高斯核函數對示例進行非線性擴展,即zi=?(xi),其中?(·)表示一個高維希爾伯特空間的初始特征空間的映射。將式(5)中的優化問題表示為

由于式(6)中的損失函數是可微的,可用標準的梯度下降法進行求解。PL-LAD 采用了常用的拉格朗日乘子技術,式(6)中的約束優化問題的拉格朗日函數可以表示為

其中,A為拉格朗日乘子矩陣。根據KKT條件求解可得:

通過求解上述線性方程組可得

其中,Γ=(1/2μ)K-1/2Im×m,且K=ZZT,最后,根據式(9)求出預測模型的輸出矩陣:

根據更新的模型參數Θ和b優化變量P?？紤]到偏標記數據原始的標記矩陣帶有噪聲,PL-LAD將模型輸出矩陣Q作為每次迭代的初始標記置信度矩陣,以在迭代中調整每個候選標記的置信度。在固定Θ和b的基礎上,式(5)中的優化問題可表示為

上述優化問題是一個約束標記傳播問題,先將其重寫為一個標準的二次規劃問題,然后借助現成的QP工具進行求解。最后,在整個迭代優化過程完成之后,根據式(9)的模型參數對未見示例進行標記預測。

1.4 PL-LAD算法流程

PL-LAD算法實現分構建示例相似度矩陣、框架形成、交替優化3個階段。第1階段是利用特征空間和標記空間的信息刻畫偏標記示例之間的相似關系。第2階段是將示例的相似關系傳遞到標記消歧過程,并與最小二乘損失共同生成優化框架。第3階段是通過交替迭代優化的方式訓練最優模型參數。算法的詳細過程如下:在給定偏標記訓練集,首先計算出每個類別標記的基向量(步驟1-3),并通過計算組合基之間的余弦相似度來描述示例特征空間的相似度(步驟4),然后構建一個相似度矩陣來描述示例之間的相似性(步驟5)。接著,迭代更新模型參數和標記置信度矩陣(步驟6-10),直到達到最大的迭代次數或該算法收斂。最后,根據式(9)的最優參數對未見示例的標記進行預測。

算法1PL-LAD算法流程

2 實驗

2.1 實驗設置

為分析、評估PL-LAD的性能,在2種數據集上進行了實驗,分別為3組人工合成UCI數據集和6個真實的偏標記數據集。表1和表2分別給出這2種數據集的詳細信息,包括數據集的樣本數目、特征數目和標記類別數目。此外,UCI數據集還給出了實驗配置,真實數據集給出了每個數據集的平均候選標記數目和應用領域。

表1 UCI數據集的數據特征

表2 真實數據集的數據特征

在3組UCI數據集上進行實驗,分別為deter、vehicle和segment。對于每個UCI數據集,依照前人工作中的協議[13-15],通過控制3個參數p、r和ε的不同配置產生噪聲標記。其中:p為偏標記樣本所占比例;r為候選標記集合中偽標記的數量,這里r個假陽性標記是從標記空間中隨機挑選出來的;ε為特定的假陽性標記與真實標記同時出現在候選標記集合中的概率。表1列出了詳細的參數配置,共28(4×7)種。按照這種參數配置,共生成3×4×7=84個不同的人工UCI偏標記數據集。

真實世界的數據集來源于多個應用領域,其中數據集FG-NET[16]來源于面部年齡估計任務,數據集Lost[5]、Soccer Player[17]和Yahoo! News[13]來源于圖像和視頻中的人臉自動命名任務,數據集MSRCv2[18]和Mirflickr[19]來源于目標分類任務。真實世界數據集的特征如表2所示。

2.2 對比實驗算法

為了進一步證明PL-LAD 的有效性,將其與5種先進的偏標記學習算法進行了實驗對比。每種對比算法具體如下:

1)PL-KNN[20]:一種基于平均策略的消歧方法,利用k近鄰的加權投票來預測未見示例。

2)LSB_CMM[18]:一種基于混合模型的最大似然偏標記學習算法,該算法提出了一個基于邏輯斯蒂結棍過程改進的概率模型來解決偏標記學習問題。

3)M3PL[21]:一種基于最大間隔準則的偏標記學習算法,通過最大限度地增加真實標記和非真實記之間的間隔確定目標函數。

4)PL-ECOC[22]:一種非消歧學習算法,該算法采用糾錯輸出編碼技術來解決偏標記學習問題。

5)PALOC[23]:一種基于問題轉換的非消歧算法,將偏標記學習的多分類任務基于一對一的分解策略劃分為二分類任務進行解決。

2.3 實驗結果

2.3.1 UCI數據集

PL-LAD算法在3個UCI數據集展開實驗,圖1～3分別展示了當噪聲標記個數r為1、2、3時,偏標記訓練樣本占比p以步長0.1從0.1增加至0.7各對比算法的分類準確率。圖4展示了當r和p都為1時,共現概率ε以步長0.1從0.1增長到0.7各對比算法的分類準確率。觀察圖1～4可以得出:

圖1 r=1各算法的分類精度

圖3 r=3各算法的分類精度

圖4 r=1,p=1各算法的分類精度

1)在UCI數據集上,PL-LAD 算法的性能整體優于其他比較算法。

2)在deter數據集上,PL-LAD算法分類精度與LSB_CMM 基本持平。在r=1、2中,PL-LAD 在p=0.6時,以1.43%和1.71%低于LSB_CMM。在r=3、p=0.1～0.2時,PL-LAD算法僅以1.41%和1.63%低于M3PL,在r=3、p=0.5～0.7時,略差于LSB_CMM,在r=3、p=0.3時,分類精度達到最高值為92.87%。

3)在vehicle數據集上,PL-LDA 算法的分類性能顯著優于所有對比算法。

4)在segment數據集上,PL-LDA算法分類精度與LSB_CMM 基本持平,僅以0.7%的差距劣于M3PL算法,并優于其他對比算法。

2.3.2 真實數據集

基于十折交叉驗證及顯著性為0.05的成對t檢驗,表3給出了PL-LAD 算法和其他對比算法在真實數據集上的性能(平均分類準確率±標準差)。以表3可看出:

表3 各比較算法在真實數據集上的分類準確率

1)與PL-KNN、LSB_CMM 算法相比,PL-LAD算法在所有數據集上取得了更優的分類性能;

2)與M3PL算法相比,PL-LAD 僅在Lost數據集上劣于M3PL,在其他數據集上的分類性能都優于M3PL。而PL-LAD 僅在數據集MSRCv2 上劣于PL-ECOC,且僅在數據集Yahoo! News 上劣于PALOC算法,在其他數據集上均優于PL-ECOC、PALOC算法;

3)在數據集FG-NET、Mirflickr和Soccer Player上,算法PL-LAD 的分類性能均優于其他對比算法。在Mirflickr和Soccer Player上,PL-LAD 的分類精度最多提高了17.4%和6%;

4)在數據集Lost上,PL-LAD 算法分類精度僅比M3PL低3.6%,優于其他對比算法,其原因在于Lost數據集中各類數據分散較為均勻,M3PL可以更好地實現聚類任務。在數據集MSRCv2 和Yahoo! News上,PL-LAD 僅以3%和2.4%低于PLECOC算法和PALOC算法。由于數據集MSRCv2和Yahoo! News數據集存在類別不平衡的問題,而PL-ECOC和PALOC則是針對不同的類別劃分多個數據集,并訓練多個分類器,最后對所有分類器加權投票來預測未見示例,可以緩解數據中的類不平衡問題。因此,相比PL-ECOC和PALOC,本研究提出的PL-LAD的性能表現略差;

5)在30組(5種對比算法 6個數據集)結果中,PL-LAD在83.3%的情況下顯著優于所有比較算法,在6.7%的情況下取得了與其他算法相當的分類性能。

3 結束語

提出了一種基于標記感知消歧的偏標記學習算法,解決了已有算法計算樣本相似度時標記信息利用不充分的問題,并利用樣本相似關系促進標記消歧過程,以提升模型分類效果。大量實驗表明,PL-LAD算法整體獲得了較好的分類性能。利用不同的方法度量樣本之間的相似性可以得到不同的消歧和分類性能,而PL-LAD 算法僅可以較好地表征樣本之間的關系。因此,在后續工作中,可考慮采用更準確的樣本相似度計算方式,來衡量樣本間的關系,進而得到更佳的分類性能。