基于混合相关的Markov网络信息检索扩展模型

甘丽新，涂 伟，王明文，石 松

(1. 江西科技师范大学 光电子与通信重点实验室,江西 南昌 330038；2. 江西师范大学 计算机信息工程学院,江西 南昌 330022；3. 上海财经大学 公共经济与管理学院,上海 200093 )

1 引言

随着互联网的飞速发展，信息检索技术的进步使人们在信息海洋中捞到所需“珍宝”的愿望得以实现。然而网络信息的膨胀使用户很难快速、准确的从浩瀚的信息资源中找到所需的信息，即所谓的“信息爆炸，资源匾乏”。其原因在于用户提供的查询信息过少、查询表达模糊不清等，使得在查询时出现难以克服的问题,即信息迷向、信息过载和词不匹配而造成信息检索的查全率和查准率都较低。查询扩展是解决上述问题的关键技术之一，它指的是利用计算语言学、信息学等多种技术，在原始查询的基础上加入与用户用词相关联的词，组成新的更长、更准确的查询，然后再次检索文档，以改善检索系统的查全率和查准率，弥补用户查询信息不足的缺陷[1-4]。因此，研究信息检索中的查询扩展技术，通过对用户的初始查询进行扩展和重构，具有重要的理论价值和实践意义[5-7]。

查询扩展一般包含两个基本的步骤: 利用新的词对原始查询进行扩展；在扩展查询中给词重新加权[8]。因此，查询扩展技术的核心问题是如何选择高质量的扩展词和如何对词进行重新加权。在已有很多研究中均认为： 若一个词与查询中某个原始查询词的直接相关性越高，则该词与查询主题越相关，因而被扩展的机会越大[9]。虽然直接相关性扩展对检索效果有所提高，但却忽略了词间间接相关性的作用。钟茂生提出了利用二分图模型来求解和量化词汇间间接相关关系的方法来解决在统计语料库中没有出现的词汇对的相关关系量化求解问题[10]。文献[11]则是通过对训练文档集的学习，利用Markov网络中的无向边，通过多层推理激活与查询词密切相关的词作为查询附加证据源加入到查询扩展中。文献[12]则提出了一种全新的全局分析查询扩展方法，利用Markov转移矩阵计算词间深层次关系的多步转移间接关系对查询进行处理。上述方法的检索效果均优于基于直接相关词扩展的检索效果。因此，本文的工作依然是建立在Markov网络的基础上，通过提取Markov网络中的词团信息来量化词间的混合相关性，即把直接相关和间接相关的量化值进行加权处理，将强化后的词间混合相关性应用于信息检索扩展模型中。实验表明： 基于混合相关的Markov网络信息检索扩展模型的检索效果优于基于直接相关的查询扩展模型的检索效果。同时，与基于团的Markov网络信息检索扩展模型相比，该模型最大的优势在于大大减少了词团提取的计算开销。

2 基于混合相关的Markov网络信息检索扩展模型

2.1 模型描述

Markov是一种较好的表示知识关联的图形表示方法，很容易从实例数据中训练获得，它的无向性更好地解释信息检索中知识之间的关系，具有强大的学习功能和推导能力，通过对文档集的学习，利用词项之间的关系构造Markov网络，通过词项之间的关系对查询进行扩展[9]。一个Markov网络可以表示为一个二元组(V,E),V为所有节点的集合,E为一组无向边的集合，E={(xi,xj)|xi≠xj∧xi,xj∈V},E中的边表示变量之间的依赖关系。在Markov网络中，每个节点v条件独立于其邻居节点给定的v的非邻居节点的任意节点子集，节点只和其直接相邻节点存在依赖性，即满足p(vi|vj)=p(vi|vj(vi,vj)∈E)[9]。在图1所示的Markov网络中，图中节点表示词，边表示词间关系。

图1 Markov网络结构

2.2 词间相关性计算

对于给定的词t1和t2，在Markov网络图中主要存在三类词间相关性： (1)直接相关性： 即可从数据集中直接统计出现的词间关系,见图2(a)所示，t1和t2直接有边相连；(2)间接相关性： 从数据集中无法统计出现或者词间通过第三方词变量隐含导出的关系，即t1和t2没有直接边相连，而是通过词t3导出，如图2(b)；(3)混合相关性： 词间既有直接相关性，又有间接相关性，如图2(c)所示。

图2 词间的三类相关性

在现有研究中，度量词间相关性的方法主要有潜在语义索引、协方差、词的共现性、互信息和条件概率等[9]。在度量词间的直接相关性时，本文选取了条件概率综合指标。两个词ti和tj之间的直接相关度记为RD(ti,tj)，如式(1)所示。

其中:p(ti|tj)是在被统计的数据集中，在词tj出现的条件下词ti出现的概率,0≤RD(ti,tj) ≤1。在实际计算中，用词频来代替相应变量的概率。

钟茂生利用二分图模型来求解和量化词汇间间接相关关系,最后将直接相关关系和间接相关关系量化值进行加权处理, 并将加权结果看成是两词汇之间的量化相关关系[10]。文献[11-12]则是通过多层推理激活与查询词密切相关的词来寻找查询附加证据源或是利用Markov转移矩阵计算词间多步转移的间接关系。本文则通过提取Markov网络中的词团信息来量化词间的混合相关性，即把直接相关和间接相关的量化值进行加权处理，将强化后的词间混合相关性应用于信息检索扩展模型中。考虑到影响词间相关性的因素[13]： (1)词间的直接或间接连接边数越多，其间的相关度越大；(2)词间的相隔路径越长，其间的相关度越小。同时鉴于文献[11-12]的实验表明： 词间间接相关性的路径不超过2对于检索最好。因此，综合考虑上述因素，本文将仅仅考虑利用3阶词团来量化词间的间接相关性。因此，上述图2中的词ti和tj的间接相关性将由图3所示的3阶词团clique(t1,t3,t2)和clique(t1,t4,t2)来量化。

图3 3阶词团

我们可以用下面的式(2)来求解词ti和tj的间接相关性RI(ti,tj)：

其中：RD(ti,tk)表示ti和tk之间的直接相关度；RD(tk,tj)表示tk和tj之间的直接相关度；clique(ti,tk,tj)表示包含词ti，tk和tj的3阶词团；m表示词团clique(ti,tk,tj)的总数；0≤RI(ti,tj) ≤1。

如图3所示，对于给定的词ti和tj，由它们构成的3阶词团即包含词间的直接相关性，也包含词间的间接相关性，即词ti和tj存在混合相关性。因此本文仍然采用类似文献[10]的加权方法量化词间混合相关性RM(ti,tj)：

其中：θ为间接相关和直接相关的加权因子，0≤θ≤1。RD(ti,tj)和RI(ti,tj)分别可以由式(1)和(2)得到。

2.3 查询扩展

查询扩展的目的在于将有利于提高检索性能的信息加入到检索过程中，其一般包含两个基本的步骤:对原始查询进行扩展和利用重新加权的扩展词进行检索。在查询扩展过程中，本文依然采用此策略： 给定一个查询，对于一个查询词，若一个扩展候选词与原始查询词的混合相关性越大，则认为该词与查询主题越相关，越有利于检索。因此,给定查询Q和任一文档D,计算其相关概率。本文采用了Markov网络检索扩展模型来计算相关概率，见式(4)。

其中：RM(ti,tj)表示词间混合相关性。

将式(3)代入式(4)，可得式(5)。

其中： λ为平滑参数(0≤λ≤1)。在实验中，本文通过同时调整平滑因子λ和θ，使得模型达到检索性能的最优效果。

3 实验设计与分析

为了验证本文提出的基于混合相关的Markov网络信息检索扩展模型对检索性能的影响，我们在5个常用的标准数据集进行了一些实验，下面介绍使用的数据集、预处理、实验步骤、结果及相关分析。

3.1 数据集与预处理

本文使用了5个标准数据集adi, med, cran, cisi及cacm。其中： adi是信息科学方面的文档集(82篇文档和35个查询)；med是医学方面的文档集(1 033篇文档和30个查询)；cran是航空方面的文档集(1 400篇文档(含2篇空文档)和225个查询)；cisi是图书馆科学方面的文档集(1 460篇文档和76个查询)；cacm是计算机科学方面的文档集(3 024篇文档和64个查询)[14]。在预处理阶段,主要提取文档中的