基于改進(jìn)螢火蟲群優(yōu)化的多示例學(xué)習(xí)算法

陳濤，董紫君

（1.深圳職業(yè)技術(shù)學(xué)院教育技術(shù)與信息中心，深圳 518055；2.深圳職業(yè)技術(shù)學(xué)院建筑與環(huán)境工程學(xué)院，深圳 518055）

0 引言

多示例學(xué)習(xí)是一種新的機(jī)器學(xué)習(xí)框架。它被Dietterichet 等人[1]在對麝香分子活性研究中提出。在多示例學(xué)習(xí)中，它的訓(xùn)練集由一些具有標(biāo)簽的包組成，包有標(biāo)簽信息；每個(gè)包中含有若干個(gè)示例，示例是沒有標(biāo)簽信息的。假若一個(gè)包中有一個(gè)示例為正，那么該包能被標(biāo)記為正包；當(dāng)包中所有的示例都為負(fù)時(shí)，這個(gè)包才被標(biāo)記為負(fù)包。通過對訓(xùn)練集的學(xué)習(xí)，構(gòu)造出學(xué)習(xí)系統(tǒng)，使用這個(gè)系統(tǒng)對測試集數(shù)據(jù)的包標(biāo)簽進(jìn)行預(yù)測[2]。

在多示例學(xué)習(xí)算法研究中，代表性算法有多樣性密度（DD）算法[3]、ED-DD 算法[4]等。DD 算法是 Maron等人提出，通過在特征空間中尋找一個(gè)目標(biāo)概念點(diǎn)，這個(gè)概念點(diǎn)與所有正包中至少有一個(gè)示例距離最近、同時(shí)遠(yuǎn)離所有負(fù)包中的示例。找到目標(biāo)點(diǎn)后，把測試集包與該點(diǎn)之間距離是否大于一閾值來判定包的標(biāo)簽。為了獲取到目標(biāo)函數(shù)的最大值，DD 算法將所有正包中的每個(gè)示例作為一次搜索的初始點(diǎn)，使用梯度上升法，在示例空間中進(jìn)行搜索，一次搜索找到一個(gè)極值點(diǎn)。最后通過比較這些極值點(diǎn)，得到全局最大值。缺點(diǎn)是需要多次搜索示例特征空間，計(jì)算耗時(shí)較長[5]。EM-DD算法是結(jié)合期望最大值算法和多樣性密度函數(shù)，在每個(gè)包中，使用估計(jì)對包的標(biāo)簽起決定作用的示例代表包，將多示例轉(zhuǎn)換為單示例，來降低尋優(yōu)復(fù)雜度。

人工螢火蟲群優(yōu)化算法是一種融合人工智能技術(shù)與仿生物學(xué)的群智能算法。群智能優(yōu)化算法是模擬自然界中生物的群體行為，并用數(shù)學(xué)定義的方法。Krishnanand 和Ghose 根據(jù)螢火蟲的發(fā)出螢光素特性和相互吸引的行為，提出人工螢火蟲群算法[6]。它把空間上的各點(diǎn)看作為一個(gè)螢火蟲，利用螢光素強(qiáng)度較高的螢火蟲吸引螢光素強(qiáng)度較弱的螢火蟲的特點(diǎn)，在螢光素較弱的螢火蟲向螢光素較強(qiáng)的螢火蟲移動的迭代過程中，找到最優(yōu)位置點(diǎn)，完成尋優(yōu)過程。該算法獲得全局最優(yōu)解的概率較高,能較好地克服局部最優(yōu)解問題，是一種有效的優(yōu)化算法，在許多領(lǐng)域得到較好應(yīng)用，已成為眾多學(xué)者研究的熱點(diǎn)[7]。

1 基于改進(jìn)螢火蟲群優(yōu)化的多示例學(xué)習(xí)算法

1.1 構(gòu)造出多示例學(xué)習(xí)的目標(biāo)優(yōu)化函數(shù)

多樣性密度算法（DD）是O. Maron 和 T. Lozanoperez 等人提出，是多示例學(xué)習(xí)的一個(gè)目標(biāo)優(yōu)化函數(shù)。它通過在示例特征空間中找到一個(gè)概念點(diǎn)，使得每個(gè)正包中至少有一個(gè)示例離該點(diǎn)最近，而負(fù)包中的示例均遠(yuǎn)離該點(diǎn)。找到該點(diǎn)，把這個(gè)點(diǎn)作為參照點(diǎn)，來判斷新包的標(biāo)簽。設(shè)目標(biāo)概念點(diǎn)t 代表DD 函數(shù)值最大的點(diǎn)，通過最大化目標(biāo)函數(shù)Pr(x=t|B1+,B+2,…,B+l+,,…,)確定點(diǎn)t。假設(shè)各包之間相互獨(dú)立，根據(jù)貝葉斯判定理論，點(diǎn)t 能被下式確定：

上式中，B+i代表第i 個(gè)正包，B+ij代表第i 個(gè)正包第j 個(gè)示例；B-i代表第i 個(gè)負(fù)包，B-ij代表第i 個(gè)負(fù)包第 j個(gè)示例，L 是訓(xùn)練集。在求解時(shí)，公式（1）中乘積項(xiàng)能被轉(zhuǎn)換成：

概率Pr(t|Bij)被看作示例為目標(biāo)概念點(diǎn)概率，由概念點(diǎn)t 與示例Bij之間的距離得出：

為了避免掉入局部最優(yōu)值，保證找到全局最大值，所有正包中的每個(gè)正示例作為一個(gè)初始值點(diǎn)，執(zhí)行一次尋優(yōu)過程，最后比較局部極值點(diǎn)，得到函數(shù)最大值。由于DD 算法需要多次使用梯度上升法搜索特征空間，所以求解最大值過程是非常耗時(shí)的，不利于在圖像檢索的應(yīng)用，需要采用優(yōu)化算法來求解最大值。

1.2 使用改進(jìn)的人工螢火蟲群算法尋找函數(shù)最優(yōu)值

人工螢火蟲群算法[7]來源于對自然界中螢火蟲發(fā)光求偶、覓食等行為研究，是一種群智能算法。它利用螢火蟲發(fā)出螢光素來誘導(dǎo)、吸引伴侶或獵物，發(fā)出的螢光素越明亮、越熾熱，代表越有吸引力，螢光素值低的螢火蟲向螢光素值高的螢火蟲移動。螢光素值對應(yīng)適應(yīng)函數(shù)的值。螢火蟲在動態(tài)決策鄰域內(nèi)尋找螢光素值高的螢火蟲。人工螢火蟲群算法被描述以下4 個(gè)公式描述：

上述公式，公式（2）是螢光素的t 次迭代更新，ρ 是衰減因子，γ 是強(qiáng)化系數(shù)，J(xi(t))是位置xi的適應(yīng)度值。公式（3）是螢火蟲 i 移動到 j 的概率，j ∈Ni(t) ，Ni(t) 是 螢 火 蟲 i 的 鄰 域 ：li(t)

在基本GSO 算法的位置x 迭代計(jì)算中，會出現(xiàn)在具有亮螢光素的螢火蟲位置處停滯現(xiàn)象，它將延遲算法的收斂，增加耗時(shí)。為了避免這個(gè)現(xiàn)象，本文提出在具有亮螢光素的螢火蟲附近擾動的改進(jìn)算法：

RGSO 算法描述如下：

（1）初始化螢火蟲數(shù) n 和位置，置常量 ρ, γ, β,nt,s,l0,rs的數(shù)值；

（2）由公式（2），更新每個(gè)螢火蟲的螢光素值；

（3）由公式（3），計(jì)算每個(gè)螢火蟲移動概率，得出移動概率最大值的螢火蟲j；

（4）由公式（4），更新每個(gè)螢火蟲的位置；

（5）由公式（5），更新每個(gè)螢火蟲的決策鄰域；

（6）由公式（6），在螢火蟲局部極值位置處擾動；

（7）如果滿足收斂條件，則退出迭代，否則跳至步驟（2）處，循環(huán)執(zhí)行；

（8）輸出具有最亮螢光素的螢火蟲位置，也就是求解的目標(biāo)概念點(diǎn)。

1.3 應(yīng)用到圖像檢索

首先將每幅圖像分割成若干個(gè)區(qū)域，每個(gè)區(qū)域析取出一個(gè)9 維的區(qū)域特征[8]，將圖像和區(qū)域分別看作為多示例學(xué)習(xí)中的包和示例，這樣，將圖像檢索問題轉(zhuǎn)換到多示例學(xué)習(xí)框架下處理。

RGSOMIL 算法流程圖，見圖1 所示。

RGSOMIL 算法描述如下：

輸入：一組檢索圖像L={(I1,y1),...,(I|L|,y|L|)}，|L|是檢索圖像數(shù)。

輸出：從圖像庫中，返回相似度概率排前k 幅圖像。

圖1 RGSOMIL算法流程圖

（1）用戶提交一組檢索圖像（含正類圖像和負(fù)類圖像，正類與負(fù)類圖像數(shù)相同）。

（2）將每幅圖像分割成若干個(gè)區(qū)域，每個(gè)區(qū)域析取出一個(gè)9 維的區(qū)域特征。將圖像和區(qū)域分別看作為多示例學(xué)習(xí)中的包和示例，構(gòu)造多示例學(xué)習(xí)優(yōu)化函數(shù)。

（3）使用改進(jìn)的螢火蟲群優(yōu)化算法RGSO，求解得特征向量空間中的最優(yōu)解，即目標(biāo)概念點(diǎn)。

（4）計(jì)算圖像庫中圖像與目標(biāo)概念點(diǎn)之間的距離，作為該圖像與檢索圖像的相似度成績。排名前k 幅圖像被作為檢索結(jié)果返回給用戶。

2 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)中使用的圖像數(shù)據(jù)庫為Corel 2000 圖像庫，它 來 自 http://www.cs.olemiss.edu/～ychen/ddsvm.html。它從Corel 圖像庫中抽取2000 幅圖像，分屬20 個(gè)類別，每類100 幅圖像，有非洲土著居民、歷史建筑、大象、海灘、公共汽車、花、滑雪、戰(zhàn)艦等20 類。實(shí)驗(yàn)時(shí)，選擇其中一類圖像作為正類，其他類別圖像作為負(fù)類，正負(fù)類的選擇圖像數(shù)相同，為各3 幅。根據(jù)Krishnanand 和 Ghose 的分析[6]和實(shí)驗(yàn)數(shù)據(jù)集，RGSO 算法中的參數(shù)設(shè)置為：ρ=0.4,γ=0.6, β=0.08,nt=5,s=0.1,l0=5,rs=3。適應(yīng)函數(shù)J( )是多示例學(xué)習(xí)中的DD 函數(shù)。初始化前，先對示例特征歸一化預(yù)處理。所有示例向量被初始化作為n 個(gè)螢火蟲位置。

圖2 是本文方法在檢索“滑雪”類別圖像的一次檢索結(jié)果，返回相似度概率排前20 幅的圖像，檢索精確率達(dá)90%，方法取得較好的檢索結(jié)果。

圖2 一個(gè)檢索“滑雪”類別圖像結(jié)果

為了估算RGSOMIL 方法的檢索效率，做了一組檢索耗時(shí)實(shí)驗(yàn)。檢索耗時(shí)是指從用戶提交檢索圖像開始，到返回排前k 幅的圖像之間時(shí)間。實(shí)驗(yàn)平臺為Intel Core i5-4570 CPU 3.2GHz，3.2GHz 和內(nèi)存 8GB。將RGSOMIL 與DD 方法進(jìn)行比較，計(jì)算耗時(shí)見表1。

表1 計(jì)算耗時(shí)（秒）

從表1 看出，本文提出的GSOMIL 方法計(jì)算耗時(shí)為3.3 秒，相較DD 方法大大減少，僅為DD 方法的1/3左右。因?yàn)椋篋D 方法需要一一將所有正包的正示例作為初始點(diǎn)，通過梯度上升法，來尋找函數(shù)極值點(diǎn)，最后選取具有最大值的極值點(diǎn)作為目標(biāo)概念點(diǎn)，這個(gè)計(jì)算過程耗時(shí)較長。而RGSOMIL 通過改進(jìn)的人工螢火蟲群優(yōu)化算法，能快速收斂，找到DD 函數(shù)最大值，減少耗時(shí)。

3 結(jié)語

本文提出了一個(gè)基于改進(jìn)螢火蟲群優(yōu)化的多示例學(xué)習(xí)算法RGSOMIL，不依賴初始值點(diǎn)，尋找全局最大值精度高，能快速收斂。在Corel 圖像集上的實(shí)驗(yàn)表明，提出的方法具有較好的檢索性能。此外，我們發(fā)現(xiàn)RGSOMIL 算法在處理高維示例特征時(shí)，尋優(yōu)值不夠理想，這將是下一步的研究方向。