金亞洲,張正軍,顏?zhàn)雍?王雅萍

(南京理工大學(xué) 理學(xué)院,南京 210094)

0 概述

目前,針對(duì)多標(biāo)記學(xué)習(xí)分類問(wèn)題的多標(biāo)記學(xué)習(xí)算法可大致分為問(wèn)題轉(zhuǎn)換方法和算法適應(yīng)方法2類[5-6]。問(wèn)題轉(zhuǎn)換方法解決此類問(wèn)題的思想是對(duì)多標(biāo)記學(xué)習(xí)訓(xùn)練樣本數(shù)據(jù)進(jìn)行處理,將該問(wèn)題轉(zhuǎn)化為已知的學(xué)習(xí)問(wèn)題,例如一個(gè)或多個(gè)單標(biāo)記問(wèn)題或者回歸問(wèn)題。算法適應(yīng)方法解決此類問(wèn)題的思想是對(duì)已有的傳統(tǒng)監(jiān)督學(xué)習(xí)算法進(jìn)行改進(jìn)或擴(kuò)展,使其能夠適應(yīng)多標(biāo)記數(shù)據(jù)的學(xué)習(xí)。

在問(wèn)題轉(zhuǎn)化方法的研究中,BR(Binary Relevance)算法[3]較簡(jiǎn)單,該算法將多標(biāo)記學(xué)習(xí)問(wèn)題轉(zhuǎn)化為若干個(gè)獨(dú)立的二分類問(wèn)題,其計(jì)算復(fù)雜度較低,但由于忽略了標(biāo)記之間內(nèi)在的相關(guān)信息,因此泛化性能較差。分類器鏈(Classifier Chain,CC)算法[7-8]在BR算法的基礎(chǔ)上,將獨(dú)立的二分類器進(jìn)行串聯(lián)形成一條鏈,該算法考慮了標(biāo)記之間的相關(guān)性等信息,但鏈表順序直接影響最終的分類效果,且其考慮的相關(guān)性信息有時(shí)并不符合樣本數(shù)據(jù)的標(biāo)記本質(zhì)相關(guān)性信息,文獻(xiàn)[7]利用CC算法的集成框架ECC來(lái)緩解由隨機(jī)確定鏈表順序帶來(lái)的不利影響。LP(Label Power-set)算法[9]是一種標(biāo)記組合算法,其基本思想是將多標(biāo)記數(shù)據(jù)集中每個(gè)唯一的標(biāo)記集合均作為一個(gè)整體標(biāo)記,訓(xùn)練和預(yù)測(cè)過(guò)程中的輸入和預(yù)測(cè)輸出均為一個(gè)整體標(biāo)記,多標(biāo)記學(xué)習(xí)問(wèn)題即被轉(zhuǎn)化為一個(gè)單標(biāo)記多分類問(wèn)題。但是,當(dāng)標(biāo)記空間較大時(shí),LP算法的訓(xùn)練樣本數(shù)據(jù)中標(biāo)記集合對(duì)應(yīng)的示例數(shù)量較少,會(huì)引起類不平衡問(wèn)題,進(jìn)而影響分類效果。

在算法適應(yīng)方法的研究中,Rank-SVM算法[10-11]通過(guò)對(duì)傳統(tǒng)的SVM算法[12]進(jìn)行擴(kuò)展,采用最大化間隔策略,通過(guò)一組線性分類器來(lái)最小化排序損失評(píng)價(jià)指標(biāo),并引入“核技巧”來(lái)處理非線性多標(biāo)記問(wèn)題。BP-MLL(Back-Propagation Multi-Label Learning)算法[13-14]基于經(jīng)典的反向傳播(Back-Propagation,BP)算法,通過(guò)采用一種新的誤差函數(shù)從而適應(yīng)于多標(biāo)記問(wèn)題,并使用梯度下降法更新網(wǎng)絡(luò)中的參數(shù)。ML-KNN方法[15-16]基于傳統(tǒng)的KNN方法,根據(jù)測(cè)試集中每個(gè)示例與訓(xùn)練集樣本的相似度來(lái)確定其K個(gè)近鄰,并通過(guò)最大后驗(yàn)概率(MAP)原理來(lái)預(yù)測(cè)樣本的標(biāo)記集合。

本文基于間隔準(zhǔn)則提出2種優(yōu)化的多標(biāo)記學(xué)習(xí)算法,兩者均可歸納為算法適應(yīng)方法。第1種算法通過(guò)優(yōu)化模型在相關(guān)標(biāo)記集合中最小輸出與不相關(guān)標(biāo)記集合中最大輸出的間隔損失來(lái)進(jìn)行標(biāo)記排序?？紤]到該算法對(duì)標(biāo)記信息利用不足的問(wèn)題,第2種算法不僅優(yōu)化上述間隔損失,同時(shí)還優(yōu)化模型在相關(guān)標(biāo)記集合中平均輸出與不相關(guān)標(biāo)記集合中最大輸出的間隔損失,以及優(yōu)化模型在相關(guān)標(biāo)記集合中最小輸出與不相關(guān)標(biāo)記集合中平均輸出的間隔損失,從而進(jìn)行標(biāo)記排序。上述2種算法均采用改進(jìn)的次梯度Pegasos算法[17-18]進(jìn)行參數(shù)學(xué)習(xí),以提高分類效果。

1 相關(guān)工作

1.1 間隔準(zhǔn)則

本文算法以基于間隔準(zhǔn)則的多分類算法[19-20]為基礎(chǔ)。在多分類算法中,令L={(x1,y1),(xn,yn)}表示訓(xùn)練集,其中,yi屬于有限數(shù)目的類別集合,該算法的目標(biāo)為最小化正則化經(jīng)驗(yàn)風(fēng)險(xiǎn)損失,即:

(1)

(2)

其中,Ω(·)為正則項(xiàng),其是一個(gè)單調(diào)增凸函數(shù),L(·)用于計(jì)算模型在訓(xùn)練樣本數(shù)據(jù)上的經(jīng)驗(yàn)風(fēng)險(xiǎn),λ為平衡參數(shù),用于平衡模型正則項(xiàng)與經(jīng)驗(yàn)損失對(duì)目標(biāo)函數(shù)的影響。多分類支持向量機(jī)(multiclass-SVM)利用模型參數(shù)的L2范數(shù)作為正則項(xiàng),即:

(3)

在經(jīng)驗(yàn)損失設(shè)置上,損失函數(shù)l(xi,yi,w)被設(shè)置為鉸鏈損失,即:

(4)

其中,Φ(·,·)為一個(gè)映射函數(shù),其將每一個(gè)示例-標(biāo)記對(duì)(x,y)映射為:

(5)

其中,Ι(·)為指示函數(shù)。在multiclass-SVM中引入松弛變量ξi,式(1)最小化問(wèn)題可以轉(zhuǎn)化為:

s.t.

?(xi,yi)∈L

ξi≥0

(6)

1.2 Pegasos算法

傳統(tǒng)二分類支持向量機(jī)問(wèn)題的學(xué)習(xí)任務(wù)均被轉(zhuǎn)化為有約束的二次規(guī)劃問(wèn)題,該問(wèn)題的最初形式為無(wú)約束、帶有懲罰項(xiàng)的經(jīng)驗(yàn)損失最小化問(wèn)題,且損失函數(shù)通常選擇鉸鏈損失,可用如下的優(yōu)化模型表示:

(7)

l(w;(xi,yi))=max(0,1-yi〈w,xi〉)

(8)

其中,〈w,xi〉表示向量w和xi的內(nèi)積。

Pegasos算法是隨機(jī)梯度下降方法在解決上述問(wèn)題時(shí)的一個(gè)應(yīng)用,該算法不需要轉(zhuǎn)化為對(duì)偶形式進(jìn)行求解,直接在原始的目標(biāo)函數(shù)上通過(guò)選取合適的步長(zhǎng)并采用隨機(jī)梯度下降方法對(duì)參數(shù)進(jìn)行學(xué)習(xí)。Pegasos算法主要分為梯度下降和投影2個(gè)階段,其主要思想如下:

在模型參數(shù)的初始值設(shè)置時(shí),令w1=0,設(shè)置迭代輪數(shù)為T,在Pegasos算法的每輪迭代t中,隨機(jī)選取一個(gè)訓(xùn)練樣本(xit,yit),將選取的訓(xùn)練樣本近似代替式(7)所表示的目標(biāo)函數(shù),如下:

(9)

上述近似目標(biāo)函數(shù)的次梯度可用下式表示:

(10)

其中,I[yit·〈wt,xit〉<1]為指示函數(shù)。更新wt+1/2←wt-ηtt,步長(zhǎng)ηt=1/(λt),更新后的模型參數(shù)可表示如下:

(11)

投影階段的模型參數(shù)更新可以表示為:

(12)

當(dāng)?shù)啍?shù)達(dá)到T時(shí),wT+1即為學(xué)習(xí)到的模型參數(shù)。

2 優(yōu)化排序多標(biāo)記學(xué)習(xí)算法

2.1 最小輸出與最大輸出間的間隔優(yōu)化

s.t.

ξi≥0,?i∈{1,2,…,N}

(13)

在上述優(yōu)化問(wèn)題中,目標(biāo)函數(shù)的第一項(xiàng)為正則項(xiàng)約束,用以衡量模型的復(fù)雜度,第二項(xiàng)為損失函數(shù),衡量模型在不滿足約束條件時(shí)的經(jīng)驗(yàn)損失。約束條件度量了每個(gè)示例對(duì)象相關(guān)標(biāo)記集合中最小輸出與不相關(guān)標(biāo)記集合中最大輸出的間隔。

式(13)優(yōu)化問(wèn)題在本文中通過(guò)改進(jìn)的次梯度Pegasos算法來(lái)解決,可通過(guò)梯度下降與投影2個(gè)階段實(shí)現(xiàn)。在每輪迭代中,隨機(jī)從訓(xùn)練數(shù)據(jù)集中抽取一個(gè)樣本,判斷該樣本是否滿足式(14):

(14)

(15)

根據(jù)梯度下降策略,模型參數(shù)的更新為:

(16)

(17)

在模型的預(yù)測(cè)階段,給定未知示例對(duì)象x,模型預(yù)測(cè)出的標(biāo)記集合為:

h(x)=sign(f1(x)-t(x),f2(x)-t(x),…,fq(x)-t(x))

(18)

其中,t(x)為閾值函數(shù),本文通過(guò)文獻(xiàn)[10]算法,即學(xué)習(xí)一個(gè)線性回歸函數(shù)來(lái)計(jì)算t(x)。

優(yōu)化最小輸出與最大輸出的間隔損失的多標(biāo)記學(xué)習(xí)算法具體步驟如下:

輸入訓(xùn)練數(shù)據(jù)集D,平衡參數(shù)λ,迭代終止次數(shù)T或迭代終止條件ε

輸出學(xué)習(xí)到的參數(shù)w

步驟2隨機(jī)從訓(xùn)練集中抽取一個(gè)樣本,檢測(cè)該樣本是否滿足式(14)約束條件。

步驟3若不滿足約束條件,則根據(jù)式(16)和式(17)更新w;否則,根據(jù)式(19)和式(17)更新w。

wt+1/2=(1-ηtλ)wt

(19)

步驟4重復(fù)步驟2和步驟3,直到滿足判定條件‖w‖F(xiàn)≤ε或迭代次數(shù)大于T,終止迭代計(jì)算并輸出w。

2.2 改進(jìn)的優(yōu)化排序多標(biāo)記學(xué)習(xí)算法

本文2.1節(jié)算法只考慮優(yōu)化示例對(duì)象相關(guān)標(biāo)記集合最小輸出與不相關(guān)標(biāo)記集合最大輸出之間的間隔,該間隔也即距離分界面最近的標(biāo)記輸出之間的差異。然而,上述算法對(duì)示例所擁有的全部標(biāo)記信息利用不足,同時(shí)易出現(xiàn)過(guò)擬合現(xiàn)象,因此,本節(jié)對(duì)該算法進(jìn)行改進(jìn),改進(jìn)算法不僅優(yōu)化上述間隔,同時(shí)優(yōu)化模型在示例相關(guān)標(biāo)記集合中的平均輸出與不相關(guān)標(biāo)記集合中最大輸出之間的間隔,以及優(yōu)化模型在示例相關(guān)標(biāo)記集合中的最小輸出與不相關(guān)標(biāo)記集合中的平均輸出之間的間隔。在上述模型的基礎(chǔ)上,再引入2個(gè)松弛變量ξ′={ξ′1,ξ′2,…,ξ′N}和υ′={υ′1,υ′2,…,υ′N}用來(lái)表示示例對(duì)象沒(méi)有滿足上述間隔要求所產(chǎn)生的損失,則改進(jìn)模型所求解的優(yōu)化問(wèn)題為:

s.t.

ξi≥0,ξ′i≥0,υ′i≥0,?i∈{1,2,…,N}

(20)

從上述優(yōu)化問(wèn)題可以看出,當(dāng)約束條件第一項(xiàng)成立時(shí),第二項(xiàng)與第三項(xiàng)顯然成立;當(dāng)約束條件第一項(xiàng)不成立時(shí),第二項(xiàng)與第三項(xiàng)存在成立的可能性,且在算法優(yōu)化過(guò)程中的初始階段,可以對(duì)全部標(biāo)記所對(duì)應(yīng)的模型參數(shù)進(jìn)行更新,加快收斂速度。隨著迭代次數(shù)的增加,約束條件第二項(xiàng)及第三項(xiàng)在模型參數(shù)更新過(guò)程中所起的作用越來(lái)越小甚至不起作用,同時(shí)第二項(xiàng)及第三項(xiàng)約束條件可以緩和過(guò)擬合現(xiàn)象,該優(yōu)化問(wèn)題的求解同樣采用改進(jìn)的次梯度Pegasos算法。

2.3 算法分析

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)設(shè)置

為了驗(yàn)證本文算法的有效性,使用來(lái)自開(kāi)源項(xiàng)目Mulan[22]所提供的4個(gè)數(shù)據(jù)集,其中,emotions來(lái)自于音樂(lè)情感分類領(lǐng)域,image與scene來(lái)自于自然場(chǎng)景分類領(lǐng)域,langlog來(lái)自于文本分類領(lǐng)域。數(shù)據(jù)集的統(tǒng)計(jì)信息如表1所示。

表1 實(shí)驗(yàn)數(shù)據(jù)集信息

在多標(biāo)記學(xué)習(xí)問(wèn)題中,常用的評(píng)價(jià)指標(biāo)為海明損失(Hamming Loss,HL)、排序損失(Ranking Loss,RL)、最前端錯(cuò)誤率(One-Error,OE)、覆蓋率(Coverage rate,CV)和平均準(zhǔn)確率(Average Precision,AP)。各指標(biāo)具體如下:

1)HL指標(biāo)考察樣本在單個(gè)標(biāo)記上的誤分類情況,即對(duì)某個(gè)示例對(duì)象而言,不相關(guān)的標(biāo)記被預(yù)測(cè)為相關(guān)或相關(guān)的標(biāo)記被預(yù)測(cè)為不相關(guān)的情況。HL計(jì)算如下:

(21)

2)RL指標(biāo)考察在樣本的語(yǔ)義標(biāo)記排序序列中出現(xiàn)排序錯(cuò)誤的情況。RL計(jì)算如下:

(22)

3)OE指標(biāo)考察在樣本的語(yǔ)義標(biāo)記排序序列中,序列最前端的標(biāo)記不屬于樣本相關(guān)標(biāo)記集合的情況。OE計(jì)算如下:

(23)

4)CV指標(biāo)考察在樣本的語(yǔ)義標(biāo)記排序序列中,覆蓋隸屬于樣本的所有相關(guān)標(biāo)記所需的搜索深度。CV計(jì)算如下:

(24)

5)AP指標(biāo)考察在樣本的語(yǔ)義標(biāo)記排序序列中,排在隸屬于該樣本的相關(guān)標(biāo)記之前的標(biāo)記仍屬于樣本相關(guān)標(biāo)記集合的情況。AP計(jì)算如下:

(25)

在分類器效果評(píng)估中,HL、RL、OE和CV 4個(gè)評(píng)價(jià)指標(biāo)的指標(biāo)值越小,則算法性能越優(yōu),AP評(píng)價(jià)指標(biāo)的指標(biāo)值越大,則算法性能越優(yōu)。

3.2 結(jié)果分析

本文將提出的第1種算法表示為Proposed1,第2種算法表示為Proposed2,平衡參數(shù)λ的取值范圍為{0.001,0.01,0.1,1,10,100},將本文2種算法與現(xiàn)有的多標(biāo)記學(xué)習(xí)算法ML-RBF[23]、BP-MLL[13]和ML-KNN[15]進(jìn)行對(duì)比,實(shí)驗(yàn)結(jié)果如表2～表6所示,其中,結(jié)果均為3次交叉驗(yàn)證后的均值,以排除隨機(jī)性,最優(yōu)結(jié)果加粗表示。

表2 海明損失結(jié)果對(duì)比

表3 排序損失結(jié)果對(duì)比

表4 最前端錯(cuò)誤率結(jié)果對(duì)比

表5 覆蓋率結(jié)果對(duì)比

表6 平均準(zhǔn)確率結(jié)果對(duì)比

從表2～表6可以看出,在4個(gè)多標(biāo)記數(shù)據(jù)集中,本文提出的2種算法的5個(gè)評(píng)價(jià)指標(biāo)均取得了較好的效果,與3種多標(biāo)記學(xué)習(xí)算法相比,評(píng)價(jià)指標(biāo)結(jié)果接近,表明本文2種算法可以實(shí)現(xiàn)多標(biāo)記分類。實(shí)驗(yàn)結(jié)果也表明,考慮相關(guān)標(biāo)記集合的平均輸出與不相關(guān)標(biāo)記集合的平均輸出,即本文第2種算法在5種評(píng)價(jià)指標(biāo)表現(xiàn)上均優(yōu)于本文第1種算法,表明考慮平均輸出的算法能夠提升基于間隔準(zhǔn)則的分類器性能。

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

受基于間隔準(zhǔn)則的多分類支持向量機(jī)的啟發(fā),本文通過(guò)優(yōu)化示例相關(guān)標(biāo)記集合中最小輸出與不相關(guān)標(biāo)記集合中最大輸出的間隔損失,以實(shí)現(xiàn)示例對(duì)應(yīng)的標(biāo)記集合排序。為了在模型參數(shù)訓(xùn)練過(guò)程中充分利用標(biāo)記空間的全部標(biāo)記信息,進(jìn)一步優(yōu)化示例相關(guān)標(biāo)記集合平均輸出與不相關(guān)標(biāo)記集合中最大輸出的間隔損失,以及示例相關(guān)標(biāo)記集合中最小輸出與不相關(guān)標(biāo)記集合中平均輸出的間隔損失。實(shí)驗(yàn)結(jié)果表明,與ML-RBF、BP-MLL和ML-KNN多標(biāo)記學(xué)習(xí)算法相比,本文提出的2種算法在4個(gè)多標(biāo)記數(shù)據(jù)集上均取得了相近的分類性能。本文假設(shè)訓(xùn)練樣本與標(biāo)記之間呈線性關(guān)系,且算法未考慮標(biāo)記之間存在的相關(guān)性,下一步考慮將特征空間擴(kuò)展到再生核希爾伯特空間中進(jìn)行學(xué)習(xí),并結(jié)合標(biāo)記之間的相關(guān)性來(lái)提高分類效果。