基于神經網絡探究標簽依賴關系的多標簽分類

宋 攀 景麗萍

(交通數據分析與挖掘北京市重點實驗室(北京交通大學) 北京 100044) (16120413@bjtu.edu.cn)

隨著計算機技術的發展和廣泛應用，文字、圖片、視頻等多種形式的數據持續產生并呈現爆炸式的增長.近些年，多標簽分類受到許多研究人員的關注.傳統的分類模型假設實例只屬于一個特定的類別，其本質是學習一個從特征空間到標簽空間的映射：f(x)→y,即對給定實例x預測其相對應的標簽y.這種分類學習也稱為單標簽分類學習.然而在大多數實際分類任務中，一個實例往往可能同時屬于多個類標簽.例如，在文本分類中，一篇文本可能同時屬于政治、經濟、體育等多個主題；在場景分類中，一幅圖片可能同時屬于室外、城市、日落等多個場景.針對這類數據，分類任務也相應地變為預測一個實例可能具有的多個標簽，該分類學習稱為多標簽分類學習.

盡管在過去的研究中，多標簽學習已經得到了廣泛關注并取得了一系列的進展，但仍存在若干問題和挑戰有待于進一步的深入研究并解決.其中，如何學習和利用多個標簽之間的依賴關系是目前被普遍認可和關注的一個關鍵問題.例如，在場景分類中，沙灘場景往往也是室外場景，一篇娛樂新聞報道則不太可能屬于政治新聞.有效地學習和利用這些依賴關系是提高多標簽分類模型性能的關鍵.盡管研究人員已經提出了多種學習和利用標簽間依賴關系的方法，但目前關于標簽之間的依賴關系并沒有明確統一的定義.

在本文中，我們基于神經網絡結構提出了一種探究標簽之間依賴關系的算法，用以提升多標簽分類算法的性能.該神經網絡由單隱層構成，并且可以利用深度學習中的先進技術提升網絡性能.

本文的主要貢獻可歸納為3部分：

1) 在神經網絡頂層加入表示語義標簽類之間的相似性度量矩陣Ω∈L×L，刻畫標簽之間的依賴關系.

2) 基于標簽之間的依賴關系處理標簽缺失問題.

3) 構建3層網絡結構,結構簡單,能夠有效避免復雜網絡結構所引發的梯度不穩定性問題.

1 問題描述

1.1 問題定義

最直觀的想法是對每個標簽類獨立地訓練一個分類器，但是這樣獨立的訓練策略不能夠探索標簽之間的依賴關系.為了打破這樣的限制，本文提出了基于神經網絡探究標簽依賴關系的多標簽分類算法,該算法在輸出層增強了不同語義標簽之間的知識共享.

1.2 相關工作

在多標簽學習問題中，每個實例同時與多個標簽相關聯.已有的算法大體可以分為2類：基于問題轉化的方法和算法適應性方法.

二元關聯(binary relevance, BR)、分類器鏈(classifier chains, CC)是典型的基于問題轉化的方法.由Boutell等人[1]提出的BR算法將多標簽學習問題轉換為多個獨立二分類任務，每個二分類器對測試樣本預測出一個可能的標簽，根據得分函數給出標簽得分,并將其排列，用最大后驗概率(MAP)原理來選擇一個或多個類來作為測試樣本的標簽.BR算法的典型缺點是它假設標簽之間是相互獨立的，忽視了標簽之間的潛在聯系，從而導致算法性能不佳.考慮到標簽之間潛在的相關性,Read等人[2]提出CC算法，該方法同樣將多標簽學習問題轉換為二分類問題，同時認為當前預測的標簽存在與否對下一個標簽的預測存在一定的影響.該算法為每個類別訓練一個分類器，根據標簽的順序構成一個分類器鏈，從第2個分類器開始,后一個分類器都是基于前一個分類器的預測結果構建的.也就是說，在樣本通過第2個分類器時，必須將樣本特征與第1個分類器預測出來的標簽合起來作為樣本新特征通過第2個分類器，以后的分類器按照此方法通過，最終得到樣本的所有標簽.但CC方法存在一個問題，當對之前的標簽預測錯誤時，該錯誤會沿著分類器鏈傳導到鏈末端，導致分類性能下降.為了降低標簽順序對分類效果的影響，Read等人[2]在此基礎上進行一定的改進，加入集成的思想，提出集成分類器鏈(ECC)算法，構建多條分類器鏈，根據多條分類器鏈的結果采用多數投票法最終得到樣本的所有標簽.除了典型的BR和CC算法，Brinker[3]提出的標準標簽排序(calibrated label ranking, CLR)算法將多標簽學習任務轉化為標簽排序任務.Tsoumakas和Vlahavas[4]提出的Randomk-labelsets算法則直接將多標簽學習任務轉化為多類別學習任務.

算法適應性方法采用學習技術來處理多標簽問題，是最主要的解決多標簽問題的途徑.Zhang和Zhou[5]提出的ML-kNN算法采用懶惰學習技術，Clare和King[6]提出的ML-DT算法采用決策樹技術，Elisseeff和Weston[7]提出的Rank-SVM算法采用核技術，Ghamrawi和Mccallum[8]提出的CML算法則采用信息論技術.為了應對超高維多標簽學習問題,基于嵌入技術的算法[9-10]和基于樹技術的算法[11-13]大量涌現.然而，大多數的多標簽學習算法[14-21]都集中在探索標簽相關性或依賴信息，以提升分類預測的性能.Jing和Yang等人[14]提出基于半監督映射學習的SLRM算法來探究標簽相關性，對映射矩陣U進行SVD分解，U的左奇異矩陣表示標簽之間的相關性；Li和Zhao等人[15]提出條件受限波爾茲曼機來探究標簽依賴關系，它在標簽輸出層和隱層之間構建受限波爾茲曼機，位于特征輸入層之上，利用波爾茲曼機的固有性質學習標簽依賴關系，將一個無向圖模型轉換為條件概率模型求解.Zhang和Yeung[16]提出刻畫多任務關系的凸優化形式MTRL算法，同時學習映射函數和任務之間的依賴關系矩陣Ω.Ciliberto和Mroueh等人[17]提出基于多任務結構的凸優化學習算法，用以刻畫任務之間的依賴關系，該算法將標簽關系矩陣作為懲罰函數的參數.

標準的多標簽分類算法都假設訓練數據是標簽完備的.這種假設在許多現實應用中不成立，由于標簽的收集非常困難，因此標簽不完備的數據普遍存在.為了處理標簽缺失問題涌現出了大量的算法[14,22-26].Lin和Singh等人[22]提出基于后驗概率正則化的PRLR算法，分別從構造映射矩陣Q和計算后驗概率P來預測標簽，同時使KL散度盡可能的小.Jing和Yang等人[14]提出的基于半監督映射學習的SLRM算法能夠基于數據獲得固有的數據結構，從而可以解決標簽缺失問題.Yu和Jain等人[26]提出一個通用的經驗風險最小化框架來處理大規模多標簽分類任務，但是僅在標簽完備的數據上訓練模型來應對標簽缺失問題，沒有充分考慮標簽缺失數據在訓練模型中的重要性.

為了進一步提升多標簽分類預測模型的性能，本文提出基于神經網絡探究標簽依賴關系的多標簽分類算法，通過在神經網絡的頂層加入一個標簽依賴關系矩陣來刻畫標簽之間的相關性，同時根據標簽依賴關系還可以解決帶有標簽缺失數據的多標簽分類問題.

2 基于神經網絡的多標簽分類算法

在本節中,主要介紹基于神經網絡探究標簽依賴關系的多標簽分類算法的細節.

2.1 基本模型

基于神經網絡探究標簽依賴關系算法模型如下：

(1)

其中，JCE是交叉熵損失函數，用來評估給定訓練樣本的真實標簽和預測結果之間的誤差;Φ(f)是正則項，用來控制f的復雜性，防止過擬合;λ是正則化參數，用來平衡目標函數中2項在相同的數量級.

2.2 交叉熵損失函數

本文中，使用交叉熵作為損失函數，它被廣泛用于神經網絡分類訓練任務.其表達式為

(2)

其中，on l和yn l分別表示對標簽l的預測結果和真實標簽.

2.3 神經網絡結構

受生物系統的啟發，神經網絡由大量的神經元相互連接而成，用以模仿神經系統中的信息處理過程.通過多層神經元級聯，神經網絡具備強大的非線性抽象能力，并且當給定足夠多的數據時，它能夠學到從輸入空間到輸出空間的任意映射.

本文構建的神經網絡結構包含3層，分別是輸入層、單隱層和輸出層.神經網絡結構如圖1所示.單隱層有F個神經元，輸入單元通過權重W(1)∈F×D和偏置項b(1)∈F×1與隱層單元h∈F×1 連接.隱層單元h∈F×1 通過權重W(2)∈L×F和偏置項b(2)∈L×1 與輸出單元o∈L×1 連接.因此該網絡能夠被寫成矩陣形式.本文構建一個前饋網絡fθ:x→o，作為范圍在[0,1]之間非線性函數的混合：

fθ(x)=fo(W(2)fh(W(1)x+b(1))+b(2)),

(3)

其中θ={W(1),b(1),W(2),b(2)}，fo和fh分別是輸出層和隱層的激活函數，因此函數fθ被重寫如下：

z(1)=W(1)x+b(1),h=fh(z(1)),

(4)

z(2)=W(2)h+b(2),o=fo(z(2)),

(5)

其中，z(1)和z(2)分別表示輸入層激活和隱層激活的權重之和.

Fig. 1 Neural network with a single hidden layer of two units圖1 含有2個隱單元的單隱層神經網絡模型

本文的目標是尋找使得損失函數J(θ;x,y)最小化的參數θ.這個損失函數評價網絡預測的標簽和真實標簽之間的差值.

2.4 標簽依賴關系學習

正如1.2節所討論的，探索標簽之間的依賴關系非常重要，能夠提高模型預測性能.因此，本文提出基于神經網絡探究標簽依賴關系的多標簽分類算法.為了加強標簽之間的知識共享，本文拓展之前的目標函數為

(6)

s.t.ATΩA≥0，tr(Ω)=1，

其中A為任意非零向量.

本文期望在學習預測模型的同時學習標簽之間的相關性，尤其是，該目標函數是凸函數，加入一個跡形式的正則項，其中輸出層的權重W(2)與標簽依賴關系矩陣Ω∈L×L的乘積作為跡范數的參數.約束ATΩA≥0 表明標簽之間的依賴關系是半正定的，因為它可以被理解為語義標簽類之間的相似性度量.系數λ1和λ2是正則化參數，用來平衡不同正則項的貢獻度.

隨著深度學習快速發展，出現大量的技術能夠有效地克服訓練神經網絡的困難，其中，Dropout技術可以避免由大量參數空間導致的過擬合現象，因此得到最終的目標函數為

(7)

其中，A為任意非零向量，λ1是正則化參數，約束tr(Ω)=1 用來防止復雜度過高.

3 優化方法

3.1 優化過程

對于式(7)提出的目標函數，采用最小批梯度下降方法(mini-batch gradient descent, Mini-batch-GD)求解該優化問題，尋找使得損失函數最小化的參數W(1),b(1),W(2),b(2),Ω.

首先考慮當Ω固定時,原優化問題變成下列無約束的優化問題：

(8)

接下來介紹當其他參數固定時，對標簽依賴關系矩陣Ω的更新.公式可以被重寫為

(9)

其中，A為任意非零向量.

根據Cauchy-Schwarz不等式，式(9)的閉式解:

(10)

首先初始化Ω=(1m)Im，表示假設起初所有的標簽之間是相互獨立的.

3.2 AdaGrad的自適應學習率

最小批梯度下降方法(Mini-batch-GD)是簡單但有效的求解目標函數最小化的技術.當采用Mini-batch-GD為優化方法時，一個重要的問題是學習率的選擇.

引，η0表示初始學習率.

在多標簽學習中，常見的情況是很少一部分標簽經常出現，而大部分標簽只是偶爾出現，因此對所有的變量進行梯度更新時采用固定相同的學習率是不合適的.如果使用AdaGrad自適應學習率，對于頻繁出現的標簽更新時學習率會很小，而對罕有出現的標簽更新時學習率會較大，從而可以精確收斂.

4 實驗與結果

4.1 評價標準

為判斷學習算法的性能優劣，首先需要確定評價標準.根據多標簽數據的分類結果可以分為2種類型：1)基于標簽排序，按樣本屬于各標簽的可能性對所有標簽進行排序，并形成一個排序結果；2)基于結果標簽集合，其中每個元素都是分類器對其預測的標簽.

基于標簽排序的評價標準：1)單一錯誤(One-error).統計預測的標簽序列中排在最前面的標簽不是真實標簽樣本的比例,值越小表明分類器的性能越好.2)覆蓋值(Coverage).統計在預測的標簽序列中，從序列的第1個元素出發，為了找出樣本所有的相關標簽需要走的平均步數，值越小表明樣本的真實相關標簽在預測標簽序列中的位置越靠前，分類器的性能越好.3)序偶損失(Rankloss).統計在預測標簽序列中兩兩標簽之間，當前測試樣本的不相關標簽排在相關標簽之前的次數，值越小表明分類器的性能越好.4)平均精確率(average precision).針對樣本的每個相關標簽，平均精確率統計了在樣本的預測標簽序列中排在它前面的相關標簽的個數，然后在所有樣本的所有標簽上求均值，值越大表明分類器的性能越好.

基于結果標簽集合的評價標準：1)召回率(Recall).統計樣本真實標簽集中的被預測到的標簽的比例，值越大表明分類器的性能越好.2)精確率(Precision).統計預測標簽集中為當前樣本真實標簽的標簽比例，值越大表明分類器的性能越好.3)F1測量(F1 measure).平衡了精確率和召回率，值越大分類器的性能越好.4)準確率(Accuracy).統計每個真實標簽集和預測標簽集的交集大小與真實標簽集和預測標簽集的并集大小的比值，并在樣本上求均值，值越大分類器正確分類的程度越大.5)AUC.表示相關標簽排在不相關標簽前面的概率,值越大表明分類器的性能越好.

4.2 數據集

為充分比較和驗證所提出算法NN_AD_Omega的有效性，本文共挑選了4個已經被廣泛采用的多標簽數據集開展實驗.這4個數據集分別為MSRC①,SUN②,Delicious③和CAL500③.MSRC是典型的基于詞包采樣的圖像數據集，而SUN是典型的基于圖像低層特征采樣的數據集.Delicious和CAL500數據集能夠直接從Mulan網站中被下載.

表1給出了這4個數據集的具體描述，其中N表示數據集樣本數量，D表示特征維數，L表示標簽數量，Cardinality定義每個樣本平均標簽個數.在這4個數據集中，標簽數量的范圍是23～983，每個樣本平均標簽個數的范圍是2.508～26.044，因此對這些數據集進行標簽預測是具有挑戰性的任務.

Table 1 Multi-Label Dataset Summary表1 多標簽數據集描述

4.3 對比算法和參數設置

為了充分驗證NN_AD_Omega算法的性能,本文選擇NN_AD[27],CRBM[15],C2AE[21]這3種典型算法作為比較對象.這3種算法代碼均在Matlab中被實現,運行在4 GB內存搭配2 GHz CPU的Windows系統中.

NN_AD算法基于神經網絡結構解決多標簽分類問題,采用AdaGrad技術和Dropout 技術保證快速收斂.CRBM算法基于條件玻爾茲曼機模型探究高階標簽之間依賴關系解決多標簽分類問題，同時解決標簽缺失問題.C2AE算法基于自編碼器模型探究標簽依賴關系解決多標簽分類問題.相關參數的具體設置取自原論文[27].

NN_AD_Omega算法基于單隱層神經網絡，隱層的神經元個數為1 000，隱層的激活函數為Relus，輸出層的激活函數為Sigmoid，學習率η0初始范圍為{0.001,0.01,0.1}.為了模擬標簽缺失情況,針對每個數據集隨機選擇一個訓練集的標簽缺失率σ,σ∈{0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9}.

4.4 算法收斂性

為了研究算法的收斂性,在2個數據集上得到目標函數的值,如圖2所示.隨著迭代次數的增加,目標函數的值會不斷地減小,并且在迭代一定次數之后目標函數的值會趨于穩定.

Fig. 2 Convergence of NN_AD_Omega on SUN and Delicious圖2 NN_AD_Omega算法在SUN和Delicious數據集上的收斂性

4.5 對比算法的性能表現

為了充分驗證NN_AD_Omega算法與對比算法的性能，本文在選定的4個數據集上進行大量的實驗，表2給出結果的平均值，每個評價指標的最優值用粗體標明.

根據表2中的結果,我們可以得出4個結論：

Table 2 Comparison of Multi-Label Learning Performance Output by Four Algorithms on Four Datasets表2 4種算法在4個數據集上的性能表現

Continued (Table 2)

Notes:“↑” means the larger the value, the better the performance; “↓” means the smaller the value, the better the performance.

1) NN_AD_Omega算法優于僅僅基于神經網絡結構的NN_AD算法,表明探究標簽之間的依賴關系對于多標簽學習任務是至關重要的.

2) NN_AD_Omega算法優于基于條件玻爾茲曼機的CRBM算法,表明在神經網絡頂層加入Ω矩陣來刻畫標簽之間的依賴關系比基于玻爾茲曼機自身屬性來構建標簽之間依賴關系更為有效.

3) NN_AD_Omega算法優于基于自編碼器的C2AE算法,表明構建矩陣Ω∈L×L具有豐富的標簽依賴信息,基于自編碼器構建標簽依賴關系會丟失部分的標簽依賴信息.

4) 為了驗證NN_AD_Omega算法學到的標簽之間的依賴關系矩陣Ω,表3給出了MSRC數據集與每個標簽最相近的2個標簽.正如所期望的,算法預測的標簽確實與給定的標簽語義相關.

Table 3 Label Correlation Identified by NN_AD_Omega on MRSC Data表3 NN_AD_Omega算法從MRSC數據集得到的標簽依賴關系

4.6 標簽缺失的性能表現

為了進一步研究NN_AD_Omega算法在標簽缺失情形下的性能表現，本文在CAL500數據集上進行實驗.對于數據集中的每個實例,通過變化缺失標簽的比例來模擬標簽缺失情形,缺失的標簽包括正標簽和負標簽.為了避免出現空標簽類和一個實例僅含有負標簽的情況,處理數據時必須保證每個標簽類至少有一個實例,每個實例至少有一個正標簽.因此,yi j=0表示第i個實例的第j個標簽缺失,yi j=1表示第i個實例包含第j個標簽,而yi j=-1表示第i個實例不包含第j個標簽.實驗中,選取不同的σ值進行缺失模擬，所有的性能指標是多次實驗的平均值，前3種算法的性能對比，如圖3所示:

Fig. 3 Comparison results of three algorithms under varying the ratio of missing entries on CAL500圖3 3種算法在CAL500數據集上標簽缺失情形下的性能表現

通過圖3可以看出，隨著標簽缺失率的增大，這3種算法的性能會逐漸降低，表明標簽信息的缺失會降低多標簽分類的性能.從總體上來看，NN_AD_Omega算法要優于NN_AD和CRBM，表明NN_AD_Omega算法相較于NN_AD和CRBM學到了更有效的標簽依賴關系.因此，NN_AD_Omega 算法能夠有效地處理標簽缺失問題.

5 結論與展望

為了解決多標簽分類任務,本文提出了一種新模型NN_AD_Omega,該模型能夠有效學習從特征空間到標簽空間的映射.通過在神經網絡頂層加入Ω矩陣,NN_AD_Omega模型能夠有效地探究標簽之間的依賴關系.同時,NN_AD_Omega模型也能夠充分地利用標簽之間的依賴關系處理標簽缺失問題.為了快速高效地優化該模型,本文采用最小批梯度下降方法(Mini-batch-GD)求解.大量的實驗表明,NN_AD_Omega算法性能優于當前已有的先進算法,并且表明NN_AD_Omega算法能夠有效地處理多標簽分類問題.

在進一步的研究工作中,我們將致力于研究刻畫標簽之間依賴關系的形式,進一步提升算法性能,以期通過不同的標簽依賴關系形式高效、準確地預測標簽信息.

SongPan, born in 1994. Master candidate. Her main research interests include machine learning, multi-label learning.

JingLiping, born in 1978. PhD, professor. Member of CCF. Her main research interests include machine learning and high-dimensional data mining.