relevance 与 diversity

前面关于 IR 的笔记里面我们知道,IR 解决的主要问题一个是 similarity/relevance(VSM 的 similarity 被认为是对 relevance 的刻画方式),一个是 de-dup(通过 shingling)。然而通过 relevance driven 的算法往往导致“diversity”不足。因此我们首先要搞明白 diversity 是什么。

一个比较清楚的介绍是将 diversity 分解成为 extrinsic diversity 何 intrinsic diversity:

  • extrinsic diversity 是指由于 ambiguity 引起的完全不同领域的各种符合 query 的要求的现象
  • intrinsic diversity 是指由于并不存在一个完全满足 query 的 item,这类 query 并不存在歧义,而是存在各种有用的声音,比如搜影评、游记、评测等等,这一般都会有多个观点,不同的侧重

其实对具体的问题来说后者可能比较容易解决,因为往往具有权威性的站点如果恰好能命中,那么一一罗列出来之后用户的体验不会太差,这是因为他们一般不大会互相抄袭结果,也试图用自己的分析给出结果。有人试图使用公理系统找到合理的 diversity 函数(作为一个 doc set、query、relevance function 和 distance function 的函数),他们要求这个函数

  • scale invariant,即 relevance function 和 distance function 在乘以相同倍数后选择的 doc set 不变
  • consistent,即在 relevance function 和 distance function 上分别加上 bias(原 doc set 加正的,否则加负的),则排序不变
  • rich,即通过调整 relevance function 和 distance function,任何排序结果应该都可能
  • stable,即当 candidate set 扩大时选择的集合应该扩大(这个假定其实不 make sense)
  • independent of irrelevant attributes,仅仅是 doc set 的函数,与其他 doc 无关
  • monotonous,增加候选 doc 不会降低函数值
  • relevance function 和 distance function 必须有用

但发现不存在符合所有这些要求的函数。我们常用的一些策略,如

  • 最大化候选集合的 relevance + 两两 doc 的相似性,不是 stable 的
  • 最大化候选集最小的 relevance + 最小的 doc 相似性,不满足 consistency 和 stability
  • 将 relevance + 到其他所有文档的 distance 作为每个 doc 的 score,这样用贪心策略即可,但不满足 consistency

另外一种 balance 两者的策略来自经济学的 portfolio 理论,这个理论解释投资使用了两个 objective,一个是收益,一个是风险,投资人一般会选择达到一定的收益情况下尽量规避风险。用这个理论来解释搜索结果就是我们希望保证 relevance 足够高的情况下,尽可能最大化 diversity。为什么两者可以一致的表达出来呢?如果我们将给定 query 后每个文档的 relevance 作为是一个随机变量的话,那么我们的收益就是 ranking 后选择排在前面的文档决定的(越向后用户看到的机会越低),而风险就在于如果两个文档之间存在较强的正 correlation(此时一荣俱荣一毁俱毁),那么我们相当于把鸡蛋放在一个篮子里面,风险就会增大。因此,我们可以看成是几个随机变量和的方差:根据公式展开后等价于每个随机变量的方差 + 协方差部分,这部分如果是正相关就会使得最后的和变大,因此规避风险就是降低选择的文档的相关性,也就是增加 diversity。这个 idea 可以演化出多种形式的优化(如将方差作为 regularizer,也可以直接 minimize 方差要求 relevance 足够高)。因此后面就是如何计算期望和方差,每个人的做法是不大一样的,一个例子是 google 的这篇文章

某些方法里面将 relevance 当做随机变量,而将 ranking score 当做一个与之相比较的参考值,这样引入一 loss 衡量 ranking score 就需要 marginalize 掉随机变量,如果用上面的思路,最后一般就考虑 loss 展开后的一阶二阶项(marginalize 之后成为 mean 和 variance)。特别的是这篇使用了一个指数减掉线性函数作为 loss。

通过一个 taxonomy 进行 diversify 的想法其实也很常见,比如我们有 V(d \mid q, c) 表示在给定类别 c 下某个 query q 对应文档 d 的点击概率(relevance),我们可以用

\displaystyle\max_S \Pr(S \mid q) = \sum_c \Pr(c \mid q) \left( 1 - \prod_{d \in S} \big(1 - V(d \mid q, c) \big)\right)

来 diversify 结果,这实际上是要求,对具有歧义的 query,此时可以有多个类型 \Pr(c \mid q) 不为零,这时后面的要求实际上是说返回该类型下相关性最高的几个文档(至少有一个 V(d \mid q, c) 很接近于 1)。当然这个优化很困难,需要用一些贪心策略求解。

为了评估 diversity,除了 ranking 常用的 DCG 这类,而与以上分类类似的一种评估策略认为存在一些 nuggets 表示某种相关性(这个可以理解成为某个 category 下的相关性,也可以理解成为别的什么),当一个文档含有该 nuggest 之后就可以认为是 relevant to query 了,这样可以宠信定义 DCG/nDCG,想法与以上类似,获得的称之为 \alpha-nDCG,这可以用来评估 IR 获得的 relevance + diversity。

当然这个领域的方法还是挺多的,文献也比较多,这纯粹作为一个入门文献 seed 留存。

——————-
And Abraham took the wood of the burnt offering, and laid it on Isaac his son; and he took the fire in his hand, and a knife; and they went both of them together.

Advertisements
relevance 与 diversity

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s