文獻(xiàn)標(biāo)識(shí)碼: A
DOI:10.16157/j.issn.0258-7998.190243
中文引用格式: 李村合,,張振凱,,朱洪波. 基于半監(jiān)督學(xué)習(xí)的多示例多標(biāo)簽改進(jìn)算法[J].電子技術(shù)應(yīng)用,2019,,45(7):32-35,,39.
英文引用格式: Li Cunhe,Zhang Zhenkai,,Zhu Hongbo. A multi-instance multi-label improved algorithm based on semi-supervised learning[J]. Application of Electronic Technique,,2019,45(7):32-35,,39.
0 引言
對(duì)于監(jiān)督學(xué)習(xí),,通過(guò)訓(xùn)練集中已知類(lèi)樣本學(xué)習(xí)構(gòu)造一個(gè)判決邊界,,并設(shè)定臨閾值,來(lái)實(shí)現(xiàn)對(duì)未知樣本的預(yù)測(cè)[1]。通常使用一個(gè)示例描述單個(gè)對(duì)象并與其類(lèi)別相關(guān)聯(lián),。但是,,實(shí)際上每個(gè)對(duì)象都可能不止有一個(gè)語(yǔ)義,如一幅含有獅子,、大象,、草原的圖,可以將其歸為“大象”類(lèi)別,,也可以將其歸為“獅子”類(lèi)別,,甚至可以因?yàn)閯?dòng)物和草原的存在將其歸為“非洲”的類(lèi)別。因此,,當(dāng)僅通過(guò)一個(gè)示例來(lái)表示一個(gè)對(duì)象時(shí),,顯然難以獲得期望的效果,。為了處理這個(gè)難題,,相關(guān)學(xué)者提出了多示例多標(biāo)簽(Multi-Instance Multi-Label,MIML)[2]機(jī)器學(xué)習(xí)模型,,最大特點(diǎn)是:在該框架中是用一組示例集合來(lái)表示一個(gè)對(duì)象,,同時(shí)該對(duì)象與多個(gè)標(biāo)簽相關(guān)聯(lián)。對(duì)于真實(shí)世界中對(duì)象的表示能力更強(qiáng),,其他的機(jī)器學(xué)習(xí)框架可以看作是多示例多標(biāo)簽框架的一種簡(jiǎn)化表示形式,。
支持向量機(jī)(Support Vector Machine,SVM)是建立在統(tǒng)計(jì)學(xué)習(xí)理論基礎(chǔ)上的一種機(jī)器學(xué)習(xí)方法,,其泛化準(zhǔn)確率高,,計(jì)算效率高,結(jié)果易解釋[3],。傳統(tǒng)的SVM多為監(jiān)督學(xué)習(xí),,然而在實(shí)際中,有標(biāo)簽的樣本數(shù)據(jù)是稀少的,,無(wú)標(biāo)簽的樣本數(shù)據(jù)的獲取相對(duì)較易,。半監(jiān)督學(xué)習(xí)即通過(guò)將無(wú)標(biāo)簽樣本數(shù)據(jù)加入訓(xùn)練集中,對(duì)其學(xué)習(xí)建模來(lái)增強(qiáng)模型的泛化性能,。因此,,出現(xiàn)了將半監(jiān)督學(xué)習(xí)和SVM方法進(jìn)行結(jié)合來(lái)訓(xùn)練分類(lèi)函數(shù)的研究。
1 相關(guān)工作
傳統(tǒng)監(jiān)督學(xué)習(xí)是一種單示例單標(biāo)記學(xué)習(xí)框架,。學(xué)習(xí)任務(wù)是學(xué)得一個(gè)映射函數(shù):f:X→Y,。
在多示例學(xué)習(xí)問(wèn)題中[2],用包含一組示例的集合來(lái)表示訓(xùn)練集中的每個(gè)對(duì)象,,同時(shí)將該對(duì)象歸屬于單個(gè)類(lèi)別標(biāo)簽中,。該模型主要學(xué)習(xí)一個(gè)分類(lèi)器(即映射函數(shù)fMIL:2x→Y)來(lái)標(biāo)記未知的示例包的標(biāo)簽。代表性的多示例學(xué)習(xí)算法有多示例最近鄰算法Citation-kNN、多示例神經(jīng)網(wǎng)絡(luò)算法BP-MIP等[4],。
在多標(biāo)簽學(xué)習(xí)問(wèn)題中[2],,對(duì)象僅由單個(gè)示例表示,并屬于一組標(biāo)簽,。該框架模型的任務(wù)是學(xué)習(xí)fMIL:x→2Y函數(shù)的映射,,然后使用此映射來(lái)預(yù)測(cè)未知集合中的標(biāo)簽類(lèi)別。代表性的多標(biāo)簽學(xué)習(xí)算法有二元相關(guān)(BR)算法和分類(lèi)器鏈(CC)算法[5]等,。
在MIML框架下,,有兩種解決問(wèn)題的方式,一種是應(yīng)用退化的方式,,以多示例學(xué)習(xí)或多標(biāo)簽學(xué)習(xí)作為橋梁,,對(duì)MIML問(wèn)題進(jìn)行退化,如MIMLSVM[6]和MIMLSVM+[7]等,。但是在退化時(shí),,有時(shí)標(biāo)簽間的關(guān)聯(lián)信息會(huì)被忽視,進(jìn)而影響到實(shí)際的分類(lèi)效果,。為了避免信息丟失,,另一種思路是改造算法找到適應(yīng)MIML框架的機(jī)器學(xué)習(xí)算法。代表性算法主要有D-MIMLSVM算法,、M3MIML算法[8]等,。
2 改進(jìn)的算法
2.1 E-MIMLSVM+算法
2.2 E-MIMLSVM+算法中引入半監(jiān)督
半監(jiān)督學(xué)習(xí)即把大量無(wú)標(biāo)記的數(shù)據(jù)和少量有標(biāo)記的數(shù)據(jù)一塊訓(xùn)練,構(gòu)建起泛化性能強(qiáng)的分類(lèi)器,,有標(biāo)簽的數(shù)據(jù)和無(wú)標(biāo)簽的數(shù)據(jù)的空間結(jié)構(gòu)分布相似,,應(yīng)用無(wú)標(biāo)簽的樣本來(lái)訓(xùn)練,有助于提高訓(xùn)練出模型的性能,。
半監(jiān)督SVM屬于半監(jiān)督領(lǐng)域中的學(xué)習(xí)算法,,它基于SVM和半監(jiān)督學(xué)習(xí)的聚類(lèi)假設(shè),嘗試尋找能將兩類(lèi)有標(biāo)簽樣本分隔,,并且通過(guò)穿過(guò)低密度區(qū)域來(lái)劃分超平面,,如此一來(lái)就能同時(shí)利用有標(biāo)簽的數(shù)據(jù)和無(wú)標(biāo)簽的數(shù)據(jù)。半監(jiān)督SVM中最經(jīng)典的是TSVM和S3VM[13],。通過(guò)文獻(xiàn)[13]對(duì)類(lèi)中心的有效性分析可以獲得基于類(lèi)中心估計(jì)的半監(jiān)督支持向量機(jī)meanS3VM,。它只需要最大化兩個(gè)類(lèi)的類(lèi)別平均值,來(lái)代替之前對(duì)所有的未標(biāo)記樣本進(jìn)行標(biāo)記的方式,。這很大程度上提升了半監(jiān)督SVM的求解速度,。
假設(shè)存在有標(biāo)記的樣本集Dl={(x1,y1),,(x2,,y2),,…,(xi,,yi)},,未標(biāo)記的樣本集Du={xl+1,xl+2,,…,,xl+u},meanS3VM算法[13]可形式化定義為:
通過(guò)分析可以得到,,式(7)只需要估計(jì)無(wú)標(biāo)簽樣本的類(lèi)別平均值即可,。與S3VM相比,meanS3VM避免了對(duì)所有未標(biāo)記樣本類(lèi)別標(biāo)簽的估計(jì),。實(shí)際上,,meanS3VM算法最大化了兩個(gè)類(lèi)的類(lèi)別平均值。由于meanS3VM算法大量減少了約束條件的個(gè)數(shù),,因此,,對(duì)半監(jiān)督SVM的求解速度更快了,從而使得半監(jiān)督SVM的時(shí)間開(kāi)銷(xiāo)變少,??梢宰C明[14],當(dāng)給定樣本集可分時(shí),,meanS3VM的損失函數(shù)與標(biāo)準(zhǔn)SVM一致;當(dāng)給定樣本集不可分時(shí),,meanS3VM的損失函數(shù)不會(huì)超過(guò)標(biāo)準(zhǔn)支持向量機(jī)hinge損失的兩倍,。
為了充分利用未標(biāo)記樣本的空間分布信息,來(lái)進(jìn)一步提升分類(lèi)器的泛化性能,,在本文中,,使用半監(jiān)督SVM算法——meanS3VM對(duì)E-MIMLSVM+算法進(jìn)行了改進(jìn)。由于meanS3VM算法適用于傳統(tǒng)的半監(jiān)督學(xué)習(xí)問(wèn)題,,本文改進(jìn)了meanS3VM算法中核函數(shù)的計(jì)算方式,,用多示例核函數(shù)進(jìn)行替代。使得meanS3VM算法能夠適用于多示例多標(biāo)簽學(xué)習(xí)中,,從而得到改進(jìn)算法SE-MIMLSVM+,。令給定有標(biāo)簽樣本集S={(Xi,Yi)|1≤i≤l},,無(wú)標(biāo)簽樣本集U={(Xi,,Yi)|l+1≤i≤l+μ},測(cè)試樣本集T={(Xi,,Yi)|1≤i≤M},,則SE-MIMLSVM+算法的優(yōu)化問(wèn)題變?yōu)椋?/p>
其中,ξiy和ρ分別代表的是有標(biāo)簽數(shù)據(jù)和無(wú)標(biāo)簽數(shù)據(jù)的松弛變量,W0反映了不同任務(wù)間的共同特征,,vy反映了不同任務(wù)間的區(qū)別,,參數(shù)μ用于協(xié)調(diào)不同任務(wù)間的相似程度。從式(4)建立的模型可以看出,,每一個(gè)分類(lèi)模型fy都有一個(gè)共同的參數(shù)w0,,也就是說(shuō)分類(lèi)模型假設(shè)每一個(gè)標(biāo)簽相互都是有關(guān)聯(lián)關(guān)系的。但是實(shí)際的情況是,,并非所有標(biāo)簽都存在關(guān)聯(lián)關(guān)系,。因此可以先在標(biāo)簽空間中聚類(lèi),從而將標(biāo)簽空間劃分成許多具有標(biāo)簽相關(guān)性的子集,,每一個(gè)示例包和標(biāo)簽之間的標(biāo)簽指示陣表示為Y,。為了衡量標(biāo)簽之間的聯(lián)系信息,在聚類(lèi)的過(guò)程中使用的是Y列上的皮爾遜相關(guān)系數(shù),。
2.3 改進(jìn)算法步驟
因?yàn)棣睾蚫的雙線性約束,,所以式(7)是一個(gè)非凸優(yōu)化模型??梢允褂猛顾沙谒惴ɑ蚪惶鎯?yōu)化算法得到未標(biāo)記樣本估計(jì)好的類(lèi)中心然后帶入式(7)將其變?yōu)橥箖?yōu)化問(wèn)題,,使用凸優(yōu)化軟件包求解。這里選擇使用求解速度更快的交替優(yōu)化算法來(lái)處理相關(guān)問(wèn)題,。
SE-MIMLSVM+的算法流程如下:
①使用有標(biāo)簽的樣本Sk訓(xùn)練SVM分類(lèi)器,。
②使用訓(xùn)練出來(lái)的SVM分類(lèi)器對(duì)未標(biāo)記的樣本集U進(jìn)行預(yù)測(cè),利用預(yù)測(cè)值初始化d的值,。
③在本輪迭代中,,固定d的取值來(lái)優(yōu)化變量α,然后再固定α的值來(lái)優(yōu)化d的值,。
④重復(fù)步驟③的迭代過(guò)程,,直至達(dá)到訓(xùn)練所指定的迭代次數(shù),得到未標(biāo)記樣本集U的類(lèi)別平均值估計(jì),。
⑤根據(jù)得到的類(lèi)別估計(jì)平均值和有標(biāo)簽樣本集求解式(8)得到一個(gè)SVM分類(lèi)器,。
(5)對(duì)于未知標(biāo)簽的樣本集X,使用T-Criterion[15]準(zhǔn)則的最終預(yù)測(cè)函數(shù)為:
3 實(shí)驗(yàn)
3.1 實(shí)驗(yàn)設(shè)置
在本文中,,用半監(jiān)督算法meanS3VM來(lái)優(yōu)化改進(jìn)E-MIMLSVM+算法,,并將對(duì)比MIMLSVM+、MIMLSVM,、E-MIMLSVM+這3個(gè)MIML算法,,以此來(lái)驗(yàn)證改進(jìn)算法的分類(lèi)性能。其中3個(gè)對(duì)比算法中的參數(shù)分別根據(jù)文獻(xiàn)[6]-[7]中的實(shí)驗(yàn)設(shè)置為最優(yōu),。根據(jù)參考文獻(xiàn)[13]將meanS3VM算法中的參數(shù)調(diào)整為最優(yōu),。實(shí)驗(yàn)同樣應(yīng)用十折交叉法,,將數(shù)據(jù)集分成訓(xùn)練集和測(cè)試集兩份,各1 000個(gè)數(shù)據(jù),。實(shí)驗(yàn)期間,,從訓(xùn)練集中無(wú)規(guī)則的選擇100個(gè)樣本作為有標(biāo)記的訓(xùn)練集,并且剩下的900個(gè)作為無(wú)標(biāo)記的訓(xùn)練集,。由于本實(shí)驗(yàn)對(duì)比的3個(gè)多示例多標(biāo)簽算法無(wú)法訓(xùn)練未標(biāo)記的樣本,,因此每次隨機(jī)抽取1 000個(gè)樣本用作訓(xùn)練集,其余樣本用作測(cè)試集,。反復(fù)10次實(shí)驗(yàn)以計(jì)算平均值以及方差,。
實(shí)驗(yàn)使用周志華等提供的多示例多標(biāo)簽數(shù)據(jù)集,分為場(chǎng)景集和文本集[6],,為了公平起見(jiàn),,算法均使用相同的樣本集和測(cè)試集。第一部分為場(chǎng)景樣本集,,共有樣本圖像2 000個(gè),,數(shù)據(jù)集中的樣本均被標(biāo)記了一組類(lèi)別標(biāo)簽。所有可能的類(lèi)標(biāo)簽為沙漠,、山脈,、海洋、日落和樹(shù)木,,其中,,屬于一個(gè)以上的類(lèi)(如海+日落)的樣本的數(shù)目約占數(shù)據(jù)集的22%,許多組合類(lèi)(如山+日落+樹(shù))約占0.75%,,單個(gè)標(biāo)簽的樣本數(shù)目約占77%,。平均而言,每個(gè)示例都與1.24個(gè)類(lèi)標(biāo)簽相關(guān)聯(lián),。每幅圖片通過(guò)SBN方法[16]用包含9個(gè)示例的示例包進(jìn)行表示,每個(gè)示例為15維的特征向量,。
第二個(gè)樣本集是文本樣本集,,這個(gè)樣本集來(lái)源于被廣泛研究的Reuters-21578[17]。該樣本集分為7個(gè)類(lèi)別標(biāo)簽,,共2 000個(gè)樣本文檔,。原始的數(shù)據(jù)集在刪除標(biāo)簽集或主文本為空的文檔后保留8 866了個(gè)文檔,之后經(jīng)過(guò)隨機(jī)刪除只有一個(gè)類(lèi)標(biāo)簽的文檔后,,得到實(shí)驗(yàn)所用的含有2 000個(gè)樣本文檔的文本數(shù)據(jù)集,。在該數(shù)據(jù)集中,每個(gè)文檔平均所屬于1.15±0.37個(gè)標(biāo)簽,,屬于多個(gè)標(biāo)簽的文檔占比約為15%,。通過(guò)使用滑動(dòng)窗口[18]技術(shù)將文檔表示為一組示例,。每個(gè)包中包括一組243維的特征向量,每一個(gè)向量代表了這篇文檔的某一個(gè)部分,。每一個(gè)包最少包含2個(gè)示例,,最多包含26個(gè)示例,平均每一個(gè)包中含有3.56±2.71個(gè)示例,。本實(shí)驗(yàn)中使用的場(chǎng)景樣本集和文本樣本集,,其結(jié)構(gòu)特征如表1所示。
3.2 實(shí)驗(yàn)結(jié)果
本實(shí)驗(yàn)選取多示例多標(biāo)簽領(lǐng)域的5個(gè)評(píng)價(jià)指標(biāo)[2]:Hamming loss,、one-error,、coverage、ranking loss和average precision,。前4項(xiàng)評(píng)價(jià)指標(biāo)的值越小,,說(shuō)明算法的分類(lèi)效果越好;最后一項(xiàng)評(píng)價(jià)指標(biāo)的值越大,,說(shuō)明分類(lèi)效果越好,。表2和表3分別顯示了各個(gè)算法在兩個(gè)集上的實(shí)驗(yàn)表現(xiàn)。表中“±”前面的值為實(shí)驗(yàn)進(jìn)行十折交叉驗(yàn)證后,,對(duì)5個(gè)評(píng)價(jià)指標(biāo)的計(jì)算取值,,“±”后面的值是計(jì)算得到的方差。
從表中可以看出,,SE-MIMLSVM+算法前4項(xiàng)評(píng)價(jià)指標(biāo)的值都是最小的,,而average precision的值則是最大的,這說(shuō)明改進(jìn)算法在場(chǎng)景樣本集和文本樣本集上取得了優(yōu)于其他多示例多標(biāo)簽算法的分類(lèi)效果,。
4 結(jié)論
本文討論了基于退化策略并且使用SVM分類(lèi)的多示例多標(biāo)簽算法E-MIMLSVM+,。通過(guò)在E-MIMLSVM+算法中引入利用未標(biāo)記樣本學(xué)習(xí)并且求解速度較快的半監(jiān)督支持向量機(jī)meanS3VM,對(duì)原始算法進(jìn)行了改進(jìn),。與其他多示例多標(biāo)簽算法相比,,改進(jìn)算法提高了分類(lèi)準(zhǔn)確率,增強(qiáng)了分類(lèi)器的泛化能力,。
參考文獻(xiàn)
[1] 李斌,,李麗娟.基于改進(jìn)TSVM的未知網(wǎng)絡(luò)應(yīng)用識(shí)別算法[J].電子技術(shù)應(yīng)用,2016,,42(9):95-98.
[2] ZHOU Z H,,ZHANG M L,HUANG S J,,et al.Multi-instance multi-label learning[J].Artificial Intelligence,,2012,176(1):2291-2320.
[3] 張磊,,殷夢(mèng)婕,,肖超恩,,等.基于優(yōu)化型支持向量機(jī)算法的硬件木馬監(jiān)測(cè)[J].電子技術(shù)應(yīng)用,2018,,44(11):17-20.
[4] 張苗.基于多示例學(xué)習(xí)的圖像檢索算法研究[D].合肥:中國(guó)科學(xué)技術(shù)大學(xué),,2017.
[5] READ J,PFAHRINGER B,,HOLMES G,,et al.Classifier chains for multi-label classification[J].Machine Learning,2011,,85(3):333.
[6] ZHOU Z H,,ZHANG M L.Multi-instance multi-label learning with application to scene classification[A].Advances in Neural Information Processing Systems 19[C].MIT Press,2007:1609-1616.
[7] LI Y X,,JI S W,,KUMAR S,et al.Drosophila gene expression pattern annotation through multi-instance multi-label learning[J].IEEE/ACM Transactions on Computational Biology and Bionformatics,,2012,,9(1):98-112.
[8] ZHANG M L,ZHOU Z H.M3MIML:a maximum margin method for multi-instance multi-label learning[C].Eighth IEEE International Conference on Data Mining.IEEE,,2008:688-697.
[9] 周志華.機(jī)器學(xué)習(xí)[M].北京:清華大學(xué)出版社,,2016.
[10] EVGENIOU T,PONTIL M.Regularized multi-task learning[A].Tenth ACM Sigkdd International Conference on Knowledge Discovery & Data Mining[C].ACM,,2004:109-117.
[11] ZHANG J,,GHAHRAMANI Z,YANG Y.Flexible latent variable models for multi-task learning[J].Machine Learning,,2008,,73(3):221-242.
[12] EVGENIOU T,MICCHELLI C A,,PONTIL M.Learning multiple tasks with Kernel methods[J].Machine Learning Research,,2005,6(4):615-637.
[13] LI Y F,,KWOK J T,,ZHOU Z H.Semi-supervised learning using label mean[A].International Conference on Machine Learning[C].ACM,2009:633-640.
[14] 李宇峰.半監(jiān)督支持向量機(jī)學(xué)習(xí)方法的研究[D].南京:南京大學(xué),,2013.
[15] BOUTELL M R,LUO J,,BROWN C.M.Learning multilabel scene classification[J].Pattern Recognition,,2004,37(9):1757-1771.
[16] MARON O,,RATAN A L.Multiple-instance learning for natural scene classification[A].Proceedings of the 15th International Conference on Machine Learning[C].Morgan Kaufmann Publishers Inc,,1998:341-349.
[17] SEBASTIANI F.Machine learning in automated text categorization[J].Computer Science,,2015,34(1):1-47.
[18] ANDREWS S,,TSOCHANTARIDIS I,,HOFMANN T.Support vector machines for multiple-instance learning[A].Advances in Neural Information Processing Systems[C].ResearchGate,2003:561-568.
作者信息:
李村合1,,張振凱1,,朱洪波2
(1.中國(guó)石油大學(xué)(華東) 計(jì)算機(jī)與通信工程學(xué)院,山東 青島266580,;
2.上海諾基亞貝爾股份有限公司青島分公司fn部門(mén),,山東 青島266100)