Equality of Opportunity in Supervised Learning

Moritz Hardt, Eric Price, Nathan Srebro

Intro

目标是为了在supervised learning中，避免在某些特定特征上产生歧视。目前有这么几种解决方案。

lacking，直接忽略某些特征，但是因为存在redundant encoding而不可行。
demographic parity / group fairness / statistical parity: $$p(\hat Y=1 | A=1) = p(\hat Y=1 | A=0)$$.要求是protected attribute $$A$$与decision $$\hat Y$$独立。但有两个问题 1. 不能保证fairness，比如A=0／1的比例特别少。下面给两个例子 1.1. 贷款，男性前70%可以得到贷款，女性前70%可以得到贷款；但由于男性女性数据集的不同，导致男性前70%的具体数值和女性前70%不同。 1.2. 中国的高考。不同省份，前0.0001%可以进清华北大，但是具体分数会差别很大。 1.3. 总结：这就说明了，demographic graphic保证了比例相同，但不保证具体数值。 2. 如果Y与A相关，那么$$\hat Y \ne Y$$，从而会影响预测结果与真实输出不匹配，最终的预测会不准确
individual fairness: 1. demographic parity的问题是会造成整体看上去公平，但是对于个体不公平。 2. 取代group fairness，核心思想就是两个个体如果特征相似，那么其决策的结果应该类似。
equalized odds：$$p(\hat Y=1 | A=1, Y=y) = p(\hat Y=1 | A=0, Y=y)$$. 1. 在给予贷款的人中，对于性别，要满足demographic parity 2. 在不给予贷款的人中，对于性别，也要满足demographic parity 3. 可以理解为比较强的individual fairness？
equal opportunity：如果只考虑advantaged group，$$p(\hat Y=1 | A=1, Y=1) = p(\hat Y=1 | A=0, Y=1)$$. 1. 在给予贷款的人中，对于性别，要满足demographic parity

Achieving equalized odds and equality of opportunity

Definition (Derived predictor). $$\tilde Y$$ is derived from a random variable $$R$$ and the protected attribute $$A$$ if it is a possibly randomized function of the random variables $$(R,A)$$ alone.

Deriving from a binary predictor

令$$\gamma_a(\hat Y) = ( P(\hat Y=1|A=a,Y=0), P(\hat Y=1|A=a,Y=1) )$$

第一部分是在demographic $$A=a$$中的 $$\hat Y$$的FP rate，第二部分是$$\hat Y$$的TP rate。

Lemma. A predictor $$\hat Y$$ satisfies

Equalized odds iff $$\gamma_0(\hat Y) = \gamma_1(\hat Y)$$

Equal opportunity iff $$\gamma_0(\hat Y)_2 = \gamma_1(\hat Y)_2$$

下面考虑一个有四个点包围的凸包convex hull

$$P_a(\hat Y) = convhull { (0,0), \gamma_a(\hat Y), \gamma_a(1-\hat Y), (1,1)}$$

Lemma. A predictor $$\tilde Y$$ is derived iff for all $$a \in A$$, we have $$\gamma_a(\tilde Y) \in P_a(\hat Y)$$

注：这里的$$\tilde Y$$是non-discriminatory，并且是预测值$$\hat Y$$的relaxation。（因为直接预测不能保证fairness）

证明：首先根据定义，$$\tilde Y$$只依赖于$$\hat Y, A$$，因此我们可以知道概率$$Pr(\tilde Y=1 | \hat Y=1 , A=a)$$, 当$$\hat y, a \in {0, 1}$$。（即就四种parameter情况）每一组parameter对应于凸包$$P_a(\hat Y)$$上的一个点，并且可以通过设置参数达到。

图1的描述中，两个加号和两个减号正好是公式4.2的定义。两个区域的覆盖部分都符合equalized odds，所以最优的点即为两条线的交点。而对于equal opportunity，只要两个点（一个在绿色一个在蓝色区域）的y轴一致那么对应的$$\tilde Y$$就符合。

将这两个lemma合并，我们能有以下的优化目标

$$ min_{\tilde Y} \,\,\, \mathbb{E} \ell(\tilde Y, Y)\ s.t. \,\,\, \forall a \in {0,1}:\, \gamma_a(\tilde Y) \in P_a(\hat Y)\ \gamma_0(\tilde Y) = \gamma_1(\tilde Y)

Deriving from a score function

首先还是用thresholding $$\hat Y = \mathbb{1}(R>t)$$

讨论的核心还是ROC curve，equalized odds要求就是在所有$$a \in A$$当中，FP要和TP相等。也就是对于protected attribute的所有数值，要求conditional behavior of the derived predictor should be exactly the same point （必须得是所有颜色区域的overlap点）。因此我们考虑$$A-$$conditional ROC curve

$$C_a(t) = (P(\hat R>t | A=a, Y=0), (\hat R>t | A=a, Y=1))$$

$$D_a = convhull { C_a(t): t\in [0, 1]}$$

在图2中，equal odds还是一样，必须是同一个点，找交点即可。而equal opportunity则转换了一下，找的是对于任意一条与x轴平行的线，找一个点使得对应的average/sum最小。

Deriving an optimal odds threshold predictor:

给定$$A=a$$， predictor $$\tilde Y$$表现的像 $$\tilde Y = \mathbb{1}(R>T_a)$$。换句话说，要这么构造一个equalized odds predictor

首先在所有convex hull中间选择一个交点 $$\gamma = (\gamma_0, \gamma_1) \in \bigcap_a D_a$$
对于每一个protected group 求一个predictor。 $$\tilde Y | (A=a) = \mathbb{1}(R > T_a)$$ 对应的predictor是 $$\tilde Y = P \mathbb{1}(R > T_A)$$
对于每一个group $$a$$，我们选择要么是用一个固定的threshold $$T_a=t_a$$，或者选择两个thresholds的混合 $$t'_a < \bar t_a$$
1. If $$R < t'_a$$, then $$\tilde Y=0$$
2. If $$R > \bar t_a$$, then $$\tilde Y=1$$
3. If $$t'_a < R < \bar t_a$$, we flip a coin and set $$\tilde Y=1$$ with probability $$p'_a$$

根据图2，也就可以说equalized odds predictor是所有group中的predictor表现最差的。但这也可以换句话说，要求构造equalized odds predictor就是要求我们要在所有group上构造最好的predictor。优化的目标函数可以表示为

$$\min_{\forall a: \gamma \in D_a} \gamma_0 \ell(1,0) + (1-\gamma_1) \ell(0,1)$$

求解这个就需要ternary search（三元搜索）。

Bayes optimal predictors

Bayes optimal equalized odds predictor可以被当作derived predictor。

Bayes optimal regression。给定随机变量$$X,A$$和目标变量$$Y$$，Bayes optimal regressor是$$R = argmin_{r(x,a)} \mathbb{E} [(Y - r(X,A))^2] = r^*(X,A)$$，其中$$r(x,a) = \mathbb{E}[Y | X=x, A=a]$$。

其实就是我们用MSE求解的最优regressor，condition on $$X=x, A=a$$。

Bayes optimal classifier类似，只是a threshold predictor of $$R$$。

Appendix

对于式子4.3和4.5怎么求解还得再考虑一下。这里更多只是证明了存在性。

Equality of Opportunity in Supervised Learning

Equality of Opportunity in Supervised Learning