加速多標簽特征提取的內核依賴最大化

邱 勁

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

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

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

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

1.1 最小二乘kMDDM

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

定理1設b為特征問題的特征向量

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

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

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

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

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

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

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

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

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

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

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

1.2 LSkMDDM拓展

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

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

其中，η＞0是一個權衡參數。這種正則化在機器學習中得到了很好的研究，稱為嶺回歸[17]。通過將右側關于p的導數設置為零，得到

最后，得到了一個閉式解

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

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

2 試驗結果及分析

2.1 試驗裝置

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

表1 數據集統計匯總

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

Pascal07數據集包含20個不同對象類別的9 963個圖像。本文使用標準訓練/測試分區來評估所提出方法的性能，有5 011張圖像用于訓練，4 952張圖像用于測試。

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

試驗中用到的五種算法總結如下：

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

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

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

·rLSkMDDM：正則化LSkMDDM。

·OLSkMDDM：正交LSkMDDM。這里使用文獻[21]中提出的算法來推導OLSkMDDM的解。

在實施過程中采用了高斯核函數，其中核的標準偏差等于數據點之間成對歐氏距離的中值。

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

其次，使用七種標準來評價多標簽學習算法的性能。第一組評價標準包括macro F1和micro F1，它們與每個實例的標簽集預測性能有關。設f是一個分類器函數，f（xi）是由f預測的二元標簽向量。兩個評價指標定義如下

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

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

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

2.2 kMDDM和LSkMDDM性能分析

首先評估kMDDM和LSkMDDM的等價關系。其中表2描述了kMDDM和LSkMDDM在AUC和兩個F1分數方面的性能。由表2可知kMDDM和LSkMDDM具有相似的性能這與文中的分析結果高度一致。

表2 場景和酵母數據集的kMDDM和LSkMDDM三方面性能

Yahoo數據集在AUC、macroF1和microF1方面的試驗結果報告如表3和表4所列。

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

表4 關于五個數據集的七種比較算法在AUC（頂部）、macro F1（mac）和micro F1（mic）方面的性能

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

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

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

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

表7 pascal07和RCV1的試驗結果

2.3 降維數的影響

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

圖1 不同維度的AUC值

圖3 不同維度的微觀F1值

2.4 可擴展性評估

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

計算時間如圖4所示可以看出，當訓練集的大小固定為500時，所有方法的時間復雜度大致相同。然而，隨著訓練集規模的增大kMDDM的時間復雜度遠高于kMDDM-ifp和LSkMDDM。此外，很容易看出最小二乘kMDDM可以進行大規模應用。

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

圖2 不同維度的macro F1值

3 結論

本文研究了用于多標簽特征提取的高效kMDDM問題?；趉MDDM與其最小二乘公式之間建立的等價關系可以采用迭代共軛梯度算法來顯著降低原kMDDM的計算成本。此外一些前景很好的技術（如l2-范數）可以很容易地合并到新的最小二乘公式中從而顯著提高泛化性能?；鶞蕯祿脑囼灲Y果證明了所提出公式的有效性和效率。