宋 巍,張 宇,劉 挺,李 生
(哈爾濱工業(yè)大學信息檢索研究中心,黑龍江哈爾濱150001)
當前,通用搜索引擎主要基于關鍵詞匹配的方法進行檢索。存在的一個問題是:用戶查詢時輸入的有限詞語并不能完全準確表達其檢索的真正意圖,查詢本身存在的歧義性導致搜索引擎返回大量與用戶需求無關的文檔。另一方面,具有不同應用背景、偏好的用戶,在輸入相同的查詢詞時可能也有著各自不同的信息需求。因此,系統(tǒng)對輸入相同查詢關鍵詞的所有用戶返回同樣的結果不能使單個用戶滿意度達到最大。鑒于以上原因,結合用戶反饋的個性化檢索成為近年來學術界[1-2]研究的熱點。
用戶的反饋信息通常用來重構當前的查詢,以使新的查詢模型與用戶檢索意圖更為接近。按照反饋方式的不同,用戶反饋可分為顯式反饋和隱式反饋兩種。顯式反饋指用戶主動向系統(tǒng)提供自己的興趣偏好或對系統(tǒng)返回的結果進行相關性評價。隱式反饋指通過分析用戶與系統(tǒng)正常的交互行為來推測用戶檢索意圖,不需用戶做額外的相關性評價。由于用戶通常不愿花費精力進行主動反饋,隱式反饋成為個性化信息檢索研究的重點。
用戶的檢索歷史是隱式反饋信息最主要的來源之一,通常包括查詢輸入、結果集、用戶點擊等,含有用戶多方面的偏好信息,同時也存在大量噪聲。以往的方法將用戶檢索歷史當成一個整體考慮,或者將其視為歷史單元的融合,利用其中的所有詞來重構查詢模型。但是,檢索歷史中并非所有詞語都與當前查詢相關,這種方法自然會導致新的查詢模型中包含與當前查詢無關的噪聲詞,影響最終的檢索性能。
本文認為與當前查詢相關的詞語和查詢中的詞語在檢索歷史中經常共現(xiàn)。詞語的上下文指在它周圍一定大小的文本窗口內出現(xiàn)的所有文本。兩個詞語共現(xiàn)指它們出現(xiàn)在同一上下文內。我們以檢索結果的網頁摘要(snippet)作為上下文,結合用戶點擊對詞語的共現(xiàn)關系進行建模,考慮檢索歷史中的候選詞語與當前查詢中的所有詞語的共現(xiàn)關系,進而選擇與整個查詢相似度最高的候選詞作為擴展詞語。通過對檢索結果重排序的實驗證明,該方法可以有效地從用戶歷史檢索中挖掘出與查詢相關的詞語,減少噪聲詞,提高排序質量。
本文第2節(jié)介紹基于用戶檢索歷史的個性化研究相關工作;第3節(jié)敘述基于檢索歷史上下文的查詢重構方法;第4節(jié)和第5節(jié)分別介紹實驗的設置及實驗結果分析;第6節(jié)做出結論,并對下一步的研究工作進行展望。
挖掘檢索歷史的方法可分為基于短期歷史和長期歷史兩種。短期歷史針對單個的查詢會話(query session)中用戶的反饋來修正查詢模型[3-5]。這類方法優(yōu)點是反饋直接針對當前查詢,噪聲較少,缺點是可獲得的信息有限。與之相比,基于長期歷史的方法則以用戶為中心,收集從不同來源獲取的用戶信息,建立長期用戶模型對當前查詢模型進行重構。Sugiyam a K等[6]以時間為主軸劃分用戶的瀏覽信息為長期反饋、近期反饋和當前反饋進行線性融合作為查詢模型。類似的還有基于用戶桌面索引[7]和領域本體[8]的方法。這類方法優(yōu)點是無需進行查詢會話劃分,能夠全面刻畫用戶興趣。缺點是長期歷史包含多個主題,存在大量噪聲。從中發(fā)現(xiàn)與當前查詢相關的信息,利用這些信息預測用戶的檢索意圖是高效利用長期歷史進行個性化檢索的關鍵。
Bin Tan等[9]將用戶檢索歷史以查詢?yōu)閱挝粯嫿ㄈ舾蓺v史單元,計算當前查詢與歷史單元的相似度作為權值對歷史單元進行線性插值形成用戶歷史模型。其目的是賦予與當前查詢相似度高的歷史單元中的詞語更高的權值,降低了不相關單元對最終查詢模型的影響。然而計算查詢之間的相似度本身是很難的任務,因為查詢較短反映的信息有限,若使用返回的結果集對查詢進行擴充則依賴于初始返回的結果,若其中包含很多不相關文檔,計算出的相似度與實際情況會有較大偏差。此外該方法使用檢索歷史中出現(xiàn)的所有詞語建模,用戶檢索歷史中的一些詞語與查詢并不相關,但由于出現(xiàn)次數(shù)較多也會獲得較高的權值形成噪聲。Jing Bai等[3]利用查詢的上下文及查詢內的詞語間關系從相關的興趣領域中挖掘與當前查詢相關的詞語重構查詢模型。本文與其思想類似,不同的是本文針對用戶的檢索歷史進行挖掘并對用戶反饋進行建模,在選擇相關詞語的過程中考慮了用戶的個性化信息。
與本文相關工作還包括基于偽相關反饋的查詢擴展[10-11]。這類方法假設初次檢索排序靠前的文檔或段落與查詢相關,并從中選擇詞語擴展查詢。其問題是過于依賴于系統(tǒng)初次檢索的質量。已有學者嘗試個性化查詢擴展方法。Paul A lexandru Chirita等[12]從用戶個人桌面文檔中選擇詞語擴展到查詢模型中。梅翔等[13]將用戶對網頁的偏好轉化為對知識庫中詞語的偏好,建立用戶興趣模型挑選出與用戶偏好關聯(lián)最緊密的關鍵詞加入原查詢。
檢索歷史包含不同的主題,其中多數(shù)與當前查詢無關。同時,一篇文章中僅有部分詞語能夠反映其主題,其余詞語起輔助作用。檢索歷史中與當前查詢無關的詞語形成噪聲,其來源可分為兩類:一類為不相關主題中的詞語,另一類為在各種主題中廣泛存在的起輔助作用的詞語,隨著檢索歷史不斷增加,此類噪聲不斷累積。
本文以用戶當前查詢?yōu)橹行?基于相關詞語在檢索歷史上下文中的共現(xiàn)及用戶點擊信息,選擇檢索歷史中與當前查詢最相關的詞語重構查詢模型。設當前查詢?yōu)镼={qi},其中qi是查詢關鍵詞。在用戶檢索歷史中,每個歷史查詢可對應一組信息,這些信息可用一個元組<查詢輸入,結果集,點擊頁面>來表示,結果集包括返回結果中所有網頁的標題、摘要以及正文鏈接。查詢模型重構過程如下:
1)將用戶檢索歷史中的網頁摘要進行索引,用當前查詢從中檢索,得到相關的歷史查詢網頁摘要并提取其中的詞語形成候選詞語集。
2)選取候選詞語的一個子集來重構查詢模型,稱該子集中的詞語為擴展詞語。以網頁摘要作為上下文語境,計算每個候選詞語與當前整個查詢的相似度并依此對候選詞語進行排序,選取前k個候選詞語作為擴展詞語。
3)利用得到的擴展詞語重構查詢模型。
最后,利用新的查詢模型對初始的檢索結果進行重排序。具體處理過程如圖1所示。
圖1 查詢模型重構過程
候選詞語應與當前查詢中的詞語在檢索歷史中經常共現(xiàn)。我們將用戶的檢索歷史以網頁摘要為單位(即將一個網頁摘要作為一個獨立文檔)進行索引,以當前查詢作為關鍵詞集合(去除其中的停用詞),檢索索引的歷史查詢網頁摘要,然后選用排序靠前的n個網頁摘要,從中提取所包含的詞語形成候選詞語集。索引時網頁摘要按照TF-IDF進行建模。當前查詢按照公式(1)估計權值。
其中,t為查詢中的一個詞語,t f(t,Q)表示t在查詢Q中出現(xiàn)的次數(shù)。d f(t)為包含t的網頁摘要數(shù),N為網頁摘要總數(shù)。
本文利用詞語在檢索歷史上下文內的共現(xiàn)并結合用戶點擊作為隱式反饋,來選取擴展詞語。首先,考察候選詞語與查詢中單個詞語的共現(xiàn)關系,在此基礎之上計算其與整個查詢的相似度,最終選取與整個查詢相似度最大的k個候選詞語作為擴展詞語重構查詢模型。
在用戶的檢索歷史中,對應某個查詢,系統(tǒng)返回的結果中可能包含多個主題,其中只有部分主題的網頁文檔真正滿足用戶的信息需求。利用詞語在上下文共現(xiàn)來提取相關詞語時,選擇的文本窗口過大會引入很多與當前查詢并無關系的噪聲詞語。因此,我們將檢索歷史中搜索引擎給出的網頁摘要作為度量詞語共現(xiàn)的上下文。一個網頁摘要是相對較小的文本窗口而且主題一致。以網頁摘要作為上下文能夠更好地估計詞語間的共現(xiàn)關系,同時易于結合用戶反饋。
3.2.1 詞語間共現(xiàn)度
首先,考察候選詞語與查詢中單個詞語的共現(xiàn)關系。采取共現(xiàn)度[11]來度量兩個詞語共現(xiàn)程度,其基本計算公式如(2)所示。
sj為排序在前n位的網頁摘要。tf(c,sj)表示詞語c在sj中出現(xiàn)的次數(shù),t f(qi,sj)表示詞語qi在sj中出現(xiàn)的次數(shù)。id f(c)為詞語c在整個數(shù)據(jù)集上的逆文檔數(shù),以降低高頻詞語的權值。co(c,qi)用來度量詞語c與qi在前n個網頁摘要中的共現(xiàn)次數(shù)。顯然,兩個詞語共同出現(xiàn)的網頁摘要數(shù)越多co(c,qi)的值越大。
3.2.2 結合用戶點擊的共現(xiàn)度
公式(3)僅對詞語共現(xiàn)進行統(tǒng)計而沒有考慮網頁摘要的質量,也沒有結合用戶的反饋。在個性化檢索中,用戶的反饋信息對于預測其真正的檢索意圖起著重要的作用。我們將公式(3)進行修改以實現(xiàn)對用戶隱式反饋與詞語共現(xiàn)的統(tǒng)一建模,如公式(4)所示。
quality(sj)用來衡量網頁摘要sj的質量,本文利用用戶點擊來估計。如果用戶曾經點擊過 sj,quality(sj)設為1,否則設為可調系數(shù)μ。μ約束了詞語權值估計時用戶反饋的重要性。當 μ=1時未點擊的網頁摘要與點擊的網頁摘要重要性相同,此時等同于沒有考慮用戶點擊信息,公式(3)即為μ=1時的特殊情況。μ=0時表示僅統(tǒng)計候選詞語與查詢中詞語在用戶點擊過的網頁摘要中的共現(xiàn)情況。0<μ<1時表示考慮所有網頁摘要,但未被點擊的網頁摘要的重要性按比例衰減,從而突出用戶點擊過的網頁摘要的重要性。因此,結合用戶反饋的共現(xiàn)度在衡量詞語間共現(xiàn)關系的同時結合用戶反饋,估計候選詞語的權值時既考慮其與查詢在統(tǒng)計上的相關性,又考慮了其與用戶偏好的相關性。
3.2.3 擴展詞語選擇
擴展的詞語應與用戶輸入的整個查詢相關而不是僅與其中的某個詞語相關。我們在計算候選詞語與查詢中單個詞語的共現(xiàn)度的基礎上,度量其與整個查詢的相似度,進而根據(jù)相似度的大小對候選詞語進行排序,從中選擇擴展詞語。通過公式(6)計算候選詞語c與查詢Q的相似性。
co_degree(c,qi)為c與查詢中詞語qi的共現(xiàn)度。w(c,Q)通過連乘的方式考察了候選詞語c與查詢中所有詞語的共現(xiàn)度進而表現(xiàn)其與整個查詢的相似度。其中δ設為0.1以避免乘積為零。
查詢中可能包含多個詞語,這些詞語不應等同對待,區(qū)分性強的詞語應當具有更高的重要性。相應地,與查詢中重要的詞語共現(xiàn)度大的候選詞語也應當被賦予較高的權值,從而進一步減少噪聲。這里的imp(qi)代表查詢中詞語qi的相對重要性。采取類似于逆文檔數(shù)(IDF)的思想,將Google索引的網頁視為大規(guī)模語料庫,利用詞語在Google的返回結果數(shù)(Google H its)來評價查詢中詞語的相對重要性,這里假設Google Hits小的詞語具有更大的相對重要性。設ghs(qi)為詞語qi的Google H its,im p(qi)的計算公式如公式(7)所示。
按照w(c,Q)對候選詞語進行排序,最終選擇前k個詞語作為擴展詞語重構查詢模型。
查詢模型重構包括兩個步驟:確定用來重構查詢的詞語集合和估計詞語權值。經候選詞語排序,得到k個擴展詞語,將其表示為 Ck={c1,c2,…,ck}。重構查詢模型使用的詞語集合為Q∪Ck。對于qi,按照公式(1)進行權值估計。使用w(ci,Q)作為ci的權值。
我們對初始檢索結果集合中每個文檔的網頁摘要(包括標題)按照空間向量模型進行建模,計算每個網頁摘要模型與重構的新查詢模型間的余弦相似度,并依此對初始檢索結果實現(xiàn)重排序。
針對個性化信息檢索,開發(fā)了基于天網100G語料的個性化評測語料標注輔助系統(tǒng)[14]。標注者利用此系統(tǒng)模擬正常的檢索行為,系統(tǒng)記錄下用戶在檢索過程中的各種隱式信息,包括查詢、檢索結果、用戶查看的網頁等。針對每個查詢,標注者對系統(tǒng)返回的前二十個網頁判斷是否符合其檢索意圖,符合標注為相關,否則標記為不相關。
收集了5名用戶的標注結果。平均每人進行了230余次檢索。從每名用戶的歷史查詢中,按照檢索時間由后向前的順序,選擇了一系列查詢用于測試。這些查詢要求同時滿足以下2個約束:
1)至少有2個或2個以上相關文檔。
2)至少符合用戶之前提交的查詢表達的興趣,如:科技、電影等,或者屬于某個查詢片段(用戶為了達到查詢目的提交的一系列查詢)。
對每一用戶,測試查詢與查詢總數(shù)的比例在10%~20%之間。數(shù)據(jù)集的統(tǒng)計如表1所示。
表1 數(shù)據(jù)集統(tǒng)計
采取p@5和Norm alized Discounted CumulativeGain(NDCG)作為評價方法,對所有測試查詢取平均值來評價系統(tǒng)的表現(xiàn)。其中p@5方法表示結果集的前5篇文檔中相關文檔比例。DCG[15]賦予排序高的文檔以更高權值并且結合不同的反饋級別(高度相關、相關和不相關),如公式(8)所示。
本文對于相關文檔令G(i)=1,對于不相關文檔令G(i)=0。NDCG是通過將DCG與理想狀況下(所有相關文檔排在結果集合的最前面)的DCG值(IDCG)做比值獲得,其值處于 0、1之間,越高說明系統(tǒng)表現(xiàn)越好。
實驗部分著重比較與分析以下3個方面:1)選取的擴展詞語數(shù)對系統(tǒng)的影響。2)用戶點擊對系統(tǒng)的作用。3)本文的查詢重構方法與以往基于檢索歷史重構查詢的方法的比較。選擇的基準系統(tǒng)包括:基于Lucene實現(xiàn)的默認檢索系統(tǒng),記為Default;將用戶的檢索歷史中所有點擊過的網頁摘要基于TFIDF建模并取質心構建用戶模型,記為Whole;采取Bin Tan等[9]的思想實現(xiàn)的對比系統(tǒng)BinTan。Bin-Tan將每個查詢形成歷史單元模型,通過計算當前查詢與所有歷史單元模型的相似度作為插值系數(shù)對所有歷史單元進行線性插值形成歷史模型。最終由當前查詢模型和歷史模型融合得到重構的查詢模型,并利用該模型對結果集合進行重排序。本文基于檢索歷史上下文分析的個性化查詢重構方法記為PQR。
PQR需要設置的參數(shù)為選取網頁摘要的數(shù)目n、擴展詞語數(shù)目k及系數(shù)μ。這里設定n=30,以保證返回的網頁摘要的相關性。分別考察 k=10,20,…,100及μ在0、1間不同取值時系統(tǒng)的表現(xiàn)。參數(shù)k反映了擴展詞語的精度,參數(shù)μ體現(xiàn)了用戶點擊對系統(tǒng)的影響。
圖2 在不同k值及μ值下PQR的表現(xiàn)
圖2給出了μ取不同值時,PQR隨擴展詞語數(shù)k變化的趨勢。當使用p@5評價時,系統(tǒng)的表現(xiàn)對k的變化較為敏感。在開始階段隨k的增大表現(xiàn)提高,當k達到30左右時系統(tǒng)表現(xiàn)最優(yōu),而后隨著k值增大而下降直至趨于穩(wěn)定,說明需要小心地設置參數(shù)k以使相關文檔盡可能排到結果集合前列。使用NDCG評價時,系統(tǒng)表現(xiàn)隨k變化相對平穩(wěn),說明重構的查詢模型能夠可靠地提高整個結果集中相關文檔的排名。
我們發(fā)現(xiàn)當μ值較小時,系統(tǒng)的表現(xiàn)更優(yōu)。如3.2.2所述,μ反映了用戶反饋的重要性,當其較小時系統(tǒng)賦予用戶點擊過的網頁摘要相對更高的權重。可見用戶點擊是可靠且有效的隱式反饋,利用用戶點擊過的網頁摘要可以更好地獲得符合用戶需求的相關詞語。
表2給出了針對2個查詢樣例,μ分別取0和1時PQR得到的擴展詞語中及BinTan歷史模型中權值最高的前10個詞語?!白匀徽Z言發(fā)展”是一個具有歧義的查詢,既可能指人類語言的演化也可能指計算機科學中的自然語言處理技術。當μ=1(所有網絡摘要的重要性相同)時,得到的擴展詞語涉及多方面的內容,不能完全準確預測用戶意圖。當μ=0(僅考慮用戶點擊過的網頁摘要中的詞語)時,擴展的詞語可以判斷用戶關注的是自然語言處理、信息檢索相關的內容。但對于一些情況,擴展詞語過于具體會使用戶局限在已有的偏好內。
表2 排序前十位的擴展詞語舉例
如查詢“推薦科幻電影”,當μ=0時,得到的擴展詞語會使系統(tǒng)傾向于將用戶過去檢索過的對象,如《第五元素》和《侏羅紀公園》等影片相關的網頁排在前面。μ=1時,擴展詞語中包含了一般化的相關詞語,如“科幻片”、“主演”等,這有助于用戶找到新的潛在感興趣的對象。因此設置合適的系數(shù)μ,既強調用戶點擊的重要性又增加一般的相關詞語來重構查詢是更好的選擇。由圖2可見,μ=0.2時系統(tǒng)表現(xiàn)較好。BinTan得到的歷史模型中,權值最高的詞多為在多個主題下經常出現(xiàn)的詞,如:“網”,“中國”,“下載”等。說明針對在各種主題中廣泛存在的噪聲詞語,BinTan去噪能力有限。隨著用戶檢索歷史增加,此類噪聲不斷積累,使用戶歷史模型準確描述用戶興趣的能力逐漸降低。
表3給出了k=30,μ=0.2時PQR與基準系統(tǒng)的比較。從中可以發(fā)現(xiàn),將用戶的檢索歷史視為一個整體建模(Whole)時系統(tǒng)的性能反而下降。這說明對于個性化檢索任務來說,將檢索歷史視為整體而不區(qū)分其中信息是否與當前查詢相關不能有效地利用用戶歷史信息,提高檢索系統(tǒng)的性能。BinTan與Default相比則有明顯提升,因為它考慮了歷史查詢與當前查詢的相似性,增加了檢索歷史中與當前查詢相關的歷史單元中的詞語的權值,對不相關主題中的噪聲具有抑制作用。使用p@5進行評價時,PQR相對BinTan提高12.8%,相對于Default提高26%;使用NDCG進行評價時,相對于BinTan提高7.2%,相對于Default提高11.4%。結合圖2,在大多數(shù)參數(shù)條件下,PQR的表現(xiàn)都好于3個基準系統(tǒng)??梢?PQR能夠較好處理檢索歷史中的兩類噪聲詞語,有效地選擇相關詞語重構查詢。適當設置參數(shù)時,可以大幅提高滿足用戶需求的網頁的排序,改善用戶體驗。
表3 PQR與基準系統(tǒng)的比較
本文針對用戶檢索歷史包含大量與當前查詢無關的噪聲的問題,將用戶的檢索歷史中的網頁摘要視為上下文語境,結合用戶點擊考察詞語在上下文中的共現(xiàn),選取與整個查詢最相關的詞語重構查詢模型。檢索結果重排序的實驗表明,在詞語選擇過程中,用戶點擊是有效的隱式反饋,對相關詞語的選擇作用明顯。選擇與當前查詢相關性最高的若干詞語重構查詢模型比將檢索歷史視為整體考慮更為合理,可以有效地減少噪聲。
本文的方法對用戶檢索歷史規(guī)模有一定依賴,利用當前查詢檢索網頁摘要時可能會面臨數(shù)據(jù)稀疏問題,對參數(shù)設置也有一定要求。在今后工作中,將局部反饋與用戶檢索歷史相結合以及自適應地確定參數(shù)等方面內容是我們需要進一步研究的課題。
[1] 曾春,邢春曉,周立柱.個性化服務技術綜述[J].軟件學報,2002,13(10):1952-1961.
[2] N icholas J.Belkin.Some(what)challenges and grand challenges for information retrieval[J].ACM SIGIR Forum,2008,42(1):47-54.
[3] Jing Bai,Jian-Yun Nie,Guihong Cao,H ugues Bouchard.Using query contex ts in in formation retrieval[C]//Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval.2007:15-22.
[4] Xuehua Shen,Bin Tan,ChengXiang,Zhai.Im p licit user mode ling for personalized search[C]//Proceedings of the 14th ACM international conference on Information and know ledge management.2005:824-831.
[5] Yuanhua Lv,Le Sun,Jun lin Zhang,Jian-Yun Nie W an Chen,Wei Zhang.An iterative imp licit feedback approach to personalized search[C]//Proceedings of the 21st International Conference on Computational Linguistics and the44th annualmeeting o f the Association for Computationa l Linguistics.2006:585-592.
[6] Sugiyama K,Hatano K,K Yoshikawa M.Adaptive w eb search based on user p ro file constructed without any effort from users[C]//Proceedings o f the 13th international conference on W orld W ide Web.2003:675-684
[7] Susan Gauch,Jason Chaffee,A laxander Pretschner.Ontology-based personalized search and brow sing[J].W eb Intelligence and Agent System s.2003,1(3-4):219-234
[8] Teevan,J.,Dumais,S.T.,&H orvitz,E.(2005).Personalizing search via automated analysis of interests and activites[C]//Proceedings of the 28th annual international ACM SIGIR con ference on Research and development in information retrieval,2005:449-456.
[9] Bin Tan,Xuehua Shen,ChengXiang Zhai.M ining long-term search history to imp rove search accuracy[C]//Proceedings o f the 12th ACM SIGKDD international conference on Know ledge discovery and data m ining,2006:718-723
[10] Lav renko,V.and Cro ft,W.B.Relevance-based languagemodels[C]//Proc.24th ACM SIGIRCon f.On Research and Development in Information Retrieval.2001:120-127.
[11] Jinxi Xu,W.Bruce Croft.Imp roving the effectiveness o f in formation retrievalwith loca l contex t analysis[J].ACM Transactions on Information System s(TOIS).2000,18(1):79-112.
[12] Pau l A lexandru Chirita,Claudiu S.Firan,Wo lfgang Nejdl.Personalized query expansion for the w eb[C]//Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval,2007:7-14.
[13] 梅翔,陳俊亮,徐萌.一種基于偏好的查詢擴展方法[J].高技術通訊,2007,17:1142-1146.
[14] 張宇,范基禮,鄭偉,鄒博偉,劉挺.基于人工標注的個性化檢索系統(tǒng)評測的研究[J].中文信息學報,2009,23(2):62-53.
[15] Kalervo J?rvelin,Jaana Kek?l?inen.IR evaluation methods for retrieving highly relevant documents[C]//Proceedings o f the 23rd annual international ACM SIGIR conference on Research and development in information retrieval,2000:41-48.