加速多標(biāo)簽特征提取的內(nèi)核依賴最大化

邱 勁

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

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

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

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

1.1 最小二乘kMDDM

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

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

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

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

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

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

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

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

然后開始解決特征值問題（1）。令Q＝HY∈Rn×c，從而得到

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

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

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

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

1.2 LSkMDDM拓展

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

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

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

最后，得到了一個閉式解

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

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

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

2.1 試驗(yàn)裝置

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

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

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

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

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

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

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

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

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

·rLSkMDDM：正則化LSkMDDM。

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

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

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

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

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

請注意，這兩個值越大，性能越好。

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

2.2 kMDDM和LSkMDDM性能分析

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

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

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

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

表4 關(guān)于五個數(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)簽樣本時的優(yōu)越性；無論數(shù)據(jù)集如何，rLSkMDDM在所有數(shù)據(jù)集上都實(shí)現(xiàn)了microF1的最高性能。此外，rLSkMDDM在九個數(shù)據(jù)集中的macro F1得分最高，而OLSkMDDM在其余兩個數(shù)據(jù)集上的得分最高。這些觀察結(jié)果表明，通過結(jié)合正則化技術(shù)和正交約束，可以顯著提高kMDDM最小二乘公式的性能。有趣的是，在所有數(shù)據(jù)集上，rLSkMDDM和OLSkMDDM在AUC方面取得了相當(dāng)相似的性能。

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

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

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

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

2.3 降維數(shù)的影響

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

圖1 不同維度的AUC值

圖3 不同維度的微觀F1值

2.4 可擴(kuò)展性評估

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

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

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

圖2 不同維度的macro F1值

3 結(jié)論

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