美文网首页
KDD2020最佳论文学习:On Sampled Metrics

KDD2020最佳论文学习:On Sampled Metrics

作者: python小白22 | 来源:发表于2020-10-11 09:07 被阅读0次
    一、简介

    项目推荐任务需要根据上下文对大型项目目录进行排序,使用取决于相关项目位置的排名度量指标来评估项目推荐算法。为了加快度量的计算,最近的工作经常使用抽样的度量,其中仅对较小的一组随机项和相关项进行排名。该论文对抽样指标进行了更详细的调查,结果表明它们与确切指标的性能不一致。另外,实验结果表明抽样规模越小,指标之间的差异就越小,而且对于非常小的抽样规模,所有指标都会塌陷为AUC指标。所以该论文提出了一种改进的抽样评价指标来提高评价质量。

    二、主要评价指标

    该论文主要研究的评价指标包括:AUC、Prec、Recall、AP以及NDCG。在之前的学习中已经详细了解了这些评价指标,具体内容可参考原文链接。目前大部分文献采用的简化过后的指标,假设只有一个正样本,即|R|=1,然后基于这个正样本采样若干个负样本,以此来进行排序,看最终该正样本排在了什么位置。各个指标可简化为:AUC(r)_n=\frac{n-r}{n-1} Prec(r)_k=\delta(r\leq k)\frac{1}{k} Recall(r)_k=\delta(r\leq k) AP(r)_k=\delta(r\leq k)\frac{1}{ r } NDCG(r)_k=\delta(r\leq k)\frac{1}{log_2( r+1)}

    三、期望指标

    用替换重复抽样过程m次,并计算某项排名较高的频率,相当于二项分布。换句话说,从抽样过程中获得的排名\widetilde{r}服从二项分布B(m,\frac{r-1}{n-1})+1。如果没有成功获得更高排名的项目,则排名保持为1,如果所有m个样本均成功,则排名为m +1。在此分布下,指标的期望值为:E[M(\widetilde r)]=\sum_{i=1}^{m+1}{p(\widetilde r=i)M(i)} 该论文将上式应用于特定指标,分析了抽样指标。

    AUC是排名的线性函数,则通过期望的线性和\widetilde{r}遵循二项分布的事实,可以得到:

    AUC 这意味着通过抽样产生的AUC测量是精确AUC的无偏估计。因为AUC也可以定义为一个随机的相关项目排在一个随机的不相关项目之上的期望。因此,AUC是抽样下的一致指标。这一结果也适用于任何抽样分布,比如超几何分布的抽样-即不替换的均匀抽样。 对于精确率和召回率: Recall

    这种分析适用于任何抽样分布,包括超几何分布。

    对于采样平均精度的期望值,分为两种情况:如果r=1,那么\widetilde{r}=1,并且采样的度量总是等于1。如果r>1,则p(j<r)>0

    AP 该部分验证了除过AUC之外的,抽样指标与确切指标的性能不一致。
    四、修正指标

    排序的无偏估计量
    第一种方法是基于一个简单的观察,通常使用的抽样度量是将精确度量M应用于观察到的排序\widetilde{r},即\hat{M}(\widetilde{r}) = M(\widetilde{r})。但\widetilde{r}是真实秩r的一个很差的估计,总是低估它。相反,可以不在观察到的等级\widetilde{r}上而是在r的无偏估计量上测量度量。如果我们让p=\frac{r-1}{n-1},那么p的无偏估计量由\frac{\widetilde{r}-1}{m}给出,因此r=1+(n-1)p的无偏估计量由\hat{r}=1+\frac{(n-1)(\widetilde{r}-1)}{m}给出。则得出以下正确的度量标准:\hat{M}(\widetilde{r})=M(1+\frac{(n-1)(\widetilde{r}-1)}{m}) 由于排序估计在[1,n]中是实数,而原来的度量M只定义在自然数上,可以对排序估计进行四舍五入,也可以使用线性插值等方法对M进行扩展。

    最小偏差估计量
    上面的修正使用的是排序的无偏估计量,但当M是非线性时,\hat{M}(\widetilde{r}) = M(\widetilde{r})是有偏的。可能寻求优化的一个准则是\hat{M}(\widetilde{r})的平均偏差,也就是


    其中p(r)是排序分布的先验。因此,我们寻求一个向量\hat{M},使以下问题最小化:
    偏差—方差权衡
    最小偏差估计量的一个潜在问题是,它可能有高方差,为了缓解这个问题,可以通过引入方差项来对上面的问题进行正则化: 这是一个正则化的最小二乘问题。
    五、结论

    该论文主要的创新点就是提出了三种方法修正指标,最后通过实验验证了修正后的指标得出的评价结果,与在全量测试样本上的评价结果是差不多相等的。

    相关文章

      网友评论

          本文标题:KDD2020最佳论文学习:On Sampled Metrics

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