0%

从检索模型到搜索结果多样化

文档处理

目的:将文本处理为词-文档矩阵,步骤如下:

  1. 拼写错误纠正、时态还原
  2. $pdf$、$html$、$doc$ 转 $txt$(图片信息将会丢失)
  3. 中文分词,精度已经达到可用的标准;英文分词,直接去标点按空格分开
  4. 去停用词(停用词表或目前最频繁的 $k$ 个词),提高系统效率,但是现在倾向于尽量少去除,造成信息丢失,例如:To be or not to be 整个句子都是停用词
  5. 词干还原,英文的可以使用 $porter$ 工具,不同意义相近的词也有可能被映射到一个词干,$households->household, alike->alik$
  6. 最终建立词项文档矩阵和倒排索引如下:

传统信息检索模型

布尔模型

通过布尔运算符 $AND、OR、NOT$ 的组合进行检索,返回倒排索引中索引符合查询条件的所有文档,不进行排序,布尔模型的词项-文档矩阵不存储词在文档中存储的次数,只存储出现或不出现。

行代表文档中出现过哪些单词,列代表单词出现在哪些文档中,查询时首先选择行(过滤掉绝大部分无关文档),然后将布尔查询应用于每一个相关的列(文档)。

布尔模型的优点是简单可控易理解,现在仍然应用于图书馆的图书检索系统中,缺点是检索结果为无序的文档集合,若条件过严则可能返回空集,条件过松则会返回过多结果。

向量空间模型:Vector Space Model

TFIDF:

$$tfidf(w,d)=tf(w,d)\times idf(w)\;\;\;$$$$tf(w,d)=词w在文档d中出现的次数$$$$idf(w)=log\frac{N}{df(w)}=log\frac{文档集上的文档数目}{文档集中包含词w的文档数目}$$

$tfidf(w,d)$ 衡量了词 $w$ 在文档 $d$ 上的重要性,实际上是文档 $d$ 的文档向量的第 $i_w$ 维,$i_w$ 指词 $w$ 在词典中的索引 $id$,文档向量和查询向量维度相同,都是词典大小。

$VSM$ 本质上基于词袋模型,没有考虑到词序对检索结果的影响.

BM25模型:Best Match 25

$$BM25(q,d)=\sum_{w\in q}log\frac{N}{df(w)}\cdot\frac{(k_1+1)tf(w,d)}{k_1((1-b)+b\frac{dl(d)}{avdl})+tf(w,d)}\tag{1}$$

  • $avdl$ 是文档集中文档的平均长度
  • $b$ 控制均值化后的文档长度对打分的影响,$b=1$ 全文档长度归一化,$b=0$ 时不进行文档长度归一化
  • $k_1$ 控制 $BM25$ 分值随 $tf(w,d)$ 值增长而饱和的速度,也控制词频对 $BM25$ 打分的影响力

当 $k_1=0$ 时,饱和函数$=1 或 0$,此时 $式1$ 第二项度量的是词 $w$ 是否在文档 $d$ 中出现;当$k_1$取无穷时,$式1$ 第二项退化为 $tf(w,d)\cdot\frac{\infty}{\infty}=tf(w,d)$ 。所以可以把 $k_1$ 看作是对$tf$ 的打折因子

语言模型:Language models for IR

  • 一元模型:$p(w_1,w_2\cdots,w_n)=p(w_1)\cdots p(w_n)$,词袋假设
  • $N$元模型:$p(w_1,w_2\cdots,w_n)=p(w_1)p(w_2|w_1)\cdots p(w_n|w_{n-1},w_{n-2},w_{1})$
  • 二元模型:$p(w_1,w_2\cdots,w_n)=p(w_1)p(w_2|w_1)\cdots p(w_n|w_{n-1})$,马尔可夫假设

用于信息检索的语言模型处理流程
利用每一个待排序的文档 $d$ 训练一个语言模型,去生成用户输入的查询 $q$

  • 选择语言模型
  • 估计模型参数,如选择一元模型就计算 $p(w|d)=\frac{tf(w,d)}{|d|}$
  • 模型平滑化,防止零概率
  • 对所有文档分别计算文档 $d$ 的模型生成查询 $q$ 的概率$p(q|d)$,计算文档 $d$ 的打分$p(d|q)$
    $$p(d|q)=\frac{p(d)p(q|d)}{p(q)}$$
    在同一个查询中 $p(q)$ 一致可忽略,$p(d)$ 可以视为文档 $d$ 的静态打分,$p(q|d)$ 就是语言模型的生成概率,表示文档与查询的匹配程度,用语言模型进行估计,如在一元模型中 $p(q|d)=\prod_{w\in q}p(w|d)$
  • 根据文档打分进行排序,返回结果

参数平滑:Smoothing

生成概率是累乘模型,所以如果文档中有一个查询词没有出现(对应的 $p(w|d)=0$ )那么文档打分就会是 $0$,不符合实际情况。平滑化方法的目标就是使每个在词典中出现过的词,即使其没有在文档 $d$ 中出现,其对应的$p(w|d)$ 都有一定正概率,避免零概率问题的出现。

混合平滑模型

  • 基于文档集估计 $p(w|C)=\frac{tf(w,C)}{|C|}$
  • 基于文档 $d$ 估计 $p(w|d)=\frac{tf(w,d)}{|d|}$
  • 线性插值:$p_{mix}(w|d)=\lambda p(w|d)+(1-\lambda)p(w|C)$

狄里克莱平滑

  • 基于文档集估计 $p(w|C)=\frac{tf(w,C)}{|C|}$
  • 基于文档 $d$ 估计 $p(w|d)=\frac{tf(w,d)}{|d|}$
  • $p_{mix}(w|d)=\frac{tf(w,d)+\mu p(w|C)}{|d|+\mu}$
  • 直观解释:一般设置 $\mu = 100-200$ ,表示文档 $d$ 还有 $\mu$ 个位置没有被观测到,实际文档长度应为 $|d|+\mu$,这 $\mu$ 个位置被词典中所有的词瓜分,瓜分的比例为其在文档集合中出现的比例。

传统信息检索排序模型的总结

此外:

  • $BM25$ 是使用最多的传统排序模型,简单、易于计算,表现稳定、对参数不敏感,常作为 $IR$ 实验的 $baseline$
  • $LMIR$ 的平滑方法多选择狄里克莱平滑

排序评价指标

标注的数据 $(q,d,r)$ ,$r$ 是人工打分的相关度指标,分二值和多值两类:

  • 二值相关度:$0$ (不相关)或 $1$(相关)
  • 多值相关度:
    • $2$(相关)或 $1$(部分相关)或 $0$(不相关)
    • 5级:Bad, Fair, Good, Perfect, Excellent

二值相关度评价指标

P@K:Precision@K

MAP:Mean Average Precision

$MAP$ 的假设是所有查询的重要性相同且用户想看到多个相关文档 $P@K$

多值相关度评价指标

DCG:Discounted Cumulative Gain


$DCG@N$ 是只考虑前 $N$ 个位置文档的$DCG$

$$DCG@N=\frac{Gain(d_{r1})}{log_2(2)}+\frac{Gain(d_{r2})}{log_2(3)}+\cdots+\frac{Gain(d_{rN})}{log_2(N+1)}$$

NDCG:Normalized Discounted Cumulative Gain

计算实例:

搜索结果多样化

基于相关性的打分对每个网页进行独立打分,没有考虑到网页之间的关系(网页内容相似、网页间的链接和上下级关系)。所以搜索结果多样化的目标是用尽可能少的网页去覆盖更多的话题,比如查询 programming language:

所以在排序程中要使用顺序文档选择,综合考虑已选择文档和待选择文档的相似度以及查询和待选择文档的相似度

最大化边缘相关度是搜索结果多样化中最常用的方法

参考文献:
[1] 徐君,《网络数据挖掘》,中国科学院大学2017年秋季研究生课程