CMU 11642 Search Engine - 多样化搜索

作者 QIFAN 日期 2017-05-01
CMU 11642 Search Engine - 多样化搜索

之前的排序方法(BM25, Indri, letor)都是基于文件相互独立互不相关的假设,但有时候,一个 query 会有多层意思,本文主要讨论多样性搜索的方法。

why 多样化

  1. 最大化用户满意度,因为大多时候机器并不知用户的想法
  2. 多样性与相关性有一定程度的 tradeoff
  3. 多样化的结果通常把最有可能的一层意思放最前面。

多样化可以是多层意思,也可能是多种不同的展现方式(网页、图片、视频等)

排序质量指标

1. P@k

前 k 位排序的准确率,只考虑是否相关,并没有体现多样性。

2. Precision-IA@k

第 k 为排序不同意图(intent)准确率的算术平均值。

$Precesion-IA@k=\sum_{q_i} p(q_i|q)P@k_{q_i}$

  • $q_i$ :某个查询 q 的第 i 层意图
  • $p(q_i|q)$ :意图发生概率,通常假设是均匀分布

Precision-IA@k 会提高满足多种意图的排序比重,这样子间接的也是提高了满足多种意图的文件的比重,也是合理的。

3. NDCG

Normalized discounted cumulative gain。将排序中每个位置计算 discount gain ,然后累加得到的一个值。gain 可以根据自己的定义来算,下面是其中的一个方法。
$NDCG@k=Z_k\sum^k_{k=1} \frac{2^{R(k)}-1}{log_2(k+1)}$

  • $Z_k$:标准化
  • $2^{R(k)}-1$ :Gain at rank k, G@k
  • $log_2{1+k}$ :discount at rank k, D@k

考虑每个位置,但没有考虑多样化

4. α-NDCG

NDCG 对 $G@k$ 增加了多样性的考虑。
$G@k=\sum_{q_i} R(d_k, q_i) (1-\alpha)^{r_{q_i}, k-1}$

  • $R(d_k, q_i)$ :文件 k 对 $q_i$ 的相关性
  • $r_{q_i}, k-1 = \sum^{k-1}_{j=1}R(d_j, q_i)$ ,re-rank 后文件涵盖 $q_i$ 的一个分数

除了对不同意图进行计算外,还有一个重排序结果对查询意图的涵盖程度。

多样性算法-隐式方法(Implicit methods)

查询意图并没有直接在排序中显示出来,相似的文件通常认为涵盖了相同的意图。

Maximum Marginal Relevance (MMR)

MMR 先通过基本算法得到一个 query 的初始排序,然后加权每个文件与 query 相关度以及与重拍后文件的相似度,每次从初始排序中选择一个最大值,放到最终排序中。是无监督性学习。
$MMR = max_{d_i \in R}(\lambda Sim(q, d_i)-(1-\lambda)max_{d_j\in S}Sim(d_i, d_j))$

  • R:初始排序
  • S:最终排序
  • $Sim(d_i, d_j)$ :文件相似度

任意两两相似度 (anything-to-anything similarity)

  • Kullback-Leibler divergence
    $KL(x\parallel y)=\sum_{t\in V}p(t\parallel x)ln\frac{p(t|x)}{p(t|y)}$
  • Jasen-Shnnon divergence ,常用
    $JS(x\parallel y) = \frac{1}{2} KL(x\parallel M) + \frac{1}{2} KL(y\parallel M)$ ,$M=\frac{x+y}{2}$

Relational - letor

如果直接把 letor 模型套进来优化某个多样性指标,效果并不好,这是因为:

  • 训练时没有任何有关多样性的 feature
  • letor 基于相关性 feature 的,并不能产生以多样性为目标的结果

所以应该再添加一些文件间关系的 feature ,如果文本相关性,主题相关性,分类相关性,链接相关性,url 相关性

Relational - ListMLE

rerank 的套路和之前都一样,就是先用基本算法得到一个初始文件集,然后每一次找一个最好的文件放入最终排序,同时更新剩余所有文件的相似度,重复这一过程直到所有文件都进入最终排序。所以时间复杂度是 $O(n^2)$ ,n 为初始文件集的大小。

隐式方法总结

上述方法没有实现直到 query 的意图,也没有偏向某个意图,初始排序选择的是相关度最高的,最后生成的结果偏向于更加的多样性。

多样性算法 - 显式方法 (Explicit methods)

xQuAD

explicit query aspect diversivication
算法如其名,以初始排名与一系列查询意图为输入,以选择出覆盖尽可能多的文件为目标。这和 MMR 很相似,区别就在于算 MMR 时,并不知道意图,而是从初始排名最高的文件开始,以它为基准进行重拍;而 xQuAD 则一开始就提供了同一个查询的不同意图,重拍时算的不是相似性,而是意图的覆盖度。
对于一个文件 d :
$xQuAD=(1-\lambda )P(d|q)+\lambda \sum_{q_i\in Q}[P(q_i|q)P(d|q_i)\prod_{d_j \in S}(1-P(d_j|q_i))]$

  • $\lambda$ 系数
  • $P(d|q)$ 文件的初始查询相关性分数
  • $P(q_i|q)$ 意图 i 在所有意图中的比重
  • $S$ 已重拍的排名

特点分析:

  • 与 MMR 类似,xQuAD 也更偏好满足多种意图的文件。
  • 默认每个意图都相同重要(实验证明这样子结果最好)
  • 每个意图都需要计算 ranking ,成本比之前的稍大些

PM-2

Proportionality Model 2
在 xQuAD 中每个 intent 的权重是一样的,但 PM-2 会根据不同子主题的热度来动态分配权重。

过程如下:

  • 对于每个查询意图 $q_i$ ,都有一个投票权重 $v_i$ 与重排权重 $s_i$ ,通过这俩变量算出 $q_i$ 当前优先度 $qt[i]$ 。
  • 选择最高优先的意图 $q^*$,
  • 计算初始排序中每个文件的分数(考虑对 $q^*$ 的覆盖度与对其他意图的覆盖度)
  • 选择分数最高的文件放入重排排名
  • 更新意图 $q^*$ 的重排权重 $s^*$
  • 重复上述过程直到重排完成

具体计算公式:
$v_i=\frac{diversifiedRankingSize}{NumberOfIntents}, s_i=0$
for all $s\in S$:

  1. $\forall q_i \in Q, qt[i]=\frac{v_i}{2s_i+1}$
  2. $i^*=max(qt[i])$
  3. $d^*=max(d_j\in R(\lambda qt[i^*]p(d_j|q_{i^*}) + (1-\lambda )\sum_{i\ne i^*}qt[i]p(d_j|q_i)))$
  4. 将 $d^*$ 从初始排序 R 中删除,并加入多样性重排排名 S
  5. 更新 $s_i$ ,$\forall q_i \in Q, s_i = s_i + \frac{p(d^*|q_i)}{\sum_{q_i \in Q}p(d^*|q_j)}$

xQuAD vs PM-2

xQuAD 对 intent 没有偏好,选择的是覆盖了最多 intents 的文件,而且排序过程中前后选择的文件对后续过程没有影响。

PM-2 先确定一个最重要的 intent ,然后寻找最贴合这个 intent 的文件。并且下一轮选文件的过程会受上一轮影响而偏好去覆盖上一轮被选择的文件所覆盖的主要 intent 。

总结

MMR: 不知道 intents ,无监督,
R-letor:不知道 intents,监督性
xQuAD:知道 intents ,无监督
PM-2:知道 intents ,无监督