李村合, 王文杰(中國石油大學 計算機與通信工程學院, 青島 266580)

基于標記依賴關系集成分類器鏈的多示例多標簽支持向量機算法①

李村合, 王文杰
(中國石油大學 計算機與通信工程學院, 青島 266580)

ECC-MIMLSVM+是多示例多標簽學習框架下一種算法, 該算法提出了一種基于分類器鏈的方法, 但其沒有充分考慮到標簽之間的依賴關系, 而且當標簽數目的增多, 子分類器鏈長度增加, 使得誤差傳播問題凸顯.因此針對此問題, 提出了一種改進算法, 將ECC-MIMLSVM+算法和標簽依賴關系相結合, 設計成基于標記依賴關系集成分類器鏈(ELDCT-MIMLSVM+)來加強標簽間信息聯系, 避免信息丟失, 提高分類的準確率. 通過實驗將本文算法與其他算法進行了對比, 實驗結果顯示, 本文算法取得了良好的效果.

多示例多標簽; 支持向量機; 標簽依賴關系; 分類器鏈

1 引言

在傳統(tǒng)監(jiān)督學習[1]中, 每個對象用一個示例進行描述, 該示例隸屬于一個概念標簽, 在該框架下對象不具有歧義性. 在多示例學習[2]中, 每個對象由多個示例進行描述, 并且同時隸屬于一個概念標簽, 其描述對象的內容存在歧義性. 在多標簽[3,4]學習中, 每個對象由單個示例描述, 并且隸屬于多個概念標簽, 其描述對象的概念存在歧義性. 然而在現實生活中的對象通常同時具有內容、概念兩方面的歧義性, 因此出現了多示例多標簽學習框架(MIML)[5,6].

2007年, 南京大學的周志華等人提出兩個多示例多標簽支持向量機算法, 分別是MIMLBOOST 算法[6]和MIMLSVM算法[7].

2010年, 河海大學的張敏靈提出MIML-KNN[8]算法, 該算法在K-NN算法基礎上的改進算法并應用于MIML學習. 該算法不僅考慮一個樣本的近鄰(稱為neighbors), 還考慮了以該樣本為近鄰的樣本.

2011年, 美國的Nguyen提出的一種新的解決MIML學習問題的SVM算法, SISL-MIML算法[9]. 該算法假設MIML樣本中的每一個示例只有一個最準確的與之對應的標簽, 因為在傳統(tǒng)的MIML樣本退化為SISL樣本時會丟失信息, 即會標錯很多示例的標簽.

2013年, 哈爾濱工業(yè)大學的Wu等人提出一種基于馬爾科夫鏈的MIML學習算法[10].

鑒于支持向量機(SVM)[11]在解決小樣本、非線性及高維模式識別問題中的優(yōu)勢, 因此在多示例多標簽學習框架下的許多算法都采用了支持向量機技術, 如E-MIMLSVM+算法[12]等.

然而這些算法通?；谕嘶呗? 該策略會導致退化過程中有效信息的丟失, 降低了分類準確率. ECC算法[13,14]是對所有的CC模型進行集成學習. 雖然在一定程度上改善退化過程中信息丟失, 但當標簽數目的增多, 子分類器鏈長度增加, 使得誤差傳播問題凸顯.

因此本文提出新算法, 改進了ECC算法誤差傳播凸顯問題,提高分類準確率. ELDCT-MIMLSVM+算法是在訓練過程中依次加入依賴程度最大的標簽信息.主要目的在于減少其他無關標簽的干擾, 避免了信息丟失, 同時也降低因增加子分類鏈而使誤差傳播凸顯的問題, 從而達到較好的分類效果.

本文的組織結構如下: 第二部分介紹相關工作,第三部分提出改進算法, 第四部分給出了實驗結果,第五部分進行了總結.

2 相關工作

在傳統(tǒng)監(jiān)督學習中, 每個對象由一個示例描述并且隸屬于一個概念標簽, 在該學習框架下, 對象與示例和標簽都是一一對應的關系[15], 學習對象不具有歧義性. 其通過已有的部分輸入數據與輸出標簽生成一個函數, 建立輸入輸出數據間的關系, 將輸入數據映射到合適的輸出.

在多示例學習中, 每個對象由多個示例描述并且隸屬于一個概念標簽, 其主要考查了對象在概念空間的歧義性. 多示例學習在給定的多示例數據集合上學習一個映射函數:2x→其中x∈x(j =1,2,...,ni)是第i個包Xi中的一個示例, 每個包?X是個示例的集合, y∈{-1,+1}是包X的所屬類別. ii

在多標簽學習中, 每個對象由單個示例描述并且同時隸屬于多個概念標簽, 其主要考察對象在語義空間的歧義性. 多標簽學習在給定的多標簽數據集合上學習一個映射函數x→, 其中x是單個示例描述的對象, Y?Yii是對象i所屬的類別標簽的集合{...},∈Y(k =1,2,...,l). i在現實生活中, 對象往往同時具有概念歧義性和語義歧義性, 為同時考察這兩方面的歧義性, 多示例多標簽學習框架應運而生. MIML既不像多標簽學習中那樣將對象僅用單一示例描述引起對象概念信息的丟失[16], 也不像多示例學習中那樣僅將對象劃分到單個預定義的語義類別引起對象語義信息的丟失. 在該框架下, 每個對象由多個示例表示同時隸屬于多個概念標簽[17], 因此它能夠充分考慮到輸入輸出空間中的歧義性, 對歧義性對象進行有效地學習. 多示例多標簽學習在給定的多示例多標簽數據集合上學習一個從示例集合X到標簽集合上的映射函數f→, 其中i?X是個示例∈x(j =1,2,...,n)的集合i,,...,,?Y是與包相關的類別標簽∈Y(k =1,2,...,l)的集合{,,...,}. 傳i統(tǒng)監(jiān)督問題、多示例問題、多標簽問題都是多示例多標簽問題的特殊表示形式, 上述三種問題都可在多示例多標簽框架下進行求解.

目前, 在MIML框架下問題的解決方式主要有兩種:

一種是基于退化的策略, 將多示例多標簽問題退化為多示例或多標簽, 再轉化為傳統(tǒng)監(jiān)督學習框架下的等價形式進行求解, 如MIMLSVM[7]、MIMLBOOST[6]等算法, 兩者分別以多標簽學習和多示例學習為橋梁, 將多示例多標簽問題退化為傳統(tǒng)監(jiān)督問題進行求解. 但這兩種方式在退化過程中都會引起有效信息的丟失, 導致分類效果不理想, 而且針對大規(guī)模機器學習問題時有明顯不足;

另一種是考察示例與標簽之間的關系, 直接設計針對多示例多標簽樣本的學習算法, 如M3MIML算法[18]. 但這種算法設計難度大, 樣本訓練時間長, 而且實驗證明分類效果不好.

Ying-xin Li和Shui-wang Ji等在果蠅基因表達模式注釋的問題中提出基于支持向量機的多示例多標簽算法的MIMLSVM+算法[12], 這是一種針對大規(guī)模學習問題提出的算法. 該算法具有較低的訓練時間和較好的分類效果, 但其沒有考慮標簽之間的依賴性, 忽略了標簽內在聯系, 影響力分類準確率.

3 改進的算法

3.1 MIMLSVM+算法(Multi-instance Multi-label SVM for Large-scale Learning)

MIMLSVM+算法同MIMLSVM和MIMLBOOST算法相似是一種基于退化的算法, MIMLSVM+將多示例多標簽問題退化為多示例單標簽問題進行求解, 該算法主要針對大規(guī)模的數據問題. MIMLSVM+算法每次為單個標簽訓練分類器, 收集所有具有該標簽的包為正包, 不具有該標簽的包為負包, 得到一系列二類分類任務, 每個任務利用支持向量機處理. 為處理類不平衡問題, MIMLSVM+采用不同的懲罰參數分別應用于正類和負類的松弛條件.

3.1.1 MIMLSVM+算法主要包括以下步驟:

①將多示例多標簽退化為二分問題, 對每個二分類問題設計SVM算法進行處理

②處理數據不平衡問題, 在訓練過程中優(yōu)化SVM, 采用“rescaling”(尺度改變)方法來調節(jié)懲罰參數大小.

③不同的核函數的計算結果不同, 選取恰當的核函數.

④設計總的分類模型.

3.1.2 MIMLSVM+的懲罰參數

對于每個標簽Yy∈, 若1),(=yXiφ, 則說明包iX具有標簽y, 若1-),(=yXi

φ

, 表明包iX不具有標簽y. MIMLSVM+的相關優(yōu)化問題為:

其中, φ（Xi）是將示例包Xi映射到核空間的映射函數, φ（Xi,y）表示包Xi是否具有標簽y. εi是hinge loss, n是示例包的數目, w和b是用于表示核空間線性描述函數的參數. C+和C-分別為正類和負類的懲罰因子.

3.1.3 MIMLSVM+的改進

為了增強分類模型的容錯率和減少訓練樣本被錯誤分類, 我們對算法引入非負松弛變量ξiy. 引入之后將公式轉化為:

經過上述改進, SVM的優(yōu)化變?yōu)橐陨蠁栴}(MIMLSVM+步驟2).

3.1.4 核函數MIMLSVM+算法采用多示例核函數[19]KMI( X,X′):

該核函數是通過對標準設置內核函數

取合適的p值得到的, 其中p≥1, K(.，.)為示例級別的內核.

為進一步利用本地視覺特征和空間特征的信息, MIMLSVM+算法重新定義了核函數

其中||xt0-xk0||衡量了兩個圖像補丁間本地視覺特征的相似性, ||xti-衡量了兩個圖像補丁間的的空間距離. 通過調節(jié)參數γ1和γ2可對本地視覺特征和空間信息進行顯式利用. MIMLSVM+的核函數十分恰當, 所以我們采用其核函數. 最終的判別函數為:

3.2 ELDCC(Ensembles of Label Dependencies Classifier Chain)

MIMLSVM+算法為每個標簽建立一個二類分類器, 忽略了標簽之間的聯系信息, 退化過程中信息丟失, 因此本篇論文提出了基于標記依賴關系的多示例多標簽分類器鏈算法. 本篇文章采用ECC技術對標簽間的聯系信息加以利用, 并依據某種策略計算標簽間的依賴程度值, 根據獲得的標簽依賴程度組織基分類器鏈.

ELDCC主要目標是依據標簽間的依賴程度的大小依次訓練基分類器, 在訓練時依次加入依賴程度最大的標簽信息, 以達到較好的分類效果. 這樣在保持了ECC算法低時間復雜度、低空間復雜度優(yōu)勢的同時,又能夠對標簽間的依賴關系加以利用, 進一步提高分類的準確率. 該算法不僅能降低時間、空間復雜度, 還能消除標簽順序對分類的影響.

以下是ELDCC算法的主要步驟:

第一步: 計算標簽間的依賴程度值.

首先依據表1統(tǒng)計數據集中相應樣本的數目. 其中N表示數據集中的樣本總數, 各個變量(a/b/c/d)對應在數據集中與兩個標記相關的樣本的統(tǒng)計量, 例如a表示數據集中同時與標簽i和標簽j相關的樣本個數．

表1 標記和的關聯表

獲得表1求得的變量值, 依據公式(1)量化標簽i與標簽j的依賴程度.

第二步: 隨機選擇m個標簽作為初始根節(jié)點, 利用prim算法生成m個有序分類器鏈.

取依賴程度值的倒數, 利用prim算法獲得最小生成樹. 集合U是已加入鏈中的標簽, 集合V是待加入標簽, 每次從集合V中選取到集合U中依賴程度最大的標簽, 并將其加入到集合U中, 更新集合V到集合U中的依賴程度值, 循環(huán)直到集合V中所有的標簽都加入到集合U中. 將依次加入集合U中標簽結點的順序作為一個分類器鏈的訓練標簽的順序.

第三步: 利用訓練樣本訓練基分類器.

假設共有L個標簽, 依據第二步獲得的標簽順序C（c1,c2,.....cL）為每個標簽構建一個二類分類器, L個二類分類器組成一個有序分類器鏈. 分類器鏈中第一個基分類器的輸入為初始樣本, 其余基分類器的輸入為上一個基分類器的輸入樣本以及該樣本相應輸出標簽的組合, 即:

其中Xi表示第i個包, xij為包Xi中的第j個示例, yk是第k個基分類器的輸出標簽. 鑒于ECC算法是解決單示例多標簽問題的算法, 本篇論文采用與ECC-MIMLSVM+算法相同的策略, 對ECC算法加以改造使其適用于解決多示例多標簽問題. 即在第k個基分類器訓練之前, 首先將標簽yk-1擴展為d維向量y=（y,y,......,y）T（k=1,...,L）, 其中d為示例的維k-1k-1k-1k-1d數, L為標簽的數目.

最終基于新的數據集合訓練第k個基分類器.第四步: 置信度的計算.

為取得更準確的分類結果, ELDCC對多個鏈的輸出結果進行匯總. 假設有m個有序分類器鏈:為m個有序分類器鏈上的輸出. h1,h2......,hm.....y根據公式計算該樣本在所有分類器鏈的平均值.

第五步: 確定閾值t.

第六步: 計算樣本的最終輸出.

利用第四步的置信度, 結合第五步的閾值函數計算該樣本的最終輸出標簽. 當第=(,.....,....,) j個標簽的置信度大于或等于閾值t時, 第j個標簽的最終輸出為1, 表明該樣本具有第j個標簽, 否則該樣本在標簽j上的輸出為0, 表明該樣本不具有標簽j.

對于一個未知標簽的測試樣本X, 將樣本輸入到m個分類器鏈中. 對應其中的一個分類器鏈, 在進行第j個標簽預測時, 獲得對應鏈第j-1個基分類器的輸出值并進行d維擴展獲得新的樣本將該樣本代入第j個標簽的分類函數中fj(X′), 獲得樣本X關于第j個標簽的估計值yj. 對于所有的有序分類器鏈都重復上述過程,將m個分類器鏈的結果進行計算獲得置信向量, 利用置信向量和閾值確定樣本的最終輸出標簽.改進算法的偽代碼:

?

1) 將標簽數據集O隨機分N次, 得到不同的n個數據集L（ii=1,2,…,N）.

2) 循環(huán)訓練集S=｛（Xi, Yi）｝（i=1,2,…,n）, 計算多示

?

4 實驗

4.1 實驗設置

本文使用周志華等人提供的兩個數據集(即表2圖像樣本集和文本樣本集特征)進行實驗.

表2的scene數據集是圖形圖像數據集. 該數據集包含2000個場景圖像, 其中每個圖像都被分配一組標簽. 總共5個類別, 分別是海、沙漠、山、樹和日落. 其中單標簽樣本數目1544個, 約占整個樣本集數量77%左右; 雙標簽441, 約占整個樣本集數量的22%左右,同時屬于三個類的樣本數目極少. 平均每個樣本與1.24±0.44個類標簽有關聯. 每幅圖片所對應的多示例多標簽樣本的示例數為9, 本文用一個15維的特征向量表示每一個示例[20].

表二的Reuters是文本數據集, 從Reuters-21578樣本集[21]中獲得. 我們基于最常用的7個類, 刪除部分只屬于一個類別的文本, 再刪除其中沒有類別和沒有正文的文本, 總共得到8848個文本. 抽出一部分單標簽樣本和所有雙標簽和三標簽樣本, 得到該樣本集所包含2000個文本. 屬于多個類的文本數占該數據集的15%左右, 平均每個文本所屬的類別數是1.15±0.37.每個文本通過滑動窗口術用一組實例向量表示, 滑動窗口的大小設置為50. 包中的示例采取基于詞頻的詞袋模型進行表示, 將詞頻為前3%的詞匯予以保留[22],最終包中的每個示例都由243維的特征向量進行表示.

把本文提出的ELDCT-MIMLSVM+算法跟、MIMLSVM+、MIMLBOOST與MIMLSVM算法進行對比. MIMLBOOST和MIMLSVM算法的參數分別根據文獻[6]和[12]設置為它們的最佳值, MIMLSVM的高斯核為γ=0.22, MIMLBOOST的boosting rounds的值設為25. 為了保證實驗客觀正確, ELDCT-MIMLSVM+算法和MIMLSVM+算法的gamma=le-5. 比較四種算法的平均分類表現.

這四種多示例多標簽算法的評價指標采用五個標準的多示例評價指標: one-error、average precision、hamming loss、ranking loss和coverage. 對于這五個評價指標, 簡單來說one-error、hamming loss、ranking loss和coverage這四個值越小說明算法效果越好; 而average precision則值越大說明算法效果越好.

表2 圖像樣本集和文本樣本集特征

4.2 實驗結果

表3和表4分別顯示了四種不同的多示例多標簽算法在圖像數據集和文本數據集上的實驗結果.

表3 場圖形圖像樣本集實驗結果

從表3可以看出, 在圖像數據集上, ELDCT-MIMLSVM+算法略好于MIMLSVM+, 對于MIMLBOOST和MIMLSVM有明顯的優(yōu)勢.

圖形圖像樣本的分類復雜, 計算數據量大. MIMLSVM+算法主要是為大規(guī)模機器學習設計的算法, 采用了SVM來提高分類, 所以其效率要好于MIMLBOOST和MIMLSVM. ELDCT-MIMLSVM+采用了分類器鏈技術, 也是將問題退化為傳統(tǒng)的機器學習. ELDCT-MIMLSVM+與其它算法不同在于, 在退化過程中依次加入標簽之間的依賴關系, 增強了標簽之間聯系, 所以可以取得比較好的效果.

表4 文本樣本集實驗結果

從表4可以看出, 在文本數據集上, ELDCT-MIMLSVM+算法的前四項指標均小于其他各項算法, Average precision大于其他算法, 所有指標在四種算法中表現最佳.

文本分類相對簡單, 各算法之間差距比較小. SVM在二分問題上有巨大的優(yōu)勢, ELDCT-MIMLSVM+采用了SVM技術, 將問題二分然后再求解, 體現SVM優(yōu)勢, 效果明顯.

表5 算法在圖像數據集上的訓練時間對比

從表5可以看出, 在圖形圖像數據集上ELDCT-MIMLSVM+的訓練時間和測試時間比MIMLSVM+差,略微優(yōu)于MIMLSVM, 對MIMLBOOST有比較明顯的優(yōu)勢.

ELDCT-MIMLSVM+采用分類器鏈設計模式, 當子分類器鏈增加, 耗時就會比較多. 更重要的是ELDCT-MIMLSVM+比MIMLSVM多一步計算標簽之間依賴關系, 這增加了計算量. 所以在訓練時間上會比MIMLSVM+多.

表6 四種算法在文本數據集上的訓練時間對比

從表6可以看出, 在文本數據集上, MIMLSVM+的訓練時間和測試時間最少, ELDCT-MIMLSVM+的訓練時間小于MIMLSVM, 但測試時間比MIMLSVM多. 效率最低的是MIMLBOOST.

與在圖形圖像數據集一樣, ELDCT-MIMLSVM+多一步計算標簽依賴關系, 所以耗時較多, 但這一步驟增強標簽之間聯系, 提高了分類準確率. 如果在強調準確率而不是對時間有特別嚴格的要求, ELDCT-MIMLSVM+算法是首選.

5 總結

從上面數據分析可知, 對于圖像數據集和文本數據集, 在保證訓練時間和測試時間的前提下, ELDCT-MIMLSVM+算法的準確率略優(yōu)于MIMLSVM+,明顯高于另外兩種算法, 并且ELDCT-MIMLSVM+在各項指標中表現優(yōu)異. 因此, 我們可推出結論: ELDCT-MIMLSVM+算法在訓練過程中可以依據標簽依賴關系, 逐步加入依賴程度較大標簽的信息來輔助分類器訓練學習, 從而進一步提高分類器分類的準確率.

1 Kotsiantis SB, Zaharakis I, Pintelas P. Supervised machine learning: A review of classification techniques. Informatica, 2007, 31(3): 249–268

2 Dietterich TG, Lathrop RH, Lozano-Pérez T. Solving the multiple-instance problem with axis-parallel rectangles. Artificial Intelligence, 1997, 89(1-2): 31–71.

3 Boutell MR, Luo J, Shen X, Brown CM. Learning multi-label scene classification. Pattern Recognition, 2004, 37(9): 1757–1771.

4 Schapire RE, Singer Y. BoosTexter: A boosting-based system for text categorization. Machine Learning, 2000, 39(2-3): 135–168.

5 Zhou ZH. A Framework for machine learning with ambiguous objects. Proc. Brain Informatics, International Conference(BI 2009). Beijing, China. 2009. 5819. 6–6

6 Zhou ZH, Zhang ML, Huang SJ, et al. Multi-instance multi-label learning. Artificial Intelligence, 2012, 176(1): 2291–2320

7 Zhou ZH, Zhang ML. Multi-instance Multi-label learning with application to scene classification. The Neural Information Processing Systems, 2006: 1609–1616.

8 Zhang ML. A k-nearest neighbor based multi-instance multi-label learning algorithm. 22ND International Conference on Tools with Artificial Intelligence. 2010, 2. 207–212.

9 Nguyen N. A new SVM approach to multi-instance multi-label learning. 2010 IEEE International Conference on Data Mining. 2010. 109.

10 Wu QY, Ng MK, Ye YM. Markov-MIML: A Markov chain-based multi-instance multi-label learning algorithm. Knowledge and Information System, 2013, 37(1): 83–104.

11 Vapnik V. The Nature of Statistical Learning Theory. Springer-Verlag, 1995.

12 Li YX, Ji SW, Kumar S, Ye JP, Zhou ZH. Drosophila gene expression pattern annotation through multi-instance multi-label learning. Trans. on Computational Biology and Bioinformatics, 2012: 98–111.

13 Read J, Pfahringer B, Holmes G, et al. Classifier chains for multi-label classification. Machine Learning, 2011, 85(3): 254–269.

14 Briggs F, Fern XZ, Raich R. Context-aware MIML instance annotation: exploiting label correlations with classifier chains. Knowledge and Information Systems, 2015, 43(1): 53–79

15 Platt JC. Fast training of support vector machines using sequential minimal optimization. Advances in Kernel Methods-Support Vector Rning. MIT Press, 1999: 185–208

16 Gǎrtner T, Flach PA, Smola AJ. Multi-instance kernels. Proc. of the 19th Intenational Conference on Machine Learning. Sydney, Australia. 2002. 179–186.

17 Yakhnenko O, Honavar V. Multi-instance multi-label learning for image classification with large vocabularies. BMVC. 2011. 1–12

18 Pei Y, Fern XZ. Constrained instance clustering in multi-instance multi-label learning. Pattern Recognition Letters, 2014, 37(1): 107–114.

19 Zhang ML, Zhou ZH. M3MIML: A maximum margin method for multi-instance multi-label learning. Proc. of the 8th IEEE International Conference on Data Mining (ICDM’08). Pisa, Italy. 2008. 688–697.

20 Haussler D. Convolution kernels on discrete structures, [Technical Report]. UCSC-CRL-99-10. Dept. of Computer Science, Univ. of California at Santa Cruz. Santa Cruz, CA. July 1999.

21 Sebastiani F. Machine learning in automated text categorization. ACM Computing Surveys, 2002, 34(1): 1–47.

22 Andrews S, Tsochantaridis I, Hofmann T. Support vector machines for multiple-instance learning. Advances 696 in Neural Information Processing Systems 15, 2003: 561–568.

23 Yang Y, Pedersen JO. A comparative study on feature selection in text categorization. Proc. of the 14th International Conference on Machine Learning. Nashville, TN. 1997. 412–420.

Multi-Instance Multi-Label Support Vector Machine Algorithm Based on Labeled Dependency Relation Ensemble Classifier Chain

LI Cun-He, WANG Wen-Jie
(College of Computer and Communication Engineering, China University of Petroleum, Qingdao 266580, China)

ECC-MIMLSVM+is an algorithm of multi-instance and multi-label learning framework. This algorithm proposes a method based on classifier chain, but it does not consider the dependencies between labels. When the number of tags increases, the length of the sub classifier chain also increases, making the error propagation problem prominent. Therefore, this paper presents a kind of improved algorithm, combining ECC-MIMLSVM+algorithm and the label dependencies. ELDCT-MIMLSVM+algorithm is designed, which is based on ensembles of label dependencies classifier chain to avoid the information loss and improve the classification accuracy. The experiment results show that the algorithm has good effect.

multi-instance multi-label; SVM; ensembles of label dependencies; classifier chains

2016-07-24;收到修改稿時間:2016-08-22

10.15888/j.cnki.csa.005686