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

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

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

1 引言

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

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

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

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

2 相關(guān)研究

傳統(tǒng)的平滑算法(Additive、Jelinek-Merrer、 Dirichlet、Absolute Discounting等)對所有的文檔進行相同的平滑處理，忽略了文檔的因素。近期有學(xué)者對此進行了深入的研究，將文檔的因素考慮到平滑之中。Kruland and lee在語料庫中構(gòu)建聚類，利用聚類信息進行文檔的排序，將文檔的因素引入平滑之中[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)構(gòu)成，PML(w|C)是與文檔不相關(guān)的因素，從全局的角度考慮詞的分布，PML(w|Cluster)通過文檔所在聚類信息去評估詞在文檔中的分布。

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

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

3 近鄰語言模型

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

本文認(rèn)為文檔的近鄰文檔能夠從一定程度上反映這篇文檔特征，例如與文檔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)從全局角度進行詞分布的調(diào)整，由近鄰PML(w|Nd)從考慮文檔自身因素的近鄰角度進行詞分布調(diào)整。

4 近鄰的選擇

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

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

(3)

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

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

5.1 實驗環(huán)境

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

表1 實驗數(shù)據(jù)說明

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

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

(4)

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

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

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

5.2 評價指標(biāo)

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

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

(5)

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

5.3 實驗結(jié)果

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

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

使用leave-one-out方法進行參數(shù)訓(xùn)練后的實驗結(jié)果如表2、表3所示。

圖1 在DOE實驗中近鄰數(shù)量與MAP的關(guān)系

圖2 在WSJ實驗中近鄰數(shù)量與MAP的關(guān)系

表2DOE的實驗結(jié)果

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

表3 WSJ90的實驗結(jié)果

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

6 結(jié)論及未來工作

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

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

[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.