基于Logistic回歸模型和凝聚函數的多示例學習算法

賀 建 軍， 王 欣， 顧 宏， 王 哲 龍

（大連理工大學 控制科學與工程學院，遼寧 大連 116024）

0 引 言

多示例學習（multi－instance learning，MIL）最早是由 Dietterich等[1]在對藥物活性預測（drug activity prediction）問題的研究中提出來的.隨著該領域內研究的不斷深入，多示例學習也被更廣泛地應用到物體檢測[2]、圖像檢索[3]和Web挖掘[4、5]等諸多方面.在多示例學習問題中，樣本——通常被稱為包（bag），由多個特征向量組成，而每個特征向量稱為一個示例；訓練集由具有標簽（label）的包組成，而包中的各個示例并沒有標簽.通常情況下，假設包中每個示例都有一個隱含的標簽，如果一個包中至少有一個正示例，則這個包的標簽即為正，反之，則該包的標簽為負.為方便問題描述，稱上面的假設為標準的多示例學習假設.

APRs算法[1]是最早的多示例學習算法.隨后，Maron等[6]對APRs算法的思想做了進一步的改進提出了多樣性密度（diverse density，DD）算法.然而，由于多樣性密度空間中存在多個局部極小點，將每一個正包示例都作為初始點進行一次搜索，會使該算法的訓練時間開銷相當大.Zhang等[7]將DD算法和EM算法相結合，提出了EM－DD算法.與DD算法相比，EM－DD算法的計算時間花費有所減少.在提出多示例學習的概念時，Dietterich等就指出“當前一個非常值得研究的課題是如何對傳統的機器學習算法進行修改，使它們可以處理多示例學習任務”，該問題對多示例學習的研究起到了推動作用.經過十多年的研究，常用的機器學習算法基本上都有了其多示例學習版本.例如，多示例版本的支持向量機（SVM）算法有Andrews等[8]提出的 MI－SVM和mi－SVM 算法，Chen等[9]提出的 MILES算法及Li等[3]提出的Ins－KI－SVM和Bag－KI－SVM 算法等；多示例版本的神經網絡算法有BP－MIP算法[10]和 RBF－MIP 算 法[11]；多 示 例 版 本 的 核miGraph－Kernel[12]和 Marginalized MI－Kernel[13]等；Cheung等[14]提出了一個多示例版本的正則化框架（regularization framework）；Zhou等[15]則將集成學習（ensemble learning）技術引入到了多示例學習中.

作為一種常用的機器學習技術，Logistic回歸模型也被應用到了多示例學習中.Xu等[16]建立了最早的基于Logistic回歸模型的多示例算法.在該算法中，每一個包的概率被定義為其示例的概率的均值，而這與標準的多示例學習假設“每個包只要至少包含一個正示例則該包就是正包”不相符.之后，Ray等[17]提出用softmax函數來處理包的概率和其示例的概率之間的關系；Raykar等[18]提出用與DD算法一樣的模型定義包的概率.后面的兩個算法雖然滿足標準的多示例學習假設，但是建立的目標函數都是非凸的，遇到了與DD算法一樣的求解困難.

本文通過定義一個新的關系函數來建立包的概率和其示例的概率之間的聯系，提出一種既能充分體現標準的多示例學習假設，又能使目標函數為凹函數的基于Logistic回歸模型的多示例學習算法.在標準的多示例學習假設中，一個包是正包當且僅當該包至少包含一個正示例.這就意味著每個包都有一個關鍵的示例控制著該包的標簽，因此可以定義每個包為正包的概率為其所含示例為正示例的概率的最大值.由于最大值函數不是一個光滑函數，本文提出用凝聚函數來逼近它.最后從理論上證明所建立的目標函數是凹函數.

1 模型建立

令χ＝Rd表示示例空間，D＝ ｛（Bi，yi）｜1≤i≤n｝表示訓練集，其中Bi＝ ｛xi1，xi2，…，xini｝是包含ni個示例的包，yi∈｛＋1，－1｝是包Bi的標簽，xij∈χ表示第i個包的第j個示例.多示例學習的任務就是要利用訓練集尋找一個能夠給出未標記包的正確標簽的函數.

因為在標準的多示例學習假設中，訓練集中的每個示例都有隱含的標簽，因此考慮用定義在示例空間χ上的線性判別函數來判

斷示例的標簽，如果f（x珘）＞0則示例x珘的標簽為正，反之則為負.為了公式書寫方便，用齊次坐標表示法表示每個示例，從而可以把f（x珘）直接寫作f（x）＝Wx.利用 Logistic函數σ（t）＝1/（1＋e－t），可以定義如下的概率：）

另外，在標準的多示例學習假設中，一個包在當且僅當至少包含一個正示例時為正包.這就意味著每個包中都有一個關鍵的示例控制著該包的標簽.于是可以用示例中正標簽概率的最大值代表該包為正的概率：

利用P（yi＝－1｜Bi，W）＝1－P（yi＝1｜Bi，W）可以推導出，Bi為負包的概率：

綜合式（2）、（3）可得

下面用最大似然估計法求解參數W.由于訓練集中各個包是相互獨立的，似然函數可以寫為

因此，可以通過最大化對數似然函數lnL求得參數W，即

2 對數似然函數逼近

凝聚函數（aggregate function）又名指數懲罰函數（exponential penalty function）

是由Li[19]最早在求解非線性規劃問題時利用代理約束概念和最大熵原理推導出來的，這里p是一個正的控制參數.該函數和對應的最大值函數有如下的關系式：

因此，對于有限正整數m，當p趨于正無窮時，Gp（x）能單調一致地逼近G（x）.

由于n0是有限的，對任意的閾值ε＞0，都存在p使得

下面討論式（11）中的對數似然函數

的性質.顯然式（12）是一個連續可微函數.

對式（12）求導可得

式中：wk表示W的第k個元素，xij（k）表示xij的第k個元素；

觀察gi1的表達式中各項，當p趨近于正無窮大時，有下式成立：

同樣，當p趨近于正無窮大時，gi2的表達式中各項有如下性質：

假設對任意的i，集合的勢為1，即對任意的i有唯一的j0∈ ｛1，2，…，ni｝使得，則當p趨近于正無窮大時

式（19）可以寫成矩陣形式

3 模型求解

前文已證明了本文建立的對數似然函數是一個凹函數，因此可以用常用的優化方法求解問題（11）.本文采用擬牛頓法求解，迭代公式如下：

式中

是一個一維的凸優化問題，用單純形法（Nelder－Mead Algorithm）[20]對其求解.下面給出了具體的算法流程.

訓練

輸出：W；

初始化：W0為任意向量，H0為單位矩陣；

（2）利用式（21）計算W（k＋1）和H（k＋1）；

測試

4 實 驗

首先在多個標準數據集上測試了本文的算法.這些數據集包括文獻[1]中提供的麝香分子數據集 Musk1和 Musk2，文獻[8]中提供的Elephant、Fox和Tiger數據集.Musk1數據集包含47個正樣本和45個負樣本；Musk2數據集包含39個正樣本和63個負樣本.Elephant、Fox和Tiger數據集均包含100個正樣本和100個負樣本，正樣本數據是由包含該種動物的圖片生成的，負樣本則由不包含該種動物的圖片數據任意組成.表1給出了這些數據集的詳細信息.表2給出了本文算法與其他算法在標準數據集上的實驗結果，每個數據集上的最好實驗結果由粗體顯示.所有算法的實驗結果都是采用十倍交叉驗證法計算所得，其他算法的實驗結果引自相關文獻.從表2可以看出，本文的算法在對Elephant和Fox數據集的實驗都得到了最高的準確率，在其他數據集上的實驗雖準確率沒有達到最高，但仍然與最好結果相近，因此本文的算法在這些標準數據集上的整體表現要優于其他算法.

表1 標準數據集的詳細信息Tab.1 The details of benchmark data sets

表2 在標準數據集上的實驗結果Tab.2 Experimental results on benchmark data sets

為了進一步驗證本文算法的性能，還針對一個文本分類問題進行了測試.該文本問題包括20個文本數據集，每個數據集由50個正樣本和50個負樣本組成，關于這些文本數據集的詳細信息，可以參考文獻[12].將本文算法與文獻[12]中算法（MI－Kernel和miGraph）的實驗結果進行了比較，結果如表3所示，所有算法的實驗結果都是采用10次十倍交叉驗證法計算所得的平均精度，最好的實驗結果由粗體顯示.從表3可以看出，本文提出的算法分別在13個數據集上的準確率要高于其他兩個算法，在1個數據集上與miGraph算法的精度一樣但要優于MI－Kernel算法，另外在所有數據集上的結果均要優于MI－Kernel算法.因此本文的算法在文本分類問題中的整體表現要優于其他兩個算法.

表3 文本分類數據集上的實驗結果Tab.3 Experimental results on text categorization

5 結 論

本文在標準多示例學習的假設條件下，建立了一個基于Logistic回歸模型的多示例學習算法.算法的創新之處是定義了一個新的似然函數，然后通過引入凝聚函數去逼近最大值函數，把對數似然函數轉化為一個光滑的凹函數，從而使問題可以用常用的無約束優化方法快速求解，不會存在局部極大值的問題.在標準數據集和實際文本分類問題上的實驗結果表明，本文的算法要優于其他算法.下一步將研究利用高斯過程推廣該算法到非線性情形，從而使得該算法更具有競爭力.

[1]DIETTERICH T G， LATHROP R H，LOZANO－PREZ T.Solving the multiple－instance problem with axis－parallel rectangles [J].Artificial Intelligence，1997，89（1－2）：31－71

[2]VIOLA P，PLATT J，ZHANG C.Multiple instance boosting for object detection [C]// Advances in Neural Information Processing Systems 18.Cambridge：MIT Press，2006：1419－1426

[3]LI Y F，KWOK J T，TSANG I W，etal.A convex method for locating regions of interest with multi－instance learning[C]//Machine Learning and Knowledge Discovery in Databases－European Conference，ECML PKDD 2009，Proceedings.Bled：Springer－Verlag，2009：15－30

[4]ZARRA A，VVENTURA S，ROMERO C，etal.Multi－instance genetic programming for web index recommendation[J].Expert System and Applications，2009，36（9）：11470－11479

[5]ZHOU Z H，JIANG K，LI M. Multi－instance learning based web mining[J].Applied Intelligence，2005，22（2）：135－147

[6]MARON O，LOZANO－PREZ T.A framework for multiple－instance learning [C]//Advances in Neural Information Processing System 10.Cambridge：MIT Press，1998：570－576

[7]ZHANG Q，GOLDMAN S A.EM－DD：an improved multiple－instance learning technique[C]//Advances in Neural Information Processing Systems 14.Cambridge：MIT Press，2002：1073－1080

[8]ANDREWS S，TSOCHANTARIDIS I，HOFMANN T.Support vector machines for multiple－instance learning [C]// Advances in Neural Information Processing Systems 15.Cambridge：MIT Press，2003：577－584

[9]CHEN Y，BI J，WANG J.MILES：Multiple－instance learning via embedded instance selection [J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2006，28（12）：1931－1947

[10]ZHOU Z H，ZHANG M L.Neural networks for multi－instance learning [C]// Proccedings of the International Conference on Intelligent Information Technology.Beijing：ICIIT，2002

[11]ZHANG M L，ZHOU Z H.Adapting RBF neural networks to multi－instance learning [J]. Neural Processing Letters，2006，23（1）：1－26

[12]ZHOU Z H，SUN Y Y，LI Y F.Multi－instance learning by treating instances as non－i.i.d.samples[C]// Proceedings of the 26th International Conference on Machine Learning （ICML＇09）.Montreal：Omnipress，2009：1249－1256

[13]KWOK J T， CHEUNG P M. Marginalized multi－instance kernels[C]//Proceedings of the 20th International Joint Conferences on Artificial Intelligence. San Francisco：Morgan Kaufmann Publishers Inc.，2007：901－906

[14]CHEUNG P M，KWOK J T.A regularization framework for multiple－instance learning [C]//Proceedings of the 23rd International Conference on Machine Learning.New York：ACM，2006：193－200

[15]ZHOU Z H， ZHANG M L. Ensembles of multi－instance learners [C]// Proceedings of the 14th European Conference on Machine learning（LNAI 2837）. Berlin：Springer－Verlag， 2003：492－502

[16]XU X，FRANK E.Logistic regression and boosting for labeled bags of instances[C]//Proceedings of the Pacific－Asia Conference on Machine Learning and Data Mining.Berlin：Springer－Verlag，2004：272－281

[17]RAY S，CRAVEN M.Supervised versus multiple instance learning：an empirical comparison [C]//Proceedings of the 22nd International Conference on Machine Learning.Bonn：Association for Computing Machinery，2005：697－704

[18]RAYKAR V C，KKRISHNAERAM B，DUNDAR J，etal. Bayesian multiple instance learning：automatic feature selection and inductive transfer[C]// Proceedings of the 25th International Conference on Machine Learning.New York ：Association for Computing Machinery， 2008：808－815

[19]LI X S.An aggregate function method for nonlinear programming [J]. Science in China Series A－Mathematics，1991，34（12）：1467－1473

[20]WANG Z L，HE J J，SHANG H，etal.Forward kinematics analysis of a six－DOF Stewart platform using PCA and NM algorithm[J].Industrial Robot：An International Journal，2009，36（5）：448－460

[21]EL－MANZALAWY Y， HONAVAR V.MICCLLR：Multiple－instance learning using class conditional log likelihood ratio.[C]//Proceedings of the 12th International Conference on Discovery Science.Heidelberg：Springer Berlin，2009：80－91

[22]MANGASARIAN O L， WILD E W. Multiple instance classification via successive linear programming [J].Journal of Optimization Theory and Applications，2008，137（3）：555－568