基于最小風險的貝葉斯決策理論相關反饋方法

(浙江師范大學 數理與信息工程學院， 浙江 金華 321004)



摘 要：在對之前的相關反饋技術的問題和不足進行總結的基礎上，提出一種基于最小風險的貝葉斯決策理論相關反饋方法，通過一種自適應機制產生記憶，同時應用最小風險來使用戶獲得滿意的檢索結果。實驗結果表明該方法準確率高、響應速度快。

關鍵詞：貝葉斯決策理論； 適應機制； 最小風險

中圖分類號：TP391 文獻標志碼：A

文章編號：10013695(2009)03117103



Bayesian decision theory relevance feedback method based on minimum risk



WEN Chunyong， ZHU Xinzhong， XU Huiying， ZHAO Jianmin



(College MathematicsPhysical Information Engineering， Zhejiang Normal University， Jinhua Zhejiang 321004， China)



Abstract: Based on the summing up of some problems and deficiencies of relevance feedback the day before， this paper proposed Bayesian decision theory relevance feedback method based on minimum risk ， in which producing memory through a adaptive mechanism， and applying minimum risk to satisfy users with the retrieval results. Experimental result shows that it is a method with high accuracy and fast response speed.

Key words：Bayesian decision theory; adaptive mechanism; minimum risk



0 引言

近年來，基于內容的圖像檢索已經成為一個研究熱點，并成為數字圖書館等重大研究項目中的關鍵技術。而與之對應的相關反饋模型和框架也相繼被提出，如Rui等人[1]通過采用內容相關的圖像檢索系統，闡述了一個最優化問題，增加了基于使用者的評價先驗知識及找回圖像的低層次特征權重。在多媒體方面，使用相關反饋的例子有PicHunter[2]、MindReader[3]和Lee等人[4]提出的框架；對于基于內容的圖像檢索系統的相關反饋方法，有文獻[5~7]提出的貝葉斯相關反饋以及文獻[8]中最新提出的動態相似度度量反饋策略；文獻[9]中詳細地描述了當前相關反饋的幾種常用的檢索模型，即基于向量距離度量、基于概率模型、基于機器學習。相關反饋方法可以把用戶也作為檢索中的一部分，能夠得到更使用戶滿意的檢索結果，但是相關反饋還有很多問題需要解決：a）多少次反饋是必需的，而多少次反饋將是多余的。由于沒有一個對圖像檢索有效的量化評判標準，現在對檢索結果的評判還是基于人們自己的主觀感覺，在檢索中并不能判斷多少次相關反饋對用戶而言是足夠的。 b）大多數相關反饋技術都有一個缺點，就是反饋過程沒有記憶(memory)，導致用戶過去的反饋操作并不能幫助未來的查詢，因此，檢索的性能并不能維持很久。

本文針對當前相關反饋面臨的兩大問題，提出一種在最小風險基礎上的反饋方法，解決反饋中的兩大難題。最后通過實驗證明本文提出的方法能很好地提高準確率，滿足用戶對系統查詢結果的要求。同時在圖像數據庫小的前提下，響應速度快，適合于實時系統。

1 貝葉斯決策理論

貝葉斯決策理論[10]為不確定性理論提供了堅實的理論基礎，它可以描述為：設觀察數據為隨機分布的樣本集合X，其中每個樣本表示為x。令y∈Y表示一個類別。每個樣本都可能被分類到某個類別中，概率P(x|y)表示樣本x屬于類別y的條件概率。令A={a1，a2，…，an}表示一組可能的決策行為（不同具體應用對決策行為的定義可能不相同）。根據貝葉斯決策理論，每個決策行為ai都有一個損失函數L(ai，x，y)（例如：損失函數可以定義為將樣本x分類到類別y損失），固定Y和A，對樣本采取決策行為ai的風險定義為

R(ai|x)=L(ai，x，y)P(y|x)dy(1)

貝葉斯決策問題的求解是要發現每個樣本的最優決策行為ai（即風險最小行為），進而發現整個策略的全局最優行為{ai}。每個樣本的最優行為定義為

a*=arg min R(a|x)(2)

分類可以作為貝葉斯決策理論的一個特殊應用，這時決策行為A和分類類別Y表示的意義一致，行為即表示將樣本x分類到類別y。例如，在貝葉斯分類中，發現風險最小化的決策行為a*等價于將樣本分類到后驗概率最大的類別中。

2 自適應貝葉斯反饋機制

在基于內容的圖像檢索中，如果說兩幅圖是否相似，是指它們的特征是否相似。關于特征的相似關系理論通常采用的是幾何模型，把圖像的特征看做是坐標空間中的點，用兩點之間的距離來表示它們的相似程度，距離越近越相似，距離越遠表明越不相似。大量的研究集中在特征的選擇和距離的定義方面，如對色彩直方圖而言，可以采用直方圖交、直方圖歐式距離、余弦距離、海明距離、馬氏距離[9]等。當某些特征和相應的距離度量方法適合某些特定的圖庫時，檢索結果會相對好一些，但對一般圖庫而言，其檢索效果會受到影響。本文提出的自適應反饋機制建立在目前被廣泛采用的貝葉斯方法決策理論的基礎上，結合了相關反饋圖像檢索系統的時序特性，在圖像的相似性度量中嵌入了人的主觀性，在某種程度上使圖像檢索結果與人的主觀感知更加接近。

基于內容的相關反饋檢索是一個逐步求精的過程。首先是用戶提交查詢實例（可能是一幅或者一組圖像），系統獲取查詢實例的特征，并結合貝葉斯決策理論，通過求取類條件概率和損失函數得到的最小風險值，求取類條件概率時加入對上一次查詢的記憶，這樣每次得到的風險值比上一次要小，從而返回給用戶的結果也是比較滿意的。用戶還可以在反饋的交互中調整最小風險的閾值來獲得自己最滿意的結果。實質上圖像檢索系統也是一個分類問題，可以把交互的過程看做是一個訓練過程，用戶認為比較滿意和不滿意的圖片可以分別當作相關例訓練數據和非相關例訓練數據，而進一步查詢的過程是一個分類問題。把圖像檢索問題轉換為分類問題是本文用貝葉斯方法來解決圖像檢索問題的基本思路。下面給出該思路的具體描述。

用Ω±表示根據用戶提供的相關訓練數據和非相關數據對樣本空間進行的一個劃分；P(Ω+)和P(Ω-)分別表示相關例類和非相關例類的先驗概率；xj表示圖像j的視覺特征；P(xj|Ω+)是根據相關例訓練數據得到的類條件概率密度；P(xj|Ω-)是根據非相關例訓練數據得到的類條件概率密度；P(Ω+|xj)表示圖像j屬于相關例類的概率。

按照貝葉斯理論，可以用下式來表示

P(Ω+|xj)=[P(xj|Ω+)P(Ω+)]/[P(xj|(Ω+)P(Ω+)+P(xj|(Ω-)P(Ω-)](3)

由于圖像的低層次特征并不能很好地反映圖像的語義特征，按照上述分類器產生的分類結果并不能完全滿足用戶的需求。本文的圖像檢索系統提供一種自適應的學習功能，允許用戶對當前分類結果進行評價，通過反復學習以提高檢索精度。本文把用戶指定的相關例類和非相關例類當做新的訓練數據，隨著用戶 提供的訓練數據的變化，相應地，P(Ω+)、P(Ω-）和Ω±均在發生變化。圖 1表示了這一過程。

圖1表示了在相關反饋圖像檢索系統中，隨著用戶不斷提供新的相關例類訓練數據和非相關例類訓練數據，相關例類和非相關例類在不斷變化的過程。“+”表示相關例類訓練數據的中心；“-”表示非相關例類訓練數據的中心。隨著用戶的交互，相關例類與非相關例類的分界線在不斷發生變化。針對相關反饋圖像檢索系統的這種動態特性，引入查詢時刻的概念，對式（3）進行了修正，用Ω±(t)表示t時刻提供的相關例類和非相關例類對樣本空間進行的一個劃分，P(Ω±(t))用來表示t時刻的P(Ω±)，而t時刻的后驗概率P(Ω+|xj)用P(Ω±(t)|xj)來表示，P(Ω±(t)|xj)則表示 t時刻的類條件概率密度。式（3）經過上述修正后，變為如下形式：

P(Ω+|xj)=P(xj|Ω+(t))P(Ω+(t))/[P(xj|Ω+(t))P(Ω+(t))+P(xj|Ω-(t))P(Ω-(t))](4)

式（4）表示在t時刻，圖像j屬于相關例類的概率，那么圖像j屬于非相關例類的概率為

P(Ω-(t)|xj)=1-P(Ω+(t)|xj)(5)

上面描述了貝葉斯方法應用于相關反饋圖像檢索中的基本思路。具體的檢索過程可以概括為：通過用戶提供的相關和非相關例類訓練數據，得到相應的類模式，對每幅圖像計算出它屬于相關例類的概率P(Ω+|xj)。在具體的實現過程中本文用函數similarity()來近似類條件概率密度。即計算出相關例類樣本的中心X+和非相關例類樣本的中心X-，對每個xj觀測它在t時刻的類條件概率密度P(xj|Ω+(t))和P(xj|Ω-(t))。

P(xj|Ω+(t))=similarity(xj，X+)(6)

P(xj|Ω-(t))=similarity(xj，X-)(7)

其中similarity(xj，X±)表示圖像j與相（非相）關例的相似度，取值是 [0，1]，1表示兩者完全相似，0表示根本不相似。根據式（4）可以計算得t-1時刻圖片j屬于相關例類的概率 P(Ω+(t-1)|xj)。顯然，與相關例訓練數據比較相似的圖片，P(Ω+(t-1)|xj)比較大；反之則P(Ω+(t-1)|xj)比較小。為了使檢索結果逐步向用戶期望的狀態發展，不斷強調有希望的圖像（離相關例比較近，離非相關例比較遠的圖像），分別用P(Ω+(t-1)|xj)和P(Ω-(t-1)|xj)代替式（7）中的P(Ω+(t))和P(Ω-(t))，這就是本文提出的帶記憶的自適應貝葉斯機制。

P(Ω+(t)|xj)=[P(xj|Ω+(t))P(Ω+(t))]/

[P(xj|Ω+(t))P(Ω+(t-1)|xj)+

P(xj|Ω-(t))PΩ-(t-1)|xj)](8)

P(Ω-(t)|xj)=[P(xj|Ω-(t))P(Ω-(t))]/

[P(xj|Ω+(t))P(Ω+(t-1)|xj)+

P(xj|Ω-(t))PΩ-(t-1)|xj)](9)

通過式（8）系統建立了一個自適應的機制，使得與用戶給出的相關例訓練數據比較相似的圖片可以快速地獲得一個比較大的P(Ω+(t)|xj)。根據貝葉斯決策理論，下面描述求得最小風險的才是最優行為，才能獲得用戶滿意的結果。

3 最小風險的貝葉斯反饋算法

令L(Ft，Ω，xj)為損失函數(Ft是t時刻的反饋行為與后驗概率P(Ω+(t)|xj)相對應的概念），對于xj與Ω的反饋風險定位為

R(Ft|xj)=xjL(Ft，Ω，xj)P(Ω-(t)|xj)dΩ(10)

其中：xj是查詢實例；P(Ω+(t)|xj)是后驗概率。定義損失函數為

L(Ft，Ω，xj)=δ(Ω±，xj)(11)

其中：δ(Ω±，xj)表示當Ω+和xj相關時L(Ft，Ω，xj)=δ(Ω+，xj)=-1，而當不相關時L(Ft，Ω，xj)=δ(Ω-，xj)=1。當后驗概率P(Ω+(t)|xj)越大時，相關性越強，風險越小；反之，當P(Ω-(t)|xj)風險越大，相關性越弱。

風險定義為

R=R(Ft|xj)dxj(12)

求解最小風險相關反饋過程為

R*={F*}=arg{Ft}min({Ft}，Ω，xj)(13)

很顯然，可以在多次的檢索反饋后得到同類R*的閾值，從而在之后的檢索反饋中對R進行相應的比較，決定反饋的次數，從而能節約系統的資源并能使用戶得到滿意的結果。

4 實驗分析

為了客觀地評價相關反饋策略的性能，實現基于內容的圖像檢索原型系統，進行了大量實驗。該原型系統的圖像數據庫中存儲了兩組圖片，分別為1 000幅和5 000幅圖片。第一組圖片是從Corel圖像庫隨即抽取的10類圖片；第二組是從Corel圖像庫中隨機抽取的50類圖片，每類100幅圖片。由于不同的用戶對同一幅圖像的理解存在差異，對同一個查詢請求，不同用戶得到的最終結果不同，很難對實驗結果進行評價。因為Corel圖像庫中每一類圖片是在內容上相關的（Corel圖像庫中的每一類反映一個主題，圖片被分成了“鳥”“虎”“玫瑰花”等），本文用計算機進行了模擬。具體方法是選一幅圖像作為查詢實例，進行第1次查詢，對具有最小風險的圖像進行考察，如果它與被查詢的圖像在同一個類，則將其作為相關類；否則作為非相關類，然后開始下一時刻的查詢。

為了突出本策略的有效性，分別按照式（3）貝葉斯式方法和最小風險方法在第一個圖像庫作了450次查詢，在第二個圖像庫上作了600次查詢并把這些查詢結果進行平均，得到相應的平均準率，具體如圖2、3所示。另外本文還與文獻[7]提出的貝葉斯反饋算法進行了比較。圖3顯示了文獻提出的方法在第二個圖像庫上進行600次查詢后得到的平均準確率。具體實驗結果數據如表1所示。

上述結果表明本文策略能夠使查詢準確率明顯提高，尤其在圖像數據庫比較大的情況下。在第二個圖庫上的實驗結果表明，基于低層次特征的平均準確率只有9.90%，采用了本文策略第1次反饋后的平均準確率提高一倍達到20%，第2次反饋后的平均準確率提高了大約兩倍達到28.7%，在25次反饋后速度放緩；第50次的反饋后的平均準確率為81.1%，第100次反饋后平均準確率達到86.2%。從表1的最后兩列看，本文提出的方法明顯優于文獻[8]提出的貝葉斯反饋算法，它使每次反饋后的平均準確率提高了5%~15%。

5 結束語

本文提出了一種新的基于內容圖像檢索的相關反饋方法策略，并利用該方法進行了大量圖像檢索實驗。實驗結果表明，使用本文的方法比未使用本文方法有明顯提高，具有準確率高、相應速度快的優點，具有用戶滿意的查全率。與一般的相關反饋方法相比，它更適用于實時系統。該方法不僅可以用于一般的圖像檢索系統，Internet網上的圖片檢索，還可以直接應用到基于內容的視頻檢索中，視頻中的一幀對應著一幅圖像，因此它對基于內容的視頻檢索非常有意義。

參考文獻：

［1］Yong R，HUANG T S H，ORTEGA M，et al.Relevance feedback:a power tool for interactive contentbased image retrieval[J]. IEEE Trans on Circuits and Video Technology，1998， 8(5):644655.

[2]COX I J，MILLER M L，MINKA T，et al.The Bayesian image retrieval system，PicHunter: theory， implementation， and psychophysical experiments[J].IEEE Trans On Image Processing，2000，9:2037.

[3]ISHIKAWA Y，SUBRAMANYA R，FALOUTSOS C. Mindreader: query databases through multiple examples[C]//Proc of the 24th VLDB Conference.New York:Morgan Kaufmann，1998:218227.

[4]LEE C， MA W Y，ZHANG H J.Information embedding based on user’s relevance feedback for image retrieval[C]// Proc of SPIE Photonic.Bellingha Press:SPIE，1999:2022.

[5]SU Zhong，ZHANG Hongliang，MA Shaoping.Using Bayesian classifier in relevant feedback of image retrieval[C]//Proc of the 12th IEEE International Conference on Tools with Artificial Intelligence.Washington DC:IEEE Computer Society，2000:258261.

[6]SU Zhong，ZHANG Hongping ，MA Shaoping.Relevant feedback using a Bayesian classifier in contentbased image retrieval[C]//Proc of the SPIE Storage and Retrieval for Media Database.San Jose:SPIE Press，2001:97106.

[7]蘇中，張宏江，馬少平.基于貝葉斯分類器的圖像檢索相關反饋算法[J].軟件學報，2002，13(10):20012006.

[8]段立娟，高文，林守勛，等.圖像檢索中的動態相似性度量方法[J].計算機學報，2001，24(11):11561162.

[9]吳洪，盧漢清，馬頌德.基于內容圖像檢索中相關反饋技術的回顧[J].計算機學報，2005，28(12):19691979.

[10]唐杰，梁邦勇，李涓子，等.語義Web中的本體自動映射[J].軟件學報，2006，29(11):19561976.