宋中山，周瑋瑜，孫翀，艾勇，劉越

(中南民族大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，湖北省制造企業(yè)智能管理工程技術(shù)研究中心，武漢 430074)

多標(biāo)記學(xué)習(xí)的概念源自文檔分類中的歧義性問題[1]，一個(gè)對象可關(guān)聯(lián)多個(gè)標(biāo)記.如一篇名為“David Beckham to face trial over speeding offense”的新聞，盡管它的新聞分類可同時(shí)屬于“體育”、“社會”，甚至“娛樂”，但用戶在搜索這條新聞時(shí)，會傾向于在“體育”類別下檢索，甚至一些新聞網(wǎng)站可能只會把它歸于“體育”類中.這說明在一個(gè)事物對應(yīng)的標(biāo)記集合中，每個(gè)標(biāo)記對這個(gè)事物描述的“程度”各異，標(biāo)記集合內(nèi)的每個(gè)標(biāo)記應(yīng)存在既定權(quán)重.若算法未同時(shí)考慮標(biāo)記間的序及權(quán)重，會影響預(yù)測的準(zhǔn)確性.本文針對以上問題，提出一種具有保序性的帶權(quán)多標(biāo)記學(xué)習(xí)算法WMLARP(Weighted Multi-label Learning Algorithm with Rank Preservation).WMLARP主要針對標(biāo)記間的相關(guān)性，分別從“相關(guān)-無關(guān)”、“相關(guān)-相關(guān)”標(biāo)記對入手來考慮標(biāo)記間的序和權(quán)重.在“相關(guān)-無關(guān)”標(biāo)記對上計(jì)算標(biāo)記間的序關(guān)系，序關(guān)系是用來區(qū)分示例的相關(guān)標(biāo)記與無關(guān)標(biāo)記的，分別將標(biāo)記值帶入線性函數(shù)，函數(shù)值較大的對應(yīng)標(biāo)記即為相關(guān)標(biāo)記；在“相關(guān)-相關(guān)”標(biāo)記對上計(jì)算標(biāo)記間的權(quán)重關(guān)系，同樣都是示例的正確標(biāo)記，仍存在哪個(gè)標(biāo)記對示例的重要性程度更大的問題，因此，在兩個(gè)相關(guān)標(biāo)記間計(jì)算權(quán)重關(guān)系，決定輸出的標(biāo)記序列中各個(gè)標(biāo)記的位置.

多標(biāo)記學(xué)習(xí)的經(jīng)典算法主要分為兩類：數(shù)據(jù)轉(zhuǎn)換類算法和方法適應(yīng)類算法[2].前者將問題從多標(biāo)記轉(zhuǎn)換為多個(gè)單標(biāo)記，以已有的單標(biāo)記算法學(xué)習(xí).BR(Binary Relevance)算法[3]是典型的數(shù)據(jù)轉(zhuǎn)換類算法，因其將多標(biāo)記問題分解為多個(gè)獨(dú)立的單標(biāo)記問題求解，忽略了標(biāo)記間的相關(guān)性.LP(Label Powerset)算法[4]考慮了標(biāo)記間的序，將標(biāo)記集合內(nèi)的標(biāo)記兩兩一組作為一個(gè)新的標(biāo)記，模型的輸出為每個(gè)標(biāo)記組合的概率值；在此基礎(chǔ)上改進(jìn)的RAkEL(Randomk-labelsets)算法[5]、PPT(Pruned Problem Transformation)算法[6]、CLR(Calibrated Label Ranking)算法[7]均計(jì)算了標(biāo)記間的序.適應(yīng)類算法則將單標(biāo)記算法改進(jìn)適應(yīng)到多標(biāo)記問題，Adaboost.MH、Adaboost.MR算法[8]是在Adaboost[9]上進(jìn)行擴(kuò)展的兩種算法，可最小化漢明及排序損失.基于SVM的多標(biāo)記算法[10]將訓(xùn)練集中每個(gè)標(biāo)記看作SVM分類器；概率生成模型[11]是在訓(xùn)練集中為每個(gè)標(biāo)記生成不同的詞，那么標(biāo)記集合元素便由其標(biāo)記所生成的混合詞來產(chǎn)生，并對每個(gè)混合詞組中的詞分布進(jìn)行學(xué)習(xí).另一個(gè)發(fā)展方向是考慮標(biāo)記間的權(quán)重大小，CHEN等人[12]提出了基于BR的優(yōu)化算法，通過在BR中加入拷貝和選擇，考慮標(biāo)記的概率因素.CHASE算法[13]通常用于不完整的數(shù)據(jù)集上，將其轉(zhuǎn)換為基于概率的數(shù)據(jù)集，各個(gè)標(biāo)記被賦予一組概率值作為權(quán)重.多媒體領(lǐng)域中通常會涉及到給標(biāo)記賦予權(quán)重的過程，例如，JIANG等人[14]將每個(gè)樂器標(biāo)記賦予了不同的權(quán)重，即可判別給定的音樂中有哪些演奏樂器.標(biāo)記間的相關(guān)性對模型質(zhì)量的影響尤為關(guān)鍵，若未充分挖掘標(biāo)記間的序與權(quán)重，會使算法應(yīng)用受限.因此，本文提出了一種具有保序性的帶權(quán)多標(biāo)記學(xué)習(xí)算法WMLARP，分別在兩種類型的標(biāo)記對上挖掘標(biāo)記間的關(guān)系，可有效提高生成模型的質(zhì)量.

1 問題描述與形式化定義

WMLARP的目標(biāo)是從訓(xùn)練集中學(xué)習(xí)并輸出一組實(shí)數(shù)函數(shù)，可區(qū)分不同示例對應(yīng)的標(biāo)記集合，且輸出的結(jié)果綜合考慮了標(biāo)記間的序關(guān)系與權(quán)重大小.設(shè)d維示例空間：X=d，標(biāo)記集：y={1,…,Q}，樣本集D={(x1,Y1),(x2,Y2), …,(xm,Ym)}，其中，|D|=m，xiX，Yi2y，多標(biāo)記分類器h:X2y.

假定對D中任一樣本(xi,Yi)，Yi均服從y上的同一概率分布，存在函數(shù)fk=wk,x+bk，其中，ky.多標(biāo)記算法的目標(biāo)是從D中習(xí)得Q個(gè)決策函數(shù)fn(ny)，h=(f1,f2, …,fQ)，WMLARP對這一組決策函數(shù)的損失函數(shù)最小化來求得最優(yōu)解.

2 損失函數(shù)

定義1(相關(guān)-相關(guān))標(biāo)記對.對于某個(gè)示例，(相關(guān)-相關(guān))標(biāo)記對為兩個(gè)均與該示例相關(guān)的標(biāo)記組成的標(biāo)記對，即：對D中任意(xi,Yi)，標(biāo)記RYi，R′Yi，則這兩個(gè)標(biāo)記構(gòu)成的標(biāo)記對(R,R′)為(相關(guān)-相關(guān))標(biāo)記對，簡寫為：(R-R′).

2.1 標(biāo)記間序關(guān)系

對D中某一樣本(xi,Yi)，WMLARP訓(xùn)練一組決策函數(shù)f構(gòu)成分類器h，即：存在函數(shù)fk=wk,xi+bk，其中kYi，wkd為第k個(gè)標(biāo)記對應(yīng)的“權(quán)值向量”，bk為第k個(gè)標(biāo)記對應(yīng)的“偏置”.決策模型的損失函數(shù)取排序損失函數(shù)，該函數(shù)用于考察在樣本標(biāo)記集合的排序序列中出現(xiàn)排序錯誤的情況，損失函數(shù)R(f)公式為：

(1)

其中R(xi)={(y1,y2)|f(xi,y1)≤f(xi,y2),(y1,y2)

2.2 標(biāo)記間權(quán)重

對于D中樣本(xi,Yi)的任一標(biāo)記對(R-R′)，有fR(x)=wR,xi+bR，fR′(x)=wR′,xi+bR′.假設(shè)在有序標(biāo)記集Yi中，標(biāo)記R排在標(biāo)記R′的前面，那么標(biāo)記R的權(quán)重值應(yīng)大于標(biāo)記R′的權(quán)重值：WeightR>WeightR′.對于任意的xi，標(biāo)記R比R′更相關(guān)的概率值用權(quán)重概率PR,R′(f)來表示.設(shè)(R-R′)間的真實(shí)權(quán)重概率為則以交叉熵的形式定義權(quán)重概率的損失函數(shù)為：

PR,R′(f)).

(2)

3 模型學(xué)習(xí)

WMLARP算法分別對訓(xùn)練集每個(gè)樣本示例的(R-U)和(R-R′)進(jìn)行訓(xùn)練，在(R-U)上，定義超平面，根據(jù)樣本點(diǎn)到該平面上的距離關(guān)系構(gòu)建分類器，同時(shí)最小化排序損失；在(R-R′)上，定義標(biāo)記對的權(quán)重概率，計(jì)算大小以確定標(biāo)記集中標(biāo)記權(quán)重的排序.

3.1 (R-U)的線性分類問題求解

WMLARP在(R-U)上，定義超平面，根據(jù)樣本點(diǎn)(xi,Yi)到該平面上的距離關(guān)系構(gòu)建決策函數(shù)來區(qū)分xi的R與U，同時(shí)最小化排序損失，訓(xùn)練(xi,Yi)的線性分類模型的具體算法如算法1所述.

定義3(R-U)的決策邊界.將向量空間劃分為兩個(gè)集合，決策邊界g(xi)表示為：

wR-wU,xi+bR-bU= 0.

(3)

定義4(R-U)的間隔.基于(R-U)的決策邊界的間隔m(xi)表示為：

(4)

具體到訓(xùn)練集D上：

(5)

假設(shè)標(biāo)記集合中的元素是排好序的，那么公式(5)應(yīng)為正值，即wR-wU,xi+bR-bU> 0，對參數(shù)w正則化，可得wR-wU,xi+bR-bU≥ 1.那么最大化間隔可定義為如下優(yōu)化問題：

(6)

理想情況下，公式(6)可進(jìn)一步被優(yōu)化：

(7)

(8)

(9)

那么，標(biāo)記對的線性分類問題求解算法的輸入為訓(xùn)練集D和參數(shù)I，對于每一個(gè)標(biāo)記對(R-U)，定義其決策邊界與間隔，可在最小化間隔的過程中求得最優(yōu)參數(shù)；另外，定義排序損失函數(shù)，將間隔與排序損失函數(shù)轉(zhuǎn)化為二次規(guī)劃問題，輸出線性模型參數(shù).

算法1訓(xùn)練分類模型.

輸入：訓(xùn)練集D和參數(shù)I

輸出：Q個(gè)分類模型的參數(shù)w,b

//fori= 1:m；

//for each(R-U)，(R-U)

//對當(dāng)前標(biāo)記對(R-U)定義決策邊界(公式(3))；

//根據(jù)決策邊界g(xi)定義間隔(公式(4))；最大化間隔求解參數(shù)(公式(6))；

//最小化損失函數(shù)來優(yōu)化參數(shù)(公式(1))；

//將間隔與損失函數(shù)求解轉(zhuǎn)換為二次規(guī)劃問題，求解參數(shù)；

//end for

//end for

標(biāo)記對的線性分類問題求解算法可解決標(biāo)記間的序關(guān)系，然而其并未考慮標(biāo)記間的權(quán)重關(guān)系，于是WMLARP算法第2步對(R-R′)上的權(quán)重進(jìn)行定義并計(jì)算相對大小.

3.2 (R-R′)的權(quán)重概率計(jì)算

WMLARP在(R-R′)標(biāo)記對上，根據(jù)3.1中計(jì)算的樣本點(diǎn)(xi,Yi)的決策函數(shù)，定義標(biāo)記對的權(quán)重概率，計(jì)算大小以確定標(biāo)記集中標(biāo)記權(quán)重的排序，優(yōu)化(xi,Yi)的線性分類模型參數(shù)w，具體算法如算法2所述.

定義5(R-R′)的權(quán)重概率.它表示標(biāo)記R比標(biāo)記R′更相關(guān)的概率，參數(shù)δ為標(biāo)記集內(nèi)調(diào)節(jié)標(biāo)記權(quán)重比值的算子，公式為：

(10)

其中PR,R′(f)[0,1].

如果WeightR>WeightR′，權(quán)重概率PR,R′(f)應(yīng)無限趨近于1；如果WeightR

(11)

最小化損失函數(shù)得到進(jìn)一步優(yōu)化的分類模型參數(shù)wR：

(12)

那么，優(yōu)化分類模型參數(shù)算法的輸入為訓(xùn)練集D和參數(shù)w,δ，為當(dāng)前(R-R′)定義權(quán)重概率，計(jì)算實(shí)際權(quán)重概率并以此定義損失函數(shù)，最小化損失函數(shù)的過程中求解最優(yōu)參數(shù)，輸出參數(shù)w.

算法2優(yōu)化分類模型參數(shù).

輸入：訓(xùn)練集D和參數(shù)w,δ

輸出：Q個(gè)分類模型的參數(shù)w

//fori= 1:m；

//for each(R-R′)，R,R′Yi；

//對當(dāng)前標(biāo)記對(R-R′)定義權(quán)重概率(公式(10))；

//對當(dāng)前標(biāo)記對(R-R′)計(jì)算實(shí)際權(quán)重概率(公式(11))；

//最小化損失函數(shù)來優(yōu)化參數(shù)(公式(2))；

//end for

//end for

3.3 標(biāo)記集序列預(yù)測

以上是如何構(gòu)建分類模型，下文將確定標(biāo)記集合內(nèi)標(biāo)記序列及標(biāo)記集合大小以輸出最終結(jié)果.

定義6標(biāo)記集合大小.標(biāo)記集合大小S(x)可由如下規(guī)則確定：

S(x)= |{fk(x)>t(x)}|,

(13)

其中t(x)為相應(yīng)閾值函數(shù).

設(shè)閾值函數(shù)t(x)=w*,f*(x)+b*為線性函數(shù)，f*(x)=(f(x,y1),f(x,y2), …,f(x,ym))Td，w*d為權(quán)值向量，b*為偏置.那么標(biāo)記集合大小S(x)的求解過程也就是最小化損失函數(shù)的過程：

(14)

最終，基于線性模型和閾值函數(shù)的解，可得多標(biāo)記分類模型：

h(x)= {yj|wj,x+bj>w*,f*(x)+b*,

1≤j≤m}.

(15)

4 實(shí)驗(yàn)與分析

4.1 數(shù)據(jù)集及實(shí)驗(yàn)環(huán)境

本文數(shù)據(jù)集選用yeast數(shù)據(jù)集[11](Yeast Saccharomyces cerevisiae)，每個(gè)基因按照功能被分為多個(gè)類別.yeast數(shù)據(jù)集包括2417個(gè)樣本，103個(gè)屬性，14個(gè)類別標(biāo)記，其基數(shù)為4.237，密度為0.303；取其中62%的樣本數(shù)據(jù)作為訓(xùn)練集，38%作為測試集.本文使用的yeast數(shù)據(jù)集為經(jīng)人工預(yù)處理的數(shù)據(jù)集，將樣本對應(yīng)的標(biāo)記集合處理為服從某個(gè)概率分布的標(biāo)記序列.本文實(shí)驗(yàn)了3種概率分布：隨機(jī)分布、均勻分布、正態(tài)分布.

實(shí)驗(yàn)環(huán)境為8G內(nèi)存的Windows7操作系統(tǒng)，其CPU為Intel Core i7-6700，主頻為3.40GHz.本算法實(shí)驗(yàn)平臺為MATLAB，部分用Python語言進(jìn)行數(shù)據(jù)處理.

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

本文提出的WMLARP算法充分考慮了標(biāo)記間的相關(guān)性，同時(shí)考慮了標(biāo)記間的序關(guān)系以及相對權(quán)重大小，使得模型能準(zhǔn)確給出示例對應(yīng)的標(biāo)記序列.為了實(shí)現(xiàn)標(biāo)記間相對權(quán)重大小序列，驗(yàn)證WMLARP算法的有效性，本文將就1-AveragePrecision、2-OneError、3-RankingLoss、4-MRR(Mean Reciprocal Rank)這四項(xiàng)評價(jià)指標(biāo)與經(jīng)典RankSVM算法進(jìn)行對比.1-AveragePrecision考察在計(jì)算序關(guān)系的多分類系統(tǒng)中排在相關(guān)標(biāo)記之前的標(biāo)記仍是示例的相關(guān)標(biāo)記的情況；2-OneError用于統(tǒng)計(jì)標(biāo)記序列中排在靠前位置的標(biāo)記不是示例的相關(guān)標(biāo)記的情況；3-RankingLoss考察標(biāo)記序列中出現(xiàn)排序錯誤的情況；4-MRR考察標(biāo)記序列的優(yōu)劣，根據(jù)示例的相關(guān)標(biāo)記在序列中的排序位置來評估分類器的性能.

WMLARP中參數(shù)δ用來調(diào)節(jié)數(shù)據(jù)集上權(quán)重占比，將δ的取值范圍定為{0.32,0.37,…,0.77}，分別取值進(jìn)行實(shí)驗(yàn)，觀察4個(gè)指標(biāo)的變化，分別取3個(gè)變化階段中最具代表性的3個(gè)值：0.37,0.43,0.50代入公式進(jìn)行實(shí)驗(yàn).

假設(shè)標(biāo)記權(quán)重服從[0,1]內(nèi)的連續(xù)隨機(jī)分布，實(shí)驗(yàn)結(jié)果如圖1所示.δ=0.50時(shí)，除了在1-AveragePrecision上WMLARP比RankSVM低0.1個(gè)百分點(diǎn)，其余3項(xiàng)指標(biāo)WMLARP均優(yōu)于RankSVM；δ=0.37、δ=0.43時(shí)，WMLARP的4項(xiàng)指標(biāo)均明顯優(yōu)于RankSVM，其中，δ取0.43時(shí)WMLARP性能最佳，權(quán)重關(guān)系被充分挖掘，WMLARP性能可明顯優(yōu)于RankSVM.

圖1 WMLARP與RankSVM四項(xiàng)指標(biāo)對比(隨機(jī)分布)

假設(shè)標(biāo)記服從[0,1]內(nèi)的均勻概率分布，實(shí)驗(yàn)結(jié)果如圖2所示.WMLARP的四項(xiàng)評價(jià)指標(biāo)均明顯優(yōu)于RankSVM，且MRR提升最高；當(dāng)δ=0.43時(shí)，WMLARP性能最優(yōu).

圖2 WMLARP與RankSVM四項(xiàng)指標(biāo)對比(均勻分布)

假設(shè)標(biāo)記服從正態(tài)概率分布，實(shí)驗(yàn)結(jié)果如圖3所示.δ=0.50時(shí)，WMLARP與RankSVM相比，1-AveragePrecision低0.02個(gè)百分點(diǎn)，3-RankingLoss高0.02個(gè)百分點(diǎn)，其余兩項(xiàng)指標(biāo)WMLARP均明顯優(yōu)于RankSVM；δ=0.37、δ=0.43時(shí)，WMLARP的4項(xiàng)指標(biāo)均優(yōu)于RankSVM，其中，δ取0.43時(shí)，WMLARP性能最佳.

由以上分析可看出，在同時(shí)考慮標(biāo)記間的序及權(quán)重大小關(guān)系的情況下，WMLARP的性能明顯優(yōu)于RankSVM，特別是當(dāng)標(biāo)記權(quán)重服從均勻分布的情況時(shí)，WMLARP性能最優(yōu)，原因可能是均勻分布的標(biāo)記權(quán)重相對更容易被WMLARP挖掘，這說明標(biāo)記的權(quán)重分布情況對分類結(jié)果有影響.當(dāng)δ的取值發(fā)生變化時(shí)，WMLARP的實(shí)驗(yàn)結(jié)果也會發(fā)生變化，這說明對數(shù)據(jù)集賦予某個(gè)權(quán)重值的占比會對模型的性能產(chǎn)生影響.δ取值過小時(shí)，權(quán)重占比太小，WMLARP在計(jì)算權(quán)重關(guān)系上作用不大；δ取值過大時(shí)，會造成模型的過擬合；因此，當(dāng)δ取在稍小于0.5的值時(shí)，分類模型的質(zhì)量更優(yōu).另外，WMLARP的參數(shù)δ共取了3次值，在第3次取值時(shí)存在兩項(xiàng)指標(biāo)差別不大的結(jié)果，其他情況下均優(yōu)于RankSVM，這說明WMLARP挖掘標(biāo)記間關(guān)系的性能更優(yōu).綜上，WMLARP算法充分考慮了標(biāo)記間的相關(guān)性，性能相對較優(yōu).

圖3 WMLARP與RankSVM四項(xiàng)指標(biāo)對比(正態(tài)分布)

5 結(jié)語

本文提出的WMLARP算法通過計(jì)算標(biāo)記集合內(nèi)標(biāo)記間的權(quán)重概率，來考慮原始標(biāo)記權(quán)重對分類結(jié)果的影響，有效提高了多標(biāo)記學(xué)習(xí)算法的精度；同時(shí)，充分挖掘了多標(biāo)記學(xué)習(xí)問題中標(biāo)記間的相關(guān)性，使模型具有更好的實(shí)用性.實(shí)驗(yàn)驗(yàn)證了WMLARP的性能.然而，WMLARP的算法復(fù)雜度與數(shù)據(jù)集規(guī)模有一定的關(guān)系，當(dāng)規(guī)模較大時(shí)，有效降低算法的復(fù)雜度成為下一步的主要工作.