周 瑜 賀建軍,2 顧 宏

1(大連理工大學(xué)電子信息與電氣工程學(xué)部 遼寧大連 116024)2 (大連民族大學(xué)信息與通信工程學(xué)院 遼寧大連 116600)(yuzhou829@sina.com)

基于變分高斯過程模型的快速核偏標(biāo)記學(xué)習(xí)算法

周 瑜1賀建軍1,2顧 宏1

1(大連理工大學(xué)電子信息與電氣工程學(xué)部 遼寧大連 116024)2(大連民族大學(xué)信息與通信工程學(xué)院 遼寧大連 116600)(yuzhou829@sina.com)

偏標(biāo)記學(xué)習(xí)(partial label learning)是人們最近提出的一種弱監(jiān)督機(jī)器學(xué)習(xí)框架，由于放松了訓(xùn)練數(shù)據(jù)集的構(gòu)造條件，只需知道訓(xùn)練樣本的真實(shí)標(biāo)記的一個(gè)候選集合就可進(jìn)行學(xué)習(xí)，可以更方便地處理很多領(lǐng)域的實(shí)際問題.在該框架下，訓(xùn)練數(shù)據(jù)的標(biāo)記信息不再具有單一性和明確性，這就使得學(xué)習(xí)算法的構(gòu)建變得比傳統(tǒng)分類問題更加困難，目前只建立了幾種面向小規(guī)模訓(xùn)練數(shù)據(jù)的學(xué)習(xí)算法.先利用ECOC技術(shù)將原始偏標(biāo)記訓(xùn)練集轉(zhuǎn)換為若干標(biāo)準(zhǔn)二分類數(shù)據(jù)集，然后基于變分高斯過程模型在每個(gè)二分類數(shù)據(jù)集上構(gòu)建一個(gè)具有較低計(jì)算復(fù)雜度的二分類算法，最終實(shí)現(xiàn)了一種面向大規(guī)模數(shù)據(jù)的快速核偏標(biāo)記學(xué)習(xí)算法.仿真實(shí)驗(yàn)結(jié)果表明，所提算法在預(yù)測(cè)精度幾乎相當(dāng)?shù)那闆r下，訓(xùn)練時(shí)間要遠(yuǎn)遠(yuǎn)少于已有的核偏標(biāo)記學(xué)習(xí)算法，利用普通的PC機(jī)處理樣本規(guī)模達(dá)到百萬級(jí)的問題只需要40 min.

偏標(biāo)記學(xué)習(xí);核方法;大規(guī)模數(shù)據(jù);高斯過程;分類

在傳統(tǒng)分類技術(shù)中，通常需要通過一個(gè)樣本的真實(shí)標(biāo)記信息準(zhǔn)確給定的訓(xùn)練數(shù)據(jù)集來訓(xùn)練分類器，而在很多實(shí)際問題中，這種強(qiáng)監(jiān)督訓(xùn)練數(shù)據(jù)通常很難或者需要付出很大代價(jià)才能獲得，相反，具有弱監(jiān)督標(biāo)記信息的數(shù)據(jù)卻唾手可得.例如，在醫(yī)療診斷中，醫(yī)生通過一個(gè)病人的癥狀(如關(guān)節(jié)疼、發(fā)燒、血沉高)，往往可以判斷他得了哪幾種疾病(可能是風(fēng)濕性關(guān)節(jié)炎、布氏桿菌病或其他疾病)，而很難確定具體是哪種疾??；在互聯(lián)網(wǎng)應(yīng)用中，用戶可以自由地為各種在線對(duì)象提供標(biāo)注，但對(duì)象獲得的多個(gè)標(biāo)注中可能僅有一個(gè)是正確的.因此，如何在弱監(jiān)督信息條件下有效地進(jìn)行學(xué)習(xí)建模已成為了很多領(lǐng)域的共同需求.偏標(biāo)記集學(xué)習(xí)(partial label learning[1-3]，也稱learning from candidate labeling sets[4]，ambiguous label learning[5]，superset label learning[6])是最近提出的一種重要的弱監(jiān)督學(xué)習(xí)框架,主要解決在只知道訓(xùn)練樣本的真實(shí)標(biāo)記屬于某個(gè)候選標(biāo)記集合的情況下如何進(jìn)行學(xué)習(xí)的問題.由于偏標(biāo)記學(xué)習(xí)是對(duì)傳統(tǒng)分類技術(shù)的一個(gè)擴(kuò)展，放松了構(gòu)造訓(xùn)練數(shù)據(jù)集的條件，因此它與傳統(tǒng)分類技術(shù)一樣具有廣闊的應(yīng)用空間，可以解決圖像處理[7]、文本挖掘[8]、醫(yī)療診斷[9]等領(lǐng)域的各種實(shí)際問題.

在偏標(biāo)記學(xué)習(xí)框架下，所能利用的訓(xùn)練數(shù)據(jù)的標(biāo)記信息不再具有單一性和明確性，真實(shí)標(biāo)記湮沒于候選標(biāo)記集合中，這就使得學(xué)習(xí)算法的構(gòu)建變得比傳統(tǒng)分類算法更加困難.最早的偏標(biāo)記學(xué)習(xí)算法可以追溯到2002年Grandvalet[10]對(duì)Logistic回歸模型的拓展研究，隨后Jin 和 Ghahramani[11]將偏標(biāo)記學(xué)習(xí)歸結(jié)為一種新的機(jī)器學(xué)習(xí)框架，提出了基于辨識(shí)模型的學(xué)習(xí)算法.在這2組科研人員的早期工作推動(dòng)下，偏標(biāo)記學(xué)習(xí)逐漸引起人們的關(guān)注，嘗試將傳統(tǒng)的機(jī)器學(xué)習(xí)模型引入偏標(biāo)記學(xué)習(xí)算法的構(gòu)建問題中，文獻(xiàn)[5]提出了一種基于k近鄰方法的偏標(biāo)記學(xué)習(xí)算法；文獻(xiàn)[12]提出了基于最大似然估計(jì)和信度函數(shù)的學(xué)習(xí)算法；Luo 和 Orabona[4]提出了最大間隔偏標(biāo)記學(xué)習(xí)算法；Cour 等人[2]和Nguyen等人[13]分別提出了線性支持向量機(jī)偏標(biāo)記學(xué)習(xí)算法；Liu和Dietterich[6]提出了條件混合多變量模型；Zhang[3]利用糾錯(cuò)輸出編碼技術(shù)(ECOC)提出了一種基于集成分類器的偏標(biāo)記學(xué)習(xí)算法；文獻(xiàn)[14]提出了一種針對(duì)結(jié)構(gòu)化輸入數(shù)據(jù)的偏標(biāo)記學(xué)習(xí)算法；文獻(xiàn)[15]提出了一種基于加權(quán)圖模型的算法.雖然經(jīng)過人們不斷的努力，目前已經(jīng)出現(xiàn)了CLPL[2]，PL-ECOC[3]，IPAL[15]等幾種較有效的偏標(biāo)記學(xué)習(xí)算法，但是這些算法要么計(jì)算復(fù)雜度較高不易處理大規(guī)模數(shù)據(jù)，要么是線性算法不易處理非線性問題，幾乎都不能有效處理大規(guī)模非線性偏標(biāo)記學(xué)習(xí)問題.針對(duì)以上問題，本文將結(jié)合糾錯(cuò)輸出編碼技術(shù)和變分高斯過程模型建立一種快速核偏標(biāo)記學(xué)習(xí)算法，與PL-ECOC[3]等基于核方法的偏標(biāo)記學(xué)習(xí)算法相比，本文算法的計(jì)算速度要遠(yuǎn)遠(yuǎn)快于這些算法，與CLPL[2]等線性偏標(biāo)記學(xué)習(xí)算法相比，本文算法的精度要高于這些算法.

1 算法描述

設(shè)X為樣本的特征空間，Y={y1,y2,…,yQ}為類別標(biāo)記集合.偏標(biāo)記學(xué)習(xí)的目的是利用一個(gè)訓(xùn)練集S={(x1,Y1),(x2,Y2),…,(xn,Yn)}(其中xi∈X是樣本的特征向量；Yi≡{yi1,yi2,…,yini}?Y是樣本xi的真實(shí)標(biāo)記的一個(gè)候選集合)確定一個(gè)函數(shù)f:X→Y，使得f可以正確輸出新(待預(yù)測(cè))樣本x*∈X的類別標(biāo)記.可以看出，與傳統(tǒng)分類框架明確給定每個(gè)訓(xùn)練樣本的真實(shí)標(biāo)記不同，在偏標(biāo)記學(xué)習(xí)框架下，我們只知道訓(xùn)練數(shù)據(jù)的真實(shí)標(biāo)記屬于某一個(gè)候選集合.為了設(shè)計(jì)有效的偏標(biāo)記學(xué)習(xí)算法，一種直觀的思路是通過定義新的模型損失函數(shù)來實(shí)現(xiàn)對(duì)偏標(biāo)記數(shù)據(jù)的候選標(biāo)記集合進(jìn)行消歧，然而，該類算法常常會(huì)受到偽標(biāo)記帶來的不利影響[1].最近，文獻(xiàn)[3]提出了一種非消歧策略，基本思想是利用ECOC技術(shù)將偏標(biāo)記學(xué)習(xí)問題的訓(xùn)練數(shù)據(jù)集變換為具有確切標(biāo)記信息的多個(gè)二分類問題的數(shù)據(jù)集，然后在每個(gè)二分類數(shù)據(jù)集上建立一個(gè)標(biāo)準(zhǔn)的二分類器，最后將各個(gè)分類器的結(jié)果綜合來輸出預(yù)測(cè)結(jié)果.本文也將基于以上策略，先利用ECOC技術(shù)將問題轉(zhuǎn)換為二分類問題，然后采用變分高斯過程二分類算法來實(shí)現(xiàn)最終的快速核偏標(biāo)記學(xué)習(xí)算法.雖然都是基于ECOC技術(shù)來構(gòu)建偏標(biāo)記學(xué)習(xí)算法，本文和文獻(xiàn)[3]的研究重點(diǎn)和創(chuàng)新性是不同的，文獻(xiàn)[3]的重點(diǎn)是構(gòu)建一種基于非消歧策略的偏標(biāo)記學(xué)習(xí)算法，主要?jiǎng)?chuàng)新是將ECOC技術(shù)引入到了偏標(biāo)記學(xué)習(xí)問題中；而本文的重點(diǎn)是構(gòu)建一種面向大規(guī)模數(shù)據(jù)的偏標(biāo)記學(xué)習(xí)算法，主要?jiǎng)?chuàng)新在采用了適合該問題的二分類器.下面分別對(duì)基于ECOC技術(shù)的問題變換策略和類不平衡變分高斯過程二分類器這2個(gè)本文算法的核心模塊進(jìn)行描述.

1.1 基于ECOC技術(shù)的問題變換策略

(1)

假設(shè)fl:X→{+1,-1}是基于訓(xùn)練集Sl構(gòu)建的二分類器，F(xiàn)*=(f1(x*),f2(x*),…,fL(x*))是由各個(gè)二分類器在待預(yù)測(cè)樣本x*上的輸出構(gòu)成的向量，在解碼階段可以將碼字與F*最接近的類別作為待預(yù)測(cè)樣本的類別，即

(2)

其中，dist(·)表示2個(gè)向量之間的距離，本文將采用海明距離.

1.2 類不平衡變分高斯過程二分類器

由于通過ECOC技術(shù)變換得到的二分類數(shù)據(jù)集有時(shí)是一種類不平衡數(shù)據(jù)集，即正負(fù)類樣本數(shù)目的比例會(huì)很懸殊，特別是當(dāng)原始偏標(biāo)記訓(xùn)練數(shù)據(jù)集本身存在類不平衡問題時(shí)，上述現(xiàn)象更為明顯，因此構(gòu)建的二分類器需要能很好地處理類不平衡問題.另外，我們希望構(gòu)建一種面向大規(guī)模數(shù)據(jù)的非線性算法，因此二分類器最好是一種具有較低計(jì)算復(fù)雜度的核分類算法.雖然人們已經(jīng)就面向大規(guī)模數(shù)據(jù)的核機(jī)器學(xué)習(xí)技術(shù)開展了一系列的研究，但是符合以上條件的算法并不多.KLSP算法[16]是一種基于變分原理建立的面向大規(guī)模數(shù)據(jù)的高斯過程二分類算法，它不僅具有較低的計(jì)算復(fù)雜度和較高的精度，而且還具有避免過擬合、可以用分布式或者隨機(jī)優(yōu)化的方法對(duì)模型進(jìn)行求解等優(yōu)點(diǎn)，但是該算法并不能處理類不平衡問題，本節(jié)將采用一種改進(jìn)的KLSP算法來作為本文算法的二分類器.

1) 假設(shè)f(x)服從如下零均值高斯過程分布：

(3)

其中，k(x,x′)表示協(xié)方差函數(shù)，本文將使用RBF核α1e-‖x-x′‖2α2作為協(xié)方差函數(shù).利用式(3),可以得到f(x)在訓(xùn)練樣本集D上的函數(shù)值FD的先驗(yàn)概率分布p(FD|D)=N(FD|0,KD)，以及f(x)在待預(yù)測(cè)樣本x*上的函數(shù)值f*=f(x*)關(guān)于FD的條件先驗(yàn)概率分布p(f*|FD,x*,D)=N(f*|K*D，其中FD=(f1,f2,…,=f(xi)，KD是協(xié)方差函數(shù)k(x,x′)在樣本集D上的值構(gòu)成的方陣，K*D表示預(yù)測(cè)樣本x*和D中樣本之間的協(xié)方差函數(shù)值構(gòu)成的行向量，K*=k(x*,x*).

2) 定義聯(lián)合似然函數(shù)

(4)

其中，p(yi|fi)可以利用Logistic函數(shù)定義為p(yi|fi)=1(1+e-yifi).

3) 計(jì)算FD的后驗(yàn)概率分布：

(5)

由于不能得到p(FD|D,Y)的分析表達(dá)式，通常需要利用Laplace逼近[16]、Expectation Propagation[17]等方法計(jì)算它的一個(gè)近似表達(dá)式q(FD|D,Y).

4) 根據(jù)p(FD|D,Y)和p(f*|FD,D,x*)計(jì)算f*的后驗(yàn)概率：

p(f*|D,Y,x*)=

(6)

從而得到x*是正樣本的概率為

p(y*=+1|D,Y,x*)=

p(FD|D,Y)=∫p(FD|FU,D)p(FU|D,Y)dFU≈

(7)

其中，F(xiàn)U是潛變量函數(shù)f(x)在訓(xùn)練樣本集D的一個(gè)子集U(U的選取方式見算法實(shí)現(xiàn)部分)上的函數(shù)值，即FU=(f(xi1),f(xi2),…,f(xim))T,xim∈U，而q(FU|D,Y)=N(FU|μ,Σ)可以通過最大化邊緣似然p(Y|D)的下界得到：

lnp(Y|D)=ln ∫p(Y|FU)p(FU|D)dFU≥

∫∫lnp(Y|FD)p(FD|FU,D)q(FU|D,Y)dFUdFD-

KL(q(FU|D,Y)‖p(FU|D))Ψ(μ,Σ).

(8)

在得到由式(7)表示的后驗(yàn)概率分布p(FD|D,Y)后，后驗(yàn)概率分布式(6)可以重新表示為

p(f*|D,Y,x*)=

∫p(f*|FD,D,x*)p(FD|D,Y)dFD≈

∫p(f*|FD,D,x*)∫p(FD|FU,D)q(FU|D,

(9)

從式(9)可以看出，f*的后驗(yàn)概率分布主要與子集U和q(FU|D,Y)=N(FU|μ,Σ)有關(guān)，因此算法的主要計(jì)算量來自計(jì)算q(FU|D,Y)=N(FU|μ,Σ).

由于通過ECOC技術(shù)變換得到的二分類數(shù)據(jù)集有時(shí)是類不平衡數(shù)據(jù)集，而前面描述的變分高斯過程分類算法KLSP并不能處理類不平衡問題.我們可以通過定義改進(jìn)的聯(lián)合似然函數(shù)來實(shí)現(xiàn)處理不平衡問題的目的，即在聯(lián)合似然函數(shù)中的正負(fù)類樣本對(duì)應(yīng)的似然上引入不同的權(quán)重系數(shù)，使得錯(cuò)分少數(shù)類樣本的代價(jià)大于錯(cuò)分多數(shù)類樣本的代價(jià)，最終實(shí)現(xiàn)改善少數(shù)類樣本預(yù)測(cè)精度的目的.按照該思想，可以將式(4)定義的聯(lián)合似然函數(shù)重新定義為

(10)

(11)

對(duì)Ψ(μ,Σ)分別關(guān)于μ,Σ求導(dǎo)，可得:

(12)

在得到梯度式(12)后，可以采用各種基于梯度的優(yōu)化方法求解μ,Σ.求得μ,Σ以后就可以利用式(9)計(jì)算f*的后驗(yàn)概率分布，從而得到樣本x*是正樣本的概率為

p(y*=+1|D,Y,x*)=

(13)

2 算法實(shí)現(xiàn)

本文算法的流程圖如算法1所示，下面給出各個(gè)關(guān)鍵模塊的實(shí)施細(xì)節(jié).誘導(dǎo)子集U可以通過各種聚類算法來選取，為了減少計(jì)算時(shí)間，本文采用Chen[18]實(shí)現(xiàn)的一種快速K均值聚類算法來完成U的(假設(shè)包含m個(gè)樣本)選取.基本規(guī)則是先對(duì)正負(fù)類樣本分別進(jìn)行聚類各生成m2個(gè)聚類中心，然后把這些聚類中心合并來構(gòu)成U.在算法的訓(xùn)練和預(yù)測(cè)階段都需要頻繁地用到協(xié)方差矩陣KU的逆矩陣，而在有的實(shí)際問題中KU會(huì)是一個(gè)奇異矩陣，為了保證數(shù)值穩(wěn)定性，在計(jì)算KU的逆矩陣時(shí)我們加入了一個(gè)擾動(dòng)項(xiàng)10-7I，即=(KU+10-7I)-1.通過權(quán)衡計(jì)算復(fù)雜度、存儲(chǔ)復(fù)雜度和穩(wěn)定性等因素，本文采用了有限儲(chǔ)存擬牛頓方法(L-BFGS)來計(jì)算潛變量函數(shù)FU的均值和方差μ,Σ，L-BFGS算法的詳細(xì)計(jì)算流程本文將不再贅述，可以參見文獻(xiàn)[19].

算法1. PL-ECOC-VGP算法的偽代碼.

訓(xùn)練階段.

輸入:訓(xùn)練集S、ECOC的編碼長(zhǎng)度L、誘導(dǎo)集的樣本個(gè)數(shù)m、L-BFGS算法的存儲(chǔ)長(zhǎng)度M、二分類集的最少樣本個(gè)數(shù)thr、L-BFGS算法的迭代次數(shù)iter、協(xié)方差函數(shù)的參數(shù)α1和α2；

forl=1,2,…,Ldo

1) 生成編碼矩陣M的第l行元素，構(gòu)造第l個(gè)二分類訓(xùn)練集Sl=?：

① 隨機(jī)生成一個(gè)長(zhǎng)度為Q的二值編碼向量v∈{-1,+1}Q；

② 根據(jù)式(2)構(gòu)造二分類訓(xùn)練集Sl；

③ 如果|Sl|

④ 設(shè)定編碼矩陣M的第l行元素為v，即M(l,:)=v；

2) 以Sl為訓(xùn)練數(shù)據(jù)集構(gòu)造變分高斯過程分類器fl：

① 利用快速聚類算法[18]選取誘導(dǎo)子集U；

③ 根據(jù)式(12)利用L-BFGS算法[19]計(jì)算FU的均值μ和方差Σ，其中L-BFGS算法的迭代次數(shù)設(shè)定為iter,存儲(chǔ)長(zhǎng)度設(shè)定為M；

end for

預(yù)測(cè)階段.

輸出:x*的預(yù)測(cè)類別.

① 計(jì)算K*；

② forl=1,2,…,Ldo

③ 計(jì)算Ul與x*的協(xié)方差矩陣K*Ul；

⑤ 如果p(y*=+1|D,Y,x*)>0.5,則確定fl在x*的輸出為fl(x*)=+1,否則fl(x*)=-1；

⑥ end for

⑦ 根據(jù)式(2)確定算法對(duì)x*的預(yù)測(cè)類別.

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

為了驗(yàn)證本文所建算法(簡(jiǎn)記為PL-ECOC-VGP)的性能，本節(jié)將其與CLPL[2]和PL-ECOC[3]2個(gè)代表性的偏標(biāo)記學(xué)習(xí)算法在6個(gè)UCI數(shù)據(jù)集[20]上進(jìn)行了比較，其中CLPL算法是2011年由Cour等人建立的一種線性偏標(biāo)記學(xué)習(xí)算法，PL-ECOC算法是2014年由Zhang建立的一種核偏標(biāo)記學(xué)習(xí)算法.這些UCI數(shù)據(jù)集的樣本數(shù)目從1萬～100萬量級(jí)不等，詳細(xì)信息如表1所示.由于UCI數(shù)據(jù)集是標(biāo)準(zhǔn)的傳統(tǒng)分類數(shù)據(jù)集，我們采用了2個(gè)控制參數(shù)p，r來把它們變換為偏標(biāo)記數(shù)據(jù)集，其中p表示偏標(biāo)記樣本(即|Yi|>1)在整個(gè)樣本集中的比例，r表示偏標(biāo)記樣本的除真實(shí)標(biāo)記以外的候選標(biāo)記個(gè)數(shù)，即r=|Yi|-1.變換過程如下：對(duì)于給定的每一對(duì)參數(shù)(p,r)，先從原始的UCI數(shù)據(jù)集中隨機(jī)選取pn個(gè)樣本(n為樣本總數(shù))；然后對(duì)于每一個(gè)被選取的樣本，隨機(jī)地從它的真實(shí)標(biāo)記以外的類別標(biāo)記中選取r個(gè)與真實(shí)標(biāo)記一起構(gòu)成該樣本的候選標(biāo)記.以下的所有實(shí)驗(yàn)結(jié)果都是通過隨機(jī)選取12的樣本作為訓(xùn)練數(shù)據(jù)，12的樣本作為測(cè)試數(shù)據(jù)，然后重復(fù)進(jìn)行5次實(shí)驗(yàn)得到的平均結(jié)果.所有結(jié)果都是在CPU主頻為2.5 GHz、內(nèi)存為8 GB的筆記本電腦上運(yùn)行得到的.

Table 1 The UCI Data Sets for Validating the Performanceof the Proposed Algorithm

觀察算法流程圖可以看出，PL-ECOC-VGP算法的參數(shù)比較多，為了避免參數(shù)選擇的麻煩，我們首先在Shuttle數(shù)據(jù)集(控制參數(shù)為p=0.6,r=3)和Protein數(shù)據(jù)集(控制參數(shù)為p=0.6,r=1)上觀察了這些參數(shù)取不同值時(shí)對(duì)算法性能的影響；然后對(duì)于一些對(duì)算法精度影響不是太大的參數(shù)，在所有的數(shù)據(jù)集上都設(shè)定了統(tǒng)一的參數(shù)，如L-BFGS算法的迭代次數(shù)iter和記憶存儲(chǔ)長(zhǎng)度M都默認(rèn)地設(shè)定為5，設(shè)定ECOC的編碼長(zhǎng)度L=10 lnQ，設(shè)定二分類集的最少樣本個(gè)數(shù)thr=n10.協(xié)方差函數(shù)的參數(shù)α1和α2的取值對(duì)算法精度的影響比較大，考慮到在連續(xù)的數(shù)值點(diǎn)上選取最優(yōu)參數(shù)比較費(fèi)時(shí)，在每個(gè)數(shù)據(jù)集上α1和α2的取值是在一個(gè)離散點(diǎn)集{(α1,α2)|α1=10-4,10-3,…,104;α2=3-2d，3-1d,…,32d}(d為隨機(jī)選取7 000個(gè)訓(xùn)練樣本計(jì)算得到的樣本之間的平均距離)上利用交叉驗(yàn)證法選取得到的.對(duì)于誘導(dǎo)子集的樣本個(gè)數(shù)m，我們發(fā)現(xiàn)在Shuttle數(shù)據(jù)集和Protein數(shù)據(jù)集上出現(xiàn)了2種完全不同的變化規(guī)律.如圖1所示，在Protein數(shù)據(jù)集上，隨著m取值的變大則算法的預(yù)測(cè)精度會(huì)逐漸變高；而在Shuttle數(shù)據(jù)集上卻正好相反，算法的預(yù)測(cè)精度會(huì)隨著m取值的變大而逐漸變低.通過進(jìn)一步分析我們發(fā)現(xiàn)，這可能與訓(xùn)練樣本的特征維數(shù)有關(guān)，在Shuttle數(shù)據(jù)集中樣本的特征維數(shù)是9，而在Protein數(shù)據(jù)集中樣本的特征維數(shù)為357.為了驗(yàn)證這個(gè)猜測(cè)在其他的數(shù)據(jù)集上做了驗(yàn)證，發(fā)現(xiàn)以上猜測(cè)基本是正確的，當(dāng)樣本的特征維數(shù)比較高時(shí)，需要的誘導(dǎo)樣本個(gè)數(shù)也比較多，但是這二者之間沒有固定的比例，而且當(dāng)m的取值變大時(shí)算法的計(jì)算時(shí)間會(huì)增加.因此在下面的實(shí)驗(yàn)中，對(duì)于特征維數(shù)在10左右的數(shù)據(jù)集，m的取值統(tǒng)一設(shè)定為50；對(duì)于剩下的數(shù)據(jù)集，m的取值統(tǒng)一設(shè)定為250.

Fig. 1 The accuracy of PL-ECOC-VGP algorithm when varying the number of inducing samples圖1 m取不同值時(shí)PL-ECOC-VGP算法的預(yù)測(cè)精度

表2列出了PL-ECOC-VGP，CLPL，PL-ECOC 3個(gè)算法在各個(gè)控制數(shù)據(jù)集上的性能表現(xiàn)，包括Acc，mAcc，Time三個(gè)性能指標(biāo)，其中，Acc表示算法在整體數(shù)據(jù)集的預(yù)測(cè)精度，mAcc表示算法在數(shù)據(jù)集的各個(gè)類別上的預(yù)測(cè)精度的平均值，Time表示算法的訓(xùn)練時(shí)間(單位為s).CLPL，PL-ECOC算法的代碼是直接從相關(guān)作者的個(gè)人主頁上下載的，參數(shù)是按照原文提供的方法設(shè)定的.從表2可以看出，雖然CLPL算法的訓(xùn)練時(shí)間要遠(yuǎn)遠(yuǎn)小于其他2個(gè)算法，但是它的預(yù)測(cè)精度也明顯比其他2個(gè)算法差.就本文提出的PL-ECOC-VGP算法和文獻(xiàn)[3]的PL-ECOC算法這2種核方法相比，它們的預(yù)測(cè)精度幾乎相當(dāng)，但是PL-ECOC-VGP算法的訓(xùn)練時(shí)間要遠(yuǎn)遠(yuǎn)小于PL-ECOC算法，對(duì)于特征維數(shù)較低而樣本數(shù)目較大的數(shù)據(jù)集(如Shuttle，Poker-hand)，這種優(yōu)勢(shì)會(huì)越明顯.另外，對(duì)于大部分?jǐn)?shù)據(jù)集，在性能指標(biāo)mAcc上PL-ECOC-VGP算法的結(jié)果要優(yōu)于PL-ECOC算法，而在性能指標(biāo)Acc上PL-ECOC算法的結(jié)果要優(yōu)于PL-ECOC-VGP算法.由于Acc指標(biāo)反映的是整體數(shù)據(jù)集上的精度，而mAcc指標(biāo)可以反映出每個(gè)類別上的預(yù)測(cè)精度，這表明，PL-ECOC-VGP算法側(cè)重在各個(gè)類別上取得較好的精度，而PL-ECOC算法側(cè)重在整體數(shù)據(jù)集上取得較好的精度.換句話說，與PL-ECOC算法相比，PL-ECOC-VGP算法能更好地處理類不平衡問題，這主要是源于我們構(gòu)建的不平衡高斯過程二分類器.

Table 2 The Performance Comparison of Three Partial Label Learning Algorithms on UCI Data Sets

4 結(jié)束語

本文基于ECOC技術(shù)和人們最近提出的變分高斯過程模型建立了一種面向大規(guī)模偏標(biāo)記學(xué)習(xí)問題的快速核分類算法，在6個(gè)UCI數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，本文算法的訓(xùn)練時(shí)間要明顯少于其他核偏標(biāo)記學(xué)習(xí)算法.當(dāng)然，與已有的線性偏標(biāo)記學(xué)習(xí)算法相比，本文算法的訓(xùn)練時(shí)間還是較長(zhǎng)，這主要是由于算法需要訓(xùn)練多個(gè)高斯過程二分類器.下一步將嘗試通過定義新的模型損失函數(shù)的方式來建立面向偏標(biāo)記問題的變分高斯過程算法，這種策略雖然可能會(huì)受到偽標(biāo)記帶來的不利影響，但是由于只需要訓(xùn)練一個(gè)分類器，因此計(jì)算時(shí)間會(huì)極大地降低.此外，目前選取協(xié)方差函數(shù)參數(shù)和誘導(dǎo)子集樣本個(gè)數(shù)的策略不僅效率低而且不能得到最優(yōu)參數(shù)，如何利用模型的邊緣似然自動(dòng)選擇這些參數(shù)也是下一步需要考慮的問題.

[1]Zhang Minling. Research on partial label learning [J]. Journal of Data Acquisition & Processing, 2015, 30(1): 77-87 (in Chinese)(張敏靈. 偏標(biāo)記學(xué)習(xí)研究綜述[J]. 數(shù)據(jù)采集與處理, 2015, 30(1): 77-87)

[2]Cour T, Sapp B, Taskar B. Learning from partial labels [J]. Journal of Machine Learning Research, 2011, 12: 1501-1536

[3]Zhang M. Disambiguation-free partial label learning [C]Proc of the 14th SIAM Int Conf on Data Mining. Philadelphia, PA: SIAM, 2014: 37-45

[4]Luo J, Orabona F. Learning from candidate labeling sets [C]Advances in Neural Information Processing Systems. Montreal, Canada: Neural Information Processing System Foundation, 2010: 1504-1512

[5]Hüllermeier E, Beringer J. Learning from ambiguously labeled examples[J]. Intelligent Data Analysis, 2006, 10(5): 419-439

[6]Liu L, Dietterich T. A conditional multinomial mixture model for superset label learning [C]Advances in Neural Information Processing Systems. Montreal, Canada: Neural Information Processing System Foundation, 2012: 557-565

[7]Zeng Z, Xiao S, Jia K, et al. Learning by associating ambiguously labeled images[C]Proc of the 26th IEEE Int Conf on Computer Vision and Pattern Recognition. Piscataway, NJ: IEEE, 2013: 708-715

[8]Grandvalet Y, Bengio Y. Learning from partial labels with minimum entropy, 2004s-28[R]. Montreal, Canada: Center for Interuniversity Research and Analysis of Organizations, 2004

[9]Fung G, Dundar M, Krishnapuram B, et al. Multiple instance learning for computer aided diagnosis [C]Advances in Neural Information Processing Systems. Cambridge, MA: MIT Press, 2007: 425-432

[10]Grandvalet Y. Logistic regression for partial labels [C]Proc of the 9th Int Conf on Information Processing and Management of Uncertainty in Knowledge-Based Systems. Annecy, France: Institute for the Physics and Mathematics of the Universe, 2002: 1935-1941

[11]Jin R, Ghahramani Z. Learning with multiple labels[C]Advances in Neural Information Processing Systems. Montreal, Canada: Neural Information Processing System Foundation, 2002: 897-904

[13]Nguyen N, Caruana R. Classification with partial labels[C]Proc of the 14th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: Association for Computing Machinery, 2008: 381-389

[14]Li Chengtao, Zhang Jianwen, Chen Zheng. Structured output learning with candidate labels for local parts[G]LNCS 8189: Proc of the European Conf on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECMLPKDD 2013). Berlin: Springer, 2013: 336-352

[15]Zhang Minling, Yu Fei. Solving the partial label learning problem: An instance-based approach[C]Proc of the 24th Int Joint Conf on Artificial Intelligence (IJCAI’15). Menlo Park, CA: AAAI, 2015: 4048-4054

[16]Williams C, Barber D. Bayesian classification with Gaussian processes[J]. IEEE Trans on Pattern Analysis and Machine Intelligence, 1998, 20(12): 1342-1351

[17]Kim H, Ghahramani Z. Bayesian Gaussian process classification with the EM-EP algorithm[J]. IEEE Trans on Pattern Analysis and Machine Intelligence, 2006, 28(12): 1948-1959

[18]Chen M. Kmeans clustering[OL].[2015-08-10]. http:www.mathworks.commatlabcentralfileexchange24616-kmeans-clustering

[19]Nocedal J, Wright S. Numerical Optimization[M]. 2nd ed. Berlin: Springer, 1999: 195-204

[20]Bache K, Lichman M. UCI machine learning repository[OL]. 2013 [2015-08-10]. http:archive.ics.uci.eduml

Zhou Yu, born in 1982. PhD candidate. Her main research interests include machine learning and data mining.

He Jianjun, born in 1983. PhD and associate professor. His main research interests include machine learning and pattern recognition.

Gu Hong, born in 1961. Professor and PhD supervisor. His main research interests include machine learning, big data and bioinformatics.

Fast Kernel-Based Partial Label Learning Algorithm Based on Variational

Gaussian Process ModelZhou Yu1, He Jianjun1,2, and Gu Hong1

1(FacultyofElectronicInformationandElectricalEngineering,DalianUniversityofTechnology,Dalian,Liaoning116024)2(CollegeofInformationandCommunicationEngineering,DalianMinzuUniversity,Dalian,Liaoning116600)

Partial label learning is a weakly-supervised machine learning framework proposed recently. Since it loosens the requirement to training data set, i.e. the learning model can be obtained when each training example is only associated with a candidate set of the ground-truth labels, and partial label learning framework can be used to deal with many real-world tasks more conveniently. The ambiguity in training data inevitably makes partial label learning problem more difficult to be addressed than traditional classification problem, and only several algorithms for small-scale training set are available up to the present. Based on ECOC technology and variational Gaussian process model, this paper presents a fast kernel-based partial label learning algorithm which can deal with large-scale problem effectively. The basic strategy is to convert the original training data set into several standard two-class data sets by using ECOC technology firstly, and then to develop a binary classify with lower computational complexity on each two-class data set by using variational Gaussian process model. The experimental results show that the proposed algorithm can achieve almost the same accuracy as the existing state-of-the-art kernel-based partial label learning algorithms but use shorter computing time. More specifically, the proposed algorithm can deal with the problems with millions samples within 40 minutes on a personal computer.

partial label learning; kernel method; large-scale data; Gaussian process; classification

2015-09-01；

2016-04-28

國(guó)家自然科學(xué)基金項(xiàng)目(61503058,61502074,U1560102)；遼寧省自然科學(xué)基金項(xiàng)目(201602190)；中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金項(xiàng)目(DC201501055，DC201501060201) This work was supported by the National Natural Science Foundation of China (61503058,61502074,U1560102), the Natural Science Foundation of Liaoning Province of China (201602190), and the Fundamental Research Funds for the Central Universities (DC201501055, DC201501060201).

顧宏(guhong@dlut.edu.cn)

TP391