一種貝葉斯和支持向量機相結合的相關反饋策略

陳長江, 侯 進

（西南交通大學信息科學與技術學院,四川成都 610031）

0 引言

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

相關反饋方法的基本思路是在檢索過程中,允許用戶對檢索結果進行評價和標記,找出結果中哪些與查詢圖像相關,哪些不相關,然后將用戶標記的相關信息,作為訓練樣本反饋給系統進行學習,指導下一輪檢索,從而使檢索結果更符合用戶的需要。相關反饋有多種算法,如基于查詢向量轉移的方法[1],基于權重調整的方法[2],基于機器學習的方法[3-5]等。

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

1 多維正態分布條件下的貝葉斯分布

1.1 多維正態分布

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

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

1.2 多維正態分布條件下的貝葉斯判別原理

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

因為在同一模式識別問題中,對于不同的類,貝葉斯公式中全概率都是相同的,所以各類的判別函數也可以定義為:

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

該函數含指數,不方便計算,考慮到對數函數是單調遞增函數,對它取對數,去掉與類無關的項得到:

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

2 支持向量機原理

支持向量機是一種基于統計學習理論的機器學習方法,它建立在VC維和結構風險最小化理論上,根據有限的樣本信息在模型的復雜性和學習能力之間尋求最佳的折中,從而期望獲得更好的泛化能力。

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

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

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

因此,SVM通過選擇適當的核函數K,可以很好的應用于非線性分類。

3 結合貝葉斯和SVM的相關反饋算法

3.1 多維正態分布條件下的貝葉斯分類

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

其中,Pr與Pn分別為相關圖像類和不相關圖像類的先驗概率,Nr與Nn分別為標注的相關圖像和不相關圖像個數,ur與un分別為兩個類的均值,I+與I-分別代表相關圖像和不相關圖像,∑r與∑n分別為兩個類的協方差矩陣。

由公式（10）分別更新兩個類的分類器參數之后,就可以對圖像庫進行分類判別了。通過分類,把圖像庫中屬于相關圖像類的圖像保存起來,構成相關圖像庫,把不屬于相關圖像庫的圖像排除掉。

3.2 基于SVM的分類

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

每次反饋過程中,用戶標注的相關圖像和不相關圖像都會進行更新變化,根據每次反饋更新后的結果訓練SVM,得到SVM 的非線性分類器。然后,用SVM分類器對貝葉斯分類得到的相關圖像庫進行分類,并返回最終結果。

3.3 貝葉斯與SVM相結合的反饋技術

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

（1）根據用戶的需要,選擇前K幅圖像作為檢索結果返回給用戶。用戶對K幅圖像進行標注,點擊當前相關的圖像I+1,剩下的為不相關的圖像I-1,分別更新相關圖像類 I+和不相關圖像類 I-。相關圖像類:I+=（I+∪I+1）-I-,不相關圖像類:I-=（I-∪I-1）-I+。

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

圖1 反饋流程圖

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

（4）用第二步得到的SVM分類器對相關圖像庫U+中的圖像進行反饋。在相關圖像庫中,每一幅圖像Ii對應著相應的分數score（Ii）=f（xi）,分數越大,與查詢圖像的相似度就越大。根據分數的大小進行排序,把分數最大的前K幅圖像反饋給用戶。

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

4 實驗分析

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

圖2 系統界面

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

圖3和圖4分別是實驗中選取的7個關鍵詞的前27幅圖像和前36幅圖像的平均查準率。利用文中提出的貝葉斯和SVM相結合的反饋算法跟單獨用傳統SVM或貝葉斯反饋算法進行比較,分別計算3種算法通過1至3次反饋后每次反饋的平均反饋精度,比較結果如圖中反饋精度曲線所示。

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

圖3 Top27的平均查全率

圖4 Top36的平均查全率

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

圖6 Top36的平均查全率

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

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

5 結束語

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

[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] 蘇中,張宏江,馬少平.基于貝葉斯分類器的圖像檢索系統相關反饋算法[J].軟件學報,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.