如何保证算法公正性？ICML 2018两篇获奖论文解读
机器之心原创
作者：韩心怡、钟瑞麒
近日 International Conference on Machine Learning 2018 宣布了获奖论文。值得注意的是这五篇中（Best paper 和 Runner up），有两篇与算法公正性有关，反映了当今机器学习学者群体对其自身的社会影响的日益关注。两篇论文都用简练优雅的数学模型描述了常见社会现象和价值观，理论与实验兼备，让人佩服。本文对这两篇获奖论文进行了解读。
第一篇缩略版本：公正反而会伤害弱势群体么？有一定情况下是的：对弱势群体降低门槛会致使他们无法完成期预期目标，使他们信用度降低，造成更长久的伤害。我们不仅要考虑算法本身是否符合人对道德的定义，更要考虑算法对社会的实际影响。
第二篇缩略版本：如果两个群体公用一个算法，传统算法只能顾及多数人群体的准确率，导致少数人群体对算法的结果不满意，逐渐退出使用算法；于是多数人群体相对比例增大，算法更加只能顾及多数人群体准确率。长此以往，少数人群体会逐渐被排挤出用户群体。
第一篇：「Delayed Impact of Fair Machine Learning」赢得了 ICML 2018 Best Paper Awards。
标题直译为《公正机器学习的滞后影响》，本推送中简称论文。在机器学习的发展进程中，招聘、借贷、广告推广等领域的机器学习模型常常被指控其结果存在偏见、伤害了弱势群体，因此非常多的学者开始探讨如何让机器学习的算法更加公正对待各个群体。然而这些普遍使用的定义只考虑算法结果是否符合人所理解的「公正」价值观，而并未考虑算法长期带来的实际影响；一言以蔽之，不仅要考虑道德义务，更要考虑结果。本次 ICML 2018 Best Paper Awards 的「Delayed Impact of Fair Machine Learning」（《公正性机器学习的滞后影响》，本推送中简称论文）给这个领域带来了另一种声音：让机器算法去符合人所定义的「公正」的价值观真的可以从结果上保护少数群体么？机器学习模型做出一个决策只需要非常短暂的时间，但是决策结果会日复一日、年复一年影响着人们：借贷政策将重新分配这个国家的财富，招聘宣传政策将掌控这个社会的机遇，学校招生政策将决定这个文明的高度；因此，仅仅考虑机器学习道德性而不考虑其实际后果明显是不足的。
本文以借贷问题作为实际背景进行了详尽的分析。直观来想，一味地追求所谓公正而去降低对弱势群体贷款申请的门槛确实很可能会导致他们最终无法按时还款，从来致使他们的信用值降低，造成更长久的伤害，恶性循环。那么，该论文是如何建立起一个更加严密的模型从而定性定量地分析这个问题的呢？介于可读性的考虑，笔者将加入更加形象具体的例子便于读者的理解。
假设一个社会有 A 和 B 两种人构成，A 种人为大多数，占总人口的
，B 种人为弱势群体，占总人口的
。每个人都有一个在 300 到 800 之间的信用值，A 群体和 B 群体的信用值分别呈
和
分布，现在所有人都想和银行借钱，那么银行该如何根据贷款申请者的信用值决定自己的借贷政策呢？
准备工作
（1）所谓贷款政策，无非便是对于每一个贷款申请者做出「借」和「不借」的决定，因此这其实是一个选择题 (selection policy)。我们可以将申请贷款成功人数占总人口的比例称为贷款申请通过率 (selection rate)
。
（2）我们要了解贷款政策对于银行效益和人们信用值的影响。若贷款者按时还钱，银行获益的同时该贷款者的信用值也会上升，而若贷款者逾期不还，则银行亏损且该贷款者的信用也会下降，因此贷款政策不仅需要对银行自身负责，也需对人民负责。该论文对银行的效益和各群体贷款者信用值平均变化值做出了准确的定义，具体见附录 1。由于鱼和熊掌往往不可兼得，银行效益和贷款者信用值平均变化值往往并非同时达到峰值，因此贷款政策往往要在这二者之间做出取舍和平衡。
（3）我们要掌握借贷政策的通行法则。借贷政策往往是一种门槛政策 (threshold policy)，如果申请者的信用大于一定值 c，银行一定借；如果低于这个值 c，银行一定不借；等于的时候，银行有一定概率借。这种门槛政策既简单省事，还可以被证明是同等贷款申请通过率下所有政策的最优解 (Proposition 5.1 Threshold policies are preferable)。因此银行只需要选择一个门槛值 (threshold) 即可。
（4）最后我们需要建立起借贷政策的评估体系，对什么一个政策的好坏达成共识。在这里，论文引入了一种结果曲线 (outcome curve)，旨在分析贷款申请通过率 (selection rate) 和公民信用变化平均值
之间的关系。
在这里，如果一个政策对公民信用值正影响力小于利益最大化政策，那我们称之造成了相对伤害 (relative harm)，反之，如果正影响力更大，那它则产生了相对提升 (relative improvement)。除此之外，如果一个政策非常尴尬地对公民平均信用造成了负面影响，那我们则称其造成了绝对伤害 (active harm)。与此相关的重要贷款通过申请率即为利益最大化政策下的
，最为人民服务的
，和
造成同样影响的对偶值
，和造成绝对伤害的临界值
。另外需要强调的是，论文在定义了左和右分位函数 (left and right quantile functions) 后在 Proposition 5.3 中证明了结果曲线是一个凹函数 (concave function)。
备选政策
硬性政策：
- 利益最大化政策 maximum utility policy(MaxUtil)：通俗来说就是银行怎么挣钱怎么来
- 群体平等政策 demographic parity(DemParity)：通俗来说就是 A 群体贷款申请成功率等于 B 群体贷款申请成功率的情况下挣得最多
- 机会同等政策 equal opportunity(EqOpt)：通俗来说就是 A 群体中能还债的人贷款申请成功率等于 B 群体中能还债的人贷款申请成功率的情况下挣得最多
需要指出的是，以上所有硬性政策是基于银行掌握着绝对可靠的信用值的情况。若信用值被低估了，则弱势群体 A 群体的贷款申请通过比例率将会进一步下降 (Proposition 4.1 Underestimation causes underselection)。
重要结论及简略推导思路
（1）群体平等政策:
群体平等政策的目标即为各群体贷款申请成功率相同的情况下追求利益的最大化：
我们可以证明上面这个式子其实是关于$eta$的一个凹函数 (theorem 6.1 (Selection rates for DemParity)。
如此一来，在的情况下，存在一定人口比例构成的范围会使得群体平等政策为弱势群体带来正影响力 (Corollary 3.2 a)
（2）机会同等政策:
机会同等政策的目标即为各群体有偿还能力者贷款申请成功率相同的情况下追求利益的最大化：
然后我们可以证明出有能力偿还者贷款成功比例和贷款成功比例是一个双映射关系 (Lemma 6.1)，从而进一步简化目标方程，这样我们可以证明这个目标方程其实是关于 t 的一个凹函数 (Theorem 6.2 Selection rates for EqOpt)。如此一来，在
的情况下，存在一定人口比例构成的范围使得机会同等政策可为弱势群体带来福祉 (Corollary 3.2 b)。
然而需要警惕的是，机会同等政策操之过急过于激进会带来相对伤害 (Corollary 3.4)。
总之，群体平等政策和机会同等政策没有普适法则，但是我们可以找到机会同等政策总是优于群体平等政策的充分条件 (Corollary 3.5 EqOpt may avoid active harm where DemParity fails 和 Corollary 3.6 DemParity never loans less than MaxUtil, but EqOpt might)。
实例模拟
论文为了验证模型的正确性，使用 2003 年美国 FICO 信用值为数据，模拟出了在贷款者还贷成功给银行带来收益和贷款者还贷给银行带来损失比例为 1/-4 和 1/-10 的情况下对非拉美裔白人和黑人贷款申请者的决策结果。
当银行获利/损失比为 1/-10 时，没有决策会造成绝对伤害 (active harm)。然而，当银行获利/损失比为 1/-4 时，DemParity 非常遗憾地对人民的平均信用造成了负面影响。更进一步的是，该论文分析了决策对于黑人和非拉美裔白人分别造成的影响。
横轴为贷款申请成功率，数轴分别为信用值平均变化量和银行收益情况。
从图的结果来看，我们可以发现三种政策对黑人和非拉美裔白人的影响是不一样的。最令人失望的是，DP 对黑人群体甚至造成了负面伤害。结果上的不一致很大程度上归结于不同种族间信用值改变情况和带来效益的不同。需要指出的是，该模型模拟出来的结果与 FICO TransUnion TransRisk 的历史数据结果基本吻合。
综上所述，该论文带给了机器学习算法公正性 (fairness in Machine Learning) 这个领域非常不一样的声音；它并没有全盘否认政治正确的意义，但敲响了警钟，告示研究者们一味追求表面的公平和正义反而会适得其反，给弱势群体带来更大的伤害。
附录 1:
论文对银行效益的定义（原文公式 1）：
对各群体贷款者信用值平均变化值的定义（原文公式 2）：
第二篇：「Fairness Without Demographics in Repeated Loss Minimization」（本推送中简称论文）赢得了 ICML 2018 Best Paper Runner Up Awards。
论文标题的大概意思是：在不知道用户所属群体、随时间推移用户分布不断变化、算法不断更新的情况下，保证算法长期公正性。这里用户所属群体范围很宽泛，可以包括民族、口音、居住地等。论文研究了以下这样一个有趣但严峻的情景：假如一个算法对 A 用户群体来说很好用，但对 B 用户群体来说很糟糕，那么 B 群体的用户就会因为其糟糕的用户体验逐渐不使用这个算法器。如果算法只是保证总体利益最大化（期望损失最小化, Empirical Risk Minimization），那么它会更加优先保证对 A 群体的效益，因为 A 群体是多数人；结果是，B 群体会更加不想使用这个算法，导致更少的 B 用户；在这样的循环下，B 群体会逐渐被算法所排斥。举个生活化的例子，有一个语音识别系统为农村和城市人口所共用；如果城市人口更多，而该系统只考虑最大化整体的准确率而「精力有限」的话，它会优先考虑城市人口的利益，多「学习」城市口音；结果导致系统无法准确识别乡村口音。农村用户发现这系统不好用。农村用户流失，城市用户会更加成为主体，使得算法更加只考虑城市用户的利益。
论文在 Section 3.1（图一）举出了以下的例子：
以图为例，分类器要为左右两个群体区分红点和黑点。最优的公正的线性分类边界是 x_2 = 0，即正中间的水平线。它最大化了两个群体的最差准确率。然而，如果集中在右边的用户逐渐流失，而算法只考虑最优化整体利益，分类器就会逐渐朝图中 t=500 的直线倾斜，即成为只能为左边用户群体所使用的分类器；结果就是这样的线性分类器对于右边的用户完全失去了作用。
这篇论文对这样的情境作了研究，以下是对每个 section 的简要概括。Section 2 用动态系统对于这样的情境进行了数学建模；主要建模成分包括：（1）在给定时间点的用户群体分布（2）模型随着时间的变化（3）用户数量随着时间和模型表现的变化。值得注意的是，这个模型中算法并不知道用户的所属潜在群体（即为标题中的「Without Demographics」）。
Section 3 指出，在相当多的情况下，即使算法一开始是公平的，因为一些轻微的随机扰动，算法会逐渐朝不公正的方向不可挽回地偏离；换言之，公平的算法在动态系统中是不稳定的不动点。
Section 4 提出了使用 DRO（Distributionally Robust Optimization）来解决该问题：（1）定义了需要最小化的目标函数（2）用 dual 更直观地理解目标函数，即保证有更少的 Loss 比较大的数据点（3）优化该函数的方法（4）该优化方式可以产生在动态系统中稳定的公正的算法。在这个 Section 里各个关于目标函数的定理的上下界都直接或间接与各个用户群体数量有联系；因此，在不知道用户的真实所属群体的情况下（Without Demographics)，这个算法用「保证不会有太大的单个损失较大的数据点」的方式来保证「不会有一个整个用户群体被严重排斥」。
Section 5 通过两个实验来证明 DRO 相对于 ERM 的有效性：第一个实验是对图一描述的情境的模拟；第二个实验是在 Amazon Mechanical Turk 上进行的，任务是让黑人和白人两个拥有不同语言习惯的用户群体使用分别用 ERM 和 DRO 训练出来的自动填充输入法，根据 Section 2 中的动态系统进行模拟，比较在整个时间段内用户的满意程度。
在这里笔者为大家梳理一下论文中的关键定义、定理：
Section 2 公式一给出了了论文想要最小化的目标，即最小化期望损失最大的用户群体；R 为损失函数，k 为用户群体编号，P 是询问的概率分布，Z 是代表询问的随机变量，theta 是模型参数。
Section 2 定义一建模了论文要研究的动态系统，包括（a）在给定时间点的用户群体分布（b）模型随着时间的变化。lambda_k 是第 k 组用户数量的期望值，alpha 是用户比例，v 是一个递减函数，决定了一个用户群体在经历了一定量的损失之后有多少比例的人会继续留在系统内。b 是每次在新的时间点产生的新用户。
Section 3 定义二定义了用户数量随着时间和模型表现的变化；
Section 3 Proposition 1 和 Corollary 1 证明了即使在一些很广泛的情况下，算法在这个动态系统中会逐渐变得不公正。粗略地来讲，H 包含了每对用户群体损失之间互相影响的关系。根据 Corollary1, 只要左手边的矩阵所有特征值中最大的模大于右边，公正的算法在这个动态系统中就是不稳定的。
Section 4.1 公式（4）定义了 DRO 目标函数，Proposition 2 证明了 DRO 目标函数是每个用户群体损失的上限. 其中 r_max 是由最小用户群体的比例决定的。这也是之后用 DRO 目标函数来分析用户比例的核心连接点。
Section 4.2 公式（5）用 dual 说明了 DRO 目标函数一个关键效果是减少损失太高的数据点。我们可以看到，DRO loss 相当于 F（theta, eta）的下届，而小于 eta 的损失的部分都不被考虑。
Section 4.3 讲述了优化这个目标函数的方法。
Section 4.4 证明了用 DRO 训练出来的模型不会导致一个用户群体被逐渐排除在外的情况。只要能满足公式（7）的条件，即只要 DRO 损失不会「太高」，就可以保证在动态系统更新到下一个时间点时，新的每个用户群体人数都不会「太少」。因此，即使随着时间推移也不会出现一组用户被排挤在外的情况。
注：该篇论文对于「公正」的定义是罗尔斯（John Rawls）体系下的，也就是最大化待遇最差的群体（保证体验最差的用户群体不会太差）；与之相对的，传统的最小化期望损失（Empirical Minimization Risk）是边沁式（Jeremy Bentham）的，即最大化总体社会利益。这篇论文对于是否罗尔斯体系是否正确不做讨论。从用词上来说，罗尔斯体系认为正义即公平，所以本推送对「公平」、「公正」不作区分；欢迎指正。