0 引言

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

    支持向量機(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ù)是稀少的，無標(biāo)簽的樣本數(shù)據(jù)的獲取相對較易。半監(jiān)督學(xué)習(xí)即通過將無標(biāo)簽樣本數(shù)據(jù)加入訓(xùn)練集中，對其學(xué)習(xí)建模來增強(qiáng)模型的泛化性能。因此，出現(xiàn)了將半監(jiān)督學(xué)習(xí)和SVM方法進(jìn)行結(jié)合來訓(xùn)練分類函數(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í)問題中^[2]，用包含一組示例的集合來表示訓(xùn)練集中的每個(gè)對象，同時(shí)將該對象歸屬于單個(gè)類別標(biāo)簽中。該模型主要學(xué)習(xí)一個(gè)分類器(即映射函數(shù)fMIL：2^x→Y)來標(biāo)記未知的示例包的標(biāo)簽。代表性的多示例學(xué)習(xí)算法有多示例最近鄰算法Citation-kNN、多示例神經(jīng)網(wǎng)絡(luò)算法BP-MIP等^[4]。

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

    在MIML框架下，有兩種解決問題的方式，一種是應(yīng)用退化的方式，以多示例學(xué)習(xí)或多標(biāo)簽學(xué)習(xí)作為橋梁，對MIML問題進(jìn)行退化，如MIMLSVM^[6]和MIMLSVM+^[7]等。但是在退化時(shí)，有時(shí)標(biāo)簽間的關(guān)聯(lián)信息會被忽視，進(jìn)而影響到實(shí)際的分類效果。為了避免信息丟失，另一種思路是改造算法找到適應(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í)即把大量無標(biāo)記的數(shù)據(jù)和少量有標(biāo)記的數(shù)據(jù)一塊訓(xùn)練，構(gòu)建起泛化性能強(qiáng)的分類器，有標(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ū)域來劃分超平面，如此一來就能同時(shí)利用有標(biāo)簽的數(shù)據(jù)和無標(biāo)簽的數(shù)據(jù)。半監(jiān)督SVM中最經(jīng)典的是TSVM和S3VM^[13]。通過文獻(xiàn)[13]對類中心的有效性分析可以獲得基于類中心估計(jì)的半監(jiān)督支持向量機(jī)meanS3VM。它只需要最大化兩個(gè)類的類別平均值，來代替之前對所有的未標(biāo)記樣本進(jìn)行標(biāo)記的方式。這很大程度上提升了半監(jiān)督SVM的求解速度。

    假設(shè)存在有標(biāo)記的樣本集D_l={(x₁，y₁)，(x₂，y₂)，…，(x_i，y_i)}，未標(biāo)記的樣本集D_u={x_l+1，x_l+2，…，x_l+u}，meanS3VM算法^[13]可形式化定義為：

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

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

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

2.3 改進(jìn)算法步驟

    因?yàn)棣睾蚫的雙線性約束，所以式(7)是一個(gè)非凸優(yōu)化模型。可以使用凸松弛算法或交替優(yōu)化算法得到未標(biāo)記樣本估計(jì)好的類中心然后帶入式(7)將其變?yōu)橥箖?yōu)化問題，使用凸優(yōu)化軟件包求解。這里選擇使用求解速度更快的交替優(yōu)化算法來處理相關(guān)問題。

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

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

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

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

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

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

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

3 實(shí)驗(yàn)

3.1 實(shí)驗(yàn)設(shè)置

    在本文中，用半監(jiān)督算法meanS3VM來優(yōu)化改進(jìn)E-MIMLSVM⁺算法，并將對比MIMLSVM⁺、MIMLSVM、E-MIMLSVM⁺這3個(gè)MIML算法，以此來驗(yàn)證改進(jìn)算法的分類性能。其中3個(gè)對比算法中的參數(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)練集和測試集兩份，各1 000個(gè)數(shù)據(jù)。實(shí)驗(yàn)期間，從訓(xùn)練集中無規(guī)則的選擇100個(gè)樣本作為有標(biāo)記的訓(xùn)練集，并且剩下的900個(gè)作為無標(biāo)記的訓(xùn)練集。由于本實(shí)驗(yàn)對比的3個(gè)多示例多標(biāo)簽算法無法訓(xùn)練未標(biāo)記的樣本，因此每次隨機(jī)抽取1 000個(gè)樣本用作訓(xùn)練集，其余樣本用作測試集。反復(fù)10次實(shí)驗(yàn)以計(jì)算平均值以及方差。

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

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

3.2 實(shí)驗(yàn)結(jié)果

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

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

4 結(jié)論

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

參考文獻(xiàn)

[1] 李斌，李麗娟.基于改進(jìn)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)化型支持向量機(jī)算法的硬件木馬監(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] 周志華.機(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.中國石油大學(xué)(華東) 計(jì)算機(jī)與通信工程學(xué)院，山東 青島266580；

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