1、 MIML：多示例多標記學習*周志華I張敏靈21南京人學計算機軟件新技術國家重點實驗室，南京210093河海人學計算機及信息工程學院，南京2100981.引言在利用機器學習技術解決實際問題時，常見的做法是先對真實對彖進行特征提取，用一個特征向屋來描述這個對彖，這樣就得到了一個示例(instance),然后把示例與該對象所對應的類別標記(label)關聯(lián)起來，就得到了一個例子(example)。在擁有了一個較人的例子集合之后，就可以利用某種學習算法來學得示例空間與標記空間Z間的一個映射，該映射可以預測未見示例(unseenmstaiice)的標記。假設每個対彖只有一個類別標記，那么形式化地來說，

2、令尢為示例空間、為標記空間，則學習任務是從數據集(刼皿)，佃2,血)，(如，如)中學得函數n，其中血尢為一個示例而m為示例所屬的類別標記。在待學習對彖具有明確的、單一的語義時，上面的學習框架已經取得了巨大的成功。然而，真實世界的對彖往往并不只具有唯一的語義，而是可能具有多義性的。例如，圖1(a)中的這幅圖像，既可認為它屬“人彖”這個類別，也可認為它屬于“獅子”、“草地”甚至“熱帶”、“非洲”：圖1(b)中的這個網頁，既可認為它屬J：“體育”這個類別，也可因為貝克漢姆娛樂明星味十足而認為它屬J：“娛樂”類，甚至可以因為皇家馬德里足球隊出訪的旅游、賺錢性質遠人J：比賽性質而認為它屬J-“旅游”類、

3、“經濟”類。由這樣的多義性對彖不再只貝有唯一的語義，這就使得前述的只考慮明確的、單一的語義的學習框架難以取得好的效果。值得注意的是，對多義性對彖進行學習是一個非常重要的問題。目前實際應用中遇到的很多難題都是由對喙的多義性所造成的。例如在基內容的圖像檢索中，眾所周知的難題是“語義鴻溝”，即從圖像的低層特征到高層語義Z間存在難以逾越的障礙。筆者認為，這一語義鴻溝存在的本質原因之一，就是因為圖像是一種多義性對彖：同樣的特征描述、不同的語義。試想，如果一幅圖像只具有唯一的語義，那么哪里還會有什么語義鴻溝呢？筆者認為，要解決多義性造成的問題，首先需要從某個任務所涉及的眾多“可能語義”中把某個具體的多義性

4、對彖所能具有的“合適語義”找出來，然后再根據具體的上卜文從這些“合適語義”中確定當前的“語境語義”。而其中第一步，實際卒本文得到國家|然科學基金(60635030)、江蘇省|然科學基金(BK2008018)和江蘇省333高層次人才培養(yǎng)工程基金的資助(a)一幅圖像APFhoiaSoccarairb4tdEd4inIjuHbhoiliA4nxconfancinSin滬pccoCflJulyNEWSAiemRealMadridSetsOffforWorldTourrtvJug400PMETMADPID.-RrlMaoeqinninq&合刃odd:ouftBangkok1willoethesecond

5、triptcsixw-eekforBeckhamsrMichal6閉nr4iowreEnjUndnational1earnirOftugesemcrieiderijjismakethejourrey.(b)個網頁eaiMadridsirstgsmev.OhcagoonSuidaj3iMddlg.Me人Qu.Gi：comMaya:hel_gAngckaoforomovingnntoAcq.圖1多義性對象的兩個例子上就是要為對象賦予合適的類別標記子集，而不再是唯一的類別標記。針對這個目的，筆者提出了MIML即多示例多標記學習”(Multi-InstanceMulti-Labelleanuiig)這

6、一學習框架W本章將對這方面的研究進展做一個簡介，主要內容及更詳細的介紹可參見。MIML框架提出MIML的基本考慮，是多義性對彖往往具有復雜的內涵，只用一個示例(即一個特征向最)來進行表示是一種過度簡化，在表示階段就丟失了有用的信息，后續(xù)的學習階段將面臨極人的困難。事實上，一個多義性對彖往往可以用多個示例來描述。例如對圖像來說，如杲使用某種技術將圖像劃分為若干個區(qū)域，那么每個區(qū)域都可以用一個示例來描述，這樣，一幅圖像就可表示成多個示例組成的一個集合；對文檔來說，如果使用某種技術將其劃分為若干部分，例如不同的章節(jié)段落，那么每個部分都可以用一個示例來描述，這樣，一個文檔就可表示成多個示例的集合。考慮

7、到多義性對象具有多個語義，我們所要學習的實際上就是從示例集合到類別標記集合上的一個映射。形式化地來說，令尢表示示例空間，表示類別標記空間，則多示例多標記學習：給定數據集(Xi,X)，(X2匕)，(Xf)，目標是學得/:2VT2兒其中，X-c為一組示例龍門血2,，血忑“尢&=1,2,，7右)，iftix-cy為X,的一組合適類別標記“1.列2,，如門，yiky(k=乙)。7鮎為X,中所含示例的個數，A為X中所含標記的個數。對多義性對彖的學習，機器學習界在多標記學習(multi-labellearning)3這一框架(fiamewoik)卜已經有一些研究。在這一框架卜，每個對彖由一個示例描述，該示

8、例具有多個類別標記，學習的目的是將所有合適的類別標記賦予未見示例。形式化地來說，多標記學習:給定數據集1.、勺,（叼.，（如$“）,目標是學得t2兒其中XiG尢為一個示例，YiC為M的一組合適類別標記如，孫2,，/，yik（k=1,2,乙）。心為X中所含類別標記的個數。利用一個示例集合來描述一個對彖，這一技術在多示例學習（multi-instanceleammg）同框架卜已有很多研究。在多示例學習框架下，每個対彖由一組示例（即一個示例包”）描述，該示例具有一個類別標記，學習的目的是預測未見示例包的類別標記。形式化地來說，多示例學習：給定數據集（X1,心（X22），（尤心如）,目標是學得其中，X

9、iC尢為一組示例力門.2,XijX（J=1.2,-,彼），m為與X；的類別標記。n.j為X,中所含示例的個數。如果再考慮本章開頭時所提到的傳統(tǒng)監(jiān)督學習（單示例、單標記）框架，那么我們就有了四種學習框架。圖2給出了一個直觀的對比。instanceinstanceobjectlabelmstaiice # # # #instance/（a）傳統(tǒng)監(jiān)督學習（單示例、單標記（b）多示例學習（多示例.單標記）Jabelinstance/labelinstancemstaiiceinstance（c）多標記學習（單示例.多標記）/label、object（d）多示例多標記學習四種機器學習框架(UP) # #

10、 既然已經有了好幾個學習框架，為什么我們還需要MIML呢？首先，從表示能力上來看，傳統(tǒng)監(jiān)督學習框架可視為多示例學習框架或者多標記學習框架的特例，而傳統(tǒng)監(jiān)督學習框架、多示例學習框架以及多標記學習框架均可視為MIML的特例。換句話說,其他三種框架卜所覆蓋的情形，MIML框架也覆蓋了：而MIML所覆蓋的一些情形，其他三種框架未必能夠覆蓋。在刈真實世界學習問題求解時，好的表示往往至關重要，在一定程度上共至直接決定了學習的成敗。采用了合適的表示，有可能更好地捕獲學習對彖所含的信息，從而使得學習任務變得容易完成：采用不合適的表示，有可能已經丟失了重要信息，從而使得學習任務變得極其困難。使用MIML來對多義

11、性對彖進行表示，有助明示示例與類別標記Z間的聯(lián)系，從而有助學習任務的解決。實際上，多標記學習框架所面臨的困難，很人程度上是因其用一個示例來描述多義性對彖所造成的。如前所述，在多標記學習框架卜，學習目標是從圖2(c)可以看出，這是一個一對多映射(從一個示例到多個類別標記)，而一対多映射并不是一個合式函數。與多標記學習框架相比，MIML框架更加合理一些，雖然多對多映射看起來比一對多映射復雜，但是多對多映射畢競是一個合式函數，具有很多一對多映射所不具備的數學性質，這就使得學習任務可能得以較好地完成。值得一提的是，與簡單地對合適標記進行預測相比，了解一個対彖為什么具有某個類別標記可能在某些場合具有更重

12、要的意義，而MIML為此提供了一種可能。如圖3所示，與圖3(a)中難以了解類別標記的原因不同，在圖3(b)中，我們可能可以知道，對彖具有l(wèi)abel】的原因是因為其含有iiistaiiccn*JI有的原因是因為其含有instancopiflJ該對象同時包含instancoi與insUuig則使得其具Wlabcljo:;pabelobject_z-Linstance0mstaiice；y?zmstanceimstance/I|z辺abeQ(a)一個具有/個類別標記的對彖(b)示例與類別標記之間的關系圖3MINIL為理解示例與標記之間的關系提供了可能除了多標記學習問題，NAML還有助涉及復雜概念的單

13、標記學習問題的解決。如圖4(町所示，対J：非洲”這個語義內涵豐富的概念，與Z對應的圖像在表現形式上具有很人的差異性。因此，対圖4(町左上角所示的圖片，將其正確地分類為“非洲”是一個困難的問題。然而如圖4(b)所示，如果我們能夠允分利用該圖片包含的樹木、獅子、人彖、草地等子概念”，由這些子概念和對而言更加明確且易學習，因此我們先利用MIML學習出子概念，然后再利用這些子概念導出“非洲”這一高層概念，這可能比直接對“非洲”進行學習要容易很多。(a)“非洲”是一個復雜.難以學習的高層概念b)利用MIML學習“子概念”，再山“子概念”導出復雜高層概念圖4MIML有助丁學習復雜高層概念為了發(fā)揮MIML框

14、架的能力，就蠱耍設計出有效的算法。為此，我們基J：退化策略提出了MIMLBOOST算法和MIMLSVM算法山巴基J：正則化(regulaiization)機制提出了D-NHMLSVM算法和M3MIML算法。本章第3節(jié)將對這些工作進行簡介。如果能夠直接接觸原始數據對彖，那么我們可以利用MIML進行建模1何獲取更多的有用信息，但在不少應用中，尤其是數據挖掘應用中，我們往往只能得到第二手數據，這些數據已由他人進行了特征提取并將一個對象表示為一個特征向嵬。在這種情況卜，雖然不能利用MIML表示的效力，但是MIML學習仍然能發(fā)揮重要的作用。我們提出了INSDIF算法，將單示例多標記樣本轉化為MIML樣本

15、進行學習以獲得更好的性能。本章第4節(jié)將對此進行簡介。如前所述，MIML框架還有助J：對復雜高層概念的學習，為此我們提出了SUBCOD算法巴通過發(fā)現目標概念的子概念來將單標記樣本轉化為多標記樣本，從而利用MIML的幫助提高學習性能。本章第5節(jié)將對此進行簡介。MIML學習算法3.1基于退化策略的MIML學習算法如第2節(jié)所述，傳統(tǒng)監(jiān)督學習是多示例學習或者多標記學習的特例，而傳統(tǒng)監(jiān)督學習、多示例學習以及多標記學習均是多示例多標記學習的特例。因此，一種簡單的MIML求解策略是以多示例學習或者多標記學習為橋梁，將MIML問題退化為傳統(tǒng)監(jiān)督學習問題進行求解。策略1-以多示例學習為橋梁：多示例多標記學習的目標

16、是學得f:2a，該目標可以簡化為一個多示例學習問題，即學習相應的目標函數/a/zl：2a，x-l.+lo此時，對丁任意的?/e”m（Xz）=+i當且僅當妙eX否則f.wL（Xz）=-i基于此，給定新樣本X*,與之對應的類別標記集合為“=|溝”旳山（中,?/）=+1。該多示例學習問題還可進一步轉化為傳統(tǒng)監(jiān)督學習問題，其目標是學得fs/SZ一1.+1并指定如何由fsiSLxtj.y）（j=1.2,，彼）的取值確定hIIL（Xi,y）的取值。此時，對于任意的?/eAfsiSL（Xihy）=+1當且僅當2/eK否則fsJSL（Xij,y）=-1。特別地,我們采用文獻7中的方法將多示例學習問題轉化為傳統(tǒng)

17、監(jiān)督學習問題，即hIIL（Xt,y）=如口刀工內兀厶（小）。值得注意的是，上述轉化過程也可采用其他方法實現。策略2-以多標記學習為橋梁：多示例多標記學習的目標是學得f:2a，該目標可以簡化為一個多標記學習問題，即學習相應的目標函數血“:zT2兒此時，対J：任意的冇ez，fMLL（Zi）=/（XJ3且僅當=0（XJ,:2，vtZ。基J：此，給定新樣本X*,與之對應的類別標記集合為二九“厶該多標記學習問題還可進一步轉化為傳統(tǒng)監(jiān)督學習問題，其目標是學得fsisL：2Xyt7+1。此時，對于任意的?/ey,fsiSL（Zi.y）=+1當且僅當?丿GX否則.fsiSL（Zi.y）=-lo基J此，=vfs

18、iSL（i,y）=+lo本文采用文獻8中的“構造性聚類（constructiveclustering）”方法實現所需的映射函數旅值得注意的是，上述轉化過程也可采用其他方法實現?；〔呗?.我們設計了多示例多標記學習算法MIMLEOOST。該算法以多示例學習為橋梁,將MIML問題退化為傳統(tǒng)監(jiān)督學習問題求解。首先，MIMLBOOST算法將每個多示例多標記樣本（冷轉化為|M個多示例單標記樣本（Xi，/兇,創(chuàng)）協(xié)wy。其中，兇，“包含為個示例（切,切,，（中崩），每個示例由X所含示例與類別標記妙拼接而來。此外，GpG,?/=+i當且僅當?/GK，否則=1/其中偽，舒幾。假設采用仃損失函數度最心Z2)，

19、則式(2)中的優(yōu)化問題可以重寫為：As7力”聞+II等細+為戸+為&1(4)t=l0一必/f(Xj.iiutxff(xij)1-4ok,(如6-必0,/y.某樣本在每一個類上的輸出，MMIML算法定義X)在第厶類上的間隔為：K(2)max.xeXi(伽,a?)+bjllwJI其中，,)用丁計算向量Z間的點積。m3miml算法進一步假設模型在(X,K)上的間隔由各個類上間隔的最小值確定，并且模型在整個訓練集上的間隔(記為)由所有樣本間隔的最小值確定。在理想情況卜，假設模型可以對訓練集中的所有樣本正確分類。則V/!，存在模型伽,切)卩使得卜式成立：乂maxwx,(x+bt)l(7)并且對丁任意的l

20、ey,最少存在一個z1.2m使得式(7)取等號。由此即為:minmlniimley必ma%A(5Q+0)l|w；|(9)(9)(9)(9)=minminleyiimy(Qmaxgext(suchthat(max(wf1,ifIeY/I.ifZGV/ 其中，h表示X在中的補集。式所示的不等式按照X取值為+誡_1兩種不同的情況在式(9)中對應不同的約束條件。而最人化式(8)所示的間隔mm相當最小化iiuixUwJI2,對應J-式(9)中的優(yōu)化目標。式(9)在優(yōu)化目標和約束條件中均涉及nmx函數，難以使用優(yōu)化技術直接尋優(yōu)。為此我們利用如卜所示的不等式在一定程度上放寬優(yōu)化目標和約束條件：inaxl|w

21、/|21-Oiij(1j0.0dj0(1jnt)其中Si=ilim,leYi是具有標記Z的樣本對應的索引集合。相應地，S=/|1im,/K為不具有標記Z的樣本対應的索引集合。W=wi.w-j.,w-f所有權值向量構成的參數矩陣而b=加,.，殲為所有偏置構成的參數向量。E=&|1i77Z,IeYi和G=匍川im.IYi.ij仏為和應的松弓也變屋集合。此外，目標函數中的參數Q用平衡系統(tǒng)在訓練集上的經驗誤差和間隔。優(yōu)化問題式(11)是一個具有凸目標函數和線性約束條件的二次規(guī)劃問題，但僅僅假設了線性模型用r樣本分類。為了使得系統(tǒng)具有非線性分類能力，我們將式(11)在其対偶形式卜利用核技巧求解,相應的優(yōu)

22、化問題變?yōu)椋?12)subjectto:V21yin,IEysuchthat()anGif/6Kt00紺C(ljif/$K工+工Is=0圧Sf迢3v=l/其中,集合4=ai（lim,IeK，B=&J1im.ZT7,1j%，r=為|1?：m,leK以及=如川iSM/eK,lj0,/where/（）=刀（計士（碼,庁iScj=lM3NUML算法的貝體細節(jié)請參見5。利用MIML學習單示例樣本如前所述，如呆能夠直接接觸原始數據對彖，那么我們可以利用MIML進行建模而獲取更多的有用信息，但在不少應用中，我們只能得到他人進行特征提取后的數據，一個對彖由一個特征向量表示。事實上，対J：采用單示例表示的対彖，

23、此時該対彖多個類別標記所蘊含的多樣性信息僅僅內嵌單一的示例中。如果能將對彖單一示例的表示形式合適地轉化為包（一組示例）的表示形式，使得包中的每個示例能從特定方面反映對彖所包含的某種信息，那么將有助J：學習問題的解決?；∩鲜隹紤]，我們設計了INSDIF（INStanceDIFferentiation）方法。該方法將單示例多標記樣本轉化為多示例多標記樣本，從而利用MIML框架獲得更好的學習結果?？偟膩砜矗琁NSDIF采用了基“示例區(qū)分”策略的兩階段學習算法。在算法的第一階段，INSDIF將每個樣本轉化為包的表示形式從而在輸入空間中顯式地描述對彖歧義性。在算法的第二階段，INSDIF利用多示例多標

24、記學習器對轉化后的數據集進行學習。令S=（幾加）.，（如,為訓練集。其中，爼疋尢為一個示例，而YiCy為與對應的一組類別標記。此外，設每個示例都是一個維的特征向量。在算法的第一階段，INSDIF為每個可能的概念類/G，計算一個原型向最切該向屋為具有類別/的所有訓練樣本對應的均值向最：whereGS,IGYJ(14)INSDIF基J：上述原型向最將對彖轉化為包的表示形式。貝體來說，在求得每一類的原型向屋后,INSDIF將每個樣本勸轉化為一組示例構成的包3,包中的每個示例対應J：樣本與某個原型向翁之間的差值：J3f=Xi-vtly（15）基J：式（15）,每個樣本由單一示例的表示形式血轉化為包的表

25、示形式B，且包的人小等所有可能的概念類別數。特別地，包中的每個示例（即血-訕考察了給定樣本與類別泛間的空間關系，從而蘊含了該樣本與此類別相關的某種信息。實際上，除了利用上述方式實現單示例表示向多示例表示的轉化，還可采用其它策略來實現該目標。在算法的第二階段，INSDIF采用MIML學習算法對轉化后的數據集S*=（場#），0“,心）進行學習。在提出該算法時叫我們使用了一種類似J：RBF神經網絡的兩層分類結構來實現該目標，但其他的MIML學習算法，例如本章第3節(jié)中所述的算法都可用于此處。具體地說，該結構的輸入為一個包含7?個示例的包=加2,.,包中的每個示例加為一個d維的屬性向量加.如2,加仃該結

26、構的輸出包含了7個實值，好，其中每個實值輸出劭與標記2相對應。該結構的第一層由M個包Ci.C2,-,6”組成，其中每個包Cj對應丁簇Gj的中心且Gi,G2.-.,Ga/將訓練集劃分為M個互不相交的子集，即U蕓1Gj=”1,“2.，血且（7,Gj=0。該結構的第二層對應J：權值矩陣W=【切其中吟為連接包C盧輸出yi的權值。我們將每個包看作一個原子對彖，基J：Hausdorff距離度鼠包Z間的距離并利用-medoids算法 將集合內小2Mm劃分為M個不相交的簇G.G2廠小這樣，每個子集Gj対應的中心G即為：Cj=arginin刀血（人“）（16）AGBqG.其中，亦（A.用J：計算包”與包Z間的H

27、ausdorff距離。由聚類過程有助發(fā)現數據集的內在結構信息，因此基J：上式求得的子集中心可能蘊含了不同包的分布信息。由此，每個包刀可以轉化為一個M維的屬性向量如（）,如，必（），其中0（3）=切（.0）。INSDIF算法所需的第二層權值矩陣W=wjiy.IxT可通過最小化如卜的誤差平方和函數得到：=（17）其中，？力）=刀舊專如旳為分類結構相対丁包D在第Z類上的實際輸出。此外，必為算法和対J：包D在第2類上的期望輸出，當？GK時必取值為+1否則取值為-1。將上式相対J：變最吟求導并設導數值為0,則最小化上述誤差平方和函數等價J：求解如卜的方程組：（勺）W=T（18）其中，矩陣=0tjrrtx

28、.v/且含有元素如=0J（3），矩陣T=tdrnxT且含有尤素/=侏這里，我們使用奇異值分解來對上式求解。在INSDIF算法的兩階段訓練過程完成后，給定新樣本分，與之對應的類別標記集合為Y*=“加附）=刀芝1紗如*）0,/G。其中，少=-Vil為與分對應的包的表示形式。INSDIF算法的貝體細節(jié)請參見26。利用MIML學習復雜高層概念如前所述，MIML框架還有助対復雜高層概念的學習，為此我們提出了SUBCOD（sub-conceptdiscovery）算法叫通過發(fā)現目標概念的子概念來將單標記樣本轉化為多標記樣本，從而利用MIML的幫助提高學習性能。SUBCOD采用了基J：“子概念發(fā)現”策略的兩

29、階段學習算法。在算法的第一階段，SUBCOD基J：訓練包中的所有示例進行聚類分析。由此，算法發(fā)現與高層概念對應的一組低層子概念，并將多示例單標記樣本轉化為多示例多標記樣本。在算法的第二階段，SUBCOD利用監(jiān)督學習器獲得低層子概念與高層概念Z間的映射關系。由此，某JMIML學習器對轉化后的數據集進行學習，并利用監(jiān)替學習器所得的映射關系對新樣本的類別標記進行預測。令s=，(x,n,如)為訓練集。其中，x：c尢為一組示例構成的包，而加6y為與尤對應的類別標記。在算法的第一階段，SUBCOD將所有訓練包中的示例構成數據集=可1,，叼切，皿”小為了方便起見，我們將D中所有示例重新索引并記為，0?n。其

30、中，N=K嚴。我們利用具有M個混合成分的混合高斯模型對數據集D進行建模，并將所得模型中的每個混合成分作為相應的低層子概念。我們基J：標準的EM算法對高斯混合模型中的參數進行學習。簡要地說，我們首先隨機初始化各個高斯混合成分的均值向量“人.，協(xié)方差矩陣工人.以及混合系數葉伙=1.2.M)。在EM算法迭代的每一輪中，我們首先求得D中每個樣本隸屬J：各混合成分的概率：=珂人“山耳：刃J仏刀舊可“仙庇，令)(19) # # # (20)(21)(22)然后，基丁所得數值対模型參數進行更新:刀舊*FT在上述EM過程收斂或迭代達到指定輪數后，我們通過如卜方式確定D中每個樣本對應的低層子概念:sc(xi)=

31、argmax(k=L2.A/)(23)b基J：上述結果，我們?yōu)槊總€訓練包X,賦予一個M維的二值類別向最C以表達其隸屬的一組低層子概念。其中，切=+1代表X,具有第j個高斯混合成分所代表的子概念，否則C1J=-lo特別地，基于式(23),cj=+l當且僅當3a;X/:sc(x)=j,否則c=一1。值得注意的是，對于兩個具有相同高層概念的包而言，由J：它們所含的示例不同，其対應的低層子概念有可能不同。由J：上述確定子概念的過程基非監(jiān)督聚類的方式實現，因此并未考慮每個包所含的高層概念。為此，我們通過考察子概念與X,的高層概念(即s)Z間的關系対二值類別向鼠做進一步的修正。具體來說，我們采用最人化間隔

32、策略來實現該目標。設竝為用J：子類別標記修正的M維實值向最，向量的每一維切0=1,+1.0區(qū)間Z內。其中，zij=+1代表標記5的取值應保持不變而Zij=1則代表應翻轉標記dj的取值。此外，設向量7；=CiOZj,其中qij=CijZij(j=1,2.M)。另設ci,C2,，Cm中至少有0個標記不能被翻轉?；谏鲜霰硎?SUBCOD算法將求解如卜的優(yōu)化問題：(24)mm舟|訓瑕+Cgls.t.yi(wf(ciZi+6)1V1m其中,Z=zi,W2.，通過優(yōu)化上述問題，我們可以得到最人化間隔意義卜的修正值Z。我們迭代地求解式(24)。在迭代過程開始前，我們將Z的每一個元素初始化為1。在迭代優(yōu)化的

33、每一輪中，我們首先固定Z的取值來優(yōu)化變鼠血與從二次規(guī)劃問題)：然后，我們固定變尿0與加勺取值來優(yōu)化修正值Z(線性規(guī)劃問題)。上述迭代過程不斷重復直至收斂或達到指定迭代輪數。此后，我們利用修正值Z將每個訓練包X刈應的二值類別向最修正為乙。其中，劭=+1當且僅當切知0，否則=-1o上述修正過程完成后，初始的多示例單標記訓練集S=(Xi,：“).,(X,”,：如J即可轉化為相應的多示例多標記數據集S*=(XbCi),-,(Xm,Cm)o基于轉化后的數據集亍,我們可以學習得到一個MIML學習器人：2t2$(=1,2,，M)。在算法的第二階段，為了將測試樣本在上的多標記輸出映射到所需的單標記，SUBCO

34、D使用一個監(jiān)督學習算法從(Cb/A),-.?(C/n,?/,)中學習得到一個分類器/：2T”在SUBCOD算法的兩階段訓練過程完成后，給定新樣本X*,與之對應的類別標記即為:=/(力.(X*)。SUBCOD算法的具體細節(jié)請參見2。結束語NflNlL是一個有潛力的而向多義性對彖的學習框架，本章対這方面的一些初步工作皿MS進行了介紹。最近，在基JXHML的圖像標注問、MIML的距離度屋學習的以及生物信息學應用】方面又有一些新進展。作為一個新框架，XHML還有很多內容需要進一步探索。我們相信，在今后的幾年中，在MIML的學習理論、高效算法、新型應用等方面都會有新成果出現。 參考文獻ZhouZH.Zh

35、angM-L.Multi-instancemulti-labellearningwithapplicationtosceneclassification.In:ScholkopfB,PlattJ.HofmannT.eds.AdvancesinNeuralInformationProcessingSystems19(NIPS06).Cambridge,MA:MITPress,2007,1609-1616.ZhouZH、ZhangM-L.HuangS-J.Li-F.NIINIL:Afiainewoikforlearimigwithambiguousobjects.CORRabs-08083231,

36、2008.TsoumakasG,KatakisI.Multi-labelclassification:Anoverview.InternationalJournalofDataWarehousingandMining,2007,3(3):1-13.周志華-多示例學習.見：劉大有主編，知識科學中的基本問題研究，北京：清華大學出版社,2006.322-336-ZhangM-L,ZhouZ-H.Amaximummarginmethodformulti-instancemulti-labelleaimng.In:Proceedingsofthe8thIEEEInteniationalConferenc

37、eonDataMining(ICDW08),Pisa,Italy,2008,688-697.ZhangM-L,ZhouZH.Multi-labellearningbyinstancedifferentiation.In:Proceedingsofthe22ndConferenceonArtificialIntelligence(AAArO7)9V1ancouver.Canada,2007,669-674.XuX,FrankE.Logisticregiessionandboostingforlabeledbagsofinstances.In:Proceedingsofthe8thPacific-

38、AsiaConferenceonKnowledgeDiscoveryandDataMining(PAKDD04)ySydney,Australia.LNAI3056,2004,272-281.ZhouZH.ZhangM-L.Solvmgmulti-instanceproblemswithclassifierensemblebasedonconstructiveclustering.KnowledgeandInformationSystems.2007,11(2):155-170.BoutellMR,LuoJ,ShenX.BrownCM.Learnmgmulti-labelsceneclassi

39、fication.PatternRecognition.2004、37(9):1757-1771.GaitnerT.FlachPA、KowalczykA、SmolaAJ.Mult卜instancekernels.In:Proceedingsofthe19thInteniationalConferenceonMachineLearning(ICML02),Sydney,Australia.2002,179-1S6.EvgemouT.MicchelliCA,PontilM.Learningmultipletaskswithkernelmethods.JournalofMachineLearningResearch.2005,&615-637.CheungPM.KwokJT.Aregularizationfiameworkformultiple-instanceleaimiig.In:Proceedingsofthe23rdInternationalConferenceonMachineLearning(ICML06),Pittsburgh.PE,2006,193-200.SmolaAJ,VishwanathanSVN.HofinannT.Kernelmethodsformissingvariables,hi:Proc