摘要

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

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

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

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

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

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）对偶看不懂参考这篇博客。

这里，我们使用结论：