面向信息檢索的近鄰語言模型

韓中元，李 生，齊浩亮，楊沐昀

(1. 哈爾濱工業(yè)大學 計算機科學與技術學院，黑龍江 哈爾濱 150001；2. 黑龍江工程學院 計算機科學與技術系，黑龍江 哈爾濱 150050)

1 引言

在信息檢索中應用文檔語言模型(簡稱語言模型)由Ponte和Croft于1998年提出[1]。這個檢索模型提出以后因其優(yōu)良的性能而受到了廣泛的關注，面向信息檢索的語言模型對單篇文檔進行建模，由于每篇文檔的數據規(guī)模過小，因此對每篇文檔進行語言模型建模存在較嚴重的數據稀疏問題。如何通過平滑技術使語言模型更好地服務于檢索系統(tǒng)是一個關鍵問題。不少學者針對數據稀疏問題提出了一些改進的平滑方法或者模型。

平滑的基本思想是將模型中可見事件的概率值折扣，并將該折扣值重新分配給模型中不可見事件的元素序列，通過調整最大似然估計得到的概率分布，從而得到一個更準確、更合理的概率分布。經典平滑算法主要有Additive[2]、Jelinek-Merrer[3]、 Dirichlet[4]、Absolute Discounting[5]等，這幾種方法從全局的角度對詞的分布進行平滑處理，平滑項與文檔無關，對所有文檔一視同仁，缺乏對文檔信息的進一步利用。在信息檢索中，聚類有助于文檔信息的利用，提出了基于聚類的檢索方法[6-10]。文獻[10]將與文檔相關的信息引入語言模型的平滑中，詞在文檔中出現(xiàn)的分布由詞在文檔中的分布、詞在文檔所處分類上的分布以及詞在整個文檔集合中的分布共同決定，采用聚類方法的一個主要缺點是對于邊界附近的文檔，其聚類信息是否只帶來正面信息具有一定的不確定性。

本文認為，經典平滑算法沒有進一步利用文檔的信息，聚類語言模型對處在聚類中心的文檔性能有所提升，但是對處于聚類邊界的文檔，聚類信息未必能較好地反應該文檔上詞的分布。因此本文用近鄰信息取代聚類語言模型中的聚類信息，以期能夠更好地調整詞在文檔中的分布，獲得性能上的提升。

本文組織如下： 第2節(jié)對語言模型的平滑技術以及聚類語言模型進行了分析，第3節(jié)介紹近鄰語言模型的基本思想，第4節(jié)描述了如何去選擇近鄰，第5節(jié)介紹了實驗環(huán)境并對實驗結果進行了分析。

2 相關研究

傳統(tǒng)的平滑算法(Additive、Jelinek-Merrer、 Dirichlet、Absolute Discounting等)對所有的文檔進行相同的平滑處理，忽略了文檔的因素。近期有學者對此進行了深入的研究，將文檔的因素考慮到平滑之中。Kruland and lee在語料庫中構建聚類，利用聚類信息進行文檔的排序，將文檔的因素引入平滑之中[11]。Liu and croft提出基于聚類的文檔模型(CBDM,Cluster-based Document Model)將聚類信息引入到語言模型的平滑中[10]，其公式為：

P(w|d)= (1-λ)PML(w|d)

+λ[(1-β)PML(w|Cluster)

+βPML(w|C)]

(1)

其中PML(w|Cluster)為w在d所在聚類上的最大似然估計，PML(w|C)為w在整個文檔集上的最大似然估計。

在聚類語言模型中，平滑項由PML(w|Cluster)和PML(w|C)構成，PML(w|C)是與文檔不相關的因素，從全局的角度考慮詞的分布，PML(w|Cluster)通過文檔所在聚類信息去評估詞在文檔中的分布。

聚類語言模型基于文檔所在的聚類能夠從一定程度上反映這篇文檔特征的假設，對于處在聚類中心區(qū)域的文檔來講，這種假設具有一定合理性，但是考慮到文本聚類本身的偏差，對于處在邊界區(qū)域的文檔來講，這種假設未必成立。

本文認為通過近鄰信息有助于消除處于聚類邊界的文檔使用聚類語言模型時所帶來的不確定性影響，由此提出近鄰語言模型。

3 近鄰語言模型

假設有一查詢“南方 干旱”，現(xiàn)在有兩篇文檔，文檔1《我校隆重慶祝九十華誕》是一篇關于哈爾濱工業(yè)大學校慶的報道(文中沒有出現(xiàn)南方和干旱兩個詞)，文檔2《云南743萬畝農田缺水917萬人飲水困難》報道了云南省當時的旱情(但文中沒有出現(xiàn)南方和干旱兩個詞)。在傳統(tǒng)平滑算法的語言模型中，這兩篇文檔對于該查詢的得分由全局信息計算，得分相同。而事實上，文檔2與該查詢的相關度較高，而文檔1與該查詢毫不相干，這暴露了傳統(tǒng)平滑算法的不足。若是采用聚類的方法，文檔1一般情況下不會被分配到旱情報道的聚類中，文檔2有可能處于旱情報道聚類中，也有可能處于與云南相關新聞的聚類中，若是后者，文檔1與文檔2得分仍可能相同，也無法區(qū)分文檔1、文檔2與查詢的關系，這主要是由于文檔并不總是處于聚類中心附近，有可能帶來較大的偏差。通過近鄰信息有助于這一問題的解決。

本文認為文檔的近鄰文檔能夠從一定程度上反映這篇文檔特征，例如與文檔2接近的文檔主要是涉及旱情的文檔，其中出現(xiàn)“南方”或“干旱”的概率較高，將近鄰信息引入語言模型，能夠更真實地描述文檔2與文檔1的差異。由此，本文提出近鄰語言模型，公式為：

PJM(w|d)= (1-λ-β)P(w|d)+βPML(w|Nd)

+λPML(w|C)

(2)

其中PML(w|C)為w在整個文檔集上的最大似然估計，PML(w|Nd)為單詞w在d的近鄰Nd中的最大似然估計。

在這個模型中，由PML(w|C)從全局角度進行詞分布的調整，由近鄰PML(w|Nd)從考慮文檔自身因素的近鄰角度進行詞分布調整。

4 近鄰的選擇

構建近鄰信息主要涉及兩個問題： 如何計算兩篇文檔之間的距離？構建近鄰的數據來源是什么？

KL距離(Kullback-Leibler divergence)是常用的描述兩個分布差異關系的一種測度。本文通過計算一篇文檔與其他文檔之間的KL距離來選擇其近鄰文檔。其KL距離公式為：

(3)

本文對構建近鄰的數據來源進行了實驗。分別實驗了從待檢索文檔構建近鄰信息，從同一領域構建近鄰信息，從較大數據集中選擇部分文檔構建近鄰信息，選擇的方法是使用與待檢索文檔集分布KL距離最接近的N篇文檔。

5 實驗環(huán)境及結果

5.1 實驗環(huán)境

TREC(Text REtrieval Conference)，文本檢索會議是文本檢索領域最權威的評測會議之一，由美國國防部和美國國家技術標準局(NIST)聯(lián)合主辦。本文采用TREC_1、TREC_2的數據作為實驗數據。其中TREC數據DOE部分(美國能源署文件)有兩個文件夾，第一個文件夾，記為DOE1,第二個文件夾記為DOE2。WSJ(《華爾街日報》)按年份劃分，記為WSJ90(90年)、WSJ91(91年)、WSJ92(92年)。實驗分為8組，其中以DOE1作為待檢索文檔的實驗有4組，近鄰選擇的數據來源分別選取了DOE1自身文檔集、與帶檢索文檔相同來源的文檔集DOE1+DOE2、在DOE1+DOE2中選擇與DOE1規(guī)模相當的100 000篇文檔、整個TREC12文檔集中選擇與DOE1規(guī)模相當的100 000篇文檔。WSJ90實驗同為4組，近鄰選取策略與DOE實驗策略相同。其具體實驗數據如下表所示：

表1 實驗數據說明

本文采用常用的采用Jelinek-Mercer平滑方法的語言模型作為對比試驗，如公式(4)所示:

PJM(w|d)=(1-λ)P(w|d)+λPML(w|C)

(4)

其中PML(w|C)為w在整個文檔集上的最大似然估計。根據經驗，λ取0.2。

其他實驗使用的公式(2)，λ,β取值在[0,1]之間，以0.01作為步長，且λ+β≤1;近鄰文檔數量取值[0,200]之間，以10作為步長;近鄰數量在實驗中選擇10,20,30,40…200篇。

參數確定采用leave one out方法，即一個查詢的參數由其他查詢作為訓練時所得的參數所確定。

5.2 評價指標

本文選用信息檢索系統(tǒng)中常用的評價指標平均精確率(MAP,Mean Average Precision)來檢驗索引策略對檢索系統(tǒng)性能的影響。

平均精確率AP(Average Precision)： 單個主題的AP是每篇相關文檔檢索出后的準確率的平均值。主題集合的MAP是每個主題的AP的平均值。MAP是反映系統(tǒng)在全部相關文檔上性能的單值指標。AP定義如公式(5)所示：

(5)

其中：rij為查詢Qi第j個相關文檔的位次；|Ri|為查詢Qi的相關文檔數；n為測試的查詢數。

5.3 實驗結果

本文測試了近鄰數量對性能的影響，實驗結果如圖1和圖2所示。圖中以每十篇近鄰數量遞進，每個線對應一組實驗統(tǒng)計值，由實驗簡稱+后綴標示，其中后綴MAX代表該實驗取得的最高MAP值，后綴AVG代表該實驗所有參數組合所取得MAP的平均值。

從圖1可以看出，對于DOE短文檔，其近鄰的數量在大于30篇之后，對近鄰語言模型可能達到的最高MAP值影響不大，但是從平均性能上，更多的近鄰數量有助于性能的提升，但提升空間有限。從圖2可以看出，對于WSJ相對較長的文檔，過多的近鄰數量對性能并沒有帶來積極作用。綜合來講無論是從最高性能還是平均性能上考慮，取相對較少的近鄰數量(20～30篇近鄰)較為合理。

使用leave-one-out方法進行參數訓練后的實驗結果如表2、表3所示。

圖1 在DOE實驗中近鄰數量與MAP的關系

圖2 在WSJ實驗中近鄰數量與MAP的關系

表2DOE的實驗結果

評估指標語言模型實驗簡稱D1 實驗編號(1)提升幅度/%D12 (2)提升幅度/%D12-100K(3)提升幅度/%T12-100k(4)提升幅度/%MAP0.12160.125230.13208.60.12734.70.12926.3

表3 WSJ90的實驗結果

對比實驗1、2和5、6可以看出，增加相同領域文檔規(guī)模，性能有所提升。對比實驗3、4和實驗7、8可以看出，從更大規(guī)模上挑選近鄰選擇來源，有助于檢索性能的進一步提升。對比實驗1、3和5、7，利用相同領域的文檔作為近鄰選擇來源與自動選定的近鄰選擇來源性能相近。

6 結論及未來工作

本文認為利用文檔的近鄰信息能夠更合理地反映詞在文檔中的分布，有助于數據稀疏問題的解決，因此將文檔的近鄰信息加入語言模型的平滑算法中，提出近鄰語言模型，并對選擇近鄰的文檔來源問題進行了分析,并在TREC數據集上測試了近鄰語言模型在不同近鄰選擇集合上的性能。實驗表明，將近鄰信息加入到語言模型中有助于改善檢索性能。

近鄰語言模型的計算量較大，一篇文檔要通過逐個計算與近鄰數據來源中每一篇文檔的距離來找到它的近鄰，這限制了該模型的應用前景。計算量主要由選擇近鄰數據來源的規(guī)模所決定，因此減少選擇近鄰數據來源的規(guī)模可以有效地降低計算量，例如可以考慮利用返回結果的前N篇文檔來作為近鄰選擇的數據來源，從而大幅度降低計算量，此外也可以離線建立并存儲近鄰關系以提高檢索速度。本文初步驗證了近鄰語言模型的有效性，未來將在如何選擇近鄰的數據來源、如何更有效地利用近鄰信息、如何降低計算復雜度等方面進行進一步的研究。

[1] Ponte J M, Croft W B. A Language Modeling Approach to Information Retrieval[C]//Proceedings of the 21th annual international ACM SIGIR conference on Research and development in information retrieval, Melbourne, Australia: ACM, 1998: 275-281.

[2] G.J.Lidstone.Note on the general case of the Bayes-Laplace formula for inductive or a posteriori probabilities[J].Transactions of the Faculty of Actuaries,1920,(8):182-192.

[3] S.M.Katz.. Estimation of probabilities from sparse data for the language model component of a speech recognizer[J].IEEE Transactions on Acoustics,Speech and Signal Processing,1987:400-401.

[4] MACKAY, D. AND PETO, L. A Hierarchical Dirichlet Language Model[J]. Natural Language Engineering, 1995,(1):289-308.

[5] NEY H., ESSEN U.,KNESER, R. On structuring probabilistic dependencies in stochastic language modeling[J]. Computer, Speech and Language, 1994,(8):1-38.

[6] Croft, W. B. A model of cluster searching based on classification[J]. Information Systems,1980,(5):189-195.

[7] Jardine, N. and van Rijsbergen, C.J. The use of hierarchical clustering in information retrieval. Information[J]. Storage and Retrieval,1971,(7):217-240.

[8] CJ Van Rijsbergen, WB Croft. Document clustering: An evaluation of some experiments with the Cranfield 1400 collection[J]. Information Processing & Management,1975,(11):171-182.

[9] Voorhees, E. M. The effectivenss and efficiency of agglomerative hierarchic clustering in document retrieval[D].The Department of Computing Science, Cornell University. 1985.

[10] Xiaoyong Liu, W. Bruce Croft. Cluster-based retrieval using language models[C]//Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, Sheffield, United Kingdom: ACM,2004:186-193.

[11] Oren Kurland, Lillian Lee.Corpus structure, language models, and ad hoc information retrieval[C]//Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, Sheffield, United Kingdom: ACM, 2004: 194-201.