检索模型及评价指标小结

经典检索模型

 

信息检索模型从它诞生到现在经历了几个不同阶段，分别是基于集合论、基于线性代数、基于统计和概率阶段。虽然专家检索不同于传统的信息检索，但两者还是有很大关联，并且本文也将基于对专家描述文档的检索作为Baseline，作为后续优化的基础。因此了解传统检索模型是很有必要的，本文下面将对不同阶段的经典模型进行摘要性介绍。

2.1.1.1  布尔模型

布尔模型是一个简单但却优雅的模型，它基于集合论和布尔代数理论。它在过去备受关注并被广泛应用到了很多早期商业搜索引擎中，近些年它逐渐被矢量空间模型和概率模型所取代，但仍然在信息检索领域占有一席之地，作为很好的Baseline来使用。

布尔模型基于如下的假设：1.一篇文档可以由词的集合表示。2.查询可以表示为关键词用AND，OR，NOT逻辑运算符连接的布尔表达式。3.如果文档中的索引词满足查询的布尔表达式，那么该文档就是相关的。

例如用户查询为“苹果 AND （乔布斯 OR ipad4）”，如果一篇文章包含“苹果”，并且同时包含“乔布斯”或者“ipad4”其中一个，那么这篇文章就是相关的，就是满足用户需求的。

布尔模型很容易理解，也很容易实现，并且有布尔代数为其提供理论支持。

但布尔模型有一个致命不足，它是严格二元相关的（0或1），即相关或者完全不相关，不能反映相关的不同程度，并且它返回的结果是无序的，过于粗糙。例如

Q=World^Cup^South^Africa^2010，Index(d)={World,Cup,South,Africa}，

d将被认为不相关。再如，

Q=World||Cup||South||Africa||2010,Index(d1)={World,Cup,South,Africa,2010}；

Index(d2)={2010}，此时d1和d2将被认为同等相关，尽管d1明显更相关一些。此外要求普通用户有能力自己构造恰当布尔表达式查询可能也不切实际。

2.1.1.2  矢量空间模型（VSM）

信息检索领域奠基人Salton于70年代提出了VSM模型，相对于布尔模型的严格二元相关，它提出了部分匹配的检索策略。VSM模型作为一种文档表示和相似度计算模型，不仅在检索领域，在文本挖掘、自然语言处理等领域也被广泛采用。

VSM将查询和文档都表示为词的集合，并映射到一个高维空间，其中每一维代表文档集合中的一个词，通过计算查询词集所代表的空间向量和文档词集所代表的空间向量的相似度作为文档和查询的相关度。

VSM将词映射到高维空间时转化为权重，比较常用的映射函数是TF*IDF，它同时考虑了词在该文档和文档集合中的出现情况。一个基础的TF*IDF公式如下：

ω=tf_i(d)*log(N/df_i)                   （2-1）

（2-2）

其中N为文档集合中文档的数目，tf_i(d)称为词频，为词i在文档d中出现的次数，df_i文档频率，为文档集中含有词i的文档数。根据TF*IDF公式，文档中某一词出现的频率越高，权值越大，说明该词表示文档的属性越强；但当文档集合中包含该词的文档越多，其权值越小，说明该词区分性较小，表示文档的属性越弱。

VSM模型中，特征权值的计算框架为TF*IDF，但具体TF，IDF计算公式却有多种变形：

一种TF变体公式为：Wtf = 1+ log(TF)，该公式是为了抑制词频过大带来的副作用。即一个单词在一篇文档中出现了10次，在另一篇文档中出现了1词，按照公式（2-1）TF会相差10倍，但实际上我们不需要这么大的差异，选取log进行缓冲，其中公式中的1是为了词频为1时的平滑。

另一种TF变体公式为： ，该公式是为了对长文档的抑制。TF表示单词在文档中的实际词频，Max（TF）代表该文档中次数最多的那个单词的词频。α是调节因子，新的研究表明α取0.4效果比较好。

一种IDF变体公式为： ，各项含义同公式（2-1），其中1是为了平滑当df等于N的情况。

根据TF*IDF计算框架，如果将一个词的TF和IDF按照高低可以分为四个象限，词的综合权重如表2.1所示。

	TF高	TF低
IDF高	高	一般
IDF低	一般	低

 

VSM假设文档在高维空间越相似，文档在内容上越相关。查询和文档的相似度可以用其映射到高维空间的向量的夹角余弦表示：

（2-2）

D和Q越相似，他们之间的向量夹角越小，cos(D，Q)越大，他们之间的向量夹角越大，说明两个向量越不同，D和Q相似度越低。但公式（2-2）存在一个明显缺陷，即对长文档过分抑制：假设长短两篇文档与检索主题相关的词权重相似，但长文档还讨论了其他主题，那么cosin公式分子部分基本相同，但分母部分长文档向量长度大于短文档长度，会导致cosin（D长，Q）小于cosin（D短，Q）。

除了用余弦计算相似度，还有如下常用相似度计算方法可以使用，如表2.2示。

表2.2  常用相似度计算方法表

方法名称	计算公式
Simple matching
Dice’s Coefficient
Jaccard’s Coefficient
Overlap Coefficient

 

通过计算查询和各文档的相似度，进而可以依此相似度将文档排序作为结果返回。VSM也很容易实现，并且它返回的相关文档是可以排序的，但当向量维度过高的时候计算将会非常耗时，系统资源利用会异常多；VSM有一个基本假设，关键词Term向量之间被认为是相互无关的，然而实际上Term之间大多是有依赖关系的，例如自然语言中词语之间存在着共现等密切联系，对此研究者后来提出了N元语言模型进行改进；除此之外VSM是个经验型模型，是靠经验和直觉不断摸索完善的，理论支持不是很充分。

 

2.1.1.3  概率模型

概率模型由Robertson和Sparck Jones在1976年提出，他们利用了相关反馈信息逐步求精以期望获得理想的查询结果。概率模型的基本思想是：根据查询Q将文档集合中的文档分为两类，与Q相关的集合R，与Q不相关的集合R’。对于相同类的文档集，各个索引项的分布相同或相近；对于不同类的文档集，各个索引项分布不同。由此可见，对文档中各个索引项的分布进行计算，依据计算出来的分布情况，我们就可以对文档和查询的相关度进行判定，即：

（2-3）

 

其中P(R=1)、P(R=0)和具体的Q相关，即P(R=1)/P(R=0)是固定的。P(d|R=1)为在与Q相关的文档集中文档d出现的概率，P(d|R=0)为在与Q不相关的文档集中d出现的概率。

到目前为止比较常用的概率模型公式是Robertson提出的BM25公式，

		（2-4）
		（2-5）

其中qtf是词t在查询中的词频，tf表示词t在文档d中的词频， 是文档长度的归一化，最后一项是平滑过的log( )，是词t的逆文档频率。k₁，b，k₃是经验参数。

概率模型有严格的数学理论基础，理论性强，是目前效果最好的模型之一，在TREC等评测项目中已经证实了这一点，但是该模型对文本集的依赖性过高，公式需要参数估计，并且依赖二元独立性假设。

2.1.1.4  语言模型

语言模型在应用于信息检索（Information Retreval）之前，已经在语音识别、机器翻译及中文分词中得到了成功应用，具有准确性高、容易训练、容易维护等优点。

语言模型建模方法大致分为两类：一种是完全依赖大规模文本数据，进行统计建模；另一种是基于乔姆斯基的形式语言为基础的确定性语言模型，该建模方法更加注重语法的分析。

从基本思路来说，其他检索模型都是从查询到文档进行考虑，即给定用户查询如何找出相关文档。然而，语言模型正相反，是一种逆向思维方式，即由文档到查询进行考虑，为每个文档建立不同的语言模型，判断由文档生成查询的概率是多少，根据这个概率大小进行排序作为最终搜索结果。

应用于IR后，语言模型和文档紧密联系，当输入查询q后，文档依据查询似然概率或者文档在该语言模型下能产生该查询的概率进行排序。如果假设词项之间相互独立，采用一元语言模型则有：

（2-6）

其中查询q中包括词t₁,…,t_M。

但语言模型面临数据稀疏问题，即查询词不在文档中出现，整个生成概率将为0，所以语言模型引入了数据平滑，即单词分布概率的“劫富济贫”，这样所有单词都有非零的概率值。语言检索模型经常引入文档集的一个背景概率来作为数据平滑。背景概率是文档集的一个整体语言模型，由于文档集规模比较大，所以绝大多数查询词都有出现，避免零概率。如果文档集合也采用一元语言模型，则一个单词的背景概率就是该单词出现的次数除以文档集所有单词的出现次数和。加入数据平滑的生成查询词概率公式为

（2-7）

其中P(t_i|C)是t_i的背景语言模型，TF/LEN是ti的文档语言模型，整个概率由两部分线性插值组成，λ属于[0,1]是一个调节因子。

后来IR中出现了很多语言模型的变种，其中一些已经超出查询似然概率模型范畴，比如基于KL距离的模型。目前各种检索评测项目中，语言模型检索方法略好于参数优化后的向量空间模型，与BM25等概率模型效果持平。

 

DFR（DivergenceFrom Randomness Models）模型由Gianni Amati, Keith van Rijsbergen在2002提出，它以统计和信息论为理论基础，是当今比较有效的检索模型之一，而且它是parameter-free的统计检索模型。

Inf(tf|d)表示文档d中每个词所包含的信息量， ，对文档排序意味着把包含信息越多的文档排到前面。

 

其中TF词在文档集中的词频，l(d)是文档d长度，tf是词在长度为l(d)的文档中的词频，TFC文档集中词的总数。

DFR分为两种类型：针对每篇文档的模型（Type I）和针对真个文档集的模型（TypeII）。

Type I DLH采用平均信息量作为词t的词权重：

Type II DPH使用另一种方式作为t的词权重：

 

 

 

检索模型评价指标

 

信息检索中最常用的两个基本指标是准确率和召回率，如图2.3所示：

 

图2.3  准确率与召回率示意图

准确率与召回率的定义如下公式：

准确率=返回结果中相关文档的数目/返回结果的数目     （2-8）

召回率=返回结果中相关文档的数目/所有相关文档的数目 （2-9）

一种融合了正确率和召回率的指标是F值：

（2-10）

TREC中的常用评测指标主要有：

 

<1表示强调准确率， >1表示强调召回率。通常F取1即准确率召回率同等看待，此时：

（2-11）

TREC中的常用评测指标主要有：

1.平均准确率AP

（2-12）

AP表示每个相关文档对应的精确率的平均值，其中Rq表示和查询q相关的文档数，DocQ(i)表示第i篇相关文档被检索时已经被检索出的文档总数，也可以理解为第i篇相关文档的位置。

2.MAP（Mean Average Precision）

MAP在AP基础上表示查询集合平均准确率均值：

（2-13）

3.P@n

表示排名最高的n篇文档中相关文档所占的比例。

4.NDCG（Normalized Discounted cumulativegain）

       每个文档不仅仅只有相关和不相关两种情况，而是可以分为不同的相关度级别，比如之前提到的五级相关，0,1,2,3,4。NDCG计算比较复杂，分为如下几个步骤，即CG（CalculatedGain），DCG（Discounted Calculated Gain），NDCG。

DCG是对多值相关的评价指标，并且包含一个位置折扣因子。

（2-14）

其中查询q的排序列表是 ， 表示在r位置的文档， 是文档的收益，一般设 = 2^l(r)-1，其中l(r)是文档r的相关度等级， 是位置折扣因子一般设为 。

NDCG是对DCG的归一化：

（2-15）

其中Z_k是文档理想的降序排序的DCG值。下面举一列，如下表2.2所示。

表2.2  准确率与召回率

Doc Id	相关度等级	Gain	CG	DCG	Max DCG	NDCG
1	5	31	31	31=31*1	31	1=31/31
2	2	3	34	32.9=31+3*0.63	40.5	0.81
3	4	15	49	40.4=32.9+15*0.5	48.0	0.84
4	4	15	64	46.9	54.5	0.86
5	4	15	79	52.7	60.4	0.87
6	…	…	…	…	…	…