基于變分高斯過程模型的快速核偏標記學習算法

周 瑜 賀建軍,2 顧 宏

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

基于變分高斯過程模型的快速核偏標記學習算法

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

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

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

偏標記學習;核方法;大規(guī)模數(shù)據(jù);高斯過程;分類

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

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

1 算法描述

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

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

(1)

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

(2)

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

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

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

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

(3)

其中，k(x,x′)表示協(xié)方差函數(shù)，本文將使用RBF核α1e-‖x-x′‖2α2作為協(xié)方差函數(shù).利用式(3),可以得到f(x)在訓練樣本集D上的函數(shù)值FD的先驗概率分布p(FD|D)=N(FD|0,KD)，以及f(x)在待預測樣本x*上的函數(shù)值f*=f(x*)關(guān)于FD的條件先驗概率分布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表示預測樣本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) 計算FD的后驗概率分布：

(5)

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

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

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)在訓練樣本集D的一個子集U(U的選取方式見算法實現(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)表示的后驗概率分布p(FD|D,Y)后，后驗概率分布式(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*的后驗概率分布主要與子集U和q(FU|D,Y)=N(FU|μ,Σ)有關(guān)，因此算法的主要計算量來自計算q(FU|D,Y)=N(FU|μ,Σ).

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

(10)

(11)

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

(12)

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

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

(13)

2 算法實現(xiàn)

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

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

訓練階段.

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

forl=1,2,…,Ldo

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

① 隨機生成一個長度為Q的二值編碼向量v∈{-1,+1}Q；

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

③ 如果|Sl|

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

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

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

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

end for

預測階段.

輸出:x*的預測類別.

① 計算K*；

② forl=1,2,…,Ldo

③ 計算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)確定算法對x*的預測類別.

3 仿真實驗

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

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

表2列出了PL-ECOC-VGP，CLPL，PL-ECOC 3個算法在各個控制數(shù)據(jù)集上的性能表現(xiàn)，包括Acc，mAcc，Time三個性能指標，其中，Acc表示算法在整體數(shù)據(jù)集的預測精度，mAcc表示算法在數(shù)據(jù)集的各個類別上的預測精度的平均值，Time表示算法的訓練時間(單位為s).CLPL，PL-ECOC算法的代碼是直接從相關(guān)作者的個人主頁上下載的，參數(shù)是按照原文提供的方法設(shè)定的.從表2可以看出，雖然CLPL算法的訓練時間要遠遠小于其他2個算法，但是它的預測精度也明顯比其他2個算法差.就本文提出的PL-ECOC-VGP算法和文獻[3]的PL-ECOC算法這2種核方法相比，它們的預測精度幾乎相當，但是PL-ECOC-VGP算法的訓練時間要遠遠小于PL-ECOC算法，對于特征維數(shù)較低而樣本數(shù)目較大的數(shù)據(jù)集(如Shuttle，Poker-hand)，這種優(yōu)勢會越明顯.另外，對于大部分數(shù)據(jù)集，在性能指標mAcc上PL-ECOC-VGP算法的結(jié)果要優(yōu)于PL-ECOC算法，而在性能指標Acc上PL-ECOC算法的結(jié)果要優(yōu)于PL-ECOC-VGP算法.由于Acc指標反映的是整體數(shù)據(jù)集上的精度，而mAcc指標可以反映出每個類別上的預測精度，這表明，PL-ECOC-VGP算法側(cè)重在各個類別上取得較好的精度，而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ī)模偏標記學習問題的快速核分類算法，在6個UCI數(shù)據(jù)集上的實驗結(jié)果表明，本文算法的訓練時間要明顯少于其他核偏標記學習算法.當然，與已有的線性偏標記學習算法相比，本文算法的訓練時間還是較長，這主要是由于算法需要訓練多個高斯過程二分類器.下一步將嘗試通過定義新的模型損失函數(shù)的方式來建立面向偏標記問題的變分高斯過程算法，這種策略雖然可能會受到偽標記帶來的不利影響，但是由于只需要訓練一個分類器，因此計算時間會極大地降低.此外，目前選取協(xié)方差函數(shù)參數(shù)和誘導子集樣本個數(shù)的策略不僅效率低而且不能得到最優(yōu)參數(shù)，如何利用模型的邊緣似然自動選擇這些參數(shù)也是下一步需要考慮的問題.

[1]Zhang Minling. Research on partial label learning [J]. Journal of Data Acquisition & Processing, 2015, 30(1): 77-87 (in Chinese)(張敏靈. 偏標記學習研究綜述[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

國家自然科學基金項目(61503058,61502074,U1560102)；遼寧省自然科學基金項目(201602190)；中央高?；究蒲袠I(yè)務(wù)費專項資金項目(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