基于迭代方法的多层Markov网络信息检索模型

洪 欢，王明文，万剑怡，廖亚男

（江西师范大学 计算机信息工程学院，江西 南昌330022）

1 引言

对于大部分用户来说，在没有充分了解文档集的情况下很难给出专为检索而设计的查询，搜索引擎用户经常需要重构他们的初始查询表式以获得他们所感兴趣的更好结果［1]。随着信息检索技术的不断发展，出现了许多通过使用和查询意图相关的信息来提升初始查询表式的方法。查询扩展就是一种使用和查询意图相关的附加信息来重构查询的反馈方法，它是指利用计算机语言学、信息学等多种技术，在初始查询表式的基础上通过一定的方法和策略把与原查询词相关的词、词组添加到原查询中，组成新的、更能准确表达用户查询意图的查询词序列，然后用新查询对文档重新检索，从而改善信息检索中的查全率和查准率低下的问题，弥补用户查询信息不足的缺陷。

在最近的一些研究当中，Zhai通过Boosting算法将相关模型［2－3]和混合模型［4]合并来提取查询扩展词，这种方法将两个弱模型合并成一个强模型［5－6]，但是没有考虑文档与词项之间的关联性。Lee通过聚类的方式将初始检索出的文档聚成多个簇，然后基于文档簇利用相关模型选取查询扩展词［7]，虽然考虑了文档与词项之间的关系，但是在文档表示方面存在缺陷，他仅仅将文档簇看成一个大的文档，忽略了每个文档之间的相关性。上述模型都是基于词独立性的假设，但实际上词之间的关联信息对检索效果有很大的影响。甘丽新等提出一种基于Markov概念的信息检索模型［8]，对于每个查询，使用团的提取算法在词项子空间的Markov网络中提取扩展词，该模型取得了良好的检索效果，但是该工作没有考虑文档之间和查询之间的相关性信息。付剑波等提出基于团模型的文档重排算法研究［9]，该模型通过对文档集的学习，构造文档子空间的Markov网络，提取出文档团，使用文档团信息进行文档重排，但是该工作没有将文档团信息用于查询扩展中。汤皖宁等提出基于文档团依赖的Markov网络检索模型［10]，该模型首先使用团的提取算法提取出文档团和词团，然后根据词项子空间和文档子空间的映射关系将词团分为文档依赖词团和非文档依赖词团，并用于查询扩展中。虽然扩展中充分利用了索引词项、文档子空间的Markov网络信息，但是没有考虑到查询子空间的Markov网络信息。

本文将汤皖宁等提出的基于文档团依赖的Markov网络检索模型［10]作为基础模型，对文档集做初次检索；接着，将初次检索得到的结果用于提取查询子空间的Markov网络，并提取出最大查询团；最后，结合前两个步骤构建基于迭代方法的多层Markov网络信息检索模型，即结合词项、文档和查询子空间的Markov网络信息用于查询扩展以及采用迭代方法计算文档与查询之间的相关概率。文中首先介绍了Markov网络检索模型、Markov网络的构造方法、最大团的提取等工作；接着，重点介绍了初始的基于文档团依赖的Markov网络检索模型以及最终的基于迭代方法的多层Markov网络查询扩展模型。最后，对本文提出的模型与一些经典的模型做对比实验，并对实验结果进行分析以及提出下一步的工作展望。

2 Markov网络检索模型构造方法

2.1 Markov网络检索模型

Markov网络是一种不确定性推理的有利图形工具［11]，它可以较好地表示知识关联，很容易从实例数据中训练获得，具有强大的学习功能和推导能力。通过它的无向边来解释信息检索中的语义关系更直接、恰当。Markov网络可以表示为一个二元组（V，E），V为所有节点的集合，E为一组无向边的集合，E＝｛（xi，xj）｜xi≠xj∧xi，xj∈V｝，E 中的边表示节点之间的依赖或相关关系。

基于Markov网络的检索模型分为三层：查询子空间，索引词项子空间，文档子空间。如图1所示，三层子空间构成了一个推理网络，根节点为词项子空间的词节点，我们利用词与词之间的相关性、文档与文档之间的相关性、查询与查询之间的相关性分别构造词项、文档、查询子空间的Markov网络。通过设定阈值，对三层子空间的Markov网络信息分别进行最大团的提取，得到最大词团、文档团、查询团。

在图1中，q代表用户给定的初始查询，qi代表查询子空间中的查询，tj代表索引词项子空间中的词项，dk代表文档子空间里的文档。图中从词项tj存在指向查询qi和文档dk的有向边，分别代表查询qi和文档dk由这些词项tj构成；在查询、词项和文档三层子空间中存在的多条无向边，分别表示查询间、词项间及文档间存在关联，并且边的权重取决于关联的程度。

图1 多层Markov网络结构图

2.1.1 词项子空间的Markov网络

在图1所示结构图的词项子空间中，节点表示词项，词项之间有边相连构成了词项子空间的Markov网络，边的权重表示词间的相关性程度。通过利用词的共现性来提取词与词之间的关系已经运用到许多研究中，在计算词共现的词频中，一般可以以整个文档、段落或是一个固定长度为窗口［12]。出于考虑效率方面的因素，本文选择文档作为窗口单位。实验中采用词的共现性来提取词项与词项之间的关系，鉴于Markov网络的无向性，因此在构造词项子空间的Markov网络时，采用两个词的综合共现性来计算，如式（1）、（2）所示。

其中ti和tj指两个词项，C（ti，tj）指在训练文档集中ti和tj在同一篇文档中同时出现的频率，C（ti）和C（tj）分别表示在训练文档集中ti和tj出现的频率，Sim（ti，tj）表示ti和tj之间的相关性，Sim 值越大，两个词的相关性就越高。当Sim值大于给定的阈值时，则词项ti和tj相互依赖，即在词项子空间的Markov网络中有边相连。

2.1.2 文档子空间的Markov网络

同样，在图1所示的文档子空间中，节点表示文档，文档之间有边相连构成文档子空间的Markov网络，边的权重表示文档间的相关性程度。本文中的文档均表示为向量，采用文档向量之间的夹角余弦公式来度量文档之间的相关性，文档与文档之间的相关性记为Sim（di，dj），计算公式如式（3）所示。

当Sim（di，dj）的值大于给定的阈值时，则文档di和dj相互依赖，即在文档子空间的Markov网络中有边相连。

2.2 团的提取

通过三层子空间的Markov网络结构分析可知，它实际构成一个相容关系图。在相容关系图中，我们发现许多完全多边形，就是每个节点都与其他节点相连的多边形，即构成了团。团的提取分为索引项词团的提取、文档团的提取和查询团的提取。

对于词项和文档子空间的Markov网络，团内的词和文档彼此相互依赖，即存在某种语义关联，可以认为它们集中表达同一个概念［13]（或主题）。本文按照词的最大团以及文档团与词团之间的映射关系来选择扩展查询词，以最大团为单位进行扩展，具体最大团的提取方法可以参照文献［8]。如果一个词团中的某个词项同时映射到一个文档团的多篇文章，则认为这个词比其他的词对主题更具有代表性，在后续的检索阶段中提高包含此类词项词团的权重，我们将这种词项称为文档依赖词。

在词项和文档子空间的Markov网络中，关键的步骤是提取出最大词团、文档团以及将最大词团映射到文档团上。按照最大团的相关性权重来选择用于扩展的最大词团，以最大团为单位作为一个概念整体扩展进来，这样有利于把语义比较集中的词扩展进来，同时也提高了那些与某个查询词的关系不是很强，但与查询主题很相关的词加入查询扩展的可能性，从而提高检索效果。在图1的词项子空间中，词项t2的最大团有｛t2、t4、t5｝，｛t2、t3、t6、t7｝，且每个最大词团会有相应的权重，取决于团内各词项间的依赖程度。

2.3 词团与文档团的映射

词团与文档团之间的映射关系可以用来强化索引词项与用户给定的初始查询之间的关联性。如果最大词团中的一个索引词项出现在一个文档团的多篇文档中，则认为包含该词项的词团与该文档团存在语义上的关联性，同时也认为这个词团与查询的主题更加相关。因此，本文通过这种映射关系将最大词团分为文档依赖词团和非文档依赖词团，并将这两种词团用于查询扩展。由于文档依赖词团可能对文档团的主题更具代表性，因此，在检索阶段会给文档依赖词团赋予更大的权重。如图1所示，词项子空间内有三个最大词团 T1＝｛t1、t4、t5｝、T2＝｛t2、t4、t5｝和 T3＝｛t2、t3、t6、t7｝，文档空间内有三个最大文档团 D1＝｛d1、d2、d3、d5｝、D2＝｛d2、d3、d4｝、D3＝｛d2、d4、d6｝。词项t4在文档团 D1中的所有文档中都出现，所以词团T1和T2都是文档依赖词团，而词团T3中的任何词项都没有在同一个文档团中的所有文档中出现，所以词团T3是非文档依赖词团。

2.4 基于文档团依赖的Markov网络检索模型

对于用户给定的初始查询q，通过利用词项、文档子空间的Markov网络信息，计算文档集D中任意文档dj∈D和查询q的相关概率p（dj｜q）。然后按照p（dj｜q）的大小排列文档集中的文档，从而得出我们需要的文档。由左家莉等提出的基于Markov网络的信息检索扩展模型［14]可得：

本文采用BM25类似权重方式来计算wi，q和wi，j，具体的计算公式参照文献［14]。

在查询扩展阶段，扩展词的选择方案采用基于最大团的方式，以最大词团为单位，作为一个概念整体对初始查询表式中对应的词项进行扩展。在选取最大词团阶段我们将词团分为两类，分别是：文档依赖词团和非文档依赖词团。利用词团与文档团之间的映射关系来提取文档依赖词团，并在检索阶段加大这类词团的权重。对于用户给定的初始查询q，文档和查询的相关概率计算公式由式（4）修正为：

其中，α：非文档依赖词团平滑参数（0≤α≤1），β：文档依赖词团平滑参数（0≤β≤1），α＋β＜1，指用式（1）计算词项之间相关性的值。

式（5）中的Cmax（t）代表词项t的最大词团，在提取最大词团时，会给每个词项的最大词团赋予不同的权重。本文提出这样的假设：最大词团的权重越大，则它所表达的概念与查询主题越相关，在查询扩展的时候优先被考虑进来。在实验中，利用式（5）对文档集做初次检索，通过调整最大词团的个数以及式（5）中的平滑参数，使该模型的检索效果达到稳健。

3 基于迭代方法的多层Markov网络信息检索模型

3.1 查询子空间的Markov网络

在图1中，查询子空间中的节点（查询）之间也有边相连，构成查询子空间的Markov网络。本文中查询之间的相关性由查询返回的结果集合中排名靠前的文档所决定，也就是利用相关反馈方法中的隐式反馈信息［1]。通过使用2.4节介绍的基于文档团依赖的 Markov网络检索模型［10]对文档集做初次检索，得出用户给定查询返回的结果集合，取结果集合中查询qi返回的前2篇文档，将这2篇相关文档合并成一个新的“文档”Di，采用类似2.1.2节中文档之间相关性的度量方法来确定查询间的相关性，记为Sim（qi，qj），计算公式如式（6）所示。

式（7）中的P′（dj｜qi）是在模型中加入了查询子空间的Markov网络信息，计算文档dj与初始查询q的最大查询团（q）中的其他查询qi的相关概率，计算公式类似于式（5），如式（8）所示：

当Sim（qi，qj）的值大于给定的阈值时，则查询qi和qj相互依赖，即在查询子空间的 Markov网络中有边相连。

3.2 查询团的提取

使用式（6）计算出查询间的相关性，从而构建查询子空间的Markov网络。将所得到的Markov网络信息用于最大查询团的提取，具体的提取方法与2.2节中的方法一致，所得到的查询子空间的Markov网络信息也可以用在查询扩展中，从而提高检索效果。

3.3 基于迭代方法的多层Markov网络查询扩展模型

结合2.4节基于文档团依赖的Markov网络检索模型［10]以及最大查询团来构建本文的基于迭代方法的多层Markov查询扩展模型。这样，就将词项、文档和查询三层子空间的Markov网络信息用于查询扩展中。加入了查询子空间的Markov网络信息后，将文档和查询的相关概率计算公式由式（5）修正为：

其中，α：非文档依赖词团平滑参数（0≤α≤1），β：文档依赖词团平滑参数（0≤β≤1），α＋β ＜

构造本文基于迭代方法的多层Markov网络信息检索模型时，迭代的具体步骤如下：

1）第一次迭代过程：

a）利用式（5）中得到的检索结果提取出最大查询团信息；

b）取出检索结果中文档与查询的相关概率值，并代入式（7）中计算新的相关概率，即将式（5）中的P（dj｜q）→P′（dj｜q）；

c）用式（7）对文档集进行重新检索；

2）第n（n＞1）次迭代过程：

a）从前一次（n－1）迭代过程中得到的检索结果中提取出最大查询团信息；

b）将检索结果中文档与查询的相关概率值代入式（7）中重新计算文档得分；

c）利用式（7）对文档集再次检索。

重复步骤2）进行多次迭代，直到实验的检索效果收敛（即检索效果已经不再提高或者提高的比例不大）为止。实验过程中，通过调整最大词团的个数以及式（7）、（8）中的平滑参数θ、α、β，使该模型的检索效果达到稳健。

4 实验设计和结果

4.1 对比实验

本文采用的是一种常用的测试集，该测试集由adi、med、cran、cisi及cacm五个标准测试文档集组成，常用于评价检索系统的性能。五个测试文档集的文档较小，且评价效果良好，下载地址：ftp：／／ftp.cs.cornell.edu／pub／smart.测试数据集的具体情况如表1所示。

表1 实验中的数据集

为了验证基于迭代方法的多层Markov网络信息检索模型（IMMR）的检索效果，本文选取使用普通BM25模型和基于Markov概念的信息检索模型［8]（MRC）来进行对比实验。并把基于文档团依赖的Markov网络检索模型［10]作为Baseline，与本文提出的模型的主要区别在于查询扩展中没有利用查询子空间的Markov网络信息，以及没有采用基于迭代的方法来计算文档与查询的相关概率。在表中可以看出本文提出的检索模型实验结果比起基准方法有比较大的提高，我们采用的评价指标是3－avg和11－avg。3－avg和11－avg分别代表一组测试查询在3个召回率点（0.2，0.5，0.8）和11个召回率点（0，0.1，0.2，……，1.0）上精确率的平均值，这种平均精度—召回率数值如今已成为信息检索系统的标准评价指标，在信息检索文献中被广泛采用［1]。本文实验的具体结果见表2和表3。

表23－avg实验结果

表311－avg实验结果

从实验结果中，我们可以发现本文提出的模型在数据集cacm和adi上相对于Baseline模型有最大幅度的提高。对于数据集cacm主要是因为其含有的文档数最多，文档团与词团的映射关系更为明显，可以有效地将最大词团划分成文档依赖词团和非文档依赖词团，并提高从较多的文档里找到与用户需求真正相关文档的概率；对于adi数据集，虽然数据集最小，但是由于其自身的特殊性，可以加入的修正信息最多，也能取得较好的检索效果。而数据集med虽然包含的词项数多，但文档总数及查询数较少，构造出的文档、查询子空间的Markov网络信息较少，使得查询扩展时加入的修正信息少，导致最后的检索效果提升不明显。

本文提出的基于迭代方法的多层Markov网络信息检索模型中，采用迭代的方法计算文档与查询的相关概率，以及从检索结果集合中构造查询子空间的Markov网络。理论上，在检索结果收敛之前，每一次迭代过程都能将与用户查询更加相关的文档排在前面，从而构造出更加符合用户查询意图的查询子空间的Markov网络，并最终提高检索效果。实验中我们发现，迭代2～3次检索结果就基本达到收敛，且第1次迭代过程检索效果提升的幅度较大。主要的原因有：1）第1次迭代过程中，在基于文档团依赖的 Markov网络检索模型［10]的基础上初次加入了查询子空间的Markov网络信息，使得检索结果有明显提高；2）本文用于构造查询子空间的Markov网络采用的方法是从检索结果集合中取出查询qi返回的前2篇文档，来计算查询间的相似性，加上实验中采用的数据集文档数相对较少，返回的前2篇文档不会有太大改变，使得后续构造的查询子空间的Markov网络基本不变。未来的工作中将在更大的数据集上做测试，同时改进构造查询子空间的Markov网络的方法（比如采用查询日志信息），相信通过迭代方法能够取得较好的检索效果。

4.2 相关性阈值的选取

在实验中，发现调整词项间、文档间以及查询间相关性的阈值会使得提取最大团的计算量变化很大，最大团的个数以及最大团中包含词、文档和查询的数量也会有较大的影响，最终对检索效果也会产生比较明显的影响。对于词项间相关性阈值的设定，数据集adi中取0.7，其余四个数据集均取0.8，这是因为adi数据集词项数最少，需要加入用于构造词项子空间的Markov网络的词项数多些。词项间的相关性阈值越大，得到的最大团的个数s越少，相反则最大团的个数s越多，用于提取最大团的计算时间也越长。当词项网络固定时，用于加入查询扩展中词项的最大团个数s会对实验结果产生较大影响：一开始随着s的增加，检索效果会随之提高；当s增加到一定的数值时，检索效果达到最优，若再增大则结果会逐渐降低。在文档间相关性阈值的设定上，根据5个数据集中文档总数的不同取不同的值，实验中数据集adi的文档数最少，取阈值0.1，med取0.2，cran、cisi、cacm取0.3。同样地，对于查询间相关性阈值的取值也与数据集中包含的查询数和需要加入的修正信息量有关，实验中数据集adi的查询数少且可加入修正的信息量大，取阈值0.2，med、cisi、cacm 取0.3，cran数据集含有的查询数最多阈值取0.5。

4.3 平滑参数的调整对实验结果的影响

本文提出的模型中包含θ、α、β这3个平滑参数，分别对应加入查询团信息的权重、非文档依赖词团权重以及文档依赖词团权重。通过调整平滑参数的取值，使检索效果达到最优，由于文档依赖词团可能对文档团的主题更具代表性，需要赋予更高的权重。因此，实验中平滑参数α和β初始值为0，令参数α以0.01，β以0.03的增量来循环计算文档与查询的相关概率，并记录在每次循环中各参数取值确定时的实验结果。实验中通过调整3个平滑参数会使得检索结果有较大影响，以数据集adi和cacm为例，图2和图3表示在第一次迭代过程中，调整平滑参数对实验结果的影响（实验中，取θ＝α，β＝3α）：

图2 adi数据集的实验结果

图3 cacm数据集的实验结果

在图2和图3中，横坐标表示α的取值，纵坐标表示平均准确率。实验表明，α和β的取值对结果的影响遵循一定的规律，在一定的范围内平滑参数α越大，检索效果越好，但达到一定数值以后结果开始变差。另外，它们的取值与文档集规模也有一定的关系。在实验当中，当文档集规模较小时，α和β取较大的数值实验结果才能达到相对较好水平，如上图2，3所示，在adi数据集中α＝0.06，β＝0.18时，实验结果达到稳健，然而在cacm数据集中α＝0.02，β＝0.06时，实验结果才能达到稳健，这是因为adi数据集中文档数目要远远少于cacm数据集中的文档数目，用于修正查询的信息量少，需要通过提高修正信息的权重来取得好的检索效果。

5 总结与展望

本文通过对训练文档集和检索结果集合的学习，构造出词项、文档和查询三层子空间的Markov网络，将得到的三层Markov网络信息用于最大词团、文档团和查询团的提取，利用文档团与词团之间的映射关系将最大词团分为文档依赖词团和非文档依赖词团，在查询扩展中加大文档依赖词团的权重。模型中通过迭代的方法从已有的检索结果集合中提取出最大查询团信息，并迭代地计算文档与查询的相关概率，直到检索效果收敛。下一步的工作有：（1）在更大的数据集上（比如TREC数据集）进行实验检测该模型的通用性；（2）本文是对已有的检索结果集合采用隐式的相关反馈方法，收集检索结果返回的前2篇相关文档信息来计算查询间的相关性，未来我们将利用用户查询日志来构造查询子空间的Markov网络；（3）随着数据集规模的增大，构造Markov网络计算量会变得非常大。因此，在面对海量数据检索时，一方面需优化Markov网络构造方法；另一方面可将词项、文档和查询间的相关性计算算法采用MapReduce编程模型并行化，加快执行效率。

［1]黄萱菁，张奇，邱锡鹏.现代信息检索［M].第一版.机械工业出版社，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].江西师范大学，2007.

［9]付剑波，王明文，罗远胜，等.基于团模型的文档重排算法研究［J].中文信息学报，2009，23（1）：71－78.

［10]汤皖宁.基于文档团的 Markov网络检索模型［D].江西师范大学，2013.

［11]何盈捷，刘惟一.由 Markov网到 Bayesian网［J].计算机研究与发展，2002，39（1）：87－99.

［12]王斌.信息检索导论［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网络的信息检索扩展模型［J].清华大学学报：自然科学版，2005，45（1）：1847－1852.