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

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