基于迭代方法的多層Markov網(wǎng)絡(luò)信息檢索模型

洪 歡，王明文，萬(wàn)劍怡，廖亞男

（江西師范大學(xué) 計(jì)算機(jī)信息工程學(xué)院，江西 南昌330022）

1 引言

對(duì)于大部分用戶來(lái)說(shuō)，在沒有充分了解文檔集的情況下很難給出專為檢索而設(shè)計(jì)的查詢，搜索引擎用戶經(jīng)常需要重構(gòu)他們的初始查詢表式以獲得他們所感興趣的更好結(jié)果［1]。隨著信息檢索技術(shù)的不斷發(fā)展，出現(xiàn)了許多通過(guò)使用和查詢意圖相關(guān)的信息來(lái)提升初始查詢表式的方法。查詢擴(kuò)展就是一種使用和查詢意圖相關(guān)的附加信息來(lái)重構(gòu)查詢的反饋方法，它是指利用計(jì)算機(jī)語(yǔ)言學(xué)、信息學(xué)等多種技術(shù)，在初始查詢表式的基礎(chǔ)上通過(guò)一定的方法和策略把與原查詢?cè)~相關(guān)的詞、詞組添加到原查詢中，組成新的、更能準(zhǔn)確表達(dá)用戶查詢意圖的查詢?cè)~序列，然后用新查詢對(duì)文檔重新檢索，從而改善信息檢索中的查全率和查準(zhǔn)率低下的問(wèn)題，彌補(bǔ)用戶查詢信息不足的缺陷。

在最近的一些研究當(dāng)中，Zhai通過(guò)Boosting算法將相關(guān)模型［2－3]和混合模型［4]合并來(lái)提取查詢擴(kuò)展詞，這種方法將兩個(gè)弱模型合并成一個(gè)強(qiáng)模型［5－6]，但是沒有考慮文檔與詞項(xiàng)之間的關(guān)聯(lián)性。Lee通過(guò)聚類的方式將初始檢索出的文檔聚成多個(gè)簇，然后基于文檔簇利用相關(guān)模型選取查詢擴(kuò)展詞［7]，雖然考慮了文檔與詞項(xiàng)之間的關(guān)系，但是在文檔表示方面存在缺陷，他僅僅將文檔簇看成一個(gè)大的文檔，忽略了每個(gè)文檔之間的相關(guān)性。上述模型都是基于詞獨(dú)立性的假設(shè)，但實(shí)際上詞之間的關(guān)聯(lián)信息對(duì)檢索效果有很大的影響。甘麗新等提出一種基于Markov概念的信息檢索模型［8]，對(duì)于每個(gè)查詢，使用團(tuán)的提取算法在詞項(xiàng)子空間的Markov網(wǎng)絡(luò)中提取擴(kuò)展詞，該模型取得了良好的檢索效果，但是該工作沒有考慮文檔之間和查詢之間的相關(guān)性信息。付劍波等提出基于團(tuán)模型的文檔重排算法研究［9]，該模型通過(guò)對(duì)文檔集的學(xué)習(xí)，構(gòu)造文檔子空間的Markov網(wǎng)絡(luò)，提取出文檔團(tuán)，使用文檔團(tuán)信息進(jìn)行文檔重排，但是該工作沒有將文檔團(tuán)信息用于查詢擴(kuò)展中。湯皖寧等提出基于文檔團(tuán)依賴的Markov網(wǎng)絡(luò)檢索模型［10]，該模型首先使用團(tuán)的提取算法提取出文檔團(tuán)和詞團(tuán)，然后根據(jù)詞項(xiàng)子空間和文檔子空間的映射關(guān)系將詞團(tuán)分為文檔依賴詞團(tuán)和非文檔依賴詞團(tuán)，并用于查詢擴(kuò)展中。雖然擴(kuò)展中充分利用了索引詞項(xiàng)、文檔子空間的Markov網(wǎng)絡(luò)信息，但是沒有考慮到查詢子空間的Markov網(wǎng)絡(luò)信息。

本文將湯皖寧等提出的基于文檔團(tuán)依賴的Markov網(wǎng)絡(luò)檢索模型［10]作為基礎(chǔ)模型，對(duì)文檔集做初次檢索；接著，將初次檢索得到的結(jié)果用于提取查詢子空間的Markov網(wǎng)絡(luò)，并提取出最大查詢團(tuán)；最后，結(jié)合前兩個(gè)步驟構(gòu)建基于迭代方法的多層Markov網(wǎng)絡(luò)信息檢索模型，即結(jié)合詞項(xiàng)、文檔和查詢子空間的Markov網(wǎng)絡(luò)信息用于查詢擴(kuò)展以及采用迭代方法計(jì)算文檔與查詢之間的相關(guān)概率。文中首先介紹了Markov網(wǎng)絡(luò)檢索模型、Markov網(wǎng)絡(luò)的構(gòu)造方法、最大團(tuán)的提取等工作；接著，重點(diǎn)介紹了初始的基于文檔團(tuán)依賴的Markov網(wǎng)絡(luò)檢索模型以及最終的基于迭代方法的多層Markov網(wǎng)絡(luò)查詢擴(kuò)展模型。最后，對(duì)本文提出的模型與一些經(jīng)典的模型做對(duì)比實(shí)驗(yàn)，并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析以及提出下一步的工作展望。

2 Markov網(wǎng)絡(luò)檢索模型構(gòu)造方法

2.1 Markov網(wǎng)絡(luò)檢索模型

Markov網(wǎng)絡(luò)是一種不確定性推理的有利圖形工具［11]，它可以較好地表示知識(shí)關(guān)聯(lián)，很容易從實(shí)例數(shù)據(jù)中訓(xùn)練獲得，具有強(qiáng)大的學(xué)習(xí)功能和推導(dǎo)能力。通過(guò)它的無(wú)向邊來(lái)解釋信息檢索中的語(yǔ)義關(guān)系更直接、恰當(dāng)。Markov網(wǎng)絡(luò)可以表示為一個(gè)二元組（V，E），V為所有節(jié)點(diǎn)的集合，E為一組無(wú)向邊的集合，E＝｛（xi，xj）｜xi≠xj∧xi，xj∈V｝，E 中的邊表示節(jié)點(diǎn)之間的依賴或相關(guān)關(guān)系。

基于Markov網(wǎng)絡(luò)的檢索模型分為三層：查詢子空間，索引詞項(xiàng)子空間，文檔子空間。如圖1所示，三層子空間構(gòu)成了一個(gè)推理網(wǎng)絡(luò)，根節(jié)點(diǎn)為詞項(xiàng)子空間的詞節(jié)點(diǎn)，我們利用詞與詞之間的相關(guān)性、文檔與文檔之間的相關(guān)性、查詢與查詢之間的相關(guān)性分別構(gòu)造詞項(xiàng)、文檔、查詢子空間的Markov網(wǎng)絡(luò)。通過(guò)設(shè)定閾值，對(duì)三層子空間的Markov網(wǎng)絡(luò)信息分別進(jìn)行最大團(tuán)的提取，得到最大詞團(tuán)、文檔團(tuán)、查詢團(tuán)。

在圖1中，q代表用戶給定的初始查詢，qi代表查詢子空間中的查詢，tj代表索引詞項(xiàng)子空間中的詞項(xiàng)，dk代表文檔子空間里的文檔。圖中從詞項(xiàng)tj存在指向查詢qi和文檔dk的有向邊，分別代表查詢qi和文檔dk由這些詞項(xiàng)tj構(gòu)成；在查詢、詞項(xiàng)和文檔三層子空間中存在的多條無(wú)向邊，分別表示查詢間、詞項(xiàng)間及文檔間存在關(guān)聯(lián)，并且邊的權(quán)重取決于關(guān)聯(lián)的程度。

圖1 多層Markov網(wǎng)絡(luò)結(jié)構(gòu)圖

2.1.1 詞項(xiàng)子空間的Markov網(wǎng)絡(luò)

在圖1所示結(jié)構(gòu)圖的詞項(xiàng)子空間中，節(jié)點(diǎn)表示詞項(xiàng)，詞項(xiàng)之間有邊相連構(gòu)成了詞項(xiàng)子空間的Markov網(wǎng)絡(luò)，邊的權(quán)重表示詞間的相關(guān)性程度。通過(guò)利用詞的共現(xiàn)性來(lái)提取詞與詞之間的關(guān)系已經(jīng)運(yùn)用到許多研究中，在計(jì)算詞共現(xiàn)的詞頻中，一般可以以整個(gè)文檔、段落或是一個(gè)固定長(zhǎng)度為窗口［12]。出于考慮效率方面的因素，本文選擇文檔作為窗口單位。實(shí)驗(yàn)中采用詞的共現(xiàn)性來(lái)提取詞項(xiàng)與詞項(xiàng)之間的關(guān)系，鑒于Markov網(wǎng)絡(luò)的無(wú)向性，因此在構(gòu)造詞項(xiàng)子空間的Markov網(wǎng)絡(luò)時(shí)，采用兩個(gè)詞的綜合共現(xiàn)性來(lái)計(jì)算，如式（1）、（2）所示。

其中ti和tj指兩個(gè)詞項(xiàng)，C（ti，tj）指在訓(xùn)練文檔集中ti和tj在同一篇文檔中同時(shí)出現(xiàn)的頻率，C（ti）和C（tj）分別表示在訓(xùn)練文檔集中ti和tj出現(xiàn)的頻率，Sim（ti，tj）表示ti和tj之間的相關(guān)性，Sim 值越大，兩個(gè)詞的相關(guān)性就越高。當(dāng)Sim值大于給定的閾值時(shí)，則詞項(xiàng)ti和tj相互依賴，即在詞項(xiàng)子空間的Markov網(wǎng)絡(luò)中有邊相連。

2.1.2 文檔子空間的Markov網(wǎng)絡(luò)

同樣，在圖1所示的文檔子空間中，節(jié)點(diǎn)表示文檔，文檔之間有邊相連構(gòu)成文檔子空間的Markov網(wǎng)絡(luò)，邊的權(quán)重表示文檔間的相關(guān)性程度。本文中的文檔均表示為向量，采用文檔向量之間的夾角余弦公式來(lái)度量文檔之間的相關(guān)性，文檔與文檔之間的相關(guān)性記為Sim（di，dj），計(jì)算公式如式（3）所示。

當(dāng)Sim（di，dj）的值大于給定的閾值時(shí)，則文檔di和dj相互依賴，即在文檔子空間的Markov網(wǎng)絡(luò)中有邊相連。

2.2 團(tuán)的提取

通過(guò)三層子空間的Markov網(wǎng)絡(luò)結(jié)構(gòu)分析可知，它實(shí)際構(gòu)成一個(gè)相容關(guān)系圖。在相容關(guān)系圖中，我們發(fā)現(xiàn)許多完全多邊形，就是每個(gè)節(jié)點(diǎn)都與其他節(jié)點(diǎn)相連的多邊形，即構(gòu)成了團(tuán)。團(tuán)的提取分為索引項(xiàng)詞團(tuán)的提取、文檔團(tuán)的提取和查詢團(tuán)的提取。

對(duì)于詞項(xiàng)和文檔子空間的Markov網(wǎng)絡(luò)，團(tuán)內(nèi)的詞和文檔彼此相互依賴，即存在某種語(yǔ)義關(guān)聯(lián)，可以認(rèn)為它們集中表達(dá)同一個(gè)概念［13]（或主題）。本文按照詞的最大團(tuán)以及文檔團(tuán)與詞團(tuán)之間的映射關(guān)系來(lái)選擇擴(kuò)展查詢?cè)~，以最大團(tuán)為單位進(jìn)行擴(kuò)展，具體最大團(tuán)的提取方法可以參照文獻(xiàn)［8]。如果一個(gè)詞團(tuán)中的某個(gè)詞項(xiàng)同時(shí)映射到一個(gè)文檔團(tuán)的多篇文章，則認(rèn)為這個(gè)詞比其他的詞對(duì)主題更具有代表性，在后續(xù)的檢索階段中提高包含此類詞項(xiàng)詞團(tuán)的權(quán)重，我們將這種詞項(xiàng)稱為文檔依賴詞。

在詞項(xiàng)和文檔子空間的Markov網(wǎng)絡(luò)中，關(guān)鍵的步驟是提取出最大詞團(tuán)、文檔團(tuán)以及將最大詞團(tuán)映射到文檔團(tuán)上。按照最大團(tuán)的相關(guān)性權(quán)重來(lái)選擇用于擴(kuò)展的最大詞團(tuán)，以最大團(tuán)為單位作為一個(gè)概念整體擴(kuò)展進(jìn)來(lái)，這樣有利于把語(yǔ)義比較集中的詞擴(kuò)展進(jìn)來(lái)，同時(shí)也提高了那些與某個(gè)查詢?cè)~的關(guān)系不是很強(qiáng)，但與查詢主題很相關(guān)的詞加入查詢擴(kuò)展的可能性，從而提高檢索效果。在圖1的詞項(xiàng)子空間中，詞項(xiàng)t2的最大團(tuán)有｛t2、t4、t5｝，｛t2、t3、t6、t7｝，且每個(gè)最大詞團(tuán)會(huì)有相應(yīng)的權(quán)重，取決于團(tuán)內(nèi)各詞項(xiàng)間的依賴程度。

2.3 詞團(tuán)與文檔團(tuán)的映射

詞團(tuán)與文檔團(tuán)之間的映射關(guān)系可以用來(lái)強(qiáng)化索引詞項(xiàng)與用戶給定的初始查詢之間的關(guān)聯(lián)性。如果最大詞團(tuán)中的一個(gè)索引詞項(xiàng)出現(xiàn)在一個(gè)文檔團(tuán)的多篇文檔中，則認(rèn)為包含該詞項(xiàng)的詞團(tuán)與該文檔團(tuán)存在語(yǔ)義上的關(guān)聯(lián)性，同時(shí)也認(rèn)為這個(gè)詞團(tuán)與查詢的主題更加相關(guān)。因此，本文通過(guò)這種映射關(guān)系將最大詞團(tuán)分為文檔依賴詞團(tuán)和非文檔依賴詞團(tuán)，并將這兩種詞團(tuán)用于查詢擴(kuò)展。由于文檔依賴詞團(tuán)可能對(duì)文檔團(tuán)的主題更具代表性，因此，在檢索階段會(huì)給文檔依賴詞團(tuán)賦予更大的權(quán)重。如圖1所示，詞項(xiàng)子空間內(nèi)有三個(gè)最大詞團(tuán) T1＝｛t1、t4、t5｝、T2＝｛t2、t4、t5｝和 T3＝｛t2、t3、t6、t7｝，文檔空間內(nèi)有三個(gè)最大文檔團(tuán) D1＝｛d1、d2、d3、d5｝、D2＝｛d2、d3、d4｝、D3＝｛d2、d4、d6｝。詞項(xiàng)t4在文檔團(tuán) D1中的所有文檔中都出現(xiàn)，所以詞團(tuán)T1和T2都是文檔依賴詞團(tuán)，而詞團(tuán)T3中的任何詞項(xiàng)都沒有在同一個(gè)文檔團(tuán)中的所有文檔中出現(xiàn)，所以詞團(tuán)T3是非文檔依賴詞團(tuán)。

2.4 基于文檔團(tuán)依賴的Markov網(wǎng)絡(luò)檢索模型

對(duì)于用戶給定的初始查詢q，通過(guò)利用詞項(xiàng)、文檔子空間的Markov網(wǎng)絡(luò)信息，計(jì)算文檔集D中任意文檔dj∈D和查詢q的相關(guān)概率p（dj｜q）。然后按照p（dj｜q）的大小排列文檔集中的文檔，從而得出我們需要的文檔。由左家莉等提出的基于Markov網(wǎng)絡(luò)的信息檢索擴(kuò)展模型［14]可得：

本文采用BM25類似權(quán)重方式來(lái)計(jì)算wi，q和wi，j，具體的計(jì)算公式參照文獻(xiàn)［14]。

在查詢擴(kuò)展階段，擴(kuò)展詞的選擇方案采用基于最大團(tuán)的方式，以最大詞團(tuán)為單位，作為一個(gè)概念整體對(duì)初始查詢表式中對(duì)應(yīng)的詞項(xiàng)進(jìn)行擴(kuò)展。在選取最大詞團(tuán)階段我們將詞團(tuán)分為兩類，分別是：文檔依賴詞團(tuán)和非文檔依賴詞團(tuán)。利用詞團(tuán)與文檔團(tuán)之間的映射關(guān)系來(lái)提取文檔依賴詞團(tuán)，并在檢索階段加大這類詞團(tuán)的權(quán)重。對(duì)于用戶給定的初始查詢q，文檔和查詢的相關(guān)概率計(jì)算公式由式（4）修正為：

其中，α：非文檔依賴詞團(tuán)平滑參數(shù)（0≤α≤1），β：文檔依賴詞團(tuán)平滑參數(shù)（0≤β≤1），α＋β＜1，指用式（1）計(jì)算詞項(xiàng)之間相關(guān)性的值。

式（5）中的Cmax（t）代表詞項(xiàng)t的最大詞團(tuán)，在提取最大詞團(tuán)時(shí)，會(huì)給每個(gè)詞項(xiàng)的最大詞團(tuán)賦予不同的權(quán)重。本文提出這樣的假設(shè)：最大詞團(tuán)的權(quán)重越大，則它所表達(dá)的概念與查詢主題越相關(guān)，在查詢擴(kuò)展的時(shí)候優(yōu)先被考慮進(jìn)來(lái)。在實(shí)驗(yàn)中，利用式（5）對(duì)文檔集做初次檢索，通過(guò)調(diào)整最大詞團(tuán)的個(gè)數(shù)以及式（5）中的平滑參數(shù)，使該模型的檢索效果達(dá)到穩(wěn)健。

3 基于迭代方法的多層Markov網(wǎng)絡(luò)信息檢索模型

3.1 查詢子空間的Markov網(wǎng)絡(luò)

在圖1中，查詢子空間中的節(jié)點(diǎn)（查詢）之間也有邊相連，構(gòu)成查詢子空間的Markov網(wǎng)絡(luò)。本文中查詢之間的相關(guān)性由查詢返回的結(jié)果集合中排名靠前的文檔所決定，也就是利用相關(guān)反饋方法中的隱式反饋信息［1]。通過(guò)使用2.4節(jié)介紹的基于文檔團(tuán)依賴的 Markov網(wǎng)絡(luò)檢索模型［10]對(duì)文檔集做初次檢索，得出用戶給定查詢返回的結(jié)果集合，取結(jié)果集合中查詢qi返回的前2篇文檔，將這2篇相關(guān)文檔合并成一個(gè)新的“文檔”Di，采用類似2.1.2節(jié)中文檔之間相關(guān)性的度量方法來(lái)確定查詢間的相關(guān)性，記為Sim（qi，qj），計(jì)算公式如式（6）所示。

式（7）中的P′（dj｜qi）是在模型中加入了查詢子空間的Markov網(wǎng)絡(luò)信息，計(jì)算文檔dj與初始查詢q的最大查詢團(tuán)（q）中的其他查詢qi的相關(guān)概率，計(jì)算公式類似于式（5），如式（8）所示：

當(dāng)Sim（qi，qj）的值大于給定的閾值時(shí)，則查詢qi和qj相互依賴，即在查詢子空間的 Markov網(wǎng)絡(luò)中有邊相連。

3.2 查詢團(tuán)的提取

使用式（6）計(jì)算出查詢間的相關(guān)性，從而構(gòu)建查詢子空間的Markov網(wǎng)絡(luò)。將所得到的Markov網(wǎng)絡(luò)信息用于最大查詢團(tuán)的提取，具體的提取方法與2.2節(jié)中的方法一致，所得到的查詢子空間的Markov網(wǎng)絡(luò)信息也可以用在查詢擴(kuò)展中，從而提高檢索效果。

3.3 基于迭代方法的多層Markov網(wǎng)絡(luò)查詢擴(kuò)展模型

結(jié)合2.4節(jié)基于文檔團(tuán)依賴的Markov網(wǎng)絡(luò)檢索模型［10]以及最大查詢團(tuán)來(lái)構(gòu)建本文的基于迭代方法的多層Markov查詢擴(kuò)展模型。這樣，就將詞項(xiàng)、文檔和查詢?nèi)龑幼涌臻g的Markov網(wǎng)絡(luò)信息用于查詢擴(kuò)展中。加入了查詢子空間的Markov網(wǎng)絡(luò)信息后，將文檔和查詢的相關(guān)概率計(jì)算公式由式（5）修正為：

其中，α：非文檔依賴詞團(tuán)平滑參數(shù)（0≤α≤1），β：文檔依賴詞團(tuán)平滑參數(shù)（0≤β≤1），α＋β ＜

構(gòu)造本文基于迭代方法的多層Markov網(wǎng)絡(luò)信息檢索模型時(shí)，迭代的具體步驟如下：

1）第一次迭代過(guò)程：

a）利用式（5）中得到的檢索結(jié)果提取出最大查詢團(tuán)信息；

b）取出檢索結(jié)果中文檔與查詢的相關(guān)概率值，并代入式（7）中計(jì)算新的相關(guān)概率，即將式（5）中的P（dj｜q）→P′（dj｜q）；

c）用式（7）對(duì)文檔集進(jìn)行重新檢索；

2）第n（n＞1）次迭代過(guò)程：

a）從前一次（n－1）迭代過(guò)程中得到的檢索結(jié)果中提取出最大查詢團(tuán)信息；

b）將檢索結(jié)果中文檔與查詢的相關(guān)概率值代入式（7）中重新計(jì)算文檔得分；

c）利用式（7）對(duì)文檔集再次檢索。

重復(fù)步驟2）進(jìn)行多次迭代，直到實(shí)驗(yàn)的檢索效果收斂（即檢索效果已經(jīng)不再提高或者提高的比例不大）為止。實(shí)驗(yàn)過(guò)程中，通過(guò)調(diào)整最大詞團(tuán)的個(gè)數(shù)以及式（7）、（8）中的平滑參數(shù)θ、α、β，使該模型的檢索效果達(dá)到穩(wěn)健。

4 實(shí)驗(yàn)設(shè)計(jì)和結(jié)果

4.1 對(duì)比實(shí)驗(yàn)

本文采用的是一種常用的測(cè)試集，該測(cè)試集由adi、med、cran、cisi及cacm五個(gè)標(biāo)準(zhǔn)測(cè)試文檔集組成，常用于評(píng)價(jià)檢索系統(tǒng)的性能。五個(gè)測(cè)試文檔集的文檔較小，且評(píng)價(jià)效果良好，下載地址：ftp：／／ftp.cs.cornell.edu／pub／smart.測(cè)試數(shù)據(jù)集的具體情況如表1所示。

表1 實(shí)驗(yàn)中的數(shù)據(jù)集

為了驗(yàn)證基于迭代方法的多層Markov網(wǎng)絡(luò)信息檢索模型（IMMR）的檢索效果，本文選取使用普通BM25模型和基于Markov概念的信息檢索模型［8]（MRC）來(lái)進(jìn)行對(duì)比實(shí)驗(yàn)。并把基于文檔團(tuán)依賴的Markov網(wǎng)絡(luò)檢索模型［10]作為Baseline，與本文提出的模型的主要區(qū)別在于查詢擴(kuò)展中沒有利用查詢子空間的Markov網(wǎng)絡(luò)信息，以及沒有采用基于迭代的方法來(lái)計(jì)算文檔與查詢的相關(guān)概率。在表中可以看出本文提出的檢索模型實(shí)驗(yàn)結(jié)果比起基準(zhǔn)方法有比較大的提高，我們采用的評(píng)價(jià)指標(biāo)是3－avg和11－avg。3－avg和11－avg分別代表一組測(cè)試查詢?cè)?個(gè)召回率點(diǎn)（0.2，0.5，0.8）和11個(gè)召回率點(diǎn)（0，0.1，0.2，……，1.0）上精確率的平均值，這種平均精度—召回率數(shù)值如今已成為信息檢索系統(tǒng)的標(biāo)準(zhǔn)評(píng)價(jià)指標(biāo)，在信息檢索文獻(xiàn)中被廣泛采用［1]。本文實(shí)驗(yàn)的具體結(jié)果見表2和表3。

表23－avg實(shí)驗(yàn)結(jié)果

表311－avg實(shí)驗(yàn)結(jié)果

從實(shí)驗(yàn)結(jié)果中，我們可以發(fā)現(xiàn)本文提出的模型在數(shù)據(jù)集cacm和adi上相對(duì)于Baseline模型有最大幅度的提高。對(duì)于數(shù)據(jù)集cacm主要是因?yàn)槠浜械奈臋n數(shù)最多，文檔團(tuán)與詞團(tuán)的映射關(guān)系更為明顯，可以有效地將最大詞團(tuán)劃分成文檔依賴詞團(tuán)和非文檔依賴詞團(tuán)，并提高從較多的文檔里找到與用戶需求真正相關(guān)文檔的概率；對(duì)于adi數(shù)據(jù)集，雖然數(shù)據(jù)集最小，但是由于其自身的特殊性，可以加入的修正信息最多，也能取得較好的檢索效果。而數(shù)據(jù)集med雖然包含的詞項(xiàng)數(shù)多，但文檔總數(shù)及查詢數(shù)較少，構(gòu)造出的文檔、查詢子空間的Markov網(wǎng)絡(luò)信息較少，使得查詢擴(kuò)展時(shí)加入的修正信息少，導(dǎo)致最后的檢索效果提升不明顯。

本文提出的基于迭代方法的多層Markov網(wǎng)絡(luò)信息檢索模型中，采用迭代的方法計(jì)算文檔與查詢的相關(guān)概率，以及從檢索結(jié)果集合中構(gòu)造查詢子空間的Markov網(wǎng)絡(luò)。理論上，在檢索結(jié)果收斂之前，每一次迭代過(guò)程都能將與用戶查詢更加相關(guān)的文檔排在前面，從而構(gòu)造出更加符合用戶查詢意圖的查詢子空間的Markov網(wǎng)絡(luò)，并最終提高檢索效果。實(shí)驗(yàn)中我們發(fā)現(xiàn)，迭代2～3次檢索結(jié)果就基本達(dá)到收斂，且第1次迭代過(guò)程檢索效果提升的幅度較大。主要的原因有：1）第1次迭代過(guò)程中，在基于文檔團(tuán)依賴的 Markov網(wǎng)絡(luò)檢索模型［10]的基礎(chǔ)上初次加入了查詢子空間的Markov網(wǎng)絡(luò)信息，使得檢索結(jié)果有明顯提高；2）本文用于構(gòu)造查詢子空間的Markov網(wǎng)絡(luò)采用的方法是從檢索結(jié)果集合中取出查詢qi返回的前2篇文檔，來(lái)計(jì)算查詢間的相似性，加上實(shí)驗(yàn)中采用的數(shù)據(jù)集文檔數(shù)相對(duì)較少，返回的前2篇文檔不會(huì)有太大改變，使得后續(xù)構(gòu)造的查詢子空間的Markov網(wǎng)絡(luò)基本不變。未來(lái)的工作中將在更大的數(shù)據(jù)集上做測(cè)試，同時(shí)改進(jìn)構(gòu)造查詢子空間的Markov網(wǎng)絡(luò)的方法（比如采用查詢?nèi)罩拘畔ⅲ?，相信通過(guò)迭代方法能夠取得較好的檢索效果。

4.2 相關(guān)性閾值的選取

在實(shí)驗(yàn)中，發(fā)現(xiàn)調(diào)整詞項(xiàng)間、文檔間以及查詢間相關(guān)性的閾值會(huì)使得提取最大團(tuán)的計(jì)算量變化很大，最大團(tuán)的個(gè)數(shù)以及最大團(tuán)中包含詞、文檔和查詢的數(shù)量也會(huì)有較大的影響，最終對(duì)檢索效果也會(huì)產(chǎn)生比較明顯的影響。對(duì)于詞項(xiàng)間相關(guān)性閾值的設(shè)定，數(shù)據(jù)集adi中取0.7，其余四個(gè)數(shù)據(jù)集均取0.8，這是因?yàn)閍di數(shù)據(jù)集詞項(xiàng)數(shù)最少，需要加入用于構(gòu)造詞項(xiàng)子空間的Markov網(wǎng)絡(luò)的詞項(xiàng)數(shù)多些。詞項(xiàng)間的相關(guān)性閾值越大，得到的最大團(tuán)的個(gè)數(shù)s越少，相反則最大團(tuán)的個(gè)數(shù)s越多，用于提取最大團(tuán)的計(jì)算時(shí)間也越長(zhǎng)。當(dāng)詞項(xiàng)網(wǎng)絡(luò)固定時(shí)，用于加入查詢擴(kuò)展中詞項(xiàng)的最大團(tuán)個(gè)數(shù)s會(huì)對(duì)實(shí)驗(yàn)結(jié)果產(chǎn)生較大影響：一開始隨著s的增加，檢索效果會(huì)隨之提高；當(dāng)s增加到一定的數(shù)值時(shí)，檢索效果達(dá)到最優(yōu)，若再增大則結(jié)果會(huì)逐漸降低。在文檔間相關(guān)性閾值的設(shè)定上，根據(jù)5個(gè)數(shù)據(jù)集中文檔總數(shù)的不同取不同的值，實(shí)驗(yàn)中數(shù)據(jù)集adi的文檔數(shù)最少，取閾值0.1，med取0.2，cran、cisi、cacm取0.3。同樣地，對(duì)于查詢間相關(guān)性閾值的取值也與數(shù)據(jù)集中包含的查詢數(shù)和需要加入的修正信息量有關(guān)，實(shí)驗(yàn)中數(shù)據(jù)集adi的查詢數(shù)少且可加入修正的信息量大，取閾值0.2，med、cisi、cacm 取0.3，cran數(shù)據(jù)集含有的查詢數(shù)最多閾值取0.5。

4.3 平滑參數(shù)的調(diào)整對(duì)實(shí)驗(yàn)結(jié)果的影響

本文提出的模型中包含θ、α、β這3個(gè)平滑參數(shù)，分別對(duì)應(yīng)加入查詢團(tuán)信息的權(quán)重、非文檔依賴詞團(tuán)權(quán)重以及文檔依賴詞團(tuán)權(quán)重。通過(guò)調(diào)整平滑參數(shù)的取值，使檢索效果達(dá)到最優(yōu)，由于文檔依賴詞團(tuán)可能對(duì)文檔團(tuán)的主題更具代表性，需要賦予更高的權(quán)重。因此，實(shí)驗(yàn)中平滑參數(shù)α和β初始值為0，令參數(shù)α以0.01，β以0.03的增量來(lái)循環(huán)計(jì)算文檔與查詢的相關(guān)概率，并記錄在每次循環(huán)中各參數(shù)取值確定時(shí)的實(shí)驗(yàn)結(jié)果。實(shí)驗(yàn)中通過(guò)調(diào)整3個(gè)平滑參數(shù)會(huì)使得檢索結(jié)果有較大影響，以數(shù)據(jù)集adi和cacm為例，圖2和圖3表示在第一次迭代過(guò)程中，調(diào)整平滑參數(shù)對(duì)實(shí)驗(yàn)結(jié)果的影響（實(shí)驗(yàn)中，取θ＝α，β＝3α）：

圖2 adi數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果

圖3 cacm數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果

在圖2和圖3中，橫坐標(biāo)表示α的取值，縱坐標(biāo)表示平均準(zhǔn)確率。實(shí)驗(yàn)表明，α和β的取值對(duì)結(jié)果的影響遵循一定的規(guī)律，在一定的范圍內(nèi)平滑參數(shù)α越大，檢索效果越好，但達(dá)到一定數(shù)值以后結(jié)果開始變差。另外，它們的取值與文檔集規(guī)模也有一定的關(guān)系。在實(shí)驗(yàn)當(dāng)中，當(dāng)文檔集規(guī)模較小時(shí)，α和β取較大的數(shù)值實(shí)驗(yàn)結(jié)果才能達(dá)到相對(duì)較好水平，如上圖2，3所示，在adi數(shù)據(jù)集中α＝0.06，β＝0.18時(shí)，實(shí)驗(yàn)結(jié)果達(dá)到穩(wěn)健，然而在cacm數(shù)據(jù)集中α＝0.02，β＝0.06時(shí)，實(shí)驗(yàn)結(jié)果才能達(dá)到穩(wěn)健，這是因?yàn)閍di數(shù)據(jù)集中文檔數(shù)目要遠(yuǎn)遠(yuǎn)少于cacm數(shù)據(jù)集中的文檔數(shù)目，用于修正查詢的信息量少，需要通過(guò)提高修正信息的權(quán)重來(lái)取得好的檢索效果。

5 總結(jié)與展望

本文通過(guò)對(duì)訓(xùn)練文檔集和檢索結(jié)果集合的學(xué)習(xí)，構(gòu)造出詞項(xiàng)、文檔和查詢?nèi)龑幼涌臻g的Markov網(wǎng)絡(luò)，將得到的三層Markov網(wǎng)絡(luò)信息用于最大詞團(tuán)、文檔團(tuán)和查詢團(tuán)的提取，利用文檔團(tuán)與詞團(tuán)之間的映射關(guān)系將最大詞團(tuán)分為文檔依賴詞團(tuán)和非文檔依賴詞團(tuán)，在查詢擴(kuò)展中加大文檔依賴詞團(tuán)的權(quán)重。模型中通過(guò)迭代的方法從已有的檢索結(jié)果集合中提取出最大查詢團(tuán)信息，并迭代地計(jì)算文檔與查詢的相關(guān)概率，直到檢索效果收斂。下一步的工作有：（1）在更大的數(shù)據(jù)集上（比如TREC數(shù)據(jù)集）進(jìn)行實(shí)驗(yàn)檢測(cè)該模型的通用性；（2）本文是對(duì)已有的檢索結(jié)果集合采用隱式的相關(guān)反饋方法，收集檢索結(jié)果返回的前2篇相關(guān)文檔信息來(lái)計(jì)算查詢間的相關(guān)性，未來(lái)我們將利用用戶查詢?nèi)罩緛?lái)構(gòu)造查詢子空間的Markov網(wǎng)絡(luò)；（3）隨著數(shù)據(jù)集規(guī)模的增大，構(gòu)造Markov網(wǎng)絡(luò)計(jì)算量會(huì)變得非常大。因此，在面對(duì)海量數(shù)據(jù)檢索時(shí)，一方面需優(yōu)化Markov網(wǎng)絡(luò)構(gòu)造方法；另一方面可將詞項(xiàng)、文檔和查詢間的相關(guān)性計(jì)算算法采用MapReduce編程模型并行化，加快執(zhí)行效率。

［1]黃萱菁，張奇，邱錫鵬.現(xiàn)代信息檢索［M].第一版.機(jī)械工業(yè)出版社，2012.

［2]Zhai C，Lafferty J.Model－based feedback in the lan－guage modeling approach to information retrieval［C]／／Proceedings of the tenth international conference on Information and knowledge management.ACM，2001：403－410.

［3]Tao T，Zhai C X.A mixture clustering model for pseudo feedback in information retrieval［M]／／Classification，Clustering，and Data Mining Applications.Springer Berlin Heidelberg，2004：541－551.

［4]Soskin N，Kurland O，Domshlak C.Navigating in the dark：Modeling uncertainty in ad hoc retrieval using multiple relevance models［M]／／Advances in Information Retrieval Theory.Springer Berlin Heidelberg，2009：79－91.

［5]Tao T，Zhai C X.Regularized estimation of mixture models for robust pseudo－relevance feedback［C]／／Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval.ACM，2006：162－169.

［6]Lv Y，Zhai C X，Chen W.A boosting approach to improving pseudo－relevance feedback［C]／／Proceedings of the 34th international ACM SIGIR conference on Research and development in Information Retrieval.ACM，2011：165－174.

［7]Lee K S，Croft W B，Allan J.A cluster－based resampling method for pseudo－relevance feedback［C]／／Proceedings of the 31st annual international ACM SIGIR conference on Research and development in information retrieval.ACM，2008：235－242.

［8]甘麗新.基于 Markov概念的信息檢索模型［D].江西師范大學(xué)，2007.

［9]付劍波，王明文，羅遠(yuǎn)勝，等.基于團(tuán)模型的文檔重排算法研究［J].中文信息學(xué)報(bào)，2009，23（1）：71－78.

［10]湯皖寧.基于文檔團(tuán)的 Markov網(wǎng)絡(luò)檢索模型［D].江西師范大學(xué)，2013.

［11]何盈捷，劉惟一.由 Markov網(wǎng)到 Bayesian網(wǎng)［J].計(jì)算機(jī)研究與發(fā)展，2002，39（1）：87－99.

［12]王斌.信息檢索導(dǎo)論［M].第一版.人民郵電出版社，2010.

［13]Metzler D，Croft W B.Latent concept expansion using markov random fields［C]／／Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval.ACM，2007：311－318.

［14]左家莉，王明文，王希.基于 Markov網(wǎng)絡(luò)的信息檢索擴(kuò)展模型［J].清華大學(xué)學(xué)報(bào)：自然科學(xué)版，2005，45（1）：1847－1852.