摘要：多示例多標簽學習框架是一種針對解決多義性問題而提出的新型機器學習框架，在多示例多標簽學習框架中，一個對象是用一組示例集合來表示，并且和一組類別標簽相關聯。E-MIMLSVM+算法是多示例多標簽學習框架中利用退化思想的經典分類算法，針對其無法利用無標簽樣本進行學習從而造成泛化能力差等問題，使用半監督支持向量機對該算法進行改進。改進后的算法可以利用少量有標簽樣本和大量沒有標簽的樣本進行學習，有助于發現樣本集內部隱藏的結構信息，了解樣本集的真實分布情況。通過對比實驗可以看出，改進后的算法有效提高了分類器的泛化性能。

0 引言

對于監督學習，通過訓練集中已知類樣本學習構造一個判決邊界，并設定臨閾值，來實現對未知樣本的預測［1］。通常使用一個示例描述單個對象并與其類別相關聯。但是，實際上每個對象都可能不止有一個語義，如一幅含有獅子、大象、草原的圖，可以將其歸為“大象”類別，也可以將其歸為“獅子”類別，甚至可以因為動物和草原的存在將其歸為“非洲”的類別。因此，當僅通過一個示例來表示一個對象時，顯然難以獲得期望的效果。為了處理這個難題，相關學者提出了多示例多標簽（Multi-Instance Multi-Label，MIML）［2］機器學習模型，最大特點是：在該框架中是用一組示例集合來表示一個對象，同時該對象與多個標簽相關聯。對于真實世界中對象的表示能力更強，其他的機器學習框架可以看作是多示例多標簽框架的一種簡化表示形式。支持向量機（Support Vector Machine，SVM）是建立在統計學習理論基礎上的一種機器學習方法，其泛化準確率高，計算效率高，結果易解釋［3］。傳統的SVM多為監督學習，然而在實際中，有標簽的樣本數據是稀少的，無標簽的樣本數據的獲取相對較易。半監督學習即通過將無標簽樣本數據加入訓練集中，對其學習建模來增強模型的泛化性能。因此，出現了將半監督學習和SVM方法進行結合來訓練分類函數的研究。

1 相關工作

傳統監督學習是一種單示例單標記學習框架。學習任務是學得一個映射函數：f:X→Y。在多示例學習問題中［2］，用包含一組示例的集合來表示訓練集中的每個對象，同時將該對象歸屬于單個類別標簽中。該模型主要學習一個分類器（即映射函數fMIL：2x→Y）來標記未知的示例包的標簽。代表性的多示例學習算法有多示例最近鄰算法Citation-kNN、多示例神經網絡算法BP-MIP等［4］。在多標簽學習問題中［2］，對象僅由單個示例表示，并屬于一組標簽。該框架模型的任務是學習fMIL：x→2Y函數的映射，然后使用此映射來預測未知集合中的標簽類別。代表性的多標簽學習算法有二元相關（BR）算法和分類器鏈（CC）算法［5］等。

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

2 改進的算法

2.1 E-MIMLSVM+算法

2.2 E-MIMLSVM+算法中引入半監督

半監督學習即把大量無標記的數據和少量有標記的數據一塊訓練，構建起泛化性能強的分類器，有標簽的數據和無標簽的數據的空間結構分布相似，應用無標簽的樣本來訓練，有助于提高訓練出模型的性能。半監督SVM屬于半監督領域中的學習算法，它基于SVM和半監督學習的聚類假設，嘗試尋找能將兩類有標簽樣本分隔，并且通過穿過低密度區域來劃分超平面，如此一來就能同時利用有標簽的數據和無標簽的數據。半監督SVM中最經典的是TSVM和S3VM［13］。通過文獻［13］對類中心的有效性分析可以獲得基于類中心估計的半監督支持向量機meanS3VM。它只需要最大化兩個類的類別平均值，來代替之前對所有的未標記樣本進行標記的方式。這很大程度上提升了半監督SVM的求解速度。假設存在有標記的樣本集Dl={（x1，y1），（x2，y2），…，（xi，yi）}，未標記的樣本集Du={xl+1，xl+2，…，xl+u}，meanS3VM算法［13］可形式化定義為：

通過分析可以得到，式（7）只需要估計無標簽樣本的類別平均值即可。與S3VM相比，meanS3VM避免了對所有未標記樣本類別標簽的估計。實際上，meanS3VM算法最大化了兩個類的類別平均值。由于meanS3VM算法大量減少了約束條件的個數，因此，對半監督SVM的求解速度更快了，從而使得半監督SVM的時間開銷變少。可以證明［14］，當給定樣本集可分時，meanS3VM的損失函數與標準SVM一致；當給定樣本集不可分時，meanS3VM的損失函數不會超過標準支持向量機hinge損失的兩倍。為了充分利用未標記樣本的空間分布信息，來進一步提升分類器的泛化性能，在本文中，使用半監督SVM算法——meanS3VM對E-MIMLSVM+算法進行了改進。由于meanS3VM算法適用于傳統的半監督學習問題，本文改進了meanS3VM算法中核函數的計算方式，用多示例核函數進行替代。使得meanS3VM算法能夠適用于多示例多標簽學習中，從而得到改進算法SE-MIMLSVM+。令給定有標簽樣本集S={（Xi，Yi）|1≤i≤l}，無標簽樣本集U={（Xi，Yi）|l+1≤i≤l+μ}，測試樣本集T={（Xi，Yi）|1≤i≤M}，則SE-MIMLSVM+算法的優化問題變為：

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

2.3 改進算法步驟

因為ω和d的雙線性約束，所以式（7）是一個非凸優化模型。可以使用凸松弛算法或交替優化算法得到未標記樣本估計好的類中心然后帶入式（7）將其變為凸優化問題，使用凸優化軟件包求解。這里選擇使用求解速度更快的交替優化算法來處理相關問題。SE-MIMLSVM+的算法流程如下：

①使用有標簽的樣本Sk訓練SVM分類器。②使用訓練出來的SVM分類器對未標記的樣本集U進行預測，利用預測值初始化d的值。③在本輪迭代中，固定d的取值來優化變量α，然后再固定α的值來優化d的值。④重復步驟③的迭代過程，直至達到訓練所指定的迭代次數，得到未標記樣本集U的類別平均值估計。⑤根據得到的類別估計平均值和有標簽樣本集求解式（8）得到一個SVM分類器。（5）對于未知標簽的樣本集X，使用T-Criterion［15］準則的最終預測函數為：

3 實驗

3.1 實驗設置

在本文中，用半監督算法meanS3VM來優化改進E-MIMLSVM+算法，并將對比MIMLSVM+、MIMLSVM、E-MIMLSVM+這3個MIML算法，以此來驗證改進算法的分類性能。其中3個對比算法中的參數分別根據文獻［6］-［7］中的實驗設置為最優。根據參考文獻［13］將meanS3VM算法中的參數調整為最優。實驗同樣應用十折交叉法，將數據集分成訓練集和測試集兩份，各1 000個數據。實驗期間，從訓練集中無規則的選擇100個樣本作為有標記的訓練集，并且剩下的900個作為無標記的訓練集。由于本實驗對比的3個多示例多標簽算法無法訓練未標記的樣本，因此每次隨機抽取1 000個樣本用作訓練集，其余樣本用作測試集。反復10次實驗以計算平均值以及方差。實驗使用周志華等提供的多示例多標簽數據集，分為場景集和文本集［6］，為了公平起見，算法均使用相同的樣本集和測試集。第一部分為場景樣本集，共有樣本圖像2 000個，數據集中的樣本均被標記了一組類別標簽。所有可能的類標簽為沙漠、山脈、海洋、日落和樹木，其中，屬于一個以上的類（如海+日落）的樣本的數目約占數據集的22%，許多組合類（如山+日落+樹）約占0.75%，單個標簽的樣本數目約占77%。平均而言，每個示例都與1.24個類標簽相關聯。每幅圖片通過SBN方法［16］用包含9個示例的示例包進行表示，每個示例為15維的特征向量。第二個樣本集是文本樣本集，這個樣本集來源于被廣泛研究的Reuters-21578［17］。該樣本集分為7個類別標簽，共2 000個樣本文檔。原始的數據集在刪除標簽集或主文本為空的文檔后保留8 866了個文檔，之后經過隨機刪除只有一個類標簽的文檔后，得到實驗所用的含有2 000個樣本文檔的文本數據集。在該數據集中，每個文檔平均所屬于1.15±0.37個標簽，屬于多個標簽的文檔占比約為15%。通過使用滑動窗口［18］技術將文檔表示為一組示例。每個包中包括一組243維的特征向量，每一個向量代表了這篇文檔的某一個部分。每一個包最少包含2個示例，最多包含26個示例，平均每一個包中含有3.56±2.71個示例。本實驗中使用的場景樣本集和文本樣本集，其結構特征如表1所示。

3.2 實驗結果

本實驗選取多示例多標簽領域的5個評價指標［2］：Hamming loss、one-error、coverage、ranking loss和average precision。前4項評價指標的值越小，說明算法的分類效果越好；最后一項評價指標的值越大，說明分類效果越好。表2和表3分別顯示了各個算法在兩個集上的實驗表現。表中“±”前面的值為實驗進行十折交叉驗證后，對5個評價指標的計算取值，“±”后面的值是計算得到的方差。

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

4 結論

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

參考文獻

［1］ 李斌，李麗娟。基于改進TSVM的未知網絡應用識別算法［J］。電子技術應用，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］ 張磊，殷夢婕，肖超恩，等。基于優化型支持向量機算法的硬件木馬監測［J］。電子技術應用，2018，44（11）：17-20.

［4］ 張苗。基于多示例學習的圖像檢索算法研究［D］。合肥：中國科學技術大學，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］ 周志華。機器學習［M］。北京：清華大學出版社，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］ 李宇峰。半監督支持向量機學習方法的研究［D］。南京：南京大學，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.