基于Indri的檢索模型研究

王莉軍

（渤海大學(xué) 遼寧 錦州 121013）

Indri是開源的信息檢索工程Lemur的一個(gè)子項(xiàng)目。Indri是一個(gè)完整的搜索引擎，支持各種不同格式文本的索引創(chuàng)建，提出了優(yōu)秀的文檔檢索模型，支持結(jié)構(gòu)化查詢語(yǔ)言，在研究和實(shí)際應(yīng)用領(lǐng)域都有比較高的價(jià)值。Indri系統(tǒng)采用C++語(yǔ)言編寫，提供了方便的API供使用者調(diào)用，由于項(xiàng)目本身開源，對(duì)于開發(fā)者而言，也可以方便的對(duì)其進(jìn)行二次開發(fā)。

1 Indri檢索模型

Indri結(jié)合了推理網(wǎng)絡(luò)模型 （Inference net）和語(yǔ)言模型（language modeling）的優(yōu)點(diǎn)，提出了一套檢索模型，其利用推理網(wǎng)絡(luò)模型的優(yōu)勢(shì)來(lái)支持比較復(fù)雜的結(jié)構(gòu)化查詢（結(jié)構(gòu)化通常指查詢語(yǔ)言中的用來(lái)表達(dá)檢索文檔中詞與詞之間聯(lián)系的operators），又利用語(yǔ)言模型及平滑技術(shù)對(duì)推理網(wǎng)絡(luò)中的一些節(jié)點(diǎn)進(jìn)行有效的預(yù)估，從而使查詢得到比較好的效果[1]。這之前，單純的推理網(wǎng)絡(luò)模型節(jié)點(diǎn)的預(yù)估采用的是規(guī)格化的tf.idf（這個(gè)值與詞在文檔中出現(xiàn)的頻率稱正比，與包含該詞的文檔數(shù)成反比）權(quán)重，而單純的語(yǔ)言模型則無(wú)法支持結(jié)構(gòu)化查詢。所以Indri檢索模型采用了兩種模型相結(jié)合的方式[2]。

推理網(wǎng)絡(luò)模型網(wǎng)絡(luò)圖如圖1所示，實(shí)際上是一個(gè)貝葉斯網(wǎng)絡(luò)（Bayesian networks）。貝葉斯網(wǎng)絡(luò)是一個(gè)有向，無(wú)環(huán)圖。

網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)代表一個(gè)事件，有一個(gè)連續(xù)或者離散的結(jié)果集。每個(gè)非根節(jié)點(diǎn)存儲(chǔ)了一個(gè)條件概率表，這個(gè)條件概率表完全描述了與給定父節(jié)點(diǎn)的情況下該節(jié)點(diǎn)出現(xiàn)相關(guān)聯(lián)的結(jié)果集的概率。每個(gè)與根節(jié)點(diǎn)相關(guān)聯(lián)的結(jié)果集被指派了一個(gè)先驗(yàn)概率。這樣在已知網(wǎng)絡(luò)圖，先驗(yàn)概率，條件概率表和節(jié)點(diǎn)代表的事件之后，就可以通過(guò)網(wǎng)絡(luò)計(jì)算出檢索文檔中出現(xiàn)查詢的概率，并按照這個(gè)概率值的大小進(jìn)行排序輸出。

圖1 推理網(wǎng)絡(luò)模型網(wǎng)絡(luò)圖Fig.1 Inference network network diagram

主要包含有以下幾類節(jié)點(diǎn)[3]：

1）文檔節(jié)點(diǎn) D（Document Node）；

2）平滑參數(shù)節(jié)點(diǎn) alpha，beta（Smoothing parameter nodes）；

3）模型節(jié)點(diǎn) θ（Model nodes）；

4）特征表示節(jié)點(diǎn) r（Representation concept nodes）；

5）查詢節(jié)點(diǎn) q（Belief nodes）；

6）信息需求節(jié)點(diǎn) I（Information need node）。

文檔節(jié)點(diǎn)（Document Node）：文檔節(jié)點(diǎn)是文檔表示的一個(gè)隨機(jī)值。Indri采用二進(jìn)制特征向量集對(duì)文檔進(jìn)行表示，而不是一般模型中單純的term序列，文檔的特征向量表示可以挖掘出更多的文本的信息，例如短語(yǔ)，是否是大寫字母詞等。文檔中每個(gè)term的位置被一個(gè)特征向量表示，向量中的元素表示特征的有無(wú)。如此一來(lái)可以將文檔看作一個(gè)多伯努利分布（Multiple-Bernoulli distribution）的抽樣。

舉一個(gè)文檔表示很簡(jiǎn)單的例子，假設(shè)文檔是由5個(gè)詞組成的，則我們用下面12個(gè)特征組成的特征序列來(lái)表示文檔，如下[4]，

Document：A B C A B

假設(shè)特征序列是[A B C AA AB AC BA BB BC CA CB CC]

平滑參數(shù)節(jié)點(diǎn)：是為模型節(jié)點(diǎn)提供平滑參數(shù)。

模型節(jié)點(diǎn)Model nodes（M）：模型節(jié)點(diǎn)代表所謂的特征語(yǔ)言模型。在Indri框架中，它們是平滑過(guò)的多伯努利分布，該分布是對(duì)文檔表示的一個(gè)建模。網(wǎng)絡(luò)中可能會(huì)有不止一個(gè)模型節(jié)點(diǎn)，與同一文檔的不同表示相關(guān)聯(lián)，如上圖所示，模型節(jié)點(diǎn)包括title，body，h1等3個(gè)模型節(jié)點(diǎn)，分別為文檔的title，body，h1部分的表示，這樣就允許模型通過(guò)不同的文檔表示來(lái)進(jìn)行預(yù)估，合并。

這里需要計(jì)算 P（M|D），

特征表示節(jié)點(diǎn)Representation concept nodes（r）：特征表示節(jié)點(diǎn)是與上述文檔表示中提到的特征向量直接相關(guān)的二進(jìn)制隨機(jī)值。這里，同樣的特征節(jié)點(diǎn)可能會(huì)在網(wǎng)絡(luò)中出現(xiàn)多次，因?yàn)槊總€(gè)相同的特征節(jié)點(diǎn)可能會(huì)有一個(gè)不同的父節(jié)點(diǎn)。

查詢節(jié)點(diǎn)Belief nodes（q）：查詢節(jié)點(diǎn)是用來(lái)合并特征節(jié)點(diǎn)或者其他查詢節(jié)點(diǎn)的二進(jìn)制隨機(jī)值。每個(gè)查詢節(jié)點(diǎn)關(guān)聯(lián)到不同的條件概率表，允許節(jié)點(diǎn)以多種不同的方式合并。查詢節(jié)點(diǎn)是根據(jù)Indri的結(jié)構(gòu)化查詢動(dòng)態(tài)的添加到網(wǎng)絡(luò)中，因此網(wǎng)絡(luò)拓?fù)涫请S著每次查詢改變的。這使得網(wǎng)絡(luò)很強(qiáng)大，根據(jù)不同的查詢式，使用不同的打分方法。

信息需求節(jié)點(diǎn)Information need node（I）：信息需求節(jié)點(diǎn)可以看作一個(gè)簡(jiǎn)單的查詢節(jié)點(diǎn)，將所有的查詢節(jié)點(diǎn)合并到一個(gè)節(jié)點(diǎn)，這個(gè)節(jié)點(diǎn)作為rank的基礎(chǔ)[5]。

也就是說(shuō) rank的依據(jù)是 P（I=1|D，alpha，beta）。

例如一個(gè)查詢：#weight（2.0#or（#1（north korea）iraq ）1.0 policy），查詢的意思大概是 “包含韓國(guó)或者伊朗以及policy的文檔，并且包含north korea或者iraq所占的比重系數(shù)為2.0，而包含policy的比重系統(tǒng)為1.0”。推理網(wǎng)絡(luò)如圖2所示。

圖2 推理網(wǎng)絡(luò)Fig.2 Inference network

再例如一個(gè)查詢：#combine（ #uw8（ hurricane wind ）.（title）damage），這個(gè)查詢的大概意思是“文檔題目域中包含一個(gè)8個(gè)詞的窗口，窗口中可以無(wú)序的包含hurricane和wind兩個(gè)詞，并且文檔中包含damage這個(gè)詞”。推理網(wǎng)絡(luò)如圖3所示。

圖3 推理網(wǎng)絡(luò)Fig.3 Inference network

2 Indri查詢語(yǔ)言

為了充分利用上面提到的檢索模型，Indri提供了一套查詢語(yǔ)言可以表達(dá)復(fù)雜的概念。Indri查詢語(yǔ)言是一種結(jié)構(gòu)化查詢語(yǔ)言，是由一些operation組成的，每個(gè)operation代表了推理網(wǎng)絡(luò)中的一個(gè)查詢節(jié)點(diǎn)（即q節(jié)點(diǎn)）[6]。

Operation可以分為以下幾類：

1）Basic operation

第三，時(shí)間和空間延展性的變化帶來(lái)的影響?；ヂ?lián)網(wǎng)上沒(méi)有時(shí)間和空間的限制，企業(yè)只需花費(fèi)較少的成本就可以加入到全球信息網(wǎng)絡(luò)和貿(mào)易網(wǎng)絡(luò)中，與消費(fèi)者進(jìn)行溝通，將產(chǎn)品的信息傳遞到消費(fèi)者中去。網(wǎng)絡(luò)商城的空間可以無(wú)限擴(kuò)張，可以陳列無(wú)限多的商品，消費(fèi)者通過(guò)互聯(lián)網(wǎng)可以用很低的價(jià)格選購(gòu)商品，所看到的商品比任何一間大商場(chǎng)的產(chǎn)品都多，方便消費(fèi)者進(jìn)行商品的比較和擇優(yōu)。

Indri查詢語(yǔ)言的基本操作是繼承Inquery結(jié)構(gòu)化查詢語(yǔ)言的，舉一些簡(jiǎn)單的例子：

#uwN（t1 t2…）包含N個(gè)單詞的無(wú)序窗口

#odN（t1 t2…）包含N個(gè)單詞的有序窗口

#combine（q1 q2…） 合并查詢q1和q2

#weight（w1q1 w1q2…） 合并查詢q1和q2并且設(shè)置了每個(gè)查詢的權(quán)重

#filrej（c s） 當(dāng)c不滿足的情況下計(jì)算表達(dá)式s

2）Field operation

這類操作符是為了支持結(jié)構(gòu)化文檔設(shè)計(jì)的。最簡(jiǎn)單的形式，比如term.field，意思是term只有出現(xiàn)在field時(shí)才是與查詢相關(guān)的。

域可以是文檔中的任何打了標(biāo)簽的信息。例如可以是文檔的一大段（如一個(gè)章節(jié)），一小段（如一個(gè)自然段），或者只有幾個(gè)句子（如名詞短語(yǔ)等）。一個(gè)域也可以多次出現(xiàn)在文檔中。

例如wash.np就可以用來(lái)實(shí)現(xiàn)這樣的查詢，“查找出現(xiàn)在名詞短語(yǔ)中的wash”。

3）Extent retrieval

Indri也支持用域來(lái)在某一區(qū)域中打分。例如查詢#combine[field]（q1，…qn），在 field 指定的區(qū)域中對(duì)（q1，…qn）進(jìn)行打分和排序。這樣可以方便地支持類似段落查詢或者語(yǔ)句查詢等這樣的需求。

4）Date and numeric retrieval

Indri來(lái)識(shí)別數(shù)字相關(guān)的性質(zhì)，包括日期等。為了查詢數(shù)字相關(guān)的性質(zhì)，Indri提供了#less，#greater和 #equal等操作。對(duì) 于 日 期 的 查 詢 ，Indri提 供 了 #date：before，#date：before 和#date：before 等操作。

一些相關(guān)操作符的計(jì)算如下[5]：

3 結(jié) 論

Indri的檢索模型合并了推理網(wǎng)絡(luò)模型和語(yǔ)言模型，可以比較好的支持結(jié)構(gòu)化查詢和推理網(wǎng)絡(luò)節(jié)點(diǎn)的預(yù)估，里面還涉及了多伯努利分布，貝葉斯方法等數(shù)學(xué)行比較強(qiáng)的推導(dǎo)過(guò)程，從測(cè)試結(jié)果來(lái)看，查詢效果比較好，具有較大的參考實(shí)用價(jià)值。

[1]Strohman T，Metzler D，Turtle H，et al.Indri.A language model-based serach engine for complex queries，IA 2005[C]//Proceedings of the 2nd International Conference on Intelligence Analysis （to appear），2005：5-10.

[2]Strohman T.Dynamic collections in Indri[C]//Technical Report IR-426， University of Massachusetts Amherst，2005：124-125.

[3]Strohman T.Low Latency Index Maintenance in Indri[C]//IR-503， University of Massachusetts Amherst，2006：54-58.

[4]Metzler D，Croft W B.Combining the language model and inference network approaches to retrieval[C]//Info.Proc.and Mgt，2004，40（5）：735-750.

[5]Metzler D，Lavrenko V，Croft W B.Formal multiple Bernoulli models for language modeling[C]//2004：540-541.

[6]Zhai C，Lafferty J.A study of smoothing methods for language models applied to information retrieval ACM Trans.Inf.Syst[C]//2004：179-214.