多示例學(xué)習(xí)的示例層次覆蓋算法*

董露露　謝　飛　章　程

(1.安徽廣播電視大學(xué)安徽繼續(xù)教育網(wǎng)絡(luò)園區(qū)管理中心, 合肥, 230022;2.合肥師范學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系,合肥,230601;3.安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,合肥,230039)

引　　言

多示例學(xué)習(xí)這一新型機(jī)器學(xué)習(xí)框架是Dietterich等于1997年進(jìn)行藥物分子活性預(yù)測(cè)研究時(shí)提出的[1]。其實(shí)質(zhì)是對(duì)由多個(gè)示例組成的包進(jìn)行學(xué)習(xí)并對(duì)未知標(biāo)記的包進(jìn)行預(yù)測(cè)。目前已在圖像分類(lèi)[2]、圖像檢索[3-5]、視覺(jué)追蹤[6]和行人檢測(cè)[7]等方面得到廣泛的應(yīng)用。

總體來(lái)說(shuō)，多示例學(xué)習(xí)主要分為兩類(lèi)。一類(lèi)從包與示例之間的關(guān)系出發(fā)，尋求解決多示例學(xué)習(xí)問(wèn)題的途徑。1988年，Maron等[8]提出多樣性密度(Diverse density, DD)算法。DD算法通過(guò)多次梯度下降搜索來(lái)求解多樣性密度點(diǎn)，但該算法計(jì)算時(shí)間較長(zhǎng)，效率不高，且并不能確保找到全局最優(yōu)解。Zhang等[9]在DD算法的基礎(chǔ)上，引入期望最大化(Expectation maximization, EM)算法，提出期望最大多樣性密度算法 (Expectation maximization vision of diverse density, EM-DD)。但該算法要通過(guò)不斷迭代獲取多樣性密度最大的示例，且正包中的正示例可能是隨機(jī)分散的，選出的目標(biāo)示例不一定能有效代表所有的正示例，因而會(huì)影響分類(lèi)效果。

另一類(lèi)則通過(guò)對(duì)傳統(tǒng)的單示例學(xué)習(xí)方法進(jìn)行改進(jìn)來(lái)解決多示例問(wèn)題[10]。該類(lèi)方法主要分為兩種，一種是直接為示例加上對(duì)應(yīng)的包的標(biāo)記來(lái)解決多示例問(wèn)題[11]。例如Andrews等[12]將支持向量機(jī)(Support vector machine,SVM)引入多示例學(xué)習(xí),并提出MI-SVM和mi-SVM算法；Zhou以半監(jiān)督學(xué)習(xí)的視角看待多示例學(xué)習(xí)問(wèn)題，并提出基于特殊半監(jiān)督支持向量機(jī)方法的多示例學(xué)習(xí)(Multiple instance learn with semi-super vised SVM,MissSVM)[13]算法；Shao等[14]對(duì)雙支持向量機(jī)進(jìn)行了擴(kuò)展，提出多示例雙支持向量機(jī)(Multi-instance twin support vector machines, MI-TWSVM)算法；Qi等[15]通過(guò)選出正包中很大可能屬于正示例的示例構(gòu)造非平行分類(lèi)器，提出MI-NSVM算法。由于正包中可能存在大量偽正例，這種方法很難有效解決多示例學(xué)習(xí)問(wèn)題。另一種方法則通過(guò)提取核心示例集，將包轉(zhuǎn)化為用特征向量表示的單示例，進(jìn)而使用傳統(tǒng)監(jiān)督算法學(xué)習(xí)。例如Chen等[16]使用DD算法提取每個(gè)包中具有最大多樣性密度的示例，提出DD-SVM算法；Chen等[17]基于一種新型特征映射方法和1-norm支持向量機(jī)模型，提出基于嵌入式示例選擇的多示例學(xué)習(xí)(Multiple instance learning via embedded instance selection,MILES)算法，在實(shí)現(xiàn)特征提取的同時(shí)完成分類(lèi)；Li等[18]利用基于示例類(lèi)別消歧的方法提取核心示例，提出MILD_ B算法；Fu等[19]提出基于示例選擇的多示例學(xué)習(xí)(Multiple instance learning with instance selection,MILIS)算法，該算法使用核密度估計(jì)方法選取核心示例，并通過(guò)一種最優(yōu)化框架來(lái)構(gòu)建分類(lèi)器；Erdem等[20]通過(guò)對(duì)包中的示例建立主導(dǎo)集找到核心示例，提出基于主導(dǎo)集的多示例學(xué)習(xí)(Multiple-instance learning with instance selection via dominant sets,MILDS)算法；Li等[21]基于多核框架將每個(gè)圖像包轉(zhuǎn)為單示例，并使用多核支持向量機(jī)(Multiple-kernels support vector machine,MKSVM)進(jìn)行分類(lèi)，提出MKSVM-MIL算法。 上述關(guān)于提取核心示例集的方法并未考慮所提取示例的代表程度，因而影響了分類(lèi)效果。為此，本文提出一種新的基于示例提取的多示例層次覆蓋算法(Multi-instance learning with a instance-level coering algorithm,MILICA)。該算法利用覆蓋算法[22](Covering algorithm, CA)選出正負(fù)包中具有代表性的示例，并使用覆蓋的示例數(shù)表示所提取示例的代表程度，每個(gè)覆蓋可視為一個(gè)聚類(lèi)，覆蓋中心即為聚類(lèi)的中心。

以上多示例學(xué)習(xí)的研究主要集中于多示例分類(lèi)問(wèn)題。近年來(lái)，非監(jiān)督多示例聚類(lèi)問(wèn)題也開(kāi)始受到研究人員的關(guān)注。Zhang等[23]率先對(duì)非監(jiān)督多示例學(xué)習(xí)問(wèn)題進(jìn)行研究，提出一種包級(jí)多示例聚類(lèi)算法(Bag-level multi-instance clustering,BAMIC)，該算法利用Hausdorff度量計(jì)算包之間的距離，并利用k-Medoids算法將原始的未標(biāo)記的訓(xùn)練集劃分為k個(gè)不相交的子集，每個(gè)子集對(duì)應(yīng)于一組訓(xùn)練包構(gòu)成的簇?；贐AMIC的聚類(lèi)結(jié)果，又提出一種基于包級(jí)轉(zhuǎn)換表示的多示例預(yù)測(cè)算法(Bag-level representation transformation for multi-instance prediction, BARTMIP)。Zhang[24]提出一種用于多示例聚類(lèi)的新的框架M3IC(Maximum margin multiple instance clustering, M3IC)。M3IC致力于在每個(gè)包的至少一個(gè)示例上找到最大化邊緣差距來(lái)實(shí)現(xiàn)多示例聚類(lèi)。上述兩篇文獻(xiàn)的研究重點(diǎn)在于多示例聚類(lèi)，尤其文獻(xiàn)[24]專(zhuān)門(mén)針對(duì)多示例聚類(lèi)問(wèn)題構(gòu)建了一種新的框架。而本文的研究目標(biāo)是得到一種用于多示例分類(lèi)的算法，并盡量確保算法能得到較高的分類(lèi)準(zhǔn)確度，重點(diǎn)是如何抽取出最具有代表性的核心示例。實(shí)驗(yàn)結(jié)果表明，相比于已有的多示例學(xué)習(xí)算法，該算法有效提高了分類(lèi)準(zhǔn)確率。

1　相關(guān)定義和算法

1.1多示例學(xué)習(xí)

在多示例學(xué)習(xí)中，訓(xùn)練集樣本是一個(gè)個(gè)包，包具有類(lèi)別標(biāo)記，每個(gè)包由若干沒(méi)有類(lèi)別標(biāo)記的示例組成。當(dāng)一個(gè)包至少包含一個(gè)正示例時(shí)，稱該包為正包，將其包含的非正例稱為假正例。當(dāng)一個(gè)包中的示例均是負(fù)示例，則稱該包為負(fù)包。多示例學(xué)習(xí)的難點(diǎn)在于訓(xùn)練集中包的標(biāo)記已知，而示例標(biāo)記未知，獲取的信息有限，且正包中含有大量的假正例，從而增加了學(xué)習(xí)的復(fù)雜性[25-26]。多示例學(xué)習(xí)的目標(biāo)是通過(guò)對(duì)訓(xùn)練包進(jìn)行學(xué)習(xí)構(gòu)造基于示例的分類(lèi)器f(x):x→y,x∈χ或者基于包的分類(lèi)器F(X):X→y對(duì)未標(biāo)記的包進(jìn)行分類(lèi)[1-6,27-33]。具體框架如圖1所示。

1.2　覆蓋算法

張鈴、張鈸教授提出的基于覆蓋的構(gòu)造性機(jī)器學(xué)習(xí)方法，簡(jiǎn)稱覆蓋算法[22]。在此給出該算法的完整過(guò)程：給定樣本集D={(vi,li)|i=1,…,m;li=1,…,j}，其中vi和li分別表示第i個(gè)樣本和該樣本的類(lèi)別，vi是d維特征向量，m表示樣本的數(shù)量，j表示樣本的類(lèi)別數(shù)。定義V={V1,V2,…,Vt}為根據(jù)類(lèi)別劃分的樣本集合，其中Vi∈V(i=1,…,j) 為第i類(lèi)的樣本子集。定義C={ci|ci=(centeri,ri,noi),i=1,2,…}表示通過(guò)覆蓋算法得到的球形領(lǐng)域覆蓋集，其中centeri表示覆蓋ci的覆蓋中心，覆蓋中心可作為覆蓋的代表性樣本，ri和noi分別表示ci的覆蓋半徑和覆蓋樣本數(shù)。用flag(v)表示樣本v是否屬于某覆蓋，若flag(v)=1，則表示v落入了某一覆蓋ci中。用表示樣本v和v′的內(nèi)積，該值與兩樣本間的歐氏距離呈反比。算法1給出了CA的訓(xùn)練過(guò)程。

算法1CA的訓(xùn)練過(guò)程

輸入：訓(xùn)練集D1

輸出：覆蓋集C

(2)使用步驟(1)中的轉(zhuǎn)換函數(shù)構(gòu)造映射：v→Hd，其中Hd是d+1維樣本空間的一個(gè)d維球面，據(jù)此產(chǎn)生一個(gè)新的訓(xùn)練集D1；

(3)對(duì)每一個(gè)Vi?D1，隨機(jī)選取一個(gè)樣本v∈Vi且flag(v)=false，計(jì)算

d1=max{|v∈Vi,v′?Vi}

d2=min{|v,v′∈Vi,>d1}

r=(d1+d2)/2

以v(即center=v)為覆蓋中心，以r為半徑，構(gòu)造覆蓋c。之后，計(jì)算落入該覆蓋的樣本數(shù)no。令flag(v) =1和flag(v″)=1，此處v″屬于覆蓋c。將覆蓋c加入C，重復(fù)執(zhí)行上述操作直到對(duì)任意v∈Vi，flag(v) =1。

可見(jiàn)，CA通過(guò)構(gòu)造一個(gè)3層的前向神經(jīng)網(wǎng)絡(luò)獲得覆蓋集C。該神經(jīng)網(wǎng)絡(luò)將樣本向量作為輸入，將C中的各個(gè)覆蓋作為隱層節(jié)點(diǎn)，其輸出層則將隱層輸出采取或門(mén)的方式連接，至此即可得到輸入樣本的標(biāo)記。由于每個(gè)覆蓋包含的樣本均同屬于一個(gè)類(lèi)別，可將一個(gè)覆蓋視為一個(gè)聚類(lèi)，從而可以使用覆蓋的半徑來(lái)衡量相應(yīng)聚類(lèi)的范圍大小，可將覆蓋中心視為聚類(lèi)中心，并根據(jù)覆蓋包含的樣本數(shù)量來(lái)衡量聚類(lèi)中心的代表程度。

對(duì)覆蓋ci∈C和測(cè)試樣本ts，神經(jīng)網(wǎng)絡(luò)的隱層輸出[15,16-31]定義為

resulti=sign (-ri)·li

(1)

式中:sign是符號(hào)函數(shù)，li表示ci的覆蓋中心類(lèi)別。若resulti>0，則表示ts落入ci中，即被ci覆蓋。若某測(cè)試樣本未被任何覆蓋包含或同時(shí)被不少于兩個(gè)的覆蓋包含，則采用類(lèi)似于聚類(lèi)的方式，將其并入距離最近的覆蓋。

2　MILICA算法

該算法先通過(guò)距離函數(shù)Hausdorff和CA獲取具有一定代表性的核心示例，再利用相似度函數(shù)將每個(gè)包轉(zhuǎn)為單示例，最后使用CA進(jìn)行學(xué)習(xí)和測(cè)試。

2.1　符號(hào)說(shuō)明

2.2　核心示例集提取

2.2.1兩類(lèi)問(wèn)題的核心示例提取

(2)

(3)

然后，通過(guò)CA和反驗(yàn)證逐步排除正包中的假正例。先將X-和CIS+中的示例分別標(biāo)記為-1和+1，并通過(guò)CA對(duì)X-和CIS+求覆蓋，將獲得的負(fù)示例和正示例的覆蓋中心集分別記為和。再使用覆蓋中心為XC-的覆蓋對(duì)正包中的示例進(jìn)行反驗(yàn)證，選出其中未被覆蓋且不屬于CIS+的示例組成示例集NC。對(duì)于NC中的每一個(gè)示例nxi，根據(jù)式(4)計(jì)算其與CIS+中所有示例之間的距離d，并選出最小距離作為d。

(4)

對(duì)d由小到大進(jìn)行排序，并據(jù)此調(diào)整對(duì)應(yīng)示例在NC中的位置。即對(duì)NC中任意兩個(gè)示例nxi，nxk，若d(nxi,xj)

從NC中選出前g*h個(gè)示例并入CIS+，而剩余距離較遠(yuǎn)的示例可能是假正例，將其并入X-，從而逐步排除正包中的假正例。當(dāng)g=0時(shí)，將NC中的示例全部歸為X-，當(dāng)g=1.0時(shí)，將NC中的示例全部歸為CIS+。

圖2給出兩類(lèi)樣本的CIS提取過(guò)程。其中，小圓圈和等邊三角形分別表示正包和負(fù)包中的示例。通過(guò)5個(gè)滿足協(xié)方差矩陣為單位矩陣的正態(tài)分布N1～N([5,5]T,I),N2～N([5,-5]T,I),N3～N([-5,5]T,I),N4～N([-5,-5]T,I),N5～N([0,0]T,I)得到各個(gè)示例，這里N([5,5]T,I)表示該正態(tài)分布的平均值為[5,5]T。一個(gè)包為正包當(dāng)且僅當(dāng)其包含的示例源自于N1，N2，N3當(dāng)中的至少兩個(gè)正態(tài)分布，否則該包為負(fù)包。圖2～3均包含6個(gè)正包和6個(gè)負(fù)包，分別使用數(shù)字1～6和7～12來(lái)標(biāo)記，每個(gè)包最多包含8個(gè)示例，且示例與其所在包具有同樣的標(biāo)記。

圖2　原始示例分布　　　　　　　　　　　　圖3　兩類(lèi)問(wèn)題對(duì)應(yīng)的CIS提取過(guò)程　　　Fig．2　Raw instance distributions　　　　　Fig.3　CIS extraction process for two-category problem

圖3中長(zhǎng)方形表示根據(jù)式(3)從正包中選取的初始示例，三角形表示最終獲得的CIS+，大的空心圓表示負(fù)示例覆蓋集CS-，用Ⅰ～Ⅶ標(biāo)記。

從圖2可看到負(fù)包中的示例周?chē)植贾芏嗾械氖纠?，它們很可能是假正例，?yīng)盡可能將其從正包中排除。從圖3可看到選取的初始示例周?chē)休^少負(fù)示例，則這些初始示例很大可能是正示例，應(yīng)首先將其選出。此外，覆蓋Ⅲ包含的示例最多，這就使得對(duì)于任意一個(gè)隨機(jī)選取的測(cè)試示例而言，其被覆蓋Ⅲ包含的概率最大，因此其覆蓋中心的代表程度也就最大。

2.2.2多類(lèi)問(wèn)題的核心示例提取

2.2.1節(jié)中的方法可直接用來(lái)處理兩類(lèi)問(wèn)題的多示例學(xué)習(xí)，但它采用的one-vs-rest策略并不適用于多類(lèi)問(wèn)題的多示例學(xué)習(xí)。one-vs-rest策略選取某一類(lèi)作為正包類(lèi)，剩余的幾類(lèi)作為負(fù)包類(lèi)且其中的示例全部認(rèn)為是負(fù)示例。但在多示例學(xué)習(xí)中，不同類(lèi)別的負(fù)包中的示例之間并無(wú)直接關(guān)系，不能簡(jiǎn)單將其作為一類(lèi)利用CA算法進(jìn)行聚類(lèi)求覆蓋[27]。所以在多類(lèi)問(wèn)題中本節(jié)采用如下方法。

對(duì)于給定的n類(lèi)包，首先將第i類(lèi)作為正包類(lèi)，其余幾類(lèi)作為負(fù)包類(lèi)，通過(guò)式(3)從每個(gè)正包中選出一個(gè)示例組成第i類(lèi)的初始示例集CISi。然后利用CA對(duì)CISi與負(fù)包中的負(fù)示例求覆蓋，求覆蓋時(shí)應(yīng)將負(fù)包中的示例按其原始類(lèi)別單獨(dú)求覆蓋，而非將其作為一類(lèi)求覆蓋。接著使用式(4)和反驗(yàn)證從第i類(lèi)正包中選出未被負(fù)類(lèi)覆蓋且不屬于CISi的示例，這些示例組成的集合用NCi表示。采用2.2.1節(jié)中的方法調(diào)整NCi中示例的位置，并根據(jù)參數(shù)g更新CISi。最后使用CA對(duì)CISi與負(fù)包中的示例求覆蓋，將得到的第i類(lèi)的覆蓋中心作為最終的CISi。重復(fù)上述步驟，依次提取其余幾類(lèi)的CISi得到CIS

(5)

2.3　轉(zhuǎn)換和分類(lèi)

由2.2節(jié)得到的核心示例集CIS和覆蓋的示例數(shù)集no定義一個(gè)相似度函數(shù)，即計(jì)算xk與包Xi中距離最近的示例之間的相似度，則

(6)

式中參數(shù)σ與核心示例間的平均距離有關(guān)，exp為以自然數(shù)為底的指數(shù)函數(shù)。

對(duì)于給定的包Xi，在得到其與xk的相似度之后，根據(jù)式(7)將其表示為一個(gè)單示例。該單示例是一個(gè)k++k-維的特征向量，且其標(biāo)記和包的標(biāo)記相同。

(7)

對(duì)于多類(lèi)問(wèn)題，由式(4,5)得到CIS和no后，定義轉(zhuǎn)換函數(shù)為

(8)

與兩類(lèi)問(wèn)題一樣，包的標(biāo)記與其轉(zhuǎn)換后得到的示例的標(biāo)記相同。完成上述轉(zhuǎn)換后，就可以用CA進(jìn)行多示例分類(lèi)了。

算法2給出兩類(lèi)問(wèn)題的MILICA算法的訓(xùn)練過(guò)程。因?yàn)槎囝?lèi)問(wèn)題僅在CIS的提取上有所不同，其余過(guò)程和兩類(lèi)問(wèn)題一致，所以文中并未介紹其訓(xùn)練過(guò)程。

算法2MILICA算法的訓(xùn)練過(guò)程

輸出:CIS和CS

(1)將訓(xùn)練集中的正包(負(fù)包)標(biāo)記為+1(-1)；

(2)利用公式(3)從正包中選出m+個(gè)正示例組成初始的CIS+；

(3)通過(guò)CA對(duì)CIS+和負(fù)包中的全部示例求覆蓋，得到覆蓋中心集合和，并利用對(duì)正包中的示例進(jìn)行反驗(yàn)證，更新和；

(4)對(duì)和X-重新求覆蓋，得到CIS和no，然后利用式(6)和式(7)將每個(gè)包轉(zhuǎn)為單示例，其標(biāo)記與包一致；

(5)對(duì)轉(zhuǎn)換后的示例求覆蓋得到覆蓋集CS。

測(cè)試時(shí)，先利用式(6,7)將每個(gè)測(cè)試包轉(zhuǎn)換為單示例，之后利用學(xué)習(xí)過(guò)程得到的CS進(jìn)行測(cè)試。

2.4　時(shí)間和空間復(fù)雜度

從上述算法步驟可以看出，MILCA需要根據(jù)式(2，3)計(jì)算每個(gè)示例與所有示例之間的距離以構(gòu)建核心示例，根據(jù)式(6，7，8)計(jì)算核心示例與各個(gè)包中距離最近示例之間的相似度以便對(duì)包進(jìn)行轉(zhuǎn)換。因此，MILCA的時(shí)間和空間復(fù)雜度均為O(e2)，其中e為總的示例數(shù)?？梢?jiàn)，本文算法與DD，EM-DD和DD-SVM等經(jīng)典算法相比，未產(chǎn)生額外的時(shí)間和空間開(kāi)銷(xiāo)。

3　實(shí)驗(yàn)結(jié)果和分析

本文通過(guò)2組不同的數(shù)據(jù)集對(duì)MILICA算法進(jìn)行了實(shí)驗(yàn)。第1組使用僅包含正包和負(fù)包的兩類(lèi)數(shù)據(jù)集，第2組使用多類(lèi)圖像數(shù)據(jù)集。實(shí)驗(yàn)中的參數(shù)σ=linspace(0.6μ,1.4μ,10)。其中，linspace(a,b,n)表示在a和b之間等間隔的取n個(gè)值，包括a和b。μ為CIS中每?jī)蓚€(gè)示例之間歐式距離的平均值，本實(shí)驗(yàn)中μ的取值分別為5,10,15,20,25,30,35,40,45和50。g=0,0.2,0.4, 0.6,0.8和1.0，即每次選取6個(gè)不同的g值進(jìn)行實(shí)驗(yàn)。

3.1　兩類(lèi)數(shù)據(jù)集分類(lèi)

本節(jié)使用多示例學(xué)習(xí)中5個(gè)常用數(shù)據(jù)集衡量MILICA算法，分別為Musk1，Musk2，Elephant，F(xiàn)ox，Tiger，其中Musk1和Musk2是藥物分子活性預(yù)測(cè)數(shù)據(jù)集[1]，Elephant，F(xiàn)ox及Tiger分別代表大象、狐貍和老虎3類(lèi)不同的多示例圖像集。表1給出5個(gè)數(shù)據(jù)集的詳細(xì)信息。

實(shí)驗(yàn)采用10次10-fold CV(10交叉驗(yàn)證)方法進(jìn)行，且每次交叉驗(yàn)證均通過(guò)調(diào)整σ得到不同的核心示例集，最終結(jié)果即10次交叉驗(yàn)證結(jié)果的算數(shù)平均值。表2給出不同g值下MILICA算法得到的平均分類(lèi)準(zhǔn)確度。為驗(yàn)證本文所提算法MILICA的有效性，將其與MILDS，MILIS，DD-SVM等經(jīng)典算法的實(shí)驗(yàn)結(jié)果進(jìn)行對(duì)比分析。表3給出了MILICA算法在5個(gè)數(shù)據(jù)集上得到的平均份額里準(zhǔn)確度及95%的置信區(qū)間，同時(shí)也給出了其他12個(gè)算法的分類(lèi)結(jié)果。對(duì)比算法中，除MILIS使用15次10-fold CV(10交叉驗(yàn)證)外，其余均采用10次10-fold CV。對(duì)比算法的結(jié)果按表3中從上到下的順序分別取自文獻(xiàn)[8,9,12～14,16,17,19,20,34]。表3按照算法是否基于核心示例提取的思想分為3部分，其中，核心示例提取算法的分類(lèi)結(jié)果位于第2～7行，非示例提取算法的分類(lèi)結(jié)果位于第8～12行，除本文算法MILICA之外的其余算法在各個(gè)數(shù)據(jù)集上平均分類(lèi)準(zhǔn)確度的均值位于最后一行。表2中當(dāng)g=0.2時(shí)，MILICA在Tiger數(shù)據(jù)集上取得85.1%的準(zhǔn)確度；g=0.6時(shí)，MILICA在Musk2數(shù)據(jù)集上取得91.4%的準(zhǔn)確度；g=0.8時(shí)，MILICA在Fox數(shù)據(jù)集上取得65.9%的準(zhǔn)確度；g=1.0時(shí)，MILICA在Elephant數(shù)據(jù)集上取得85.0%的準(zhǔn)確度。

從表3可以看出，MILICA算法在5個(gè)數(shù)據(jù)集上的準(zhǔn)確度比其他MIL算法的平均值都至少高出2.4%，特別是在Tiger上更是高出6.6%，相應(yīng)的95%的置信區(qū)間也小于其他算法。其中，在Musk1上，MILICA算法的分類(lèi)準(zhǔn)確度為90.7%，僅低于MI-TSVM，明顯高于其他示例提取算法。在其余4個(gè)數(shù)據(jù)集上，MILCA都取得最高的分類(lèi)準(zhǔn)確率。非示例提取算法DD，mi-SVM，MI-SVM，EM-DD和MissSVM在5個(gè)數(shù)據(jù)集上的準(zhǔn)確度均低于MILICA。

表1兩類(lèi)數(shù)據(jù)集的詳細(xì)信息

Tab.1Detailinformationoftwo-categorydatasets

數(shù)據(jù)集正包/負(fù)包數(shù)平均示例數(shù)/包維數(shù)Musk147/455．17166Musk239/6364．69166Elephant100/1006．96230Fox100/1006．60230Tiger100/1006．10230

表2不同g值下MILICA算法在標(biāo)準(zhǔn)數(shù)據(jù)集上的平均分類(lèi)準(zhǔn)確度

Tab.2AverageclassificationaccuracyofMILICAoverdifferentvaluesofgonbenchmarkdatasets

%

表3　不同MIL算法在標(biāo)準(zhǔn)數(shù)據(jù)集上的分類(lèi)結(jié)果比較

由實(shí)驗(yàn)結(jié)果可以看出，與其他MIL算法相比，MILICA算法表現(xiàn)出了更好的分類(lèi)性能，驗(yàn)證了MILICA算法在解決多示例學(xué)習(xí)問(wèn)題方面的有效性。究其原因，主要是MILICA能提取出具有代表性的示例，并且覆蓋的示例數(shù)能有效地表示這些示例的代表程度。

3.2　多類(lèi)圖像分類(lèi)

圖像分類(lèi)是多示例學(xué)習(xí)最成功的應(yīng)用領(lǐng)域之一。為衡量本文算法在多示例圖像分類(lèi)中的作用，本節(jié)實(shí)驗(yàn)選用20類(lèi)JPEG格式的圖像集，每類(lèi)100幅，共計(jì)2 000幅，均來(lái)自COREL圖像庫(kù)。將每幅圖像作為一個(gè)包，包中的示例即表征圖像區(qū)域特征的顯著特征點(diǎn)，每個(gè)特征點(diǎn)由一個(gè)9維的特征向量表示。表4給出了COREL數(shù)據(jù)集的詳細(xì)信息。

本組實(shí)驗(yàn)分兩部分進(jìn)行，分別選用前10類(lèi)共計(jì)1 000幅和全部20類(lèi)共計(jì)2 000幅圖像進(jìn)行訓(xùn)練和測(cè)試。實(shí)驗(yàn)中，從每類(lèi)圖像集中隨機(jī)選取50%用于訓(xùn)練，其余的用于測(cè)試。實(shí)驗(yàn)采用5次2-fold CV方法進(jìn)行，且每次通過(guò)調(diào)整參數(shù)σ的值獲得不同的核心示例集，取5次交叉驗(yàn)證結(jié)果的平均值作為最終的結(jié)果。表5給出MILICA的不同g值對(duì)應(yīng)的平均分類(lèi)準(zhǔn)確度。表6為MILICA和其他10種算法的平均分類(lèi)準(zhǔn)確度和95%的置信區(qū)間的比較。其中，比較算法的結(jié)果分別取自文獻(xiàn)[12,13,16,17,19～21,35]給出的最好結(jié)果。表8按照算法是否基于核心示例提取的思想分為3部分，其中，基于示例提取的算法對(duì)應(yīng)于第2～7行，非示例提取算法對(duì)應(yīng)于第8～11行，除本文算法之外的其余算法在各個(gè)數(shù)據(jù)集上的平均分類(lèi)準(zhǔn)確度的均值對(duì)應(yīng)于最后一行Average的值。表5和表6中粗體字為表中最好的結(jié)果。

觀察表5發(fā)現(xiàn)，當(dāng)g=0.2和g=0.8時(shí)，MILICA分別在1 000幅和2 000幅圖像上得到最高的分類(lèi)精度，為86.9%和72.6%，表2的準(zhǔn)確度高于表5列出的其他多示例學(xué)習(xí)算法。

從表6可知，MILICA算法在2 000幅圖像上的分類(lèi)準(zhǔn)確度低于1 000幅。這是因?yàn)榍罢甙烁嗟脑肼暿纠沟锰崛『诵氖纠倪^(guò)程受到干擾，從而弱化了分類(lèi)預(yù)測(cè)的結(jié)果。同時(shí)，某些類(lèi)別的圖像存在很多視覺(jué)上的相似、語(yǔ)義上關(guān)聯(lián)的區(qū)域，例如沙灘、山川和瀑布均含有水，也會(huì)降低分類(lèi)準(zhǔn)確度。

從實(shí)驗(yàn)結(jié)果還可以看出，基于示例提取的算法在兩組圖像數(shù)據(jù)集上的準(zhǔn)確度均高于非示例提取算法，這說(shuō)明所選取的示例對(duì)類(lèi)別的正確判斷具有顯著作用。MILICA在前1 000幅和2 000幅圖像上的平均分類(lèi)準(zhǔn)確度均高于表6中其他所有算法，且比其余算法的準(zhǔn)確度平均值分別高出7.4%和8.5%，相應(yīng)的95%的置信區(qū)間均小于表6中其他算法。這表明本文提出的MILICA算法不僅適用于解決兩類(lèi)多示例問(wèn)題，在多類(lèi)圖像分類(lèi)問(wèn)題中也有效。

表4每類(lèi)圖像提取得到的平均示例數(shù)

Tab.4Averagenumbersofinstancesextractedfromeachkindofimage

編號(hào)圖像類(lèi)名稱示例數(shù)/包0非洲土著居民4．841沙灘3．542建筑物3．103公共汽車(chē)7．594恐龍2．005大象3．026鮮花4．467馬3．898山川3．389食物7．2410狗3．8011蜥蜴2．8012時(shí)裝模特5．1913夕陽(yáng)3．5214小轎車(chē)4．9315瀑布2．5616家具2．3017戰(zhàn)艦4．3218滑雪3．3419沙漠3．65

表5不同g值下MILCA在Corel圖像數(shù)據(jù)集上的平均分類(lèi)準(zhǔn)確度

Tab.5　Average classification accuracy of MILIA over different values of g on the Corel datasets %

表6不同算法在Corel圖像數(shù)據(jù)集上的分類(lèi)結(jié)果比較

Tab.6　Comparison of the performance of various MIL algorithms on the Corel datasets %

從表2和表5可看出，在多數(shù)數(shù)據(jù)集上并非當(dāng)g=0或1.0時(shí)取得最好的效果，通過(guò)不斷排除正包中的假正例，選出適當(dāng)數(shù)量的具有代表性的示例有利于提高分類(lèi)準(zhǔn)確度。

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

本文從改變包的表現(xiàn)形式出發(fā)，結(jié)合核心示例提取方法，提出MILCA算法。該算法首先利用距離函數(shù)Hausdorff和CA構(gòu)造初始核心示例集，然后使用CA算法計(jì)算這些示例的代表程度，降低假正例對(duì)分類(lèi)效果的影響，并得到最終的核心示例集；最后利用核心示例集將包轉(zhuǎn)變成向量的形式，從而將多示例學(xué)習(xí)轉(zhuǎn)為監(jiān)督單示例學(xué)習(xí)。實(shí)驗(yàn)結(jié)果表明，與已有的多示例學(xué)習(xí)方法相比，MILCA算法取得了較好的效果。未來(lái)的工作是研究如何更有效地選取初始示例，并對(duì)提取的核心示例集進(jìn)行約簡(jiǎn)，以及嘗試其他方法計(jì)算所提取示例的代表程度，并將其應(yīng)用于多示例多標(biāo)簽學(xué)習(xí)。

參考文獻(xiàn):

[1]Dietterich T G, Lathrop R H, Lozano-Pérez T. Solving the multiple instance problem with axis-parallel rectangles[J]. Artificial Intelligence, 1997, 89(1/2):31-71.

[2]Li Daxiang, Wang Jing, Zhao Xiaoqiang. Multiple kernel-based multi-instance learning algorithm for image classification[J]. Journal of Visual Communication and Image Representation, 2014, 25(5):1112-1117.

[3]Zafra A, Pechenizkiy M, Ventura S. ReliefF-MI:An extension of relief to multiple instance learning[J]. Neurocomputing, 2012, 75(1):210-218.

[4]Wu Jia, Zhu Xingquan, Zhang Chenqi, et al. Multi- instance learning from positive and unlabeled bags[C]// 18th PAKDD: Advances in Knowledge Discovery and Data Mining. Switzerland: Springer International Publishing, 2014:237-248.

[5]Ding Xinmiao, Li Bing, Xiong Weihua, et al. Multi-instance multi-label learning combining hierarchical context and its application to image annotation[J]. IEEE Transactions on Multimedia, 2016, 18(8):1616-1627.

[6]Babenko B, Yang M H, Belongie S. Robust object tracking with online multiple instance learning[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011, 33 (8):1619-1632.

[7]Qi Zhiquan, Xu Yitian, Wang Laisheng, et al. Online multiple-instance boosting for object detection[J]. Neurocomputing, 2011, 74 (10):1769-1775.

[8]Maron O, Lozano- Pérez T. A framework for multiple-instance learning[C]// Advances in Neutral Information Processing Systems 10 (NIPS′97). Cambridge, MA: MIT Press, 1998:570-576.

[9]Zhang Q, Goldman A S. EM-DD:An improved multi-instance learning technique[C]// Advances in Neutral Information Processing Systems 14. Cambridge, MA: MIT Press, 2002:1073-1080.

[10] Wang Xinqi, Wei Dan, Cheng Hui, et al. Multi-instance learning based on representative instance and feature mapping[J]. Neurocomputing, 2016, 216:790-796.

[11] Vanwinckelen G, Tragante do O V, Fierens D, et al. Instance-level accuracy versus bag-level accuracy in multi-instance learning[J]. Data Mining and Knowledge Discovery, 2016, 30(2):313-341.

[12] Andrews S, Tsochantaridis I, Hofmann T. Support vector machines for multiple-instance learning[C]// Advance in Neutral Information Processing System.[S.l.]:IEEE,2003:561- 568.

[13] Zhou Zhihua, Xu Junming. On the relation between multi-instance learning and semi-supervised learning[C]// Proceedings of the 24th ICML. Corvalis, Oregon:ICML, 2007:1167-1174.

[14] Shao Yuanhai, Yang Zhixia, Wang Xiaobo, et al. Multiple instance twin support vector machines[J]. ISORA, 2010(8):433-442.

[15] Qi Zhiquan, Tian Ying, Yu Xiaodan, et al. A multi-instance learning algorithm based on nonparallel classifier[J]. Applied Mathematics and Computation, 2014,241:233-241.

[16] Chen Yixin, Wang J Z. Image categorization by learning and reasoning with regions[J]. Journal of Machine Learning Research, 2004,5(8):913-939.

[17] Chen Yixing, Bi Jin Bo, Wang J Z, et al. MILES: Multiple- instance learning via embedded instance selection[J]. IEEE Transaction Pattern Analysis and Machine Intelligence, 2006, 28(12): 1931-1947.

[18] Li Wujun, Yeung D Y. MILD: Multiple-instance learning via disambiguation[J]. IEEE Trans on Knowledge and Data Engineer, 2010, 22(1):76-89.

[19] Fu Zhouyu, Robles-Kelly A, Zhou Jun. MILIS: Multiple instance learning with instance selection[J]. IEEE Transaction Pattern Analysis and Machine Intelligence, 2011, 33(5): 958-977.

[20] Erdem A, Erdem E. Multiple-instance learning with instance selection via dominant sets[J]. Similarity-Based Pattern Recognition, 2011, 7005:171-191.

[21] Li Daxiang, Wang Jing, Zhao Xiaoqiang, et al. Multiple kernel-based multi-instance learning algorithm for image classification[J]. Journal of Visual Communication and Image Representation, 2014, 25(5):1112-1117.

[22] 張鈴，張鈸. M-P神經(jīng)元模型的幾何意義及其應(yīng)用[J]. 軟件學(xué)報(bào), 1999, 9(5):925-929.

Zhang Ling, Zhang Ba. A geometrical representation of M-P neural model and its applications[J]. Journal of Software, 1999, 9(5):925-929.

[23] Zhang Minling, Zhou Zhihua. Multi-instance clustering with applications to multi-instance prediction[J]. Applied Intelligence, 2009, 31(1):47-68.

[24] Zhang Dan, Wang Fei, Si Luo, et al. Maximum margin multiple instance clustering with its applications to image and text clustering[J]. IEEE Trans Neural Networks, 2011, 22(5):739-751.

[25] 張敏靈. 偏標(biāo)記學(xué)習(xí)研究綜述[J].數(shù)據(jù)采集預(yù)處理，2015, 3(1):77-87.

Zhang Minling. Research on partial label learning[J]. Journal of Data Acquisition and Processing, 2015, 30(1):77-87.

[26] 甘睿，印鑒. 通過(guò)挖掘示例中的概念來(lái)解決多示例學(xué)習(xí)問(wèn)題[J]. 軟件學(xué)報(bào)，2011，48(S2):73-78.

Gan Rui, Yin Jian. Solving multi-instance learning problem with mining concept in instances[J]. Journal of Computer Research and Development, 2011, 48(S2):73-78.

[27] Zhou Zhihua, Sun Yuyin, Li Yufeng. Multi-instance learning by treating instance as Non-I.I.D samples[C]// Proceedings of the 26th International Conference on Machine Learning. New York: ACM Press, 2009:1249-1256.

[28] Zhao Shu, Rui Chen, Zhang Yanping. MICkNN: Multi-instance covering kNN algorithm[J]. Tsinghua Science and Technology, 2013, 18(4):360-368.

[29] Zhang Minglin, Huang Shengjun. Multi-instance multi-label learning[J]. Artificial Intelligence, 2012, 176(1):2291-2320.

[30] Hajimirsadeghi H, Mori G. Multi-Instance classification by max-margin training of cardinality-based markow networks[J]. IEEE Transactions On Pattern Analysis And Machine Intellgence,2016, 99(3):1-15.

[31] Xu Y Y. Multiple-instance learning based decision neural networks for image retrieval and classification[J]. Neurocomputing, 2016, 171(1):826-836.

[32] Li Yan, Tax D, Duin R, et al. Multiple-instance learning as a classifier combining problem[J]. Pattern Recognition, 2013, 46(3):865-874.

[33] Doran G, Ray S. Multiple-instance learning from distributions[J]. Journal of Machine Learning Research, 2016, 17(128):1-50.

[34] Liu Qiang, Zhou Sihang, Zhu Chengzhang, et al. MI-ELM: Highly efficient multi-instance learning based on hierarchical extreme learning machine[J]. Neurocomputing, 2016, 173:1044-1053.

[35] Csurka G, Bray C, Dance C, et al. Visual categorization with bags of keypoints[C]// Proc ECCV Workshop on Statistical Learning in Computer Vision. Prague, Czech:[s.n.], 2004:59-74.