可解释的差异补偿以实现高效的公平排名

摘要

由于基础数据的偏差，决策系统中使用的排名函数通常会针对不同人群产生不同的结果。 解决并补偿这些不同的结果是公平决策的关键问题。 最近的补偿措施主要集中在排名功能的不透明转变上，以满足公平保证，或使用配额或预留款来保证代表性不足群体成员获得最低数量的积极成果。 在本文中，我们提出了易于解释的数据驱动的排名函数补偿措施。 我们的措施依赖于向代表性不足群体的成员提供奖励积分，以解决排名功能中的差异。 奖励积分可以提前设置，并且可以组合，允许考虑表示的交叉点并为利益相关者提供更好的透明度。 我们提出了基于采样的高效算法来计算奖励点数以最小化差异。 我们使用现实世界的学校招生和累犯数据集验证我们的算法，并将我们的结果与现有的公平排名算法的结果进行比较。

我简介

排名函数广泛用于决策系统，例如资源分配、候选人选择或风险评估。 由于基础数据存在偏差，这些排名机制通常会产生不同的结果。 因此，补偿差异是现代决策系统确保更公平、更公平结果的关键任务。 了解偏差的来源有时并不明显，而是隐藏在相关性中，对于解决结果差异至关重要。 在本文中，我们提出了数据驱动的差异补偿措施，以透明地根据基础数据调整排名机制。 我们的措施旨在易于向利益相关者解释，以确保决策系统负责任且值得信赖。

现实世界系统中使用的排名功能的差异补偿机制主要依赖于软性或硬性配额的使用，以确保受保护群体成员的最低代表性。 配额（或预留）的优点是，当仅存在一个方面的不平等时（例如，为低收入学生预留入学所需的预留），易于实施和解释。 然而，一旦需要考虑多个维度的差异（例如英语学习者、低收入学生、残疾学生），配额的使用就变得麻烦且难以实施：两个或多个受保护类别的成员是否计入一个或多个配额？ 受保护类别的每种组合是否都有单独的配额？ [1] 随着更多维度的添加，设置准确的预留阈值对于利益相关者来说似乎是任意且反复无常的。

我们提出了一种基于使用补偿性奖励积分来解决排名应用中的差异的机制，如[2]（参见第III-D节）所定义。 视差表示统计奇偶性的缺乏，并通过测量公平属性空间中所选（高等级）和未选择（低等级）对象之间的距离来计算。 我们的奖励积分方法简单且易于理解，因为它将奖励积分直接与数据中的偏差来源联系起来。 它允许组合奖励点来模拟偏见的交叉性以及不同差异来源对排名决策结果的复合效应。 它可以快速、轻松地调整以适应新的数据和场景。

我们提出了用于识别奖励积分值的算法，该算法将最大限度地减少给定数据分布上的不同结果。 我们的工作基于基于样本的方法，该方法考虑基础数据分布并抽取样本来计算分配给每个视差因子的最佳奖励点数。 与现有技术相比，这种基于样本的方法具有三个主要优点。 首先，只要知道基本分布，它就可以在收集所有数据之前通过生成预期分布的样本来识别一组补偿奖励点。 这在向利益相关者提供透明信息至关重要的应用程序中可能是有益的（例如，让学生提前知道他们将按照哪些标准进行排名、进行了哪些以公平为中心的调整以及这将如何影响他们）。 其次，通过处理小数据样本而不是整个数据集，我们能够在亚线性时间内识别出高质量的补偿奖励点，而现有技术的运行时间高达指数级，并且对于大型数据集来说是不切实际的。数据集。 这使得我们的方法可用于许多现实世界的用例。 第三，使用奖励积分足够灵活，可以通过积分的复合效应来补偿多种不同的影响，从而解决偏见和差异的多种来源。

我们做出以下贡献：

• 基于对受保护类别成员的奖励积分的分配的排名函数的差异补偿模型。 （第 III 节）

• 视差补偿算法 (DCA)，用于识别补偿奖励点的最佳值，以最小化 top-$k$ 选择集的视差。 DCA 以亚线性时间运行（第 IV 节）。 我们提出对 DCA 进行修改，考虑整个排名，使用对数折扣技术[3]，以适应不同的选择大小（第 IV-E 节）。

• 对我们的补偿机制对两个现实世界数据源的影响进行了广泛的评估：用于高中招生的纽约市公立学校学生记录，以及用于估计保释和量刑决定中的累犯风险的数据集。 (V 和 VI 节）

• 与最先进的公平排名技术的比较表明，我们提出的 DCA 算法可产生可比较或更好的视差减少结果，同时显着提高效率。 (VI-C 节）

我们在第 II 节中介绍相关工作，在第 III 节中介绍激励性示例，并在第 VII 节中进行总结。

II 相关工作

提供具有公平结果的排名功能和系统的问题最近受到了广泛的关注。 多项调查对数据管理社区 [4, 5] 和推荐系统社区 [6] 中的文献提供了很好的概述。 这些调查根据公平性指标的应用时间，将公平性排名方法分为预处理、处理中和后处理技术。 预处理技术在应用排名函数[7]之前转换数据。 我们的方法可以归类为预处理，因为奖励积分在排名之前应用于数据。

已经讨论了供分类器使用的几种类型的预处理技术。 他们的目标是预处理数据，以便任意分类器不太可能导致不公平的结果。 这些转换通常是在事先不了解分类器机制的情况下完成的，这可能会限制这种方法的有效性。 一篇开创性的论文[8]讨论了分类器预处理数据的几种基本技术，例如抑制（完全删除对象的某些属性）和采样（其中一些对象是重复的，另一些对象是重复的）已删除。 他们还讨论了公平性与准确性的权衡：随着数据公平性的增加，分类器的准确性会降低； [9] 中进一步探讨了这种权衡，它提供了可证明公平的解决方案，而 [10] 则给出了基于凸优化的解决方案。 类似地，[11] 和 [7] 使用不同的公平概念解决类似的问题：因果公平，用户可以指定允许哪些属性影响结果[11]，以及个体公平性，其目标是确保对象受到与其最近邻居类似的对待[7]。

对于排名应用程序，更常用的是处理中方法。 这些方法通过学习技术[12]或操纵加权函数[13]来调整排名函数以优化给定的公平目标。 Celis 等人[14]提出了近似算法，以提供尽可能接近原始排名质量指标的排名，同时满足公平性约束。 Yang 和 Stoyanovich [3] 考虑一种基于概率的公平模型，其中每一类对象都应得到平等对待。 [15] 中也考虑了这种概率解释，它在只有一个受保护类的设置中提供了概率公平性保证；此设置在 [16] 中有所放松，但该方法依赖于所有受保护类的笛卡尔积，并且成本高昂。 这些方法的一个缺点是它们导致的排名功能通常不透明且难以向利益相关者解释；相反，我们的目标是使视差补偿过程透明且易于解释。

已经提出了与排名相关的几种公平概念； [17]在公平分类的背景下讨论了群体公平与个人公平的概念，并认为统计平等是公平的理想衡量标准。 我们使用的视差度量（第 III-B 节）可以解释为统计奇偶性的度量[2]。 暴露[18]经常被用作公平性的衡量标准，尽管文献中暴露的定义各不相同；我们在实验评估中使用与[19]相同的定义(VI-C4节）。 公平排名本质上涉及选择。 在[20]中，作者证明了不同的公平性度量是不兼容的，即使在近似的情况下也是如此。 在做出任何特定于数据集的选择之前，需要选择如何定义给定问题的公平性。 如上所述，我们关注公平性的统计平价解释，因为它很容易解释，并且不需要对潜在的偏见来源做出假设。

公平排名在现实世界中的一个常见应用是学校招生。 学区使用抽签来选择学生，作为整合学校和减少选择结果偏差的一种方式。 然而，彩票并不是解决差异的简单答案，实际上可能会加剧选择偏差[21]或成就偏差[22]。 为了确保多样性，纽约和芝加哥等许多学区[23]已成功选择为低收入学生预留配额。 然而，这些基于平权行动的方法已被证明可能对少数群体不利[24,25,26]，具体取决于潜在的择校模式。 此外，当多个群体应受到保护待遇时，基于配额的方法很难实施。 作品考虑了重叠配额[1]，以考虑候选者表现出多种受保护特征、配额的最小和最大界限[27]，或配额[28]。 这些方法的计算成本都很高。 相比之下，我们的差异补偿奖励点允许（1）对差异的每个维度（甚至重叠维度）进行有针对性的干预，以及（2）计算高效的方法。

III 背景

排名函数广泛应用于各种具有较高社会影响的决策系统中：招聘工具、学校招生、资源分配（例如疫苗、治疗、公共住房）或风险评估（例如欺诈、累犯）。 确保这些机制公平至关重要。 为此，我们提出了基于定向加分分配的差异补偿措施模型。

我们在第 III-A 节中介绍了我们工作的两个激励示例，并在第 III-B 节中设置了问题的定义和参数。

III-A 激励例子

纽约市高中招生

纽约市高中招生使用延迟录取 (DA) 匹配算法 [29]，类似于 Gale-Shapley [30] 设计的稳定婚姻算法。 该算法根据学生的偏好和学校的录取排名列表（评分细则）将学生与学校相匹配。 学校使用成绩、考试成绩、缺勤、试镜或面试等指标来制定自己的排名标准。 此类屏幕已成为争议话题，被视为歧视性目标，因为其生成的排名列表中的基本指标往往表现出高度不成比例，因为来自弱势群体的学生在评分细则中使用的某些指标中得分通常较低。

目前，纽约市教育部主要依靠为低收入学生预留（软配额）来解决差距并在每所学校培养多样化的学生群体。 这些措施的结果好坏参半，具体取决于学校地理区域的人口统计数据和学生的选择模式。 这些预留空间主要限于低收入学生，尽管也考虑了其他方面的不利因素（当前学校、英语学习者、临时住房的学生）。 然而，正如第II节中提到的，组合多个配额可能很麻烦并且计算成本很高。

在本文中，我们探讨了如何使用分配给表现出一个或多个方面劣势的学生的补偿性“奖励积分”。 我们的目标是确保学校招生标准所选择的学生能够充分代表底层人口。 由于纽约市使用匹配算法，因此无法提前知道学校会接受名单中排名靠前的学生；我们的技术可以通过最小化所有 $k$ 值的差异来调整所选对象 $k$ 数量的未知值，对数折扣以支持较小的 $k$ 值（第 IV-E 节）。 我们使用纽约市高中录取数据进行的实验评估表明，我们的补偿指标能够很好地适应多重选择百分比（第 VI-A 节）。

一些学校系统已经考虑使用基于积分的计划来实现学校多元化。 特别是，法国巴黎通过为弱势学生提供“奖励”积分，在改善社会经济多样性方面取得了良好的效果[31]。 然而，该系统是基于决策者随意决定的临时奖励积分，当积分校准不正确时，这会在一些学校产生一些不良后果：在一种情况下，一所高中被分配了绝大多数（83%）的低年级学生。 - 收入学生（而不是 40% 的统计均等目标），违背了多样性目的。 相比之下，我们提出了一种数据驱动的奖励积分分配方式，最能反映数据分布及其对排名的影响。

COMPAS 累犯数据

累犯算法（例如 COMPAS）用于预测与刑事司法系统互动的人再次犯罪的可能性，并被美国法院用来协助保释和量刑决定。 这些决策算法的影响是毋庸置疑的，但决策的不透明性使得很难验证过程是否公平。

2016 年，ProPublica 的一项调查[32]认为 COMPAS 算法对许多弱势群体，特别是美国黑人不公平。 内部COMPAS排名算法尚未公开； ProPublica 的调查基于佛罗里达州布劳沃德县通过公共记录请求获取的数据，并将这些数据公开。 随后，这个COMPAS数据成为评估公平机制的流行数据集；根据[4]中的公平性调查，它是公平性分析中最受欢迎的大型数据集。

虽然 COMPAS 用于将主题分类，但类别（十分位数）基于主题的基本排名。 十分位数分数经常被（错误地）用作累犯的绝对分数，而不是相对分数。 由于分数是基于比较数据，因此它们加剧了潜在的歧视性做法。 内部 COMPAS 算法是专有的，其内部工作原理和潜在的不同处理方式一直是争议和猜测的主题[33, 34]。 然而，COMPAS 十分位数分数在实践中的不同影响是不可否认的。 此外，该过程不透明且不易理解。 我们探索将差异补偿技术与 COMPAS 分数结合使用，以解决 COMPAS 工具的不同影响，并在第 VI-B 节中报告我们的结果。

COMPAS 数据集的使用一直受到有关此类数据的道德使用的多种批评[35]。 我们将 COMPAS 纳入案例研究绝不是认可其在现实生活决策中的使用，而是说明我们基于补偿的方法如何帮助显着减少各种类型的排名和分类功能的不成比例，即使这些隐藏在黑匣子专有系统后面。

III-B 定义

我们注重可解释性，以便利益相关者的公平薪酬选择简单、透明且易于理解。 这种可解释性的概念对于获得利益相关者的支持尤其重要[36]。 我们现在定义排名函数的格式（第III-B1节）和补偿奖励积分（第III-C节）以及我们的选择公平性指标（第 III-D 节）。

III-B1 排名功能

我们的解释重点是基于分数的排名函数。 我们的奖励积分还可以通过模拟基于排名的基础分数来适应其他排名功能（请参阅第 VI-B 节）。

定义1

基于分数的排名函数 我们在对象 $o$ 上的一组 $A$ 属性 $a_1,\mathrm{\dots }.,a_A$ 上定义基于分数的排名函数 $f$如$f(o)=f(a_1,\mathrm{\dots }.,a_A)$。 排名过程$R$选择具有最高$f(o)$值的$k$％最佳对象作为其答案$R_k$。

每个对象都有一组属性$A$，它们定义其属性并为其分配值。 出于这项工作的目的，我们认识到属性的一个特殊子集公平属性（在文献中也称为受保护属性），它代表我们想要控制偏见和不同影响的维度。 公平属性可以由排名函数$f$用来对对象进行评分，或者可以不参与排名，但仍然对评估结果的公平性感兴趣。

例如，学校可以根据学生 GPA 和考试成绩（属性）的加权总和，使用 100 分评分函数对申请人进行排名。 公平属性可能包括学生的低收入或残疾状况。

III-C 奖励积分

我们的方法以奖励积分为中心，以补偿各种方面的差异。 奖励积分乘以相应的公平属性值，并添加到最终的排名函数得分$f(o)$中。 当公平属性值为二元时，这相当于当该值等于1时将奖金添加到最终分数上。 例如，如果学校申请者的低收入状况被编码为 {0,1} 二进制，则 2 分的奖励将为每个低收入申请者的最终分数加 2；如果低收入状态被编码为[0,1]中的连续值，那么奖金2将乘以该属性的值，以给出更精确的差距补偿工具。

我们将奖励积分定义为：

定义2

奖励分 给定公平属性向量 $\overrightarrow{A_f}$ 和形状相同的奖励分向量 $\overrightarrow{B}$，让对象 $o$ 的分数定义为 $f_b(o)=f(o)+\overrightarrow{A_f}\cdot \overrightarrow{B}$

我们要求奖励积分为正（对于需要较低分数的情况为负）。 负奖励积分将被视为一种惩罚，可能不容易被利益相关者接受。

除了机制的灵活性之外，使用奖励积分的优点还包括：交叉性，奖励积分可以组合和复合，以解决多个维度的偏差； 透明度，利益相关者清楚公平干预的程度和影响； 可比性，可以轻松调整对象的分数并进行对象比较，增加透明度和信任度； 可预测性，结合如何进行选择的信息（例如历史阈值），申请人可以轻松评估自己的机会，并清楚了解采取哪些行动或干预措施是需要进行选择的。

例如，在我们的学校录取场景中，奖励积分可用于捕捉残疾学生和低收入学生的交叉性：具有这两种特征的学生将比具有一种特征的学生获得更多的奖励积分，或者没有任何。 这些信息可以在申请截止日期之前透明地发布，为家庭提供清晰、可预测和可比较的信息。 录取决定明确，公布了明确的门槛，并为每个申请者确定了每个排名属性的参与度和公平性补偿加分。 这为学生带来了更加透明和可解释的体验，他们在申请时知道自己的分数和公平性调整（如果有）。

III-D 差距

我们关注 [2] 中可解释的差异作为我们的目标公平性指标，因为它旨在满足统计奇偶性 [7]。 此外，它很容易被人类解释，即使维度数量增加也能表现良好，并且可以处理连续或离散数据的维度。

视差定义为平均选定对象与平均未选定对象之间的矢量差。 正式定义如下：

定义3

视差给定一组$O$对象和$O$中$k$%对象的选择$K$，让${\overrightarrow{D}}_O^F$ 为$O$在一组公平属性$F$上的质心，并让${\overrightarrow{D}}_k^F$为在$K$上选定对象的质心同一组属性。 我们将视差${\overrightarrow{D}}^F$定义为$|F|$维度视差向量，其中${\overrightarrow{D}}^F\equiv {\overrightarrow{D}}_k^F-{\overrightarrow{D}}_O^F$。

当理解公平属性集后，为了符号简单起见，我们省略 ^F:$\overrightarrow{D}\equiv {\overrightarrow{D}}_k-{\overrightarrow{D}}_O$

直观上，视差衡量的是平均选定对象与总体平均对象之间的差异。 离散维度的差异值表示需要更改以实现统计奇偶校验的所选集合的百分比。 例如，如果人口中 30% 属于低收入，而选定群体中 20% 属于低收入，则将导致 30 - 20 = 10% 差距或 0.1。 这意味着，如果所选群体中有 10% 从非低收入变为低收入，那么就会出现统计平等。 对于连续公平属性，视差根据值的范围进行归一化。 例如，在收入为 [$0;$200,000] 的人群中，如果该人群的平均收入为 40,000 美元（标准化为 0.2），而所选群体的平均收入为 100,000 美元（标准化为 0.5），则会导致差异60,000 美元（标准化为 0.3）。 每个公平属性都是视差向量的一个维度。 假设所有值均在 0 和 1 之间标准化，则视差大小为 -1 或 1 分别意味着受保护属性仅存在于总体中或仅存在于受保护集中。 差异为零表示统计奇偶性。

IV 视差补偿方法

我们现在提出我们的差异补偿方法。 我们首先在第 IV-A 节中强调我们旨在解决的几个挑战。 在第IV-B节中，我们描述了我们的主要贡献——视差补偿算法（DCA）；我们在IV-C节中讨论了DCA的准确性，并在IV-D节中提供了它的时间复杂度。

IV-A 挑战

我们的目标是找到分配给受保护群体的最佳分数，以尽量减少差异。 该任务可以被认为是一个优化任务，其目标是选择一个奖励向量$\overrightarrow{B}$，使得视差向量$\overrightarrow{D}$的$L^2$范数被最小化。 形式上，我们希望最小化差异：

$\underset{𝐵}{\text{minimize}}$ ${\Vert \overrightarrow{D}(\overrightarrow{B})\Vert }_2$ subject to $b_i\ge 0$

其中 $\overrightarrow{D}(\overrightarrow{B})$ 是给定群体的差异，作为上面定义的奖励向量的函数，包含给予每个公平属性的奖励点数。 由于以下挑战，这种最小化变得复杂。

1. 有大量可能的解决方案。 这意味着大多数传统算法解决方案都非常慢。 例如，最近的公平算法是超多项式[16]，并且不易扩展。

2. 在集合选择任务中，例如识别 $k$ 对象，评估排名公平性的度量是阶跃函数，因为它们的值随着每个新选择的候选者或排名顺序的每次变化而变化。 因此，奖励点向量的微小变化可能会导致视差发生任意大的变化，这意味着优化函数不平滑或不连续。 因此，它们是不可微的，并且标准的基于导数的优化方法不适用。

3. 我们的最小化函数不表现出凸性，甚至不表现出拟凸性，这使我们无法使用凸优化技术。

4. 评估每个可能的解决方案的成本很高，因为它需要对数据集进行重新排序。 因此，非微分（无导数）优化解决方案效率低下，因为它们通常会对数据重新排序数百次[37]。

5. 出于实际目的，我们的方法需要足够快，以便功能设计者（例如学校管理人员）可以迭代多个选项来评估公平性调整的影响。 .

为了应对这些挑战，我们建议使用一种新颖的基于下降的方法来计算正确的奖励点数以消除差异

IV-B 视差补偿算法

Result: $\overrightarrow{B}$

O $\leftarrow$ the entire set of available objects;

k $\leftarrow$ size of the selection;

lr $\leftarrow$ list of learning rates sorted in decreasing order;

t $\leftarrow$ number of iterations;

$\overrightarrow{B}$ $\leftarrow$ weight vector of dimensionality equal to number of fairness attributes initialized randomly;

for L in lr do

for x in t do

S $\leftarrow$ A random sample of $sample\mathrm{\_}size$ from O;

${\overrightarrow{D}}_k$ $\leftarrow$ Disparity of the $k$ selection over S after applying $\overrightarrow{B}$ bonus points;

$\overrightarrow{B}$ $\leftarrow$ $\overrightarrow{B}-L\times {\overrightarrow{D}}_k$;

for D in $\overrightarrow{B}$ do

$D\leftarrow max(D,0)$

end for

end for

end for

Algorithm 1 Core DCA

Result: $\overrightarrow{B}$

A $\leftarrow$ An array for computing the average;

O $\leftarrow$ the entire set of available objects;

$\overrightarrow{B}$ $\leftarrow$ The output vector of DCA;

k $\leftarrow$ size of the selection;

t $\leftarrow$ number of iterations for refinement;

for x in t do

S $\leftarrow$ The next sample in O;

${\overrightarrow{D}}_k$ $\leftarrow$ Disparity with $\overrightarrow{B}$ bonus points over S;

$\overrightarrow{B}$ $\leftarrow$ Adam.step($\overrightarrow{B},{\overrightarrow{D}}_k$);

A $\leftarrow$ $A+\overrightarrow{B}$;

end for

return ROUND(AVERAGE(A));

Algorithm 2 DCA Refinement

传统的基于下降的方法不能应用于我们的设置，因为大平台和步骤的存在使得函数不可微分；标准梯度下降方法是基于导数的，不能用于不可微的优化函数。 我们通过直接使用视差向量而不是其梯度来规避这个问题。

我们的视差补偿算法（DCA）（算法1)基于这样的观察：一个维度中任何旨在补偿该维度视差的下降运动只要它能产生更好的结果不翻转视差 $\overrightarrow{D}$ 的符号（即，产生相反的不同影响）。

我们考虑的是我们希望在未来的决策中防止出现不同结果的情况，而不仅仅是在已知的数据集上。 因此，仅仅完美地解决训练数据的差异是不够的，我们的解决方案必须适用于任何类似的数据集。 然后，训练数据可以被视为从基础分布中提取的样本，我们的目标是最小化该分布的差异。 因此，我们可以使用中心极限定理和分位数中心极限定理[38]来估计排序函数对基础分布的选择性（第IV-C节）。 如果已知数据集的预期分布，我们的方法可以在没有训练数据的情况下类似地应用。

算法如算法1所示。 DCA 的工作原理是保留一个奖励向量，该向量在视差的相反方向上增量调整。 DCA 通过降低学习率（步长）来循环，以将视差向量（记为 $\overrightarrow{D}$)减小到尽可能接近零。 对于每个学习率，算法会在固定数量的步骤$t$上调整奖励向量，以使用该学习率尽可能接近零；然后它下降到下一个学习率。 在每个步骤中，仅根据从总体分布（或代表性集合）中均匀随机抽取的小样本训练来计算视差。 整个对象集 $O$ 永远不会被直接查看。 对于每个学习率，我们采用固定数量的样本。 在每个步骤中，DCA 使用样本上的视差来预测整个分布上的视差，并使用奖励分 $\overrightarrow{B}$ 的当前最佳猜测。 然后 DCA 在视差的相反方向上调整当前的最佳猜测。 例如，在上述情况中，如果人口中 30% 为低收入，而所选群体为 20% 低收入，则将导致 10% 的差异或 0.1。 当学习率为 0.2 时，群体中的每个低收入成员将在下一次迭代的评分函数中获得 $0.1\times 0.2=0.02$ 额外分数。 然后，将采集新样本并进行排序，并再次计算差异。

我们在算法2中提出了一个细化步骤。 细化过程由一个 for 循环组成，该循环使用自适应学习率（使用 Adam 方法[39])来找到最佳估计。 Adam 方法不是对所有参数使用固定的学习率，而是对每个参数使用单独的学习率，该学习率根据梯度的变化（或者在我们的例子中为视差）单独优化。 Adam 方法对于处理样本产生的噪声特别有用且流行。 接下来，取猜测的平均值，以进一步减少随机样本产生的噪声并获得更一致的结果。 正如我们将在第 VI-A5 节中通过实验看到的那样，此细化步骤会产生更平滑的视差补偿结果。

$lr$ 和 $t$ 的值提供了时间和准确性之间的权衡。 我们根据实验经验设置它们(V 节）。

IV-C DCA的准确度

为了显示 DCA 的准确性，我们首先考虑 DCA 的一种变体，称为完整 DCA，它考虑整个数据集，而不是样本。 考虑两个对象$p$和$q$,$q$在top-$k$和$p$在top-$k$。 如果交换他们的位置会减少差距，Full DCA 将始终减少他们之间的分数差异。 正式：

定理IV.1

在Full DCA的每一步，如果从top-k中删除对象$q$并用对象$p$替换它会减少整体差异，Full DCA将在该步骤分配更多的奖励点$p$ 比 $q$ 更重要。

从数学上讲，这意味着：

或者

$$0>\overrightarrow{D}\cdot (\overrightarrow{F_p}-\overrightarrow{F_q})$$

其中$\overrightarrow{F_p}$和$\overrightarrow{F_q}$是公平属性向量，$\overrightarrow{D}$是视差，$L$是步长，$\overrightarrow{B}$ 是奖励向量。 当使用 DCA 而不采样时，这始终是正确的。 这可以从视差的定义和给定的假设看出，切换这两个对象将减少视差：

$${|\overrightarrow{D}|}_2>{|\frac{1}{s}\sum _{i\in \text{S}}{F}_i+\frac{1}{s}\times \overrightarrow{F_p}-\frac{1}{s}\times \overrightarrow{F_q}-\overrightarrow{Q}|}_2$$

其中 Q 是整个分布的质心（在 DCA 运行期间保持不变），s 是所选对象的数量。 使用 $L_2$ 范数的定义，我们看到上述不等式仅在以下情况下成立：

$$\overrightarrow{D}\cdot \overrightarrow{D}>\overrightarrow{D}\cdot \overrightarrow{D}+\frac{2}{s}\times (\overrightarrow{F_p}-\overrightarrow{F_q})\cdot \overrightarrow{D}+\frac{1}{s^2}\times (\overrightarrow{F_p}-\overrightarrow{F_q})\cdot (\overrightarrow{F_p}-\overrightarrow{F_q}))$$

这简化为：

$$-\frac{1}{2s}\times (\overrightarrow{F_p}-\overrightarrow{F_q})\cdot (\overrightarrow{F_p}-\overrightarrow{F_q})>\overrightarrow{D}\cdot (\overrightarrow{F_p}-\overrightarrow{F_q})$$

由于左边总是负数，我们已经证明

$$0>\overrightarrow{D}\cdot (\overrightarrow{F_p}-\overrightarrow{F_q})$$

并且$p$将始终比$q$获得更多的额外奖励积分。

与完整 DCA 不同，DCA 依靠分布样本来有效识别最佳奖励点向量 $\overrightarrow{B}$，并将其应用于公平属性集 $F$，以最小化差距。 DCA 的准确性取决于样本上视差度量 $\overrightarrow{D}$ 计算的准确性，作为整个数据集上视差的估计量。

视差 $\overrightarrow{D}$ 计算为所有对象 $O$、${\overrightarrow{D}}_O$ 集合上的质心与 $K$ 的质心之间的距离> 选定的对象，${\overrightarrow{D}}_k$（第III-B节）。 在本节中，我们将展示通过数据集样本计算 ${\overrightarrow{D}}_O$ 和 ${\overrightarrow{D}}_k$ 可以很好地估计它们在整个数据集上的值。

引理IV.2

样本 $s$ 在一组对象 $O$ 上的质心 $\overrightarrow{D_s}$ 是对质心 ${\overrightarrow{D}}_O$ 的无偏、低误差估计覆盖整个对象集$O$。

这一结果直接源自中心极限定理，该定理指出，只要样本量足够大（至少 30），样本的均值就会近似于原始分布的均值。

接下来，我们证明样本 $s$ 中 $k^{th}$ 百分位处的对象得分是 $k^{th}$ 百分位处对象得分的良好估计器在整个分布上。

引理IV.3

样本 $s$ 在一组对象 $O$ 上的量化值 $k$ 的得分是对整个对象 $O$ 在量化值 $k$ 上的得分的无偏、低误差估计。

该引理是分位数中心极限定理的直接结果。 [38]，表示样本的分位数$k$近似于原始分布的相应分位数，只要样本在$1-k$ 只要样本大小至少为 $\frac{1}{k}$，就满足此条件，这为我们提供了 DCA 中使用的样本大小的下限。

对于接近 0 或 1 的 $k$ 值，作为估计量的样本分位数的方差可能很大，并且在这些情况下可能会导致低质量的估计。 这在现实世界的实验中得到了体现，如VI-A3部分所示；但是，对于合理的 $k$ 值，样本的 $k^{th}$ 百分位数是分布的 $k^{th}$ 百分位数的准确估计值。

引理IV.4

一组对象 $O$ 上的样本 $s$ 的 $k$ 所选对象百分比的质心 ${\overrightarrow{D_s}}_k$ 是无偏的、低误差的，估计所选对象在整个对象集 $O$ 中的百分比 $k$ 的质心 ${\overrightarrow{D}}_k$。

从引理IV.3我们知道样本$s$的$k^{th}$百分位值是$k^{th}$百分位值的估计量所有对象$O$的分布。 因此，来自 $s$ 的前 $k$ 百分比对象与来自 $O$ 的前 $k$ 百分比对象取自相同的分布： $O$ 在 $k^{th}$ 百分位数处截断。

从中心极限定理我们知道，只要样本量足够大（至少30），样本的均值就会逼近原始分布的均值。 由于样本 $s$ 和 $O$ 的前 $k$ 百分比选择均取自同一分布，因此适用中心极限定理，并且 ${\overrightarrow{D_s}}_k$ 是 ${\overrightarrow{D}}_k$ 的无偏、低误差估计。

从以上结果可以看出：

定理IV.5

样本视差 $\overrightarrow{D_s}\equiv {\overrightarrow{D_s}}_k-{\overrightarrow{D_s}}_O$ 是整个数据集视差 $\overrightarrow{D}\equiv {\overrightarrow{D}}_k-{\overrightarrow{D}}_O$ 的无偏、低误差估计。

IV-D DCA的时间复杂度

DCA 的时间复杂度不取决于数据集的大小，而是取决于样本大小和分布特征，这在实践中可以实现快速性能。 这是因为 DCA 专注于纠正基础分布中的差异，而不是特定数据集。 训练数据集代表隐藏分布上的更大样本。 这使得 DCA 的执行时间取决于（较小的）样本的大小，而不是数据集的大小。 该算法所花费的时间是计算一个样本差异所需时间的常数倍。 这次是

$$O(sample\mathrm{\_}size\times log(sample\mathrm{\_}size))$$

如果样本已完全排序。 样本量需要足够大，才能应用中心极限定理，一般认为在 30 左右。 这意味着 $30=sample\mathrm{\_}size\ast k$ 且样本大小为 $O(\frac{1}{k})$。

此外，出于同样的原因，每个感兴趣的子组都需要以合理的数量出现在样本中，因此中心极限定理可以适用。 这导致最终样本大小为 $O(max(\frac{1}{k},\frac{1}{r}))$，其中 $k$ 是排名过程选择的元素比例，$r$ 是最不常见组的频率。数据集。 鉴于此，假设 $k$ 足够大，必须对整个样本进行排序，则 DCA 的时间复杂度不依赖于数据集的大小，为：

$$O(max(\frac{1}{k},\frac{1}{r})\times log(max(\frac{1}{k},\frac{1}{r}))$$

IV-E 针对$k$的多个值调整DCA的优化目标

我们针对提前知道选择 $k$ 大小的情况提出了 DCA。 然而，当 $k$ 事先未知时（例如学校匹配应用程序中的排名列表），或者使用整个群体的排名时，优化整个排名通常很有用。

我们提出了对 DCA 的修改，更新了视差的定义，以使用整个排名以及 [3] 中描述的对数折扣技术，为首先选择的对象分配比最后选择的对象更重要的重要性。 对数折扣将 k 处的差异替换为我们第 III-D 节的最小化目标：

$$\frac{1}{Z}\sum _{i\in 10,20,30..}^{i=k}\frac{{\overrightarrow{D}}_i}{lo{g}_2(i+1)}$$

其中 Z 是定义为最大可能值的归一化因子。

算法 1 和 2 中 ${\overrightarrow{D}}_k$ 的计算被这个新的对数贴现视差所取代。 这个新指标保留了前一个指标的有用特征：它是一个向量，每个维度代表一个单独的公平属性并独立计算，它的范围在 -1 表示在一个方向上完全不公平到 1 表示在另一个方向上完全不公平，是等于 0 表示公平表示，并且可以通过其范数来概括。

当使用对数贴现视差时，第IV-A节的最小化问题改为：

$\underset{𝐵}{\text{minimize}}$ ${\displaystyle \sum _{j\in 10,20,30..}^{j=k}}{\displaystyle \frac{{\Vert {\overrightarrow{D}}_j(\overrightarrow{B})\Vert }_2}{lo{g}_2(j+1)}}$ subject to $b_i\ge 0$

其中 ${\overrightarrow{D}}_j$ 是与 $k=j$ 的差异。

就时间复杂度而言，使用 DCA 的对数贴现视差版本需要更长的时间，额外增加了样本大小的一个因素，因为我们需要评估样本中每个点的视差，从而导致总时间为：

$$O((max(\frac{1}{k},\frac{1}{r})\times log(max(\frac{1}{k},\frac{1}{r}))\times max(\frac{1}{k},\frac{1}{r}))$$

通常，用户只对排名的一部分感兴趣。 对数折扣差异可以根据不同的排名需求进行调整。 例如，用户可能只对排名的上半部分感兴趣。 在这种情况下，可以忽略排名该部分之外的视差，并且仍然可以仅针对 的值直接计算折扣视差。

V 实验设置

现在，我们描述评估中使用的数据集、为实现 DCA 算法而设置的参数以及我们的实验环境。

V-A 数据集

纽约市学校数据集

我们使用来自纽约市的真实学生数据来评估我们的算法，这些数据是通过纽约市数据请求[40]收到的，并且我们已获得 IRB 的批准。

本文使用的数据包括 2016-2017 学年和 2017-2018 学年各约 80,000 名 7${}^{\text{th}}$ 年级学生的成绩、考试成绩、缺勤和人口统计数据。 当学生处于 8${}^{\text{th}}$ 年级时，纽约市高中使用第 III-A 节中描述的入学匹配系统；因此，用于对学生进行排名的各种属性来自他们的 7${}^{\text{th}}$ 成绩成绩单。 我们使用2016-2017学年的数据作为训练数据，使用2017-2018学年的数据作为测试数据。

我们选择排名函数来模拟几所真实的纽约市高中在 2017 年和 2018 年招生时使用的录取函数：加权和函数 $f=0.55\ast GPA+0.45\ast TestScores$，其中 $GPA$ 是标准化的学生数学、ELA、科学和社会研究成绩的平均值，$TestScores$ 是数学和 ELA 州测试成绩的标准化平均值。 除非另有说明，我们认为 5% 的学生被选中。

该数据集包括人口统计数据以及有关学生当前学校的信息。 我们考虑公平的以下维度：

• 低收入：在纽约市公立学校系统中，$70\%$ 的学生符合低收入资格。

• ELL：英语学习者。 由于考虑 ELA（英语语言艺术）成绩和考试成绩的录取方法，这些学生显然处于不利地位。

• ENI：经济需求指数，衡量与该学生就读同一所学校的学生的总体经济需求。 ENI 计算为学校中有经济需要的学生的百分比。 如果一所学校的经济需求指数 (ENI) 至少为 $60\%$，则该学校被定义为高度贫困。

• 特别版： 正在接受特殊教育服务的学生。

康帕斯

COMPAS 数据集包含佛罗里达州布劳沃德县的累犯数据，这些数据是 2016 年 ProPublica 调查的结果。 该数据集包含 7214 名被告的个人人口统计信息、犯罪历史、COMPAS 累犯风险评分、2 年内的逮捕记录。 COMPAS 十分位数分数代表被告与目标比较被告群体相比的十分位数排名，范围从 1 到 10。

我们将十分位数分数视为排名函数（越低越好，请参阅第VI-B节中的讨论），并使用种族作为公平属性来计算补偿奖励分。

V-B 评价参数

奖励积分。

奖励积分可以理解为属性值的乘数。 当属性为二元时，奖励分值将添加到具有该属性的对象的分数中（例如，ELL 的奖励分将添加到标记为英语学习者的学生的分数中）。 对于连续属性，奖励积分的值乘以属性的值（例如，学生就读学校的ENI值将乘以ENI奖励积分，所得结果将添加到分数中）学生）。

在算法的最后一步，我们根据利益相关者的决定，舍入到所需的奖励点粒度。 为了简单和高效，我们在两种评估场景中将奖励积分限制为粒度为 0.5 分的值。

DCA 对比 核心DCA

在VI-A5节中，我们评估了算法2的细化步骤对算法1 在本文的其余部分，我们使用名称 DCA 来指代应用了细化步骤的算法。

算法 DCA - 样本大小。

我们最稀有的公平类别的频率为 10%，因此我们选择了 500 个元素的样本大小，以确保代表 50 个元素（默认选择百分比为 5%），足以显示属性之间的大部分相关性。

算法 DCA - 学习率。

我们尝试了不同的学习率，并确定了 3 组 DCA，每个学习率 100 轮。 在第一遍中，我们使用学习率为 1。 这为我们提供了正确的搜索区域。 我们使用 0.1 的学习率来进一步磨练正确的位置。 然后，我们使用现代权重更新算法 Adam 对数据进行第二次遍历，以找到最佳奖励分值[39]。 最后，我们取最后 100 个点的滚动平均值，以提高稳定性并避免临近结束时异常样本产生太多随机影响。

V-C 实验环境

实验全部在具有 30GB RAM 的 Optiplex7060 上进行。 该机器配备 Intel(R) Core(TM) i7-8700 CPU @ 3.20GHz。 我们提出的算法是使用 Python 3.8 和 Pandas 实现的。 比较算法（多项式 FA**IR）是使用 [16] 作者的实现在 Java 中实现的。

VI评估结果

我们现在讨论使用我们的数据集和各种设置的 DCA 的详细评估结果。

Baseline Disparity	Low-Income	ELL	ENI	Special Ed	Norm
Training 2016-2017	-0.252	-0.106	-0.176	-0.191	0.377
Test 2017-2018	-0.24	-0.105	-0.179	-0.191	0.37
Core DCA	Low-Income	ELL	ENI	Special Ed	Norm
Bonus Points	2.0	11.0	11.0	14.0	-
Training 2016-2017	0.051	0.018	0.001	0.049	0.073
Test 2017-2018	0.052	-0.006	-0.001	0.029	0.06
DCA	Low-Income	ELL	ENI	Special Ed	Norm
Bonus Points	1.0	11.5	12.0	12.0	-
Training 2016-2017	-0.018	0.001	0.001	-0.014	0.023
Test 2017-2018	-0.01	-0.017	0.005	-0.028	0.034

表一： 奖励积分前后纽约市高中数据的视差向量

VI-A 学校数据集的结果

VI-A1 视差缩小

表I显示了每个目标公平性维度和总体（Norm）的差异值。 表的顶部显示了使用学校排名函数选择 $5\%$ 名学生且未进行任何视差校正时的基线视差。 我们可以看到，对于这两年以及我们所有的公平目标来说，差距都很大：例如，低收入学生在选择中的比例$25\%$少于总人口中的比例。 总体而言，差距为0.37。 请注意，差异为 0 是目标，绝对值越高，存在的差异越大。 差异的符号给出了这种影响的方向：负值表示代表性不足，正值表示代表性过高。

表的底部显示了 DCA 算法产生的奖励积分以及由此减少的差异。 我们可以看到，对于所有目标属性，在对训练和测试数据集应用奖励分后，差异几乎为 0。 整体差距也接近于0。 达到这些结果所需的奖励积分数量很容易理解：例如，由于 ELL 学生因包含 ELA 成绩和分数而处于不利地位，因此他们在排名功能上获得 11.5 奖励积分，以平衡竞争环境。 用于解决低收入学生所遭受的差距的奖励积分数量出人意料地低：只给他们 1 个奖励积分就可以使他们在所选组中达到统计平等，这可能是因为 ENI 也捕捉到了经济劣势。

VI-A2 公用事业

在公平排名应用中，效用衡量差异补偿方法对原始排名的影响程度。 简单来说，它衡量新排名与未修正排名的差距。

效用的常见衡量标准是 $nDCG$，或标准化贴现累积收益 [41, 15]。 标准贴现累积收益$DCG$定义为：

$$\sum _{i=1}^k\frac{w_i}{lo{g}_2(i+1)}$$

$nDCG$定义为测量的$DCG$与理想$DCG$的比率。 在公平排名应用中，理想的$DCG$是应用公平补偿之前的原始排名。

1 分意味着公平补偿完全不会影响效用：排名不变。 对于我们默认的学生$5\%$选择集，DCA的$nDCG\mathrm{@}0.05$是0.957。 这与处理多个公平维度的其他公平排名算法相当。 [16]。 图 1 报告了 $nDCG\mathrm{@}k$，其中 $k$ 表示所选学生的比例，显示出对所有选择百分比的良好实用性。

Figure 1: $nDCG\mathrm{@}k$ on the school data (Test dataset) for varying $k$

Figure 2: $nDCG\mathrm{@}k$ and disparity norm on the school data (Test dataset) for varying proportions of total recommended bonus points

Figure 3: Disparity on the school data (Test dataset) for varying proportions of total recommended bonus points

DCA 可以轻松地针对不同的所需公平阈值或效用值进行校准。 奖励积分可以通过权重乘法因子进行调整，以降低奖励积分的重要性并增加效用（由$nDCG$衡量）。 可以通过二分搜索来选择要应用的正确奖励积分比例。 图2显示了对奖励积分应用减少权重对效用和差异的影响。

图3显示了我们调整奖励积分总比例时差异的详细细分。 该函数的阶跃性质是由于我们限制奖励积分为 0.5 的倍数。 该函数接近线性，应用一半的最佳视差减少奖励点，提供大约一半的视差减少。 这表明 DCA 可以轻松调整，为任何给定的效用或公平阈值提供解决方案。

VI-A3 改变选定对象的百分比的效果

(a) Disparity adjusted for k on the school data when k is known in advance

(b) The disparity across all k when k is assumed to be 5% The bonus vector for this graph is: {Special-Ed:13, Low-Income:1.5, ELL:10.5, ENI:12.0}

(c) The disparity across all k when k is assumed to be logarithmically discounted for k0.5 the bonus vector, In this case, the bonus vector is {Special-Ed:13.5, Low-Income:2, ELL:9.5, ENI:18.5}

图4： 在 School 数据集上使用 DCA 进行实验

一些应用程序提前确定所选对象的数量（例如疫苗分配）。 其他人可能会受到外部因素的影响，这些外部因素会改变所选对象的数量，例如通过候补名单流程。 如第 III-A 节所述，纽约市学校招生由匹配算法处理。 学校事先并不知道他们会接受排名靠后的学生，因为这取决于许多因素：学生的选择、其他学校的排名和招生目标。

正如 IV-E 节中所讨论的，我们的算法可以通过不同的方式来解释所选对象 $k$ 百分比的变化：

• 如果 $k$ 已知，我们的算法可以针对特定值进行优化并给出出色的结果。 在图4(a)中，显示了针对不同的$k$校正之前（虚线）和之后（实线）的视差。在每种情况下，考虑到选择性，DCA 都成功地从根本上消除了差异。

• 如果$k$在奖励积分分配时未知但可以近似，则可以针对近似值优化DCA，并在该估计值接近真实值时产生良好的结果（图4(b))。 然而，当 $k$ 未正确估计时，视差结果会降低。

• 如果 $k$ 未知，或者几个不同的 $k$ 值很重要，我们使用对数贴现方法（第 IV-E 节）将奖励积分设置为该设置将为排名列表中许多不同 $k$ 值的加权平均值提供最佳视差结果。 这意味着 DCA 的目标是最小化许多 $k$ 值之间差异的加权平均值，而不是仅最小化特定 $k$ 处的差异。然而，如果在选择奖励点时已知 k 的确切值，则选择一个奖励向量来最小化 $k$ 的确切值的差异可为该特定 $k$ 提供更好的结果，以 $k$ 的其他值的平均值更高为代价。通过比较图4(b)和图4(c)在$k=0.05$处的差异可以看出这一点。 虽然图4(c)最多具有较低的差异$k$，但图4(b)显示DCA专门针对$k$接近 0.05，并且当 $k$ 接近 0.05 时效果更好。

Figure 5: Log-Discounted disparity when there is a maximum number of bonus points

Figure 6: The disparity reduction achieved by a simple quota system

Figure 7: Accuracy vs. disparity for both DCA and the ($\mathrm{\Delta }$ + 2)-approximation algorithm (training Dataset)

VI-A4 最高奖金限额

DCA 可以轻松地进行调整，以使用预设的最小和最大奖金值来限制其分配的奖金值。 本文中的所有实验都限制 DCA 永远不会给出负奖励，因为这些可以被视为惩罚。 如果需要，还可以设置最大奖金。 每个精炼步骤的奖励积分数量可以设置上限；这可能会导致相关非上限属性的调整。 图 5 显示了当奖金金额限制在 0 到 20 之间时 的对数折扣差异。 由此产生的差距会受到明显的影响，当最大奖励积分数较小时，结果最差，但随着最大奖励积分数的增加，差距会变小。

VI-A5 细化步骤的影响

(a)

(b)

Figure 8: Evaluation of the DCA Refinement Step on the School dataset. (a) Disparity adjusted for k on the school data when k is known in advance, using Core DCA without refinement, (b) Time taken for each k in both the unrefined (Core DCA) and refined version (DCA).

Figure 9: Norm after optimization with DCA for Disparity (dotted lines), or Disparate Impact (solid lines). Disparity in blue, Disparate Impacts in black.

表 I 显示算法 2 的细化步骤比单独的核心 DCA 算法 1 的结果有所改进。 在学校数据集中，这些改进大约是三倍。 图8(a)显示与图4(a)相同的设置，但没有细化步骤。 我们看到，除了更好的视差补偿之外，细化步骤还产生了更平滑的结果。

图8(b)显示了核心DCA和细化后的DCA所花费的时间。 在大多数情况下，细化步骤大约需要 10 秒。 如图所示，$k$ 值较小时，成本较高。这是因为 DCA 所需的样本大小取决于 $max(\frac{1}{k},\frac{1}{r})$。 当 k 很小时，样本大小需要增加，这会导致执行时间更长。 一旦 $\frac{1}{k}$ 变得足够小到 5%，样本大小将基于 $r$（数据集中最不常见组的频率），这对于数据集中的所有设置都是相同的。 然而，随着 k 的增加，作为视差 $\overrightarrow{D_k}$ 计算一部分的质心计算需要更长的时间，因为考虑的元素更多。

这些结果显示了细化步骤的好处。 如果需要更快的执行时间，则可以省略此步骤，但会造成一些质量损失。

VI-B COMPAS 数据集的结果

(a) The Disparity of the COMPAS algorithm when bonus points are added to the decile scores and computed for each $k$

(b) The False Positive Rate of the COMPAS algorithm when bonus points are added to the decile scores and computed for each $k$

(c) The Disparity of the COMPAS algorithm when bonus points are computed once using the log discount mode of DCA

图10： 在 COMPAS 数据集上使用 DCA 进行实验

图10(a)显示了基于种族的COMPAS十分位数分数的基线差异（虚线）。 对于黑人来说，这种差异很明显，因为他们更有可能被标记为累犯风险，而白人则被标记为累犯风险的可能性要小得多。 DCA（全线）提供的奖励积分补偿可以显着缩小这种差距。

试图解决 COMPAS 数据差异的一个困难是它的分数非常粗略：它们只有 10 个可能的分数，这使得奖励积分很难产生影响。 当在图10(c)中使用DCA的对数贴现模式时，这一点可以最清楚地看到：随着每个新桶移入所选集合，视差急剧变化。 然而，如图10(a)和10(c)所示，所有情况仍然导致视差显着减小。

VI-C 与现有方法和指标的比较

VI-C1 与现实世界配额系统的比较

如前所述，基于配额的方法很难扩展到多项式情况。 许多现实世界的环境，例如纽约市的学校系统，对所有不同的公平维度使用一个配额。 图6显示该方法确实减少了视差，但效果不如DCA（图4)。

VI-C2 与多项式 FA**IR 的比较

我们还在学校数据集上将 DCA 与多项式 FA**IR 方法[16]进行了比较。 多项式 FA**IR 是一种后处理方法，可在保证公平性的情况下对数据集进行重新排序。 多项式 FA**IR 仅适用于不重叠的公平性参数，因此我们查看了所有参数的笛卡尔积，并选择了 3 个最受歧视的子组作为我们的公平性晴雨表，如 [16]< 中所建议的/t0>. 由于多项式 FA**IR 的效率限制，我们只能在纽约市学校的单个学区（包含 2,500 名学生）上运行他们的代码，而不是整个数据集。 我们在表II中报告了我们的结果。 我们看到，虽然这两种方法都显着改善了差异，但 DCA 由于其处理重叠子组的能力而产生了更好的结果。

	Low-Inc	ELL	Sp. Ed	Norm
Baseline	-0.262	-0.036	-0.179	0.320
Bonus Points	2	9	5	-
DCA	0.009	-0.011	0.001	0.007
Mult. FA**IR	-0.084	-0.036	-0.052	0.105

表二： DCA 与多项式 FA**IR 的比较

VI-C3 与 ($\mathrm{\Delta }$ + 2) 近似算法的比较

由于多项式 FA**IR 的时间复杂度，我们还与 [14] 中的更快近似算法 ($\mathrm{\Delta }$ + 2) 进行了比较。 该算法的工作原理是查看所有（位置，项目）对并贪婪地选择最能提高效用的一对（在我们的例子中由 nDCG 测量），而不违反对每种类型的最大项目数的预设（输入）公平性约束。 为了进行公平比较，我们将DCA实现的视差($\mathrm{\Delta }$ + 2)作为其输入预设公平性约束。 与 DCA 不同，($\mathrm{\Delta }$ + 2) 是一个后处理步骤，仅适用于现有结果；因此我们将其与 DCA 一年的结果进行比较。 如图7所示，($\mathrm{\Delta }$ + 2) 获得的结果与 DCA 非常相似。 就效率而言，该算法很大程度上取决于选择的项目$k$的比例。对于较小的 $k$ 值（例如 5%），其性能与 DCA 类似，大约需要 30 秒；对于较大的值（例如 30%），需要大约 30 分钟，这使得 DCA 成为更快的选择。

VI-C4 接触

曝光度是衡量排名公平性的常用指标。 它被定义为对象具有排名顺序中的位置的概率乘以该位置的值的总和。 不同来源对职位的价值有不同的定义；我们使用了[19]中的定义。 他们将暴露定义为

$$Exposure(G|R)=\sum _{i\in G}\frac{1}{lg(r(i)+1)}$$

其中G是一个群体，R是一个排名，r(i)是一个对象的排名。 他们根据这个定义定义了一个公平指标：人口差异约束或 DDP，定义为

$$DDP(R)=max(G_j,G_k)\frac{exposure(G_j|R)}{|G_j|}-\frac{exposure(G_k|R)}{|G_k|}$$

直观上，这意味着任何群体的暴露程度都不应该与其他群体有很大不同。 值为零意味着完全公平。 不同大小的数据集之间的确切值不具有可比性，因为暴露值随着数据集的增长而缩小。

我们在没有 ENI 属性的情况下计算了学校数据集的曝光值，因为 DDP 不处理非二元公平属性。 由于曝光考虑的是整个排名，因此采用了DCA的对数贴现模式。 得到的奖励点向量为 {'Special-Ed': 14, 'Low-Income': 5, 'ELL': 11}。

在基线视差设置下，DDP值为0.00899。 应用DCA补偿奖励积分后，DDP变为0.00166。 DDP 减少 5 倍与第 VI-A 节中的视差实验一致，证实通过合理大小的奖励点向量可以实现公平性的重要改进。

VI-C5 将 DCA 与其他公平性指标结合使用

我们的 DCA 算法可用于最小化视差以外的公平性指标。 一个限制是最小化度量必须表示为向量的范数，并且它必须提供 -1,1 之间的界限，其中 -1 表示对一组完全不公平，1 表示对另一组完全不公平，0 表示公平。

为了展示 DCA 与其他指标的行为，我们对最流行的公平性指标之一进行了细微的修改：不同影响 (DI)。 DI 对受保护组和未受保护组中的阳性（选定）对象的比例设置了限制。 我们使用[42]中稍微修改过的版本。 具体来说，对于每个公平维度，不同的影响衡量如下：

$$min(\frac{P(O=1|F=0)}{P(O=1|F=1)},\frac{P(O=1|F=1)}{P(O=1|F=0)})$$

其中F=0表示对象不具有受保护（公平）属性（例如，不是低收入），O=1表示对象被选择。 为了使其可供 DCA 使用，我们必须将其缩放到 [-1;1] 范围。 通过此修改，不同的影响可以直接应用于离散情况（包括对数贴现变化），从而产生“特殊教育”奖励向量：14 分，“低收入”：5.5 分，“ELL”：12.5与使用“特殊教育”差异的类似奖励向量相比：14 分，“低收入”：5 分，“ELL”：11.5 分。 我们展示了使用 Disparity 和 DI 与 DCA 的比较图 9。 两个版本的性能相似。 DCA 的不同影响版本需要 164 秒，而使用这些设置的常规 DCA 需要 64 秒。

这种类型的扩展不仅限于统计奇偶性度量：当数据可用时，DCA 还可以与均等赔率度量一起使用，例如误报率。 FPR 定义为被算法误识别为阳性的真实阴性病例的比例。 不同群体之间这一比率的差异是对 COMPAS 算法最初的批评之一。 为了最小化这种差异，我们从每组 FPR 中减去总体 FPR。 这种差异具有 DCA 所需的属性。 将此指标与 DCA 结合使用会产生一种算法，该算法可以找到奖励积分的数量，以最大限度地减少组间 FPR 的差异。 图10(b)显示FPR差异在$k$秒范围内减小。

七结论

我们提出了 DCA，一种使用补偿奖励积分来解决排名过程结果差异的算法。 我们表明，DCA 通过依靠基于采样的方法，成功地减少了各种设置中的差异，同时比最先进的方法在亚线性时间内运行的效率显着提高。 这使得 DCA 成为迭代过程的良好候选者，该迭代过程允许用户确定最适合其需求的排名函数，同时检查其公平性影响和所需的补偿奖励积分。

我们的方法依赖于补偿性奖励积分的使用，这与之前的工作不同，之前的工作主要集中于直接修改排名函数或使用配额。 补偿性奖励积分的一个显着优点是它们是透明的、可解释的，并且很容易向所有利益相关者解释。