圖趨勢過濾誘導的噪聲容錯多標記學習模型

林騰濤，查思明，陳 蕾，2*，龍顯忠

（1.南京郵電大學計算機學院、軟件學院、網絡安全學院，南京 210003；2.江蘇省大數據安全與智能處理重點實驗室（南京郵電大學），南京 210003）

0 引言

在現實生活中，一個示例通常與多個標記相關聯，例如，一篇文檔可能與多個不同主題相關，一幅圖片通常包含多個物體，一段音樂可能有多個體裁。因此，多標記學習受到了廣泛的關注，并在文本分類、圖像標注、圖像分割、動作識別、面部表情識別、生物信息學等各個領域都取得了成功應用。

多標記學習旨在從一系列候選標記集中選出與樣本相關的標記，由于標記集有著大量的標記并且多個標記在某個語義空間里通常是相互關聯的，因此，探索標記之間的關聯關系有助于多標記學習。例如，在圖像標注中，如果標記“駱駝”和“仙人掌”同時出現，那么有極大可能性會出現“沙漠”這個標記，而出現“蝴蝶”這一標記的可能性就極低。多標記學習試圖將不同程度的標記相關性結合起來，已有許多相關算法被提出來探索標記之間的關聯關系。其中，標記排序方法通過考慮兩兩標記之間的關系從而將多標記分類問題轉化為標記排序問題［1-2］。進一步地，為了探索標記之間的高階關聯關系，即一個標記與其他所有標記之間的關聯關系，最典型的方法是將原始標記向量投影到一個低維的標記空間中［3］，文獻［4］同時考慮了全局和局部的標記關聯關系，文獻［5］將原始離散的二值標記空間擴展成歐氏空間，并同時考慮了特征流形和標記流形結構。

然而在許多實際應用中，獲得的數據往往是不完美的，往往同時包含特征噪聲和標記噪聲，忽略任意一種噪聲都將影響多標記學習模型的預測性能，而現有的多標記模型大多只考慮其中一種噪聲。一方面，標記可能會有缺失或者錯誤，針對標記噪聲，通過標記之間的關聯關系可以很好地解決標記缺失［6］，文獻［7-8］利用直推式半監督學習方法補全缺失標記，文獻［9］試圖解決基于標記缺失的大規模多標記學習問題。另一方面，特征也可能存在噪聲，例如圖片模糊等，針對特征噪聲，文獻［10-11］提出許多方法解決特征噪聲。盡管文獻［12］解決了特征噪聲和標記噪聲同時出現的情況，但是基于L2范數誘導的圖拉普拉斯正則化在含噪的數據集中可能并不準確，忽略了含噪特征向量與標記向量的不一致性，即噪聲容錯性不足。

為了解決上述問題，本文提出了一種圖趨勢過濾誘導的噪聲容錯多標記學習（Graph trend filtering guided Noise Tolerant Multi-label Learning，GNTML）模型。該模型通過采用組稀疏約束橋接標記增強矩陣的機制來同時容忍特征噪聲和標記噪聲。具體地，本模型通過探索標記之間的內在關聯關系學習得到一個標記增強矩陣，用增強過后的標記矩陣替代原始標記矩陣，以解決可能存在的標記缺失，這個標記增強矩陣理想情況下是根據特征矩陣獲得的，進一步，為了在混合噪聲場景下學習到合理的標記增強矩陣，本文一方面引入圖趨勢過濾（Graph Trend Filtering，GTF）［13］機制來容忍含噪示例特征與標記之間關聯的不一致性，即某些示例由于存在噪聲特征相似，但實際上它們的標記卻是不相近的。另一方面，本文引入組稀疏約束的標記保真懲罰來減輕標記噪聲對標記增強矩陣學習的影響，以及組稀疏約束同時解決特征噪聲。此外，本文還通過引入標記關聯矩陣的稀疏約束來刻畫標記之間的局部關聯特性，使得樣本標記能夠在相似樣本之間得以更好的傳播。本文利用交替方向法（Alternating Direction Method，ADM）來有效地求解模型，并在7 個真實多標記數據集上的實驗表明，本文提出的噪聲容錯多標記學習模型在66.67%的情況下取得最優值或次優值，能有效地提高多標記學習的魯棒性。

1 相關工作

基于標記之間的關聯程度，多標記學習問題求解策略通常可以被劃分為三種［14］：最簡單的一種是“一階”策略，該策略逐一考察單個標記而忽略標記之間的關聯關系，最典型的算法就是BR（Binary Relevance）［15］，將多標記問題轉化為多個二分類問題，為每一個標記都訓練一個分類器；相應地，“二階”策略考察兩兩標記之間的相關性，從而構造多標記學習系統，例如校準標記排序（Calibrated Label Ranking，CLR）［2］，將多標記問題轉化問為兩兩標記之間的排序問題，然而當實際問題中標記具有超越二階的相關性時，該策略會受到影響。“高階”策略則考察了高階的標記相關性，考慮了所有標記之間的關聯關系，例如CC（Classifier Chain）［16］，將多標記問題轉化為鏈式的二元分類問題，雖然“高階”策略可以較好反映真實世界問題的標記相關性，但通常模型復雜度較高，計算代價太大。文獻［5］則把標注信息標記當作訓練樣本示例的豐富語義化編碼的簡化。

然而，獲得的數據集通常并不是完美的，往往含有各種噪聲，因此，含噪多標記學習取得了很大關注。通常噪聲包含兩方面：特征噪聲和標記噪聲。針對標記噪聲，由于多標記學習有著大量類標記，在某些實際應用中可能只能觀察到部分標記，且多標記學習性能受不完整標記影響很大，對此提出了許多減少性能衰退的方法。例如：文獻［17］提出了一種基于正則化的歸納式半監督多標記學習方法；文獻［18］通過考慮標記關聯來恢復完整的標記矩陣；文獻［19］首先選出關鍵標記，再根據標記進行排序，然后利用組稀疏，最后采用支持向量機（Support Vector Machine，SVM），從而處理標記缺失；文獻［20］是基于矩陣補全的多視圖弱監督學習來解決標記噪聲；文獻［4］通過建模全局和局部標記關聯性，學習潛在標記表示并優化標記流形來解決標記缺失。針對特征噪聲，文獻［21］通過降維，文獻［22］通過特征選擇來解決特征噪聲。文獻［12］同時解決了特征噪聲和標記噪聲。

2 模型框架

2.1 預備知識

其中L(·，·)和R(·)分別表示損失函數和關于W的正則化項。W根據不同的前提假設設計不同的正則化項。

2.2 圖趨勢過濾誘導的噪聲容錯多標記學習模型

本文所提出的圖趨勢過濾誘導的噪聲容錯多標記學習模型GNTML 是針對特征噪聲和標記噪聲共同出現的場景。具體來說，首先在含有噪聲的訓練集中探索不同標記之間的關聯關系，以此獲得一個新的標記增強矩陣，這個增強的標記矩陣理想情況下是根據特征矩陣獲得的。但是由于數據集是含有噪聲的，因此借助圖趨勢過濾的噪聲容錯能力來容忍含噪示例特征與標記之間關聯的不一致性，從而減輕特征噪聲對標記增強矩陣的影響。接著用這個標記增強矩陣代替原始標記矩陣，引入組稀疏同時解決特征噪聲和標記噪聲，從而學習從特征空間到增強標記空間的映射，所提模型整體框架如圖1所示。

為了得到這個標記增強矩陣，該模型在含噪的訓練集中學習得到一個標記關聯矩陣B∈Rc×c，其中bij表示標記yi與標記yj的關聯程度，基于新的標記增強矩陣，學習得到的預測模型W由于考慮到特征和標記的關聯關系將變得更加合理。目標函數如下：

其中R(B)表示關于B的正則化項。可以觀察到，通過自適應學習得到的投影矩陣B可以捕獲所有c個不同標記之間的關聯關系，例如，大多數樣本同時出現“藍天”和“白云”兩個標記，那么這兩個標記是強關聯的，則在投影矩陣B中可以體現，并且這是個一對多的高階依賴關系BY，而不是一對一的依賴關系。這樣一來，就可以通過其他標記之間的關聯關系來重構任何丟失的標記，矩陣就是標記增強矩陣。此外，獲得的標記增強矩陣應該與原始標記矩陣保持一致性，因此本文定義了一個標記保真懲罰項來刻畫原始標記矩陣與標記增強矩陣之間的差異。考慮到標記噪聲的存在，同時施加了組稀疏約束，標記保真懲罰項定義如下：

其中，關于一個A∈Rp×q矩陣的L2，1范數定義為‖A‖2，1=

回憶一下，該模型目的是在特征噪聲和標記噪聲共現時學習標記增強矩陣，由于GTF 是一種對圖進行非參數回歸的統計方法，通過L0懲罰圖頂點之間標記差取代通常用的L2范數的圖拉普拉斯平滑假設，有著很強大的噪聲容錯能力和局部自適應性。因此本文引入GTF來更好誘導標記增強矩陣的學習。首先基于訓練樣本構建一個鄰接矩陣S，sij刻畫了示例i和示例j的特征相似度，如果示例j屬于示例i的k個最近鄰樣本集，則它們的相似度通過如下高斯核函數計算，否則sij=0：

其中δ表示高斯核寬度。接著用鄰接矩陣S來構造一個圖G(V，E)，V={xi|1 ≤i≤n}表示訓練樣本組成的頂點集合，E={(xi，xj)|sij≠0，1 ≤i≠j≤n}表示邊的集合，如果sij非0，則表示示例i與示例j有邊相連。

此外，本文又定義一個n×e的矩陣P，其中e表示圖G中邊的條數，若第k條邊連接xi和xj，則矩陣P的第k列定義如下：

值得注意的是，考慮到部分標記之間可能沒有關聯關系，因此這里給B施加一個L1范數約束，學習得到一個稀疏的標記關聯矩陣。同時通過組稀疏‖BY-WX‖2，1處理有損壞的特征，如圖1 中的圖片c，利用組稀疏使得對特征噪聲更加魯棒。

圖1 模型框架Fig.1 Model framework

本文所提模型有如下優勢：1）利用標記增強矩陣BY代替原始標記矩陣Y以解決標記的缺失；2）本文通過組稀疏同時處理特征噪聲和標記噪聲；3）在GTF 的誘導下探索了數據的局部特性，即特征相似的樣本標記也相近，保留了原始特征空間的局部幾何結構，并過濾掉那些由于特征噪聲存在使得特征相似但實際上標記卻不相近的樣本。

3 優化求解

因為式（6）是凸的，因此解決的方法有很多，本文采用交替方向法（Alternating Direction Method，ADM）求解，但是由于L1范數項是非平滑的，因此為了求解方便，引入輔助變量C，令B=C，從而式（6）等價變為：

對應的增廣拉格朗日函數如下：

由于上述問題是無約束的，因此可以通過固定其他變量來分別優化B、W和C，然后更新乘子Γ，其中μ＞0 是懲罰系數。

固定W和C，更新B：

當固定W和C，關于B優化問題變為：

可以寫成如下關于B的函數形式：

固定B和C，更新W：

當固定B和C，關于W的函數變為：

令上述關于W的函數導數為0，可得

固定B和W，更新C：

當固定B和W，關于C優化問題變為：

其中：⊙表示哈達瑪積，sgn(·)表示signum函數。

更新乘子Γ：

算法1給出了該優化算法框架的偽代碼。

算法1 所提出的GNTML模型的優化算法。

輸入：訓練樣本特征矩陣X∈Rd×n，標記矩陣Y∈Rc×n，以及超參數λ1，λ2，λ3，λ4；

輸出：線性分類器W，標記關聯矩陣B。

4 實驗

4.1 數據集和評價指標

為了證明所提方法的有效性，本文在7 個標準多標記數據集上進行了實驗：Birds、Emotion、CAL500、Scene、Corel5k、Medical、Genbase。這些數據集均來自Mulan 網站（http：//mulan.sourceforge.net/datasets-mlc.html）。數據集的詳細信息如表1 所示，注意這里的LCard（label cardinality）是一種多標記標記密度的量，是用來指示在數據集中每一個樣本平均有多少個標記。

表1 多標記數據集的特征Tab.1 Characteristics of multi-label datasets

與文獻［23］的工作類似，本文采取了5 種常見的評價指標。給定一個多標記測試集，其中Yi為隸屬于示例xi的相關標記集合，以及h(xi)表示示例i的預測標記集合，f(xi，y)對應xi具有標記y的“置信度”。此外，實值函數f(·，·)還可以轉化為一個排序函數

Hamming Loss（HL） 用于考察樣本在單個標記上的誤分類情況，例如一個相關標記未出現在預測的標記集合中或者無關標記出現在預測的標記集合中。

其中Δ用于度量兩個集合之間的“對稱差”。

Ranking Loss（RL） 用于考察在樣本的類別標記排序序列中出現排序錯誤的情況，即不相關標記在排序序列中位于相關標記之前。

One Error（OE） 用于考察在樣本的類別標記排序序列中，序列最前端的標記不在相關標記集合中的比例。

Coverage（Cov） 用于考察在樣本的類別標記排序序列中，覆蓋所有相關標記所需的搜索深度情況。

Average Precision（AP） 用于考察樣本的類別排序序列中，排在相關標記之前仍為相關標記的情況。

上述這些評價指標常用于多標記學習中，并且可以從不同角度評估多標記算法的性能。對于Average Precision，值越大，分類器的性能越好，對于其他值，值越小分類器的性能越好。

4.2 實驗設置

本文將所提模型同幾個相關的算法進行比較，包括文獻［15］提出的BR（Binary Relevance），BR 將多標記學習問題轉化為多個“二分類”問題求解；文獻［23］提出的基于k近鄰（k-Nearest Neighbor，kNN）的多標記學習算法ML-kNN（Multilabel Learning-k-Nearest Neighbor），ML-kNN 將“惰性學習”算法k近鄰進行改造以適應多標記學習；文獻［2］提出的校準標記排序（Calibrate Label Ranking，CLR），CLR 通過“成對比較”將多標記學習轉化為標記排序問題，并且對噪聲也具有魯棒性；文獻［16］提出的ECC（Ensemble of Classifier Chains），ECC是基于CC（Classifier Chains）鏈式的集成多標記集成鏈式算法；以及文獻［10］提出的混合噪聲多標記學習（Hybrid Noise Oriented Multi-label Learning，HNOML）模型，HNOML 同時考慮了特征噪聲和標記噪聲并基于L2范數的圖拉普拉斯矩陣考慮標記關聯關系。

對于本文模型GNTML 的超參數λ1、λ2、λ3、λ4，本文從集合｛10-4，10-3，…，102｝通過網格搜索策略確定每個參數的最值，對于k值設定為5，因為它的變化對模型性能影響不大。對于其余算法盡最大努力調參以達到最好效果。

4.3 實驗結果

本文實驗中隨機從數據集中選出2/3 作為訓練集，剩下1/3 作為測試集，由于實驗存在隨機性，本文實驗重復運行30次，求得最后的平均值和標準差。本文所提模型與其他對比模型的實驗結果如表2 所示，由于每個數據集都是隨機劃分的，因此表中每個評價指標給出最后結果的平均值和標準差，并將最優值標記為粗體，次優值標記為下劃線，最后一行統計了各個算法分別取得最優值和次優值的次數。從表中可以觀察到，本文提出的模型GNTML 在7 個真實數據集的5 個評價指標上，66.7%（28/42）情況下取得最優值或次優值，其中38.1%（16/42）的情況下取得最優值，28.6%（12/42）的情況下取得次優值，相比于其他算法有一定的優勢。作為多標記學習的經典基本算法BR，由于沒有考慮標記之間的關聯關系，所以它的結果是很一般的，最優值情況為0%，次優值僅占11.9%。ECC 算法通過集成學習結合基方法，由于要將上一個預測的標記結果輸入到下一個預測數據集中，所以考慮到了標記關聯，因此性能要比BR 有了很大的提升，在19.0%情況取得最優值，21.4%取得次優值。ML-kNN 算法雖然在Scene數據集上能表現出優異性能，但是在其他數據集上表現卻是一般，因此不是很穩定。HONML 模型算法也稍弱于GNTML。

進一步地，為了驗證所提出的模型在特征噪聲和標記噪聲共現時的魯棒性，本文在Emotion數據集上進行了噪聲魯棒性實驗。本文同時給訓練樣本的特征矩陣和標記矩陣人工添加噪聲來模擬特征噪聲和標記噪聲共現的場景。具體地，對于特征矩陣，本文選取了0%～20%的樣本添加特征噪聲，每個選中的樣本將其50%的特征值數值置為0，對于標記矩陣；本文同樣選取了0%～20%樣本添加標記噪聲，每個選中的樣本將其50%的標記值從正例變為負例，負例變為正例。

實驗結果如圖2 所示，從圖2 中可以觀察到，在數據集Emotion上，ML-kNN算法在不添加噪聲時性能優于其他算法，但是隨著添加噪聲比例的增加，性能有所下降，HNOML 算法是基于L2范數的圖拉普拉斯平滑假設，并且能處理混合噪聲，表現也比較穩定，本文的方法用圖趨勢過濾代替基于L2范數的平滑假設，性能優于HNOML，也因此證明了本文模型中圖趨勢過濾項的有效性。

圖2 在數據集Emotion上不同噪聲比例下的魯棒性實驗Fig.2 Robustness experiments with different noise ratios on Emotion dataset

4.4 收斂性

本文提出的模型GNTML通過交替方向迭代優化求解，圖3是數據集Birds和CAL500上的收斂情況，可以看出隨著迭代次數的增大，模型的收斂速度很快，并且通常不超過10 次就能穩定。

圖3 本文算法在數據集Birds和CAL500上的收斂性實驗Fig.3 Convergence experiments of the proposed algorithm on Birds and CAL500 datasets

5 結語

考慮到訓練樣本可能同時存在特征噪聲和標記噪聲，本文提出了一個圖趨勢過濾誘導的噪聲容錯多標記學習模型，這個模型通過挖掘標記之間的關聯關系，增強原始標記空間，并結合組稀疏來同時處理特征噪聲和標記噪聲。本文采用圖趨勢過濾不僅保留了數據的局部特性，也可以容忍含噪示例特征與標記之間關聯的不一致性，從而減輕特征噪聲對標記增強矩陣學習的影響。在多個真實數據集上的實驗也證明了所提模型的有效性。在后續工作中，計劃將本文的模型推廣到多視圖情形，通過探索示例的多視圖特征來進一步減輕特征噪聲對多標記學習性能的影響。