基于Tri-training的半監(jiān)督多標記學習算法

劉楊磊，梁吉業(yè)，高嘉偉，楊靜

(1.山西大學計算機與信息技術(shù)學院，山西太原030006;2.山西大學計算智能與中文信息處理教育部重點實驗室，山西太原030006)

多標記學習(multi-label learning)［1］是機器學習領域的重要研究方向之一.在多標記學習問題中，一個訓練樣本可能同時對應于一個或多個不同的概念標記，以表達其語義信息，學習的任務是為待學習樣本預測其對應的概念標記集合.多標記學習問題普遍存在于真實世界中，比如在圖像場景分類任務中，一幅圖像可能因包含“樹木”、“天空”、“湖泊”以及“山峰”等語義概念，而擁有多個概念標記.

傳統(tǒng)的多標記學習通常是在監(jiān)督意義下進行的，即要求訓練數(shù)據(jù)集的訓練樣本必須全部是已標記樣本.然而，在現(xiàn)實生活中，雖然獲取大量的訓練數(shù)據(jù)集并不十分困難，但是為這些數(shù)據(jù)提供正確的類別標記卻需要耗費大量的人力和時間.比如，在圖像場景分類任務中，現(xiàn)實世界中存在著海量的未標記圖像，而且一幅圖像往往擁有大量的候選類別標記，要完整標注訓練集中的每一個樣本就意味著需要人工查看每一幅圖像的所有候選類別并逐一標注.當數(shù)據(jù)規(guī)模較大且類別數(shù)目較多時，要獲得完整類別標記的訓練樣本集是非常困難的.此時，在監(jiān)督意義下如果只使用少量已標記樣本訓練，則得到的模型很難具有較強的泛化能力.而半監(jiān)督學習能夠較好地解決上述問題，它綜合利用少量的已標記樣本和大量的未標記樣本以提高泛化性能［2-3］.

因此，本文主要以協(xié)同訓練思想為核心，提出了基于Tri-training的半監(jiān)督多標記學習算法(a semisupervised multi-label learning algorithm based on Tritraining，SMLT)，以解決廣泛存在于實際生活中的文本分類、圖像場景分類以及生物信息學等半監(jiān)督多標記學習問題.

1 背景知識

1.1 多標記學習

在多標記學習框架下，每個對象由一個樣本描述，該樣本具有多個類別標記，學習的目的是將所有合適的類別標記賦予待學習樣本［4］.形式化地來說，令X表示樣本空間，Y表示類別標記空間，給定數(shù)據(jù)集{(x1，Y1)，(x2，Y2)，…，(xm，Ym)}，目標是學得 f:X→2Y.其中，xi∈X(i=1，2，…，m)為一個樣本，Yi?Y 為 xi的一組類別標記{yi1，yi2，…，yin}，yij∈Y(j=1，2，…，n)，n 為 Yi中所含類別標記的個數(shù).

如果限定每個樣本只對應一個類別標記，那么傳統(tǒng)的2類或多類學習問題均可以看作是多標記學習問題的特例.然而，多標記學習的一般性也使得其相較于傳統(tǒng)的學習問題更加難以解決.目前，多標記學習面臨的最大挑戰(zhàn)在于其輸出空間過大，即與一個待學習樣本相關聯(lián)的候選類別標記集合的數(shù)量將會隨著標記空間的增大而呈指數(shù)規(guī)模增長.如何充分利用標記之間的相關性是構(gòu)造具有強泛化能力多標記學習系統(tǒng)的關鍵.根據(jù)考察標記之間相關性的不同方式，已有的多標記學習問題求解策略大致可以分為以下 3 類［5］:

1)“一階”策略:將多標記學習問題分解為多個獨立的二分類問題進行求解.該類方法效率較高且實現(xiàn)簡單，但是由于忽略了標記之間的相關性，通常學習系統(tǒng)的泛化性能較低.

2)“二階”策略:考察兩兩標記之間的相關性，將多標記學習問題轉(zhuǎn)化成標記排序問題進行求解.該類方法在一定程度上考慮了標記之間的相關性，學習系統(tǒng)的泛化性能較好，但是當實際問題中標記之間具有超越二階的相關性時，該類方法的性能將會受到很大影響.

3)“高階”策略:考察高階的標記相關性，充分利用標記之間的結(jié)構(gòu)信息進行求解.該類方法可以較好地反映真實世界問題的標記相關性，但其模型復雜度較高，且在缺乏領域知識指導的情況下，幾乎無法利用標記之間的結(jié)構(gòu)信息.

另一方面，近幾年來，多標記學習越來越受到機器學習領域?qū)W者的關注，研究人員對多標記學習問題提出了許多學習方法和策略，對這些問題的研究大致可分為2種思路:一種是問題轉(zhuǎn)化，另一種是算法改編.第1種思路試圖將多標記學習任務轉(zhuǎn)化為一個或多個單標記學習任務，然后利用已有的學習算法求解.代表性學習算法有一階方法Binary Relevance［6］，它將多標記學習問題轉(zhuǎn)化為二分類問題進行求解;二階方法 Calibrated Label Ranking［7］將多標記學習問題轉(zhuǎn)化為標記排序問題求解;高階方法Random k-labelsets［8］將多標記學習問題轉(zhuǎn)化為多類分類問題求解.第2種思路是對現(xiàn)有算法進行改編或設計新算法，使之能直接處理多標記學習任務.代表性學習算法有一階方法ML-kNN［9］，它將“惰性學習”算法k近鄰進行改造以適應多標記數(shù)據(jù);二階方法Rank-SVM［10］將“核學習”算法SVM進行改造用于多類別標記;高階方法 LEAD［5］將“貝葉斯學習”算法中的 Bayes網(wǎng)絡進行改造，以適應多標記數(shù)據(jù).

上述的多標記學習算法通常為監(jiān)督學習算法.然而，為訓練數(shù)據(jù)集提供正確的類別標記需要耗費大量的人力和時間.因此，當只有少量已標記樣本可用時，傳統(tǒng)的多標記學習算法將不再適用.

1.2 半監(jiān)督多標記學習

近來年，有一些研究者開始研究半監(jiān)督/直推式多標記學習(semi-supervised/transductive multi-label learning)方法.半監(jiān)督學習和直推式學習都是試圖利用大量的未標記樣本來輔助對少量已標記樣本的學習，但二者的基本思想?yún)s有顯著的不同.直推式學習的測試樣本是訓練集中的未標記樣本，測試環(huán)境是封閉的;而半監(jiān)督學習的測試樣本與訓練樣本無關，測試環(huán)境是相對開放的.

2006年，Liu等［11］基于如果樣本之間具有很大的相似性，那么它們的標記集合之間也應該具有很大的相似性這樣的假設，提出了CNMF(constrained non-negative matrix factorization)方法，通過解一個帶約束的非負矩陣分解問題，期望使得這2種相似性差值最小，從而獲得最優(yōu)的對未標記樣本的標記.2008年，姜遠等［12］提出了基于隨機游走(random walk)的直推式多標記學習算法TML，并將其用于文本分類.同年，Chen等［13］基于樣本相似性度量與標記相似性度量構(gòu)建圖，提出了SMSE(semi-supervised algorithm for multi-label learning by solving a Sylvester equation)方法，采用標記傳播的思想對未標記樣本的標記進行學習，整個優(yōu)化問題可采用Sylvester方程進行快速求解.2010 年，Sun 等［14］和周志華等［15］考慮多標記學習中的弱標記問題，即訓練樣本對應的標記集合中只有一小部分得到了標記，或者根本沒有任何的標記，分別提出了 WELL(weak label learning)方法和 TML-WL(transductive multi-label learning method for weak labeling)方法，他們同樣采用標記傳播的思想對缺失標記進行學習.2013年，周志華等［16］還采用標記傳播的思想，首先將學習任務看作是一個對標記集合進行估計的優(yōu)化問題，然后為這個優(yōu)化問題找到一個封閉解，提出的TRAM算法為未標記樣本分配其對應的標記集合.以上方法都是直推式方法，這類方法不能自然地對除測試樣本以外的未見樣本進行預測.2012年，周志華等［17］在傳統(tǒng)經(jīng)驗風險最小化原理基礎上，引入2種正則項分別用于約束分類器的復雜度和相似樣本擁有相似結(jié)構(gòu)化的多標記輸出，針對歸納式半監(jiān)督多標記學習，提出了一種正則化方法MASS(multi-label semi-supervised learning).

1.3 Tri-training算法

從20世紀90年代末標準協(xié)同訓練算法被提出開始，很多研究者對協(xié)同訓練技術(shù)進行了研究，不僅提出了很多學習方式不同、限制條件強弱各異的算法，而且對協(xié)同訓練的理論分析和應用研究也取得了不少進展，使得協(xié)同訓練成為半監(jiān)督學習中重要的研究方向之一［18］.

初期的協(xié)同訓練算法引入了很多的限制和約束條件.而Tri-training算法［19］是周志華等在2005年提出的一種新的協(xié)同訓練方法，它使用3個分類器進行訓練.在學習過程中，Tri-training算法采用集成學習中經(jīng)常用到的投票法，使用3個分類器對未見樣本進行預測.

由于Tri-training對屬性集和3個分類器所用監(jiān)督學習算法都沒有約束，而且不使用交叉驗證，其適用范圍更廣、效率更高，因此本文以協(xié)同訓練思想為核心，利用Tri-training算法訓練分類器，來研究半監(jiān)督多標記學習.

2 基于Tri-training的半監(jiān)督多標記學習算法

下面提出一種基于Tri-training的半監(jiān)督多標記學習算法，該算法考察兩兩標記之間的相關性，將多標記學習問題轉(zhuǎn)化為標記排序問題進行求解;因此在一定程度上考慮了標記之間的相關性，并采用半監(jiān)督學習中的協(xié)同訓練思想，利用Tri-training過程來訓練分類器.

本文中相關量的定義如下:L={(xi，Yi)，i=1，2，…，m}是包含m個樣本的已標記樣本集.其中，xi表示第 i個樣本的屬性集合;Yi={yi1，yi2，…，yin}表示樣本xi對應的包含n個標記的類別標記集合，且yij∈{0，1}，j=1，2，…，n，若 yij=1，則表示第 j個標記是當前樣本 xi的真實標記，否則 yij=0.U=，k=1，2，…，t}是包含 t個樣本的未標記樣本集.L∪U是包含m+t個樣本的訓練集.為了驗證所提分類算法的有效性，構(gòu)建的 T=，s=1，2，…，w}是包含 w個樣本的測試集.數(shù)組 Rsj(s=1，2，…，w，j=1，2，…，n)用于存放測試集 T 中樣本在第 j類標記上的得票數(shù).

為了對后續(xù)過程中產(chǎn)生的標記排序結(jié)果進行分析，并得到最終的預測標記集合，需要設置一個閾值來劃分上述標記排序結(jié)果.因此，在算法的預處理階段，為每一個訓練樣本xi添加一個虛擬標記yi0，把虛擬類標記的得票數(shù)作為閾值對標記排序結(jié)果進行劃分.此時，涉及到標記的下標應從0開始.

SMLT算法的基本思想是:首先，為已標記樣本集L中的每一個樣本xi添加一個虛擬標記yi0，然后考慮兩兩標記之間的相關性，對L中每一對標記(y*p，y*q)(0≤p＜q≤n)進行訓練，并利用 Tri-training過程學習得到相應的3個分類器.對一個新的測試樣本，用學習到的分類器對相應的每一對標記進行預測，并統(tǒng)計每個標記所得的票數(shù)Rsj，得到該測試樣本的一個標記排序結(jié)果.最后以虛擬標記ys0″的得票數(shù)Rs0作為確定類標記的依據(jù)，若Rsj＞Rs0(j=1，2，…，n)，則樣本的最后標記 ysj″=1，否則 ysj″=0，即可得到一組測試集樣本的預測結(jié)果Y″.

SMLT算法的流程如圖1所示.SMLT算法的詳細步驟如下.

輸入:已標記樣本集L，未標記樣本集U，測試集T.

輸出:對測試集T的預測結(jié)果Y″.

1)初始化 Rsj=0(s=1，2，…，w，j=0，1，…，n)和用于存放訓練樣本的集合Vpq=?(0≤p＜q≤n).

2)預處理已標記樣本集L.對于任一對未處理的標記(y*p，y*q)，遍歷xi∈L，將滿足以下規(guī)則的xi放入集合 Vpq中.若 yip=1，yiq=0 則樣本(xi，1)放入集合 Vpq中;若 yip=0，yiq=1 則將樣本(xi，0)放入集合Vpq中;若yip=yiq則不考慮樣本xi，即樣本xi不放入集合Vpq中.

3)將集合Vpq作為新的已標記樣本集Lnew，結(jié)合未標記樣本集U，在訓練集中利用Tri-training算法學習得到3個分類器.

4)使用投票法和得到的3個分類器對測試集T中的未標記樣本(s=1，2，…，w)進行預測，得到預測結(jié)果rspq并統(tǒng)計對應的標記投票個數(shù).若rspq=1則表示樣本″屬于第p類標記，Rsp=Rsp+1;若rspq=0則表示樣本″屬于第q類標記，Rsq=Rsq+1.

5)將標記(y*p，y*q)設置為已處理，若還有未處理的標記對，則轉(zhuǎn)步驟2)，否則下一步.

圖1SMLT算法Fig.1 Flow chart of the SMLT algorithm

3 實驗結(jié)果及分析

本文在 emotions、scene、yeast、enron 這 4 個較為常用的多標記數(shù)據(jù)集［20］上與多標記學習的多種典型方法進行實驗比較，其中包括ML-kNN［9］、RANKSVM［10］以及 TRAM［16］.實驗數(shù)據(jù)集的相關信息如表1所示.

表1 實驗數(shù)據(jù)集相關信息Table 1 The characteristics of datasets

實驗采用4種常用的多標記學習評價指標［4］對算法性能進行評估:Hamming Loss、One-Error、Coverage和Ranking Loss.以上4種評估指標的值越小，表明該算法的性能越好［4］.

實驗將抽取各數(shù)據(jù)集的90%作為訓練樣本集(其中20%的訓練樣本是已標記樣本集，80%的訓練樣本是未標記樣本集)，其余10%的數(shù)據(jù)為測試樣本集，重復10次統(tǒng)計其平均結(jié)果.由于TRAM方法是直推式方法，不能直接對測試樣本集以外的未見樣本進行預測，實驗中將最終測試樣本作為TRAM訓練時的未標記樣本集.表2～5給出了實驗結(jié)果，加粗部分為每個指標上的最佳性能.

表2 數(shù)據(jù)集emotions上各算法的實驗結(jié)果Table 2 The summary results of four algorithms on emotions dataset

表3 數(shù)據(jù)集scene上各算法的實驗結(jié)果Table 3 The summary results of four algorithms on scene dataset

表4 數(shù)據(jù)集yeast上各算法的實驗結(jié)果Table 4 The summary results of four algorithms on yeast dataset

表5 數(shù)據(jù)集enron上各算法的實驗結(jié)果Table 5 The summary results of four algorithms on enron dataset

通過分析表2～5，在 emotions和 enron這2個數(shù)據(jù)集上，提出的算法SMLT在4個評估指標上都優(yōu)于其他算法，而在scene數(shù)據(jù)集上有2個評估指標優(yōu)于其他算法，但在Hamming Loss和Ranking loss上略差于其他算法，在yeast數(shù)據(jù)集上有3個評估指標優(yōu)于其他算法，僅在Hamming Loss上略差于其他算法.可能的原因是本文提出的算法充分利用了已標記樣本集和未標記樣本集的信息，這要比不利用已標記樣本集或者單純只利用已標記樣本集的信息，更能提高分類算法的性能.

為了進一步驗證已標記樣本集的規(guī)模對SMLT算法的影響，在4個數(shù)據(jù)集上分別進行實驗.訓練樣本集和測試樣本集的構(gòu)成方法與上文實驗相同，但是已標記樣本集占訓練數(shù)據(jù)集的比例依次調(diào)整為10%、20%、30%、40%和50%時，SMLT算法在4項評估指標上的取值與已標記樣本集比例的關系如圖2～5所示.

圖2 數(shù)據(jù)集emotions在4項評估指標上的實驗結(jié)果Fig.2 The summary results of four evaluation metrics on emotions dataset

圖3 數(shù)據(jù)集scene在4項評估指標上的實驗結(jié)果Fig.3 The summary results of four evaluation metrics on scene dataset

圖4 數(shù)據(jù)集yeast在4項評估指標上的實驗結(jié)果Fig.4 The summary results of four evaluation metrics on yeast dataset

圖5 數(shù)據(jù)集enron在4項評估指標上的實驗結(jié)果Fig.5 The summary results of four evaluation metrics on enron dataset

根據(jù)圖2～5可以發(fā)現(xiàn)，在半監(jiān)督學習的意義下，SMLT算法對應的4項評估指標的值大多隨著已標記樣本集比例的增加而不斷減小，即算法的分類性能越來越好.并且在已標記樣本集比例較小時曲線下降較快，隨著已標記樣本集比例的增加，曲線趨于平緩.僅在yeast數(shù)據(jù)集上的One-Error評價指標的曲線比較特殊.這是因為給定的監(jiān)督信息越多，越有助于分類，從而得到更好的分類結(jié)果，而當已標記樣本集比例增加到一定程度時，監(jiān)督信息不再是影響分類性能的主要因素.

4 結(jié)束語

本文針對廣泛存在于實際生活中的半監(jiān)督多標記學習問題，以協(xié)同訓練思想為核心，以兩兩標記之間的關系為出發(fā)點，利用Tri-training算法訓練分類器，并將多標記學習問題轉(zhuǎn)化為標記排序問題進行求解，實驗結(jié)果表明了該算法的有效性.但是，當多標記的數(shù)量和規(guī)模較大時，如何進一步降低算法的計算復雜度仍將是需要深入討論的問題.

［1］TSOUMAKAS G，KATAKIS I.Multi-label classification:an overview［J］.International Journal of Data Warehousing and Mining，2007，3(3):1-13.

［2］ZHU Xiaojin.Semi-supervised learning literature survey［R］.Madison，USA:University of Wisconsin-Madison，2008.

［3］常瑜，梁吉業(yè)，高嘉偉，等.一種基于Seeds集和成對約束的半監(jiān)督聚類算法［J］.南京大學學報:自然科學版，2012，48(4):405-411.CHANG Yu，LIANG Jiye，GAO Jiawei，et al.A semi-supervised clustering algorithm based on seeds and pair wise constraints［J］.Journal of Nanjing University:Natural Sciences，2012，48(4):405-411.

［4］ZHOU Zhihua，ZHANG Minling，HUANG Shengjun，et al.Multi-instance multi-label learning［J］.Artificial Intelligence，2012，176(1):2291-2320.

［5］ZHANG Minling，ZHANG Kun.Multi-label learning by exploiting label dependency［C］//Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.Washington，DC，USA，2010:999-1007.

［6］BOUTELL M R，LUO Jiebo，SHEN Xipeng，et al.Learning multi-label scene classification［J］.Pattern Recognition，2004，37(9):1757-1771.

［7］FURNKRANZ J，HULLERMEIER E，MENCIA E L，et al.Multi-label classification via calibrated label ranking［J］.Machine Learning，2008，73(2):133-153.

［8］TSOUMAKAS G，VLAHAVAS I.Random k-labelsets:an ensemble method for multilabel classification［C］//Proceedings of the 18th European Conference on Machine Learning.Berlin:Springer，2007:406-417.

［9］ZHANG Minling，ZHOU Zhihua.ML-kNN:a lazy learning approach to multi-label learning［J］.Pattern Recognition，2007，40(7):2038-2048.

［10］ELISSEEFF A，WESTON J.A kernel method for multi-labelled classification［M］//DIETTERICH T G，BECKER S，GHAHRAMANI Z.Advances in Neural Information Processing Systems 14.Cambridge，USA:The MIT Press，2002:681-687.

［11］LIU Yi，JIN Rong，YANG Liu.Semi-supervised multi-label learning by constrained non-negative matrix factorization［C］//Proceedings of the 21st National Conference on Artificial Intelligence.Menlo Park，USA，2006:421-426.

［12］姜遠，佘俏俏，黎銘，等.一種直推式多標記文檔分類方法［J］.計算機研究與發(fā)展，2008，45(11):1817-1823.JIANG Yuan，SHE Qiaoqiao，LI Ming，et al.A transductive multi-label text categorization approach［J］.Journal of Computer Research and Development，2008，45(11):1817-1823.

［13］CHEN Gang，SONG Yangqiu，WANG Fei，et al.Semisupervised multi-label learning by solving a Sylvester equation［C］//Proceedings of SIAM International Conference on Data Mining.Los Alamitos，USA，2008:410-419.

［14］SUN Yuyin，ZHANG Yin，ZHOU Zhihua.Multi-label learning with weak label［C］//Proceedings of the 24th AAAI Conference on Artificial Intelligence.Menlo Park，USA，2010:593-598.

［15］孔祥南，黎銘，姜遠，等.一種針對弱標記的直推式多標記分類方法［J］.計算機研究與發(fā)展，2010，47(8):1392-1399.KONG Xiangnan，LI Ming，JIANG Yuan，et al.A transductive multi-label classification method for weak labeling［J］.Journal of Computer Research and Development，2010，47(8):1392-1399.

［16］KONG Xiangnan，NG M K，ZHOU Zhihua.Transductive multi-label learning via label set propagation［J］.IEEE Transactions on Knowledge and Data Engineering，2013，25(3):704-719.

［17］李宇峰，黃圣君，周志華.一種基于正則化的半監(jiān)督多標記學習方法［J］.計算機研究與發(fā)展，2012，49(6):1272-1278.LI Yufeng，HUANG Shengjun，ZHOU Zhihua.Regularized semi-supervised multi-label learning［J］.Journal of Computer Research and Development，2012，49(6):1272-1278.

［18］周志華，王玨.機器學習及其應用［M］.北京:清華大學出版社，2007:259-275.

［19］ZHOU Zhihua，LI Ming.Tri-training:exploiting unlabeled data using three classifiers［J］.IEEE Transactions on Knowledge and Data Engineering，2005，17(11):1529-1541.

［20］Multi-label datasets［EB/OL］.［2013-01-06］.http://sourceforge.net/projects/mulan/files/datasets/.