多示例學習下的深度森林架構

任 婕 侯博建 姜 遠

(計算機軟件新技術國家重點實驗室(南京大學) 南京 210023) (軟件新技術與產業化協同創新中心(南京大學) 南京 210023)

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

而近年來，深度神經網絡也在各個領域都取得了很好的效果[6-8].其中MI-Net with DS和MI-Net with RC[9]是深度神經網絡在多示例學習領域的成功應用，它使用了深度學習的技巧：深度監督和剩余連接，在圖像領域的數據上取得了優異的成績.然而在非圖像任務上的性能并不像在圖像任務上那么優秀.與大部分的深度神經網絡模型一樣，它也需要人工針對不同的數據集進行結構調整和參數選擇.

最近幾年，深度森林[10]進入了人們的視野.這是一種基于非可微模塊構建的深度模型，具有比深度神經網絡少得多的超參數，同時其模型復雜性可以通過數據相關的方式自動確定.實驗表明，其性能對于超參數設置非常穩健，因此在大多數情況下，即使面對來自不同領域的不同數據，也可以通過使用相同的默認設置獲得出色的性能.此外由于決策樹的特性，深度森林在非圖像的領域上也有著不錯的效果.

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

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

1 背景知識

本節主要介紹多示例學習問題的定義, 并回顧一個經典的基于包級別的多示例決策樹算法ID3-MI[11].

多示例學習(MIL)問題最初在藥物活性預測中提出.現在多示例學習已經被廣泛應用于許多領域，并成為機器學習中的一個重要問題.在大量的多媒體數據中都包含著多示例(multiple instance, MI)結構，例如文本數據中的文章可以被分為多個段落，圖像數據可以被劃分成多個局部區域，基因表達數據包含著多個基因.多示例學習能夠有效地處理這些多示例(MI)數據.

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

ID3-MI算法就是一種包級多實例學習的算法，它遵循的是一種常見的分而治之的決策樹方式.眾所周知，決策樹算法有著2個重要組成部分：1) 如何選擇分割樹節點的屬性;2) 如何使用樹進行預測.因此ID3-MI算法使用與標準決策樹相同的方法來進行預測，也就是使用未知標簽的包所落入的葉子節點的標簽來確定該包的標簽.顯然ID3-MI算法的關鍵是如何定義一種衡量標準用來選擇決策樹的劃分點.

對于傳統的熵(entropy)，不妨假設數據集D包含p個正例和n個負例，那么依據類別得到的D的熵可以寫作:

(1)

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

(2)

此時的信息增益可以寫作:

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

(3)

Infomulti(D)=

(4)

Infomulti(D,V)=

(5)

使用相同思路可以得到多示例學習下的信息增益：

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

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

(6)

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

② 將節點node置為葉子節點;

③ return;

④ end if

thresholdthen

node.depth+1);

node.depth+1);

2 多示例深度森林

多示例深度森林同時具有多示例森林和深度森林的優勢.但是簡單地將兩者結合起來并不可行，我們需要更有效的結合方式.

2.1 多示例森林

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

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

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

2.2 多示例深度森林

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

在深度森林中，如果將示例提供給級聯結構的某一層，則這一層中所有的森林都會預測出一個類別分布的估計值，并將這個分布估計值轉化為類別向量，如圖1所示.之后我們將類別向量與原始特征向量拼接起來，作為輸入傳遞給下一層.但在MIDF中，得到該層中的每個森林所給出的包級預測后，我們不能簡單地將長度為2的類別向量與大小為ni×d的原始特征矩陣直接拼接起來，因為他們在維度上并不相同.

Fig. 2 The illustration of the cascade structure of multiple instance deep forest圖2 多示例深度森林級聯示意圖

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

3 實驗測試

在本節中，我們分別在多個多示例學習基準數據集上進行實驗，包括分子活動、圖像識別以及文本分類數據集.并在這些數據集上對比多示例深度森林算法(MIDF)、Wang等人提出的多示例神經網絡算法(MI-Net with DS和MI-Net with RC)以及MILES,miGraph, ID3-MI,MIRF等多示例學習算法的效果.

3.1 任務及其數據集

我們分別在3類任務上進行實驗：

1) 藥物激活預測.Musk數據集是1997年由Dietterich等人發布的關于預測分子是否具有麝香味的數據集.由于每個分子都可以被描述為它能夠折疊成的不同形狀(構象異構體)，我們將每個分子對應為一個包，而包中的每一個示例則對應該分子的不同構象.其中，不同構象負責分子的不同性質，也就是它的氣味.在實驗里，如果至少包含一種能夠讓分子產生麝香味的構象，我們就將這個分子(包)標為正類，如果沒有任何一種構象具有這種性質，我們就把這個分子標為負類.

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

3) 文本分類.我們從一個名為20 Newsgroups的語料庫中生成了20個文本分類數據集，對于20個新聞類別中的每一個都生成了50個正包和50個負包.其中每個正包都包含了從目標類別中隨機抽取的3%的示例，并從其他類別中隨機均勻采樣剩余示例，每個負包則只包含從其他類別中均勻采樣的示例，并不包含本類別的數據.在所生成的包中的每個示例均擁有80維的特征.

3.2 實驗設計

我們設計實驗用來驗證本文的多示例深度森林算法能夠與深度神經網絡以及其他算法在多個數據集上效果相當，并且在某些數據集上會取得更好的效果，同時我們的算法還能夠更加容易地進行超參數的調整.在實驗中，對于所有的數據集，我們都使用相同的級聯結構(參數)：每一層由2個包級多示例極跟隨機樹(BLRT)和2個包級多示例隨機森林(MIRF)構成，其中每個森林均包含50棵樹.

對于深度神經網絡，我們使用Wang等人在2018年提出的MI-Net with DS和MI-Net with RC算法，這些算法都需要設定不同的學習率、權重衰減和動量值來獲得在不同數據集上的高性能.因此，我們進行實驗時在驗證集上驗證不同參數的效果，選擇最佳的參數，并在訓練集上重新訓練得到最終的預測結果.

對于其余的多示例算法我們也使用了和MI-Net with DS和MI-Net with RC一樣的方法來確定它們在不同數據集上的最優參數，并使用該參數得到最終的預測結果.

3.3 實驗結果

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

表1給出了在藥物激活預測以及自動圖像標注任務上的實驗結果，表2給出了在文本分類任務上的實驗結果，其中用黑體加粗來標注得到的最好結果.

Table 1 Detailed Characteristics of Datasets表1 數據集的具體信息

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

表2 藥物和圖片標注數據集上不同算法的平均預測準確率

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 文本分類數據集上不同算法的平均預測準確率

Note: The best results are in bold.

MIDF在這些數據集上均展現了較好的效果，尤其是在處理文本分類任務時，我們在20個數據集中的12個數據集上取得了最優效果，并在其他8個數據集上同最優結果相當.同時在圖像數據上我們同示例級的神經網絡算法效果也相差不大.此外盡管其他算法在某些數據集上也展現了不錯的效果，但他們往往需要針對不同數據集使用不同的超參數，這類超參數的選擇十分困難且耗時.而我們的算法只需要使用相同的超參就可以得到很好的結果.

4 結束語

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