幾種多示例學習算法研究分析

楊雪潔　趙凱

摘要：多示例學習與傳統機器學習有很大不同，多示例學習中一個樣本包中有多個示例，樣本包有類別，而示例沒有類別標記，屬于一對多的學習框架。本文介紹了多示例學習提出背景及基本特點，從包層次和示例層次兩方面分析比較了幾種具有代表性的多示例學習算法，最后展望了多示例學習算法的進一步研究方向。

關鍵詞：多示例學習 機器學習 BP算法 KNN算法

中圖分類號：TP391.41 文獻標識碼：A 文章編號：1007-9416（2016）08-0151-01

1 引言

T.G.Dietterich等人在研究藥物活性預測時提出了多示例學習的概念[1]。該問題是通過機器學習方法對樣本分子（已標記適合制藥及不適合制藥）進行學習，從而盡可能正確預測某些新分子是否適合制藥。研究人員因技術原因只知道哪些分子適合制藥，而對于該分子中哪一種具體形狀適合制藥并不清楚，因為一個藥物分子可能有多種可能的形狀（同分異構體），要有一個形狀起作用，則這個分子就適于制藥，若該分子所有示例都不適合制藥，該分子才不適合制藥，該問題提出了樣本和示例一對多的學習框架，在該框架中若按監督學習直接以分子為對象進行學習，將所有適合制藥的分子作為正例學習，會出現由于正例中噪聲太高而難以學習，因為正例中也會有大量不適合制藥的形狀，所以該問題提出了一種新的學習方式—多示例學習。

2 多示例學習

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

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

3 示例層次算法

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

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

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

4 包層次算法

上述方法都是基于包中的每一個示例學習的，為更好的將傳統機器學習方法修正后處理多示例學習任務，研究人員開始從包層次來設計算法，例如基于KNN、基于BP、基于SVM的多示例學習算法。

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

基于BP的多示例學習算法[10]是對神經網絡中BP算法進行改造，通過改造傳統BP誤差函數，得到多示例下的學習算法，該誤差函數是在包層次上定義，包的實值輸出是由包中示例的最大實值輸出所決定。

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

5 結語

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

參考文獻

[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]周志華.多示例學習[J].知識科學中的基本問題研究.北京：清華大學出版社，2006：322-336.

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