董露露 謝 飛 章 程
(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.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所示。
張鈴、張鈸教授提出的基于覆蓋的構(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中。用
算法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{
d2=min{
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 (
(1)
式中:sign是符號(hào)函數(shù),li表示ci的覆蓋中心類(lèi)別。若resulti>0,則表示ts落入ci中,即被ci覆蓋。若某測(cè)試樣本未被任何覆蓋包含或同時(shí)被不少于兩個(gè)的覆蓋包含,則采用類(lèi)似于聚類(lèi)的方式,將其并入距離最近的覆蓋。
該算法先通過(guò)距離函數(shù)Hausdorff和CA獲取具有一定代表性的核心示例,再利用相似度函數(shù)將每個(gè)包轉(zhuǎn)為單示例,最后使用CA進(jìn)行學(xué)習(xí)和測(cè)試。
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.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è)試。 從上述算法步驟可以看出,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)。 本文通過(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)。 本節(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ù)能有效地表示這些示例的代表程度。 圖像分類(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)確度。 本文從改變包的表現(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.2.3 轉(zhuǎn)換和分類(lèi)
2.4 時(shí)間和空間復(fù)雜度
3 實(shí)驗(yàn)結(jié)果和分析
3.1 兩類(lèi)數(shù)據(jù)集分類(lèi)
3.2 多類(lèi)圖像分類(lèi)
4 結(jié)束語(yǔ)