多示例學(xué)習(xí)及其研究現(xiàn)狀_蔡自興

多 示 例 學(xué) 習(xí) 及 其 研 究 現(xiàn) 狀多示例問題是 Dietterich 等 1 于上個(gè)世紀(jì) 90 年 代中期提出的 ,其目的是判斷藥物分子是否為麝香 分子 ( musky) .麝香分子問題是多示例學(xué)習(xí)方法的應(yīng)用之一. Maron 等 2 將多示例學(xué)習(xí)方法應(yīng)用于其他多示例問 題 ,比如股票投資中的個(gè)股選擇問題 ; Ruffo 等 3 將 多示例學(xué)習(xí)方法應(yīng)用于數(shù)據(jù)挖掘 ; Ant rews 等 4 , Huang 等 5 , Yang 等 6 , Zhang 等 7 分別將多示例 學(xué)習(xí)方法用于圖像檢索 ; Chevaleyre 等 8 用多示例 學(xué)習(xí)方法研究了 Mutagenesis 問題. 應(yīng)用結(jié)果表明 , 多示例學(xué)習(xí)方法對于多示例這類不分明問題能達(dá)到 較高的準(zhǔn)確性.多示例學(xué)習(xí)被認(rèn)為是第 4 種機(jī)器學(xué)習(xí)框架 ,并 在短短幾年時(shí)間內(nèi)取得了一些引人矚目的理論成果 和應(yīng)用成果. 本文首先介紹多示例學(xué)習(xí)的概念 ,并總 結(jié)出一些基本性質(zhì) ; 然后對測試數(shù)據(jù)集 musk 進(jìn)行 分析 ,重點(diǎn)討論了多示例學(xué)習(xí)的主要算法 ,并通過測 試數(shù)據(jù)集 musk 的測試準(zhǔn)確度對這些算法的性能進(jìn) 行比較 ;最后對多示例學(xué)習(xí)的未來發(fā)展作了展望.多示例學(xué)習(xí)的概念與性質(zhì)多示例學(xué)習(xí)問題可描述為 : 假設(shè)訓(xùn)練集中每個(gè) 數(shù)據(jù)是一個(gè)包 ( bag) ,每個(gè)包由一集示例 (instances) 組 成 ,每個(gè)包有一個(gè)訓(xùn)練標(biāo)記 :如果包有負(fù)標(biāo)記 ,則 包中所有示例都認(rèn)為是負(fù)標(biāo)記 ;如果包有正標(biāo)記 ,則 包 中至少有一個(gè)示例被認(rèn)為是正標(biāo)記. 學(xué)習(xí)算法需要生成一個(gè)分類器 ,能對未知的包 ( unseen bags) 進(jìn) 行正確分類. 多示例學(xué)習(xí)問題可用圖 1 來說明. 學(xué)習(xí) 算法的目標(biāo)是要找出 unknown p rocess f () 的最佳 逼近方法.圖 1多示例學(xué)習(xí)問題描述假設(shè)有 N 個(gè)包 B 1 , B 2 , , B N , 第 i 個(gè)包由 a ( i) 個(gè)示例 B 11 , B 12 , , B 1 a 組成 , 每個(gè)示例 B ij 是一個(gè) d 維特征向量 B ij1 , B ij2 , , B ij d T , 標(biāo)記集 為 = l i , l2 , , l N | l i , 其中為標(biāo)記空間. 記示例空間為 , 其子集為 B 1 , B 2 , , B N , 訓(xùn)練 數(shù)據(jù)集為D =B ,= B i , l i | i = 1 , 2 , N .(1)定義 1已知示例空間 及其子集 ( 包) B i = B ij | j = 1 , 2 , , a ( i) , i = 1 , 2 , , N , 標(biāo)記空間 = positive ,nagative , 標(biāo)記集 和訓(xùn)練數(shù)據(jù)集 D=B , 并且已知 :條件 1f M : B 1 , B 2 , B N .(2)則多示例學(xué)習(xí)問題為尋找一個(gè)映射 f M , 作為真實(shí)未知映射 f M 的最佳逼近.如果已知包中每個(gè)示例的標(biāo)記 , 則可計(jì)算出包 的標(biāo)記. 于是可利用下列條件 1 :條件 2f : B ij | i = 1 , 2 , , N , j = 1 , 2 , , a ( i) .(3)意為將 N 個(gè)包中的示例合并為一個(gè)數(shù)據(jù)集 DB= B ij | i = 1 , 2 , , N , j = 1 , 2 , , a ( i) , 每個(gè)數(shù) 據(jù)是一個(gè)示例 , 可按示例學(xué)習(xí) 9 , 10 等方式進(jìn)行學(xué) 習(xí). 按這種方式對多示例問題進(jìn)行學(xué)習(xí)的算法稱為 單示例學(xué)習(xí)算法.條件 1 與條件 2 之間有如下關(guān)系 :命題 1已知示例空間 及其子集 ( 包) B i = B ij | j = 1 , 2 , , a ( i) , i = 1 , 2 , , N :1) 如 果 標(biāo) 記 空 間 = TRU E (positive) ,FAL SE ( nagative) , 則對多示例問題 , 有f M ( B i ) = f ( B i1) f ( B i2) f ( B ia ( i) ) ,i = 1 , 2 , N ,(4)其中“ ”為布爾“OR”運(yùn)算 ;2) 如果 是實(shí)的二值集合 , 正標(biāo)記對應(yīng)的實(shí)數(shù) 比負(fù)標(biāo)記大 , 則對多示例問題 , 有f M ( B i ) = max f ( B i1) , f ( B i2) , f ( B ia ( i) ) ,i = 1 , 2 , N .(5)當(dāng)以示例作為訓(xùn)練數(shù)據(jù)時(shí) , 使用條件 2 可學(xué)習(xí)到一個(gè)映射 f , 作為映射 f 的最佳逼近 ;然后按命題1 也能構(gòu)造出一個(gè)映射 f M , 作為真實(shí)未知映射 f M 的最佳逼近.以示例或包作為訓(xùn)練數(shù)據(jù) , 是一個(gè)利用信息量 多少的問題. 從這一角度可分為以下幾種方式 :1) 將多示例轉(zhuǎn)變?yōu)閱问纠?, 也就是只利用條件2. 這時(shí)可用各種示例學(xué)習(xí)算法 (例如基于事例學(xué)習(xí) , 基于 實(shí) 例 學(xué) 習(xí) , 決 策 樹 算 法 ID3 及 其 改 進(jìn) 算 法 C4. 5 ,B P 神經(jīng)網(wǎng)絡(luò)等 9 , 10 ) 進(jìn)行學(xué)習(xí) , 獲取一個(gè)映射 f 作為映射 f 的最佳逼近 , 然后構(gòu)造出映射 f M .2) 同時(shí)利用條件 1 和條件 2 , 獲取一個(gè)映射 f作為映射 f 的最佳逼近 , 然后構(gòu)造出映射 f M .3) 同時(shí)利用條件 1 和條件 2 , 通過多示例學(xué)習(xí) 算法直接獲取映射 f M .4) 只利用條件 1 , 通過多示例學(xué)習(xí)算法直接獲 取映射 f M .從利用信息量看 , 方式 2) 和方式 3) 效果要好 些 , 方式 1) 效果較差. 文獻(xiàn)1 作過測試 , 按方式 1) 使用算法 C4 . 5 和反向傳播 B P 神經(jīng)網(wǎng)絡(luò)的效果較 差.從研究情況劃分 , 多示例學(xué)習(xí)算法可分成三 類 :一是將單示例學(xué)習(xí)算法擴(kuò)展為該算法的多示例 版本 ;二是針對多示例問題的特性構(gòu)造專門的算法 ; 三是前二者的結(jié)合 , 稱為混合方式. 多示例學(xué)習(xí)的測試數(shù)據(jù)集 musk對于多示例測試數(shù)據(jù)集的構(gòu)造 ,通常是首先選 擇所討論問題的特征向量和標(biāo)記集 ; 然后按問題 要求的規(guī)則 ,確定一組特征向量的取值作為一個(gè)示 例 ,若干示例組成一個(gè)包 ;最后按包中是否有正示例 而相應(yīng)地標(biāo)記正包或負(fù)包.常用的多示例測試數(shù)據(jù)集是 Dietterich 等 1 構(gòu) 造的 musk ,其目的是通過對收集的已知分子的分析 和訓(xùn)練學(xué)習(xí)系統(tǒng) ,能預(yù)知一個(gè)新的分子是否可用于 制藥. 為此 ,構(gòu)造 24 條射線來描述分子的形狀 (特征 向量) ,對每個(gè)分子結(jié)構(gòu)測量相應(yīng)的 24 個(gè)特征值. 對 于選擇的兩個(gè)麝香分子集 (其中有 62 個(gè)重復(fù)) ,用計(jì) 算機(jī)搜索每個(gè)分子的可能結(jié)構(gòu). 然后用優(yōu)化算法找 出其中的低能量結(jié)構(gòu). 對每個(gè)低能量結(jié)構(gòu)記錄其 24個(gè)特 征 值 , 組 成 表 1 所 示 的 數(shù) 據(jù) 集 musk1 和 a1 , b1 ; a2 , b2 ; ad , bd =musk2 (可從 U CI 機(jī)器學(xué)習(xí)數(shù)據(jù)庫中提取 11 ) . ( x 1, x 2, xd ) | ai x i bi , i = 1 , 2 , d .表 1 musk 數(shù)據(jù)集data setmusksnon2muskstotallow energy并構(gòu)造了幾種算法來學(xué)習(xí)該矩形 , 希望這個(gè)矩形能 覆蓋盡可能多的正示例 , 且盡量不含負(fù)示例. co nfo r matio n 1474592476239631026 598從表 1 可以看出 ,musk1 含有 47 個(gè)正包 (麝香分 子) 和 45 個(gè)負(fù)包 (非麝香分子) ,每個(gè)包中的示例數(shù) 量在 2 到 40 之間變化 ; musk2 含有 39 個(gè)麝香分子和 63 個(gè)非麝香分子. musk2 中的數(shù)量是 musk1 的 13. 8 倍 ,而分子只多了 10 個(gè) ,因此 musk2 的學(xué)習(xí)難度更 大.將表 1 中的 musk 數(shù)據(jù)集作為多示例學(xué)習(xí)算法 的訓(xùn)練集 ,每個(gè)分子作為一個(gè)包 ,具有 musks 性質(zhì)的 分子標(biāo)為正包 , 沒有即 non2musks 性質(zhì)的分子標(biāo)為 負(fù)包.多示例學(xué)習(xí)的主要算法多示例學(xué)習(xí)問題的概念并不復(fù)雜 ,但其求解卻 相當(dāng)困難. 自從 1997 年 Dietterich 等 1 發(fā)表第 1 篇多 示例學(xué)習(xí)算法的文章以來 ,通過近幾年的研究已形 成了一些有效的算法.多示例學(xué)習(xí)成為第 4 種學(xué)習(xí)框架多示例學(xué)習(xí)問題出現(xiàn)在機(jī)器學(xué)習(xí)的復(fù)雜應(yīng)用 中 ,學(xué)習(xí)系統(tǒng)對每個(gè)訓(xùn)練例子有部分或不完全的知 識 ,因此多示例學(xué)習(xí)成為與監(jiān)督學(xué)習(xí) 、非監(jiān)督學(xué)習(xí)和 強(qiáng)化學(xué)習(xí)并列的一種機(jī)器學(xué)習(xí) ,但與監(jiān)督學(xué)習(xí)和非 監(jiān)督學(xué)習(xí)又有所區(qū)別. 強(qiáng)化學(xué)習(xí)是學(xué)習(xí)“狀態(tài) 行 為”的映射 ,并提供了延遲獎(jiǎng)勵(lì) ;多示例學(xué)習(xí)是一類 廣泛存在的學(xué)習(xí)任務(wù) ,具有訓(xùn)練數(shù)據(jù)集的特殊性和 研究方法上的特點(diǎn). 包中負(fù)示例和正示例的比率 (噪 聲比) 可能任意高 , 多示例學(xué)習(xí)甚至比有噪聲的監(jiān) 督學(xué)習(xí)更難 ,這也是多示例學(xué)習(xí)需要深入研究的原 因之一.多示例學(xué)習(xí)的數(shù)據(jù)集特征介于監(jiān)督學(xué)習(xí)和非 監(jiān)督學(xué)習(xí)之間. 從方法上說 ,它可通過一定的轉(zhuǎn)換機(jī) 制轉(zhuǎn)變?yōu)楸O(jiān)督學(xué)習(xí)或非監(jiān)督學(xué)習(xí)問題. 轉(zhuǎn)變?yōu)楸O(jiān)督 學(xué)習(xí)的方法之一是將多示例問題變?yōu)閱问纠龁栴} , 從而把復(fù)雜的多示例學(xué)習(xí)問題變?yōu)橄鄬唵蔚膯问?例學(xué)習(xí)問題 ;反之 ,監(jiān)督學(xué)習(xí)或非監(jiān)督學(xué)習(xí)算法通過 改造也可轉(zhuǎn)變?yōu)槎嗍纠龑W(xué)習(xí)算法.軸 2 平行矩形分類器Dietterich 等 1 將每個(gè)分子視為一個(gè)包 , 假定分 類器可表為一個(gè)軸 2 平行矩形Long 等 8 描述了一個(gè)多項(xiàng)式時(shí)間理論的算法 , 并且證明如果包內(nèi)的示例是從積分布中獨(dú)立取的 , 則軸 2 平行矩形 A PR 是 PAC2 可學(xué)習(xí)的.Auer 等 12 證 明 如 果 包 中 的 示 例 不 獨(dú) 立 , 則A PR 學(xué)習(xí)在多示例學(xué)習(xí)框架下是 N P2hard 問題 , 需 要使用啟發(fā)式搜索方法 ; 并且提出一種不需要積分 布的 理 論 算 法 , 進(jìn) 而 構(gòu) 造 了 相 應(yīng) 的 實(shí) 際 算 法MUL T IN ST. 基于多樣性密度的學(xué)習(xí)算法Maron 等 13 提出了多樣性密度 (DD) 的通用框 架 , 它基于如下假設(shè) :正包減去負(fù)包的并的交點(diǎn)可通 過最大化多樣性密度來獲取. 對特征空間的每個(gè)點(diǎn) 定義一個(gè)多樣性密度 , 一個(gè)點(diǎn)附近的正包越多 、負(fù)包 越少 , 則該點(diǎn)的多樣性密度越大. 此算法的目標(biāo)是尋 找多樣性密度最大的點(diǎn).Zhang 等 14 將多樣性密度與 EM 算法結(jié)合起 來 , 將多樣性密度算法改進(jìn)為 ED2DD 算法. 這是目 前對 musk 數(shù)據(jù)集測試結(jié)果最好的算法. 其他機(jī)器學(xué)習(xí)的多示例版本自多示例問題提出以來 , 將其他機(jī)器學(xué)習(xí)擴(kuò)充 為多示例學(xué)習(xí)一直成為研究的焦點(diǎn) , 并取得了某些 成果.Wang 等 15 采用 Hausdorff 距離 , 擴(kuò)展了 k 2 最 近鄰算法 ( kNN) , 用于多示例學(xué)習(xí) ; Ruffo 3 擴(kuò)展了 C4. 5 決斷樹 , 構(gòu)造了多示例版本 Relic.Chevaleyre 等 8 構(gòu)造了 ID32M I 和 R IPPER2M I 算法 , 它們分別是 ID3 和 R IPPER 的多示例版本 , 并 進(jìn) 一 步 構(gòu) 造 了 NAV IV E2R IPPER2M I 和 R IPPER2M I2R EF IND ED2COV 等算法 16 .Zhou 等 17 通過使用特殊的誤差函數(shù)反向傳播 神經(jīng)網(wǎng)絡(luò) , 構(gòu)造了多示例學(xué)習(xí)算法 B P2M IP. 所構(gòu)造 的誤差函數(shù)利用了多示例問題的特性 , 因此算法的 性能良好. 多示例神經(jīng)網(wǎng)絡(luò)和多示例 SVMRamon 等 18 構(gòu)造了一個(gè)多示例神經(jīng)網(wǎng)絡(luò) , 包標(biāo) 記和包內(nèi)示例標(biāo)記通過命題 1 中的 max 函數(shù)來描 述. 對每個(gè) a ( i) 的可能值構(gòu)造了神經(jīng)網(wǎng)絡(luò) NN a ( i) , 整個(gè)網(wǎng)絡(luò)的輸出作為 f M 的最佳逼近. 當(dāng)訓(xùn)練代數(shù)充 分大時(shí) , 收斂點(diǎn)能使 f M 與輸出的平方誤差充分小.Andrews 等 4 利用支持向量機(jī) ( SVM) 來處理多示例學(xué)習(xí)問題 , 稱為 M I2SVM 算法 , 并通過人工 數(shù)據(jù)和圖像檢索來說明該方法的有效性.主要算法的性能比較目前通用的評價(jià)算法性能的數(shù)據(jù)集只有 musk 測試數(shù)據(jù)集 1 , 11 , 因此下面僅對已提出的一些算法 的測試結(jié)果進(jìn)行簡單的對比. 表 2 中的算法是按字 母順序排列的.表 2主要算法對 musk 測試數(shù)據(jù)集的性能比較2) 改造其他學(xué)習(xí)算法作為多示例學(xué)習(xí)算法. 多 示例學(xué)習(xí)的奠基者 1 指出 ,一個(gè)特別有意義的問題 是如何針對多示例問題修改決策樹 、神經(jīng)網(wǎng)絡(luò)和其 他流行的機(jī)器學(xué)習(xí)算法. 相信適當(dāng)?shù)剡x擇多示例學(xué) 習(xí)的特征 ,構(gòu)造的算法會有更好的性能.3) 對現(xiàn)有多示例算法的改進(jìn). 現(xiàn)有的算法仍有 需要改進(jìn)之處 ,比如提高算法的準(zhǔn)確性 ,針對大樣本 空間減少算法的計(jì)算代價(jià)等.算法musk1 數(shù)據(jù)集correct %musk2 數(shù)據(jù)集correct %4) 擴(kuò)展多示例學(xué)習(xí)算法的應(yīng)用. 目前 , 該算法 主要 應(yīng) 用 于 藥 物 分 子 活 性 研 究 和 圖 像 檢 索All2positive APR 1 80. 472. 6等 3 ,13 ,14 ,1921 . 由于多示例問題其實(shí)是一類不分明Backpropagation 1 75. 067. 7Bayesian2kNN 15 90. 282. 4BP2M IP 17 83. 8未測試C4. 5 1 68. 558. 8Citation2kNN 15 92. 486. 3Diverse Densit y 13 88. 982. 5EM2DD 14 96. 896. 0GFS all2positive APR 1 83. 766. 7GFS elim2count APR 1 90. 275. 5GFS elim2kde