机器学习之多样性排序算法

作者: EasonZhao | 来源:发表于2016-01-07 13:37 被阅读1023次

    论文贡献

    1. 设计了一个贪婪的多样性搜索策略;
    2. 设计了新的用于衡量多样性指标的metrics;

    细节内容

    多样性搜索策略

    假设搜索词存在语言多样性的时候,多样性的搜索策略可以提高Recall。这种情形在推荐场景下会显得更加重要。
    问题定义如下:

    图1:问题定义

    其中,V(d|q,c)可以理解为文档d满足“带有真实目的为c的q”的满意度概率,那么(1-V(d|q,c))就是不满意的概率。
    根据贝叶斯公式:P(S|q) = \sum_c{P(c|q)P(S|c,q)},因此P(S|c,q)等于上图中的右边括号部分,意思就是返回的结果里面至少有一个以上满足用户搜索意图的概率。

    这个问题定义有两个需要注意的地方:

    1. 目标没有要求尽量的多样;
    2. 目前没有对返回结果的顺序作要求。

    但是,后面给的IA贪婪算法却是对顺序有保障的。另外,因为该问题具有很强的子问题结构信息,所以可以采用动态规划的思路进行贪婪搜索。该方法并不能保证一定能够得到最优解,但是却有一个最坏结果的error bound。

    图2:贪婪IA算法

    其中,参数的含义分别如下:

    • C(q)是query可能存在的语义集合
    • R(q)是query搜索返回的结果集合
    • C(d)是document的语义集合
    • P(c|q)是query的语义概率
    • V(d|q,c)是带有语义c的q查询时,d满足要求的概率
    • U(c|q,S)是图1中公式(1)的右边括弧中的相乘部分,也就是集合S不满足“q的语义c”的概率。

    注意:需要试验测试一下原文的正确性,从公式来推导,应该取argmin,而不是argmax。

    多样性评价metrics

    传统的检索评估指标,比如NDCG,多是用来衡量检索结果与搜索词的语义相关性来进行评估的。但是当搜索词的语义存在多样性的时候,那么NDCG就不适用了,需要新的指标来进行评估。

    该文假设检索结果与检索词的相关度是和检索词的语义条件独立的,并根据该假设求的NDCG在不同语义上的期望得到NDCG-IA结果作为评价指标。

    图3:NDCG-IA

    参考论文

    http://www.wsdm2009.org/papers/p5-agrawal.pdf

    相关文章

      网友评论

        本文标题:机器学习之多样性排序算法

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