李村合,張振凱

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

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

為了解決上述問題,多示例多標(biāo)簽[2,3]框架應(yīng)運(yùn)而生.在該框架下一個(gè)對(duì)象用一組示例來表示,并且和一組類別標(biāo)記相關(guān)聯(lián).比如一篇文章中的每個(gè)部分可以用一個(gè)示例來表示,而這篇文章可能同時(shí)屬于“娛樂”、“旅游”、“經(jīng)濟(jì)”等不同的類別.多示例多標(biāo)簽已成功應(yīng)用到了場(chǎng)景分類、基因功能注釋、圖像標(biāo)注等領(lǐng)域,彰顯了其強(qiáng)大的學(xué)習(xí)能力和潛力.

支持向量機(jī)(Support Vector Machines,SVM)[4]是一種高效的分類識(shí)別方法,在解決高維模式識(shí)別問題呈現(xiàn)出其獨(dú)特的優(yōu)勢(shì).它通過尋找一個(gè)最優(yōu)分類超平面來實(shí)現(xiàn)分類.支持向量機(jī)以統(tǒng)計(jì)學(xué)習(xí)理論中的VC 維(Vapnik-Chervonenkis Dimension)理論[5]以及結(jié)構(gòu)風(fēng)險(xiǎn)最小原理為基礎(chǔ),最終的決策函數(shù)由少量支持向量決定,其數(shù)學(xué)形式簡(jiǎn)單,同時(shí)有效克服樣本空間的高維性帶來的計(jì)算復(fù)雜問題,已經(jīng)在系統(tǒng)辨識(shí)、人臉檢測(cè)及生物信息等領(lǐng)域中被用到.多示例多標(biāo)記框架下的許多算法或直接使用了SVM 或?qū)ζ涓脑焓蛊溥m應(yīng)多示例多標(biāo)記的學(xué)習(xí),這些算法在學(xué)習(xí)過程中已經(jīng)取得了不錯(cuò)的分類效果.在真實(shí)的學(xué)習(xí)問題中,標(biāo)記之間通常具有局部標(biāo)記相關(guān)性及全局相關(guān)性,如果僅僅考慮其一有可能會(huì)影響到實(shí)驗(yàn)分類的準(zhǔn)確率,因此如何兼顧考慮二者是能否取得良好實(shí)驗(yàn)效果的關(guān)鍵.

本文的整體組織結(jié)構(gòu)如下：第1 部分介紹相關(guān)工作,第2 部分提出改進(jìn)的算法,第3 部分給出了實(shí)驗(yàn)及結(jié)果,最后進(jìn)行了總結(jié).

1 相關(guān)工作

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

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

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

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

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

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

2 MIMLSVM 算法及改進(jìn)算法

2.1 MIMLSVM 算法

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

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

2.2 MIMLSVM 算法的改進(jìn)算法

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

2.2.1 基本模型

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

具體來說,我們使用：

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

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

2.2.2 利用全局和局部相關(guān)性

利用標(biāo)簽相關(guān)性對(duì)多標(biāo)簽學(xué)習(xí)至關(guān)重要,在這里,我們使用標(biāo)簽相關(guān)性來規(guī)范模型.需要注意的是全局和局部相關(guān)性可以共存,本節(jié),引入標(biāo)簽流形正則化項(xiàng)來兼顧考慮二者.全局流形正則化項(xiàng)的基本思想是從實(shí)例級(jí)流形正則化項(xiàng)[29]中改進(jìn)而來.具體而言,兩個(gè)標(biāo)簽越正相關(guān),相應(yīng)分類器輸出越接近,反之亦然.

回想一下,對(duì)n 個(gè)示例的預(yù)測(cè)都存儲(chǔ)在l ×n 的矩陣F0中,其第i 行 fi,:包含第i 個(gè)標(biāo)簽的預(yù)測(cè).如果第i 個(gè)和第j 個(gè)標(biāo)簽更具正相關(guān)性,則 fi,:應(yīng) 該更加相似于 fj,:,反之亦然.類似于實(shí)例級(jí)流形正則化項(xiàng)[29,30],標(biāo)簽流形正則項(xiàng)被定義為：

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

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

其中,λ1,λ2,λ3,λ4是平衡參數(shù).

標(biāo)簽流形正則化之所以能兼顧二者或者說促進(jìn)作用是因?yàn)槿謽?biāo)簽相關(guān)性用拉普拉斯矩陣 L0編碼,局部標(biāo)簽相關(guān)性用 Lm編碼,直觀來說,一個(gè)大的局部組對(duì)全局標(biāo)簽相關(guān)性的∑貢獻(xiàn)更大,特別的,當(dāng)使用余弦相似度計(jì)算 Sij時(shí) ,通常,當(dāng)全局標(biāo)簽相關(guān)矩陣是局部標(biāo)簽相關(guān)矩陣的線性組合時(shí),相應(yīng)的全局標(biāo)簽拉普拉斯矩陣也是具有相同組合系數(shù)的局部標(biāo)簽拉普拉斯矩陣的線性組合.綜上所述,問題(4)可以被重寫為：

2.2.3 學(xué)習(xí)標(biāo)簽相關(guān)性

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

2.2.4 通過交替最小化進(jìn)行優(yōu)化學(xué)習(xí)

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

2.2.4.1 更新Zm

隨著U,V,W的被固定,式(6)變?yōu)?/p>

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

2.2.4.2 更新V

隨著Zm,U,W的被固定,式(6)變?yōu)椋?/p>

注意,V的列彼此獨(dú)立,因此可以逐列得到V.設(shè)ji和vi分別為j和v的第i列,vi的優(yōu)化問題可以寫為：

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

2.2.4.3 更新U

隨著Zm,V,W的被固定,式(6)變?yōu)椋?/p>

我們?cè)僖淮卫锰荻认陆?關(guān)于U的梯度為：

2.2.4.4 更新W

隨著Zm,U,V的被固定,式(6)變?yōu)椋?/p>

關(guān)于W的梯度為：

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

表1 MIMLSVM-GLOCAL 算法

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

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

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

表2 場(chǎng)景樣本集數(shù)據(jù)特征

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

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

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

的輸出更相似(相反).局部標(biāo)簽流形還允許標(biāo)簽分類器的局部適應(yīng).拉普拉斯矩陣的學(xué)習(xí)發(fā)現(xiàn)了最適合全局和局部數(shù)據(jù)子集的標(biāo)簽相關(guān)性,并避免了手動(dòng)指定標(biāo)簽相關(guān)性的常見任務(wù)和困難任務(wù).從總體上看,MIMLSVM、MIMLBOOST、MIMLSVM+和MIMLSVM-GLOCAL 在文本樣本集上分類的各項(xiàng)指標(biāo)明顯優(yōu)于場(chǎng)景樣本集,這可能與樣本集內(nèi)部的結(jié)構(gòu)有一定的關(guān)系,文本樣本集示例的維數(shù)遠(yuǎn)遠(yuǎn)多于場(chǎng)景樣本集,文本樣本集可以更加準(zhǔn)確的來表示對(duì)象,因此造成了兩個(gè)樣本集上的結(jié)果差異較大.

表3 文本樣本集和場(chǎng)景樣本集特征

表4 場(chǎng)景樣本集實(shí)驗(yàn)結(jié)果

表5 文本樣本集實(shí)驗(yàn)結(jié)果

4 結(jié)束語

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