邱 勁

（蘇州科技大學(xué) 電子與信息工程學(xué)院，江蘇 蘇州215009）

多標(biāo)簽分類近年來(lái)在圖像自動(dòng)標(biāo)注[1]、多主題文檔分類[2]和蛋白質(zhì)功能預(yù)測(cè)[3]等各種應(yīng)用中受到了廣泛的關(guān)注。與傳統(tǒng)的單標(biāo)簽分類（每個(gè)實(shí)例只屬于一個(gè)類別）不同，多標(biāo)簽分類解決每個(gè)實(shí)例可能與多個(gè)類關(guān)聯(lián)的問(wèn)題。文獻(xiàn)中已經(jīng)給出了大量的算法?，F(xiàn)有的方法大致可以分為兩類：算法自適應(yīng)和問(wèn)題轉(zhuǎn)化[4]。算法自適應(yīng)法嘗試擴(kuò)展現(xiàn)有的單標(biāo)簽分類算法來(lái)處理多標(biāo)簽問(wèn)題。典型示例包括神經(jīng)網(wǎng)絡(luò)[5]、惰性學(xué)習(xí)[6]、Adaboost MR[7]、秩SVM[8]。對(duì)于轉(zhuǎn)化法，通常將多標(biāo)簽分類問(wèn)題轉(zhuǎn)化為多個(gè)單標(biāo)簽分類問(wèn)題，以便可以輕松使用現(xiàn)有的單標(biāo)簽方法。顯著的示例包括二元相關(guān)性法[9]、成對(duì)法[10]和標(biāo)簽嵌入法[11]。

但是多標(biāo)簽分類經(jīng)常涉及高維數(shù)據(jù)，這使得現(xiàn)有方法由于維數(shù)問(wèn)題而變得難以實(shí)現(xiàn)。在文獻(xiàn)中已經(jīng)給出了大量的多標(biāo)簽降維方法。如在文獻(xiàn)[12]中提出了多標(biāo)簽信息隱形語(yǔ)義索引（MLSI），用于多標(biāo)簽降維。多標(biāo)簽信息隱形語(yǔ)義索引（MLSI）使用標(biāo)簽信息來(lái)指導(dǎo)轉(zhuǎn)換的學(xué)習(xí)，并已成功應(yīng)用于多標(biāo)簽文本分類。文獻(xiàn)[13]將經(jīng)典線性判別分析拓展至處理多標(biāo)簽數(shù)據(jù)樣本。但是這并沒(méi)有將標(biāo)簽相關(guān)性考慮在內(nèi)。文獻(xiàn)[14]中提出了一種新型多標(biāo)簽線性判別分析（MLDA），其利用標(biāo)簽相關(guān)性并探索強(qiáng)大的辨別能力以處置多標(biāo)簽DR。文獻(xiàn)[15]中則提出了一種基于依賴最大化的多標(biāo)簽降維方法（MDDM）。該多標(biāo)簽降維方法使用希爾伯特-施密特獨(dú)立性準(zhǔn)則（HSIC）來(lái)獲取特征描述和相關(guān)標(biāo)簽之間的強(qiáng)依賴性。但MDDM需涉及到廣義特征值分解，這使得其對(duì)于高維數(shù)據(jù)的計(jì)算成本大大增加。上述問(wèn)題表明多標(biāo)簽特征提取方法通常需要解決一個(gè)特征值問(wèn)題且該問(wèn)題計(jì)算量非常大。因此近年來(lái)很多學(xué)者對(duì)多標(biāo)簽特征提取中的可擴(kuò)展性問(wèn)題進(jìn)行了相關(guān)研究。文獻(xiàn)[16]中的作者給出了一類廣義特征值問(wèn)題的最小二乘公式并采用共軛梯度算法來(lái)提高訓(xùn)練進(jìn)程。具體而言典型相關(guān)分析和核典型相關(guān)分析已重新表示為最小二乘問(wèn)題，但kMDDM的最小二乘公式仍然是一個(gè)未解決的難題。因此在文中制定了一種有效解決kMDDM的算法-kMDDM的等效最小二乘公式用以降低計(jì)算成本。簡(jiǎn)言之，本文的主要貢獻(xiàn)有以下三點(diǎn)：首先，證明了kMDDM可以重新表示為一個(gè)最小二乘問(wèn)題，基于這種等價(jià)關(guān)系可通過(guò)共軛梯度算法有效推導(dǎo)出kMDDM的解；其次，在多個(gè)基準(zhǔn)數(shù)據(jù)集上進(jìn)行了大量試驗(yàn)用以證明所提出的公式的有效性；最后，將有效的正則化技術(shù)合并至最小二乘框架用以提高泛化性能。

1 基于最小二乘法的有效kMDDM

1.1 最小二乘kMDDM

為了有效地計(jì)算kMDDM，需使用以下定理。

定理1設(shè)b為特征問(wèn)題的特征向量

特征值為λ。如果Kp=b，則p是具有相同特征值λ的特征問(wèn)題的特征向量。

證明 將Kp=b代入式（1），得到

定理1表明在不求解特征問(wèn)題時(shí)，式（1）的解可以通過(guò)以下兩個(gè)步驟得到:第一步，求解特征問(wèn)題（1）得到b；第二步，求出滿足Kp=b的p。

在實(shí)踐中，線性方程Kp=b可能不成立，轉(zhuǎn)而考慮以下最小二乘問(wèn)題

由于K通常是對(duì)稱正定的，因此基于共軛梯度的迭代算法可用于求解最小二乘問(wèn)題（3）。在實(shí)施過(guò)程中使用LSQR算法來(lái)求解稀疏線性方程組和稀疏最小二乘。

上述步驟表明，kMDDM可以重新表示為一個(gè)最小二乘問(wèn)題，此方法被稱為最小二乘kMDDM（LSkMDDM）。

然后開(kāi)始解決特征值問(wèn)題（1）。令Q＝HY∈Rn×c，從而得到

然而，矩陣QQT的大小為n×n，這對(duì)于直接尋找特征值及其相關(guān)向量是很難的。因此利用下面的引理并采用一種計(jì)算可行的方法來(lái)解決這個(gè)問(wèn)題。

引理1如果矩陣QTQ有一個(gè)特征值對(duì)其中vk是對(duì)應(yīng)于特征值σk的歸一化特征向量，那么矩陣QQT有一個(gè)特征值對(duì)是對(duì)應(yīng)于特征值σk的歸一化特征向量。

上述引理表明，為了得到大n×n矩陣QQT的特征系統(tǒng)，可以求解需要較少計(jì)算成本的小c×c矩陣QTQ的特征系統(tǒng)。

以LSkMDDM的計(jì)算成本分析來(lái)結(jié)束本節(jié)。LSkMDDM需要求解特征問(wèn)題（1）和最小二乘問(wèn)題（3）。特征問(wèn)題的計(jì)算需要3/2nc2+9/2c3flam，其就n而言具有線性時(shí)間復(fù)雜度。對(duì)于最小二乘問(wèn)題，LSQR的每次迭代需要2n2+8n。由于最小二乘求解c次，所以LSQR的總成本為Tc（2n2+8n），其中T是迭代次數(shù)。因此，LSkMDDM的總時(shí)間復(fù)雜度為3/2nc2+9/2c3+Tc（2n2+8n）?？紤]到c＜＜n，時(shí)間復(fù)雜度可以改寫(xiě)為2Tcn2+O（m）+O（n），比原公式小得多。

1.2 LSkMDDM拓展

基于kMDDM和最小二乘法之間的等價(jià)關(guān)系提出了LSkMDDM的兩種泛化。

首先，考慮使用正則化技術(shù)來(lái)控制復(fù)雜性并提高泛化性能。一種常見(jiàn)的正則化項(xiàng)是在p上加上l2范數(shù)，為此提供了以下正則化的LSkMDDM（稱為rLSkMDDM）

其中，η＞0是一個(gè)權(quán)衡參數(shù)。這種正則化在機(jī)器學(xué)習(xí)中得到了很好的研究，稱為嶺回歸[17]。通過(guò)將右側(cè)關(guān)于p的導(dǎo)數(shù)設(shè)置為零，得到

最后，得到了一個(gè)閉式解

此外，正交約束也可以合并到kMDDM的最小二乘公式中，從而得到以下表達(dá)式

其中，B是n×c矩陣，其列是（1）的特征向量。約束條件形成一個(gè)Stiefel流形，導(dǎo)致了矩陣流形的一個(gè)典型優(yōu)化問(wèn)題[18]。經(jīng)典的牛頓算法和共軛梯度算法可以拓展到Stiefel流形上來(lái)處理這類問(wèn)題。

2 試驗(yàn)結(jié)果及分析

2.1 試驗(yàn)裝置

首先使用場(chǎng)景和酵母數(shù)據(jù)集來(lái)驗(yàn)證kMDDM和LSkMDDM之間的等價(jià)關(guān)系[19－20]。同時(shí)，利用Yahoo數(shù)據(jù)集、pascal07和RV1三個(gè)高維數(shù)據(jù)集來(lái)進(jìn)一步驗(yàn)證最小二乘模型的有效性。這些數(shù)據(jù)集的重要統(tǒng)計(jì)數(shù)據(jù)如表1所列。

表1 數(shù)據(jù)集統(tǒng)計(jì)匯總

使用由高維網(wǎng)頁(yè)構(gòu)成的多主題網(wǎng)頁(yè)分類數(shù)據(jù)集（表示為Yahoo）來(lái)驗(yàn)證提出的模型的有效性。Yahoo數(shù)據(jù)集如表1所述，其由14個(gè)頂級(jí)類別（即“藝術(shù)與人文”、“社會(huì)與教育”等）構(gòu)成。頂級(jí)類別進(jìn)一步分為多個(gè)二級(jí)子類別，這些子類別構(gòu)成了每個(gè)數(shù)據(jù)集中分類的主題。RCV1數(shù)據(jù)集包含來(lái)自路透社的新聞專線報(bào)道。該數(shù)據(jù)集的處理方法是刪除停止詞、詞干提取并將文檔轉(zhuǎn)換為TF-IDF格式的向量。在試驗(yàn)中使用了一個(gè)包含6 000個(gè)示例的子集，其中3 000個(gè)示例用于訓(xùn)練，其余的用于測(cè)試。

Pascal07數(shù)據(jù)集包含20個(gè)不同對(duì)象類別的9 963個(gè)圖像。本文使用標(biāo)準(zhǔn)訓(xùn)練/測(cè)試分區(qū)來(lái)評(píng)估所提出方法的性能，有5 011張圖像用于訓(xùn)練，4 952張圖像用于測(cè)試。

對(duì)于表1中前兩個(gè)相對(duì)較小的數(shù)據(jù)集，從3個(gè)隨機(jī)分區(qū)中選擇2個(gè)作為訓(xùn)練集，其余的作為測(cè)試數(shù)據(jù)。對(duì)于Yahoo數(shù)據(jù)集，其被分成兩部分：一個(gè)包含4 000個(gè)樣本的訓(xùn)練集和一個(gè)包含剩余樣本的測(cè)試集。接下來(lái)，重復(fù)分區(qū)過(guò)程10次并報(bào)告平均結(jié)果。

試驗(yàn)中用到的五種算法總結(jié)如下：

·KPCA：主成分分析的非線性拓展。KPCA是一種無(wú)監(jiān)督的方法。

·KCCA：核典型相關(guān)分析在試驗(yàn)中采用了更有效的KCCA的最小二乘公式。

·LSkMDDM：kMDDM的最小二乘公式。

·rLSkMDDM：正則化LSkMDDM。

·OLSkMDDM：正交LSkMDDM。這里使用文獻(xiàn)[21]中提出的算法來(lái)推導(dǎo)OLSkMDDM的解。

在實(shí)施過(guò)程中采用了高斯核函數(shù)，其中核的標(biāo)準(zhǔn)偏差等于數(shù)據(jù)點(diǎn)之間成對(duì)歐氏距離的中值。

利用上述算法可得到一個(gè)變換矩陣并將每個(gè)測(cè)試樣本映射到一個(gè)低維空間。接下來(lái)將低維空間的維數(shù)設(shè)置為c（標(biāo)簽的數(shù)量），然后采用多標(biāo)簽k-最近鄰分類器 來(lái)預(yù)測(cè)測(cè)試樣本的標(biāo)簽[22]。

其次，使用七種標(biāo)準(zhǔn)來(lái)評(píng)價(jià)多標(biāo)簽學(xué)習(xí)算法的性能。第一組評(píng)價(jià)標(biāo)準(zhǔn)包括macro F1和micro F1，它們與每個(gè)實(shí)例的標(biāo)簽集預(yù)測(cè)性能有關(guān)。設(shè)f是一個(gè)分類器函數(shù)，f（xi）是由f預(yù)測(cè)的二元標(biāo)簽向量。兩個(gè)評(píng)價(jià)指標(biāo)定義如下

其中，yi是真二元標(biāo)簽向量，例如xi，yi（k）是yi的第k個(gè)元素，fk（x）是f（x）的第k個(gè)元素。

請(qǐng)注意，這兩個(gè)值越大，性能越好。

第二組評(píng)價(jià)標(biāo)準(zhǔn)包括排名損失（RL）、一次誤差、覆蓋率和平均精度（AP），與標(biāo)簽排名性能有關(guān)。這些標(biāo)準(zhǔn)的詳細(xì)說(shuō)明見(jiàn)[23]。還研究了每個(gè)標(biāo)簽的ROC曲線下面積（AUC）[24]。將多標(biāo)簽分類視為c個(gè)二元分類問(wèn)題，并計(jì)算每個(gè)問(wèn)題的AUC。之后報(bào)告所有標(biāo)簽的平均AUC。注意RL、一次誤差和覆蓋率的值越小，而AP和AUC的值越大時(shí)，性能越好。

2.2 kMDDM和LSkMDDM性能分析

首先評(píng)估kMDDM和LSkMDDM的等價(jià)關(guān)系。其中表2描述了kMDDM和LSkMDDM在AUC和兩個(gè)F1分?jǐn)?shù)方面的性能。由表2可知kMDDM和LSkMDDM具有相似的性能這與文中的分析結(jié)果高度一致。

表2 場(chǎng)景和酵母數(shù)據(jù)集的kMDDM和LSkMDDM三方面性能

Yahoo數(shù)據(jù)集在AUC、macroF1和microF1方面的試驗(yàn)結(jié)果報(bào)告如表3和表4所列。

表3 關(guān)于前六個(gè)數(shù)據(jù)集的七種比較算法在AUC（頂部）、macro F1（mac）和micro F1（mic）方面的性能

表4 關(guān)于五個(gè)數(shù)據(jù)集的七種比較算法在AUC（頂部）、macro F1（mac）和micro F1（mic）方面的性能

由表3和表4可知，KPCA取得了比KLSCCA更高的AUC，而KLSCCA在macroF1和microF1方面的性能優(yōu)于KPCA；kMDDM和rLSkMDDM都依賴于HSIC并取得了比KPCA和KLSCCA更好的性能。這表明HSIC在處理高維多標(biāo)簽樣本時(shí)的優(yōu)越性；無(wú)論數(shù)據(jù)集如何，rLSkMDDM在所有數(shù)據(jù)集上都實(shí)現(xiàn)了microF1的最高性能。此外，rLSkMDDM在九個(gè)數(shù)據(jù)集中的macro F1得分最高，而OLSkMDDM在其余兩個(gè)數(shù)據(jù)集上的得分最高。這些觀察結(jié)果表明，通過(guò)結(jié)合正則化技術(shù)和正交約束，可以顯著提高kMDDM最小二乘公式的性能。有趣的是，在所有數(shù)據(jù)集上，rLSkMDDM和OLSkMDDM在AUC方面取得了相當(dāng)相似的性能。

表5 至表7報(bào)告了Yahoo、pascal07和RCV1數(shù)據(jù)集在RL、一次誤差、覆蓋率和AP方面的結(jié)果。結(jié)果也很理想。從表5和表6中可以看出，無(wú)論標(biāo)準(zhǔn)如何，rLSkMDDM在八個(gè)數(shù)據(jù)集上都實(shí)現(xiàn)了最高性能。此外，可以看到OLSkMDDM在pascal07數(shù)據(jù)集上實(shí)現(xiàn)了最佳性能，而rLSkMDDM就RCV1數(shù)據(jù)集在RL、覆蓋率和AP分?jǐn)?shù)方面取得了更好的性能。

表5 關(guān)于前六個(gè)數(shù)據(jù)集的七種比較算法在RL、一次誤差、覆蓋率和AP方面的性能

表6 關(guān)于五個(gè)數(shù)據(jù)集的六種比較算法在RL、一次誤差、覆蓋率和AP方面的性能

表7 pascal07和RCV1的試驗(yàn)結(jié)果

2.3 降維數(shù)的影響

使用Yahoo數(shù)據(jù)集來(lái)測(cè)試維度對(duì)分類性能的影響。首先從Yahoo中選取了四個(gè)高維數(shù)據(jù)集，并用不同的降維方法對(duì)其性能進(jìn)行了評(píng)估。圖1至圖3描述了不同降維條件下AUC、macro F1和micro F1的性能?？梢杂^察到，隨著維數(shù)的增加，所有比較方法的性能都有所提高。特別是，rLSkMDDM和OLSkMDDM往往比其他方法取得更好的性能。

圖1 不同維度的AUC值

圖3 不同維度的微觀F1值

2.4 可擴(kuò)展性評(píng)估

在本試驗(yàn)中，比較了原MDDM與第2.1中給出的MDDM最小二乘公式（LSkMDDM）的可擴(kuò)展性。除了基于SVD的kMDDM方法外，還使用免逆預(yù)處理Krylov子空間方法]來(lái)求解kMDDM的原始特征值問(wèn)題。具體而言，從Yahoo中選擇了四個(gè)數(shù)據(jù)集并通過(guò)將訓(xùn)練集的大小從500改到2 000來(lái)估計(jì)kMDDM和LSkMDDM的計(jì)算時(shí)間，其他數(shù)據(jù)集也可以觀察到類似的趨勢(shì)變化。

計(jì)算時(shí)間如圖4所示可以看出，當(dāng)訓(xùn)練集的大小固定為500時(shí)，所有方法的時(shí)間復(fù)雜度大致相同。然而，隨著訓(xùn)練集規(guī)模的增大kMDDM的時(shí)間復(fù)雜度遠(yuǎn)高于kMDDM-ifp和LSkMDDM。此外，很容易看出最小二乘kMDDM可以進(jìn)行大規(guī)模應(yīng)用。

圖4 隨著樣本量的增加，LSkMDDM、kMDDM和kMDDM-ifp在藝術(shù)、商業(yè)、電腦和教育數(shù)據(jù)集上的計(jì)算時(shí)間比較

圖2 不同維度的macro F1值

3 結(jié)論

本文研究了用于多標(biāo)簽特征提取的高效kMDDM問(wèn)題?；趉MDDM與其最小二乘公式之間建立的等價(jià)關(guān)系可以采用迭代共軛梯度算法來(lái)顯著降低原kMDDM的計(jì)算成本。此外一些前景很好的技術(shù)（如l2-范數(shù)）可以很容易地合并到新的最小二乘公式中從而顯著提高泛化性能?；鶞?zhǔn)數(shù)據(jù)集的試驗(yàn)結(jié)果證明了所提出公式的有效性和效率。