結(jié)合雙流形映射的不完備多標(biāo)簽學(xué)習(xí)

許智磊,黃睿

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

0 引言

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

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

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

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

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

1 ML-DMM算法

在多標(biāo)簽學(xué)習(xí)中,由n個樣本構(gòu)成的訓(xùn)練數(shù)據(jù)集表示為X=[x1,x2,…,xn]T∈n×d,對應(yīng)的邏輯型類標(biāo)簽集表示為Y=[y1,y2,…,yn]T∈{0,1}n×q,其中,d表示特征維數(shù),q表示標(biāo)簽個數(shù)。樣本xi∈d對應(yīng)的邏輯標(biāo)簽為yi={yi1,yi2,…,yiq}∈{0,1}q,其中,1表示標(biāo)簽與實例相關(guān),0表示標(biāo)簽與實例無關(guān)或標(biāo)簽缺失。

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

回歸模型的目標(biāo)函數(shù)一般形式如下:

(1)

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

(2)

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

因此,結(jié)合了低維流形Z的回歸模型目標(biāo)函數(shù)為:

(3)

1.2 雙流形映射的構(gòu)建

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

(4)

其中:α1、α2和α3是權(quán)衡參數(shù)。

1.3 ML-DMM優(yōu)化求解

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

1.3.1Z的更新

當(dāng)W和C固定時,對Z求導(dǎo)并令導(dǎo)數(shù)等于0,得到封閉解:

(5)

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

1.3.2W的更新

當(dāng)Z和C固定時,目標(biāo)函數(shù)僅為W的函數(shù),被記為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(wǎng)在第t次迭代的結(jié)果;f(W)的導(dǎo)數(shù)為?f(W)=XT(XW-Z);proxε(·)為元素軟閾值運算符。

proxε(·)定義如下:

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

(13)

1.3.3C的更新

當(dāng)Z和W固定時,對C求導(dǎo)并令導(dǎo)數(shù)等于零,得到封閉解:

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

(14)

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

1.3.4 利普希茨常數(shù)計算

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

(15)

其中:ΔW=W1-W2。

因此,目標(biāo)函數(shù)的利普希茨常數(shù)計算為:

(16)

1.4 ML-DMM算法流程

算法1ML-DMM算法

輸入訓(xùn)練數(shù)據(jù)集X,訓(xùn)練標(biāo)簽集Y,權(quán)重參數(shù)α1、α2、α3

輸出回歸系數(shù)矩陣W,標(biāo)簽相關(guān)性矩陣C,流形Z

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

2. 重復(fù)

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

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

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

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

10.t←t+1;

11. 達(dá)到停止標(biāo)準(zhǔn);

12. Z*←Zt;

13. W*←Wt;

14. C*←Ct;

1.5 ML-DMM算法復(fù)雜度分析

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

2 實驗

2.1 數(shù)據(jù)集

在8個多標(biāo)簽數(shù)據(jù)集上進(jìn)行實驗來驗證所提算法的性能。所有數(shù)據(jù)集的詳細(xì)信息如表1所示。

表1 實驗數(shù)據(jù)集Table 1 Experimental datasets 單位:個

2.2 實驗設(shè)置

本文的實驗環(huán)境為Windows 10 64 bit操作系統(tǒng),處理器為AMD Ryzen 7 5800H CPU,內(nèi)存為16 GB。

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

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

2.3 實驗結(jié)果分析

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

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

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

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

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

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

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

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

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

(17)

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

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

3 結(jié)束語

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