SIGIR 2020最佳论文解读出炉，可缓解排名问题的马太效应？

作者 | 陈大鑫

编辑 | 青 暮

凡是少的，就连他剩下的也要夺过来。凡是多的，还要让他他多多益善。

任何个体、群体或地区，在某一个方面（如金钱、名誉、地位等）获得成功和进步，就会产生一种积累优势 ，就会有更多的机会取得更大的成功和进步。

这就是“马太效应” ，反映当今社会中存在的一个普遍现象，即赢家通吃。

在一些推荐排名应用中马太效应同样存在，比如大家经常浏览的微博、知乎热搜。同一类话题排名越靠前被点击的概率也就越大，这样，在一段时间内，越是靠前的话题就越会被人点击，然后它越会靠前，然后它就越会......

当然，也许热搜机制存在的意义就在于此，或许不必缓解马太效应。

但是在其它很多排名环境中，不只涉及用户，还有项目提供方。在网上搜索中，很大一部分人只会看搜索出来的第一个页面，至于第二个页面，很多人都不会去看，甚至有时一度忘记竟然还有第二个页面。如果这时用户是在某APP搜索想要购买的商品，那么对于商家而言马太效应带来的偏差和不公平对收益的影响可是很大的。

那么类似这种排名环境中的马太效应可以得到很好的缓解吗？

7月29日晚，第43届国际信息检索研究与发展（SIGIR ）年会最佳论文奖正式公布，由柏林工业大学和康奈尔大学的研究者摘得该奖项，该研究对动态学习排名的不公平和偏差做了一些控制，尤其是想要解决马太效应中的“富者越富”这一问题。

论文：《Controlling Fairness and Bias in Dynamic Learning-to-Rank》

论文地址：https://arxiv.org/pdf/2005.14713.pdf

论文作者：Marco Morik, Ashudeep Singh, Jessica Hong, Thorsten Joachims

接下来我们就来看一下论文是如何解决这一问题的。

1

曝光模型&偏差概念

我们先看看动态学习排序问题的设置。假设现在有一个新闻网站，它需要将六篇新闻文章归入政治类。如果没有任何关于新闻文章的事先信息，我们可能会向第一个用户提供随机排名。根据从第一个用户获得的点击，我们可以将新闻的排名更新，然后使用接下来从用户获得的点击数，继续更新排名，等等。到最后，我们能找到一个对大多数用户或普通用户有用的排名。

现在，由于使用点击数作为相关性的估计值，我们可能已经看到这种方法存在一些问题。

第一个问题是位置选择偏差，计算点击次数的方法会导致相关性的偏差估计。也就是说，每篇新闻文章的平均点击次数并不等于喜欢这篇新闻文章的用户的个数。这是因为位置越低，注意力越少，点击次数也就越少。

这是一个“富者越富”的动态：从最底层开始的有一点机会上升到排名的顶部，比如上图中的新闻4，而从顶部开始的则有更高的机会保持在顶部。

现在，即使我们能够以某种方式计算出新闻文章的真实相关性，我们也可能面临第二个问题：曝光分配不公。

假设这六篇新闻文章属于G-left和G-right两组。用户分布包括49%的左偏向性用户和51%的右偏向性用户，也就是说49%的用户喜欢G-left文章，而51%的用户喜欢G-right文章。

根据概率排序原则，如果我们根据文章的关联概率对这些文章进行排序：

那么排序将使几乎所有衡量其效用的指标最大化：

在这个例子中得到的排名将是右偏向性文章排在所有左偏向性文章之前。尽管两组的平均相关性仅有2%的差异，但这种赢者通吃的分配是概率排序原则固有的。而且这不仅不公平，还会产生不良的下游效应，比如两极分化，在这个例子中的表现就是左偏向性用户会被赶出平台。

基于位置的曝光模型

我们来看看马太效应的形成机制。我们假设一个基于位置的曝光模型，即文档的曝光是检查特定位置的用户的一部分。曝光度e_j是用户在位置j观察到项目的概率：

，并用眼球跟踪、干预研究 、干预收获来评估曝光。

因此，我们从曝光的角度考虑了两种不公平。我们希望根据组的相关度来分配曝光，这时曝光是平均相关度价值的函数：

从约束的角度来看，人们可能希望分配与每个组的相关度成比例的曝光：

因此，我们将两组之间的平均差距定义为曝光率和相关度之间的差异：

与曝光的差异类似，“影响力”也要确保公平分配。在排名中，“影响力”可以定义为每个文档的预期点击率：

而在位置偏差模型下，影响力等于曝光量，即检验概率乘以文件的相关性：

对于约束，需要分配与群体的平均相关度成比例的影响力：

相似地，一对组间差异的平均影响力可以定义为平均值：

现在回到最初的例子，我们看到平均相关性2%的差异会导致某个曝光分布的平均曝光量有很大的差异。现在，这个例子既不满足曝光的公平性，也不满足我们前面定义的影响力公平性。

2

Fairco算法

为了缓解马太效应，我们必须要有一个动态的学习排名过程：

我们希望顺序呈现动态的排名，最大化预期用户效益，同时确保不公平性归零，使排名收敛。

为此，该研究提出了一种Learning-to-Rank算法Fairco，也就是公平控制器：Fairness Controller。

Fairco基本上是根据修改后的相关度得分来寻找文档，该分数是

加上一个误差项

当我们给定文档的条件相关度估计值时，我们将

乘以另一项，时刻

处的误差项为：

也就是

减去文档d组与在曝光或影响力方面具有最大优势的组之间的最大差距。

此时这个误差项对于已经拥有最大优势的组来说将是零，而它就会提高其他组的排名

这种排名将采取比例控制器或P控制器的形式保护它们，这是一个线性反馈控制系统，其中校正与误差成比例。同样对于Fairco，我们可以提供一个保证：如果问题是适定的，即在公平排名成功的条件下，随着

趋于无穷大，平均差距

将趋于零。

这是以一个字节的速率发生的，现在使用Fairco来动态学习排名设置，需要三件事。第一是位置偏差的估计，前文已经讨论过了，另外两个是无偏条件相关性的估计

和平均相关性的估计

，估计平均相关性的关键是在Fairco算法中定义误差项时需要平均相关性。或许，它们也可以用来为热门新闻和最受欢迎的项目排序。

然而，在这个示例中展示的基于平均点击次数进行排名的方法并不是对每个文档的平均元素的一致估计。相比之下，我们可以通过衡量每次点击的反比倾向来计算无偏相关性：

其中

表示在t时刻d上的点击，

表示d位置的位置偏差。

可以证明这个估计量是一个文档的无偏估计量，在这里无偏意味着IPS估计量收敛到每个文档的真实关联概率值

：

3

评估&实验

1、估计无偏平均相关性

现在，为了用相关的IPS估计器来评估Fairco，该研究使用了一个自己的示例模拟。首先，从广告中抽取新闻文章作为测试媒体偏差数据集的样本，该数据集用两极化得分标记每个新来源。然后模拟访问这个网站的用户，这样每个用户都有一个相关的两极化得分和一个开放性参数。

一个用户新闻文章的真实相关度是新闻文章的两极化以及用户开放性的函数，其真实相关度分布服从伯努利分布：

我们的算法目标是将排名呈现给一系列进入的用户，以使他们的效用最大化，同时公平地接触所有的新闻文章。

Fairco会让“富人破产”吗?

在第一个实验中对一些右偏向性用户进行模拟，右偏向性用户可以通过在G-right文章中引入点击来偏向排名。可以看到公平控制器Fairco能从最初的偏差中恢复过来，同时仍在学习相关度。

别的排名算法很难打破最初少数用户造成的偏差，而Fairco能够将这种偏差减少到零，并将不公平性保持在较低水平，即使某些“富人”在一开始就有大量的领先优势。这就意味着最开始的“富人”是有破产的风险的，但是某些“富人”也可能会继续受用户“偏爱”而富下去。

Fairco是如何保护少数群体的偏好的？

可以看到，如果我们改变左偏向性用户在用户群体中的比例，Fairco可以始终将不公平性保持在接近零的水平，同时在其中一个群体占多数的情况下以公平换取效用，如右图所示。

2、估计无偏的条件相关性

到目前为止，我们只考虑了公共排名，比如豆瓣影评高分榜。但是现在我们想要个性化的排名，比如个性化的电影推荐。

我们仍然想确保它们的相关度分摊到所有用户，因此为了在Fairco里使用它们的情况下进行个性化排名，我们还需要定义如何估计条件相关性，这需要具体给出一些查询和文档特征。

神经网络派上用场

我们要学习一个评估器

，它是通过训练一个神经网络来进行学习的，通过最小化以下损失函数：

损失函数使用点击和位置倾向来形成一个平方损失的无偏估计量。这里的损失是无偏的，这意味着在期望中，误差的值等于完全信息平方损失。

当观察到真正的相关度是代替位置偏差点击时，现在我们使用这个评估器

来估计公平排名中的条件相关性，并对其进行保护，并评估结果，以在真实世界的数据集上测试Fairco算法的有效性。

3、Fairco算法在电影数据集上实验

该研究从ML-20M数据集中选择前五大制片公司的100部电影，以此作为电影镜头数据集的一个子集。然后在这些电影中选择10K个最活跃的用户。之后计算这些用户和电影之间的评分矩阵，并使用这个矩阵分解得到的用户特征作为模型的输入。

这里的目标是向每一个用户展示排名，最大限度地提高DCG指标，同时确保制片公司获得与他们电影平均元素相对应的曝光份额。

在这个实验中，本文展示了Fairco算法在公平性方面的有效性，与只根据无偏相关估计进行排名的D-ULTR方法相比，本文还比较了朴素估计，并证明了在测试集上不公平性归零，如下面两图的红线、绿线所示。

4

结论

1、论文确定了在动态学习排序中，有偏反馈是如何导致不公平和次优排序的。

2、论文提出了一种自适应的公平协同算法，在相关度仍在学习的情况下，强制执行相关度公平约束。另外Fairco算法易于实现，并且在运行时非常有效。

3、论文提出的算法打破了动态排名中“富者更富”的现象。

参考链接：

https://sigir-schedule.baai.ac.cn/poster/fp0069