《電子技術(shù)應(yīng)用》
您所在的位置:首頁 > 嵌入式技術(shù) > 設(shè)計應(yīng)用 > 基于半監(jiān)督學(xué)習(xí)的多示例多標(biāo)簽改進算法
基于半監(jiān)督學(xué)習(xí)的多示例多標(biāo)簽改進算法
2019年電子技術(shù)應(yīng)用第7期
李村合1,,張振凱1,朱洪波2
1.中國石油大學(xué)(華東) 計算機與通信工程學(xué)院,,山東 青島266580,; 2.上海諾基亞貝爾股份有限公司青島分公司fn部門,山東 青島266100
摘要: 多示例多標(biāo)簽學(xué)習(xí)框架是一種針對解決多義性問題而提出的新型機器學(xué)習(xí)框架,,在多示例多標(biāo)簽學(xué)習(xí)框架中,,一個對象是用一組示例集合來表示,,并且和一組類別標(biāo)簽相關(guān)聯(lián),。E-MIMLSVM+算法是多示例多標(biāo)簽學(xué)習(xí)框架中利用退化思想的經(jīng)典分類算法,針對其無法利用無標(biāo)簽樣本進行學(xué)習(xí)從而造成泛化能力差等問題,,使用半監(jiān)督支持向量機對該算法進行改進,。改進后的算法可以利用少量有標(biāo)簽樣本和大量沒有標(biāo)簽的樣本進行學(xué)習(xí),有助于發(fā)現(xiàn)樣本集內(nèi)部隱藏的結(jié)構(gòu)信息,,了解樣本集的真實分布情況,。通過對比實驗可以看出,改進后的算法有效提高了分類器的泛化性能,。
中圖分類號: TP181
文獻標(biāo)識碼: A
DOI:10.16157/j.issn.0258-7998.190243
中文引用格式: 李村合,,張振凱,朱洪波. 基于半監(jiān)督學(xué)習(xí)的多示例多標(biāo)簽改進算法[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.
A multi-instance multi-label improved algorithm based on semi-supervised learning
Li Cunhe1,,Zhang Zhenkai1,Zhu Hongbo2
1.School of Computer and Communication Engineering,,China University of Petroleum,,Qingdao 266580,China,; 2.Shanghai Nokia Bell Co.,,Ltd.,Qingdao Branch fn Department,,Qingdao 266100,,China
Abstract: The multi-instance multi-label learning framework is a new machine learning framework for solving ambiguity problems. In the multi-instance multi-label learning framework, an object is represented by a set of examples and is associated with a set of category labels. The E-MIMLSVM+ algorithm is a classical classification algorithm that uses degenerate ideas in the multi-instance multi-label learning framework. It can′t use unlabeled samples to learn and cause poor generalization ability. This paper uses semi-supervised support vector machine to implement the algorithm. The improved algorithm can use a small number of labeled samples and a large number of unlabeled samples to learn, which helps to discover the hidden structure information inside the sample set and understand the true distribution of the sample set. It can be seen from the comparison experiment that the improved algorithm effectively improve the generalization performance of the classifier.
Key words : machine learning;multi-instance multi-label,;semi-supervised,;SVM;generalization performance

0 引言

    對于監(jiān)督學(xué)習(xí),,通過訓(xùn)練集中已知類樣本學(xué)習(xí)構(gòu)造一個判決邊界,,并設(shè)定臨閾值,來實現(xiàn)對未知樣本的預(yù)測[1],。通常使用一個示例描述單個對象并與其類別相關(guān)聯(lián),。但是,實際上每個對象都可能不止有一個語義,,如一幅含有獅子,、大象、草原的圖,,可以將其歸為“大象”類別,,也可以將其歸為“獅子”類別,甚至可以因為動物和草原的存在將其歸為“非洲”的類別,。因此,,當(dāng)僅通過一個示例來表示一個對象時,顯然難以獲得期望的效果,。為了處理這個難題,,相關(guān)學(xué)者提出了多示例多標(biāo)簽(Multi-Instance Multi-Label,MIML)[2]機器學(xué)習(xí)模型,,最大特點是:在該框架中是用一組示例集合來表示一個對象,,同時該對象與多個標(biāo)簽相關(guān)聯(lián)。對于真實世界中對象的表示能力更強,其他的機器學(xué)習(xí)框架可以看作是多示例多標(biāo)簽框架的一種簡化表示形式,。

    支持向量機(Support Vector Machine,,SVM)是建立在統(tǒng)計學(xué)習(xí)理論基礎(chǔ)上的一種機器學(xué)習(xí)方法,其泛化準(zhǔn)確率高,,計算效率高,,結(jié)果易解釋[3]。傳統(tǒng)的SVM多為監(jiān)督學(xué)習(xí),,然而在實際中,,有標(biāo)簽的樣本數(shù)據(jù)是稀少的,無標(biāo)簽的樣本數(shù)據(jù)的獲取相對較易,。半監(jiān)督學(xué)習(xí)即通過將無標(biāo)簽樣本數(shù)據(jù)加入訓(xùn)練集中,,對其學(xué)習(xí)建模來增強模型的泛化性能。因此,,出現(xiàn)了將半監(jiān)督學(xué)習(xí)和SVM方法進行結(jié)合來訓(xùn)練分類函數(shù)的研究,。

1 相關(guān)工作

    傳統(tǒng)監(jiān)督學(xué)習(xí)是一種單示例單標(biāo)記學(xué)習(xí)框架。學(xué)習(xí)任務(wù)是學(xué)得一個映射函數(shù):f:X→Y,。

    在多示例學(xué)習(xí)問題中[2],,用包含一組示例的集合來表示訓(xùn)練集中的每個對象,同時將該對象歸屬于單個類別標(biāo)簽中,。該模型主要學(xué)習(xí)一個分類器(即映射函數(shù)fMIL:2x→Y)來標(biāo)記未知的示例包的標(biāo)簽,。代表性的多示例學(xué)習(xí)算法有多示例最近鄰算法Citation-kNN、多示例神經(jīng)網(wǎng)絡(luò)算法BP-MIP等[4],。

    在多標(biāo)簽學(xué)習(xí)問題中[2],,對象僅由單個示例表示,并屬于一組標(biāo)簽,。該框架模型的任務(wù)是學(xué)習(xí)fMIL:x→2Y函數(shù)的映射,,然后使用此映射來預(yù)測未知集合中的標(biāo)簽類別。代表性的多標(biāo)簽學(xué)習(xí)算法有二元相關(guān)(BR)算法和分類器鏈(CC)算法[5]等,。

rgzn-1-x1.gif

    在MIML框架下,,有兩種解決問題的方式,,一種是應(yīng)用退化的方式,,以多示例學(xué)習(xí)或多標(biāo)簽學(xué)習(xí)作為橋梁,對MIML問題進行退化,,如MIMLSVM[6]和MIMLSVM+[7]等,。但是在退化時,有時標(biāo)簽間的關(guān)聯(lián)信息會被忽視,,進而影響到實際的分類效果,。為了避免信息丟失,另一種思路是改造算法找到適應(yīng)MIML框架的機器學(xué)習(xí)算法。代表性算法主要有D-MIMLSVM算法,、M3MIML算法[8]等,。

2 改進的算法

2.1 E-MIMLSVM+算法

rgzn-gs1.gif

rgzn-gs2-6.gif

2.2 E-MIMLSVM+算法中引入半監(jiān)督

    半監(jiān)督學(xué)習(xí)即把大量無標(biāo)記的數(shù)據(jù)和少量有標(biāo)記的數(shù)據(jù)一塊訓(xùn)練,構(gòu)建起泛化性能強的分類器,,有標(biāo)簽的數(shù)據(jù)和無標(biāo)簽的數(shù)據(jù)的空間結(jié)構(gòu)分布相似,,應(yīng)用無標(biāo)簽的樣本來訓(xùn)練,有助于提高訓(xùn)練出模型的性能,。

    半監(jiān)督SVM屬于半監(jiān)督領(lǐng)域中的學(xué)習(xí)算法,,它基于SVM和半監(jiān)督學(xué)習(xí)的聚類假設(shè),嘗試尋找能將兩類有標(biāo)簽樣本分隔,,并且通過穿過低密度區(qū)域來劃分超平面,,如此一來就能同時利用有標(biāo)簽的數(shù)據(jù)和無標(biāo)簽的數(shù)據(jù)。半監(jiān)督SVM中最經(jīng)典的是TSVM和S3VM[13],。通過文獻[13]對類中心的有效性分析可以獲得基于類中心估計的半監(jiān)督支持向量機meanS3VM,。它只需要最大化兩個類的類別平均值,來代替之前對所有的未標(biāo)記樣本進行標(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]可形式化定義為:

rgzn-gs7.gif

    通過分析可以得到,,式(7)只需要估計無標(biāo)簽樣本的類別平均值即可。與S3VM相比,,meanS3VM避免了對所有未標(biāo)記樣本類別標(biāo)簽的估計,。實際上,meanS3VM算法最大化了兩個類的類別平均值,。由于meanS3VM算法大量減少了約束條件的個數(shù),,因此,對半監(jiān)督SVM的求解速度更快了,,從而使得半監(jiān)督SVM的時間開銷變少,。可以證明[14],當(dāng)給定樣本集可分時,,meanS3VM的損失函數(shù)與標(biāo)準(zhǔn)SVM一致,;當(dāng)給定樣本集不可分時,meanS3VM的損失函數(shù)不會超過標(biāo)準(zhǔn)支持向量機hinge損失的兩倍,。

    為了充分利用未標(biāo)記樣本的空間分布信息,,來進一步提升分類器的泛化性能,在本文中,,使用半監(jiān)督SVM算法——meanS3VM對E-MIMLSVM+算法進行了改進,。由于meanS3VM算法適用于傳統(tǒng)的半監(jiān)督學(xué)習(xí)問題,本文改進了meanS3VM算法中核函數(shù)的計算方式,,用多示例核函數(shù)進行替代,。使得meanS3VM算法能夠適用于多示例多標(biāo)簽學(xué)習(xí)中,從而得到改進算法SE-MIMLSVM+,。令給定有標(biāo)簽樣本集S={(Xi,,Yi)|1≤i≤l},無標(biāo)簽樣本集U={(Xi,,Yi)|l+1≤i≤l+μ},,測試樣本集T={(Xi,Yi)|1≤i≤M},,則SE-MIMLSVM+算法的優(yōu)化問題變?yōu)椋?/p>

    rgzn-gs8.gif

其中,,ξiy和ρ分別代表的是有標(biāo)簽數(shù)據(jù)和無標(biāo)簽數(shù)據(jù)的松弛變量,W0反映了不同任務(wù)間的共同特征,,vy反映了不同任務(wù)間的區(qū)別,,參數(shù)μ用于協(xié)調(diào)不同任務(wù)間的相似程度。從式(4)建立的模型可以看出,,每一個分類模型fy都有一個共同的參數(shù)w0,,也就是說分類模型假設(shè)每一個標(biāo)簽相互都是有關(guān)聯(lián)關(guān)系的。但是實際的情況是,,并非所有標(biāo)簽都存在關(guān)聯(lián)關(guān)系,。因此可以先在標(biāo)簽空間中聚類,從而將標(biāo)簽空間劃分成許多具有標(biāo)簽相關(guān)性的子集,,每一個示例包和標(biāo)簽之間的標(biāo)簽指示陣表示為Y,。為了衡量標(biāo)簽之間的聯(lián)系信息,在聚類的過程中使用的是Y列上的皮爾遜相關(guān)系數(shù),。

2.3 改進算法步驟

    因為ω和d的雙線性約束,,所以式(7)是一個非凸優(yōu)化模型??梢允褂猛顾沙谒惴ɑ蚪惶鎯?yōu)化算法得到未標(biāo)記樣本估計好的類中心然后帶入式(7)將其變?yōu)橥箖?yōu)化問題,使用凸優(yōu)化軟件包求解。這里選擇使用求解速度更快的交替優(yōu)化算法來處理相關(guān)問題,。

    SE-MIMLSVM+的算法流程如下:

rgzn-gs9.gif

    ①使用有標(biāo)簽的樣本Sk訓(xùn)練SVM分類器,。

    ②使用訓(xùn)練出來的SVM分類器對未標(biāo)記的樣本集U進行預(yù)測,利用預(yù)測值初始化d的值,。

    ③在本輪迭代中,,固定d的取值來優(yōu)化變量α,然后再固定α的值來優(yōu)化d的值,。

    ④重復(fù)步驟③的迭代過程,,直至達到訓(xùn)練所指定的迭代次數(shù),得到未標(biāo)記樣本集U的類別平均值估計,。

    ⑤根據(jù)得到的類別估計平均值和有標(biāo)簽樣本集求解式(8)得到一個SVM分類器,。

    (5)對于未知標(biāo)簽的樣本集X,使用T-Criterion[15]準(zhǔn)則的最終預(yù)測函數(shù)為:

    rgzn-gs10.gif

3 實驗

3.1 實驗設(shè)置

    在本文中,,用半監(jiān)督算法meanS3VM來優(yōu)化改進E-MIMLSVM+算法,,并將對比MIMLSVM+、MIMLSVM,、E-MIMLSVM+這3個MIML算法,,以此來驗證改進算法的分類性能。其中3個對比算法中的參數(shù)分別根據(jù)文獻[6]-[7]中的實驗設(shè)置為最優(yōu),。根據(jù)參考文獻[13]將meanS3VM算法中的參數(shù)調(diào)整為最優(yōu),。實驗同樣應(yīng)用十折交叉法,將數(shù)據(jù)集分成訓(xùn)練集和測試集兩份,,各1 000個數(shù)據(jù),。實驗期間,從訓(xùn)練集中無規(guī)則的選擇100個樣本作為有標(biāo)記的訓(xùn)練集,,并且剩下的900個作為無標(biāo)記的訓(xùn)練集,。由于本實驗對比的3個多示例多標(biāo)簽算法無法訓(xùn)練未標(biāo)記的樣本,因此每次隨機抽取1 000個樣本用作訓(xùn)練集,,其余樣本用作測試集,。反復(fù)10次實驗以計算平均值以及方差。

    實驗使用周志華等提供的多示例多標(biāo)簽數(shù)據(jù)集,,分為場景集和文本集[6],,為了公平起見,算法均使用相同的樣本集和測試集,。第一部分為場景樣本集,,共有樣本圖像2 000個,數(shù)據(jù)集中的樣本均被標(biāo)記了一組類別標(biāo)簽,。所有可能的類標(biāo)簽為沙漠,、山脈,、海洋、日落和樹木,,其中,,屬于一個以上的類(如海+日落)的樣本的數(shù)目約占數(shù)據(jù)集的22%,許多組合類(如山+日落+樹)約占0.75%,,單個標(biāo)簽的樣本數(shù)目約占77%,。平均而言,每個示例都與1.24個類標(biāo)簽相關(guān)聯(lián),。每幅圖片通過SBN方法[16]用包含9個示例的示例包進行表示,,每個示例為15維的特征向量。

    第二個樣本集是文本樣本集,,這個樣本集來源于被廣泛研究的Reuters-21578[17],。該樣本集分為7個類別標(biāo)簽,共2 000個樣本文檔,。原始的數(shù)據(jù)集在刪除標(biāo)簽集或主文本為空的文檔后保留8 866了個文檔,,之后經(jīng)過隨機刪除只有一個類標(biāo)簽的文檔后,得到實驗所用的含有2 000個樣本文檔的文本數(shù)據(jù)集,。在該數(shù)據(jù)集中,,每個文檔平均所屬于1.15±0.37個標(biāo)簽,屬于多個標(biāo)簽的文檔占比約為15%,。通過使用滑動窗口[18]技術(shù)將文檔表示為一組示例,。每個包中包括一組243維的特征向量,每一個向量代表了這篇文檔的某一個部分,。每一個包最少包含2個示例,,最多包含26個示例,平均每一個包中含有3.56±2.71個示例,。本實驗中使用的場景樣本集和文本樣本集,,其結(jié)構(gòu)特征如表1所示。

rgzn-b1.gif

3.2 實驗結(jié)果

    本實驗選取多示例多標(biāo)簽領(lǐng)域的5個評價指標(biāo)[2]:Hamming loss,、one-error,、coverage、ranking loss和average precision,。前4項評價指標(biāo)的值越小,,說明算法的分類效果越好;最后一項評價指標(biāo)的值越大,,說明分類效果越好,。表2和表3分別顯示了各個算法在兩個集上的實驗表現(xiàn)。表中“±”前面的值為實驗進行十折交叉驗證后,,對5個評價指標(biāo)的計算取值,,“±”后面的值是計算得到的方差,。

rgzn-b2.gif

rgzn-b3.gif

    從表中可以看出,SE-MIMLSVM+算法前4項評價指標(biāo)的值都是最小的,,而average precision的值則是最大的,,這說明改進算法在場景樣本集和文本樣本集上取得了優(yōu)于其他多示例多標(biāo)簽算法的分類效果,。

4 結(jié)論

    本文討論了基于退化策略并且使用SVM分類的多示例多標(biāo)簽算法E-MIMLSVM+,。通過在E-MIMLSVM+算法中引入利用未標(biāo)記樣本學(xué)習(xí)并且求解速度較快的半監(jiān)督支持向量機meanS3VM,對原始算法進行了改進,。與其他多示例多標(biāo)簽算法相比,,改進算法提高了分類準(zhǔn)確率,增強了分類器的泛化能力,。

參考文獻

[1] 李斌,,李麗娟.基于改進TSVM的未知網(wǎng)絡(luò)應(yīng)用識別算法[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] 張磊,,殷夢婕,,肖超恩,等.基于優(yōu)化型支持向量機算法的硬件木馬監(jiān)測[J].電子技術(shù)應(yīng)用,,2018,,44(11):17-20.

[4] 張苗.基于多示例學(xué)習(xí)的圖像檢索算法研究[D].合肥:中國科學(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] 周志華.機器學(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)督支持向量機學(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.中國石油大學(xué)(華東) 計算機與通信工程學(xué)院,山東 青島266580,;

2.上海諾基亞貝爾股份有限公司青島分公司fn部門,,山東 青島266100)

此內(nèi)容為AET網(wǎng)站原創(chuàng),未經(jīng)授權(quán)禁止轉(zhuǎn)載,。