幾種多示例學(xué)習(xí)算法研究分析

楊雪潔　趙凱

摘要：多示例學(xué)習(xí)與傳統(tǒng)機(jī)器學(xué)習(xí)有很大不同，多示例學(xué)習(xí)中一個(gè)樣本包中有多個(gè)示例，樣本包有類別，而示例沒有類別標(biāo)記，屬于一對多的學(xué)習(xí)框架。本文介紹了多示例學(xué)習(xí)提出背景及基本特點(diǎn)，從包層次和示例層次兩方面分析比較了幾種具有代表性的多示例學(xué)習(xí)算法，最后展望了多示例學(xué)習(xí)算法的進(jìn)一步研究方向。

關(guān)鍵詞：多示例學(xué)習(xí) 機(jī)器學(xué)習(xí) BP算法 KNN算法

中圖分類號：TP391.41 文獻(xiàn)標(biāo)識碼：A 文章編號：1007-9416（2016）08-0151-01

1 引言

T.G.Dietterich等人在研究藥物活性預(yù)測時(shí)提出了多示例學(xué)習(xí)的概念[1]。該問題是通過機(jī)器學(xué)習(xí)方法對樣本分子（已標(biāo)記適合制藥及不適合制藥）進(jìn)行學(xué)習(xí)，從而盡可能正確預(yù)測某些新分子是否適合制藥。研究人員因技術(shù)原因只知道哪些分子適合制藥，而對于該分子中哪一種具體形狀適合制藥并不清楚，因?yàn)橐粋€(gè)藥物分子可能有多種可能的形狀（同分異構(gòu)體），要有一個(gè)形狀起作用，則這個(gè)分子就適于制藥，若該分子所有示例都不適合制藥，該分子才不適合制藥，該問題提出了樣本和示例一對多的學(xué)習(xí)框架，在該框架中若按監(jiān)督學(xué)習(xí)直接以分子為對象進(jìn)行學(xué)習(xí)，將所有適合制藥的分子作為正例學(xué)習(xí)，會(huì)出現(xiàn)由于正例中噪聲太高而難以學(xué)習(xí)，因?yàn)檎幸矔?huì)有大量不適合制藥的形狀，所以該問題提出了一種新的學(xué)習(xí)方式—多示例學(xué)習(xí)。

2 多示例學(xué)習(xí)

多示例學(xué)習(xí)中的訓(xùn)練示例沒有被標(biāo)記類別，監(jiān)督學(xué)習(xí)中所有訓(xùn)練樣本都有具體類別；多示例學(xué)習(xí)中訓(xùn)練分子（包）是有具體類別，非監(jiān)督學(xué)習(xí)的訓(xùn)練樣本都沒有類別標(biāo)記。在監(jiān)督、非監(jiān)督學(xué)習(xí)中，一個(gè)樣本就是一個(gè)示例，不可以再次分割，一個(gè)樣本只能屬于一個(gè)具體的類別，即樣本和示例是一一對應(yīng)關(guān)系，而多示例學(xué)習(xí)，一個(gè)樣本（即包）中有多個(gè)示例，訓(xùn)練集由若干個(gè)有類別的包組成，其中每個(gè)包包含一些沒有類別的示例。若一個(gè)包中至少存在一個(gè)正示例，則該包被標(biāo)記為正包；一個(gè)包中不含有任何正例，則該包為反包。學(xué)習(xí)系統(tǒng)通過對已經(jīng)標(biāo)定類別的包進(jìn)行學(xué)習(xí)來建立模型，希望盡可能正確地預(yù)測訓(xùn)練集以外的包的類別標(biāo)記[2]。機(jī)器學(xué)習(xí)算法目標(biāo)是要找出unkown process 的最佳逼近方法，傳統(tǒng)監(jiān)督、非監(jiān)督學(xué)習(xí)描述見圖1，多示例學(xué)習(xí)問題描述見圖2。

多示例學(xué)習(xí)的提出拓寬了機(jī)器學(xué)習(xí)解決問題的領(lǐng)域，該問題在現(xiàn)實(shí)生活中可以找到很多原型，例如基于內(nèi)容的圖像檢索、文本分類、視頻內(nèi)容檢測、計(jì)算機(jī)安全預(yù)測等。國內(nèi)外研究人員提出了多種多示例學(xué)習(xí)算法，大致可以分為兩類，從具體示例角度的示例層次算法和從包層次分析的包層次算法。

3 示例層次算法

示例層次算法早期具有代表性的是T.G.Dietterich等人提出的三個(gè)軸-平行矩形（APR）算法。他們將一個(gè)分子看成一個(gè)包，該分子的不同形狀作為包中的不同示例，為表示這些示例，將該分子固定在坐標(biāo)原點(diǎn)，從原點(diǎn)放射出多條射線，射線與分子的交點(diǎn)到坐標(biāo)原點(diǎn)的距離作為一個(gè)屬性，再加上分子中氧原子位置屬性，包中的每個(gè)示例可以用上述屬性值來描述。APR算法基本思想是找出覆蓋所有正包示例的軸平行矩形，再通過貪心算法逐步排除反包中的反示例以縮小矩形，最終找到一個(gè)最小矩形確定多示例數(shù)據(jù)集中上限和下限，從而將所有不在矩形內(nèi)的樣本排除，最終落在矩形中的樣本即為正例。三種APR算法中預(yù)測效果較好的是Iterated-discrim APR算法，由于APR算法都是基于矩形的，對于解決麝香分子問題效果較好，難以直接用于解決實(shí)際的多示例學(xué)習(xí)問題，不具有較好的通用性。

另一種有代表性的方法是基于概率的多樣性密度（簡稱DD）算法。DD算法中每個(gè)包的示例是一個(gè)n維空間的向量，對應(yīng)空間中的一個(gè)點(diǎn)，空間中存在某個(gè)區(qū)域，滿足每個(gè)正包中至少有一個(gè)示例在該區(qū)域內(nèi)或者距離足夠近，所有來自反包的示例到該區(qū)域的距離足夠遠(yuǎn)。為找到該區(qū)域， Maron用多樣性密度來衡量空間中的每個(gè)點(diǎn)。一個(gè)點(diǎn)周圍的正包數(shù)越多，反包示例越遠(yuǎn)，則該點(diǎn)多樣性密度越大，空間中多樣性密度最大的點(diǎn)被認(rèn)為是目標(biāo)區(qū)域。算法采用noisy-or模型和梯度下降法來尋找多樣性密度最大的點(diǎn)，將全部正包中的示例都作為候選的目標(biāo)，進(jìn)行一次全局搜索以避免局部最優(yōu)解。該算法在麝香分子上測試效果雖然不如Iterated-discrim APR算法，但可以應(yīng)用于其他方面，如股票選擇、基于內(nèi)容的圖像檢索等。

由于需要多次使用梯度下降搜索目標(biāo)示例，DD算法訓(xùn)練時(shí)間花費(fèi)較大，研究人員又提出了EM-DD算法，該算法在EM算法的E步從訓(xùn)練集的每個(gè)示例包中選出決定各包類別的訓(xùn)練示例，再在M步選出的示例中使用多樣性密度算法以最大化多樣性密度，反復(fù)進(jìn)行E步和M步直至算法收斂，該算法在麝香分子數(shù)據(jù)集預(yù)測精度一度是最高的，與DD算法相比縮短了不少時(shí)間，但由于該方法是不斷迭代的過程，比較容易陷入局部最優(yōu)。

4 包層次算法

上述方法都是基于包中的每一個(gè)示例學(xué)習(xí)的，為更好的將傳統(tǒng)機(jī)器學(xué)習(xí)方法修正后處理多示例學(xué)習(xí)任務(wù)，研究人員開始從包層次來設(shè)計(jì)算法，例如基于KNN、基于BP、基于SVM的多示例學(xué)習(xí)算法。

KNN算法用樣本間的距離來度量樣本間的相似度，基于K-NN的多示例學(xué)習(xí)算法使用修改的Hausdorff 距離，這樣就可以有效地計(jì)算不同的包之間的距離。在此基礎(chǔ)上，他們提出了兩種算法，即Bayesian-kNN 和Citation-kNN。前者使用Bayes 理論來分析鄰包，從而獲得新包的標(biāo)記。后者不僅考慮其鄰包，還考慮將該新包作為鄰包的包。這兩種算法在麝香分子測試時(shí)，Citation-kNN效果與Iterated-discrim APR算法接近，略優(yōu)于Bayesian-kNN，K-NN多示例學(xué)習(xí)算法未針對麝香分子進(jìn)行優(yōu)化，因而有更廣泛的應(yīng)用場合，但這兩種算法只能預(yù)測包的類別，無法預(yù)測包中示例的類別，這點(diǎn)上無法與DD算法相比。同時(shí)兩種算法需要將訓(xùn)練樣本全部保存，存儲空間較大，預(yù)測分類時(shí)需遍歷所有樣本空間，時(shí)間花費(fèi)較大。

基于BP的多示例學(xué)習(xí)算法[10]是對神經(jīng)網(wǎng)絡(luò)中BP算法進(jìn)行改造，通過改造傳統(tǒng)BP誤差函數(shù)，得到多示例下的學(xué)習(xí)算法，該誤差函數(shù)是在包層次上定義，包的實(shí)值輸出是由包中示例的最大實(shí)值輸出所決定。

基于SVM的多示例算法將在輸入數(shù)據(jù)的特征空間找到一個(gè)超平面，此超平面使訓(xùn)練數(shù)據(jù)之間的不同類樣本的間距最大，在包層次中將最大分類間隔為包間隔，對于反包，由于反包中所有示例都是反示例，因此包之間的間隔與監(jiān)督學(xué)習(xí)方式一致，對于正包，將包之間的最大間隔定義為分類超平面和正包中所有示例間距離的最大值。該方法試圖尋找每個(gè)正包的正示例，適合處理小樣本數(shù)據(jù)集，但該方法忽略了正包中的反示例。

5 結(jié)語

隨著多示例學(xué)習(xí)算法的不斷優(yōu)化，可以考慮將專門的多示例算法和已擴(kuò)展為多示例學(xué)習(xí)的原監(jiān)督學(xué)習(xí)算法結(jié)合使用解決問題，如利用集成學(xué)習(xí)方法，先通過已有機(jī)器學(xué)習(xí)算法重新組織數(shù)據(jù)集，將包抽象為空間的點(diǎn)，找到正包中正示例（或者排除正包中大量的反例），然后利用選出的示例將多示例學(xué)習(xí)轉(zhuǎn)為監(jiān)督學(xué)習(xí)，這也是下一步努力的方向。

參考文獻(xiàn)

[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）：31-71.

[2]周志華.多示例學(xué)習(xí)[J].知識科學(xué)中的基本問題研究.北京：清華大學(xué)出版社，2006：322-336.

[3]蔡自興，李枚毅.多示例學(xué)習(xí)及其研究現(xiàn)狀[J].控制與決策，2004，19（6）：607-611.