使用NDCG评估关键词推荐系统的相关性

对于传统推荐策略, 我们在验证其效果的时候, 一般会采用以下流程验证其实验效果:
  1. offline 的评测: 思路基本和传统机器学习的思路类似, 例如在推荐算法中我们直接使用AUC,F2等评估模型效果一样, 线下使用测试数据就能知道算法的初步效果。
  2. 用户调研实验: 该方式需要人的参与, 例如招一批人, 不告诉他们新老算法的界面或是使用的算法, 然后看用户的行为, 之后使用他们的最终交互, 或是选择判定算法/交互方案的优略。
  3. 线上实验: 最真实的尝尽, 例如小流量进行A/B test
具体关于评测后续会用专门的文章介绍,此处略去。 此处仅考虑一种特定的评估:关键词推荐系统的相关性评估。
因为baidu 关键词推荐系统是关键词的推荐,所以在很大程度上, 该推荐系统和传统的IR系统有着非常紧密的联系, 评估标准也较为相像。
对于一次推荐,用户进入百度关键词推荐系统交互界面: 关键词推荐系统会主动向用户push推荐的关键词,同时用户可以输入种子query进行查询:
如果将种子query看成是搜索引擎上的query,返回的关键词看成doc, 则问题就转换为搜索引擎的结果评估问题, 一种常用的方式为:NDCG(Normalized Discount Cummulative Gain)
CG
要介绍NDCG,我们首先介绍CG(Cummulative Gain), 其思想比较简单, 就是将相关性的分值累加后, 作为某个query/ 请求结果的分值。
reli 为处于位置i的推荐结果与query的相关性, p代表我们要考察前p个结果。
DCG
CG的一个缺点是CG没有考虑结果处于不同位置对结果的影响,例如我们总是希望相关性高的结果应排在前面,相关性低的结果排在靠前的位置会严重影响用户体验, 所以需要在CG的基础上引入位置影响因素,即DCG(Discounted Cummulative Gain)
即相同的相关性rel,排在对整次检索结果的正向影响,相较于放在后边更大。
NDCG
DCG仍然有其局限之处,即不同的query之间,很难进行横向的评估。例如, 我们评估百度关键词推荐系统, 或是搜索引擎的时候,都不可能仅使用一个query及相应结果进行评估, 一般都是是使用一批query及结果进行评估。 不同的query的评估分数就需要进行归一化。 也即NDCG。
例如我们定义:
其中DCG的定义如上, IDCG为特定query返回的最好结果, 即假设返回结果按照相关性排序, 最相关的结果放在最前面, 此序列的DCG为IDCG。因DCG的值介于 (0,IDCG],故NDCG的值介于(0,1]
具体操作方式
在具体操作中, 可以事先确定query和结果的相关系分级, 例如可以使用 0,1分别表示相关或不相关, 或是这是0~5分别表示严重不相关到非常相关。 相当于确定了rel值的范围。
之后对于每一个query的返回结果给定rel值,然后使用DCG的计算公式计计算出返回结果的DCG值。
使用根据sort后的rel值得序列计算IDCG值, 即可计算NDCG
参考文献:
百度关键词系统评估
 可关注微博: weibo.com/dustinsea
也可直接访问: http://semocean.com