xuxiaomeng
2022/06/09阅读:28主题:重影
Fairness through awareness
摘要
本文研究的是分类中的公平性。
目标:在保证分类器精度的同时防止个体因属于某个群体而受到歧视。
主要贡献:提出了公平分类的框架,主要包括以下两点
-
一种(假设的)特定于任务的指标,用于确定个体之间的相似程度。 -
一种在公平约束下最大化效用的算法,相似的个体被相似的对待。
该框架允许我们将问题描述为一个可以用线性规划求解的优化问题。
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 令
注 2.1 使用
于是,我们提出了一个更好的确定分布之间相似性的方案,叫作
公式中 sup 表示上确界,上确界表示的是一个集合的最小上界。
假设有一个数列
的一个上界。但知道
在该方案中,对于个体
符号定义:前面,我们把映射
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)
如果一个映射
proposition 3.1
设映射
proposition 3.1 说的是,如果
3.1 为什么 Statistical parity 不够用
在某些情况下,Statistical parity 似乎是可取的——特别是,它中和了冗余编码问题。
冗余编码,一种所用符号数比所表示信息所需要的符号数目多的代码。利用了纠错码的编码原理,在加密的文件中加入了大量的冗余信息,从而达到加密的目的。
这一小节,作者举了三个例子,说明 Statistical parity 作为公平的概念是不充分的,在这些例子中,统计上保持了公平,但从个人角度来看,结果明显是不公平的。在描述案例时,用
案例 1 Reduced Utility
假设在
案例 2 self-fulfilling prophecy
使用 Statistical parity 给与了被保护群体更多的关注。但这也导致了一个问题,被保护群体中的不合格者也被给予了更多的关注,这对其他群体中的合格者不公平,且产生了资源的浪费。例如,在招聘中为了保证 Statistical parity,会给与非裔候选人更多的面试机会(即使是完全不符合要求的非裔参选者)。这就对其他裔合格的候选人产生了不公平,且出现了资源的浪费。
案例 3 Subset Targeting
集合
3.2 Earthmover distance: Lipschitz versus statistical parity
我们的方法需要解决一个基本问题:Lipschitz condition 什么时候意味着在
接下来的定义,我们将回答:“在最坏的情况下,公平 LP 的方案可能对
LP 的意思是线性规划(Linear programming)。
定义 3.2 偏差(bias)
最大值在所有
引理 3.1
令
证明:令
实际上,令
Earthmover Distance
定义 3.3 Earthmover Distance
Earthmover Distance 即陆地移动距离,是一种在 D 区域两个概率分布距离的度量。设

引理 3.2
令
定理 3.3
令
证明看不懂就记结论吧,确实太困难了
证明:在对偶线性规划中,我们可以将
线性规划中的对偶(Duality in linear programs)对偶看不懂参考这篇博客。
这里,我们使用结论: