美文网首页搜索引擎
检索模型与检索排序

检索模型与检索排序

作者: SHAN某人 | 来源:发表于2018-03-18 18:16 被阅读24次

    1. 用户查询与返回结果相关度度量

    1.1 相似性计算:空间向量余弦夹角

    https://www.jianshu.com/p/5619e73e1322
    查询和文档转化为特征后,用户查询与文档之间的相关度问题变成了
    计算用户查询特征向量与文档特征向量的相似度问题。

    1.2 特征权重计算: Tf*IDF 框架

    词频因子 TF

    TF,Term Frequency的缩写,中文为 词频因子,意思是一个词在某一语料库中出现的次数频率。特征单词在文档中出现的次数越多,词频因子越大,越能反应文档的内容,所以应该设更高的权重。

    词频因子变体计算公式

    如果不取log而是直接采用词频,则10的特征权值比1大10倍,取log是为了一直这种过大的差异。加1是避免词频为1的时候词频权值为0的情况。

    词频因子计算变体公式

    上面这种词频因子计算方法被称为增强型规范化tf,这种方法被称为增强型规范化tf, 其中的a是调节因子,过去经验值为0.5,新的研究表明取值为0.4效果更好.公式中的tf代表这个单词的实际词频数目,而MAX(tf)代表了文档中所有单词中出现次数最多的那个单词对应的词频数目.之所以要如此操作,主要对于长文档的一种抑制,因为如果文档较长,则长文档中所有单词的tf值会普遍比段文档的值高,但是这并不意味着长文档与查询更相关.用单词的实际词频除以文档中最高词频,等于将绝对的数值进行了规范化转换,公式的含义就转换为:同一个文档内单词之间的相对重要性.

    逆文档因子 IDF

    IDF,Inverse Document Frequency的缩写,中文为 逆文档频率因子,意思是这个词在所有语料中的分布情况,用公式表达:

    N文档集合中文档总数,nk 出现特征单词k 的文档数

    逆文档频率因子反应了以特征单词区分文档的能力,逆文档频率因子越大,区分文档的能力越强。

    TF*IDF 框架

    特征权重计算

    特征权重值 为两者的乘积,特征值越大,越是好的 指示词。

    1.3 概率检索模型

    贝叶斯公式的推导

    假定变量A代表一个事件,它是所有可能的结果构成的空间②上的一个子集①。同样,我们可以通过随机变量(random variable)来代表该子集,它是从结果到实数的一个映射函数。对应该子集,随机变量A会取一个具体的值。通常我们并不能确信某个事件是否为真,此时,我们想知道事件A发生的概率P(A),它满足 0 ≤ P(A) ≤ 1。对于两个事件A、B,它们的联合事件发生的可能性通过联合概率P(A,B)来描述。条件概率 P(A| B)表示在事件B发生的条件下A发生的概率。联合概率和条件概率的关系可以通过如下的链式法则(chain rule)来体现:


    链式法则

    上式表明,在不做任何假设的条件下,两个事件的联合概率等于其中一个事件的概率乘上在该事件发生的条件下另一个事件发生的条件概率。

    事件 A 的补集的概率记为 P ( A补) ,同样有

    概率论中的全概率定理(partition rule)为:如果事件 B 可以划分成互不兼容(即互斥)的多个子事件,那么 B 的概率将是所有子事件概率的和。下式给出的是该定理的一个特例:


    基于上述结果可以推导出贝叶斯定理(Bayes’s rule):

    贝叶斯定理

    概率排序原理

    概率排序原理作为概率检索模型的指导思想,指示了对召回文档进行排序的大体框架,并没有给出具体的做法。概率排序原理是一种对于用户需求相关性进行建模的方法,这点明显区别于向量空间模型,向量空间模型以query语句与文档内容之间的相似性作为相关性的替代品。

    概率排序原理的基本思想搜索召回的文档能够根据文档和用户需求的相关性从高到底排序,这种搜索系统的准确性是最由的。

    对文档按用户需求的相关性划分为两类:相关文档子集和不相关文档子集。对于某一个文档A,如果其属于相关文档子集的概率大于属于不相关文档子集的概率,则可以认为该文档与用户需求是相关的。也就是

                                                               P(R|D)>P(NR|D)
    
    代入贝叶斯公式 公式变换

    上式的目的是对于给定文档根据与用户需求之间的相关性进行分类,如果满足上式则判断该文档是相关的,否则是不相关的。但是排序问题不是一个二分类问题,我们只需要根据公式左边的值从大到小排序即可。


    文档与用户需求相关性计算公式,值反映相关性程度

    BIM 二元独立模型

    假设一:二元假设

    所谓二元假设,类似于布尔模型的表示方法,一篇文章在由特征表示的时候,以特征“出现”和“不出现”两种情况来表示,也可以理解为相关不相关。

    假设二:词汇独立性假设

    所谓独立性假设,是指文档里出现的单词之间没有任何关联,任一个单词在文章中的分布率不依赖于另一个单词是否出现,这个假设明显与事实不符,但是为了简化计算,很多地方需要做出独立性假设,这种假设是普遍的。

    在以上两个假设的前提下,二元独立模型即可以对两个因子P(D|R)和P(D|NR)进行估算(条件概率),举个简单的例子,文档D中五个单词的出现情况如下:{1,0,1,0,1} 0表示不出现,1表示出现。用Pi表示第i个单词在相关文档中出现的概率,在已知相关文档集合的情况下,观察到文档D的概率为:


    对于因子P(D|NR),我们假设用Si表示第i个单词在在不相关文档集合中出现的概率,于是在已知不相关文档集合的情况下,观察到文档D的概率为:


    于是我们可以得到下面的估算


    可以将各个因子规划为两个部分,一部分是在文档D中出现的各个单词的概率乘积,另一部分是没在文档D中出现的各个单词的概率乘积,于是公式可以理解为下面的形式

    其中i:di=1代表了文档中出现过各个单词的乘积

    对公式进行一下等价的变换,可得:



    第一部分代表在文章中出现过的单词所计算得到的单词概率乘积,第二部分表示所有特征词计算得到单词概率乘积,它与具体的文档无关,所有文档该项的得分一致,所以在排序中不起作用,可以抹除掉。得到最终的估算公式:



    为了方便计算,对上述公式两边取log,得到:

    那么如何估算概率Si和Pi呢,如果给定用户查询,我们能确定哪些文档集合构成了相关文档集合,哪些文档构成了不相关文档集合,那么就可以用如下的数据对概率进行估算:

    相关文档 不相关文档 文档数量
    di=1 ri ni-ri ni
    di=0 R-ri (N-R)-(ni-ri) N-ni
    文档数量 R N-R N

    根据上表可以计算出Pi和Si的概率估值,为了避免log(0),对估值公式进行平滑操作,分子+0.5,分母+1.0



    代入估值公式得到:



    这个公式代表的含义就是,对于同时出现在查询Q和文档D中的单词,累加每个单词的估值结果就是文档D和查询Q的相关性度量,在预先不知道哪些文档相关哪些文档不相关的情况下,可以使用固定值代替,这种情况下该公式等价于向量空间模型(VSM)中的IDF因子,实际证明该模型的实际使用结果不好,但是它是BM25模型的基础。

    BM25模型

    BIM(二元假设模型)对于单词特征,只考虑单词是否在doc中出现过,并没有考虑单词本身的相关特征,BM25在BIM的基础上引入单词在查询中的权值,单词在doc中的权值,以及一些经验参数,所以BM25在实际应用中效果要远远好于BIM模型。



    BM25由3部分组成,第一部分是BIM模型得分,上面也提到了,在一定的情况下该部分等价于IDF,第二部分是查询词在文档D中的权值,f是查询词在文档中的频率,K1和K是经验参数,第三部分是查询词自身的特征,qf是查询词在用户查询中的频率,但一般用户查询都比较短,qf一般是1,K2是经验参数,从上面的公式可以看出BM25是查询中单词的分值叠加得到,每个单词是一个个体,而整个文档被作为一个整体。

    在第二部分中K因子代表了文档长度的考虑,dl是文档的长度,avdl是文档的平均长度,k1和b是调整参数,b为0时即不考虑文档长度的影响,经验表明b=0.75左右效果比较好。但是也要根据相应的场景进行调整。b越大对文档长度的惩罚越大,k1因子用于调整词频,极限情况下k1=0,则第二部分退化成1,及词频特征失效,可以证明k1越大词频的作用越大。

    在我们不知道哪些文档相关,哪些文档不相关的情况下,将相关文档数R及包含查询词相关文档数r设为0,那么第一部分的BIM公式退化成类似IDF的形式:

    就是IDF因子的定义,N是总文档数,n是查询词的tf信息,0.5是平滑因子。

    待补充
    实用工具:
    在线数学公式编辑器

    相关文章

      网友评论

        本文标题:检索模型与检索排序

        本文链接:https://www.haomeiwen.com/subject/oktyqftx.html