雙層多示例集成學(xué)習(xí)

袁漢寧

(武漢理工大學(xué)經(jīng)濟(jì)學(xué)院，湖北 武漢 430070)

在多示例學(xué)習(xí)(multiple instance learning，MIL)中，訓(xùn)練集由具有概念標(biāo)記的包組成，包是若干示例的集合，如果包被標(biāo)記為正，則包中至少有一個(gè)示例為正;如果包被標(biāo)記為負(fù)，這個(gè)包中所有的示例都為負(fù)。多示例學(xué)習(xí)中存在的最大挑戰(zhàn)在于雖然包的概念標(biāo)記是已知的，但正包中的示例的概念標(biāo)記是模糊的，不能將包的標(biāo)記直接傳遞給包中的示例。其學(xué)習(xí)任務(wù)是通過(guò)對(duì)訓(xùn)練集中有標(biāo)記包的學(xué)習(xí)，建立和優(yōu)化目標(biāo)概念模型，對(duì)未標(biāo)記的包或示例分類或預(yù)測(cè)。

傳統(tǒng)多示例集成(traditional multiple instance ensemble，TMIE)學(xué)習(xí)是在包層次上實(shí)施重抽樣建立多個(gè)訓(xùn)練集，然后使用訓(xùn)練集生成集成個(gè)體。集成個(gè)體間的差異是提高集成學(xué)習(xí)性能的重要因素。在多示例集成學(xué)習(xí)中集成個(gè)體間的差異是通過(guò)訓(xùn)練數(shù)據(jù)的隨機(jī)性和獨(dú)立性提供的，TMIE只是在包層次上實(shí)現(xiàn)數(shù)據(jù)的重抽樣，整個(gè)數(shù)據(jù)集合沒(méi)有得到充分的攪動(dòng)，限制了集成個(gè)體間的差異性，影響了集成學(xué)習(xí)性能。針對(duì)這種情況，筆者設(shè)計(jì)了包內(nèi)示例的重抽樣方法并提出了一種雙層多示例集成(double multiple instance ensemble，DMIE)學(xué)習(xí)框架，該框架實(shí)現(xiàn)了包層次上和示例層次的重抽樣，充分?jǐn)噭?dòng)訓(xùn)練數(shù)據(jù)，增強(qiáng)集成個(gè)體間的差異性，能更有效地提高分類器的分類精度。

1 多示例集成學(xué)習(xí)

多示例學(xué)習(xí)最先由DIETTERICH［1］等在藥物活性預(yù)測(cè)中提出，是一類特殊的機(jī)器學(xué)習(xí)任務(wù)。目前多示例學(xué)習(xí)的研究?jī)?nèi)容主要包括:①基于監(jiān)督學(xué)習(xí)的多示例學(xué)習(xí)算法。該類方法主要思想是將多示例學(xué)習(xí)轉(zhuǎn)化成監(jiān)督學(xué)習(xí)，如ANDREWS提出的支持向量機(jī)的mi-SVM算法和MI-SVM算法［2］，WANG 等提出的基于距離的 Bayesian-KNN和Citation-KNN算法［3］。②基于非監(jiān)督學(xué)習(xí)的多示例學(xué)習(xí)算法，如ZHOU等提出的多示例學(xué)習(xí)的聚類算法Bamic［4］。③基于半監(jiān)督學(xué)習(xí)和主動(dòng)學(xué)習(xí)的多示例學(xué)習(xí)算法，該類算法是針對(duì)標(biāo)記樣本稀疏和標(biāo)記代價(jià)昂貴的情況，利用未標(biāo)記數(shù)據(jù)的學(xué)習(xí)算法。如RAHMANI等提出的MISSL(multiple instance semi-supervised learning)算法［5］;ZHOU 提出的 MissSVM(multiple instance learning by semi-supervised support vector machine)算法［6］。

由于其獨(dú)特的性質(zhì)，多示例學(xué)習(xí)在國(guó)際機(jī)器學(xué)習(xí)界引起了極大的反響，被認(rèn)為是一種新的學(xué)習(xí)框架，其具體應(yīng)用包括基于內(nèi)容的圖像檢索，遙感圖像檢索、股票預(yù)測(cè)、藥物活性研究、自然場(chǎng)景分類、Web目錄頁(yè)面推薦和計(jì)算機(jī)安全領(lǐng)域，如口令檢查、入侵檢測(cè)和網(wǎng)絡(luò)管理等［7］。

與傳統(tǒng)的分類器相似，大部分多示例學(xué)習(xí)的分類器受數(shù)據(jù)驅(qū)動(dòng)且不穩(wěn)定。集成學(xué)習(xí)是一種能有效提高不穩(wěn)定的分類器分類精度的方法［8］。在傳統(tǒng)的多示例集成學(xué)習(xí)TMIE［9］中，包被看作獨(dú)立的樣本，對(duì)訓(xùn)練集有放回地抽取訓(xùn)練樣本，為每一個(gè)基本分類器都構(gòu)造出一個(gè)與訓(xùn)練集同樣大小但各不相同的訓(xùn)練集，通過(guò)抽樣得到的訓(xùn)練集對(duì)基本分類器進(jìn)行訓(xùn)練，得到不同的集成個(gè)體，再通過(guò)投票對(duì)集成個(gè)體的學(xué)習(xí)結(jié)果進(jìn)行整合。TMIE在包層次上實(shí)現(xiàn)數(shù)據(jù)的重抽樣，一旦包被選中，包中的所有示例就會(huì)全被選中，因而降低了訓(xùn)練集之間的差異性。如果想獲得差異性最大的訓(xùn)練集集合，就要在示例層次上實(shí)現(xiàn)重抽樣。因?yàn)橹爻闃雍笳械氖纠赡苋繛樨?fù)示例，因此直接簡(jiǎn)單地在所有示例上實(shí)現(xiàn)重抽樣可能會(huì)破壞包的性質(zhì)，導(dǎo)致正包的標(biāo)記與內(nèi)容矛盾。在設(shè)計(jì)示例層次上的重抽樣算法時(shí)必須考慮保持正包的性質(zhì)不變。

2 雙層多示例集成學(xué)習(xí)方法

2.1 示例層次上的重抽樣

在雙層多示例集成學(xué)習(xí)中，樣本重抽樣是通過(guò)包層次和示例層次上的重抽樣實(shí)現(xiàn)的。在包層次上的重抽樣中，每個(gè)包作為獨(dú)立的樣本被抽取而在示例層次重抽樣中，包中每個(gè)示例被作為獨(dú)立的樣本被抽取。實(shí)現(xiàn)示例層次重抽樣的關(guān)鍵在于保證抽樣后的包的性質(zhì)不變。對(duì)于負(fù)包，在包中示例上實(shí)施重抽樣不會(huì)改變包的性質(zhì)。對(duì)于正包，因?yàn)榘惺纠臉?biāo)記是模糊的，實(shí)施重抽樣后不能保證抽樣后的正包中至少有一個(gè)正示例，甚至?xí)龅阶顗牡那闆r，即正包中的所有正示例都沒(méi)有被抽中，抽樣后的正包中的示例全部是負(fù)示例，這樣就導(dǎo)致了包的性質(zhì)改變。因此，為了保證正包的性質(zhì)，示例層次重抽樣必須保證抽樣后的正包中至少有一個(gè)正示例。多示例學(xué)習(xí)的特性決定了正包中示例的概念標(biāo)記是模糊的，因此找到每個(gè)正包中的一個(gè)正示例是實(shí)現(xiàn)示例層次上重抽樣的關(guān)鍵。

LI提出的Disambiguation方法［10］可以找到每個(gè)正包中最可能為正的示例t。定義多示例學(xué)習(xí)中的包為Bi，l(Bi)為該包的標(biāo)記(+1為正包，-1表示負(fù)包)，Bi中的第k個(gè)示例為bik，給定一個(gè)有P個(gè)正包和N個(gè)負(fù)包的訓(xùn)練集T，Disambiguation方法中定義示例t為正的概率為:

包中最可能為正的示例是具有最大概率的示例:

θt的候選項(xiàng)集合為N}。P*(t)反映的是示例t區(qū)分訓(xùn)練集中包的能力，P*(t)的值越大，t為正示例的可能性就越大，每個(gè)包中最可能為正的示例就是P*(t)值最大的示例。LI通過(guò)Disambiguation方法找到所有包中最可能為正的示例t，用該示例代表所在的包，再使用傳統(tǒng)的分類方法如支持向量機(jī)分類。筆者借鑒Disambiguation方法識(shí)別每個(gè)正包中最可能為正的示例，通過(guò)在正包示例層次上的重抽樣中保留包中該示例，保持示例層次上重抽樣后的正包性質(zhì)不變，實(shí)現(xiàn)多示例集成學(xué)習(xí)中示例層次上的重抽樣算法。

示例層次重抽樣算法如下:

輸入:有 M 個(gè)包的訓(xùn)練集 T={B1，B2，B3，…，BM}

for i←1到M do

m:包Bi中示例的個(gè)數(shù)

if包Bi的標(biāo)記為正then

else

end if

end for

輸出:抽樣后的訓(xùn)練集 T={B'1，B'2，…B'M}

在示例層次重抽樣算法中，對(duì)于正包，先采用Disambiguation方法找到每個(gè)正包中最可能為正的示例P*(t)，對(duì)正包中的示例實(shí)施重抽樣后，在抽樣得到的新包中加入最可能為正的示例P*(t)，就保證了抽樣后得到的新包中至少有一個(gè)正示例，從而保證了新包的概念標(biāo)記不變。對(duì)于負(fù)包，因?yàn)榘械氖纠龢?biāo)記都為負(fù)，可以直接實(shí)施重抽樣。

在示例層次上實(shí)施重抽樣的算法如上所述。設(shè)正包Bi中有m個(gè)示例，找到包Bi中最可能為正的示例t后，在包中實(shí)施m-1次有放回的抽樣，得到含有m-1個(gè)示例的新包B'i，最后將示例t加入到新包中，這樣抽樣后的新包中至少保存了一個(gè)正示例從而保證了抽樣后包的性質(zhì)不變。

2.2 雙層多示例集成學(xué)習(xí)框架

DMIE學(xué)習(xí)框架由包層次的重抽樣和示例層次的重抽樣組成，雙層多示例集成學(xué)習(xí)框架如下:

輸入包含M 個(gè)包的訓(xùn)練集T={B1，B2，B3，…，BM}

多示例基本分類器L，包層次上的重抽樣次數(shù)I和示例層次上的重抽樣次數(shù)J，未標(biāo)記的包Bx

for i←1到I do

Ti←對(duì)T實(shí)施包層次上的重抽樣for j←1到J do

return標(biāo)記包Bx為yx

第一階段實(shí)施包層次上的重抽樣，即將訓(xùn)練集T中的每個(gè)包作為獨(dú)立的樣本，實(shí)施I次包層次上的重抽樣得到一組Bootstrap集合T1，T2，…，TI，其中Ti擁有與訓(xùn)練集T相同的包的數(shù)目。第二階段實(shí)施示例層次上的重抽樣，即將包中的示例看作獨(dú)立的樣本，對(duì)每個(gè)Ti實(shí)施J次包層次上的重抽樣。在第j(j≤J)次重抽樣中，訓(xùn)練集Ti每個(gè)包中的示例被抽樣并組成新包，所有抽樣后得到的新包組成新的訓(xùn)練集。通過(guò)訓(xùn)練集對(duì)基本分類器訓(xùn)練得到分類器Lji。

DMIE在包層次和示例層次上實(shí)施了兩種重抽樣，每種重抽樣都對(duì)應(yīng)一次集成，因此DMIE包含了兩種層次的集成。首先對(duì)由Ti實(shí)施J次包層次上的重抽樣訓(xùn)練得到的分類器通過(guò)投票整合得到分類器Li，然后再對(duì)分類器Li的學(xué)習(xí)結(jié)果投票整合得到最終的分類器L。

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

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

為了分析DMIE學(xué)習(xí)框架的學(xué)習(xí)性能，筆者用Java和WEKA機(jī)器學(xué)習(xí)軟件實(shí)現(xiàn)了DMIE和TMIE，并將DMIE與傳統(tǒng)的多示例集成學(xué)習(xí)方法TMIE及單個(gè)多示例學(xué)習(xí)方法(single multiple instance learning，SMI)進(jìn)行了比較。實(shí)驗(yàn)選取WEKA機(jī)器學(xué)習(xí)軟件中的CKNN(citation-k nearest neighbors)、MIOptimalBall、MINND(multiple instance n nearest distance distribution)、MIDD(multiple instance diversity density)和MISVM(multiple instance support vector machine)5種方法作為SMI、TMIE和DMIE方法的基本分類器，對(duì)多示例學(xué)習(xí)中的 5 個(gè)典型數(shù)據(jù)集 musk1，musk2，tiger，fox和elephant采用了十折交叉驗(yàn)證。實(shí)驗(yàn)中基本分類器的參數(shù)均使用WEKA機(jī)器學(xué)習(xí)軟件中的默認(rèn)參數(shù)，包層次重抽樣和示例層次重抽樣的次數(shù)均設(shè)置為10。3種方法分類準(zhǔn)確率的比較結(jié)果如表1所示，其中準(zhǔn)確率最高的結(jié)果用黑體表示。

表1 不同方法的分類精度比較

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

對(duì)SMI、TMIE和DMIE的實(shí)驗(yàn)結(jié)果進(jìn)行Win/lose/tie分析，分析結(jié)果如表2所示。

表2 Win/lose/tie分析結(jié)果

通過(guò)3種方法在5個(gè)數(shù)據(jù)集上分類準(zhǔn)確率的比較分析，發(fā)現(xiàn)與SMI和TMIE相比，DMIE具有更高的學(xué)習(xí)精度，能有效地提高多示例分類學(xué)習(xí)的精度。如SMI在數(shù)據(jù)集elephant上的學(xué)習(xí)精度為69%，DMIE則在SMI的基礎(chǔ)上將學(xué)習(xí)精度提高了10%左右。甚至對(duì)一些穩(wěn)定的分類器，如SVM和CKNN，DMIE也能較好地提高分類學(xué)習(xí)的精度。這可能是因?yàn)樵诙嗍纠龑W(xué)習(xí)中包的標(biāo)記限制了該類分類器的穩(wěn)定性，使該類穩(wěn)定的分類方法變得相對(duì)不穩(wěn)定。

4 結(jié)論

筆者提出了一種能有效提高分類精度的雙層多示例集成學(xué)習(xí)方法。識(shí)別包中最可能為正的示例保留該示例實(shí)現(xiàn)包中示例層次上的重抽樣。通過(guò)包層次和示例層次的雙層重抽樣充分?jǐn)噭?dòng)訓(xùn)練集，增強(qiáng)了集成個(gè)體的差異性。實(shí)驗(yàn)結(jié)果證明，該方法與單個(gè)的多示例學(xué)習(xí)方法和傳統(tǒng)的多示例集成方法相比，能更有效地提高多示例學(xué)習(xí)分類器的學(xué)習(xí)精度。

［1］DIETTERICH T G，LATHROP R H，LOZANO-PéREZ T.Solving the multiple-instance problem with axis parallel rectangles［J］.Artificial Intelligence，1997，89(1-2):31-71.

［2］ANDREWS S，HOFMANN T，TSOCHANTARIDIS I.Multiple instance learning with generalized support vector machines［C］//IEEE National Conference on Artificial Intelligence.Edmonton:［s.n.］，2002:943-944.

［3］WANG J，ZUCKER J D.Solving the multiple instance problem:a lazy learning approach［C］//IEEE the 17th International Conference on Machine Learning.San Francisco:［s.n.］，2000:1119-1125.

［4］ZHOU Z H，SUN Y Y，LI Y F.Multi-instance learning by treating instances as non-I.I.D.samples［C］//IEEE Proceedings of the 26th International Conference on Machine Learning.Canada:［s.n.］，2009:1249-1256.

［5］RAHMANI R，GOLDMAN S A.Missl:multiple instance semi-supervised learning［C］//IEEE the 23rd International Conference on Machine Learning.Pittsburgh:［s.n.］，2006:705-712.

［6］ZHOU Z H，XU J M.On the relation between multiinstance learning and semi-supervised learning［C］//IEEE the 24th International Conference on Machine Learning.Corvalis:［s.n.］，2007:1167-1174.

［7］ZHOU Z H.Multi-instance learning from supervised view［J］.Journal of Computer Science and Technology，2006，21(5):800-809.

［8］ZHOU Z H，YU Y.Ensembling local learners through multimodal perturbation［J］.IEEE Transactions on Systems，2005，35(4):725-735.

［9］ZHOU Z H，ZHANG M L.Ensembles of multi-instance learners［C］//The 14th European Conference on Machine Learning.Croatia:［s.n.］.2003:492-502.

［10］LI W J.MILD:Multiple instance learning via disambiguation［J］.IEEE Transactions on Knowledge and Data Engineering，2010，22(1):76-89.