信息檢索中的相關反饋技術綜述
2009-01-01 00:00:00嚴華云劉其平肖良軍
計算機應用研究 2009年1期
（ 1.湖州師范學院 信息工程學院， 浙江 湖州 313000； 2.同濟大學 電子與信息工程學院， 上海 201804）
摘 要：論述了信息檢索中的向量空間模型、概率模型以及語言模型中所采用的相關反饋技術。其中主要介紹檢索詞的權重調整、查詢擴展、文檔相關反饋，以及語言模型中的查詢語言模型和文檔語言模型的調整。針對最近反饋方面的最新成果——基于term的反饋技術進行了探討，指出了相關反饋在今后研究的方向，即提供個性化的如分層反饋和利用日志進行反饋，并討論了相關反饋技術對檢索性能的影響。
關鍵詞：信息檢索； 相關反饋； 查詢擴展
中圖分類號：TP391 文獻標志碼：A
文章編號：10013695(2009)01001104
Survey on relevance feedback for information retrieval
YAN Huayun1，2， LIU Qiping1， XIAO Liangjun2
(1.School of Information Engineering， Huzhou Teachers College， Huzhou Zhejiang 313000， China; 2.College of Electronics Information Engineering， Tongji University， Shanghai 201804， China）
Abstract:This paper introduced relevance feedback mothod about vector space model， probability model and language model in information retrieval fields， elaborated how to regulate the weights of terms， expands query， relevance feedback of documents， regulate about the query language model and document language model. It also introduced how to adopt relevance feedback to improve information retrieval performance. It discussed the novel technology of feedback with term feedback technology.At last， discussed the problems ofthe future direction in relevance feedback， the personality of hierachical feedback and the feedback of using log .
Key words：information retrieval; relevance feedback; query expansion
0 引言
經典信息檢索模型中包括布爾模型、向量空間模型、概率模型和語言模型。布爾模型出現在20世紀50年代，其查詢詞間以布爾表達式形式提交。這種方法實現簡單，但不易操作。其后出現了向量空間模型，它把文檔用向量表示，查詢同樣也看成文檔向量，通過計算查詢和文檔向量的相似性進行打分。1960年Maron和Kuhns又提出了概率檢索模型[1]，把文檔的相關性理解為一種概率事件，通過查詢詞在相關文檔和不相關文檔的百分比進行打分。語言模型于1998年由Ponte和Croft提出[2]，其主要思想是把相關度看成每篇文檔對應語言下生成該查詢的可能性，從而根據相關度進行打分。這四種模型進行檢索時主要存在的問題是用戶需求本身模糊[3] 、不熟悉檢索環境[4]等，從而導致信息檢索的研究與實踐中一直存在的主要不足是系統的準確率和召回率不夠高[5] 。為了使檢索系統更加有效，使檢索結果更好地滿足用戶的查詢請求，出現了反饋技術[6] 。
文獻[1]含有最初的反饋思想雛形，正式的反饋思想出現在著名向量空間模型系統SMART中[7]。
信息檢索系統中根據反饋的用戶是否真正參與分為兩類反饋技術：
a)偽相關反饋機制。系統默認自己檢索出的結果中含有大量相關的文檔，從中取出前N篇作為相關文檔，對查詢進行調整或擴展。
b)用戶參與的反饋機制。系統檢索出初始結果后，提交給用戶由用戶判斷文檔是否相關，從而進行調整和查詢。
由于在布爾模型的基礎上進行反饋的研究很少，本文就不討論布爾模型的反饋。
1 向量空間模型中的反饋
向量空間模型把文檔和查詢都看成是詞組成的向量，通過計算兩個向量的cosine值來表示兩個向量之間的相似度。向量空間模型中的反饋主要就是通過對檢索結果的相關性判定，重新調整查詢向量。
向量長度；N是假定的文獻集大??；n是文獻集中相關文獻的大小；R是相關文獻的集合；R是不相關文獻的集合。
實際應用中，在對初始檢索結果的相關判定之后，式（1）就可以形成有效的相關反饋。
Rocchio提出了一個近似公式，即向原始的查詢表達式中加入相關文獻中相關的檢索詞，同時從查詢中去除不相關文獻中出現的檢索詞。其近似式如下：
其中:Qi+1為修改后的查詢向量；Qi為原有查詢向量；R和R的意義同上；α、β以及γ是用于調整的三個常量，β部分用于正反饋，γ部分用于負反饋，α、β、γ的取值比率決定了在調整檢索詞的權重時原先的查詢、相關文獻、不相關文獻之間的相對重要性。幾種常用取值方法：α=β=γ=1或α=β=1，γ=0。在原始的Rocchio公式中隱藏著一個基本的假設，即已知的不相關文獻代表了所有的不相關文獻。Rocchio后來把R的范圍擴大為不被用戶判斷為相關文檔的都是不相關文檔。
Ide[8]后來對式（2）作了兩種修改，其形式如下：
公式中的γ沒有為查詢表達式加入任何檢索詞，其作用僅僅是減少某些從不相關文獻中擴展的檢索詞的權重，γ可能會使某些檢索詞的權重為負數，但權重為負數的檢索詞將從查詢表達式中剔除。
在向量權重的調整策略方面，式（2）~（4）是有差異的：式（2）采用的是標準化因子方法；式（3）則是將所有相關文獻和不相關文獻的實際向量權重加入到查詢表達式來完成的；式（4）采用的是直接向查詢表達式加入所有相關文獻向量的實際權重以及一篇最不相關文獻向量的實際權重的方法實現的。
在很多情況下，用戶并未給出不相關的文檔。一種辦法是把用戶選定的第一個相關文檔前的文檔都當做不相關文檔，這種情況要求用戶的閱讀習慣是從第一個到最后一個；否則可能會把相關文檔當做不相關文檔進行處理。另外一種方法就是干脆不考慮不相關文檔。
Aalbersberg[9]提出了一種增量的反饋方法：每步檢索只選出一篇文檔，由用戶判定其相關性。因為這種情況下，式（2）~（4）是一致的：經過多次迭代，產生最后的查詢。
對用戶而言，他們最希望系統能夠自動產生結果，而不是需要他們的參與，因此偽相關反饋的算法更加重要。最簡單的偽相關反饋算法就是假定初始檢索結果的前N篇文檔與查詢相關，然后按照不考慮不相關文檔的方式進行擴展。但這樣做不可避免地會把一些不相關的文檔當做相關文檔進行處理，同時也會把一些相關文檔當做不相關文檔。
Iwayama[10]認為在初始結果的文檔集中，相關文檔相似度是較高的，而不相關文檔是相對松散的，在這個假定的基礎上提出了一種先聚類、后反饋的方法。首先對初始結果的前N（N一般取20~30）篇文檔進行聚類；然后將每一類文檔的相似度相加，在相似度和最高的一類中取出前K篇文檔進行反饋。在此基礎之上，他還提出了一個改進的方法：在聚類之前，每篇文檔要加上初始查詢。
Amo等人[11]認為，對初始查詢的前N篇文檔作同樣的處理可能會導致一部分信息的損失，即初始查詢中相關度的排序關系沒有利用。他們提出了利用平滑函數來對不同排位的文檔進行加權。按照隨序數遞增權重遞減以及所有權重相加等于1這兩個原則，設計了幾個平滑函數，這樣排在前面的文檔就能在反饋中發揮更大的作用。
Rocchio方法及Ide的這兩個方法都有問題，即在擴展時將相關文檔向量直接與原查詢合并，這樣勢必會引起特征過多、計算量過大，同時某些相關文檔中偶然出現的與查詢無關的詞也將引入新的查詢。因此在多數情況下，要對擴展的特征進行選擇，一個比較通用也較簡單的方法是把相關文檔中權重較高的詞取出，而將權重較低的部分舍棄，這樣能有效地降低向量的維數，并且對性能沒有太大損害甚至有所提高。另外的方法包括進行潛層語義索引（LSI）[12]。
LSI的目的是希望減小一詞多意和一意多詞對信息檢索的負面影響，去掉那些對文檔區低，近似的詞項被合并，同義詞在k維空間中有相似的表示，LSI相當于構造了新的語義空間，具備概念檢索的特征。
2 概率模型中的反饋
概率模型包括回歸模型和二元獨立模型（BIM）。由于回歸模型中目前沒有研究反饋的資料，以下講的概率模型的反饋都是針對BIM模型進行的。
概率檢索模型是通過概率的方法將查詢與文檔聯系起來的一種模型[13]。經典的概率模型是1976 年Robertson等人[14]提出的二元獨立模型（BIM）。該模型存在兩個基本假設，即文獻集中檢索詞之間的分布是相互獨立的和二元屬性取值假設(即文檔D可以表示為D(x1，x2，…，xn)。其中二元隨機變量xi表示檢索詞ti是否在D中出現。如果出現則取值為1；否則為0)。
概率模型不同于向量空間模型，它考慮的是檢索詞在相關文獻、不相關文獻中的概率分布，不考慮對查詢詞進行修改。用戶對檢出文獻進行相關性判斷，系統利用該反饋信息，根據每個檢索詞在相關和不相關文獻集中的分布情況來修改其相關概率，從而計算出各自的權重，并根據包含在每篇文獻中與查詢表達式中匹配的檢索詞的相關權重計算出文獻的權值，據此對文獻進行排序輸出。
2.1 BIM模型中反饋簡介
概率模型中相關反饋的基本過程如下：
a)給定一個初始的查詢，運行查詢后，用戶判斷出相關文獻和不相關文獻。
b)對于在相關和不相關文獻中包含的每個檢索詞ti，分別計算ti在相關和不相關文獻中的出現概率pi和ui。對ti可以用下式計算它的相關權重：
c)對于集合中的每一篇文獻D，計算文獻相關度因子g(D)=log (Pr(D｜rel)/Pr(D｜non rel))。其中：Pr(D｜rel)表示文獻向量D出現在相關文獻集中的概率；Pr(D｜non rel) 表示文獻向量D出現在不相關文獻集中的概率，可用它所包含的與查詢中檢索詞匹配的檢索詞權值之和來計算。
d)根據函數g(D)遞減進行排列，得到相關文獻集。
在概念模型中的兩個假設下，BIM中文檔D(x1，x2，…，xn)與查詢Q的相似度可采用下式來進行度量：
sim(D，Q)=∑ni=1xi log [pi(1-ui)/ui(1-pi)]+Δ
（5）
其中:Δ是一個常數；ti表示檢索詞；pi表示ti在相關文獻中的出現概率；ui表示ti在不相關文獻中的出現概率。假定每個ti的pi是一個常數，而在不相關文檔中的分布與整個文檔集中的分布近似相等，N是文檔集的大小，ni是文檔集中ti出現的文檔數，則由式（5）可以得到
sim (D，Q)=∑ni=1xi log [(N-ni)/ni]+Δ
(6)
在反饋時，可以假設term在相關文檔中的分布與在所有相關文檔中的分布一樣，所有未被檢索出的文檔都可以看做不相關文檔。根據這兩個假設，新的Pi和ui變為pi=ri/R，ui=(ni-ri)/（N-R）。這里有一個問題：如果某個term出現的頻率較低， ri有可能為0，因此需要進行平滑。一般情況下調整因子是0.5，pi和ui就變為pi=(ri+0.5)/（R+1），ui=(ni-ri+0.5)/（N-R+1）。如果檢索結果中沒有相關文檔，則每個term的pi就與它在整個文檔中的分布一致，即ni/N。因此可以將調整因子改為ni/N，則Pi和ui就變為pi=(ri+ni/N)/（R+1），ui=(ni-ri+ni/N)/（N-R+1）。
概率模型中的反饋有一個特點：新的查詢詞與舊查詢詞無關，但原始查詢中的詞應當占有更重要的地位。對于原始查詢中的詞，可以給予適當的加權調整。這種方式可以得到更高的檢索效率。
2.2 概率模型中查詢詞修改問題
由于經典的概率模型不具有向量空間模型具有的查詢詞擴展的功能，很多學者圍繞這一問題展開了研究。
Harper等人[15]提出了一種利用MST(最大生成樹)算法對查詢詞進行擴展的方法。
Crestani[16，17]提出了一種神經網絡的檢索模型，將所有的文檔和查詢進行處理后生成一個知識表示矩陣，然后利用這個知識表示矩陣生成相關文檔列表。
2.3 概率模型反饋的優缺點
由于真實情況下，對于每個查詢無法事先得到相關文檔集和不相關文檔集，無法使用理想情況下的公式計算，必須進行估計。通常根據以前檢索的結果進行估計，可以在估計出pi和ui的基礎上進行相關度計算。與基于向量空間模型中的相關反饋方法相比，基于BIM的相關反饋的優勢是：
a)反饋直接與檢索詞在相關文獻、不相關文獻中出現的概率聯系。
b)文獻相似度函數的表達式隨著與文獻匹配的查詢表達式中每個檢索詞ti的權重因子Wi的增加而增加，并且在檢索詞獨立假設和二元屬性取值假設的情況下，其權值調整是最理想的。
在概率模型的相關反饋中也存在大量有用信息被忽視的情形，例如：
a)BIM中沒有考慮各個檢索詞的重要性，也沒有考慮初始檢索詞。
b)從因子Wi的表示來看，其實質相當于只是考慮了IDF，而沒有考慮TF。
例如，當ti在相關文獻和不相關文獻中所占的比率分別為pi=0.1和ui=0.01，則ti的權重為11；當ti在相關文獻和不相關文獻中所占的比率分別變為pi=0.01和ui=0.001時，ti的權重就變為約10.1?？梢姡敊z索詞在相關文獻和不相關文獻中所保持的比例不變的話，該檢索詞在文獻中的權重就基本上沒什么變化。但從剛才的舉例來看，前一種情況顯然更相關，這不是愿意看到的結果。
考慮到上述因素，Ponte等人[2]提出了流行的OKAPI概率式，它是Wi的進一步優化。其形式如下：
∑t∈q∩ d{ln (N-n+0.5)/（n+0.5）×(k1+1)×c(t，d)/[k1×((1-b)+b×｜d｜/avdl) +c(t，d)]×(k3+1)×c(t，q)/[k3+c(t，q)]}（7）
其中：k1、k3和b都是經驗參數，可以自己進行調整，如在著名的lemur工具中就有此功能；N是文檔總數；n為與檢索詞t相關的文檔總數；c(t，d)表示檢索詞t在文檔中出現的次數；c(t，q)是檢索詞在查詢中的出現次數。從中可以看出，式（7）與向量空間模型一樣綜合考慮了IDF和TF，同時還通過參數b對文檔的長度進行了歸一化。
向量空間模型與BIM相比，Croft認為BIM模型優于向量空間模型，Salton認為向量空間模型強于BIM模型?，F在兩者的思想逐漸融合，其性能表現相當。
3 語言模型中的反饋
語言模型[2]是1998年由Croft等人提出的。語言模型來自于基于統計方法的自然語言處理系統的研究中，如語音識別、機器翻譯、中文分詞和字符識別等。
3.1 語言模型分類
常用的語言模型有查詢似然模型、翻譯模型和KL距離模型。
查詢似然模型把相關度看成是每篇文檔對應的語言下生成該查詢的可能性；翻譯模型假設查詢經過某個噪聲信道變形成某篇文章，則由文檔還原成該查詢的概率(翻譯模型)可以視為相關度，這種模型研究得比較少；而KL距離模型是將查詢對應某種語言，每篇文檔對應某種語言，查詢語言和文檔語言的KL距離作為相關度度量。
3.2 語言模型中的反饋簡介
BIM計算查詢詞的相關和不相關百分比進行反饋，但是這種做法只能依賴人們的經驗，缺乏必要的理論依據。
語言模型則可以通過對反饋回來的文檔建立反饋模型MF，然后與原有查詢模型MQ或文檔模型MD相結合，生成新的查詢模型M′Q或文檔模型M′D，再查詢、排序，對反饋回來的文檔建模。經過多次循環，使最終的查詢模型或文檔模型趨于穩定。所以語言模型的反饋可以與查詢模型或文檔模型合并為一個模型。查詢模型和文檔模型的反饋如下：
M′Q=(1-α)MQ+αMF（8）
M′D=(1-α)MD+αMF（9）
其中：α為參數，表示兩個模型在新的模型中所占的百分比；MF的計算可通過生成式結合模型和最小化經驗分歧來實現。
通過式（8）（9）不斷地修正文檔模型和查詢模型，最后根據前面介紹的三種語言模型進行打分，從而對文檔進行排序返回。
4 反饋技術的新進展
前面介紹的三種模型的反饋都涉及一個問題，那就是當用戶要查詢的是稀少的主題時，通過反饋時很容易因為未被選進相關文檔而被過濾掉，從而造成用戶檢索不到。
現在有研究基于檢索詞terms的新的反饋方式，即不像以前只是基于文檔進行反饋。這種技術在反饋時先從初始檢索的結果集中選前N篇文檔進行terms提取，然后返回terms讓用戶進行判斷。
基于terms反饋技術由UIUC的Tan等人[18]提出。該方法在terms基礎上進行聚類形成一個個子主題簇（subtopic clusters），然后以子主題簇為單位返回terms由用戶進行判斷。這種反饋方式效果更好。
其過程是當用戶輸入初始檢索詞檢索得到初始結果集后，也要將結果集中的terms提取出來，過濾掉常用詞后將這些terms進行聚類，并將聚類生成的一個個子主題中的terms按其出現頻率的多少提交給用戶進行判斷。其反饋方式如下：
p(w｜θq′)=λp(w｜θq)+(1-λ)×
∑Ki=1[(∑Lj=1δti，j)/∑Kk=1∑Lj=1δtk，j] p(w｜θi)（10）
其中：∑Lj=1δti，j是通過聚類后第i簇的相關terms個數；∑Kk=1∑Lj=1δtk，j是所有簇中的相關terms個數；θq是初始查詢模型；θq′是修改后的查詢模型；θi是第i個簇模型，所有K個簇模型組成了文檔模型；(∑Lj=1δti，j)/∑Kk=1∑Lj=1δtk，j表示的是第j個簇模型在整個文檔模型中所占的比例。
文獻[18]中，通過修改式（10），再進一步利用KL距離模型來對文檔進行打分。
Tan的反饋方式的優點就是通過聚類從而可以有效地儲存稀少子主題的terms，其實驗證明這種反饋方式是有效的；其缺點就是這種方法要求用戶進行真實的反饋，而不是偽反饋，因而用戶操作起來稍微麻煩一些。
5 結束語
通過對以上經典檢索模型的相關反饋的分析不難發現，反饋具有以下主要優點：
a）簡單易用。布爾模型需要人工構建查詢表達式，要求用戶很專業，但反饋可以讓人在不很熟悉文獻集環境和查詢環境的情況下構建有效的查詢。
b）將查詢操作分解為一系列小的查詢步驟?？梢愿鶕z索出來的結果修正查詢詞和擴展查詢詞，以漸進的方式接近期望的目標。
c）用戶可以參與到構建查詢的過程中來，決定哪些查詢詞用做正反饋，哪些用于負反饋。
由于現有反饋方法都有其局限性，反饋還有其研究空間。以后的反饋技術應該更著眼于為用戶提供個性化的服務，而不是千人一面的通用性服務，因此，如何更有效地利用搜索引擎的日志數據應該是一個解決問題的方向，如分層次的反饋[19]、基于日志的反饋[20]等。
參考文獻：
［1］TAI Xiaoying， REN Fuji， KITA K. Longterm relevance feedback using simple PCA and linear transformation[C]//Proc of the 13th International Workshop on Database and Expert Systems Applications. 2002:261268.
[2]PONTE J， CROFT B. A language modeling approach to information retrieval[C]//Proc of ACM SIGIR’98. 1998:275281.
[3]RUTHVEN I， TOMBROS A， JOSE J. A study on the use of summaries and summarybased query expansion for a questionanswering task[C]//Proc of ECIR’01. 2001:4153.
[4]SALTON G， BUCKLEY C. Improving retrieval performance by relevance feedback[J]. Journal of the American Society for Information Science，1990，41(4):288297.
[5]LANCASTER F W. MEDLARS:report on the evaluation of its operating efficiency[J]. American Documentation，1969，20(2):119148.
[6]BUCKLEY C， SALTON G， ALLAN J. The effect of adding relevance information in a relevance feedback environment[C]//Proc of ACM SIGIR Conference on Research and Development in Information Retrieval. 1994:292300.
[7]ROCCHIO J J. Relevance feedback in information retrieval[M]//The smart systemexperiments in automatic document processing.[S.l.]: PrenticeHall，1971:313323.
[8]IDE E. New experiments in relevance feedback[M]//The smart systemexperiments in automatic document processing.[S.l.]: PrenticeHall， 1971:337354.
[9]AALBERSBERG I J. Incremental relevance feedback[C]//Proc of ACM SIGIR Conference on Research and Development in Information Retrieval. 1992:1122.
[10]IWAYAMA M. Relevance feedback with a small number of relevance judgements[C]//Proc of ACM SIGIR Conference on Research and Development in Information Retrieval. 2000:1016.
[11]AMO P， FERRERAS F L， CRUZ F，et al. Smoothing functions for automatic relevance feedback in information retrieval[C]//Proc ofthe 11th International Workshop on Database and Expert Systems Applications. 2000:115119.
[12]DEERWESTER S C， DUMAIS S T， LANDAUER T K，et al. Indexing by latent semantic analysis[J]. Journal of the American Society for Information Science，1990，41(6):391407.
[13]JONES K S，WALKER S， ROBERTSON S E. A probabilistic model of information retrieval:development and comparative experiments[J]. Information Processing and Management，2000，36(6):779808.
[14]ROBERTSON S E， SPARCK J K. Relevance weighting of search terms[J]. Journal of the American Society for Information Science，1976，27(3):129146.
[15]HARPER D J， Van RIJSBERGEN C J. An evaluation of feedback in document retrieval using cooccurrence data[J]. Journal of Documentation， 1978，34(3):189216.
[16]CRESTANI F. Domain knowledge acquisition for information retrieval using neural networks[J]. Journal of Applied Expert Systems， 1994，2(2):101116.
[17]CRESTANI F. Comparing neural and probabilistic relevance feedback in an interactive information retrieval system[C]//Proc of IEEE International Conference on Neural Networks. 1994:34263430.
[18]TAN Bin， VELIVELLI A，FANG Hui， et al. Term feedback for information retrieval with language models[C]//Proc of ACM SIGIR Conference on Research and Development in Information Retrieval. 2007:263270 .
[19]ZENG Huajun， HE Qicai， CHEN Zheng，et al. Learning to cluster Web search results[C]//Proc of ACM SIGIR Conference on Research and Development in Information Retrieval. 2004:210217.
[20]WANG Xuanhui， ZHAI Chengxiang. Learn from Web search logs to organize search results[C]//Proc of ACM SIGIR Conference on Research and Development in Information Retrieval. 2007:8794.
[21]ANICK P. Using terminological feedback for Web search refinement: a logbased study[C]//Proc of ACM SIGIR Conference on Research and Development in Informaion Retrieval. 2003:8895.
