結合雙流形映射的不完備多標簽學習

許智磊,黃睿

(上海大學通信與信息工程學院,上海 200444)

0 引言

傳統的單標簽學習在實際應用中已無法有效應對復雜且多語義的海量數據。為處理這種多語義數據,多標簽學習應運而生。與一個實例只屬于一個類別的單標簽學習不同,多標簽學習認為一個實例可以同時具有多個類別標簽。近年來,多標簽學習受到研究者的重視,并被廣泛應用于情感分類[1]、音樂檢索[2]、文本分類[3]、圖像/視頻標注[4-5]等領域。

多標簽學習通常被認為是單標簽學習的擴展。根據單標簽學習思想進行多標簽學習,算法可以分為兩類[6]:問題轉換和算法適應。第一類是將學習任務轉換為一個或多個單標簽分類任務[7-8];第二類則在已有的單標簽學習算法上進行改進,從而能適應多標簽數據[9-10]。與標簽互斥的單標簽學習不同,多標簽學習中的類標簽之間通常存在相關性。例如,一個樣本具有標簽“駱駝”,則大概率也具有標簽“沙漠”,而不太可能有標簽“海洋”。有效利用標簽相關性能提升算法的分類性能。根據標簽相關性的利用情況,多標簽學習算法又可分為一階、二階和高階三類。一階方法將多標簽數據轉換為多個互不相關的單標簽數據,單獨處理每個類別標簽,完全不考慮標簽相關性[4,11];二階和高階方法分別利用了標簽對之間的相關性[12-14]和所有標簽集或標簽子集間的相關性[15-16]。

標簽相關性一般通過分析訓練樣本獲得,現有的大部分多標簽學習算法默認觀察到的標簽矩陣是完整的。然而在實際應用中,隨著數據量的急劇增長,主觀的人工標注往往不能獲取完整的標簽信息,導致標簽矩陣是不完備的。而不完備的標簽信息會使得標簽相關性的計算不準確,同時也會誤導學習算法造成算法性能的下降。因此,提升不完備多標簽學習算法性能的一個關鍵問題是在缺失標簽情況下,如何正確地估算和利用標簽相關性。

針對上述不完備多標簽學習問題,目前已經提出一些基于標簽相關性的分類方法。例如,文獻[17]提出的基于邊信息的加速矩陣補全算法和文獻[18]提出的基于矩陣補全的多視角弱標簽學習算法。兩種算法都采用了同一種策略,即嘗試將標簽和特征空間組合成一個統一的空間,再使用標準的矩陣補全技術來補充缺失的標簽,并且都利用了低秩結構來隱式地捕獲標簽相關性。然而,它們僅能在轉導方式下適用,較大地限制了其應用。也有一些方法不使用轉導學習的策略。比如,半監督不完備標簽多標簽學習算法[19]利用低秩矩陣恢復模型進行自動標簽計算。但是,只有全局低秩標簽結構被隱式捕獲,而局部低秩結構被忽略。因此,為了同時考慮全局和局部的低秩結構,文獻[20]提出缺失標簽情況下的判別多標簽學習算法,通過對具有相同標簽實例的所有預測施加低秩結構算法,并對具有不同標簽的實例預測施加最大分離結構,來完成對局部和全局低秩標簽結構的建模。除了上述利用低秩結構來隱式地捕獲標簽相關性以提升算法性能的方法外,也有研究者直接顯式地利用標簽相關性矩陣。例如,文獻[21]提出的缺失特征和標簽情況下的多標簽學習算法,不僅利用流形正則化技術保持了實例相似性和標簽相關性,而且還利用矩陣分解理論來進行缺失標簽的恢復。文獻[22]提出基于特征-標簽雙映射的缺失標簽-類屬特征學習(FLDM)算法,利用標簽向量直接計算標簽相關性,并通過特征-標簽雙映射學習目標權重進行潛在的不完全標簽恢復。然而,上述的標簽相關性都是直接從訓練數據中計算得到的,當訓練數據中缺失大量的類標簽時,標簽相關性的計算結果會不準確。針對這個問題,文獻[23]利用從不完整的訓練數據中學習得到的標簽相關性矩陣來進行缺失標簽的恢復,提出了聯合類屬特征和標簽相關性的缺失標簽下的多標簽學習(LSLC)算法。文獻[24]通過建立輔助標簽矩陣,對標簽子空間施加低秩和高秩約束,并同時學習一個標簽相關性矩陣來進行缺失標簽的恢復和分類器的訓練,提出基于低秩標簽子空間變換的不完備多標簽學習(LRMML)算法。此外,還可以在模型中加入實例相關性,以進一步提高模型性能。文獻[25]提出的基于實例顆粒度判別的缺失標簽情況下的弱多標簽學習(C2ML)算法,能夠同時利用實例流形和標簽流形對標簽流形進行重構訓練特征標簽映射,并進行分類器的學習和標簽矩陣的恢復。然而,以上算法一般通過回歸系數矩陣直接將數據從特征空間映射到標簽空間,認為兩個空間存在線性映射關系。但在多數情況下,這種線性回歸假設是不合理的。

本文提出一種結合雙流形映射的不完備多標簽學習(ML-DMM)算法。該算法構造兩種流形映射:特征流形映射保留實例的局部結構;標簽流形映射捕獲并利用標簽的相關性。具體說來,ML-DMM首先由拉普拉斯映射[26]構造數據的低維流形,然后通過回歸系數矩陣和標簽相關性矩陣將初始特征空間和初始標簽空間分別映射到該低維流形上,從而形成一種雙流形映射結構來提升算法性能。最后利用迭代學習得到的回歸系數矩陣進行多標簽分類。

1 ML-DMM算法

在多標簽學習中,由n個樣本構成的訓練數據集表示為X=[x1,x2,…,xn]T∈n×d,對應的邏輯型類標簽集表示為Y=[y1,y2,…,yn]T∈{0,1}n×q,其中,d表示特征維數,q表示標簽個數。樣本xi∈d對應的邏輯標簽為yi={yi1,yi2,…,yiq}∈{0,1}q,其中,1表示標簽與實例相關,0表示標簽與實例無關或標簽缺失。

1.1 基于低維流形的回歸模型

回歸模型的目標函數一般形式如下:

(1)

受流形學習理論的啟發,算法認為數據通過線性回歸矩陣映射到數據的低維流形Z∈n×q,該數據空間和低維流形空間之間應具有相似的局部結構信息。具體地,若樣本xi和xj在原始特征空間是相似的,則低維流形空間中對應的zi,：和zj,：也是相似的,其中zi,：和zj,：分別表示Z的第i行和第j行。因此,可以通過最小化流形正則化項來進行結構約束,Sij是鄰接矩陣的第(i,j)項,表示實例xi和xj之間的相似度。當xi∈Nk(xi)orxj∈Nk(xj)時,鄰接矩陣S計算如下:

(2)

其中:σ是參數,通常設置為1;Nk(xi)表示實例xi的k近鄰集合,本文中k值取為20。在其他情況下Sij=0。

因此,結合了低維流形Z的回歸模型目標函數為:

(3)

1.2 雙流形映射的構建

不完備的多標簽數據使得一般多標簽算法很難捕獲正確的標簽相關性。為了解決這個問題,ML-DMM定義了一個增廣標簽矩陣YC,其中,C∈q×q為標簽相關性矩陣,每一個元素Cij表示第i個標簽和第j個標簽的相關性程度。與不完備的原始數據標簽矩陣Y相比,增廣標簽矩陣YC通過標簽相關性矩陣進行了擴充,從而擁有更豐富的標簽信息。為了增強低維流形Z和增廣標簽分布之間的一致性,通過加入回歸項來約束標簽相關性矩陣。同時,這也形成了標簽空間和流形空間之間的映射關系。結合式(3)中的回歸項兩者共同構成了一種雙映射結構。因此,結合雙流形映射的模型表示為:

(4)

其中:α1、α2和α3是權衡參數。

1.3 ML-DMM優化求解

式(4)的優化問題涉及3個優化參數Z、W和C。由于W的L1范數不具有光滑性,因此采用加速近端梯度[27]方法來優化目標函數。

1.3.1Z的更新

當W和C固定時,對Z求導并令導數等于0,得到封閉解:

(5)

其中:I是一個d×d的單位矩陣。

1.3.2W的更新

當Z和C固定時,目標函數僅為W的函數,被記為F(W),則W的計算如下:

(6)

其中:H是指希爾伯特空間。

f(W)和g(W)的定義如下:

(7)

(8)

QL(W,W(t))=f(W(t))+〔?f(W(t)),W-W(t)〕+

(9)

(10)

(11)

(12)

其中:W(t)為W在第t次迭代的一個中間變量;Wt表示W在第t次迭代的結果;f(W)的導數為?f(W)=XT(XW-Z);proxε(·)為元素軟閾值運算符。

proxε(·)定義如下:

proxε(wij)=(|wij|-ε)+sign(wij)

(13)

1.3.3C的更新

當Z和W固定時,對C求導并令導數等于零,得到封閉解:

C=(α1YTY+2α3I)-1α1YTZ

(14)

其中:I是一個q×q的單位矩陣。

1.3.4 利普希茨常數計算

為了考察f(W)的利普希茨連續性,給定W1和W2,根據f(W)的導數?f(W)可以推斷:

(15)

其中:ΔW=W1-W2。

因此,目標函數的利普希茨常數計算為:

(16)

1.4 ML-DMM算法流程

算法1ML-DMM算法

輸入訓練數據集X,訓練標簽集Y,權重參數α1、α2、α3

輸出回歸系數矩陣W,標簽相關性矩陣C,流形Z

1.初始化:構建拉普拉斯矩陣L;W0,W1←(XTX+λI)-1XTY;C←zeros(q,q);b0,b1←1;t←1;

2. 重復

3.根據式(16)計算利普希茨常數Lf;

4.根據式(5)更新Z;

7.W(t+1)←W(t);

9.根據式(14)更新C;

10.t←t+1;

11. 達到停止標準;

12. Z*←Zt;

13. W*←Wt;

14. C*←Ct;

1.5 ML-DMM算法復雜度分析

所提ML-DMM算法的時間復雜度可以從4個部分分別進行分析,即ML-DMM算法流程中步驟3的利普希茨常數Lf計算、步驟4的流形Z更新、步驟6的權重系數矩陣W更新和步驟9的標簽相關性矩陣C更新。計算利普希茨常數的復雜度為O(nd2);更新Z的復雜度為O(nq2+ndq);更新W的復雜度為O(nd2+qd2+ndq);更新C的復雜度為O(nq2+q3)。因此,聯合4個部分復雜度,ML-DMM的總時間復雜度為O(q3+(n+q)d2+nq2+ndq)。

2 實驗

2.1 數據集

在8個多標簽數據集上進行實驗來驗證所提算法的性能。所有數據集的詳細信息如表1所示。

表1 實驗數據集Table 1 Experimental datasets 單位:個

2.2 實驗設置

本文的實驗環境為Windows 10 64 bit操作系統,處理器為AMD Ryzen 7 5800H CPU,內存為16 GB。

為了驗證所提算法的有效性,選取5種多標簽學習算法與ML-DMM算法進行比較。ML-DMM算法的參數α1～α3在{2-8,2-9,…,22}中選取。5種對比算法及其參數設置分別為:1)LLSF[29]學習用于多標簽分類的類屬特征,參數α和β在{2-10,2-9,…,210}中選取;2)GLOCAL[30]利用全局和局部標簽相關性來恢復缺失標簽以進行多標簽學習,參數λ=1,λ1～λ5在{10-5,10-4,…,101}中選取,k在{0.1q,0.2q,…,0.6q}中選取,g在{5,10,15,20}中選取;3)LSML[31]通過學習高階標簽相關性來補充不完整標簽矩陣,將缺失標簽矩陣恢復和類屬特征學習統一到一個框架中,參數λ1～λ4在{10-5,10-4,…,103}中選取;4)FLDM[22]通過特征標簽雙映射進行潛在的缺失標簽恢復,以有效地獲得目標權重,參數α、β和γ在{2-4,2-2,…,213}中選取,參數λ設置為2-1;5)LRMML[24]通過建立輔助標簽矩陣,對標簽子空間施加低秩和高秩約束,從而進行缺失標簽的恢復,參數δ設置為0.005,參數λR、λL和λT在{10-10,10-9,…,105}中選取。所有算法均通過網格搜索確定最優參數。

實驗采用平均精度(AP)、平均ROC 曲線下面積(AUC)、1-錯誤率(OE)、排序損失(RL)[6]4種廣泛使用的多標簽學習評價指標來衡量算法性能。這4種評價指標的取值范圍都為0～1,其中,AP和AUC的值越大,OE和RL的值越小,表示分類性能越好。

2.3 實驗結果分析

實驗將標簽缺失率設置為10%、30%和50%,以此來比較訓練標簽矩陣不完備程度對算法性能的影響。同時,在每類標簽中至少保留一個樣本且每個樣本至少保留一個正標簽的前提下,根據預設的缺失率隨機丟棄完整標簽矩陣中的元素。所有實驗都采用5倍交叉驗證,并將5次運行的測試集性能指標進行平均,最終評價結果以平均值±標準差的形式呈現。

表2～表5展現了6種算法分別在3種缺失率和8個數據集上的性能指標。其中,↑和↓分別表示該指標值越大或越小,算法分類性能越好,ρ表示標簽缺失率。表6進一步展現了不同算法在所有數據集的不同缺失率下各個評價指標的平均排序值。最優結果均以粗體表示。

表2 6種算法在AP (↑)上的實驗結果Table 2 Experimental results of six algorithms on AP (↑)

表3 6種算法在AUC (↑)上的實驗結果Table 3 Experimental results of six algorithms on AUC (↑)

表5 6種算法在RL (↓)上的實驗結果Table 5 Experimental results of six algorithms on RL(↓)

表6 不同算法在所有數據集上的平均排序值Table 6 Average ranking value of different algorithms on all datasets

從表2～表5的實驗結果可以看出,隨著標簽缺失率的提高,所有算法的性能在不同數據集上都有不同程度的下降。這說明標簽缺失越多,對算法性能的影響越大。其中,LLSF性能下降最多,明顯劣于GLOCAL、LSML、FLDM、LRMML和ML-DMM。原因在于LLSF沒有針對標簽缺失的情況進行建模。而在其他5種算法中,雖然ML-DMM在數據集Yeast、Science和Corel6k001上未體現最優性能,但從總體上來看,其性能具有明顯優勢。原因在于算法的雙流形映射不僅利用標簽相關性矩陣擴充了缺失標簽矩陣信息,還聯合加強了流形空間、原始特征空間和原始標簽空間之間的關聯來提升分類性能。從表6的排序結果可以看出,ML-DMM算法在所有數據集上的平均排名是最高的。

在8個數據集上對于3種缺失率和4種評價指標,ML-DMM算法始終排名第一。

為評估6種算法的顯著性差異,引入Nemenyi 檢驗[32]。當兩種比較算法在所有數據集上的平均排名差異大于臨界差異(CD)時,認為兩種算法存在顯著差異。CD計算公式如下:

(17)

其中:k為算法個數;N為數據集個數;qα為系數。置信度水平α=0.05,有6個算法和24個數據集(3種缺失率×8個多標簽數據集),查表可得系數qα=2.850,從而計算得到臨界差異為1.539 2。圖1展現了每個評價指標對應的CD圖,數軸表示算法的排名,即算法的性能在每個評估子圖中從右到左依次下降。當兩種算法性能沒有顯著性差異時用紅色實線連接;反之,則無實線連接(彩色效果見《計算機工程》官網HTML版)。ML-DMM在每個子圖中始終位于最右側,這表明所提算法的性能排名是最高的。同時,ML-DMM在評價指標AUC和RL上顯著優于其他算法,在AP和OE上與FLDM無顯著性差異。實驗結果和分析充分表明了ML-DMM在處理不完備多標簽學習時的有效性。

圖1 基于 Nemenyi 檢驗的算法性能比較Fig.1 Performance comparison of algorithms based on Nemenyi test

3 結束語

本文提出一種結合雙流形映射的不完備多標簽學習算法ML-DMM。該算法構造了特征流形映射和標簽流形映射。前者用于保留實例的局部結構;后者用于捕獲并利用標簽的相關性。首先由拉普拉斯映射構造數據低維流形,然后通過回歸系數矩陣和標簽相關性矩陣將初始特征空間和初始標簽空間分別映射到低維流形上,形成一種雙流形映射的結構來聯合加強流形空間、原始特征空間和原始標簽空間之間的關聯,提升算法性能。在不同標簽缺失率下的多標簽分類實驗結果表明,相比于其他算法,ML-DMM具有更好的性能。ML-DMM算法通過迭代學習標簽相關性矩陣,并將其用于不完備標簽矩陣的增強,但未考慮標簽相關性隱含的低秩結構特點。下一步將在標簽相關性學習中有效利用其低秩性來提高不完備多標簽學習性能。