楊菊英，劉 燚，羅 佳

(1.電子科技大學(xué)成都學(xué)院 計(jì)算機(jī)系，四川 成都 611731；2.西華師范大學(xué) 計(jì)算機(jī)學(xué)院，四川 南充 637009)

0 引 言

多標(biāo)簽學(xué)習(xí)中每個訓(xùn)練樣本可能同時帶有多個標(biāo)簽，當(dāng)標(biāo)簽規(guī)模成千上萬時，傳統(tǒng)方法往往遇到可擴(kuò)展性和高時間開銷問題[1,2]。

極限多標(biāo)簽分類方法的目的是在解決上述問題、處理巨大數(shù)據(jù)集和大規(guī)模標(biāo)簽的同時，控制算法的時間開銷，使分類成為事實(shí)可用的方法[3]。

在多標(biāo)簽學(xué)習(xí)領(lǐng)域，MIMLfast可以高效地處理大規(guī)模數(shù)據(jù)集[4]，但實(shí)驗(yàn)結(jié)果表明其處理的數(shù)據(jù)集的標(biāo)簽數(shù)量是有限的?；谥С窒蛄繖C(jī)的多標(biāo)簽學(xué)習(xí)[5]在多個數(shù)據(jù)集上取得了不錯的分類精度，但時間開銷偏大，使其應(yīng)用于大規(guī)模數(shù)據(jù)集的有效性受限。隱含狄利克雷分配(latent Dirichlet allocation, LDA)模型是多標(biāo)簽學(xué)習(xí)領(lǐng)域的經(jīng)典方法[6]?；诖四Ｐ停簧賹W(xué)者提出了其應(yīng)用于極限學(xué)習(xí)場景的改進(jìn)方法，例如基于緩存計(jì)算的LDA[7]、FUN-LDA[8]和DOLDA[9]等，這些取得了較好的實(shí)驗(yàn)效果，但極限多標(biāo)簽分類的伸縮性和效率問題仍未徹底解決。

帶標(biāo)簽的隱含狄利克雷分配(labeled latent Dirichlet allocation, LLDA)模型是近年來熱門的多標(biāo)簽學(xué)習(xí)方法，基于這一類方法，學(xué)者們在圖像標(biāo)簽學(xué)習(xí)、文本標(biāo)簽分類等領(lǐng)域取得了不少的成果[10,11]。雖然LLDA在大規(guī)模數(shù)據(jù)訓(xùn)練中的時間復(fù)雜度不再依賴標(biāo)簽集的規(guī)模L，但與每個實(shí)例的平均標(biāo)簽數(shù)量有關(guān)，因此仍然不適用于復(fù)雜多標(biāo)簽學(xué)習(xí)問題。本文提出了一種劃分子集的帶標(biāo)簽隱含狄利克雷分配模型，改模型可進(jìn)一步提高算法在大規(guī)模極限學(xué)習(xí)時的可擴(kuò)展性和時間效率。

1 LDA與LLDA

1.1 隱含狄利克雷分配模型

隱含狄利克雷模型是一種經(jīng)典的、高效的概率主題模型。為了統(tǒng)一對模型的描述，首先規(guī)定如下：設(shè)樣本的標(biāo)簽總數(shù)為L，特征總數(shù)為V，l表示一個標(biāo)簽，v表示一種特征類型，wi是特征在樣本位置i處的標(biāo)記，樣本的總數(shù)為M，其中MTRAIN和MTEST分別表示訓(xùn)練集和測試集的規(guī)模，m表示一個樣本。此外，Lm表示樣本m的標(biāo)簽數(shù)量，Nm表示它的非零特征數(shù)量。

隱含狄利克雷模型假設(shè)當(dāng)給定一個樣本集時，存在兩種分布的集合，標(biāo)簽-特征分布稱之為φ，實(shí)例-標(biāo)簽分布稱之為θ。LDA模型通過對φ和θ進(jìn)行邊緣化操作，只使用隱含變量分配z來求解模型。在采樣過程中算法使用兩個計(jì)數(shù)矩陣，其中一個矩陣用于記錄特征v被分配給標(biāo)簽l的次數(shù)nlv，另一個用于記錄樣本m的特征被分配給標(biāo)簽l的次數(shù)nml。LDA原理如圖1所示。

圖1 LDA原理

在采樣階段，LDA根據(jù)l∈{1,…,L}來更新wi的硬分配參數(shù)zi，對于數(shù)據(jù)集中的所有標(biāo)記，更新時按照固定的迭代次數(shù)順序執(zhí)行的。更新方程如式(1)所示

(1)

式中：α和β是超參數(shù)。完成上述流程后，可以通過計(jì)算參數(shù)φ和θ進(jìn)行點(diǎn)估計(jì)。

1.2 帶標(biāo)簽的隱含狄利克雷分配模型

帶標(biāo)簽的隱含狄利克雷模型對傳統(tǒng)狄利克雷模型的改進(jìn)主要在于根據(jù)觀測到的樣本標(biāo)簽來限制某個標(biāo)記分配給某個標(biāo)簽的概率。對測試實(shí)例的推理類似于無監(jiān)督的LDA，標(biāo)簽-特征分布φ與之前在訓(xùn)練數(shù)據(jù)中學(xué)習(xí)到的內(nèi)容相匹配，而測試數(shù)據(jù)的θ分布參數(shù)通過估計(jì)獲得。

LLDA在標(biāo)簽上使用對稱的超參數(shù)α，給它們賦予相同的權(quán)重，然而在絕大多數(shù)真實(shí)應(yīng)用中，標(biāo)簽往往呈偏態(tài)分布。并且，特別是當(dāng)標(biāo)簽規(guī)模增大時，對標(biāo)簽依賴關(guān)系建?？梢蕴岣吣Ｐ捅憩F(xiàn)。為解決這些問題，學(xué)者在LLDA的基礎(chǔ)上提出了Prior-LDA和Dep-LDA[12]。Prior-LDA通過非對稱α超參數(shù)整合訓(xùn)練集中觀察到的標(biāo)簽頻率，更頻繁出現(xiàn)的標(biāo)簽將獲得更大的α′值，如式(2)所示

α′l=η·fl+α

(2)

式中：fl表示標(biāo)簽l在訓(xùn)練集中的頻率，fl∈[0,1]。

Dep-LDA是一個兩階段的算法，首先通過T個主題訓(xùn)練一個非監(jiān)督的LDA模型。通過估計(jì)得到的LDA模型將包含有關(guān)標(biāo)簽依賴性的信息，因?yàn)橄嚓P(guān)標(biāo)簽往往由同一個或同一批主題描述。其次，Dep-LDA將訓(xùn)練一個帶標(biāo)簽的隱含狄利克雷分配模型，之前通過訓(xùn)練估計(jì)的非監(jiān)督LDA模型的參數(shù)θ′和φ′將被用來計(jì)算非對稱的α′ml。特別是向量α′m將通過式(3)計(jì)算

α′m=η(θ′m·φ′)+α

(3)

帶標(biāo)簽的隱含狄利克雷分配模型的原理如圖2所示。

圖2 LLDA原理

2 劃分子集的LLDA

當(dāng)標(biāo)簽集的規(guī)模過大時(例如大于104)，LLDA即將難以適應(yīng)問題的規(guī)模，因?yàn)樗桥cL的規(guī)模線性相關(guān)的。不幸的是現(xiàn)有的各種LLDA的變種模型也不是針對這一問題進(jìn)行改進(jìn)的。

2.1 Subset LLDA原理

為解決以上問題，我們對經(jīng)典的LLDA模型的預(yù)測過程進(jìn)行了不同的改進(jìn)，通過限制標(biāo)簽空間，算法可以在其中搜索解決方案。我們提出的改進(jìn)模型可以分為如下兩個階段：

(1)首先，對于每個測試樣本都定義了一個候選的標(biāo)簽集，記為Lm Rel?？梢圆捎枚喾N方法來確定此候選列表，在本文中我們在訓(xùn)練集中搜索m個最鄰近的樣本，記作Mm Rel，并將候選列表設(shè)置為檢索到的實(shí)例標(biāo)記的聯(lián)合。

(2)其次，我們通過LLDA來做預(yù)測，但是限制可能的標(biāo)簽數(shù)量為Lm Rel。與Prior-LDA類似，我們修正了實(shí)例-主題分布的先驗(yàn)以表示標(biāo)簽在m個最鄰近的相似樣本中的出現(xiàn)頻率。例如，當(dāng)m=10時，如果一個給定的標(biāo)簽lA在3個相似的臨近樣本中出現(xiàn)，另一個給定的標(biāo)簽lB在5個相似的臨近樣本里出現(xiàn)，我們就讓α′lA=η+0.3α，α′lB=η+0.5α。

從形式上來說，我們提出的改進(jìn)的主題模型帶有如下假設(shè)：首先，對于一個給定的樣本s和給定的已經(jīng)標(biāo)記的實(shí)例集合MTRAIN，s的標(biāo)簽集合Ls將包含MTRAIN中m個臨近的最相似的樣本的標(biāo)簽的聯(lián)合。顯然，這一假設(shè)保證n→MTRAIN，但是在其它任何樣例中它將表示一種近似，并且我們希望Ls?Ls Rel。第二個假設(shè)與Gibbs采樣中的每個標(biāo)簽權(quán)重有關(guān)，我們假設(shè)對于一個給定的實(shí)例s，它的標(biāo)簽可以通過對多項(xiàng)式分布φ′m的采樣實(shí)現(xiàn)。這個假設(shè)與Prior-LDA中的策略非常類似，都是通過限制實(shí)例的標(biāo)簽只能通過Lm Rel而不是L來產(chǎn)生?；趧澐肿蛹膸?biāo)簽狄利克雷分配模型的原理如圖3所示。

圖3 Subset LLDA原理

如圖3所示，在Subset LLDA模型中，對于給定的實(shí)例m，其標(biāo)簽可以通過對m的臨近相似實(shí)例的多項(xiàng)式分布采樣而獲得。

Subset LLDA模型的原理如上所述，其生成過程如算法1所示。

算法1: Subset LLDA模型的生成過程

標(biāo)簽l∈L，樣例m，V上的采樣φl～Dirchlet(β)

begin

(1)Sampleninstance fromMTRAIN

(2)SetLm Rel=∪Lmiwithmi∈Mm Relandi∈{1,…,n}

(3)Sample a multinomial distributionφ′m～Dirchlet(β′)

(4)Calculateα′ according to Equation 2

(5)Sample a distributionθm～Dirichlet(α′) overLm Rel

(6)For each feature positioni∈{1…Nm}

Sample a labelzi～Multinomial(θm)

Sample a feature typevi～Multinomial(φl)with

l=zi

end

由于另一個原因，在預(yù)測期間約束標(biāo)簽集也很有用：LLDA需要搜索整個標(biāo)簽空間以便給一個給定的測試樣本推薦合適的標(biāo)簽，由于它是基于概率的模型，算法可能會陷入局部最優(yōu)解，特別是當(dāng)L的規(guī)模比較大時。例如一個訓(xùn)練好的LLDA模型來處理一個具有很高的φlv概率值的特殊的特征v；或者例如一個測試實(shí)例m包含特征v，其中只有一個上述標(biāo)簽在語義上相關(guān)。在以上這些情況下，這些噪聲標(biāo)簽，再加上LLDA的概率特性，可能會導(dǎo)致算法以犧牲正確標(biāo)簽為代價(jià)，偏向其中一個無關(guān)標(biāo)簽。這些問題當(dāng)然可以通過增大樣本數(shù)量并應(yīng)用馬爾可夫鏈方法解決，但這樣時間開銷太大，并不實(shí)用。因此，對LLDA進(jìn)行特征子集的劃分，在控制時間復(fù)雜度上也很有意義。

最終，我們用tf-idf方法和余弦相似度來選擇每個實(shí)例的最相似臨近實(shí)例，并設(shè)置n=10。

2.2 時間復(fù)雜度分析

對于數(shù)據(jù)集中每個樣本的所有特征標(biāo)記，LDA模型在求解時需要計(jì)算所有標(biāo)簽的概率分布，然后為標(biāo)記采樣標(biāo)簽。因此標(biāo)準(zhǔn)的LDA模型的時間復(fù)雜度是與標(biāo)簽集的規(guī)模L線性相關(guān)的，如式(4)所示

(4)

對于LLDA，通過限制特征標(biāo)記可以在實(shí)例的標(biāo)簽集Ld上獲取的可能標(biāo)簽，從而可以在訓(xùn)練期間引入監(jiān)督。一般來說，訓(xùn)練LLDA的時間開銷如式(5)所示

TLLDA∝Ο(MTRAIN·Vm·Lm)

(5)

根據(jù)之前的分析，LLDA測試過程的時間開銷與LDA相同，所以可以通過式(4)計(jì)算，而本文提出的基于劃分子集的LLDA模型在測試期間，只需要考慮最相似的n個樣本的標(biāo)簽，因此Subset LLDA的總的時間復(fù)雜度包含尋找n個最相似臨近樣本的時間開銷，如式(6)所示

(6)

其中，SubsetLLDA通過縮小標(biāo)簽集的規(guī)模，大大降低了算法的時間復(fù)雜度。

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

3.1 實(shí)驗(yàn)數(shù)據(jù)集

在實(shí)驗(yàn)部分，我們選擇了多個經(jīng)典的多標(biāo)簽開放數(shù)據(jù)集，我們將這些數(shù)據(jù)集劃分為4個小規(guī)模的樣本集和4個大規(guī)模的樣本集，每個數(shù)據(jù)集的統(tǒng)計(jì)特征見表1。

表1 實(shí)驗(yàn)數(shù)據(jù)集的統(tǒng)計(jì)特征

將實(shí)驗(yàn)數(shù)據(jù)分為4個小數(shù)據(jù)集和4個大數(shù)據(jù)集是為了便于將本文提出的方法和其它LLDA的變種方法以及其它極限分類方法作對比。

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

本文提出的模型基于Java平臺實(shí)現(xiàn)，為了對照實(shí)驗(yàn)的公平性，我們在模型訓(xùn)練中為所有的基于LLDA的模型選擇了相同的參數(shù)，取αl=50/L，α=0.1，β=0.01，在預(yù)測階段，設(shè)η=50，α=30/L，β=0.01。在訓(xùn)練階段以及預(yù)測階段，我們對所有數(shù)據(jù)集的處理都采用同樣的馬爾可夫鏈方法，迭代輪數(shù)為200輪。

為了驗(yàn)證劃分子集的主題模型方法是否可有效控制標(biāo)簽集規(guī)模，我們驗(yàn)證了不同算法對各數(shù)據(jù)集標(biāo)簽規(guī)模的情況，實(shí)驗(yàn)結(jié)果見表2。

表2 各算法在不同數(shù)據(jù)集上的標(biāo)簽規(guī)模

準(zhǔn)確率是分類問題最直觀的性能指標(biāo)。為此，我們對比了各種算法在不同數(shù)據(jù)集上的Precision，所有算法為每個實(shí)例輸出相關(guān)標(biāo)簽的排名，實(shí)驗(yàn)結(jié)果見表3。

表3 各算法在不同數(shù)據(jù)集上的Precision

如表3所示，與EL-LLDA、LDAIEC和Parabel算法相比，Subset LLDA模型不僅具有最高的標(biāo)簽預(yù)測綜合準(zhǔn)確率，而且各數(shù)據(jù)集上的預(yù)測準(zhǔn)確率比較穩(wěn)定，是所有對照算法中差異最小的。

對于多分類問題，我們希望在n個二分類混淆矩陣上綜合考察查準(zhǔn)率和查全率。一種直接的做法是先在各混淆矩陣上分別計(jì)算出查準(zhǔn)率和查全率，記為(P1,R1),(P2，R2)，…,(Pn，Rn)，再計(jì)算平均值，這樣就得到“宏查準(zhǔn)率Macro-P”、“宏查全率Macro-R”，以及相應(yīng)的“宏F1”(Macro-F1)，如式(7)所示

(7)

此外，我們可以通過真正例TP、假正例FP、真反例TN和假反例FN求得“微F1(Micro-F1)”如式(8)所示

(8)

我們用Micro-F1指標(biāo)和Macro-F1指標(biāo)衡量算法的性能，并與多個經(jīng)典方法進(jìn)行對比，實(shí)驗(yàn)結(jié)果見表4和表5。

表4 各算法在不同數(shù)據(jù)集上的Micro-F1

表5 各算法在不同數(shù)據(jù)集上的Macro-F1

如表4、表5所示，我們的對比方法包括屬于LLDA類模型的經(jīng)典或最新算法EL-LLDA[13]和LDAIEC[14]，以及非LLDA類的極限分類算法Parabel[15]。無論是與LLDA類的算法相比，還是和其它極限分類算法相比，本文提出的模型都有更高的分類性能。雖然各種算法在不同數(shù)據(jù)集上的表現(xiàn)各有差異，但Subset LLDA無論在大多數(shù)數(shù)據(jù)集上還是在綜合表現(xiàn)上，都優(yōu)于對照算法。實(shí)驗(yàn)結(jié)果還表明，相對非LLDA類的方法，LLDA類方法是具有一定的性能優(yōu)勢的。

綜合表3～表5的實(shí)驗(yàn)結(jié)果可知，與各種類型的經(jīng)典方法相比，本文提出的SubsetLLDA模型都具有較高的多標(biāo)簽預(yù)測的準(zhǔn)確率、召回率以及在不同類型數(shù)據(jù)集上性能的穩(wěn)定性，從多標(biāo)簽分類精度的角度而言，Subset LLDA模型是一種理想的多標(biāo)簽學(xué)習(xí)工具。

對于極限學(xué)習(xí)方法，時間開銷是衡量算法性能的重要指標(biāo)，由于前文實(shí)驗(yàn)所采用的8個數(shù)據(jù)集規(guī)模各不相同，因此我們依然使用之前的數(shù)據(jù)集，衡量各種算法在不同數(shù)據(jù)規(guī)模下的時間開銷。實(shí)驗(yàn)結(jié)果見表6。

表6 各算法在不同數(shù)據(jù)集上的時間開銷/s

此外，我們通過實(shí)驗(yàn)測試了各對照算法的時間開銷隨數(shù)據(jù)集規(guī)模的變化情況，實(shí)驗(yàn)結(jié)果如圖4所示。

圖4 時間開銷隨數(shù)據(jù)規(guī)模的變化對比

在表6中，時間開銷的度量單位為s，如表6所示，相對其它極限分類方法，LLDA類方法的時間開銷較高，但Subset LLDA在LLDA類方法中的時間開銷并不高。圖4 中數(shù)據(jù)量單位為MB，時間單位為s，如圖4所示，在各類基于LDA的方法中，隨著數(shù)據(jù)規(guī)模的增大，本文提出算法的時間開銷增長最為緩慢。本文提出的多標(biāo)簽學(xué)習(xí)方法在提高準(zhǔn)確率的同時控制了時間開銷，并未以增大計(jì)算復(fù)雜度作為代價(jià)，反而由于劃分子集的策略，在一定程度上減小了時間開銷。

4 結(jié)束語

多標(biāo)簽分類問題是大數(shù)據(jù)時代巨量數(shù)據(jù)挖掘的重要問題，帶標(biāo)記的隱含狄利克雷模型是解決多標(biāo)簽分類的重要方法。雖然LLDA在這一領(lǐng)域取得了不少成果，但其準(zhǔn)確率和效率依然具有提升空間。本文提出了一種基于劃分子集的Subset LLDA方法，通過限制候選標(biāo)簽的規(guī)模，進(jìn)一步提高了LLDA模型的精度和效率。應(yīng)用于多個數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果表明，本文提出方法具有高于經(jīng)典極限學(xué)習(xí)方法的多標(biāo)簽預(yù)測準(zhǔn)確率，并且相對于其它LLDA類方法，降低了時間開銷，使模型具有更強(qiáng)的實(shí)際應(yīng)用價(jià)值。

隨著社會網(wǎng)絡(luò)實(shí)時用戶生成內(nèi)容的增加，并行化處理、流式計(jì)算變得越來越重要。Subset LLDA如何與分布式、流式計(jì)算平臺融合，通過集群運(yùn)算進(jìn)一步降低時間開銷，將是這一領(lǐng)域未來有價(jià)值的研究方向。