面向標(biāo)記分布學(xué)習(xí)的標(biāo)記增強(qiáng)

耿 新 徐 寧 邵瑞楓

(東南大學(xué)計算機(jī)科學(xué)與工程學(xué)院 南京 211189) (計算機(jī)網(wǎng)絡(luò)和信息集成教育部重點實驗室(東南大學(xué)) 南京 211189) (軟件新技術(shù)與產(chǎn)業(yè)化協(xié)同創(chuàng)新中心(南京大學(xué)) 南京 210093) (無線通信技術(shù)協(xié)同創(chuàng)新中心(東南大學(xué)) 南京 211189)

面向標(biāo)記分布學(xué)習(xí)的標(biāo)記增強(qiáng)

耿 新 徐 寧 邵瑞楓

(東南大學(xué)計算機(jī)科學(xué)與工程學(xué)院 南京 211189) (計算機(jī)網(wǎng)絡(luò)和信息集成教育部重點實驗室(東南大學(xué)) 南京 211189) (軟件新技術(shù)與產(chǎn)業(yè)化協(xié)同創(chuàng)新中心(南京大學(xué)) 南京 210093) (無線通信技術(shù)協(xié)同創(chuàng)新中心(東南大學(xué)) 南京 211189)

(xgeng@seu.edu.cn)

(CollaborativeInnovationCenterofWirelessCommunicationsTechnology(SoutheastUniversity),Nanjing211189)

多標(biāo)記學(xué)習(xí)(multi-label learning, MLL)任務(wù)處理一個示例對應(yīng)多個標(biāo)記的情況，其目標(biāo)是學(xué)習(xí)一個從示例到相關(guān)標(biāo)記集合的映射.在MLL中，現(xiàn)有方法一般都是采用均勻標(biāo)記分布假設(shè)，也就是各個相關(guān)標(biāo)記(正標(biāo)記)對于示例的重要程度都被當(dāng)作是相等的.然而，對于許多真實世界中的學(xué)習(xí)問題，不同相關(guān)標(biāo)記的重要程度往往是不同的.為此，標(biāo)記分布學(xué)習(xí)將不同標(biāo)記的重要程度用標(biāo)記分布來刻畫，已經(jīng)取得很好的效果.但是很多數(shù)據(jù)中卻僅包含簡單的邏輯標(biāo)記而非標(biāo)記分布.為解決這一問題，可以通過挖掘訓(xùn)練樣本中蘊含的標(biāo)記重要性差異信息，將邏輯標(biāo)記轉(zhuǎn)化為標(biāo)記分布，進(jìn)而通過標(biāo)記分布學(xué)習(xí)有效地提升預(yù)測精度.上述將原始邏輯標(biāo)記提升為標(biāo)記分布的過程，定義為面向標(biāo)記分布學(xué)習(xí)的標(biāo)記增強(qiáng).首次提出了標(biāo)記增強(qiáng)這一概念，給出了標(biāo)記增強(qiáng)的形式化定義，總結(jié)了現(xiàn)有的可以用于標(biāo)記增強(qiáng)的算法，并進(jìn)行了對比實驗.實驗結(jié)果表明：使用標(biāo)記增強(qiáng)能夠挖掘出數(shù)據(jù)中隱含的標(biāo)記重要性差異信息，并有效地提升MLL的效果.

多標(biāo)記學(xué)習(xí)；標(biāo)記分布學(xué)習(xí)；標(biāo)記增強(qiáng)；邏輯標(biāo)記；標(biāo)記分布

多標(biāo)記學(xué)習(xí)(multi-label learning, MLL)可以處理一個示例對應(yīng)多個標(biāo)記的情況，其目標(biāo)是學(xué)習(xí)一個多標(biāo)記的分類器，將示例映射到與之相關(guān)的標(biāo)記集合上[1-3].在過去的十余年間，MLL技術(shù)已經(jīng)被廣泛地應(yīng)用于許多領(lǐng)域，例如文本[4]、圖像[5]、語音[6]、視頻[7]等的分類、識別和檢索等，這些領(lǐng)域中的數(shù)據(jù)往往都含有豐富的語義，適合于用MLL來進(jìn)行建模.

標(biāo)記分布學(xué)習(xí)的出現(xiàn)使得從數(shù)據(jù)中學(xué)習(xí)比多標(biāo)記更為豐富的語義成為可能，比如可以更精確地刻畫與同一示例相關(guān)的多個標(biāo)記的相對重要性差異等.事實上，Geng[8]曾經(jīng)指出，單標(biāo)記學(xué)習(xí)和MLL都可以看作標(biāo)記分布學(xué)習(xí)的特例，這也就意味著標(biāo)記分布學(xué)習(xí)是一個更為泛化的機(jī)器學(xué)習(xí)框架，在此框架內(nèi)研究機(jī)器學(xué)習(xí)方法具有重要的理論和應(yīng)用價值.然而，標(biāo)記分布學(xué)習(xí)應(yīng)用的基礎(chǔ)是假設(shè)每個示例由一個涵蓋所有標(biāo)記重要程度的標(biāo)記分布來標(biāo)注，這一點在很多實際應(yīng)用中往往無法滿足.這些實際應(yīng)用中的數(shù)據(jù)多數(shù)情況下由單標(biāo)記或者多標(biāo)記(均勻標(biāo)記分布)標(biāo)注，缺乏完整的標(biāo)記分布信息.盡管如此，這些數(shù)據(jù)中的監(jiān)督信息本質(zhì)上卻是遵循某種標(biāo)記分布的.這種標(biāo)記分布雖然沒有顯式給出，卻常常隱式地蘊含于訓(xùn)練樣本中.如果能夠通過合適的方法將其恢復(fù)出來，則可以真正發(fā)揮標(biāo)記分布學(xué)習(xí)挖掘更多語義信息的優(yōu)勢.

基于上述考慮，本文提出的面向標(biāo)記分布學(xué)習(xí)的標(biāo)記增強(qiáng)是指將訓(xùn)練樣本中的原始邏輯標(biāo)記轉(zhuǎn)化為標(biāo)記分布的過程，這一過程依賴于對隱藏在訓(xùn)練樣本中的標(biāo)記相關(guān)信息的挖掘.假設(shè)Y表示樣本的原始邏輯標(biāo)記空間，D表示經(jīng)過標(biāo)記增強(qiáng)后的標(biāo)記分布空間，那么，標(biāo)記增強(qiáng)方法將原始的標(biāo)記空間Y={0,1}c拓展為D=[0,1]c，其中c表示標(biāo)記的個數(shù).事實上，D構(gòu)成c維歐氏空間中的一個超立方體，而Y僅位于該超立方體的頂點.標(biāo)記增強(qiáng)利用隱含于數(shù)據(jù)中的標(biāo)記間相關(guān)性，可以有效加強(qiáng)示例的監(jiān)督信息，進(jìn)而通過標(biāo)記分布學(xué)習(xí)獲得更好的預(yù)測效果.

盡管現(xiàn)有文獻(xiàn)中并未明確提出過標(biāo)記增強(qiáng)的概念，但是許多工作中實際上已經(jīng)涉及了一些與之相關(guān)的方法.例如：在頭部姿態(tài)估計問題中，文獻(xiàn)[9-10]依靠對數(shù)據(jù)的先驗知識，直接假設(shè)每個示例的標(biāo)記分布為高斯分布；文獻(xiàn)[11-12]用圖模型表示示例間的拓?fù)浣Y(jié)構(gòu)，通過加入一些模型假設(shè)，建立示例間相關(guān)性與標(biāo)記間相關(guān)性之間的關(guān)系，進(jìn)而將示例的邏輯標(biāo)記增強(qiáng)為標(biāo)記分布；文獻(xiàn)[13-16]從訓(xùn)練樣本中生成示例對每個標(biāo)記的模糊隸屬度，從而可以將原有的邏輯標(biāo)記增強(qiáng)為標(biāo)記分布.上述工作有些是直接為標(biāo)記分布學(xué)習(xí)而提出的，有些則是在其他領(lǐng)域提出但可以用來生成標(biāo)記分布.不管哪種情況，它們都可以統(tǒng)一到同一個概念下，即本文提出的面向標(biāo)記分布學(xué)習(xí)的標(biāo)記增強(qiáng).

1 符號及形式化定義

給定訓(xùn)練集S={(xi,Li)|1≤i≤n}，標(biāo)記增強(qiáng)即根據(jù)S中蘊含的標(biāo)記間相關(guān)性，將每個示例xi的邏輯標(biāo)記Li轉(zhuǎn)化為相應(yīng)的標(biāo)記分布Di，從而得到標(biāo)記分布訓(xùn)練集E={(xi,Di)|1≤i≤n}的過程.

2 標(biāo)記增強(qiáng)方法

在標(biāo)記分布學(xué)習(xí)這一概念提出之后，陸續(xù)有文獻(xiàn)提出了一些面向標(biāo)記分布學(xué)習(xí)的標(biāo)記增強(qiáng)方法.這些研究有的利用了具體應(yīng)用中的先驗知識，如頭部姿態(tài)和人臉年齡的先驗分布[9-10]；有的使用了半監(jiān)督學(xué)習(xí)[17]中常用的標(biāo)記傳播方法[11]；也有的引入了流形學(xué)習(xí)[12]，均取得了不錯的結(jié)果.而事實上，在標(biāo)記分布學(xué)習(xí)概念提出之前，其他領(lǐng)域也已經(jīng)出現(xiàn)了一些方法，盡管它們的應(yīng)用背景和具體目標(biāo)不盡相同，但是放到標(biāo)記分布學(xué)習(xí)的框架之中，卻可以用于實現(xiàn)標(biāo)記增強(qiáng)，經(jīng)典的如模糊聚類[13]、核隸屬度[14]等.

本文將現(xiàn)有的標(biāo)記增強(qiáng)算法分為3種類型，分別是基于先驗知識的標(biāo)記增強(qiáng)、基于模糊方法的標(biāo)記增強(qiáng)和基于圖模型的標(biāo)記增強(qiáng).下面分別闡述這3種類型中典型的標(biāo)記增強(qiáng)算法.

2.1 基于先驗知識的標(biāo)記增強(qiáng)

基于先驗知識的標(biāo)記增強(qiáng)算法建立在對數(shù)據(jù)本身特點有較為深入理解的基礎(chǔ)之上，完全依靠先驗知識直接將邏輯標(biāo)記增強(qiáng)為標(biāo)記分布，或者部分引入先驗知識，在此基礎(chǔ)上通過挖掘隱含的標(biāo)記間相關(guān)性將邏輯標(biāo)記增強(qiáng)為標(biāo)記分布.本節(jié)介紹2種基于先驗知識的標(biāo)記增強(qiáng)算法，分別是基于先驗分布的標(biāo)記增強(qiáng)算法和基于自適應(yīng)先驗分布的標(biāo)記增強(qiáng)算法.

2.1.1 基于先驗分布的標(biāo)記增強(qiáng)

在某些特定的應(yīng)用中，人們根據(jù)對數(shù)據(jù)的了解，可以預(yù)先知道每個示例應(yīng)滿足的標(biāo)記分布的參數(shù)模型，這種含參標(biāo)記分布模型就稱為先驗分布.一旦利用邏輯標(biāo)記以及一些啟發(fā)式方法確定了這種模型中的參數(shù)，就可以為每個示例生成相應(yīng)的標(biāo)記分布.

(1)

基于先驗分布的標(biāo)記增強(qiáng)算法一般在假設(shè)一個先驗分布的前提下，利用邏輯標(biāo)記以及一些啟發(fā)式方法確定先驗分布的參數(shù)，直接將示例xi的邏輯標(biāo)記Li轉(zhuǎn)化為相應(yīng)的標(biāo)記分布Di，從而得到標(biāo)記分布訓(xùn)練集E={(xi,Di)|1≤i≤n}.這類方法依賴于算法設(shè)計者對數(shù)據(jù)本身的深入理解.如果這種理解與事實相符則可能獲得不錯的效果，并且實現(xiàn)起來方便高效.然而，一旦對數(shù)據(jù)的理解有所偏差，則標(biāo)記增強(qiáng)后的結(jié)果往往并不理想.

2.1.2 基于自適應(yīng)先驗分布的標(biāo)記增強(qiáng)

如前所述，2.1.1節(jié)中的標(biāo)記增強(qiáng)算法完全依靠先驗知識直接將邏輯標(biāo)記增強(qiáng)為標(biāo)記分布.這一做法過于依賴先驗知識，在許多對數(shù)據(jù)的了解不夠充分的情況下，其生成的標(biāo)記分布不一定能夠真實反映數(shù)據(jù)本身的特點.為了解決上述問題，Geng等人[10]以人臉年齡估計為應(yīng)用背景，在引入先驗分布的前提下，通過自適應(yīng)方法確定先驗分布中的參數(shù)，從而將每個示例xi的邏輯標(biāo)記Li轉(zhuǎn)化為相應(yīng)的標(biāo)記分布Di.

(2)

基于自適應(yīng)先驗分布的標(biāo)記增強(qiáng)算法部分引入先驗知識，通過自適應(yīng)的方法，從訓(xùn)練樣本中學(xué)習(xí)得到先驗分布的參數(shù)，進(jìn)而將每個示例xi的邏輯標(biāo)記Li轉(zhuǎn)化為相應(yīng)的標(biāo)記分布Di.這類方法部分依賴先驗知識，部分依賴從樣例中學(xué)習(xí)，因此相較2.1.1節(jié)中完全依賴先驗知識的方法更能有效利用隱藏在訓(xùn)練數(shù)據(jù)中的標(biāo)記間相關(guān)性.正如文獻(xiàn)[10]中的實驗所報告的結(jié)果，一般情況下，基于自適應(yīng)先驗分布的標(biāo)記增強(qiáng)算法效果要優(yōu)于完全依賴先驗分布的標(biāo)記增強(qiáng)算法.

2.2 基于模糊方法的標(biāo)記增強(qiáng)

基于模糊方法的標(biāo)記增強(qiáng)[13-16]利用模糊數(shù)學(xué)的思想，通過模糊聚類、模糊運算和核隸屬度等方法，挖掘出標(biāo)記間相關(guān)信息，將邏輯標(biāo)記轉(zhuǎn)化為標(biāo)記分布.值得注意的是，這類方法提出的目的一般是為了將模糊性引入原本剛性的邏輯標(biāo)記，而并未明確其可以將邏輯標(biāo)記增強(qiáng)為標(biāo)記分布.但是，很多模糊標(biāo)記增強(qiáng)方法實際上可以基于模糊隸屬度輕松生成標(biāo)記分布.

本節(jié)介紹2種基于模糊方法的標(biāo)記增強(qiáng)算法，分別是基于模糊聚類的標(biāo)記增強(qiáng)算法和基于核隸屬度的標(biāo)記增強(qiáng)算法.

2.2.1 基于模糊聚類的標(biāo)記增強(qiáng)

基于模糊聚類的標(biāo)記增強(qiáng)[13]通過模糊C-均值聚類(fuzzy c-means algorithm, FCM)[18]和模糊運算，將訓(xùn)練集S中每個示例xi的邏輯標(biāo)記Li轉(zhuǎn)化為相應(yīng)的標(biāo)記分布Di，從而得到標(biāo)記分布訓(xùn)練集E={(xi,Di)|1≤i≤n}.

模糊C-均值聚類(FCM)是用隸屬度確定每個數(shù)據(jù)點屬于某個聚類程度的一種聚類算法.FCM把n個樣本分為p個模糊聚類，并求每個聚類的中心，使得所有訓(xùn)練樣本到聚類中心的加權(quán)(權(quán)值由樣本點對相應(yīng)聚類的隸屬度決定)距離之和最小.假設(shè)FCM將訓(xùn)練集S分成p個聚類，μk表示第k個聚類的中心，則可用:

(3)

(4)

即Aj為所有屬于第j個類的樣本的隸屬度向量之和.經(jīng)過行歸一化后得到的矩陣A可以被當(dāng)作一個“模糊關(guān)系”矩陣，A中的元素Ajk表示了第j個類別(標(biāo)記)與第k個聚類的關(guān)聯(lián)強(qiáng)度.

Vi=A°mxi，

(5)

其中，°表示模糊數(shù)學(xué)中的合成算子.最后，對隸屬度向量Vi進(jìn)行歸一化，使向量中元素的和為1，即得到標(biāo)記分布Di.

基于模糊聚類的標(biāo)記增強(qiáng)算法利用模糊聚類過程中產(chǎn)生的示例對每個聚類的隸屬度，通過類別和聚類的關(guān)聯(lián)矩陣，將示例對聚類的隸屬度轉(zhuǎn)化為對類別的隸屬度，從而生成標(biāo)記分布.在這一過程中，模糊聚類反映了示例空間的拓?fù)潢P(guān)系，而通過關(guān)聯(lián)矩陣將這種關(guān)系轉(zhuǎn)化到標(biāo)記空間，從而有可能使得簡單的邏輯標(biāo)記產(chǎn)生更豐富的語義，轉(zhuǎn)變?yōu)闃?biāo)記分布.

2.2.2 基于核隸屬度的標(biāo)記增強(qiáng)

該標(biāo)記增強(qiáng)方法源于一種模糊支持向量機(jī)中核隸屬度的生成過程[14]，通過一個非線性映射函數(shù)將示例xi映射到高維空間，利用核函數(shù)計算該高維空間中正負(fù)類的中心、半徑和各示例xi到類別中心的距離，進(jìn)而通過隸屬度函數(shù)計算示例xi的標(biāo)記分布.

φ(xi)，

(6)

(7)

其中，φ(xi)是一個非線性映射函數(shù)，由核函數(shù)K(xi,xj)=φ(xi)×φ(xj)確定.正類和負(fù)類的半徑分別計算為

(8)

(9)

樣本xi到正類和負(fù)類中心的平方距離分別是：

(10)

(11)

則示例xi對于標(biāo)記yj的隸屬度為

基于核隸屬度的標(biāo)記增強(qiáng)算法利用核技巧在高維空間中計算示例對每個類別的隸屬度，從而能夠挖掘訓(xùn)練數(shù)據(jù)中類別標(biāo)記間較為復(fù)雜的非線性系.

2.3 基于圖模型的標(biāo)記增強(qiáng)

基于圖模型的標(biāo)記增強(qiáng)算法用圖模型表示示例間的拓?fù)浣Y(jié)構(gòu)，通過引入一些模型假設(shè)，建立示例間相關(guān)性與標(biāo)記間相關(guān)性之間的關(guān)系，進(jìn)而將示例的邏輯標(biāo)記增強(qiáng)為標(biāo)記分布.本節(jié)介紹2種基于圖模型的標(biāo)記增強(qiáng)算法，分別是基于標(biāo)記傳播的標(biāo)記增強(qiáng)算法和基于流形的標(biāo)記增強(qiáng)算法.

2.3.1 基于標(biāo)記傳播的標(biāo)記增強(qiáng)

文獻(xiàn)[11]將半監(jiān)督學(xué)習(xí)[17]中的標(biāo)記傳播技術(shù)應(yīng)用于標(biāo)記增強(qiáng)中.該方法首先根據(jù)示例間相似度構(gòu)建一個圖，然后根據(jù)圖中的拓?fù)潢P(guān)系在示例間傳播標(biāo)記，由于標(biāo)記的傳播會受到路徑上權(quán)值的影響，會自然形成不同標(biāo)記的描述度差異，當(dāng)標(biāo)記傳播收斂時，每個示例的原有邏輯標(biāo)記即可增強(qiáng)為標(biāo)記分布.

具體地，假設(shè)多標(biāo)記訓(xùn)練集S={(xi,Li)|1≤i≤n}，G=(V,E,W)表示以S中的示例為頂點的全連通圖，其中V={xi|1≤i≤n}表示頂點，E表示頂點兩兩之間的邊，xi與xj之間的邊上的權(quán)值為它們之間的相似度：

(13)

F(t)=αPF(t-1)+(1-α)Φ，

(14)

其中，α是平衡參數(shù)，控制了初始的邏輯標(biāo)記和標(biāo)記傳播對最終描述度的影響程度.經(jīng)過迭代，最終F收斂到：F*=(1-α)(I-αP)-1Φ，對F*做歸一化處理：

(15)

基于標(biāo)記傳播的標(biāo)記增強(qiáng)算法通過圖模型表示示例間的拓?fù)浣Y(jié)構(gòu)，構(gòu)造了基于示例間相關(guān)性的標(biāo)記傳播矩陣，利用傳播過程中路徑權(quán)值的不同使得不同標(biāo)記的描述度自然產(chǎn)生差異，從而反映出蘊含在訓(xùn)練數(shù)據(jù)中的標(biāo)記間關(guān)系.

2.3.2 基于流形的標(biāo)記增強(qiáng)

基于流形的標(biāo)記增強(qiáng)算法[12]假設(shè)數(shù)據(jù)在特征空間和標(biāo)記空間均分布在某種流形上，并利用平滑假設(shè)將2個空間的流形聯(lián)系起來，從而可以利用特征空間流形的拓?fù)潢P(guān)系指導(dǎo)標(biāo)記空間流形的構(gòu)建，在此基礎(chǔ)上將示例的邏輯標(biāo)記增強(qiáng)為標(biāo)記分布.

具體地，該算法用圖G=(V,E,W)表示多標(biāo)記訓(xùn)練集S的特征空間的拓?fù)浣Y(jié)構(gòu)，其中V是由示例構(gòu)成的頂點集合，E是邊的集合，W=(wij)n×n是圖的邊權(quán)重矩陣.首先，在特征空間中，假設(shè)示例分布的流形滿足局部線性，即任意示例xi可以由它的K-近鄰的線性組合重構(gòu)，重構(gòu)權(quán)值矩陣W可通過最小化得到：

s.t.wij=0,xj不是xi的K-近鄰，

(16)

其中，Wi表示W(wǎng)的第i行，1T表示全部由1構(gòu)成的向量.通過平滑假設(shè)[19]，即特征相似的示例的標(biāo)記也很可能相似，可將特征空間的拓?fù)浣Y(jié)構(gòu)遷移到標(biāo)記空間中，即共享同樣的局部線性重構(gòu)權(quán)值矩陣W.這樣，標(biāo)記空間的標(biāo)記分布可由最小化得到：

(17)

(18)

基于流形的方法通過重構(gòu)特征空間和標(biāo)記空間的流形，利用平滑假設(shè)將特征空間的拓?fù)潢P(guān)系遷移到標(biāo)記空間中，建立示例間相關(guān)性與標(biāo)記間相關(guān)性之間的關(guān)系，從而將邏輯標(biāo)記增強(qiáng)為標(biāo)記分布.

2.4 小結(jié)與比較

本節(jié)簡要介紹了現(xiàn)存的3類可用于實現(xiàn)標(biāo)記增強(qiáng)的方法，分別是基于先驗知識的標(biāo)記增強(qiáng)、基于模糊方法的標(biāo)記增強(qiáng)和基于圖模型的標(biāo)記增強(qiáng)，每一類方法分別介紹了幾種典型的實現(xiàn)算法.這些算法有些是專門為了將邏輯標(biāo)記增強(qiáng)為標(biāo)記分布而提出的，如基于先驗知識的標(biāo)記增強(qiáng)方法和基于圖模型的標(biāo)記增強(qiáng)方法；有些則是源于其他領(lǐng)域的工作，但可以借用到本文語境中實現(xiàn)標(biāo)記增強(qiáng)，如基于模糊方法的標(biāo)記增強(qiáng).這些不同的增強(qiáng)方法，或者通過先驗知識，或者通過從樣本中學(xué)習(xí)來獲得額外的監(jiān)督信息，從而將訓(xùn)練樣本原有的簡單邏輯標(biāo)記轉(zhuǎn)化為信息量更為豐富的標(biāo)記分布.綜合來看，對于不同類型的標(biāo)記增強(qiáng)算法，其優(yōu)點和缺點總結(jié)如下：

1) 基于先驗知識的標(biāo)記增強(qiáng).優(yōu)點：在對數(shù)據(jù)有比較深入理解的前提下，可以充分利用先驗知識，快速高效地實現(xiàn)標(biāo)記增強(qiáng)；缺點：過于依賴先驗知識，在缺乏關(guān)于數(shù)據(jù)的領(lǐng)域知識的情況下無法應(yīng)用此類方法.

2) 基于模糊方法的標(biāo)記增強(qiáng).優(yōu)點：利用模糊隸屬度，將標(biāo)記間相關(guān)信息與邏輯標(biāo)記融合，不需要建立精確的數(shù)學(xué)模型，有較強(qiáng)的魯棒性，數(shù)據(jù)和參數(shù)等對算法影響較??；缺點：缺乏深度挖掘標(biāo)記空間和特征空間信息的明確模型，往往難以生成符合特定數(shù)據(jù)特點的標(biāo)記分布.

3) 基于圖模型的標(biāo)記增強(qiáng).優(yōu)點：充分利用特征空間的拓?fù)潢P(guān)系來指導(dǎo)標(biāo)記空間相關(guān)性信息挖掘，有良好的數(shù)學(xué)基礎(chǔ)，有利于形成適合數(shù)據(jù)本身特點的標(biāo)記增強(qiáng)算法；缺點：模型較為復(fù)雜，數(shù)據(jù)和參數(shù)對算法的影響較大.

3 實 驗

本節(jié)實驗在不同數(shù)據(jù)集上測試了第2節(jié)提到的3種代表性的標(biāo)記增強(qiáng)算法.由于基于先驗知識的標(biāo)記增強(qiáng)方法依賴于對數(shù)據(jù)本身的深入理解，只有在特定數(shù)據(jù)集上才能應(yīng)用，因此這類算法這里不作比較.

實驗主要分為2個部分：

1) 在一個人造數(shù)據(jù)集上測試所有對比算法由邏輯標(biāo)記增強(qiáng)為標(biāo)記分布的精度;

2) 在11個多標(biāo)記數(shù)據(jù)集上，將基于標(biāo)記增強(qiáng)的標(biāo)記分布學(xué)習(xí)算法與主流的MLL算法進(jìn)行對比.

3.1 實驗設(shè)置

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

實驗中共使用了12個數(shù)據(jù)集，包括1個人造數(shù)據(jù)集和11個真實世界的多標(biāo)記數(shù)據(jù)集.

(19)

(20)

(21)

(22)

(23)

(24)

這樣共生成2 601個分布于三維特征空間流形上的示例，每個示例對應(yīng)的真實標(biāo)記分布D由式(19)～(23)產(chǎn)生.

Table 1 Attributes of the Benchmark Multi-label Data Sets表1 基準(zhǔn)多標(biāo)記數(shù)據(jù)集屬性

實驗第2部分使用11個基準(zhǔn)多標(biāo)記數(shù)據(jù)集*http://meka.sourceforge.net/#datasets和http://mulan.sourceforge.net/datasets.html，這些數(shù)據(jù)集均來自真實應(yīng)用場景，在本實驗中用于比較基于標(biāo)記增強(qiáng)的MLL與傳統(tǒng)MLL算法.表1總結(jié)了這些數(shù)據(jù)集的各種屬性.其中，|S|,dim(S),L(S)和F(S)分別表示數(shù)據(jù)集的樣本數(shù)目、特征維度、類別標(biāo)記數(shù)目和特征類型.另外還有一些關(guān)于多標(biāo)記數(shù)據(jù)的統(tǒng)計指標(biāo)[20]，包括標(biāo)記基數(shù)LCard(S)、標(biāo)記密度LDen(S)、獨特標(biāo)記集合DL(S)和獨特標(biāo)記集合占比PDL(S).

3.1.2 對比算法

實驗的第1部分在人造數(shù)據(jù)集上直接對比4種標(biāo)記增強(qiáng)算法生成的標(biāo)記分布與真實標(biāo)記分布相比的相似程度.第2部分在11個多標(biāo)記數(shù)據(jù)集上對比基于標(biāo)記增強(qiáng)的MLL和傳統(tǒng)的MLL算法.所謂基于標(biāo)記增強(qiáng)的MLL是指先分別用4種標(biāo)記增強(qiáng)算法將數(shù)據(jù)集中原有的邏輯標(biāo)記增強(qiáng)為標(biāo)記分布；然后用標(biāo)記分布學(xué)習(xí)算法SA-BFGS[8]為從示例到標(biāo)記分布的映射建模；最后在測試時，用3.1.1節(jié)介紹的二值化方法將預(yù)測出的標(biāo)記分布轉(zhuǎn)化為邏輯標(biāo)記.

用于對比的傳統(tǒng)MLL算法包括4種MLL領(lǐng)域的主流算法，分別為binary relevance(BR)[21],calibrated label ranking(CLR)[22],ensemble of classifier chains (ECC)[20]和RAndom K-labELsets (RAKEL)[23].這4種算法都在MULAN MLL包[24]上運行，基分類器為logistic regression模型，ECC全體尺度設(shè)置為30，RAKEL的全體尺度設(shè)置為2c且K=3.

3.1.3 評價指標(biāo)

Table 2 Evaluation Measures for Label Enhancement Algorithms

Notes: “↓” indicates the smaller the better, and “↑” indicates the larger the better.

將標(biāo)記增強(qiáng)算法與傳統(tǒng)的MLL方法比較時，我們使用了在MLL中常用的5種評價指標(biāo)，分別是Hamming-loss,One-error,Coverage,Ranking-loss和Average-precision[25].

3.2 實驗結(jié)果

3.2.1 標(biāo)記分布比較實驗

為了直觀可視化標(biāo)記增強(qiáng)的效果，假設(shè)人造數(shù)據(jù)集中標(biāo)記分布的3個分量分別對應(yīng)RGB顏色空間的3個顏色通道.這樣，每個示例的標(biāo)記分布就可以用示例空間中點的顏色來直觀表示.根據(jù)3.1.1節(jié)描述的人造數(shù)據(jù)采樣方法可知，2 601個樣本點分布在三維示例空間的一個流形上.因此，通過比較這個流形上的顏色模式即可直觀判斷不同算法標(biāo)記增強(qiáng)的效果.圖1顯示了人造數(shù)據(jù)集上的真實標(biāo)記分布(圖1(a))以及4種標(biāo)記增強(qiáng)算法得到的標(biāo)記分布(圖1(b)～1(e)).為了方便觀察，圖1中對流形上的顏色應(yīng)用了去相關(guān)拉伸(decorrelation stretch)技術(shù)來增強(qiáng)顏色對比度.由圖1可以看出，LP算法標(biāo)記增強(qiáng)后的顏色模式非常接近真實標(biāo)記分布，KM算法和ML算法記增強(qiáng)后的顏色模式也與真實標(biāo)記分布相似,FCM算法的顏色模式和真實值差距較大.

進(jìn)一步，我們對4種標(biāo)記增強(qiáng)算法在人造數(shù)據(jù)集上的表現(xiàn)進(jìn)行了定量分析.表3給出了4種標(biāo)記增強(qiáng)算法在表2所示的6種評價指標(biāo)上的比較結(jié)果，每個結(jié)果后的括號中給出了相應(yīng)算法的排序，并且統(tǒng)計了每種算法在所有指標(biāo)上的平均排序.表3中的結(jié)果與圖1的可視化比較結(jié)果一致，即根據(jù)平均排序：LP?KM?ML?FCM.LP算法的表現(xiàn)最好，因為該算法在保留了原始的邏輯標(biāo)記的前提下，使用示例間相關(guān)信息對邏輯標(biāo)記進(jìn)行了增強(qiáng)；KM算法使用了模糊方法，不會對增強(qiáng)后的標(biāo)記分布引入過多的誤差，因此該算法也能夠得到較為不錯的結(jié)果；ML算法使用了流形模型，將示例間的相關(guān)信息與標(biāo)記相關(guān)信息建立了聯(lián)系，但使用的約束項不能夠保留較多的原始邏輯信息，因此標(biāo)記增強(qiáng)效果與KM算法接近；FCM算法的標(biāo)記分布生成中使用了簡單的模糊合成運算，不能有效地挖掘標(biāo)記相關(guān)信息，因此標(biāo)記增強(qiáng)的效果較差.

Fig. Visual comparison between the tabel distributions generated by the label anhancement algorithms and the groun-truth label distributions

圖1 標(biāo)記增強(qiáng)算法生成的標(biāo)記分布與真實標(biāo)記分布的可視化對比

Table3 Quantitative Comparison Between the Label Distributions Generated by the Label Enhancement Algorithms and the Ground-truth Label Distributions

表3 標(biāo)記增強(qiáng)算法生成的標(biāo)記分布與真實標(biāo)記分布的定量對比

Notes:“↓” indicates the smaller the better, and “↑” indicates the larger the better.

3.2.2 MLL比較實驗

實驗的第2部分在11個真實世界的多標(biāo)記數(shù)據(jù)集上比較基于標(biāo)記增強(qiáng)的MLL與傳統(tǒng)MLL算法.在每個數(shù)據(jù)集上采用10倍交叉驗證，記錄每個算法分別在5個MLL評價指標(biāo)上的平均值，結(jié)果如表4～8所示.其中，評價指標(biāo)后的“↓”表示“越低越好”，“↑”表示“越高越好”.在每種指標(biāo)和每個數(shù)據(jù)集上表現(xiàn)最好的算法的結(jié)果用黑體表示.算法在每種指標(biāo)和每個數(shù)據(jù)集上的排序顯示在其結(jié)果后的括號中，并統(tǒng)計了每種算法在所有數(shù)據(jù)集上的平均排序.

Table 4 Comparison of Multi-label Learning Algorithms on Ranking-loss↓ (mean±std)表4 MLL算法在Ranking-loss↓指標(biāo)(均值±標(biāo)準(zhǔn)差)上的比較

Table 5 Comparison of Multi-label Learning Algorithms on One-error↓ (mean±std)表5 MLL算法在One-error↓指標(biāo)(均值±標(biāo)準(zhǔn)差)上的比較

Table 6 Comparison of Multi-label Learning Algorithms on Hamming-loss↓ (mean±std)表6 MLL算法在Hamming-loss↓指標(biāo)(均值±標(biāo)準(zhǔn)差)上的比較

Table 7 Comparison of Multi-label Learning Algorithms on Coverage↓ (mean±std)表7 MLL算法在Coverage↓指標(biāo)(均值±標(biāo)準(zhǔn)差)上的比較

Table 8 Comparison of Multi-label Learning Algorithms on Average-precision↑ (mean±std)表8 MLL算法在Average-precision↑指標(biāo)(均值±標(biāo)準(zhǔn)差)上的比較

為了從統(tǒng)計意義上比較8種算法在11個數(shù)據(jù)集上的表現(xiàn)，這里采用一種由Dem?ar[26]提出的兩步統(tǒng)計假設(shè)檢驗法.該方法首先對原假設(shè)“所有算法的平均排序是一樣的”應(yīng)用Friedman檢驗.表9給出了在顯著水平為0.05、對比算法數(shù)為8、數(shù)據(jù)集數(shù)為11時，各個評價指標(biāo)上的Friedman統(tǒng)計值FF及關(guān)鍵值(critical value).可以看出，所有指標(biāo)上的FF值均大于關(guān)鍵值，因此在所有指標(biāo)上都可以拒絕原假設(shè)，即在每個指標(biāo)上所有算法的平均排序不是都一樣的.在此基礎(chǔ)上，該方法第2步用Nemenyi檢驗來檢驗算法兩兩之間的平均排序比較，結(jié)果可用如圖2所示的CD(critical difference)圖來表示.Nemenyi檢驗在顯著水平為0.05、對比算法數(shù)為8、數(shù)據(jù)集數(shù)為11時，CD=2.809 6.在CD圖中，每個算法的平均排序被標(biāo)注在同一條坐標(biāo)軸上.如果2個算法的平均排序之差小于CD值，則說明兩者沒有顯著差異，在CD圖中即將這2個算法用一條線段連起來.

Table 9 Friedman Statistics on Each Evaluation Measure表9 各種評價指標(biāo)上的Friedman統(tǒng)計值

Fig. 2 CD diagrams (CD=2.809 6) of the Nemenyi tests on the eight algorithms for the five evaluation measures圖2 在5個不同評價指標(biāo)上對8種算法對比應(yīng)用Nemenyi檢驗的CD圖

基于表4～8和圖2中的實驗結(jié)果，我們可以得出以下8條結(jié)論：

1) 總體上，4種標(biāo)記增強(qiáng)算法排名大致為LP?ML?KM?FCM.

2) 在Ranking-loss(圖2(a))和Coverage(圖2(d))指標(biāo)上，LP的平均排序是最小的(最優(yōu)的).

3) 在One-error(圖2(b))、Hamming-loss(圖2(c))和Average precision(圖2(e))指標(biāo)上，ML的平均排序是最小的(最優(yōu)的).

4) 在5種評價指標(biāo)中，ML和LP并沒有顯著差異，而且這2種標(biāo)記增強(qiáng)算法都顯著地優(yōu)于MLL算法BR.

5) 在One-error和Average precision指標(biāo)上，ML顯著地優(yōu)于MLL算法BR,CLR和RAKEL.

6) 在Ranking-loss,Coverage和Average precision指標(biāo)上，LP顯著優(yōu)于MLL算法BR和RAKEL.

7) 在5種指標(biāo)上，KM優(yōu)于BR，且KM與ECC,CLR,RAKEL沒有顯著的差異.

8) 4種標(biāo)記增強(qiáng)方法中，F(xiàn)CM平均排序是最差的，但與BR沒有顯著差異.

對比3.2.1節(jié)中的實驗結(jié)果，ML在第2部分實驗的表現(xiàn)好于KM主要是因為這里采用的數(shù)據(jù)集的標(biāo)記空間維度(標(biāo)記個數(shù))明顯高于3.2.1節(jié)中所采用的人造數(shù)據(jù)集.這時，KM中對標(biāo)記逐個處理的手法自然使得其在標(biāo)記個數(shù)較多時表現(xiàn)不佳.另外，總體來看，基于圖模型的標(biāo)記增強(qiáng)(LP和ML)平均性能要優(yōu)于基于模糊方法的標(biāo)記增強(qiáng)(KM和FCM)，這主要是因為KM和FCM都并非為了面向標(biāo)記分布的標(biāo)記增強(qiáng)而專門設(shè)計，因此一些非針對性的做法，如模糊操作的簡單運用或者對不同標(biāo)記的逐個處理使得這類方法直接用于標(biāo)記增強(qiáng)效果并不理想.當(dāng)然，在一些特殊情況下，如標(biāo)記個數(shù)比較少時，模糊方法也可能取得不錯的表現(xiàn).例如，在人造數(shù)據(jù)集上KM的表現(xiàn)就要優(yōu)于ML.

綜上，可以認(rèn)為，一方面，有效的標(biāo)記增強(qiáng)(如LP和ML算法)能夠顯著提升傳統(tǒng)MLL的效果.這說明標(biāo)記增強(qiáng)確實有助于挖掘蘊含在訓(xùn)練樣本中的標(biāo)記間相關(guān)信息;另一方面，由于KM和FCM算法并非為標(biāo)記分布專門設(shè)計，所以標(biāo)記增強(qiáng)的效果并不理想，這也說明了針對面向標(biāo)記分布的標(biāo)記增強(qiáng)進(jìn)行專門研究的必要性.

4 結(jié) 論

本文提出了面向標(biāo)記分布的標(biāo)記增強(qiáng)這一新概念.這類方法可以從訓(xùn)練樣本中挖掘隱藏的標(biāo)記間相關(guān)性信息，將樣本中原有的簡單邏輯標(biāo)記增強(qiáng)為包含更多監(jiān)督信息的標(biāo)記分布，從而為后續(xù)的機(jī)器學(xué)習(xí)過程提供了更多可用信息.

本文綜述了可用于面向標(biāo)記分布的標(biāo)記增強(qiáng)方法.它們有些是專門為標(biāo)記分布學(xué)習(xí)提出的增強(qiáng)方法，有些則是在其他領(lǐng)域(如模糊分類)提出，但可以用于實現(xiàn)標(biāo)記增強(qiáng).本文進(jìn)一步通過在1個人造數(shù)據(jù)集和11個真實世界的多標(biāo)記數(shù)據(jù)集上的實驗，比較了已有標(biāo)記增強(qiáng)算法的表現(xiàn)，顯示了標(biāo)記增強(qiáng)方法的優(yōu)勢.實驗結(jié)果表明，建立在良好標(biāo)記增強(qiáng)基礎(chǔ)上的MLL算法能夠取得比建立在邏輯標(biāo)記基礎(chǔ)上的傳統(tǒng)MLL算法更好的表現(xiàn)，這也說明了對標(biāo)記增強(qiáng)方法進(jìn)一步深入研究的必要性.未來在標(biāo)記增強(qiáng)方面的研究至少包括3點重要內(nèi)容：

1) 建立可用于標(biāo)記增強(qiáng)實驗的標(biāo)準(zhǔn)數(shù)據(jù)集.目前適合于標(biāo)記增強(qiáng)算法實驗的數(shù)據(jù)集還非常少，本文不得不借助人造數(shù)據(jù)或者多標(biāo)記數(shù)據(jù)集來進(jìn)行初步實驗.而適合于標(biāo)記增強(qiáng)的專門數(shù)據(jù)集中應(yīng)包括真實的標(biāo)記分布以及對應(yīng)的邏輯標(biāo)記.

2) 建立標(biāo)記增強(qiáng)算法的性能評價體系.該評價體系應(yīng)能全面反映算法從簡單邏輯標(biāo)記恢復(fù)真實標(biāo)記分布的能力.

3) 提出能夠充分利用標(biāo)記間相關(guān)性的標(biāo)記增強(qiáng)算法.標(biāo)記間相關(guān)性既可以體現(xiàn)在標(biāo)記空間，也可能從示例空間遷移而來，這方面不論是理論層面還是應(yīng)用層面都還有很大的研究空間.

[1]Gibaja E, Ventura S. A tutorial on multilabel larning[J]. ACM Computing Surveys, 2015, 47(3): 1-38

[2]Tsoumakas G, Katakis I, Vlahavas I. Mining multi-label data[G]//Data Mining and Knowledge Discovery Handbook. Berlin: Springer, 2009: 667-685

[3]Zhang Minling, Zhou Zhihua. A review on multi-Label learning algorithms[J]. IEEE Trans on Knowledge & Data Engineering, 2014, 26(8): 1819-1837

[4]Rubin N T, Chambers A, Smyth P, et al. Statistical topic models for multi-label document classification[J]. Machine Learning, 2012, 88(1): 157-208

[5]Cabral S R, Torre F D, Costeira P J, et al. Matrix completion for multi-label image classification[C] //Proc of NIPS 2011. Cambridge, MA: MIT Press, 2011: 190-198

[6]Lo H Y, Wang J C, Wang H M, et al. Cost-sensitive multi-Label learning for audio tag annotation and retrieval[J]. IEEE Trans on Multimedia, 2011, 13(3): 518-529

[7]Wang Jingdong, Zhao Yinghai, Wu Xiuqing, et al. A transductive multi-label learning approach for video concept detection[J]. Pattern Recognition, 2011, 44(10/11): 2274-2286

[8]Geng Xin. Label distribution learning[J]. IEEE Trans on Knowledge and Data Engineering, 2016, 28(7): 1734-1748

[9]Geng Xin, Xia Yu. Head pose estimation based on multivariate label distribution[C] //Proc of IEEE Conf on Computer Vision and Pattern Recognition. Piscataway, NJ: IEEE, 2014: 3742-3747

[10]Geng Xin, Wang Qin, Xia Yu. Facial age estimation by adaptive label distribution learning[C] //Proc of the 22nd Int Conf on Pattern Recognition. Piscataway, NJ: IEEE, 2014: 4465-4470

[11]Li Yukun, Zhang Minling, Geng Xin. Leveraging implicit relative labeling-importance information for effective multi-label learning[C] //Proc of IEEE Int Conf on Data Mining. Piscataway, NJ, IEEE, 2015: 251-260

[12]Hou Peng, Geng Xin, Zhang Minling. Multi-label manifold learning[C] //Proc of the 30th AAAI Conf on Artificial Intelligence. Menlo Park, CA: AAAI, 2016: 1680-1686

[13]Gayar N E, Schwenker F, Palm G. A study of the robustness of KNN classifiers trained using soft labels[C] //Proc of the 2nd Conf Artificial Neural Networks in Pattern Recognition. Berlin: Springer, 2006: 67-80

[14]Jiang Xiufeng, Yi Zhang, Lv Jiancheng. Fuzzy SVM with a new fuzzy membership function[J]. Neural Computing & Applications, 2006, 15(3/4): 268-276

[15]Lin Xiaotong, Chen Xuewen. Mr. KNN: Soft relevance for multi-label classification[C] //Proc of the 19th ACM Int Conf on Information and Knowledge Management. New York: ACM, 2010: 349-358

[16]Jiang J Y, Tsai C C, Lee S J. FSKNN: Multi-label text categorization based on fuzzy similarity and k nearest neighbors[J]. Expert Systems with Applications, 2012, 39(3): 2813-2821

[17]Zhu Xiaojin, Goldberg A B. Introduction to Semi-Supervised Learning[M]. Williston, VT: Morgan & Claypool, 2009[18]Klir J G, Yuan B. Fuzzy sets and fuzzy logic[G] //Theory and Applications. Upper Saddle River, NJ: Prentice Hall, 1995

[19]Zhu Xiaojin, Lafferty J, Rosenfeld R. Semi-supervised learning with graphs[D]. Pittsburgh, PA: Language Technologies Institute, School of Computer Science, Carnegie Mellon University, 2005

[20]Read J, Pfahringer B, Holmes G, et al. Classifier chains for multi-label classification[J]. Machine Learning, 2011, 85(3): 333-359

[21]Boutell R M, Luo Jiebo, Shen Xipeng, et al. Learning multi-label scene classification[J]. Pattern Recognition, 2004, 37(9): 1757-1771

[22]Fürnkranz J, Hüllermeier E, Mencía E L, et al. Multi-label classification via calibrated label ranking[J]. Machine Learning, 2008, 73(2): 133-153

[23]Tsoumakas G, Katakis I, Vlahavas I. Randomk-labelsets for multilabel classification[J]. IEEE Trans on Knowledge and Data Engineering, 2011, 23(7): 1079-1089

[24]Tsoumakas G, Eleftherios S, Vilcek J, et al. MULAN: A Java library for multi-label learning[J]. Journal of Machine Learning Research, 2011, 12(7): 2411-2414

[25]Zhang Minling, Zhou Zhihua. A review on multi-label learning algorithms[J]. IEEE Trans on Knowledge and Data Engineering, 2014, 26(8): 1819-1837

[26]Dem?ar J. Statistical comparisons of classifiers over multiple data sets[J]. Journal of Machine Learning Research, 2006, 7(1): 1-30

Geng Xin, born in 1978. PhD, professor. His main research interests include machine learning, pattern recognition, and computer vision.

Xu Ning, born in 1988. PhD candidate. His main research interests include pattern recognition and machine learning.

Shao Ruifeng, born in 1994. Master candidate. His main research interests include pattern recognition and machine learning.

Label Enhancement for Label Distribution Learning

Geng Xin, Xu Ning, and Shao Ruifeng

(SchoolofComputerScienceandEngineering,SoutheastUniversity,Nanjing211189) (KeyLaboratoryofComputerNetworkandInformationIntegration(SoutheastUniversity),MinistryofEducation,Nanjing211189) (CollaborativeInnovationCenterofNovelSoftwareTechnologyandIndustrialization(NanjingUniversity),Nanjing210093)

Multi-label learning (MLL) deals with the case where each instance is associated with multiple labels. Its target is to learn the mapping from instance to relevant label set. Most existing MLL methods adopt the uniform label distribution assumption, i.e., the importance of all relevant (positive) labels is the same for the instance. However, for many real-world learning problems, the importance of different relevant labels is often different. For this issue, label distribution learning (LDL) has achieved good results by modeling the different importance of labels with a label distribution. Unfortunately, many datasets only contain simple logical labels rather than label distributions. To solve the problem, one way is to transform the logical labels into label distributions by mining the hidden label importance from the training examples, and then promote prediction precision via label distribution learning. Such process of transforming logical labels into label distributions is defined as label enhancement for label distribution learning. This paper first proposes the concept of label enhancement with a formal definition. Then, existing algorithms that can be used for label enhancement have been surveyed, and compared in the experiments. Results of the experiments reveal that label enhancement can effectively discover the difference of the label importance hidden in the data, and improve the performance of multi-label learning.

multi-label learning (MLL); label distribution learning (LDL); label enhancement; logical label; label distribution

2017-01-03；

2017-03-09

國家自然科學(xué)基金優(yōu)秀青年科學(xué)基金項目(61622203)；江蘇省自然科學(xué)基金杰出青年基金項目(BK20140022) This work was supported by the National Natural Science Fundation of China for Excellent Young Scientists (61622203) and Jiangsu Natural Science Funds for Distinguished Young Scholar (BK20140022).

TP391