改進(jìn)特征引導(dǎo)消歧的偏標(biāo)記學(xué)習(xí)算法

易 品， 劉振丙， 殷建華

(桂林電子科技大學(xué) 計(jì)算機(jī)與信息安全學(xué)院，廣西 桂林 541004)

監(jiān)督學(xué)習(xí)是機(jī)器學(xué)習(xí)中被研究的最為廣泛的一種學(xué)習(xí)框架[1]，在這種學(xué)習(xí)框架下，每個(gè)學(xué)習(xí)示例都有明確的標(biāo)記信息，是使訓(xùn)練得到的模型具有強(qiáng)泛化性能的前提。而真實(shí)世界的情景更為復(fù)雜，由于標(biāo)記成本高、真實(shí)標(biāo)記難以獲得等原因，常常無(wú)法得到明確的標(biāo)記信息。如何在弱監(jiān)督條件下進(jìn)行學(xué)習(xí)，已經(jīng)成為機(jī)器學(xué)習(xí)領(lǐng)域的熱門研究問(wèn)題[2]。

偏標(biāo)記學(xué)習(xí)屬于弱監(jiān)督學(xué)習(xí)的一種，屬于不準(zhǔn)確監(jiān)督，即給定的標(biāo)簽不總是真[3-5]。在偏標(biāo)記學(xué)習(xí)領(lǐng)域，每個(gè)訓(xùn)練示例與一系列的候選標(biāo)簽集相關(guān)聯(lián)，其中只有一個(gè)標(biāo)簽是真實(shí)的標(biāo)簽，其余的標(biāo)簽為偽標(biāo)簽[6-7]。偏標(biāo)記學(xué)習(xí)算法是通過(guò)有干擾的數(shù)據(jù)訓(xùn)練來(lái)習(xí)得分類模型，在現(xiàn)實(shí)生活中許多場(chǎng)景都存在類似情況，所以該領(lǐng)域具有很高的研究?jī)r(jià)值[8]。如在互聯(lián)網(wǎng)搜索引擎中，對(duì)一個(gè)關(guān)鍵詞進(jìn)行搜索時(shí)，會(huì)出現(xiàn)許多相關(guān)程度不高的圖片，這是由于該圖片的標(biāo)簽不止一個(gè)[9-10]，這種場(chǎng)景就適于用偏標(biāo)記學(xué)習(xí)算法來(lái)解決[11]，通過(guò)對(duì)帶有干擾的標(biāo)簽進(jìn)行學(xué)習(xí)，最終得到更高的識(shí)別精度，減少了在不考慮偽標(biāo)簽干擾情況下所帶來(lái)的損失。偏標(biāo)記學(xué)習(xí)是對(duì)傳統(tǒng)分類學(xué)習(xí)的一種延伸擴(kuò)展，具有非常廣闊的發(fā)展空間和應(yīng)用前景，在圖像分類、醫(yī)療診斷、文本挖掘、醫(yī)學(xué)圖像處理等領(lǐng)域也有相應(yīng)的應(yīng)用。

1 理論分析與設(shè)計(jì)

1.1 特征引導(dǎo)消歧

文獻(xiàn)[12]提出了一種基于特征感知消歧的偏標(biāo)記學(xué)習(xí)算法，利用特征空間的潛在信息，將偏標(biāo)記學(xué)習(xí)問(wèn)題轉(zhuǎn)換成多輸出回歸問(wèn)題。該算法分為2個(gè)階段：第一階段是消歧，通過(guò)對(duì)樣本在特征空間的流形結(jié)構(gòu)進(jìn)行學(xué)習(xí)得到結(jié)構(gòu)信息，并利用結(jié)構(gòu)信息在候選標(biāo)記集合上生成歸一化的標(biāo)記置信度信息；第二階段是預(yù)測(cè)模型的生成歸納，利用第一階段的信息來(lái)學(xué)習(xí)一個(gè)基于正則化的多輸出回歸模型，最終得到回歸模型在多個(gè)標(biāo)記中輸出值最大的一個(gè)所對(duì)應(yīng)的標(biāo)記。

1.2 改進(jìn)特征引導(dǎo)消歧方法

以往的消歧策略是把學(xué)習(xí)的重心放在標(biāo)簽信息空間[13]，忽視了特征信息與標(biāo)簽之間的聯(lián)系，未對(duì)已有的信息進(jìn)行充分利用。作為一種將樣本特征之間的相關(guān)性充分利用和結(jié)合的方法，改進(jìn)特征引導(dǎo)消歧方法彌補(bǔ)了特征信息欠擬合的弱點(diǎn)，使偏標(biāo)記學(xué)習(xí)過(guò)程中消歧的效果得到了改善[14-15]。但是在衡量樣本相關(guān)度的過(guò)程中，僅采用一種最小二乘法來(lái)計(jì)算權(quán)重矩陣，使相關(guān)度的計(jì)算過(guò)程存在單一性。因此，將示例的相似性進(jìn)行綜合考量，對(duì)特征引導(dǎo)消歧方法做出改進(jìn)，并采用集成學(xué)習(xí)的方法對(duì)分類模型的生成進(jìn)行優(yōu)化，提出了改進(jìn)特征引導(dǎo)消歧的集成學(xué)習(xí)偏標(biāo)記算法，簡(jiǎn)稱PL-FGD。

1.2.1 構(gòu)建特征相似度矩陣

每個(gè)樣本xi都由對(duì)應(yīng)的特征空間y和擁有多個(gè)標(biāo)簽集合的空間l組成，偏標(biāo)記學(xué)習(xí)系統(tǒng)的目標(biāo)是獲得一個(gè)輸出正確標(biāo)簽的多分類器h。消歧思想第一步是構(gòu)造一個(gè)樣本關(guān)聯(lián)度矩陣，獲得特征空間的結(jié)構(gòu)信息，為了得到不同示例特征之間的關(guān)聯(lián)度，首先要生成一個(gè)置信度矩陣，其能夠反映出第j個(gè)樣本和第i個(gè)樣本的相似度。對(duì)于偏標(biāo)記樣本，假設(shè)當(dāng)樣本間的特征相似度越高，樣本間具有相同標(biāo)簽的可能性就越高?；诖思僭O(shè)，用特征權(quán)重矩陣來(lái)定義示例樣本之間的特征關(guān)聯(lián)性。樣本特征空間X{x1,x2,…,xm}中的每個(gè)樣本xi都有一個(gè)基于KNN構(gòu)建的k近鄰樣本矩陣Ni，用于存放第i個(gè)樣本的緊鄰樣本序號(hào)，近鄰樣本數(shù)由參數(shù)k控制，通過(guò)計(jì)算最小二乘式得到樣本之間的權(quán)重矩陣，權(quán)重矩陣的計(jì)算可表示為

(1)

為了保證矩陣W是嚴(yán)格的對(duì)稱矩陣，需滿足

W=W+WT。

(2)

x從樣本的特征空間分布中獲得，權(quán)重矩陣中的wij表示示例xi與示例xj之間的相似度，該值越大，則對(duì)應(yīng)的2個(gè)樣本之間相似度越高。與已有的消歧算法不同的是，考慮到權(quán)重矩陣在構(gòu)建不同樣本的特征關(guān)聯(lián)過(guò)程中尤為重要，為了使權(quán)重矩陣在算法中具有更好的表現(xiàn)，用加權(quán)最小二乘法對(duì)權(quán)重矩陣進(jìn)行優(yōu)化處理。首先將通過(guò)加權(quán)最小二乘法得到的權(quán)重矩陣視為迭代初值，回代計(jì)算后求出初始?xì)埐睿瑢⒊跏細(xì)埐顦?biāo)準(zhǔn)化；然后將標(biāo)準(zhǔn)殘差代入權(quán)重初值進(jìn)行迭代計(jì)算，返回以上步驟，并依次進(jìn)行迭代；當(dāng)相鄰兩步的回歸系數(shù)差值的絕對(duì)值滿足臨界條件時(shí)，迭代結(jié)束。

1.2.2 構(gòu)建標(biāo)簽相似度矩陣

偏標(biāo)記學(xué)習(xí)領(lǐng)域存在標(biāo)簽信息利用不充分的問(wèn)題[16]，而在提出的假設(shè)中，不同示例標(biāo)簽之間可以利用的信息也對(duì)解決該領(lǐng)域問(wèn)題起重要作用。標(biāo)簽作為對(duì)樣本特征的一種描述和定義，也反映了樣本之間的聯(lián)系，利用標(biāo)簽信息進(jìn)行相似度計(jì)算能夠一定程度緩解數(shù)據(jù)稀疏性問(wèn)題。考慮到標(biāo)簽信息之間也存在與樣本特征之間相似的關(guān)聯(lián)性，用一個(gè)相似度矩陣度量候選標(biāo)簽集之間的相似度，以此達(dá)到在消歧階段對(duì)標(biāo)簽信息充分利用的目的。為了獲得可以將標(biāo)簽個(gè)體聯(lián)系起來(lái)的相似度矩陣，用皮爾遜相關(guān)系數(shù)度量標(biāo)簽集合間的相關(guān)度，相關(guān)系數(shù)越大，表示二者間的關(guān)聯(lián)性越強(qiáng)，反之則關(guān)聯(lián)性越弱。

2個(gè)樣本標(biāo)簽間的皮爾遜相關(guān)系數(shù)定義為2個(gè)變量之間的協(xié)方差與標(biāo)準(zhǔn)差的商，可表示為

(3)

通過(guò)估算樣本的協(xié)方差和標(biāo)準(zhǔn)差得到皮爾遜相關(guān)系數(shù)，可表示為

(4)

(5)

通過(guò)特征信息和標(biāo)簽信息得到的樣本之間的相似度可作為消歧的重要參考依據(jù)，將樣本之間的相似度定義為S，樣本之間的綜合相似度系數(shù)可表示為

(1-α)sim(L,Lk)，

(6)

其中，α為模型參數(shù)，用于調(diào)節(jié)特征權(quán)重和標(biāo)簽相似度之間的比例，使樣本之間的相似程度更符合真實(shí)樣本集的情況。用顯信度矩陣得到的最終計(jì)算結(jié)果為F= [fn,j]m×k,每行Fn=[fn,1,fn,2,…,fn,k]表示各個(gè)標(biāo)記作為示例xi的真實(shí)標(biāo)記的置信度，可表示為

(7)

1.2.3 生成預(yù)測(cè)模型

為了提高模型的分類精度，PL-FGD在學(xué)習(xí)框架中利用了集成學(xué)習(xí)中的bagging策略，使用CART樹[17]來(lái)實(shí)現(xiàn)分類決策樹的構(gòu)建。

集成學(xué)習(xí)是由多個(gè)分類器組成的學(xué)習(xí)系統(tǒng)，通過(guò)將多個(gè)學(xué)習(xí)器進(jìn)行結(jié)合，?？色@得比單一學(xué)習(xí)器顯著優(yōu)越的泛化性能，從而得到更好的結(jié)果[18]。一般集成學(xué)習(xí)方法可分為2種，一種是個(gè)體學(xué)習(xí)器間存在著強(qiáng)依賴的Adaboost算法，另一種是單個(gè)學(xué)習(xí)器之間相互獨(dú)立，同時(shí)可并行運(yùn)算，如隨機(jī)森林算法[19]。PL-FGD采用的集成方法是多個(gè)學(xué)習(xí)器的結(jié)合策略，學(xué)習(xí)器的結(jié)合具有如下好處：首先，多個(gè)學(xué)習(xí)器的結(jié)合比單個(gè)學(xué)習(xí)器有更好的泛化性能[20]，可通過(guò)多個(gè)學(xué)習(xí)器共同發(fā)揮作用來(lái)解決過(guò)擬合的問(wèn)題，且參數(shù)很少，對(duì)于回歸和分類都適用；其次，通過(guò)多次運(yùn)行可降低陷入局部極小點(diǎn)的風(fēng)險(xiǎn)，也無(wú)需事先做特征選擇，每次只隨機(jī)選取幾個(gè)特征來(lái)訓(xùn)練；最后，通過(guò)學(xué)習(xí)器的結(jié)合，樣本相應(yīng)的假設(shè)空間有所擴(kuò)大，實(shí)現(xiàn)了對(duì)數(shù)據(jù)的最大化利用，有效性更高。圖1為所建立的分類模型的流程示意圖。

圖1 分類模型的流程示意圖

根據(jù)A是否在某個(gè)結(jié)點(diǎn)處被劃分為2個(gè)樣本集合D1和D2，在特征A的條件下，集合D的基尼指數(shù)被定義為

(8)

如何確定葉子節(jié)點(diǎn)的預(yù)測(cè)值是構(gòu)建cart樹的關(guān)鍵，將決策樹視為一個(gè)分段函數(shù)，分段的依據(jù)是某個(gè)屬性的基尼系數(shù)值，在節(jié)點(diǎn)處，根據(jù)每個(gè)葉子結(jié)點(diǎn)確定一個(gè)分段區(qū)間，葉子節(jié)點(diǎn)的輸出即為函數(shù)在該節(jié)點(diǎn)的值。

1.3 本算法流程

PL-FGD算法被分為2個(gè)階段，第一階段是用改進(jìn)的特征引導(dǎo)方法對(duì)偏標(biāo)記數(shù)據(jù)進(jìn)行消歧處理；第二階段是采用集成學(xué)習(xí)中的bagging策略構(gòu)建分類模型，并使用CART決策樹作為單個(gè)分類器對(duì)劃分后的數(shù)據(jù)子集進(jìn)行訓(xùn)練。詳細(xì)的過(guò)程如下：在消歧階段，首先對(duì)不同類別的示例采用最小二乘的方法進(jìn)行權(quán)重計(jì)算；再采用更適用于多維空間的皮爾遜相關(guān)系數(shù)計(jì)算標(biāo)簽之間的相似度，解決示例之間相似度計(jì)算中的單一性問(wèn)題；最終得到迭代后的置信度矩陣，實(shí)現(xiàn)對(duì)不同類別示例消歧的目的，并得到用于分類模型的輸入數(shù)據(jù)。在分類階段，采用集成學(xué)習(xí)的方法預(yù)測(cè)真實(shí)標(biāo)記，同時(shí)將Cart樹作為弱分類器構(gòu)成單個(gè)決策樹，對(duì)劃分好的數(shù)據(jù)進(jìn)行訓(xùn)練，將其與bagging算法結(jié)合。在UCI數(shù)據(jù)集和偏標(biāo)記數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，本算法表現(xiàn)出更高的分類準(zhǔn)確率。算法流程如算法1所示。

算法1PL-FGD算法流程

輸入：

D：輸入樣本訓(xùn)練集{xi,Si|1≤i≤m}

k:近鄰樣本個(gè)數(shù)

λ,μ:函數(shù)的模型參數(shù)

x*：未見(jiàn)示例

輸出：

y*：樣本的預(yù)測(cè)標(biāo)簽

過(guò)程：

初始化參數(shù)

基于k近鄰構(gòu)建近鄰樣本矩陣Ni

根據(jù)式(1)計(jì)算最小二乘，得到樣本特征的權(quán)重矩陣

根據(jù)式(5)計(jì)算近鄰樣本間的皮爾遜相關(guān)系數(shù)，得到標(biāo)簽間的相似度矩陣

用加權(quán)最小二乘法對(duì)權(quán)重矩陣進(jìn)行優(yōu)化

通過(guò)式(6)得到樣本間綜合相似度S

根據(jù)式(7)得到消歧后的標(biāo)簽信息

根據(jù)式(8)、(9)構(gòu)建CART決策樹，并獲取預(yù)測(cè)

標(biāo)簽y*

2 實(shí)驗(yàn)結(jié)果

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

為了評(píng)估PL-FGD算法的性能，將實(shí)驗(yàn)數(shù)據(jù)分為兩部分?jǐn)?shù)據(jù)集：第一部分是人工改造的UCI數(shù)據(jù)集，分別為Vehicle、Pendigit、Usps、Letter、Segment；第二部分是真實(shí)的偏標(biāo)記數(shù)據(jù)集。表1和表2分別給出UCI數(shù)據(jù)集與真實(shí)數(shù)據(jù)集的性質(zhì)，包括數(shù)據(jù)集中的樣本數(shù)、特征屬性數(shù)、標(biāo)簽類別數(shù)。真實(shí)數(shù)據(jù)集還給出樣本的平均候選標(biāo)記集合大小。

表1 UCI數(shù)據(jù)集的數(shù)據(jù)特征

在UCI數(shù)據(jù)集上設(shè)置了3個(gè)參數(shù)，分別為r,p,ε，通過(guò)這3個(gè)參數(shù)構(gòu)造出28組實(shí)驗(yàn)數(shù)據(jù)，當(dāng)r從{1，2，3}中選擇其中一個(gè)，p將依次從{0.1，0.2，0.3，0.4，0.5，0.6，0.7}中選擇對(duì)應(yīng)的參數(shù)，構(gòu)成21組數(shù)據(jù)。另外，當(dāng)r=1，p=1時(shí)，ε控制偽標(biāo)簽和真實(shí)標(biāo)簽同時(shí)出現(xiàn)的概率。r表示在原數(shù)據(jù)的基礎(chǔ)上添加的偽標(biāo)簽數(shù)，p表示偽標(biāo)簽在訓(xùn)練數(shù)據(jù)集的所有標(biāo)簽中所占的比例，ε表示真實(shí)標(biāo)簽和偽標(biāo)簽同時(shí)出現(xiàn)的概率，在構(gòu)造訓(xùn)練數(shù)據(jù)時(shí)，通過(guò)不同的參數(shù)設(shè)置可以得到多個(gè)相對(duì)應(yīng)的數(shù)據(jù)組，從而觀測(cè)到算法的性能在不同的偏標(biāo)記數(shù)量下的波動(dòng)情況。

表2 偏標(biāo)記數(shù)據(jù)集的數(shù)據(jù)特征

2.2 對(duì)比實(shí)驗(yàn)方法

為了進(jìn)一步驗(yàn)證本算法的有效性，用6種對(duì)比實(shí)驗(yàn)方法作為比較對(duì)象，每種對(duì)比方法的介紹和參數(shù)設(shè)置具體如下：

1) PALOC[13]：一種采用二類分解機(jī)制方法的非消歧策略。

2) LSB-CMM[21]：通過(guò)極大似然方法生成預(yù)測(cè)模型的一種消歧策略。

3) M3PL[5]：基于邊緣最大化的偏標(biāo)記學(xué)習(xí)算法。該方法針對(duì)標(biāo)簽直接進(jìn)行邊緣最大化，提出了一種新的最大邊緣表達(dá)式，并使用交替優(yōu)化來(lái)實(shí)現(xiàn)消歧和最大邊緣化過(guò)程。

4) IPAL[7]：一種基于示例的偏標(biāo)記學(xué)習(xí)方法。該方法通過(guò)一種標(biāo)簽迭代的過(guò)程進(jìn)行消歧，然后基于未見(jiàn)示例近鄰樣本的最小誤差重建方法來(lái)進(jìn)行分類。

5) PL-LEAF[12]：充分利用特征空間中有用潛在信息的兩階段消歧分類方法。

6) PL-ECOC[13]：一種利用基于糾錯(cuò)輸出編碼技術(shù)的非消歧偏標(biāo)記學(xué)習(xí)算法。

2.3 實(shí)驗(yàn)結(jié)果

2.3.1 UCI數(shù)據(jù)集

本實(shí)驗(yàn)在3個(gè)人造UCI數(shù)據(jù)集上展開，從圖2～5可看出，在UCI人工數(shù)據(jù)集上，PL-FGD算法的分類準(zhǔn)確率優(yōu)于大部分已有的偏標(biāo)記學(xué)習(xí)算法，并在數(shù)據(jù)集Deter上表現(xiàn)出分類準(zhǔn)確率受偏標(biāo)記率增長(zhǎng)而產(chǎn)生的起伏較為明顯，在數(shù)據(jù)集Segment和Vehicle上起伏不明顯。具體表現(xiàn)在:

1) 在Deter數(shù)據(jù)集上，PL-FGD算法的平均分類準(zhǔn)確率與LSB-CMM持平，并優(yōu)于其他偏標(biāo)記學(xué)習(xí)算法，僅在r=1，p=0.1和r=1，p=0.5時(shí)分別以1%的差距次于算法LSB-CMM，并在參數(shù)r=1，p=0.5時(shí)分類準(zhǔn)確率達(dá)到最高，為94.2%。

2) 在Segment數(shù)據(jù)集上，PL-FGD算法的平均分類準(zhǔn)確率均優(yōu)于其他偏標(biāo)記學(xué)習(xí)算法，在r=3，p=0.1～0.4時(shí)，與IPAL算法基本持平，僅在r=1，p=0.2和r=1，p=0.5時(shí)，以0.5%的差距次于LSB-CMM算法，并在r=1，p=0.3時(shí)，分類準(zhǔn)確率達(dá)到最高，為94.9%。

3) 在Vehicle數(shù)據(jù)集上，r=1，p=0.2～0.3時(shí)，PL-FGD與PL-LEAF持平，在其他參數(shù)設(shè)置下，PL-FGD整體優(yōu)于其他對(duì)比算法，并在r=1，p=0.1時(shí)，分類準(zhǔn)確率達(dá)到最高，為83.2%。

圖2 當(dāng)r=1時(shí)各算法的分類精度

2.3.2 偏標(biāo)記數(shù)據(jù)集

表3給出基于十倍交叉驗(yàn)證方法在偏標(biāo)記數(shù)據(jù)集上的平均分類精度?；陲@著程度為0.05的成對(duì)t檢驗(yàn)，各數(shù)據(jù)集上性能最優(yōu)的算法在表3中用黑體形式標(biāo)注。從表3可看出：

1) 在數(shù)據(jù)集MSCRv2上，PL-FGD算法性能優(yōu)于其他對(duì)比算法；

2) 在數(shù)據(jù)集Bird Song上，PL-FGD算法性能優(yōu)于其他對(duì)比算法，且分類精度的提升效果最為顯著，與對(duì)比算法相比，分類精度平均提升了4.23%；

3) 在數(shù)據(jù)集Yahoo! News上，PL-FGD算法分類精度僅以3.88%和4.5%低于IPAL和M3PL算法，優(yōu)于其他對(duì)比算法；

4) 在數(shù)據(jù)集Soccer Player上，PL-FGD算法性能優(yōu)于其他對(duì)比算法；

5) 在數(shù)據(jù)集Lost上，PL-FGD算法的分類精度僅以0.93%低于PL-LEAF算法，優(yōu)于其他對(duì)比算法。

提出的PL-FGD算法分別在3組UCI數(shù)據(jù)集和3組偏標(biāo)記數(shù)據(jù)集上表現(xiàn)優(yōu)越。從整體看，PL-FGD算法在UCI數(shù)據(jù)集上比其他對(duì)比算法的分類精度高且魯棒性更好，僅在偏標(biāo)記數(shù)據(jù)集Yahoo! News 上低于IPAL和M3PL算法，在數(shù)據(jù)集Lost上低于PL-LEAF算法。

圖3 當(dāng)r=2時(shí)各算法的分類精度

圖4 當(dāng)r=3時(shí)各算法的分類精度

表3 各對(duì)比算法在偏標(biāo)記數(shù)據(jù)集上的分類精度

圖5 當(dāng)r=1,p=1時(shí)各算法的分類精度

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

提出了一種改進(jìn)特征引導(dǎo)消歧的偏標(biāo)記學(xué)習(xí)算法，解決了已有的特征引導(dǎo)消歧方法相似度計(jì)算中存在的單一性問(wèn)題，旨在更有效地利用標(biāo)簽與特征數(shù)據(jù)之間的聯(lián)系，且在分類階段用到了集成學(xué)習(xí)的思想，有利于提高算法的泛化性能。在人工改造的UCI數(shù)據(jù)集和偏標(biāo)記數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，本算法取得較好的分類精度，驗(yàn)證了本算法的有效性。在后續(xù)工作中，考慮在集成分類算法中，針對(duì)偏標(biāo)記數(shù)據(jù)的性質(zhì)和特點(diǎn)采用更好的分類方法。另外，最終的分類結(jié)果除簡(jiǎn)單的投票法外，可考慮更加高效的方式來(lái)得到分類結(jié)果。