摘要

本文研究的是分类中的公平性。

目标：在保证分类器精度的同时防止个体因属于某个群体而受到歧视。

主要贡献：提出了公平分类的框架，主要包括以下两点

一种（假设的）特定于任务的指标，用于确定个体之间的相似程度。
一种在公平约束下最大化效用的算法，相似的个体被相似的对待。

该框架允许我们将问题描述为一个可以用线性规划求解的优化问题。

Statistical parity： 在尽可能相似地对待相似个体的情况下，满足任何分类的一组个体的人口统计数据与基本人口统计数据相同。

公平与隐私的关系：公平什么时候意味着隐私？在差分隐私背景下开发的工具如何应用于公平？

1 介绍

研究领域：分类公平

研究背景：所有的分类任务都面临着一种挑战：在实现分类效用的同时，防止对受保护人口亚群的歧视。

1.1 框架的关键要素

1.1.1尽可能相似地对待相似的个体

首先，任何两个在特定任务上相似的人都应该被归类为类似的人。

为了实现这种基于个体的公平性，作者假设了一种定义个体之间相似性的距离指标。

Lipschitz condition

假设为两个个体，分类器为，相似性距离指标为。

表示个体之间的相似度，越大表示相似度越低，。

Lipschitz condition 要求对于任意两个个体，若，有。

1.1.2 优化问题公式化

将 Lipschitz condition 应用于优化问题。

这个 Lipschitz 优化问题可以表示为一个线性规划，因此可以有效的求解。

1.1.3 个体公平与群体公平之间的联系

Statistical parity 指的是那些获得正面或负面分类者的人口统计数据与整个人口的人口统计数据具有相同的性质。

Statistical parity 说明了群体公平，而不是个体公平，它使受保护群体和非受保护群体的结果相等。

Lipschitz condition 说明了个体公平。

在第三章中，通过 Earthmover distance 给出了相似性指标的条件，使得个体公平产生群体公平。

更准确地说，论文证明了当且仅当两组之间的 Earthmover distance 距离很小时，Lipschitz 条件意味着两组之间满足 Statistical parity 。

1.1.4 Fair affirmative action

当 Lipschitz 条件不满足特定要求时，论文在尽可能保证个体公平的情况下，提出了强制实现群体公平的一系列技术。这些技术被作者译作 Fair affirmative action。

1.1.5 与隐私的密切关系

我们对公平的定义是差分隐私概念的泛化

在第五章中，作者将个体公平与差分隐私设置进行类比。

以此类比为基础，利用差分隐私技术来开发更有效的公平机制变体。

1.2 讨论：相似性指标

理想情况下：指标如实反映实际情况。

实际情况下：所使用的指标很可能只是社会当前对真相的最佳近似。

研究难点：证明相似性指标在各种环境中的可用性或可访问性。

相似性指标在广告系统、招聘网站、贷款申请中早有使用，作者主张将这些指标公开，以符合公平。

应用：医疗决策系统，帮助医生根据过去研究过的类似患者和其他医生的共识意见为患者提供合适的诊断。

1.3 相关工作

关于公平，有广泛的理论支撑，特别是在社会选择理论，博弈论，经济学和法学等。

其中一个很经典的公平理论是机会均等，关于机会均等，有以下描述。

机会均等是政治哲学和政策分析中一个重要的福利标准。
哲学定义：一个人的成就与他的某些特征无关（如肤色，种族等）。

在过去，计算机领域的公平主要体现在分布式计算上，本论文则将公平应用到机器学习分类中。

2 问题的公式描述

在分类问题中，个体是要分类的对象，用表示个体的集合，来表示结果集（二分类中）。

为了保证公平，我们考虑将个体映射到结果集的随机分类器。

设个体相似性指标为，考虑从个体到结果概率分布的随机映射。

公平规则：分配给相似个体的分布是相似的（分布用符号表示分布间的差异）。

定义 2.1 Lipschitz mapping

对于任意，如果映射满足属性，有

分类器的选择取决于分类精度。于是作者定义了一个损失函数来优化分类器。

问题就转变为：在符合 lipschitz 条件的情况下，以最小化预期损失的方式找到一个从个体到结果分布的映射。

2.1 实现公平

我们的公平定义得到了一个优化问题，在这个优化问题中，我们在实现给定相似性指标的属性的同时，最小化损失函数。

我们用表示由一个相似性指标和一个损失函数组成问题的实例。

用表示优化问题的最小值，映射可写成，其中。

2.1.1 Probability Metrics

用于确定分布之间相似性的一种方法是统计距离。令和表示有限区域上的概率，那么和之间的统计距离（总变差范数）可以表示为：

tv 是 total variation 的缩写，表示总变差。

引理 2.1 令，给定一个实例，我们可以用一个大小为 poly(|V|,|A|) 的线性规划来计算

注 2.1 使用作为分布的距离度量的一个缺点是：我们应该假设距离度量与个体相似指标成正比，对于相似的个体接近于 0，对于非常不相似的个体接近于 1。

于是，我们提出了一个更好的确定分布之间相似性的方案，叫作

公式中 sup 表示上确界，上确界表示的是一个集合的最小上界。

假设有一个数列，因为每一项都小于等于 1 ，那么有，即是数列

的一个上界。但知道并没有什么实际意义，我们需要知道它最终能收敛于哪一个值。对求极限，有，即的上确界是 2。

在该方案中，对于个体和，如果，那么他们是相似的。如果，那么这两个个体非常不同。

符号定义：前面，我们把映射写成，其中。在这种情况下，当是上的分布时，我们用表示上的分布，定义为，其中。

2.1.2 Useful Fact

引理2.2

Fact 2.1 对任意三个分布和任意两个非负数，如果，我们有

后处理：我们定义的公平在后处理中表现良好。具体是，若，满足。对于一个将集合随机映射到集合的函数，有组合是一个映射。

2.2 案例：广告网络

华尔街日报的一篇文章曾详细描述过广告网络[x+1] 跟踪网络如何收集个人的人口统计信息，比如他们的浏览历史、地理位置和购物行为，并利用这些信息将个体分为 66 类中的一类。例如，他们把家庭收入中位数刚刚超过五万美元、年龄在 25 岁至 45 岁之间、有孩子、受过高等教育的人分类为 "White Picket Fences"。根据对个体的分类，公司向不同的群体展示具有特定信用条款的信用卡。

广告网络 [x+1]维持着从个体到类别的映射。我们可以把这些分类看作结果，因为它决定了向用户展示哪些信用卡。为了满足前面提出的公平需求，从个体到类别的映射必须是随机的，并满足条件。这样，相似的个体就能被分到相似的类中。

2.3 与差分隐私的联系

我们提出的个体公平规则可以看作是差分隐私的一种泛化。

考虑一个简单的差分隐私设置，数据库管理员维护一个数据库，表示某个域。数据分析师允许对数据库进行查询，我们用表示数据库的集合，用表示查询的范围。

一个映射满足当且仅当满足属性。令表示和之间的镜像距离，我们定义 。用于把等号前的内容定义为等号后的内容。

分析师从机制中获得的答案的效用损失定义为，即真实答案与给定答案之间的距离。

表示中测得的某些距离。例如，当。

在此设置中，$opt(I) \overset{def}{=} min \mathbb{E}{x \sim V} \mathbb{E}{\alpha \sim \mu_x}L(x,a) $ ，优化问题现在定义了最佳的差分隐私机制。

Lipschitz property 与 statistical parity 之间的关系

这一小节中，作者论证了 Lipschitz property 自然地揭示了人口的某些子群体满足 statistical parity。

定义 3.1 （Statistical parity）

如果一个映射在偏差内满足分布和之间的 Statistical parity ，那么有

proposition 3.1

设映射满足定义 3.1。对于输出域的任意子集，我们有如下两条性质

proposition 3.1 说的是，如果满足 Statistical parity , 中的成员和中的成员有相似的可能性被映射到同一组。此外，根据一个个体的预测结果，并不能由此退出他来自还是。

3.1 为什么 Statistical parity 不够用

在某些情况下，Statistical parity 似乎是可取的——特别是，它中和了冗余编码问题。

冗余编码，一种所用符号数比所表示信息所需要的符号数目多的代码。利用了纠错码的编码原理，在加密的文件中加入了大量的冗余信息，从而达到加密的目的。

这一小节，作者举了三个例子，说明 Statistical parity 作为公平的概念是不充分的，在这些例子中，统计上保持了公平，但从个人角度来看，结果明显是不公平的。在描述案例时，用表示被保护集，表示它的补集。

案例 1 Reduced Utility

假设在大学中，最有才华的学生被引流到科学和工程专业，而才华较低的学生被引流到金融专业。与此相反，在大学中，最有才华的学生被引流到金融专业，而才华较低的学生被引流到科学和工程专业。一个不了解大学并寻求最有才华的人的组织可能会选择金融专业的学生，即使是在保持 statistical parity 的情况下。出现这种情况的原因是，在保证公平时，忽视了中的成员。

案例 2 self-fulfilling prophecy

使用 Statistical parity 给与了被保护群体更多的关注。但这也导致了一个问题，被保护群体中的不合格者也被给予了更多的关注，这对其他群体中的合格者不公平，且产生了资源的浪费。例如，在招聘中为了保证 Statistical parity，会给与非裔候选人更多的面试机会（即使是完全不符合要求的非裔参选者）。这就对其他裔合格的候选人产生了不公平，且出现了资源的浪费。

案例 3 Subset Targeting

集合满足 Statistical parity 并不意味着的子集满足 Statistical parity，这个特点会被恶意应用在很多方面。例如，考虑一个产品的广告，其目标可能是对感兴趣的成员和对不太感兴趣的成员。点击这样的广告可能与的成员资格有很强的相关性（即使广告的曝光率符合统计上的公平性）

3.2 Earthmover distance: Lipschitz versus statistical parity

我们的方法需要解决一个基本问题：Lipschitz condition 什么时候意味着在上的两个分布和之间的 statistical parity？

接下来的定义，我们将回答：“在最坏的情况下，公平 LP 的方案可能对和产生多大的偏见？”。

LP 的意思是线性规划（Linear programming）。

定义 3.2 偏差(bias)

最大值在所有映射中取，，映射到。

引理 3.1

令，为任意分布。那么，在范围内满足分布和上的 statistical parity。

证明：令是任意映射到的映射。我们构造一个映射，它在和之间与有相同的偏差。

实际上，令。设，。我们声称是。我们可以很容易的看出

Earthmover Distance

定义 3.3 Earthmover Distance

Earthmover Distance 即陆地移动距离，是一种在 D 区域两个概率分布距离的度量。设是一个非负的距离函数。两个分布和之间的 - Earthmover Distance 可以表示为，定义为 Earthmover LP 的值：

引理 3.2

令，那么

定理 3.3

令是一种相似性指标，那么。除此之外，如果，对所有的我们有

证明看不懂就记结论吧，确实太困难了

证明：在对偶线性规划中，我们可以将用以下线性规划表示：

线性规划中的对偶（Duality in linear programs）对偶看不懂参考这篇博客。

这里，我们使用结论：

上述线性规划中，等式右侧的式子 (RHS) 的约束由且。

先证明：

因为是一种相似性指标，应用[引理 3.2](####_引理 3.2)。令是[引理 3.2](####_引理 3.2) 中定义的线性规划问题，对所有

，设置，我们可以其推广为具有相同目标值的定义线性规划的可行解。因此，我们有。

再证明，如果，对所有的我们有 ：

考虑去掉的约束，用表示得到的 LP:

看到这里，你可能想当然的认为，但实际上恰好相反。为了说明这一点，考虑的所有解。在不改变目标值的情况下，我们假设。因为我们假设

，这意味着。现在令，这就给出了实现相同目标值的的解决方案。因此，我们有。

另一方面，由强对偶线性规划，我们有：

因为是一个相似度指标，我们可以应用[引理 3.2](####_引理 3.2)得出结论，因此。

注意 3.1

本文还给出了不涉及线性规划对偶的的另一种证明方式。

事实上，可以理解为给定两个分布和之间的最佳耦合（coupling）的代价服从惩罚函数。回忆一下，耦合是上的分布，他们的边界分布是和。耦合的成本是。不难论证这样的耦合给出了的上界。我们选择线性规划证明，因为它产生了对定理紧致边界的额外知识。

引理 3.4

。

因此，所有的映射也是映射。我们可以说，映射是松弛版的映射。

推论 3.5

为了完备性，我们由的定义得到了对偶线性规划：

与[定理3.3](####定理 3.3)相似，我们可以把该问题解释为流问题。变量表示从到的非负流动，是松弛变量。变量不受限制，因为它对应于一个等式约束。第一个约束条件要求在中至少有个流出单位。等式右侧的约束规定，从接收一个单位流的惩罚量是。然而我们不再清楚是否可以消除变量。

4 Fair Affirmative Action

本章讲述如何实施所谓的公平平权行动（Fair Affirmative Action）。一个典型的问题是，如果我们想保证两个组和之间的统计均等，但是组中的成员不太可能是合格的，该怎么办？例如，某银行在黑人和白人群体中进行贷款评估，黑人占总人口的 10%，白人占总人口的 90%。银行评估的结果只有通过和不通过两种，通过的人和不通过的人群在群体内是非常相似的，但通过的群体和不通过群体之间的距离较远。假设总人口中，获得通过的人占比 20%。如果黑人中通过的人数和白人中一致，那么黑人中获得通过的人占比远高于 20%，而白人中获得通过的人数少于 20%，这是因为通过和没有通过的人没有被公平对待，正如第一章所说的，（能力一致的前提下）黑人的资料受到更多的关注。

是否实施统计平价的影响

实施统计平价

设白人群体为，黑人群体为；获得通过的白人群体为，未通过为；获得通过的黑人群体为，未通过为；通过的群体为（包括和。因为实施个体公平，所以中任意的两个个体被视为相似的个体。实施统计平价的一种方式是，对群体和用固定的概率给所有个体通过，从而使所有个体被公平的对待。但是，这种方式严重损害了银行的利益。

不实施统计平价

如果和之间的距离相对较远，那么条件的约束较弱，那么它无法防止一些不公平的做法。如，某些极端情况下，因为中个体较少，直接将中所有个体划到。

4.1 一个可选优化问题

经过上述讨论，我们提出了另一种方法，即坚持统计平价，但是放宽了和之间的条件。如果和之间的距离信息比这两个集合内部的距离度量更低，那么宽松版条件才有意义。

具体包括以下两步：

（a）首先，我们计算一个从中元素到上分布的映射，它将上的均匀分布转换为上的均匀分布，同时最小化总距离。此外，此映射保持了内元素之间的条件。（b）该映射为中的元素提供了以下新的损失函数：对和，我们定义了一个新的损失函数，其中是步骤 a 中计算出来的映射。考虑到上的损失，可以被视为损失函数的重新加权。
最后使用新的损失函数，仅仅在上运行 Fairness LP。

将这两个步骤组合在一起，将产生从到的映射。通常，我们可以将该替代方式的第一步定义为：

其中，代表上的均匀分布，给定最小化公式14 的和限制在上的最小化原始 Fairness LP 的，我们定义映射：

在说明的性质之前，我们先提一些注意事项：

从根本上说，这种新的方法从满足约束的损失最小化转变为最小化要求的损失，满足和上的约束。这给了我们一个具有广泛选择范围的双目标优化问题。
即使在目前的版本中，我们也有一些灵活性。例如，我们可以取消重新加权，禁止供应商（例如银行）对中元素的命运发表任何意见。这在几种情况下都是有意义的。例如，供应商可能由于对S的无知(例如，缺乏市场研究)而请求这样做，或者供应商可能对有歧视。
将另一种方法与公平线性规划的修改进行比较是有指导意义的，在这一项修改中，我们强制执行了统计平价并消除了上的要求。另一种方法更忠实于距离，提供了对引言中讨论的自我实现预测的保护。在该预测中，供应商错误选择的错误子集，同时仍保持统计上的等价性。
解决优惠待遇的一种方法涉及相似性指标的调整，即条件意味着统计平价。这与公平平权行动背后的至少一个理念不谋而合：该指标没有充分放映可能因为资源获取不平等而导致未被开发的潜力。因此，当我们考虑中最强的个体时，平权行动表明，将该个体与中最强壮的个体之一相似更为合适。在这种情况下，自然会调整和中元素之间的距离，而不是每个种群内部的距离。这就产生了一系列优化问题：

找到一个新的相似性指标，该指标在和间具有较小陆地移动距离的条件下接近于。

设是等式 15 的映射，则的下述属性很容易被验证。

命题 4.1 公式 15 中的映射满足

在偏差内满足和之间的统计平价
任意对

证明：第一条属性满足当且仅当

第二项声明对的影响微乎其微，所以令。那么有

我们放弃了和之间的条件，而是依赖于目标函数中的项来阻止将映射到远处的。

结果表明，元素和之间仍保持了均值水平，期望违例由给出。

命题 4.2

假设满足公式 14，得到的映射满足

证明：对所有和我们有

5 Small loss in bounded doubling dimension

一般的线性规划表示，给定一个实例，有可能在多项式时间内找到一个“最优公平”映射。然而，这个结果并没有对由此造成的损失一个具体的数量界限。此外，当实例非常大时，需要提出更加有效的方法来定义映射。

我们现在给出一个公平机制，我们可以证明它在自然环境中所达到的损失界限。此外，该机制比一般线性规划的效率高得多。我们的机制基于指数机制，首先在差分隐私环境中考虑。

我们将在自然的环境中描述该方法，即映射将中的元素映射到本身的分布上。这个方法可以泛化到一个不同的集合上，只要我们在集合上有一个距离函数和一些将嵌入到的距离保护。当被映射到上的分布时，一个最小的自然损失函数由相似度指标给出。在这个设置中，我们将给出一个显示的映射，并表明在度量空间的前提下，映射实现了最小损失。

定义 5.1

给定一个相似度指标，那么指数机制可以用以下方式定义：

引理 5.1

指数机制是。

一般来说，我们不能期望指数机制能实现较小的损失。然而这在有较小的 doubling dimension 的情况下是成立的。需要注意的是，在差分隐私中，数据库的空间不会有较小的 doubling dimension。机器学习应用中出现的许多度量空间都具有有界的 doubling dimension。因此，我们将要证明的定理在许多自然环境中都适用。

定义 5.2

对于所有和每一个的以为圆心，为半径的球，可以表示为。它能被个半径为的球覆盖。一个度量空间的 doubling dimension 是能覆盖度量空间的最小球的数量。

定义 5.3

如果存在一个正整数，使得对所有有，我们称度量空间为分离良好的空间。

定理 5.2

设是有界 doubling dimension 的一个良好度量空间，那么指数机制满足：

证明：假设有 doubling dimension k。文献表明 doubling dimension k 意味着对于所有有

，其中