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

（1.中國(guó)科學(xué)院信息工程研究所，北京 100093；2.中國(guó)科學(xué)院大學(xué)網(wǎng)絡(luò)空間安全學(xué)院，北京 100049；3.中國(guó)電子科技集團(tuán)公司信息科學(xué)研究院，北京 100086）

1 引言

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

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

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

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

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

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

3) 在6 個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，本文方案優(yōu)于代表性的標(biāo)簽缺失下的多標(biāo)簽學(xué)習(xí)方案。在一些評(píng)估標(biāo)準(zhǔn)下，本文方案的精度比最好的對(duì)比方案提升了10%以上。

2 相關(guān)工作

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

針對(duì)以上不足，研究者提出隱式方法來(lái)提升模型預(yù)測(cè)精度，其大體分為基于標(biāo)簽矩陣方法和基于擬合矩陣方法?；跇?biāo)簽矩陣方法的核心思想是利用典型相關(guān)分析和線性變化等技術(shù)壓縮高維標(biāo)簽空間為低維空間，隨后在低維空間中預(yù)測(cè)標(biāo)簽并將其翻轉(zhuǎn)到原標(biāo)簽空間。例如，Tai 等[11]對(duì)標(biāo)簽矩陣做奇異值分解，利用奇異值向量矩陣（低維正交矩陣）做投影矩陣，利用其轉(zhuǎn)置矩陣做解碼矩陣（正交矩陣的逆矩陣是其轉(zhuǎn)置矩陣）。Zhang 等[5]利用2 個(gè)線性變換分別壓縮標(biāo)簽和預(yù)測(cè)標(biāo)簽，通過(guò)典型相關(guān)分析尋找壓縮標(biāo)簽空間最優(yōu)預(yù)測(cè)方向來(lái)俘獲標(biāo)簽關(guān)聯(lián)。隨后，在文獻(xiàn)[5]方案的框架下，Zhang 等[12]保持標(biāo)簽距離結(jié)構(gòu)與嵌入標(biāo)簽距離結(jié)構(gòu)一致性，并最大化數(shù)據(jù)預(yù)測(cè)標(biāo)簽與其他數(shù)據(jù)預(yù)測(cè)標(biāo)簽的邊界距離，提出了嵌入標(biāo)簽可區(qū)分性和可預(yù)測(cè)性的多標(biāo)簽學(xué)習(xí)方案。然而，隨著標(biāo)簽規(guī)模的變大，確保整體數(shù)據(jù)距離結(jié)構(gòu)的方案[12]需要極大的計(jì)算開(kāi)銷。針對(duì)該不足，Jin 等[13]僅約束實(shí)例預(yù)測(cè)標(biāo)簽與其嵌入標(biāo)簽距離小于實(shí)例預(yù)測(cè)標(biāo)簽與其近鄰數(shù)據(jù)嵌入標(biāo)簽距離。

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

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

3 模型描述

3.1 模型動(dòng)機(jī)

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

圖1 模型流型正則和標(biāo)簽排序正則步驟

3.2 標(biāo)簽標(biāo)記流程

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

圖2 標(biāo)簽標(biāo)記流程

3.3 擬合矩陣的低秩結(jié)構(gòu)

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

其中，參數(shù)k1與k0一一對(duì)應(yīng)。

3.4 流型正則

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

3.4.1 幾何相似度

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

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

3.4.2 標(biāo)簽預(yù)測(cè)距離

融合幾何相似度與標(biāo)簽預(yù)測(cè)距離，本文獲得如下形式的流型正則

3.5 排序正則

排序正則的核心目標(biāo)是確保每個(gè)實(shí)例的正標(biāo)簽排在其負(fù)標(biāo)簽的前面，可定義為

其中，(i,j)p,n={x|實(shí)例x的第i個(gè)標(biāo)簽是正標(biāo)簽,第j個(gè)標(biāo)簽是負(fù)標(biāo)簽}。為實(shí)現(xiàn)該目標(biāo)，本文定義標(biāo)簽完備下任意標(biāo)簽對(duì)的排序損失。

3.5.1 標(biāo)簽完備下的排序損失

本文假設(shè)訓(xùn)練集D中所有實(shí)例都被完全標(biāo)記，即任意實(shí)例x的任意標(biāo)簽i和標(biāo)簽j為正標(biāo)簽或負(fù)標(biāo)簽，不存在任何缺失。針對(duì)該情況，對(duì)于任意標(biāo)簽i和標(biāo)簽j的排序損失定義為

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

3.5.2 非完備標(biāo)簽下的排序損失

針對(duì)任意標(biāo)簽對(duì)(i,j)，本文假設(shè)其未被完全標(biāo)記，即訓(xùn)練集D中必存在一實(shí)例，其標(biāo)簽i和標(biāo)簽j存在一個(gè)標(biāo)簽缺失。針對(duì)該情況，訓(xùn)練集D中的所有實(shí)例可分為5 個(gè)類別：(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| 實(shí)例x的第i個(gè)標(biāo)簽是正標(biāo)簽,第j個(gè)標(biāo)簽是缺失標(biāo)簽}，剩余4 種類別的定義類似該定義。上述5 種情況的排序損失函數(shù) 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分別是標(biāo)簽i和標(biāo)簽j的正實(shí)例個(gè)數(shù)與整體實(shí)例個(gè)數(shù)的比值。完整的排序損失函數(shù)為

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

3.6 目標(biāo)函數(shù)

通過(guò)融合流型正則、排序正則與式(1)，并通過(guò)懲罰法轉(zhuǎn)化有約束優(yōu)化問(wèn)題為無(wú)約束優(yōu)化問(wèn)題，獲得如下形式的目標(biāo)函數(shù)

其中，λ1和λ2用于控制相關(guān)部分的權(quán)值。

4 模型優(yōu)化

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

首先，引入輔助變量M=Z，將變量M的優(yōu)化問(wèn)題轉(zhuǎn)化為變量M和Z的優(yōu)化問(wèn)題，其目標(biāo)函數(shù)為

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

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

4.1 更新M

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

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

求函數(shù)關(guān)于變量M的導(dǎo)函數(shù)，并設(shè)置導(dǎo)函數(shù)為0，可得

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

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

4.2 更新Z

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

式(10)是最小化核范數(shù)問(wèn)題，可用文獻(xiàn)[24]算法來(lái)高效優(yōu)化，其解為

4.3 更新γ

固定式(4)問(wèn)題中變量M和Z，變量γ可通過(guò)如下形式來(lái)更新

4.4 復(fù)雜度分析

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

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

5 實(shí)驗(yàn)

本節(jié)在6 個(gè)經(jīng)典的多標(biāo)簽數(shù)據(jù)集上比較本文方案和代表性標(biāo)簽缺失下的多標(biāo)簽學(xué)習(xí)方案的預(yù)測(cè)效果。

5.1 數(shù)據(jù)集

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

表1 實(shí)驗(yàn)數(shù)據(jù)統(tǒng)計(jì)信息

5.2 對(duì)比方案

為證明本文方案的預(yù)測(cè)效果，本節(jié)實(shí)驗(yàn)與如下代表性的標(biāo)簽缺失下的多標(biāo)簽學(xué)習(xí)方案進(jìn)行比較：BR、WSABIE、LEML、SLRM、ICVL。本節(jié)使用Hamming Loss、Recall、F1-Measure、F1 macro、F1 micro 等5 個(gè)標(biāo)準(zhǔn)來(lái)評(píng)估各方案的預(yù)測(cè)效果。詳細(xì)評(píng)估標(biāo)準(zhǔn)信息如文獻(xiàn)[26]所示。

5.3 實(shí)驗(yàn)結(jié)果

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

表2 6 個(gè)數(shù)據(jù)集上的Hamming Loss 比較

表3 6 個(gè)數(shù)據(jù)集上的Recall 比較

表4 6 個(gè)數(shù)據(jù)集上的F1-Measure 比較

表5 6 個(gè)數(shù)據(jù)集上的F1 macro 比較

表6 6 個(gè)數(shù)據(jù)集上的F1 micro 比較

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

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

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

圖3 Mediamill 數(shù)據(jù)集上預(yù)測(cè)效果對(duì)比

圖4 Emotions 數(shù)據(jù)集上預(yù)測(cè)效果對(duì)比

圖5 Birds 數(shù)據(jù)集上預(yù)測(cè)效果對(duì)比

圖6 Scene 數(shù)據(jù)集上預(yù)測(cè)效果對(duì)比

圖7 NUS-WIDE-B 數(shù)據(jù)集上預(yù)測(cè)效果對(duì)比

6 結(jié)束語(yǔ)

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