任 婕 侯博建 姜 遠(yuǎn)

(計(jì)算機(jī)軟件新技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室(南京大學(xué)) 南京 210023) (軟件新技術(shù)與產(chǎn)業(yè)化協(xié)同創(chuàng)新中心(南京大學(xué)) 南京 210023)

多示例學(xué)習(xí)(multiple instance learning, MIL)在藥物活性預(yù)測(cè)調(diào)查期間被首次提出[1].與傳統(tǒng)的單示例學(xué)習(xí)不同，多示例學(xué)習(xí)的輸入是一組標(biāo)簽為正或負(fù)的包，而不是一組標(biāo)簽為正或負(fù)的示例.在多示例學(xué)習(xí)中我們不會(huì)得到任何示例的標(biāo)簽信息.如今，多示例學(xué)習(xí)已經(jīng)廣泛地應(yīng)用于各種領(lǐng)域，如圖像分類檢索、人臉識(shí)別、文本分類、計(jì)算機(jī)輔助醫(yī)療診斷等[2].在過去的時(shí)間里，已經(jīng)提出了很多有效的MIL算法[3-5].

而近年來，深度神經(jīng)網(wǎng)絡(luò)也在各個(gè)領(lǐng)域都取得了很好的效果[6-8].其中MI-Net with DS和MI-Net with RC[9]是深度神經(jīng)網(wǎng)絡(luò)在多示例學(xué)習(xí)領(lǐng)域的成功應(yīng)用，它使用了深度學(xué)習(xí)的技巧：深度監(jiān)督和剩余連接，在圖像領(lǐng)域的數(shù)據(jù)上取得了優(yōu)異的成績(jī).然而在非圖像任務(wù)上的性能并不像在圖像任務(wù)上那么優(yōu)秀.與大部分的深度神經(jīng)網(wǎng)絡(luò)模型一樣，它也需要人工針對(duì)不同的數(shù)據(jù)集進(jìn)行結(jié)構(gòu)調(diào)整和參數(shù)選擇.

最近幾年，深度森林[10]進(jìn)入了人們的視野.這是一種基于非可微模塊構(gòu)建的深度模型，具有比深度神經(jīng)網(wǎng)絡(luò)少得多的超參數(shù)，同時(shí)其模型復(fù)雜性可以通過數(shù)據(jù)相關(guān)的方式自動(dòng)確定.實(shí)驗(yàn)表明，其性能對(duì)于超參數(shù)設(shè)置非常穩(wěn)健，因此在大多數(shù)情況下，即使面對(duì)來自不同領(lǐng)域的不同數(shù)據(jù)，也可以通過使用相同的默認(rèn)設(shè)置獲得出色的性能.此外由于決策樹的特性，深度森林在非圖像的領(lǐng)域上也有著不錯(cuò)的效果.

因此在非圖像任務(wù)上利用深度森林架構(gòu)來解決多示例學(xué)習(xí)問題或許是一種更好的選擇.Amores[2]指出包級(jí)別的算法通常比示例級(jí)的算法效果要好.但由于深度森林結(jié)構(gòu)的限制，組成深度森林的每一個(gè)森林并不能直接被替換成包級(jí)別的森林，所以并不能把包級(jí)別的思想直接套用到深度森林框架上.這就使得我們需要提出一種新的深度森林結(jié)構(gòu)來解決多示例學(xué)習(xí)問題.

本文提出了一種新的深度森林架構(gòu)(multiple instance deep forest, MIDF)，使用了包級(jí)的算法思想.在拼接時(shí)我們把包里的每個(gè)示例都看做是一個(gè)包，從而使得中間層的輸出分布可以和包中的示例拼接成功，讓級(jí)聯(lián)結(jié)構(gòu)依然有效.此外我們的架構(gòu)由2個(gè)級(jí)聯(lián)結(jié)構(gòu)組成，一個(gè)使用k折交叉驗(yàn)證來幫助自動(dòng)確定深度森林的層數(shù)，另一個(gè)根據(jù)所求的層數(shù)來計(jì)算最終的結(jié)果.實(shí)驗(yàn)結(jié)果表明：我們的方法在圖像任務(wù)上的性能與擅長(zhǎng)處理圖像任務(wù)的MI-Net with DS和MI-Net with RC相當(dāng)；而在文本數(shù)據(jù)上，我們的算法取得了比它們和其他基線算法更好的效果.

1 背景知識(shí)

本節(jié)主要介紹多示例學(xué)習(xí)問題的定義, 并回顧一個(gè)經(jīng)典的基于包級(jí)別的多示例決策樹算法ID3-MI[11].

多示例學(xué)習(xí)(MIL)問題最初在藥物活性預(yù)測(cè)中提出.現(xiàn)在多示例學(xué)習(xí)已經(jīng)被廣泛應(yīng)用于許多領(lǐng)域，并成為機(jī)器學(xué)習(xí)中的一個(gè)重要問題.在大量的多媒體數(shù)據(jù)中都包含著多示例(multiple instance, MI)結(jié)構(gòu)，例如文本數(shù)據(jù)中的文章可以被分為多個(gè)段落，圖像數(shù)據(jù)可以被劃分成多個(gè)局部區(qū)域，基因表達(dá)數(shù)據(jù)包含著多個(gè)基因.多示例學(xué)習(xí)能夠有效地處理這些多示例(MI)數(shù)據(jù).

目前已經(jīng)有許多算法被用來解決MIL問題.根據(jù)Amores的調(diào)查，MIL算法可以分為3個(gè)種類：示例空間(instance space, IS)范式、包空間(bag space, BS)范式和嵌入空間(embedded space, ES)范式.簡(jiǎn)而言之，對(duì)于IS范式，判別信息被認(rèn)為是在示例級(jí)別上的，而在BS范式中，判別信息是在包級(jí)別上的.ES范式中的多示例學(xué)習(xí)算法明確或隱含地將每個(gè)包映射到單個(gè)特征向量上，該特征向量總結(jié)了關(guān)于整個(gè)包的相關(guān)信息.

ID3-MI算法就是一種包級(jí)多實(shí)例學(xué)習(xí)的算法，它遵循的是一種常見的分而治之的決策樹方式.眾所周知，決策樹算法有著2個(gè)重要組成部分：1) 如何選擇分割樹節(jié)點(diǎn)的屬性;2) 如何使用樹進(jìn)行預(yù)測(cè).因此ID3-MI算法使用與標(biāo)準(zhǔn)決策樹相同的方法來進(jìn)行預(yù)測(cè)，也就是使用未知標(biāo)簽的包所落入的葉子節(jié)點(diǎn)的標(biāo)簽來確定該包的標(biāo)簽.顯然ID3-MI算法的關(guān)鍵是如何定義一種衡量標(biāo)準(zhǔn)用來選擇決策樹的劃分點(diǎn).

對(duì)于傳統(tǒng)的熵(entropy)，不妨假設(shè)數(shù)據(jù)集D包含p個(gè)正例和n個(gè)負(fù)例，那么依據(jù)類別得到的D的熵可以寫作:

(1)

如果選擇在屬性V上劃分，并將D劃分為{D1,D2,…,Dl}，那么此時(shí)的熵可以寫作:

(2)

此時(shí)的信息增益可以寫作:

Gain(D,V)=Info(D)-Info(D,V)=

(3)

Infomulti(D)=

(4)

Infomulti(D,V)=

(5)

使用相同思路可以得到多示例學(xué)習(xí)下的信息增益：

Gainmulti(D,V)=Infomulti(D)-

Infomulti(D,V)=Infomulti(D)-

(6)

算法1通過偽代碼的形式給出了包級(jí)多實(shí)例決策樹ID3-MI生成決策樹過程的詳細(xì)描述：

② 將節(jié)點(diǎn)node置為葉子節(jié)點(diǎn);

③ return;

④ end if

thresholdthen

node.depth+1);

node.depth+1);

2 多示例深度森林

多示例深度森林同時(shí)具有多示例森林和深度森林的優(yōu)勢(shì).但是簡(jiǎn)單地將兩者結(jié)合起來并不可行，我們需要更有效的結(jié)合方式.

2.1 多示例森林

Fig. 1 The illustration of class vector generation圖1 類向量生成示意圖

本節(jié)介紹2種多示例森林算法MIRF和BLRT[12]，它們分別受到隨機(jī)森林算法和極根隨機(jī)樹算法的啟發(fā).

在極根隨機(jī)樹算法(ExtraTrees)[15]中，使用了更進(jìn)一步的隨機(jī)化步驟.與隨機(jī)森林一樣，極根隨機(jī)樹也是在候選特征的隨機(jī)子集上來尋找劃分，但不同的是極根隨機(jī)樹并非在每個(gè)屬性上計(jì)算最優(yōu)劃分點(diǎn)，而是在這些屬性上隨機(jī)選擇劃分點(diǎn).換言之這個(gè)值是在屬性的經(jīng)驗(yàn)范圍內(nèi)均勻隨機(jī)選取的.在所有的隨機(jī)劃分點(diǎn)中，極根隨機(jī)樹會(huì)選擇其中最優(yōu)的作為該節(jié)點(diǎn)的劃分點(diǎn).BLRT受到了極根隨機(jī)樹的影響，并將傳統(tǒng)的ExtraTree像ID3-MI那樣推廣成了包級(jí)多示例ExtraTree.

2.2 多示例深度森林

多示例深森林(MIDF)受到了深度森林的啟發(fā)，它也具有級(jí)聯(lián)結(jié)構(gòu)，級(jí)聯(lián)的每一層都是從其前一層接收特征，并將結(jié)果發(fā)送給下一層作為輸入.MIDF的每一層都是MIRF和BLRT這2種不同多示例森林的集成，使用不同種類的森林集成可以增加MIDF算法的多樣性.

在深度森林中，如果將示例提供給級(jí)聯(lián)結(jié)構(gòu)的某一層，則這一層中所有的森林都會(huì)預(yù)測(cè)出一個(gè)類別分布的估計(jì)值，并將這個(gè)分布估計(jì)值轉(zhuǎn)化為類別向量，如圖1所示.之后我們將類別向量與原始特征向量拼接起來，作為輸入傳遞給下一層.但在MIDF中，得到該層中的每個(gè)森林所給出的包級(jí)預(yù)測(cè)后，我們不能簡(jiǎn)單地將長(zhǎng)度為2的類別向量與大小為ni×d的原始特征矩陣直接拼接起來，因?yàn)樗麄冊(cè)诰S度上并不相同.

Fig. 2 The illustration of the cascade structure of multiple instance deep forest圖2 多示例深度森林級(jí)聯(lián)示意圖

本文算法由2個(gè)級(jí)聯(lián)結(jié)構(gòu)組成：1)用于確定MIDF的層數(shù);2)用于計(jì)算最終預(yù)測(cè)結(jié)果.第1個(gè)級(jí)聯(lián)中的每個(gè)森林所預(yù)測(cè)出的類別向量都是通過k折交叉驗(yàn)證得到的，這里我們通常取k=3.詳細(xì)地,每個(gè)示例都會(huì)被用作訓(xùn)練數(shù)據(jù)k-1次，產(chǎn)生k-1個(gè)類別向量，然后對(duì)其取平均值以產(chǎn)生用于傳遞給下一層的增強(qiáng)特征.此外，在擴(kuò)展一個(gè)新層之后，整個(gè)級(jí)聯(lián)的性能將在驗(yàn)證集上進(jìn)行評(píng)估，如果沒有顯著的性能增益，那么訓(xùn)練過程將會(huì)終止.因此，我們可以通過第1個(gè)級(jí)聯(lián)結(jié)構(gòu)來自動(dòng)地確定級(jí)聯(lián)的層數(shù).第2個(gè)級(jí)聯(lián)的每一層則使用了完整的訓(xùn)練數(shù)據(jù)，其訓(xùn)練的層數(shù)由第1個(gè)級(jí)聯(lián)結(jié)構(gòu)計(jì)算給出，并得到最終的預(yù)測(cè)結(jié)果.

3 實(shí)驗(yàn)測(cè)試

在本節(jié)中，我們分別在多個(gè)多示例學(xué)習(xí)基準(zhǔn)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，包括分子活動(dòng)、圖像識(shí)別以及文本分類數(shù)據(jù)集.并在這些數(shù)據(jù)集上對(duì)比多示例深度森林算法(MIDF)、Wang等人提出的多示例神經(jīng)網(wǎng)絡(luò)算法(MI-Net with DS和MI-Net with RC)以及MILES,miGraph, ID3-MI,MIRF等多示例學(xué)習(xí)算法的效果.

3.1 任務(wù)及其數(shù)據(jù)集

我們分別在3類任務(wù)上進(jìn)行實(shí)驗(yàn)：

1) 藥物激活預(yù)測(cè).Musk數(shù)據(jù)集是1997年由Dietterich等人發(fā)布的關(guān)于預(yù)測(cè)分子是否具有麝香味的數(shù)據(jù)集.由于每個(gè)分子都可以被描述為它能夠折疊成的不同形狀(構(gòu)象異構(gòu)體)，我們將每個(gè)分子對(duì)應(yīng)為一個(gè)包，而包中的每一個(gè)示例則對(duì)應(yīng)該分子的不同構(gòu)象.其中，不同構(gòu)象負(fù)責(zé)分子的不同性質(zhì)，也就是它的氣味.在實(shí)驗(yàn)里，如果至少包含一種能夠讓分子產(chǎn)生麝香味的構(gòu)象，我們就將這個(gè)分子(包)標(biāo)為正類，如果沒有任何一種構(gòu)象具有這種性質(zhì)，我們就把這個(gè)分子標(biāo)為負(fù)類.

2) 自動(dòng)圖像標(biāo)注.在這一類任務(wù)中有3個(gè)比較有名的數(shù)據(jù)集，分別是Andrews等人于2002年提出的Fox,Tiger和Elephant數(shù)據(jù)集[3].在這類任務(wù)中，我們把圖像本身作為包，圖像的不同區(qū)域作為包中的示例.對(duì)于每個(gè)類別，如果圖像包含該類動(dòng)物，我們就把這個(gè)圖像看作為正包，如果圖像僅包含其他動(dòng)物(來自其他類別的動(dòng)物，不僅僅是Fox,Tiger和Elephant)，那我們將其看作為負(fù)包.

3) 文本分類.我們從一個(gè)名為20 Newsgroups的語料庫(kù)中生成了20個(gè)文本分類數(shù)據(jù)集，對(duì)于20個(gè)新聞?lì)悇e中的每一個(gè)都生成了50個(gè)正包和50個(gè)負(fù)包.其中每個(gè)正包都包含了從目標(biāo)類別中隨機(jī)抽取的3%的示例，并從其他類別中隨機(jī)均勻采樣剩余示例，每個(gè)負(fù)包則只包含從其他類別中均勻采樣的示例，并不包含本類別的數(shù)據(jù).在所生成的包中的每個(gè)示例均擁有80維的特征.

3.2 實(shí)驗(yàn)設(shè)計(jì)

我們?cè)O(shè)計(jì)實(shí)驗(yàn)用來驗(yàn)證本文的多示例深度森林算法能夠與深度神經(jīng)網(wǎng)絡(luò)以及其他算法在多個(gè)數(shù)據(jù)集上效果相當(dāng)，并且在某些數(shù)據(jù)集上會(huì)取得更好的效果，同時(shí)我們的算法還能夠更加容易地進(jìn)行超參數(shù)的調(diào)整.在實(shí)驗(yàn)中，對(duì)于所有的數(shù)據(jù)集，我們都使用相同的級(jí)聯(lián)結(jié)構(gòu)(參數(shù))：每一層由2個(gè)包級(jí)多示例極跟隨機(jī)樹(BLRT)和2個(gè)包級(jí)多示例隨機(jī)森林(MIRF)構(gòu)成，其中每個(gè)森林均包含50棵樹.

對(duì)于深度神經(jīng)網(wǎng)絡(luò)，我們使用Wang等人在2018年提出的MI-Net with DS和MI-Net with RC算法，這些算法都需要設(shè)定不同的學(xué)習(xí)率、權(quán)重衰減和動(dòng)量值來獲得在不同數(shù)據(jù)集上的高性能.因此，我們進(jìn)行實(shí)驗(yàn)時(shí)在驗(yàn)證集上驗(yàn)證不同參數(shù)的效果，選擇最佳的參數(shù)，并在訓(xùn)練集上重新訓(xùn)練得到最終的預(yù)測(cè)結(jié)果.

對(duì)于其余的多示例算法我們也使用了和MI-Net with DS和MI-Net with RC一樣的方法來確定它們?cè)诓煌瑪?shù)據(jù)集上的最優(yōu)參數(shù)，并使用該參數(shù)得到最終的預(yù)測(cè)結(jié)果.

3.3 實(shí)驗(yàn)結(jié)果

我們通過10次10折交叉驗(yàn)證來比較ID3-MI、MIRF以及MIDF算法的性能(運(yùn)行10次10折交叉驗(yàn)證，每次采取不同的隨機(jī)數(shù)據(jù)劃分).表1和表2展示了測(cè)試準(zhǔn)確率的比較.

表1給出了在藥物激活預(yù)測(cè)以及自動(dòng)圖像標(biāo)注任務(wù)上的實(shí)驗(yàn)結(jié)果，表2給出了在文本分類任務(wù)上的實(shí)驗(yàn)結(jié)果，其中用黑體加粗來標(biāo)注得到的最好結(jié)果.

Table 1 Detailed Characteristics of Datasets表1 數(shù)據(jù)集的具體信息

Table 2Average Prediction Accuracy of DifferentMethods for Drug and Image Datasets

表2 藥物和圖片標(biāo)注數(shù)據(jù)集上不同算法的平均預(yù)測(cè)準(zhǔn)確率

AlgorithmsMusk1MUSK2ElephantFoxTigerMILES0.840.800.820.610.80miGraph0.880.840.800.600.79MI-Net with RC0.880.850.840.600.81MI-Net with DS0.890.840.850.590.81ID3-MI0.770.710.670.560.69MIRF0.870.800.760.540.72MIDF0.890.810.840.580.79

Note: The best results are in bold.

Table 3 Average Prediction Accuracy of Different Methods for Text Categorization Datasets表3 文本分類數(shù)據(jù)集上不同算法的平均預(yù)測(cè)準(zhǔn)確率

Note: The best results are in bold.

MIDF在這些數(shù)據(jù)集上均展現(xiàn)了較好的效果，尤其是在處理文本分類任務(wù)時(shí)，我們?cè)?0個(gè)數(shù)據(jù)集中的12個(gè)數(shù)據(jù)集上取得了最優(yōu)效果，并在其他8個(gè)數(shù)據(jù)集上同最優(yōu)結(jié)果相當(dāng).同時(shí)在圖像數(shù)據(jù)上我們同示例級(jí)的神經(jīng)網(wǎng)絡(luò)算法效果也相差不大.此外盡管其他算法在某些數(shù)據(jù)集上也展現(xiàn)了不錯(cuò)的效果，但他們往往需要針對(duì)不同數(shù)據(jù)集使用不同的超參數(shù)，這類超參數(shù)的選擇十分困難且耗時(shí).而我們的算法只需要使用相同的超參就可以得到很好的結(jié)果.

4 結(jié)束語

本文提出了一個(gè)新的深度森林框架MIDF來解決多示例學(xué)習(xí)問題.在這種新的框架下，拼接時(shí)會(huì)把包中的每個(gè)示例都看做是一個(gè)包，從而使得中間層的輸出分布可以和包中的示例拼接成功，進(jìn)而使得級(jí)聯(lián)結(jié)構(gòu)依然有效.另外，我們的架構(gòu)由2個(gè)級(jí)聯(lián)結(jié)構(gòu)組成，其中一個(gè)使用k折交叉驗(yàn)證來幫助自動(dòng)確定深度森林的層數(shù)，另一個(gè)根據(jù)所求的層數(shù)來計(jì)算最終的結(jié)果.實(shí)驗(yàn)結(jié)果表明：我們的方法在圖像任務(wù)上的性能并不比擅長(zhǎng)處理圖像任務(wù)的MI-Nets差，而在在文本數(shù)據(jù)上，本文方法取得了比MI-Nets更好的效果.