周 博,岑榮偉,劉奕群,張 敏,金奕江,馬少平

(智能技術(shù)與系統(tǒng)國家重點實驗室,清華大學計算機科學與技術(shù)系,北京100084)

1 引言

怎樣根據(jù)用戶的反饋信息提高檢索系統(tǒng)的檢索性能,這個問題在研究界已經(jīng)有很多的相關(guān)工作。主流的工作可以被分為兩個方向：1)查詢擴展;2)檢索結(jié)果重排序。查詢擴展的思路是利用用戶反饋信息中的相關(guān)文檔,擴充用戶原始的查詢,從而使新的查詢能夠更好的描述用戶的意圖,再利用新的查詢進行信息檢索。文檔重排序則不需要進行二次檢索,只需要根據(jù)用戶的反饋信息將原始的檢索結(jié)果重新排序,排序算法會保證用戶所需的文檔被排在前列。

反饋這個問題有很多方面,其中首先需要明確的一條是反饋信息的來源。如果反饋信息直接來自于用戶標注的結(jié)果,則我們稱建立在這種反饋信息之上的技術(shù)為相關(guān)反饋技術(shù);如果反饋信息來源于搜索引擎前幾位的檢索結(jié)果,則建立在這種反饋信息之上的技術(shù)成為偽相關(guān)反饋技術(shù)(因為反饋信息并不是由用戶有意提供的)。近幾年來,有關(guān)偽相關(guān)反饋的研究越來越多,主要原因是在大規(guī)模信息檢索中很難由用戶直接提供反饋信息。

在TREC 2008上,相關(guān)反饋被作為一個獨立的任務(wù)集中研究如何根據(jù)反饋信息提高檢索性能,不同研究隊伍對相同的查詢主題,根據(jù)相同的反饋信息,通過不同的方法進行檢索性能的改進。

本文的方法是在已經(jīng)確定了反饋信息的情況下,根據(jù)反饋信息對初次檢索的結(jié)果進行重信排序。該方法主要基于反饋信息中的文檔與初次檢索結(jié)果中文檔之間的相似度距離,在利用反饋信息時,同時考慮反饋信息中的不相關(guān)文檔與相關(guān)文檔兩方面的因素。

2 相關(guān)工作

已經(jīng)有很多研究表明相關(guān)反饋是提升信息檢索性能的有效方法[1]。雖然有關(guān)相關(guān)反饋的研究可以追述到幾十年以前,但是研究界最近幾年仍然有不少有關(guān)相關(guān)反饋的工作[2-4]。主流的相關(guān)反饋方法可以分為兩種：第一,基于查詢擴展的方法;第二,基于搜索結(jié)果重排序的方法。本文關(guān)注的是第二種方法。

雖然在研究界相關(guān)反饋已經(jīng)可以在很大程度上提高檢索系統(tǒng)的性能,但是在實際的應用中,相關(guān)反饋卻有很大的局限性,在網(wǎng)絡(luò)搜索中這種局限性更加明顯。其中一部分原因是由于技術(shù)上的不足,例如無法準確地確定用戶一個查詢需求所對應的完整的查詢點擊序列,另一部分原因是因為用戶已經(jīng)習慣了手動改變查詢。

還有一些相關(guān)的方法是在將檢索系統(tǒng)返回的前幾位搜索結(jié)果作為用戶的反饋信息來進行查詢擴展,即偽相關(guān)反饋。而一些研究者認為：偽相關(guān)反饋的方法在大的文檔集合上的性能很不穩(wěn)定[5]?；趥蜗嚓P(guān)反饋的方法還有一個主要問題是將前多少位的返回文檔作為反饋信息[6-11]。但是事實證明這是很難確定的,如果窗口較小,則很少的相關(guān)文檔會落入窗口,如果窗口過大,則很多不相關(guān)文檔會進入窗口,從而影響性能的提升。

研究界也有提出許多基于檢索結(jié)果重排序的方法,文獻[8]提出了一種基于文檔所在的文檔重排序方法。文獻[8]中的方法是基于一個在整個文檔集合上的層次聚類結(jié)構(gòu),根據(jù)聚類結(jié)構(gòu)對文檔進行重排序。文獻[9]提出了根據(jù)文檔的標題信息進行重排序的方法。文獻[6]則是查詢中的詞對結(jié)果進行重排序。文獻[12-13]利用全局與局部信息對局部的上下文進行分析,利用分析后的結(jié)果對文檔進行重排序。文獻[14]利用手動構(gòu)建的同義詞庫對文檔進行重排序,其中利用同義詞庫中原始查詢的同義詞擴展原始查詢。文獻[7]則是通過賦值可控制詞典庫對搜索結(jié)果進行重排序。文獻[10-11]中則提出了同時利用查詢中與前幾位檢索結(jié)果中的 term進行重排序的方法。

3 基于文檔相似度的搜索結(jié)果重排序

基于假設(shè)：相關(guān)文檔與標注為相關(guān)文檔的相似度應該大于相關(guān)文檔與標注為不相關(guān)文檔的相似度,我們認為標注文檔與其他文檔間的相似度信息對于描述查詢與文檔間的相似度是有幫助的。在基于文檔相似度的相關(guān)反饋方法中,根據(jù)標注文檔與其他文檔的相關(guān)性,初始的搜索結(jié)果被重排序。所以這里涉及兩個基本的問題：第一,如何描述文檔之間的相關(guān)性;第二,如何根據(jù)文檔間的相關(guān)性對檢索結(jié)果進行重排序。

首先,我們來解決文檔相關(guān)性的問題。在本文中我們使用向量空間模型[2]來表示一篇文檔。在向量空間模型中,每篇文檔被表示為一個向量,向量的每一維是由這篇文檔中的term的特征構(gòu)成的。在這個模型的簡單表示形式中,每篇文檔可以被表示成為詞頻(Term Frequency,TF)向量：

其中t fi為文檔的第i個term在所在文檔中的詞頻。對于該模型的比較常用的改進方法是：對與每一個 term進行加權(quán),所加權(quán)值是倒序文檔頻度(Inverse Document Frequency,IDF)。這樣改進的目的是：如果一個term在很多文檔中均出現(xiàn)過,那么該term在文檔中的重要性就沒有那些僅在幾個文檔出現(xiàn)過的term高。所以這樣的term在表示一篇文檔的時候需要加以相應的懲罰因子。一般的做法是將t fi與log(N/d fi)相乘,其中N代表文檔集合中的所有文檔數(shù)目,d fi代表包含第i個term的文檔數(shù)目。這樣我們就得到了一篇文檔t f-id f的表示：

有了一篇文檔的向量表示,我們就可以利用各種距離來計算文檔之間的相關(guān)性。在多年的研究中有兩種距離經(jīng)常被用來計算兩篇文檔之間的相似度。第一種是余弦距離：

由于文檔的長度為1,公式可以簡化為cos(di,dj)=dj。當兩篇文檔相同的時候,該距離取值為1,當兩篇文檔完全不同的時候,該距離的取值為0。

另一種是歐氏距離：

當兩篇文檔完全相同的時候,該距離的取值為0;當兩篇文檔的完全不相同的時候,該距離的取值為。我們在本文中采用了余弦距離來衡量文檔之間的相關(guān)性。

在搜索結(jié)果重排序中我們需要考慮的因素有：搜索結(jié)果原始的評分值、搜索結(jié)果與標注為相關(guān)文檔的相關(guān)性、搜索結(jié)果與標注為不相關(guān)文檔的相關(guān)性、這幾個特征如何整合。搜索結(jié)果的原始評分值反映了用戶查詢與各個搜索結(jié)果之間相關(guān)性,體現(xiàn)了用戶的需求。搜索結(jié)果與標注為相關(guān)文檔的相關(guān)性越高,則該搜索結(jié)果就越有可能是用戶需要找的相關(guān)文檔,我們在重排序中就應該將這種文檔向前排。搜索結(jié)果與標注為不相關(guān)文檔的相關(guān)性越高,則該搜索結(jié)果就越不太可能是用戶所希望得到的文檔。所以我們希望重排序公式中可以體現(xiàn)出這些特征,將與正例文檔近而與負例文檔遠的文檔向前排。具體對一篇文檔的排序公式如下：

其中Dres表示原始搜索結(jié)果的文檔集合;Drel表示被標注為相關(guān)的文檔集合;Dnrel表示被標注為不相關(guān)的文檔集合,d is(di,dj)表示文檔di與文檔d j之間的余弦距離;最后一篇文檔與查詢相似度計算的公式如下：

從上述公式中我們可以看到：如果一篇文檔與被標注為相關(guān)的文檔近似,而與被標注為不相關(guān)的文檔差別較大,那么r fscore(di)的取值偏高;反之,如果一篇文檔與被標注為相關(guān)的文檔差別較大,而與被標注為不相關(guān)的文檔較近似,那么r fscore(di)的取值偏低。在計算score(di)時需要對r fscore(di)和sim(qk,di)這兩個不同量綱的值分別進行歸一化;在公式中有兩個控制因子,它們之間的關(guān)系是α+β=1。

sim(qk,di)表示文檔di與查詢qk相似度的評分,在本文中sim(qk,di)使用的是BM 2500檢索模型[15],BM 2500公式的定義如下：

其中Q表示查詢;tf表示一個查詢詞在某一篇文檔中的出現(xiàn)頻次;qt f表示查詢詞在所有Q的檢索結(jié)果集合中的出現(xiàn)頻次;d l與avd l分別表示文檔的長度和平均的文檔長度。權(quán)值W的計算方法如下：

其中N表示文檔的數(shù)量;n表示包含查詢詞的文檔數(shù)量;R表示與查詢詞相關(guān)的文檔數(shù)量;r表示相關(guān)文檔中包含查詢詞的文檔數(shù)量。

4 性能評測

4.1 評測集合

為了驗證本文中提出的搜索結(jié)果重排序方法,使用了TREC feedback任務(wù)制定的數(shù)據(jù)集合,該任務(wù)采用了前些年TREC中M illionQuery任務(wù)與Teraby te任務(wù)的數(shù)據(jù)集合,并根據(jù)查詢主題編號的奇偶制作了兩個評測查詢集合Even_Set與Odd_Set(各150個Topic)。為了測試不同規(guī)模的反饋信息對于重排序結(jié)果的影響,對于每一個Topic都有不同規(guī)模的反饋信息。其中B、C、D、E集合分別體現(xiàn)了反饋信息的多少,B集合中只有一篇被標注為相關(guān)的文檔,C集合中有3篇被標注為不相關(guān)的文檔,3篇被標注為相關(guān)的文檔,D中有10篇經(jīng)過標注的文檔,E集合中的被標注文檔數(shù)不定,但是平均值為246篇。需要注意的是B、C、D、E集合是超集的關(guān)系。表中給出了重排序之后MAP值的提高數(shù)值。

4.2 實驗結(jié)果及對比分析

首先給出的表1與表2是本文中的方法在兩個評測集合上對于MAP的提升。從表中我們可以發(fā)現(xiàn)隨著反饋信息的增加,M AP值的提高程度也逐漸的增加。這是比較容易理解的。

表1 MAP在Even_Set上的提升

表2 MAP在Odd_Set上的提升

為了橫向比較本文中的重排序方法較經(jīng)典查詢擴展方法在性能上的差異,我們采用了文獻[19]中的查詢擴展方法。該方法采用如下公式度量 term與查詢的同現(xiàn)程度：

其中t f(t,d)與 tf(qi,d)分別表示t與qi在文檔d中出現(xiàn)的頻次。我們用上述公式度量t與qi在集合S中同現(xiàn)的可能性。在整合多個查詢term的同現(xiàn)取值時,我們使用了下面的公式：

其中id f(t)的定義與第三節(jié)中介紹的相同,δ表示平滑因子。

基于文本相似度的重排序方法,目前在本文中給出的是TREC Relevance Feedback官方評測結(jié)果。表3則給出了基于查詢擴展方法的性能提升,用QE表示,其中QE-X代表不同的反饋信息規(guī)模。

表4 基于檢索結(jié)果重排序方法的評測結(jié)果

表4中列出了在280個官方Topic上,基于文本相似度的重排序方法對各種性能指標的提升,用RR表示,其中RR-X表示不同的反饋信息規(guī)模。

表5則給出了兩種方法的性能對比。表5中Imp+列表示針對左列性能指標的提升程度;表中的項標識為粗體,則表示在使用同樣規(guī)模的相關(guān)反饋信息時,本文中的方法性能優(yōu)于查詢擴展的方法。從表5的性能對比可以看出本文提出的方法在B與E上的性能明顯要好于查詢擴展的方法,這也說明在反饋信息很少(B只有一篇相關(guān)文檔)與反饋信息很多(E)的情況下本文的方法有明顯的優(yōu)勢。

從表5中我們還可以知道查詢擴展方法在D集合時的性能最好,而本文中提出的方法則在E上的性能最好,因此圖1中給出了在這兩種情況下不同Topic上的性能提升程度。從圖中我們可以看到本文的方法對于不同Topic有著很好的普適性。相較之下,查詢擴展的方法則比較依賴于具體的Topic,即在有些Topic上性能提升很多,在有些Topic上提升很少或者沒有提升。

圖1 在每個Topic上E2與平均水平對比的結(jié)果

表5 TREC官方對全部結(jié)果的評測結(jié)果

圖1中體現(xiàn)了基于文本相似度的重排序方法,在每個Topic上相較于Median Level(所有參賽隊在每個Topic上表現(xiàn)的平均值)。我們可以看到基于文本相似度的重排序方法在16個Topic上的表現(xiàn)明顯高于M edian Level,在14個Topic上的表現(xiàn)略低于Median Level。但是,從總體角度出發(fā),基于文本相似度的重排序方法的表現(xiàn)高于M edian Level。

5 結(jié)論

本文提出了一種基于文本相似度的重排序方法,該方法在相關(guān)反饋中可以有效地提高檢索系統(tǒng)的檢索性能。這種重排序方法綜合考慮了：原始檢索系統(tǒng)評分、與被標注為相關(guān)文檔的相關(guān)性、與被標注為不相關(guān)文檔的相關(guān)性三種特征。在大規(guī)模網(wǎng)絡(luò)信息檢索標準實驗數(shù)據(jù)上的實驗結(jié)果表明：該方法不僅可以穩(wěn)定的提高系統(tǒng)的檢索性能,并且相較于經(jīng)典的查詢擴展方法有著明顯的優(yōu)勢。

在未來的工作中,我們會嘗試將基于文本相似度的重排序方法與查詢擴展的方法結(jié)合起來。另外,選擇對什么樣的查詢做相關(guān)反饋,怎樣選擇反饋信息也是非常值得研究的問題。

[1] Jinxi,X.,W.B.Croft.Imp roving the effectiveness of information retrieval with local context analysis[J].ACM Trans.Inf.Syst.,2000,18(1)：79-112.

[2] Gerard,S..Automatic tex t processing：the transformation,analysis,and retrieval of in formation by computer[M].Addison-W esley Longman Publishing Co.,Inc.1989：78-99.

[3] Kamps,J..Improving Retrieval Effec tiveness by Reranking Documents Based on Contro lled Vocabu lary[C]//Proceedings o f the 21th European Con ference on In formation Retrieval,2004：283-295.

[4] Qu,Y.L.,G.W.Xu,etal..Rerank Method Based on Individual Thesaurus[C]//Proceedings of NTCIR2 Workshop,2000：79-112.

[5] Bodo,B.,Z.Justin.Questioning query expansion：an examination of behaviour and parameters[C]//Proceedings of the 15th Australasian database con ference-Volume 27.Dunedin,New Zealand,Australian Computer Society Inc.,2004：69-76.

[6] Carolyn,J.C.,B.C.Donald.Im proving the retrieval effectiveness o f very short queries[J].Inf.Process.M anage.2002,38(1)：1-36.

[7] Jones,K.S.,S.W alker.A p robabilistic model of information retrieval：development and comparative experiments[J].Inf.Process.Manage.2000,36(6)：779-808.

[8] Kyung Soon,L.,W.B.Cro ft,et al..A clusterbased resamp ling method for pseudo-relevance feedback[C]//Proceedings o f the 31stannual international ACM SIGIR conference on Research and development in information retrieval.Singapore,Singapore,ACM.2008：235-242.

[9] Lee,K.,Y.Park,etal..Document re-rankingmodel using clusters[J].Information Processing and Management,2001,37(1)：1-14.

[10] Xuanhui,W.,F.Hui,et al..A study of methods for negative relevance feedback[C]//Proceedings o f the 31st annual international ACM SIGIR conference on Research and development in information retrieval.Singapore,Singapore,ACM,2008：219-226.

[11] Yang,L.,D.Ji,et al..Document re-ranking based on automatically acquired key terms in Chinese in formation retrieval[C]//Proceedings of the 20th international conference on Computational Linguistics.Geneva,Sw itzerland,A ssociation for Computational Linguistics,2004：480-481.

[12] Guihong,C.,N.Jian-Yun,et al..Selec ting good expansion terms for pseudo-relevance feedback[C]//Proceedings of the 31st annual international ACM SIGIR conference on Research and development in information retrieval.Singapore,Singapore,ACM,2008：243-250.

[13] Jinxi,X.,W.B.Croft.Query expansion using local and global document ana lysis[C]//Proceedings of the 19th annual international ACM SIGIR conference on Research and development in information retrieval.Zurich,Switzerland,ACM,1996：4-11.

[14] Luk,R.W.P.,K.F.W ong.Pseudo-Relevance Feedback and Title Re-Ranking for Chinese IR[C]//Proceedings of NTCIRWorkshop 4,2004：315-326.

[15] S.E.Robertson,S.W alker,S.Jones et al..Okapi at TREC-3[C]//The Third Text Retrieval Conference(TREC-3),1995：109-126.