基于實例結構的不完備多標簽學習

陳天柱，李鳳華，郭云川，李子孚

（1.中國科學院信息工程研究所，北京 100093；2.中國科學院大學網絡空間安全學院，北京 100049；3.中國電子科技集團公司信息科學研究院，北京 100086）

1 引言

物聯(lián)網中實體、資源和服務常用唯一標識來識別，每個標識可能包含多個具有語義信息的標簽。由于物聯(lián)網中資源的海量性，采用人工方式標注資源的語義面臨巨大挑戰(zhàn)。為了自動標注語義，學術界和工業(yè)界提出了多標簽學習技術。然而，在一些應用場景中，訓練集數據由網絡志愿者標記而獲得，其通常呈現標簽缺失的現象[1]。

現有標簽缺失下的多標簽學習方法主要利用標簽關聯(lián)來填充缺失標簽。這些方法大體可分為顯式標簽關聯(lián)法和隱式標簽關聯(lián)法。其中，顯式標簽關聯(lián)法的核心思想是利用標簽向量直接計算標簽關聯(lián)，并約束預測標簽也具有該關聯(lián)。例如，Wu等[2]利用標簽向量計算了標簽相似度，并約束語義相似標簽的預測向量也相似。Li 等[3]從維基百科等輔助源中抽取標簽知識創(chuàng)建標簽關聯(lián)矩陣。Wu等[4]通過實例特征向量和標簽向量直接構建無向標簽關聯(lián)圖，在此基礎上融合標簽語義層次結構（例如，動物標簽是馬標簽的父節(jié)點）創(chuàng)建了標簽關聯(lián)混合圖。然而，上述方法僅利用標簽間的直接關聯(lián)，忽略了非直接關聯(lián)，這使這些方法的預測表現通常較差。

隱式標簽關聯(lián)法基于低秩假設，利用隨機投影、典型相關分析、線性變化等方法壓縮高維標簽為低維空間。隨后在低維空間中預測標簽并將預測標簽翻轉到原標簽空間而獲得預測標簽。其中，隱式標簽關聯(lián)嵌入標簽壓縮中。例如，Zhang 等[5]利用典型相關分析技術挖掘壓縮標簽與預測標簽間的線性關聯(lián)，從而將標簽關聯(lián)蘊含于多標簽學習中。Yu 等[6]在特征矩陣低秩假設下，基于矩陣低秩分解技術俘獲了擬合矩陣低秩結構。然而，上述方法并未有效解決標簽缺失下相似度準確度量問題，也未結合顯式關聯(lián)與隱式關聯(lián)來解決標簽缺失下的多標簽標記問題。此外，在標簽完備情況下，標簽排序[7-8]也是提升模型預測精度的重要方法。然而，現有工作很少從標簽排序的角度來解決標簽缺失下的多標簽標記問題。

針對上述不足，本文從實例的特征和標簽結構出發(fā)，利用標簽矩陣低秩結構和數據標簽流型結構來補全缺失標簽，利用加權排序損失體現標簽對數據的相關程度并降低正關系學為負關系所帶來的模型偏差程度。具體地，通過確保數據預測標簽幾何相似度與數據標簽幾何相似度的一致性來俘獲數據流型結構；通過度量完備標簽下和不完備標簽下的排序損失來區(qū)分正負標簽對實例的相關程度。實驗結果表明本文方案優(yōu)于典型的標簽缺失下的多標簽學習方案。本文的貢獻如下。

1) 本文設計了新的流型結構，該結構降低了對標簽缺失率的依賴。具體地，本文假設實例正標簽是準確標記的，利用k-means 聚類方法對每個標簽所有正實例的特征向量進行聚類，并利用類中心的最小主角計算標簽相似度。同時，本文通過度量完備標簽下和非完備標簽下的排序損失，提出了新的排序正則化方法。

2) 為高效優(yōu)化目標函數，本文松弛目標函數精確解為非精確解，提出了線性ADMM（LADMM,linear alternating direction method of multipliers）。通過線性近似迭代獲得子問題的近似解，該近似解可確保線性ADMM 的收斂性。

3) 在6 個數據集上的實驗結果表明，本文方案優(yōu)于代表性的標簽缺失下的多標簽學習方案。在一些評估標準下，本文方案的精度比最好的對比方案提升了10%以上。

2 相關工作

標簽關聯(lián)法是處理標簽缺失情況下多標簽標記問題的一般方法，其可分為顯式方法和隱式方法。在顯式方法中，Li 等[3]提出包含特征輸入層、標簽輸出層和潛標簽輸出層的三層玻爾茲曼機，并利用潛輸出層學習高階標簽關聯(lián)，同時利用標簽先驗知識來俘獲標簽關聯(lián)，利用其正則化模型。Wu等[4]以標簽為節(jié)點，以標簽一致性和實例相似度構建節(jié)點無向邊，以標簽語義層次構建節(jié)點有向邊，創(chuàng)建標簽關聯(lián)混合圖。其中，標簽語義層次是指某一標簽的語義信息包含了另一標簽的語義信息，如植物標簽和玫瑰標簽。Zhu 等[9]利用標簽在數據集上的分布計算標簽相似度，并確保相似度高的標簽的標簽預測分布距離小，相似度低的標簽的標簽預測分布距離大。具體地，將訓練集聚類成子集，在子集和數據集中分別俘獲局部和全局標簽結構。Huang 等[10]從缺失訓練數據中訓練高階標簽關聯(lián)，對每個標簽學習與其最相關的特征而獲得數據的低維表示。該方案同時學習標簽關聯(lián)與低維表示。然而，上述方法將缺失標簽看作負標簽來計算標簽關聯(lián)，造成標簽直接關聯(lián)度量錯誤，該錯誤隨著標簽缺失率的變大而越來越不準確。同時，這些方法也忽略了標簽非直接關聯(lián)。

針對以上不足，研究者提出隱式方法來提升模型預測精度，其大體分為基于標簽矩陣方法和基于擬合矩陣方法?；跇撕灳仃嚪椒ǖ暮诵乃枷胧抢玫湫拖嚓P分析和線性變化等技術壓縮高維標簽空間為低維空間，隨后在低維空間中預測標簽并將其翻轉到原標簽空間。例如，Tai 等[11]對標簽矩陣做奇異值分解，利用奇異值向量矩陣（低維正交矩陣）做投影矩陣，利用其轉置矩陣做解碼矩陣（正交矩陣的逆矩陣是其轉置矩陣）。Zhang 等[5]利用2 個線性變換分別壓縮標簽和預測標簽，通過典型相關分析尋找壓縮標簽空間最優(yōu)預測方向來俘獲標簽關聯(lián)。隨后，在文獻[5]方案的框架下，Zhang 等[12]保持標簽距離結構與嵌入標簽距離結構一致性，并最大化數據預測標簽與其他數據預測標簽的邊界距離，提出了嵌入標簽可區(qū)分性和可預測性的多標簽學習方案。然而，隨著標簽規(guī)模的變大，確保整體數據距離結構的方案[12]需要極大的計算開銷。針對該不足，Jin 等[13]僅約束實例預測標簽與其嵌入標簽距離小于實例預測標簽與其近鄰數據嵌入標簽距離。

在基于擬合矩陣的方法中，Yu[6]等分解擬合矩陣為2 個低維矩陣，利用一個矩陣壓縮特征空間為低維空間，另一個矩陣擬合壓縮后的特征從而獲得標簽預測。此外，Jing 等[14]為俘獲有效標簽個數，約束擬合矩陣核范數從而實現擬合矩陣低秩結構，同時引入流型結構來確保特征相似度高的數據的預測標簽相似度也高。Li 等[1]利用與標簽個數等維的標簽關聯(lián)方陣來映射實例標簽向量，從而恢復缺失標簽，并利用一個具有低秩結構的去噪聲編碼器來學習標簽關聯(lián)方陣。Zhu 等[9]分解標簽矩陣為2 個低維矩陣的和，利用一個矩陣表示標簽的潛標簽空間，另一個矩陣表示原始標簽投影到潛標簽空間的投影矩陣。然而，上述方法未結合標簽顯式關聯(lián)和隱式關聯(lián)來解決標簽缺失下的標簽標記問題。Li等[15]對標簽矩陣做低秩分解來補全缺失標簽，并利用希爾伯特?施密特獨立性準則來俘獲標簽空間和特征空間的關聯(lián)，從而提升模型預測精度。此外，Gupta 等[16]將訓練集聚成多個子類，基于單詞嵌入方法的思想，分別將每個子類的數據實例和其最近鄰實例映射為主題模型中的單詞和上下文，利用Skip Gram Negative Sampling 將每個實例的特征向量和標簽向量嵌入低維特征空間和標簽空間上。進一步地，Liu 等[17]利用平滑剪裁的絕對偏差和最小最大凹懲罰兩類非凸函數來消除子類數據預測時的模型偏差。

實例正標簽比其負標簽更能體現實例語義信息，約束模型正標簽輸出值大于負標簽輸出值可正則化模型?；诖擞^察，研究者針對標簽完備情況，利用線性模型、支持向量機、神經網絡提出了各種標簽排序方案。Usunier 等[18]基于有序加權平均函數和鉸鏈函數提出了有序加權排序損失函數。Weston 等[7]利用鉸鏈函數來近似0-1 排序損失，提出了函數性質為光滑的加權損失函數。然而，上述方案利用傳統(tǒng)的數據特征作為模型輸入，導致預測精度較低。Gong 等[8]訓練了包含幾個卷積層和dense 連接層的神經網絡結構，以近似處理后的加權損失函數為基礎構造top-k 排序損失，提出了基于深度卷積排序的圖像多標簽標記方法。Durand 等[19]以4 096 維的深度圖像特征為模型輸入，利用2 個潛變量分別預測標簽的正向證據和負向證據。標簽排序已廣泛用于多媒體數據標記、語音標記中，并獲得了較大成功，然而標簽排序很少用于解決標簽缺失下的多標簽學習問題。

3 模型描述

3.1 模型動機

模型流型正則和標簽排序正則步驟如圖1 所示。本文研究動機基于如下3 個事實。1) 在較小規(guī)模和中規(guī)模標簽的數據集中，標簽矩陣和特征矩陣通常呈現一定的低秩結構。通過學習標簽矩陣和特征矩陣的低秩結構來俘獲標簽內在關聯(lián)，并利用該標簽關聯(lián)補充缺失標簽。2) 對于2 個在特征向量上相似度越高的實例，其標簽向量也越相似；對于2 個在特征向量上相似度不高的實例，其標簽向量也不相似。利用實例準確的特征信息來度量實例相似度，并利用該相似度約束預測標簽的相似度以實現缺失標簽補全。3) 實例的正標簽比負標簽更能描述實例的語義信息，因此在模型訓練過程中確保正標簽的輸出值大于負標簽的輸出值具有較大意義。綜上所述，本文從低秩結構出發(fā)俘獲了標簽間的隱式關聯(lián)；利用數據流型結構確保數據特征間距離與標簽間距離的一致性，進而俘獲了標簽顯式關聯(lián)；利用標簽加權排序區(qū)分了正負標簽對數據的描述能力，俘獲了每個實例的標簽顯式關系。

圖1 模型流型正則和標簽排序正則步驟

3.2 標簽標記流程

本節(jié)簡略介紹標簽標記過程，其可粗略分為4 個子過程：訓練集處理、模型建模、模型訓練和標簽標記，如圖2 所示。訓練集處理過程中，首先，專業(yè)人員根據現實需求和數據語義信息挑選標簽并制定標簽字典。然后，標簽標記者從標簽字典中挑選合適的標簽來標記收集的數據，從而形成訓練集。由于標記者工作疏忽，訓練集中的數據可能呈現標簽缺失、標簽冗余和標簽噪聲現象。最后，專業(yè)人員對訓練集數據做特征處理，將數據轉化為可度量形式。例如，依據圖像數據的紋理、色彩和像素信息將數據轉化為特征向量表示。模型建模過程根據訓練集特點，選取線性模型、隨機森林模型和深度學習模型來預測數據標簽，并根據標簽關聯(lián)關系、流型結構和L2 范數等對模型進行正則化。模型訓練過程根據目標函數的特點，挑選恰當的優(yōu)化方法來最小化目標函數。典型的優(yōu)化方法包括梯度下降法、線性搜索法、牛頓法和翻轉牛頓法等。標簽標記過程將檢測數據的向量表示傳遞給預測模型獲得數據標簽預測。本文標簽標記過程不涉及訓練集處理步驟。

圖2 標簽標記流程

3.3 擬合矩陣的低秩結構

其中，k0用于約束擬合矩陣的秩，約束條件rank(M)

其中，參數k1與k0一一對應。

3.4 流型正則

機器學習的核心目標是設計一個在訓練集和檢測集上都具有較好效果的算法。研究者們設計了一些正則化方法[21]來減少測試誤差（可能以增大訓練誤差為代價）。正則化方法大體分為兩類：控制模型復雜度、控制實例的幾何結構[22]。本節(jié)利用實例分布設計了一個流型正則用于控制實例的幾何結構，其核心挑戰(zhàn)是尋找一個相似度度量函數來滿足如下性質：對于任何2 個實例，如果兩者的特征向量越相似，兩者的預測標簽距離就越小，反之亦然。

3.4.1 幾何相似度

本節(jié)利用k-means 聚類方法對每個標簽所有正實例的特征向量進行聚類，其中特征向量間的距離采用歐氏距離來度量。具體地，第i個標簽對應正實例聚成p個類，簇中心集為Si，每個元素s∈S是一個d維特征向量。對于任何一個簇中心s和簇中心集S，本節(jié)用最小主角來度量s到S的距離dist (s,S)[23]，即

其中，sT是s的轉置向量?；谠摼嚯x定義，本節(jié)定義標簽i與標簽j的幾何相似度為

3.4.2 標簽預測距離

融合幾何相似度與標簽預測距離，本文獲得如下形式的流型正則

3.5 排序正則

排序正則的核心目標是確保每個實例的正標簽排在其負標簽的前面，可定義為

其中，(i,j)p,n={x|實例x的第i個標簽是正標簽,第j個標簽是負標簽}。為實現該目標，本文定義標簽完備下任意標簽對的排序損失。

3.5.1 標簽完備下的排序損失

本文假設訓練集D中所有實例都被完全標記，即任意實例x的任意標簽i和標簽j為正標簽或負標簽，不存在任何缺失。針對該情況，對于任意標簽i和標簽j的排序損失定義為

其中(i,j)n,p={x| 實例x是的第i個負標簽，實例x的第j個標簽是正標簽}，鉸鏈損失h(j,i,x)為max {0,1+M jx?M ix}。因此，所有標簽對的排序損失和為實例排序損失。由于無法區(qū)分一個實例不同正標簽對實例描述程度的差異，本文未對實例正標簽進行排序；同理，本文也未對實例負標簽進行排序。

3.5.2 非完備標簽下的排序損失

針對任意標簽對(i,j)，本文假設其未被完全標記，即訓練集D中必存在一實例，其標簽i和標簽j存在一個標簽缺失。針對該情況，訓練集D中的所有實例可分為5 個類別：(i,j)p,m、(i,j)n,m、(i,j)m,p、(i,j)m,n和(i,j)m,m。其中，(i,j)p,m={x| 實例x的第i個標簽是正標簽,第j個標簽是缺失標簽}，剩余4 種類別的定義類似該定義。上述5 種情況的排序損失函數 rli (i,j)p,m、rli (i,j)n,m、rli (i,j)m,p、rli (i,j)m,n和 rli (i,j)m,m分別定義為

其中，θi和θj分別是標簽i和標簽j的正實例個數與整體實例個數的比值。完整的排序損失函數為

則標簽排序損失 RL(M)為標簽完備下的排序損失與標簽非完備情況下的排序損失和，即

3.6 目標函數

通過融合流型正則、排序正則與式(1)，并通過懲罰法轉化有約束優(yōu)化問題為無約束優(yōu)化問題，獲得如下形式的目標函數

其中，λ1和λ2用于控制相關部分的權值。

4 模型優(yōu)化

在目標函數式(2) 中，部分項g(M)=和 RL(M)是非連續(xù)不規(guī)則函數，其導函數是間斷函數，這使目標函數不具備精確解。同時，目標函數中的核范數||M||*與二次項的和可用高效算法來優(yōu)化[24]。針對上述特點，本節(jié)借鑒ADMM 的可分性，將目標函數中核范數||M||*與二次項組合，并與剩余項分割開，利用文獻[24]算法來優(yōu)化核范數部分。對于剩余項，本節(jié)利用線性近似法求解其近似解。上述方法融合了近似法與傳統(tǒng) ADMM[1]，本文稱之為線性LADMM，其詳細過程如下。

首先，引入輔助變量M=Z，將變量M的優(yōu)化問題轉化為變量M和Z的優(yōu)化問題，其目標函數為

其次，轉化式(3)問題為如下增廣拉格朗日形式

其中，β是正的乘子參數，γ∈Rd×l是正的拉格朗日常數。本節(jié)算法包含三部分：更新M、更新Z、更新γ。

4.1 更新M

固定式(4)問題中的變量Z和γ，式(4)問題變?yōu)榍蠼庾僊的最小化問題

式(5)問題包含非連續(xù)的不規(guī)則項g(M)和RL(M)，其不具備精確解。本文利用二次近似法優(yōu)化該問題從而獲得任意程度的近似解。具體地，選取初始點M(0)，對2 個項g(M)和 RL(M)在初始點展開為二次近似形式，展開后的函數是良定形式，求其精確解。以精確解為新的展開點重復上述過程直到獲得任意近似程度的解。函數g(M)和RL(M)在近似點M(k)的近似展開形式為

求函數關于變量M的導函數，并設置導函數為0，可得

通過分析發(fā)現，Q1和2XXT是2 個對稱矩陣，其對稱分解為Q1=UAUT和2XXT=VBVT。其中U和V是特征向量，A和B是對角矩陣，對角線元素是Q1和2XXT的特征值。利用對稱分解替換式(6)中的Q1和2XXT，可得

對式(7)左右兩邊分別乘以UT和V，可將其化簡為

4.2 更新Z

固定式(4)問題中變量M和γ，該問題變?yōu)榍蠼庾兞縕的最小化問題，即

式(10)是最小化核范數問題，可用文獻[24]算法來高效優(yōu)化，其解為

4.3 更新γ

固定式(4)問題中變量M和Z，變量γ可通過如下形式來更新

4.4 復雜度分析

從式(6)可知，更新變量M需要計算變量Q1和Q2以及2XXT和Q1的對稱分解，2XXT和Q1為常數矩陣，其計算和對稱分解由預處理步驟處理。在計算Q2過程中，流型正則部分的導數為，其時間復雜度為O(ld2)。本節(jié)假設每個數據以均等概率標注標簽和不標注標簽，則排序正則部分的時間復雜度為O(l2n2d)。因此，更新變量M的時間復雜度為O(k(ld2+l2n2d+ld))，其中k是迭代次數。更新變量Z的時間復雜度為O(min{ld2,l2d})。更新變量γ的時間復雜度為O(ld)。

本文方案（簡稱為SLCR）單次循環(huán)時間復雜度為O((l2n2d+k(ld2+l2n2d+ld)+min {ld2，l2d}+ld)nk)，其中，nk表示近似算法的迭代次數。BR 的時間復雜度為O(ld3+ldn2+d2n2+d3)。文獻[7]方案（簡稱為WSABIE）采用批量梯度下降法優(yōu)化目標函數，其時間復雜度為O(n s(ld+l2))，其中，ns表示單次選取的梯度下降數據數。文獻[6]方案（簡稱為LEML）使用交替下降法優(yōu)化目標函數，其單次循環(huán)時間復雜度為O(nnz(Y)+nnz(X))k+(n+l)k2)，其中，nnz(Y)?nL，k表示擬合矩陣的秩。文獻[14]方案（簡稱為SLRM）采用交替下降法優(yōu)化目標函數，其單次循環(huán)時間復雜度為O(d2nl+dn2+ldnl+min{dl2,d2l}+dl)，其中，nl表示訓練集中標記標簽數據個數。文獻[25]方案（簡稱為ICVL）采用交替下降法優(yōu)化目標函數，其單次循環(huán)時間復雜度為O(l2n+d2n+d3+l3+ldn)，其中，n表示實例個數，l表示標簽個數，d表示特征維數。如上所述，本文方案時間復雜度高于對比方案時間復雜度。

5 實驗

本節(jié)在6 個經典的多標簽數據集上比較本文方案和代表性標簽缺失下的多標簽學習方案的預測效果。

5.1 數據集

本文實驗的數據集為Emotions、Scene、Birds、Mediamill、Delicious、NUS-WIDE-B。為有效檢測標簽缺失下模型的預測效果，本文剔除了未標記標簽的數據，其詳細統(tǒng)計信息如表1 所示。

表1 實驗數據統(tǒng)計信息

5.2 對比方案

為證明本文方案的預測效果，本節(jié)實驗與如下代表性的標簽缺失下的多標簽學習方案進行比較：BR、WSABIE、LEML、SLRM、ICVL。本節(jié)使用Hamming Loss、Recall、F1-Measure、F1 macro、F1 micro 等5 個標準來評估各方案的預測效果。詳細評估標準信息如文獻[26]所示。

5.3 實驗結果

本文方案與對比方案在6 個數據集上的預測效果如表2～表6 所示。在5 個實驗評估標準中，Hamming Loss 取值越小其方案效果越好，其余評估標準取值越大方案效果越好。為準確比較方案的實驗效果，本文從大量實驗結果中挑選了具有相似Hamming Loss 值的實驗結果。從表2～表6 可以看出，本文方案獲得了較好的預測效果。例如，在數據集 NUS-WIDE-B 上，本文方案在 Recall、F1-Measure、F1 macro、F1 micro 評估標準上比最好對比方案分別高0.073、0.075、0.057 和0.042。該結果證明了本文方案在處理缺失標簽情況下更具穩(wěn)定性。詳細分析如下。

表2 6 個數據集上的Hamming Loss 比較

表3 6 個數據集上的Recall 比較

表4 6 個數據集上的F1-Measure 比較

表5 6 個數據集上的F1 macro 比較

表6 6 個數據集上的F1 micro 比較

1) LEML、SLRM 和ICVL 直接或間接考慮了低秩結構來提升預測精度，WSABIE 使用標簽排序來約束目標函數。然而，本文方案比LEML、SLRM和ICVL 有更好的實驗效果，其原因是低秩結構俘獲了標簽整體結構上的關聯(lián)，標簽排序和流型正則俘獲了個體標簽間的關聯(lián)，2 種標簽關聯(lián)相互補充，從而獲得了較好的預測效果。

2) 在Recall、F1-Measure、F1 macro 和F1 micro等評估標準下，BR 實驗效果與WSABIE、LEML和SLRM 的實驗效果接近。該結果證明了低秩結構在某些數據中并不總是有效。同時，本文方案在Scene 和Delicious 上取得了總體優(yōu)于對比方案的實驗效果，間接證明了流型正則化和排序正則化俘獲了更有效的標簽關聯(lián)。

不同標簽缺失率下本文方案與對比方案的預測效果如圖3～圖7 所示。該實驗在5 個數據集Emotions、Scene、Birds、Mediamill 和NUS-WIDE-B 上進行。從圖3～圖7 可以看出，盡管本文方案的實驗效果隨著標簽缺失率下降而下降，但是本文方案相比于對比方案仍獲得較好的實驗效果。其原因是本文流型結構從標簽正實例出發(fā)來度量標簽關聯(lián)，避免了使用標簽向量度量標簽關聯(lián)帶來的偏差問題。同時，排序正則化在一定程度上緩解了標簽錯誤標記帶來的模型偏差。

圖3 Mediamill 數據集上預測效果對比

圖4 Emotions 數據集上預測效果對比

圖5 Birds 數據集上預測效果對比

圖6 Scene 數據集上預測效果對比

圖7 NUS-WIDE-B 數據集上預測效果對比

6 結束語

本文針對標簽缺失下的多標簽標記問題，從數據流型角度出發(fā)俘獲了標簽關聯(lián)，利用加權排序降低了模型偏差，并利用低秩結構正則化模型，從而有效填充了缺失標簽。具體地，通過確保數據標簽幾何相似度與標簽預測距離一致性俘獲數據流型結構；通過度量完備標簽下和不完備標簽下的排序損失來對模型進行正則。實驗結果表明，本文方案優(yōu)于現有標簽缺失下的多標簽學習方案。