一種貝葉斯和支持向量機(jī)相結(jié)合的相關(guān)反饋策略

陳長江, 侯 進(jìn)

（西南交通大學(xué)信息科學(xué)與技術(shù)學(xué)院,四川成都 610031）

0 引言

近年來,基于內(nèi)容的圖像檢索已成為較為熱門的研究課題。傳統(tǒng)的圖像檢索系統(tǒng)自動(dòng)提取圖像特征,通過比較圖像間的相似度,從圖像庫中返回相似度大的圖像。在這種系統(tǒng)中,最大的問題是計(jì)算機(jī)自動(dòng)提取的低層特征和用戶理解間存在“語義鴻溝”,使檢索結(jié)果不盡人意。于是,相關(guān)反饋技術(shù)被引入到基于內(nèi)容的圖像檢索領(lǐng)域。

相關(guān)反饋方法的基本思路是在檢索過程中,允許用戶對檢索結(jié)果進(jìn)行評價(jià)和標(biāo)記,找出結(jié)果中哪些與查詢圖像相關(guān),哪些不相關(guān),然后將用戶標(biāo)記的相關(guān)信息,作為訓(xùn)練樣本反饋給系統(tǒng)進(jìn)行學(xué)習(xí),指導(dǎo)下一輪檢索,從而使檢索結(jié)果更符合用戶的需要。相關(guān)反饋有多種算法,如基于查詢向量轉(zhuǎn)移的方法[1],基于權(quán)重調(diào)整的方法[2],基于機(jī)器學(xué)習(xí)的方法[3-5]等。

相關(guān)反饋建立在圖像檢索[6]結(jié)果基礎(chǔ)上,是用戶和系統(tǒng)反復(fù)交互的過程,提高反饋的效率,減少用戶與系統(tǒng)的交互次數(shù)始終是相關(guān)反饋研究的關(guān)鍵問題。Bayesian反饋算法多數(shù)會(huì)受到小樣本問題和訓(xùn)練樣本不對稱問題的制約,如何克服這個(gè)問題對提高反饋效果至關(guān)重要。針對以上問題,在傳統(tǒng)的反饋算法基礎(chǔ)上提出結(jié)合貝葉斯[7-8]和SVM（SVM+Bayesian,S+B）的反饋策略。該算法用貝葉斯分類器對圖像庫進(jìn)行分類,聚集相關(guān)的圖像,去除無關(guān)的圖像,實(shí)現(xiàn)圖像庫的壓縮,然后用SVM分類器對縮小后的圖像庫反饋,從而縮小算法的搜索范圍,減少反饋次數(shù),提高了反饋效果。對小樣本問題和訓(xùn)練樣本不對稱問題也有幫助。首先,雖然檢索開始時(shí)貝葉斯分類器的訓(xùn)練樣本有限,但隨著反饋次數(shù)增加,用戶標(biāo)注的樣本數(shù)增加,訓(xùn)練樣本逐漸累加,樣本個(gè)數(shù)逐漸增多,貝葉斯分類器效果會(huì)變好;其次,算法中的貝葉斯分類器的參數(shù)不是固定的,它隨著樣本數(shù)的改變更新自身的參數(shù),所以每次反饋用的貝葉斯分類器都不同,這樣構(gòu)造的貝葉斯分類器會(huì)更合理,效果會(huì)更好;最后,反饋過程中用戶標(biāo)注的是前K幅圖像,只標(biāo)注相關(guān)圖像,剩下的為不相關(guān)圖像,而不是把圖像庫中所有未標(biāo)注的圖像作為不相關(guān)圖像,所以基本不可能產(chǎn)生訓(xùn)練樣本不對稱問題。

1 多維正態(tài)分布條件下的貝葉斯分布

1.1 多維正態(tài)分布

高斯分布模型是一種通用的概率分布模型。這種模型運(yùn)算簡單,而且現(xiàn)實(shí)世界的很多事件和高斯分布有著極大的相似性。假定 n維空間Rn中的向量x滿足高斯分布,則x的概率密度函數(shù)為:

其中,x=（x1,x2,…,xd）T為d維特征向量,u=（u1,u2,…,ud）T為d維均值向量,∑為 d×d維協(xié)方差矩陣,∑-1為∑的逆矩陣,為∑的行列式。

1.2 多維正態(tài)分布條件下的貝葉斯判別原理

貝葉斯分類以貝葉斯定理為基礎(chǔ),通過訓(xùn)練大量樣本來估算后驗(yàn)概率。貝葉斯分類器把樣本劃分到后驗(yàn)概率大的一類中,因此可以定義 ωi類的判別函數(shù)為:

因?yàn)樵谕荒Ｊ阶R別問題中,對于不同的類,貝葉斯公式中全概率都是相同的,所以各類的判別函數(shù)也可以定義為:

判別函數(shù)中,先驗(yàn)概率P（ωi）是一個(gè)與特征向量無關(guān)的常量,類條件概率密度P（x|ωi）則滿足一定的概率分布,假定 P（x|ωi）符合 d維正態(tài)分布,則判別函數(shù)為:

該函數(shù)含指數(shù),不方便計(jì)算,考慮到對數(shù)函數(shù)是單調(diào)遞增函數(shù),對它取對數(shù),去掉與類無關(guān)的項(xiàng)得到:

得到判別函數(shù)后,就有了分類判別的依據(jù),就能通過比較兩類判別函數(shù)的大小對數(shù)據(jù)進(jìn)行分類。

2 支持向量機(jī)原理

支持向量機(jī)是一種基于統(tǒng)計(jì)學(xué)習(xí)理論的機(jī)器學(xué)習(xí)方法,它建立在VC維和結(jié)構(gòu)風(fēng)險(xiǎn)最小化理論上,根據(jù)有限的樣本信息在模型的復(fù)雜性和學(xué)習(xí)能力之間尋求最佳的折中,從而期望獲得更好的泛化能力。

作為一種可訓(xùn)練的機(jī)器學(xué)習(xí)方法,假定訓(xùn)練數(shù)據(jù)為{（x1,y1）,（x2,y2）,…,（xl,yl）},x∈Rn,y∈{-1,1},其中y是類別標(biāo)號。假定n維空間下的線性判別函數(shù)為g（x）=ω.x+b,它對應(yīng)的分類超平面為 ω.x+b=0。將g（x）歸一化,讓兩類的樣本 x滿足|g（x）|≥1,通過它得到分類間隔2/‖ω‖。分類間隔最大等價(jià)于‖ω‖或‖ω‖2最小,所以尋求最優(yōu)超平面的問題轉(zhuǎn)化為解決下面目標(biāo)函數(shù)的二次規(guī)劃問題:

對于線性不可分情況,SVM引入松弛變量ξ和懲罰因子C,目標(biāo)函數(shù)變成:

通過核函數(shù)K（x,y）=（φ（x）,φ（y））的非線性轉(zhuǎn)換,SVM把輸入空間轉(zhuǎn)換到高維空間,在高維空間中求最優(yōu)分類面,得到高維空間的分類函數(shù)為:

因此,SVM通過選擇適當(dāng)?shù)暮撕瘮?shù)K,可以很好的應(yīng)用于非線性分類。

3 結(jié)合貝葉斯和SVM的相關(guān)反饋算法

3.1 多維正態(tài)分布條件下的貝葉斯分類

根據(jù)多維正態(tài)分布條件下的貝葉斯分布,可以容易實(shí)現(xiàn)貝葉斯分類。由多維正態(tài)分布條件下貝葉斯分布的判別函數(shù)公式（5）,類i的判別函數(shù)有3個(gè)參數(shù):均值ui,協(xié)方差矩陣∑i和先驗(yàn)概率P（ωi）。相關(guān)反饋過程中,假定用戶標(biāo)注的相關(guān)圖像和不相關(guān)圖像為兩類。每次反饋,根據(jù)標(biāo)注得到的兩個(gè)圖像類,分別更新兩個(gè)類的貝葉斯分類器參數(shù),就可不斷提高兩個(gè)類分類器的性能。以下為兩個(gè)貝葉斯分類器的3個(gè)參數(shù)更新方程:

其中,Pr與Pn分別為相關(guān)圖像類和不相關(guān)圖像類的先驗(yàn)概率,Nr與Nn分別為標(biāo)注的相關(guān)圖像和不相關(guān)圖像個(gè)數(shù),ur與un分別為兩個(gè)類的均值,I+與I-分別代表相關(guān)圖像和不相關(guān)圖像,∑r與∑n分別為兩個(gè)類的協(xié)方差矩陣。

由公式（10）分別更新兩個(gè)類的分類器參數(shù)之后,就可以對圖像庫進(jìn)行分類判別了。通過分類,把圖像庫中屬于相關(guān)圖像類的圖像保存起來,構(gòu)成相關(guān)圖像庫,把不屬于相關(guān)圖像庫的圖像排除掉。

3.2 基于SVM的分類

SVM分類依據(jù)支持向量機(jī)原理。由非線性支持向量機(jī)的分類函數(shù)公式（9）,求圖像 x到分類超平面的距離需要知道核函數(shù)K（xi,x）,拉格朗日乘子 αi和偏移因子b*。核函數(shù)選擇徑向基核函數(shù),拉格朗日乘子和偏移因子可通過求目標(biāo)函數(shù) φ（ω）=‖ω‖2/2的二次規(guī)劃問題求出,這樣就有了非線性條件下SVM的分類函數(shù)。

每次反饋過程中,用戶標(biāo)注的相關(guān)圖像和不相關(guān)圖像都會(huì)進(jìn)行更新變化,根據(jù)每次反饋更新后的結(jié)果訓(xùn)練SVM,得到SVM 的非線性分類器。然后,用SVM分類器對貝葉斯分類得到的相關(guān)圖像庫進(jìn)行分類,并返回最終結(jié)果。

3.3 貝葉斯與SVM相結(jié)合的反饋技術(shù)

結(jié)合以上兩種分類算法,提出一種貝葉斯和SVM相結(jié)合的反饋算法。首先,每次反饋標(biāo)注的結(jié)果跟前面幾次反饋的標(biāo)注結(jié)果合并,得到相關(guān)圖像類和不相關(guān)圖像類;其次,利用正態(tài)分布下的貝葉斯建立相關(guān)圖像類和不相關(guān)圖像類的分類器,同時(shí)用標(biāo)注結(jié)果訓(xùn)練SVM得到SVM分類器;最后,用兩個(gè)貝葉斯分類器對圖像庫進(jìn)行分類,得到屬于相關(guān)圖像類的圖像集合,也就是相關(guān)圖像庫,然后用SVM分類器對相關(guān)圖像庫進(jìn)行分類,并返回最終結(jié)果。其流程如圖1所示,具體的算法流程如下:

（1）根據(jù)用戶的需要,選擇前K幅圖像作為檢索結(jié)果返回給用戶。用戶對K幅圖像進(jìn)行標(biāo)注,點(diǎn)擊當(dāng)前相關(guān)的圖像I+1,剩下的為不相關(guān)的圖像I-1,分別更新相關(guān)圖像類 I+和不相關(guān)圖像類 I-。相關(guān)圖像類:I+=（I+∪I+1）-I-,不相關(guān)圖像類:I-=（I-∪I-1）-I+。

（2）根據(jù)更新得到的相關(guān)圖像類I+和不相關(guān)圖像類I-,利用公式（10）分別更新相關(guān)圖像類和不相關(guān)圖像類的貝葉斯分類器參數(shù),同時(shí)訓(xùn)練SVM,得到SVM分類器。

圖1 反饋流程圖

（3）經(jīng)過每次更新參數(shù)后,相關(guān)圖像類和不相關(guān)圖像類就有了各自的分類判別函數(shù)gr（x）、gn（x）,把圖像庫中的圖像代入兩個(gè)判別函數(shù)進(jìn)行判定,如果gr（x）＞gn（x）,就把 x歸屬于相關(guān)圖像庫。這樣,經(jīng)過貝葉斯判別后,就得到了本次反饋的相關(guān)圖像庫U+。

（4）用第二步得到的SVM分類器對相關(guān)圖像庫U+中的圖像進(jìn)行反饋。在相關(guān)圖像庫中,每一幅圖像Ii對應(yīng)著相應(yīng)的分?jǐn)?shù)score（Ii）=f（xi）,分?jǐn)?shù)越大,與查詢圖像的相似度就越大。根據(jù)分?jǐn)?shù)的大小進(jìn)行排序,把分?jǐn)?shù)最大的前K幅圖像反饋給用戶。

（5）保存檢索結(jié)果,如果用戶感到滿意,反饋的過程就可以停止了。否則,用戶再提交標(biāo)注圖像,轉(zhuǎn)到第一步,然后再次反饋,直到反饋結(jié)果滿足用戶需要。

4 實(shí)驗(yàn)分析

從Corel圖像庫中選取30個(gè)語義類,每類選取30幅圖像,一共有900幅圖像,包括鳥、海浪、猴子等。系統(tǒng)界面如圖2所示,界面中左邊部分用來標(biāo)注圖像,右邊用來顯示反饋結(jié)果。顏色特征通過計(jì)算HSV顏色直方圖來提取每個(gè)區(qū)域的主色,也就是HSV均值,這個(gè)特征是1×3維的,紋理特征利用曲波系數(shù)即尺度為5,方向?yàn)?的曲波特征,它是1×84維的特征。實(shí)驗(yàn)中的SVM 基于Libsvm,采用徑向基核函數(shù)K（x,y）=exp（-λ‖x-y‖2）,λ＞0,其中 λ=0.1,SVM算法中的懲罰系數(shù)C=100,參數(shù)λ和C是經(jīng)過多次試驗(yàn)之后選取的最優(yōu)值。

圖2 系統(tǒng)界面

假定用戶查詢的是每一個(gè)語義類的圖像,考慮到用戶的耐心和貪婪性,假定反饋次數(shù)為3次,用戶每次反饋標(biāo)識的圖像數(shù)目為界面中的前5頁,即45幅圖像。使用圖像檢索領(lǐng)域通用的評價(jià)標(biāo)準(zhǔn),即平均查準(zhǔn)率評價(jià)系統(tǒng)的性能。實(shí)驗(yàn)中選取bird、mountain、monkey、bonsai、wave、flower、bear作為它們對應(yīng)類的檢索關(guān)鍵詞,然后分別統(tǒng)計(jì)這7個(gè)關(guān)鍵詞每次反饋過程中前27幅圖像和前36幅圖像中相關(guān)圖像個(gè)數(shù),分別求出各個(gè)關(guān)鍵詞的前27幅圖像和前36幅圖像的反饋精度,最終求出通過3次反饋后的平均反饋精度。反饋精度公式定義為:P=a/b,其中a為前K幅圖像中相關(guān)圖像個(gè)數(shù),b為前K幅圖像的個(gè)數(shù)。

圖3和圖4分別是實(shí)驗(yàn)中選取的7個(gè)關(guān)鍵詞的前27幅圖像和前36幅圖像的平均查準(zhǔn)率。利用文中提出的貝葉斯和SVM相結(jié)合的反饋算法跟單獨(dú)用傳統(tǒng)SVM或貝葉斯反饋算法進(jìn)行比較,分別計(jì)算3種算法通過1至3次反饋后每次反饋的平均反饋精度,比較結(jié)果如圖中反饋精度曲線所示。

圖3和圖4表明Top27和Top36的平均查全率,從圖中曲線可以看出,單獨(dú)用SVM算法的平均反饋精度要比用貝葉斯算法的效果好;利用SVM和貝葉斯結(jié)合的算法要比單獨(dú)使用兩種算法的效果好;結(jié)合SVM和貝葉斯的算法在3次反饋的時(shí)候已經(jīng)達(dá)到了比較高的反饋精度,而單獨(dú)使用兩種算法的時(shí)候反饋精度要差。

圖3 Top27的平均查全率

圖4 Top36的平均查全率

為了進(jìn)一步說明貝葉斯結(jié)合SVM算法的有效性,將該算法同基于動(dòng)態(tài)學(xué)習(xí)的SVM算法[9]（Active SVM,S+A）進(jìn)行比較,并在同一數(shù)據(jù)集上做反饋結(jié)果測試。圖5和圖6是兩種算法在前27和前36幅圖像中平均查全率的比較結(jié)果。

圖6 Top36的平均查全率

圖5和圖6表明S+B和S+A通過3次反饋后的平均查全率,通過圖中曲線看出,無論是在前27幅圖像還是前36幅圖像中,貝葉斯和SVM相結(jié)合的反饋算法的平均反饋精度都好于基于動(dòng)態(tài)學(xué)習(xí)的SVM反饋算法,從而進(jìn)一步證明該算法的有效性。

從以上實(shí)驗(yàn)結(jié)果可以看出,提出的結(jié)合貝葉斯和SVM的反饋方法,先用貝葉斯對圖像庫進(jìn)行分類,去除了很多不相關(guān)圖像,而且得到屬于相關(guān)圖像類的相關(guān)圖像庫。這讓用SVM進(jìn)行反饋時(shí),僅僅針對得到的相關(guān)圖像庫,而不是整個(gè)圖像庫,大大縮小算法搜索范圍,減少了反饋次數(shù),提高了反饋的效率和效果。

5 結(jié)束語

相關(guān)反饋在基于內(nèi)容的圖像檢索中有重要意義,減少交互的次數(shù),提高反饋的精度是相關(guān)反饋必須解決的問題。文中提出一種結(jié)合貝葉斯和SVM的反饋算法,來減少反饋次數(shù),提高反饋效果。該算法通過多維正態(tài)分布條件下的貝葉斯分類,對圖像庫進(jìn)行壓縮,讓SVM分類針對經(jīng)過貝葉斯壓縮后的相關(guān)圖像庫,從而在減少反饋次數(shù)的基礎(chǔ)上,提高了反饋精度。如何進(jìn)一步優(yōu)化貝葉斯分類器的性能,是以后需要解決的問題。

[1] Y Rui,T S Huang,S Mehrotra.Content-based image retrieval with relevance feedback in mars[C].Proceedings of International Conference on Image Processing,USA,1997.

[2] Y Rui,T S Huang,S Mehrotra.Relevance feedback:a power tool for interactive content-based image retrieval[J].Circuits and Systems for Video Technology,1998,8（5）:56-59.

[3] JI Ai-bing,NIU Qi-ming,HA Ming-hu.Support vector machine learning from positive and unlabeled samples[C].Proceedings of International Conference on Intelligent System andKnowledge Engineering,China,2008.

[4] WAND Xue-jun,YANG Ling-ling.Yang.Application of SVM relevance feedback algorithms in image retrieval[C].Proceedings of International Conference on Information Science andEngineering,China,2008.

[5] YU Xia,HUANG Xiao-sha.Image retrieval combined color,texture,shape and SVM relevant feedback[J].Research of the Application of Computers,2007,11（11）:292-294.

[6] Hou Jin,Zhang Deng-sheng,Chen Zeng.Web image search by automatic image annotation and translation[C].Proceedings of International Conference on Signals and Image Processing,Brazil,2010.

[7] 蘇中,張宏江,馬少平.基于貝葉斯分類器的圖像檢索系統(tǒng)相關(guān)反饋算法[J].軟件學(xué)報(bào),2002,13（10）:2001-2006.

[8] SU Zhong,ZHANG Hong-jiang.Relevance feedback in content-based image retrieval:bayesian framework,feature subspaces,and progressive learning[J].Image Process,2003,12（8）:924-937.

[9] S Tong,E Chang.Support vector machine active learning for image retrieval[C].Proceedings of the 9th ACM International Conference on Multimedia,2001.