基于全局和局部標簽相關性的MIMLSVM改進算法①

李村合,張振凱

(中國石油大學(華東)計算機與通信工程學院,青島 266580)

在利用機器學習中的傳統監督學習[1]解決實際問題時,常見的做法是先對真實的對象進行特征提取,用一個特征向量來描述這個對象,這樣就得到了一個示例(instance),然后把示例與該對象所對應的類別標記(label)關聯起來,就得到了一個例子(example).在擁有了一個較大的例子集合之后,就可以利用某種學習算法來學得示例空間與標記空間之間的一個映射,該映射可以預測未見示例的標記.在待學習對象具有明確的、單一的語義時,上面的學習框架已經取得了巨大的成功.但是真實世界中的對象往往具有復雜的含義,只用一個示例和一個標記來表達過于簡單,在剛開始的表示階段就失去了很多重要的信息.

為了解決上述問題,多示例多標簽[2,3]框架應運而生.在該框架下一個對象用一組示例來表示,并且和一組類別標記相關聯.比如一篇文章中的每個部分可以用一個示例來表示,而這篇文章可能同時屬于“娛樂”、“旅游”、“經濟”等不同的類別.多示例多標簽已成功應用到了場景分類、基因功能注釋、圖像標注等領域,彰顯了其強大的學習能力和潛力.

支持向量機(Support Vector Machines,SVM)[4]是一種高效的分類識別方法,在解決高維模式識別問題呈現出其獨特的優勢.它通過尋找一個最優分類超平面來實現分類.支持向量機以統計學習理論中的VC 維(Vapnik-Chervonenkis Dimension)理論[5]以及結構風險最小原理為基礎,最終的決策函數由少量支持向量決定,其數學形式簡單,同時有效克服樣本空間的高維性帶來的計算復雜問題,已經在系統辨識、人臉檢測及生物信息等領域中被用到.多示例多標記框架下的許多算法或直接使用了SVM 或對其改造使其適應多示例多標記的學習,這些算法在學習過程中已經取得了不錯的分類效果.在真實的學習問題中,標記之間通常具有局部標記相關性及全局相關性,如果僅僅考慮其一有可能會影響到實驗分類的準確率,因此如何兼顧考慮二者是能否取得良好實驗效果的關鍵.

本文的整體組織結構如下：第1 部分介紹相關工作,第2 部分提出改進的算法,第3 部分給出了實驗及結果,最后進行了總結.

1 相關工作

傳統的監督學習框架是一種單示例單標記(Single-Instance Single-Label,SISL)學習框架,形象化的來說,另x為 示例空間,y為標記空間,則學習的任務是從數據集{(x1,y1),(x2,y2),···,(xm,ym)}中 學得函數f:x→y,其中xi∈X為一個示例,yi∈y為 示例xi所屬的類別標記[1].

多示例學習(Multi-Instance Learning,MIL)[2]中的每個對象是用一個示例包來表示,同時該對象只與一個類別標記相關聯.給定數據集{ (x1,y1),(x2,y2),···,(xm,ym)},目標是學得f:2x→y.其中xi?x為 一組示例{xi1,xi2,···,xi,ni},xij∈x(j=1,2,···,ni),yi∈y為 與xi的 類別標記.ni為xi中所含示例的個數.近年來,也出現了很多多示例學習算法,比如Diverse Density[6]、EM-DD[7]、k-近鄰,決策樹算法RELIC[8],神經網絡算法RBF-MIP[9]等.多示例學習也被廣泛的應用于自然場景分類、基于內容的圖像檢索、WEB 目錄頁面推薦以及機器人領域中[10].

多標記學習(Multi-Label Learning,MLL)[2]中一個對象是用一個示例來表示,同時該對象與多個類別標記相關聯.多標簽學習近年來得到了廣泛的研究.根據所使用的標簽相關程度,它可以分為三類[11]：一階,二階和高階.對于第一組,不考慮標簽相關性,并將多標簽問題轉換為多個獨立的二元分類問題.一個眾所周知的例子是二元相關(BR)算法[12],它為每個標簽獨立地訓練一個分類器.對于第二組,考慮成對標簽關系.例如,校準標簽排名(CLR)[13]將多標簽學習問題轉化為成對標簽排序問題.最后,對于第三組,所有其他標簽對每個標簽施加的影響都被考慮在內.例如,分類器鏈(CC)[14]將多標簽學習問題轉換為二元分類問題鏈,將標注標簽編碼為特征.另一種考慮所有標簽相關性的方法是通過學習一個潛在的標簽空間來捕捉更高級別的標簽語義.通常,這是通過標簽矩陣的低秩分解[15]獲得的.最近,Yeh CK 等人[16]也提出了深度學習方法來學習聯合特征和標簽嵌入.這些方法與典型相關分析(CCA)高度相關[17],它學習了一個潛在的子空間,以便將實例表示與相應的標簽對齊.

要發揮多示例多標記框架的能力,要設計有效的學習算法.傳統的監督學習、多示例學習以及多標記學習都可以看作是多示例多標記的退化表示形式,因此設計多示例多標記算法的一種思路是使用退化策略,將多示例多標記問題轉化為多示例或者是多標記學習問題,進而再進一步轉化為傳統監督學習問題,最后使用傳統的機器學習來解決相應問題.但是在退化的過程中會有重要信息丟失,比如標記之間的聯系信息、示例與標記之間的聯系信息等,進而影響到了最后的分類效果.為了避免退化策略中信息丟失問題的發生,衍生了另一種算法思路,即直接改造機器學習中相應的的算法使其適應多示例多標簽框架.

基于退化策略,周志華等人提出了MIMLBOOST算法[3]和MIMLSVM 算法[3],基于正則化機制以及最大化間隔策略提出了D-MIMLSVM 算法[1]和M3MIML算法[18].MIMLBOOST 算法首先將多示例多標記樣本(Xi,Yi)轉 化為|y|個 多示例單標記樣本{([Xi,y],φ[Xi,y])|y∈Y}( |y|是標記空間中標記的數目),其中,每一個示例[Xi,y]都 是由示例集合Xi和 類別標記y拼接而成,當類別標記y∈Yi時 ,φ [Xi,y]=+1,否則φ [Xi,y]=-1.轉化完成后,多示例多標記問題已經變為多示例學習問題了,然后使用多示例學習中的MIBOOSTING 算法[19]對轉化后的問題進行求解.MIMLSVM 算法則是以多標記為橋梁,首先利用聚類將多示例多標記轉化為多標記學習問題,再借助于多標記學習的算法進行求解.MIMLBOOST 算法和MIMLSVM 算法都是使用的退化方法,因此均有信息丟失.D-MIMLSVM 算法假設類別標記集合Y中共含有T個類別標記,同時假設分類系統由T個函數f=(f1,f2,···,fT)構成,每一個函數都是由示例空間到實值空間的映射,即ft:2X→R,t=1,2,···,T,也就是為每一個標記建立一個分類器.該算法在訓練集上定義了一個損失函數V,使用了某種定義在包上的多示例核函數[20],最后通過優化V,利用CCCP[21,22]的迭代優化策略對其求解.M3MIML 算法假設分類系統包含T個線性模型,每個線性模型對應于一個可能的概念類,一個測試樣本是否屬于第i類是由其包含的所有示例在上述對應的某個線性模型上的最大輸出決定的.M3MIML 基于最大化間隔策略,將二次規劃問題分解為一系列相對簡單的線性規劃問題求解,最后利用KKT 條件[23]求解對偶問題獲得模型參數.

以前的大多數研究集中在全局標簽相關性上,但是,有時標簽關聯只能由局部數據子集所共享.為了緩解這個問題,使用局部相關性的多標簽學習(MLLOC)[24]通過嵌入代碼來擴展每個實例的特征表示,所述代碼編碼實例標簽對局部標簽相關性的影響.MLLOC 在利用局部相關性方面取得了成功.但是像摘要所提到的那樣,有時局部和全局同樣重要,而MLLOC 僅僅可以處理局部標簽并且無法處理缺失標簽的情況.為了進一步解決這個問題,提出了本文的算法.

2 MIMLSVM 算法及改進算法

2.1 MIMLSVM 算法

MIMLSVM 算法是以多標記學習為橋梁,將多示例多標記學習問題退化為傳統監督學習問題求解.首先,MIMLSVM 算法將每個多示例多標記樣本(Xi,Yi)轉化為一個單示例多標記樣本 (φ(Xi),Yi).其中,函數φ是基于構造性聚類[25]將每個示例包Xi轉化為一個示例Zi.該聚類過程將集合Λ ={X1,···,Xm}中的每個包看作一個原子對象,基于Hausdorff 距離度量包之間的距離并利用k-medoids 算法將集合 Λ劃分為若干個聚類.此時Zi的每一維即為包Xi與各聚類中心的距離,這樣,多示例多標記樣本集就轉換成了單示例多標記樣本集,此過程完成后,MIMLSVM 算法利用MLSVM 算法[26]對轉換得到的多標記學習問題進行求解.MLSVM算法將多標簽學習問題分解為多個獨立的二元分類問題,從而為每一個類別標記建立一個SVM 分類器,事實上,示例zi參 與了每一個分類器的構建,示例Zi對應的 標 簽 集 合Yi包 含y時,即y∈Yi時φ (Zi,y)=+1,否 則φ(Zi,y)=-1.至此,已經將多標記學習轉化為了傳統的監督學習,可以使用SVM 進行訓練分類了.對于未見標記的示例包,利用構造性聚類轉化為單個的示例,然后交給訓練出來的|y|個分類器,每個分類器在該示例上會有不同輸出,用輸出為正的分類器對應的類別來標記該示例即可.但是注意到,如果未見標記的示例在每個分類器上的輸出都為負值,那該示例將會變得不可分,即沒有類別標記與之對應.為了避免這種情況的出現,這里采用T-Criterion 準則[27]來進行預測,即當所有分類器的輸出均是負值時,用輸出值“最大”的分類器對應的類別來標記該示例.

但是在退化過程中存在一個明顯的問題,那就是為每一個類別標記建立分類器的時候,忽略了標記之間的相關性.前文也提到過,針對此也提出了一些改進算法,比較有效的是MLLOC 算法,雖然此算法有一定效果,但是僅僅只是從局部標簽相關性角度出發,忽略了全局相關性.這里使用多標記學習中的一種既考慮局部相關性又考慮全局相關性并且可以處理缺失標簽的算法GLOCAL[28]對MIMLSVM 算法進行改進.

2.2 MIMLSVM 算法的改進算法

GLOCAL 算法[28]是Yue Zh、Kwok JT 和Zhou ZH 在研究多標記學習時提出的一種全新的多標記算法,通過學習潛在標簽表示和優化標簽流形,同時處理全標簽和缺失標簽情況,并且同時利用全局和局部標簽相關性.GLOCAL 算法之所以能夠取得成功,主要歸咎于以下四點：(1)它使用標簽矩陣的低秩結構來獲得更緊湊和更抽象的潛在標簽表示,這也為丟失標簽恢復提供了自然的解決方案(2.2.1 中介紹)；(2)它利用全局和局部標簽相關性,因此標簽分類器可以利用來自所有標簽的信息2.2.2 中介紹)；(3)它直接從數據中學習標簽相關性,而不需要通過在關聯矩陣中進行普通且困難的人工分辨(2.2.3 中介紹)；(4)將上述問題綜合為一個聯合學習問題,采用高效交替最優化策略進行優化(2.2.4 中介紹).

2.2.1 基本模型

基本GLOCAL 模型對標簽矩陣應用低秩分解以獲得潛在標簽,并學習從特征空間到潛在標簽的映射.因此,我們可以得到一個更緊湊和更抽象的潛在標簽表示,它是密集的,實值的,并且是低維的.學習從特征空間到潛在標簽空間的映射也比學習原始標簽空間(稀疏,二進制值和更高維)更容易.此外,它直接提供缺少標簽恢復的解決方案.

具體來說,我們使用：

為了將示例映射到潛在標簽,我們學習了一個矩陣W ∈Rd×k,這個W 可以通過最小化平方損耗獲得,其中 X=[x1,···,xn]∈Rd×n是包含所有示例的矩陣.隨后,針對示例 x 所預測的標簽是 s ign(f(x)),其中f(x)=UWTx.讓其中 fj(x)是 x 的 第j 個預測標簽,可以將所有 x ∈X 的 f(x)連接在一起成為結合低秩矩陣分解的重構誤差最小化和從示例到潛在標簽的線性映射的平方損失最小化,我們得到了基本GLOCAL 模型的以下優化問題：

其中,R (U,V,W)是 正則化參數,λ1,λ2是平衡參數,盡管問題(2)使用了平方損失,但它可以被任何可微分損失函數代替.

2.2.2 利用全局和局部相關性

利用標簽相關性對多標簽學習至關重要,在這里,我們使用標簽相關性來規范模型.需要注意的是全局和局部相關性可以共存,本節,引入標簽流形正則化項來兼顧考慮二者.全局流形正則化項的基本思想是從實例級流形正則化項[29]中改進而來.具體而言,兩個標簽越正相關,相應分類器輸出越接近,反之亦然.

回想一下,對n 個示例的預測都存儲在l ×n 的矩陣F0中,其第i 行 fi,:包含第i 個標簽的預測.如果第i 個和第j 個標簽更具正相關性,則 fi,:應 該更加相似于 fj,:,反之亦然.類似于實例級流形正則化項[29,30],標簽流形正則項被定義為：

其中,S0是l ×l 的全局標簽相關矩陣.如果標簽i 和j是正相關的,那么 [ S0]i,j也是正數.通過最小化式(3),將變小.令 D0為 對角線S01的對角矩陣,其中1 是1 的向量表示.在式(3)中,流行正則化項可以等價寫成t r(F0TL0F0)[31],其中L0=D0-S0是 S0的 l ×l 標簽拉普拉斯矩陣.

由于局部之間的標簽相關性可能不同,因此我們引入局部流形正則化式.假設數據集X 被分為g 個組其 中Xm∈Rd×nm具 有nm個 示 例.令Ym為Y 對應于 Xm的標簽子矩陣,Sm∈Rl×l為組m 的局部標簽相關矩陣,與全局標簽相關性相似,我們支持分類器輸出正(負)相關標簽上相似(或不相似),并最小t r(FmTLmFm),其中 Lm是Sm的拉普拉斯矩陣,Fm=UWTXm是組m 的分類器輸出矩陣.對于問題(2)加入全局和局部標簽流形正則化式后,得到以下優化后的：

其中,λ1,λ2,λ3,λ4是平衡參數.

標簽流形正則化之所以能兼顧二者或者說促進作用是因為全局標簽相關性用拉普拉斯矩陣 L0編碼,局部標簽相關性用 Lm編碼,直觀來說,一個大的局部組對全局標簽相關性的∑貢獻更大,特別的,當使用余弦相似度計算 Sij時 ,通常,當全局標簽相關矩陣是局部標簽相關矩陣的線性組合時,相應的全局標簽拉普拉斯矩陣也是具有相同組合系數的局部標簽拉普拉斯矩陣的線性組合.綜上所述,問題(4)可以被重寫為：

2.2.3 學習標簽相關性

標簽流形正則化成功是取決于好的標簽相關矩陣(或等價于一個好的拉普拉斯矩陣),在多標簽學習中,一種基本的方法是用余弦距離計算兩個標簽之間的相關系數[32].但是,由于某些標簽在訓練數據中可能只有極少數正示例,因此估計值可能會很嘈雜.當標簽可能丟失時,這個估計值甚至會引起很大的誤差,因為觀察到的標簽分布可能與真實的標簽分布有很大不同.在本算法中,沒有直接指定任何相關度量或標簽相關矩陣,而是直接學習拉普拉斯矩陣,這樣省去了在關聯矩陣中進行普通且困難的人工分辨.需要注意的是,拉普拉斯矩陣是對稱正定的,因此,對于m∈{1,···,g},我們將Lm分 解為ZmZmT,其中Zm∈Rl×k.為了簡單起見,將k設置為潛在表示V的維度.因此,學習拉普拉斯矩陣轉換為學習注意,優化關于Zm可能會導致平凡解Zm=0.為了避免這種情況,我們添加約束條件,即每個對角線元素ZmZmT為1,這也使我們能夠獲得Lm的歸一化拉普拉斯矩陣[33].

2.2.4 通過交替最小化進行優化學習

問題(6)可以通過交替最小化來解決.這使得我們能夠迭代的調整變量以找到滿意的解決方案.在每次迭代中,我們用梯度下降來更新 {Z,U,V,W}中的一個變量,并固定其他變量.整個優化問題進而簡化為幾個簡單的子問題.具體來說,MANOPT 工具箱[34]被用來在歐幾里得空間上用線搜索實現梯度下降以更新U,V,W以及更新Z的流形,詳細更新過程將在下面討論.

2.2.4.1 更新Zm

隨著U,V,W的被固定,式(6)變為

由于約束diag(ZmZmT)=1,它沒有閉式解,我們用投影的梯度下降來解決它,關于Zm的梯度為為了滿足約束條件diag(ZmZmT)=1,每次更新后我們將Zm的每一行投影到單位標準球上：

2.2.4.2 更新V

隨著Zm,U,W的被固定,式(6)變為：

注意,V的列彼此獨立,因此可以逐列得到V.設ji和vi分別為j和v的第i列,vi的優化問題可以寫為：

設置梯度關于vi到0,我們得到以下vi閉式解：vi=(UTdiag(ji)U+(λ+λ2)I)-1(λWTxi+UTdiag(ji)yi).這里涉及為每個i計算逆矩陣,如果計算代價很大,我們可以在式(8)上執行梯度下降,在式(8)上,關于V的梯度下降為：?v=UT(J°(UV-Y))+λ(V-WTX)+λ2V.

2.2.4.3 更新U

隨著Zm,V,W的被固定,式(6)變為：

我們再一次利用梯度下降,關于U的梯度為：

2.2.4.4 更新W

隨著Zm,U,V的被固定,式(6)變為：

關于W的梯度為：

MIMLSVM 算法是針對多示例多標記框架設計的算法,在基于構造性聚類將每一個包轉化為一個示例之后就變成了單示例多標記問題,GLOCAL 算法針對的是單示例多標簽的分類問題,因此可以使用GLOCAL算法對原來的MIMLSVM 算法進行改進,替代原來的MLSVM 算法得到MIMLSVM-GLOCAL 算法,像前文提到的那樣,GLOCAL 算法并沒有僅僅從局部或者全局一方面出發,而是兩者都考慮在內去解決相關問題,并且也可以在標簽缺失的情況下去解決問題.MIMLSVMGLOCAL 的算法描述如表1所示.

表1 MIMLSVM-GLOCAL 算法

3 實驗

為了檢驗MIMLSVM-GLOCAL 算法的分類效果,將MIMLSVM-GLOCAL 算法和其他的多示例多標記算法MIMLBOOST、MIMLSVM、MIMLSVM+進行了比較.MIMLBOOST 算法以多示例為橋梁,首先將多示例多標簽樣本轉化為多示例單標簽樣本,然后使用多示例學習中的MIBOOSTING 算法對轉化后的問題進行求解.MIMLSVM 算法則是以多標簽為橋梁,首先利用聚類將多示例多標簽問題轉化為多標簽問題,再借助于多標簽學習中的MLSVM 算法進行求解.MIMLSVM+算法利用退化策略,將多示例轉化成單示例,再把多標簽分解成一系列的兩類分類問題.實驗中使用的SVM均使用高斯核函數,MIMLBOOST、MIMLSVM 算法中的參數根據文獻[3]中的實驗設置為最優,MIMLSVM+算法中的參數根據文獻[1]中的實驗設置為最優,GLOCAL算法根據文獻[28]中的實驗設置為最優.

這里我們使用周志華等人提供的圖像樣本集[3]和文本樣本集[19]進行實驗.實驗中的算法均使用相同的樣本集和測試集,均采用10 折交叉驗證.其中圖像樣本集由2000 個自然場景圖片構成,分為5 個類別,分別是沙漠、山、海、日落和樹.屬于一個以上的類(如山+日落)的樣本的數目約占數據集的22%左右,許多組合類(如山+海+樹)約占0.75%左右,單個標簽的樣本數目約約占77%左右.平均來說,每個樣本都與大約1.24 個類標簽相關聯,如表2所示.

表2 場景樣本集數據特征

每張圖片通過SBN 方法用包含9 個示例、每個示例為15 維的特征向量的示例包來表示.文本數據集來自Reuters 數據集,此樣本集被廣泛利用,包含7 個類別的2000 個文本樣本,這2000 個樣本是由去除沒有標記和沒有正文的文本,再隨機去除一些只有一個類別標記的文本后得到的.具有多個標記的文本樣本約占15%,平均每個文本樣本具有1.15±0.37 個類別標記.通過使用滑動窗口[27]技術將每一篇文檔用一個包來表示,每個包中包含一組數量不等的特征向量,每個特征向量都是243 維的并且代表了這篇文檔的某個部分.本實驗采用10 折交叉驗證的方式,每次從2000 個數據集中隨機的抽取1500 個數據作為訓練集,其余的500 個數據作為測試集,重復10 次實驗之后求得實驗的平均值以及方差.本實驗中使用的場景樣本集和文本樣本集,其結構特征如表3所示.

對于評級指標,我們采用采用基本樣本的也是廣泛使用的hamming loss、one-error、coverage、ranking loss 和average precision[1]來衡量學習效果.簡單來說,對于hamming loss、one-error、coverage 和ranking loss的值越小說明算法效果越好；對于average precision的值越大說明算法效果越好.表4和表5分別顯示了MIMLBOOST、MIMLSVM、MIMLSVM+和MIMLSVMGLOCAL 算法在場景樣本集和文本樣本集上的分類效果.

從表4和表5的實驗結果可以看出,無論在場景樣本集還是文本樣本集,MIMLSVM-GLOCAL 算法的性能都要高于其他算法,取得了良好的性能,這主要得益于文章2.2 節所論述的優勢,此外,全局標簽流形提供有關標簽如何作為一個整體相關的信息,并幫助學習少數標簽,如果少數標簽與其他標簽正相關(相反,負相關),我們可以鼓勵其標簽分類器輸出與其他標簽

的輸出更相似(相反).局部標簽流形還允許標簽分類器的局部適應.拉普拉斯矩陣的學習發現了最適合全局和局部數據子集的標簽相關性,并避免了手動指定標簽相關性的常見任務和困難任務.從總體上看,MIMLSVM、MIMLBOOST、MIMLSVM+和MIMLSVM-GLOCAL 在文本樣本集上分類的各項指標明顯優于場景樣本集,這可能與樣本集內部的結構有一定的關系,文本樣本集示例的維數遠遠多于場景樣本集,文本樣本集可以更加準確的來表示對象,因此造成了兩個樣本集上的結果差異較大.

表3 文本樣本集和場景樣本集特征

表4 場景樣本集實驗結果

表5 文本樣本集實驗結果

4 結束語

多示例多標記框架下的MIMLSVM 算法已經取得了不錯的分類效果,針對其第二步中由于忽略標簽相關性而導致信息丟失的問題在之前也提出了一些解決方案,但都考慮的不周全,與以前的工作相比,本文將一種既考慮到全局又考慮到局部標簽相關性的GLOCAL 算法融入到了MIMLSVM 算法中,整體提升了算法的性能,提高了分類準確率,取得了良好的實驗效果.