一種基于文檔相似度的檢索結(jié)果重排序方法

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

(智能技術(shù)與系統(tǒng)國(guó)家重點(diǎn)實(shí)驗(yàn)室,清華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系,北京100084)

1 引言

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

反饋這個(gè)問(wèn)題有很多方面,其中首先需要明確的一條是反饋信息的來(lái)源。如果反饋信息直接來(lái)自于用戶標(biāo)注的結(jié)果,則我們稱建立在這種反饋信息之上的技術(shù)為相關(guān)反饋技術(shù);如果反饋信息來(lái)源于搜索引擎前幾位的檢索結(jié)果,則建立在這種反饋信息之上的技術(shù)成為偽相關(guān)反饋技術(shù)(因?yàn)榉答佇畔⒉⒉皇怯捎脩粲幸馓峁┑?。近幾年來(lái),有關(guān)偽相關(guān)反饋的研究越來(lái)越多,主要原因是在大規(guī)模信息檢索中很難由用戶直接提供反饋信息。

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

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

2 相關(guān)工作

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

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

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

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

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

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

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

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

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

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

另一種是歐氏距離：

當(dāng)兩篇文檔完全相同的時(shí)候,該距離的取值為0;當(dāng)兩篇文檔的完全不相同的時(shí)候,該距離的取值為。我們?cè)诒疚闹胁捎昧擞嘞揖嚯x來(lái)衡量文檔之間的相關(guān)性。

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

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

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

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

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

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

4 性能評(píng)測(cè)

4.1 評(píng)測(cè)集合

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

4.2 實(shí)驗(yàn)結(jié)果及對(duì)比分析

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

表1 MAP在Even_Set上的提升

表2 MAP在Odd_Set上的提升

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

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

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

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

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

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

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

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

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

表5 TREC官方對(duì)全部結(jié)果的評(píng)測(cè)結(jié)果

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

5 結(jié)論

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

在未來(lái)的工作中,我們會(huì)嘗試將基于文本相似度的重排序方法與查詢擴(kuò)展的方法結(jié)合起來(lái)。另外,選擇對(duì)什么樣的查詢做相關(guān)反饋,怎樣選擇反饋信息也是非常值得研究的問(wè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.