Wasserstein Fair Classification

INTRODUCTION

The increasing use of machine learning in decision-making scenarios that have serious implications for individuals and society, such as health care, criminal risk assessment, social services, hiring, financial lending, and online advertising (De Fauw et al., 2018; Dieterich et al., 2016; Eubanks, 2018; Hoffman et al., 2018; Malekipirbazari and Aksakalli, 2015; Perlich et al., 2014), is raising concern that bias in the data and model inaccuracies can lead to decisions that are “unfair” towards underrepresented or historically discriminated groups.

This concern has motivated researchers to investigate ways of ensuring that sensitive information (e.g. race and gender) does not ‘unfairly’ influence the decisions. In the classification case considered in this paper, the most widely used approach is to enforce statistical independence between class predictions and sensitive attributes, a criterion called demographic parity (Feldman et al., 2015).

In the common scenario in which the model outputs continuous values from which class predictions are obtained through thresholds, this approach would however ensure fairness only with respect to the particular choice of thresholds. Furthermore, as independence constraints on the class predictions are difficult to impose in practice, uncorrelation constraints on the model outputs are often imposed instead.

In this paper, we propose an approach that overcomes these limitations by imposing independence constraints directly on the model outputs. This is achieved through enforcing small Wasserstein distances between the distributions of the model outputs corresponding to groups of individuals with different sensitive attributes. We demonstrate that using Wasserstein-1 distances to the barycenter is optimal, in the sense that it achieves independence with minimal changes to the class predictions that would have been obtained without constraints. We introduce a Wasserstein-1 penalized logistic regression method that learns the optimal transport map in the logistic model parameters, with a variation that has the advantage of being demographically blind at test time. In addition, we provide a simpler and faster post-processing method. We show that the proposed methods outperform previous approaches in the literature on four benchmark fairness datasets.

STRONG DEMOGRAPHIC PARITY

We are interested in ensuring that sensitive information does not influence the decisions. This is often achieved by imposing that the model satisfies a fairness criterion called demographic parity (DP), defined as

DP can equivalently be expressed as requiring statistical independence between $\hat{Y}$ and $\bm{A}$, denoted as \hat{Y}\mathchoice{\mathrel{\hbox to0.0pt{\displaystyle\perp\hss}\mkern 2.0mu{\displaystyle\perp}}}{\mathrel{\hbox to0.0pt{\textstyle\perp\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox to0.0pt{\scriptstyle\perp\hss}\mkern 2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox to0.0pt{\scriptscriptstyle\perp\hss}\mkern 2.0mu{\scriptscriptstyle\perp}}}\bm{A}.

To deal with these limitations, we propose an approach that enforces statistical independence between $S$ and $\bm{A}$, S\mathchoice{\mathrel{\hbox to0.0pt{\displaystyle\perp\hss}\mkern 2.0mu{\displaystyle\perp}}}{\mathrel{\hbox to0.0pt{\textstyle\perp\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox to0.0pt{\scriptstyle\perp\hss}\mkern 2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox to0.0pt{\scriptscriptstyle\perp\hss}\mkern 2.0mu{\scriptscriptstyle\perp}}}\bm{A}. We call this fairness criterion strong demographic parity (SDP), as it ensures that the decision does not depend on the sensitive attribute regardless of the threshold $\tau$ used, since S\mathchoice{\mathrel{\hbox to0.0pt{\displaystyle\perp\hss}\mkern 2.0mu{\displaystyle\perp}}}{\mathrel{\hbox to0.0pt{\textstyle\perp\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox to0.0pt{\scriptstyle\perp\hss}\mkern 2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox to0.0pt{\scriptscriptstyle\perp\hss}\mkern 2.0mu{\scriptscriptstyle\perp}}}\bm{A} implies \hat{Y}\mathchoice{\mathrel{\hbox to0.0pt{\displaystyle\perp\hss}\mkern 2.0mu{\displaystyle\perp}}}{\mathrel{\hbox to0.0pt{\textstyle\perp\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox to0.0pt{\scriptstyle\perp\hss}\mkern 2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox to0.0pt{\scriptscriptstyle\perp\hss}\mkern 2.0mu{\scriptscriptstyle\perp}}}\bm{A} for any value of $\tau$. SDP can be defined as

In Remark 1, we prove that this definition is equivalent toWe omit the brackets from the expectation to simplify the notation.

where $U(\Omega)$ denotes the uniform distribution over $\Omega$. This result leads us to use

as a measure of dependence of $S$ on $\bm{A}$, the we call strong pairwise demographic disparity (SPDD).

WASSERSTEIN FAIR CLASSIFICATION

We suggest to achieve SDP by enforcing the model output pdfs corresponding to groups of individuals with different sensitive attributes, $\{p_{S_{{\bm{a}}}}\}_{{\bm{a}}\in\mathcal{A}}$, to coincide with their Wasserstein-1 barycenter distribution $p_{\bar{S}}$. The use of the Wasserstein distance is motivated because this distance is defined and computable even between distributions with disjoint supports. This is critical because the empirical estimates $\{\hat{p}_{S_{a}}\}$, $\hat{p}_{\bar{S}}$ of $\{p_{S_{a}}\}$ and $p_{\bar{S}}$ used to implement the methods and their supports are typically disjoint.

Given two pdfs $p_{X}$ and $p_{Y}$ on ${\cal X}$ and ${\cal Y}$, a transportation map $T:{\cal X}\rightarrow{\cal Y}$ is defined by $\int_{\mathcal{B}}p_{Y}(y)dy=\int_{T^{-1}(\mathcal{B})}p_{X}(x)dx$ for any measurable subset $\mathcal{B}\subset{\cal Y}$ (indicating that the mass of the set $\mathcal{B}$ with respect to the density $p_{Y}$ equals the mass of the set $T^{-1}(\mathcal{B})$ with respect to the density $p_{X}$). Let $\mathcal{T}$ be the set of transportation maps from ${\cal X}$ to ${\cal Y}$, and $\textrm{c}:{\cal X}\times{\cal Y}\rightarrow[0,\infty]$ be a cost function such that $\textrm{c}(x,T(x))$ indicates the cost of transporting $x$ to $T(x)$. In the original formulation (Monge, 1781), the optimal transport map $T^{*}$ is the one that minimizes the total transportation cost, i.e.

To address limitations of this formulation, Kantorovich (1942) reformulated the optimal transport problem as finding an optimal pdf $p_{X\times Y}$ in the set $\Gamma(p_{X},p_{Y})$ of joint pdfs on ${\cal X}\times{\cal Y}$ with marginals over $Y$ and $X$ given by $p_{X}$ and $p_{Y}$ such that

The $p$-Wasserstein distance is defined as

where ${\cal X}={\cal Y}$, d is a distance on ${\cal X}$, and $p\geq 1$.

Fair Optimal Post-Processing.

Let us first consider the problem of post-processing the beliefs of a model to achieve SDP while making minimal model class prediction changes.

Given two belief variables $S_{1}$ and $S_{2}$ in $\Omega=$ with pdfs $p_{S_{1}}$ and $p_{S_{2}}$, the following three quantities are equal:

$\mathcal{W}_{1}(p_{S_{1}},p_{S_{2}})=\min\limits_{T\in\mathcal{T}}\int_{x\in\Omega}|x-T(x)|p_{S_{1}}(x)dx$.

Expected class prediction changes due to transporting $p_{S_{1}}$ into $p_{S_{2}}$ through the map $T^{*}$

In the one-dimensional case of $p_{S_{1}}$ and $p_{S_{2}}$, the total transportation cost $\mathcal{W}_{1}(p_{S_{1}},p_{S_{2}})$ can be written as

where $P_{S_{1}}$ and $P_{S_{2}}$ are the cumulative distribution functions of $S_{1}$ and $S_{2}$ respectively. This prove that (i) equals (ii).

The expected class prediction changes due to applying the transportation map $T$ is given by

which coincides with the Wasserstein-1 barycenter with normalized subgroup size as weight to every group distribution $p_{S_{{\bm{a}}}}$ (Agueh and Carlier, 2011).

In summary, we have demonstrated that the optimal post-processing procedure that minimizes total expected model prediction changes is to use the Wasserstein-1 optimal transport map $T^{*}$ to transport all group distributions $p_{S_{{\bm{a}}}}$ to their weighted barycenter distribution $p_{\bar{S}}$.

Optimal Trade-Offs.

We have shown that post-processing the beliefs of a model through optimal transportation achieves SDP (and therefore $\textrm{SPDD}=0$) whilst minimizing expected prediction changes. We now examine the case in which, after transportation, SDP is not attained, i.e. SPDD is positive. By triangle inequality

We call this upper bound on SPDD pseudo-SPDD. Pseudo-SPDD is the tightest upper bound to SPDD among all possible target distributions by the definition of the barycenter $p_{\bar{S}}$ and Proposition 1. Indeed

for any distribution $p_{S^{0}}\in\mathcal{P}(\Omega)$. Since SPDD is difficult to derive optimal trade-offs for, we do that with respect to the pseudo-SPDD as the measure of fairness instead.

where $\gamma=\sum_{\bar{\bm{a}}\in\mathcal{A}\setminus{\bm{a}}}\mathcal{W}_{1}(p_{S_{\bar{{\bm{a}}}}^{*}},p_{\bar{S}})$. By triangle inequality, $\mathcal{W}_{1}(p_{S_{{\bm{a}}}},p^{*})\geq|\mathcal{W}_{1}(p_{S_{{\bm{a}}}},p_{\bar{S}})-\mathcal{W}_{1}(p^{*},p_{\bar{S}})|$. The distance $\mathcal{W}_{1}(p_{S_{{\bm{a}}}},p^{*})$ reaches its minimum if and only if $p^{*}$ lies on a shortest path between $p_{S_{{\bm{a}}}}$ and $p_{\bar{S}}$. Thus it is optimal to transport $p_{S_{{\bm{a}}}}$ along any shortest path between itself and $p_{\bar{S}}$ in the Wasserstein-1 metric space. In the approach proposed in the next section, we approximate transporting group distributions along these shortest paths with hyperparameter tuning of a gradient descent method to minimize $\mathcal{W}_{1}(p_{S_{{\bm{a}}}},p_{\bar{S}})$ for every group.

Empirical Computation of the Barycenter.

In practice, as building the barycenter from the population distributions $p_{S_{a}}$ is impossible, we use the empirical distributions $\hat{p}_{S_{a}}$ obtained from $\mathcal{D}_{{\bm{a}}}$. The choice is justified by the following result:

If the samples in $\mathcal{D}$ are i.i.d., as $|\mathcal{D}|\rightarrow\infty$, if $\mathcal{W}_{1}(p_{S},p_{S_{{\bm{a}}}})<\infty$ for all ${\bm{a}}$, the empirical barycenter distribution satisfies $\lim\sum_{{\bm{a}}}\hat{p}_{{\bm{a}}}\mathcal{W}_{1}(\hat{p}_{\bar{S}},\hat{p}_{S_{\bm{a}}})\rightarrow\sum_{{\bm{a}}}p_{{\bm{a}}}\mathcal{W}_{1}(p_{\bar{S}},p_{S_{\bm{a}}})$ almost surelySee Klenke (2013) for a formal definition of almost sure convergence of random variables..

In the next two sections we introduce two different approaches to achieve SDP with Wasserstein-1 distances: A penalization approach to logistic regression and a simpler practical approach consisting in post-processing model beliefs.

2 WASSERSTEIN-1 PENALIZED LOGISTIC REGRESSION

The average logistic regression loss function over $\mathcal{D}=\{{\bm{a}}^{n},{\bm{x}}^{n},y^{n}\}_{n=1}^{N}$ is given by

The gradient of $J_{\mathcal{D}}({\bm{\theta}})$ with respect to ${\bm{\theta}}$ is given by

where the upper script ${\bm{\theta}}$ in $\textrm{C}_{{\bm{a}}}^{\bm{\theta}}$ is maintained to remind the reader that model predictions are a function of the model parameter ${\bm{\theta}}$.

The Wasserstein-1 penalized logistic regression objective is given by

where $\alpha$ and $\beta$ are penalization coefficients.

where $T_{b,c}^{*}=\arg\min_{T_{b,c}\in U(b,c)}\langle T_{b,c},\textrm{C}\rangle$ is the optimal coupling resulting from the optimization objective of Eq. (2).

The result follows immediately from the subgradient rule for a pointwise max function (see Boyd and Vandenberghe (2004)). ∎

The gradient of $J_{\mathcal{W}_{1}}({\bm{\theta}})$ equals:

where $T_{{\bm{a}}}^{*}$ is the optimal coupling between $\hat{p}_{S_{\bm{a}}}$ and $\hat{p}_{\bar{S}}$Recall that $T_{{\bm{a}}}^{*}$ is a function of ${\bm{\theta}}$..

This formula is a consequence of the chain rule and Lemma 1. ∎

We propose to optimize the Wasserstein penalized logistic loss objective (Eq. (3)) via gradient descent. The procedure is detailed in Algorithm 1. We start by describing how to perform Step 2. under the assumption that $\hat{p}_{\bar{S}}$ and $\{\bar{s}^{i}\}_{i=1}^{\bar{N}}$ have been computed. The computation of the optimal coupling family $\{T_{\bm{a}}^{*}\}$ hinges on the following Lemma.

This lemma characterizes the coupling matrix between the empirical distributions of two datasets made of real numbers. When $N_{b}=N_{c}$ and the datasets are $\{b^{i}\}^{N}_{b}$ and $\{c^{i}\}^{N}_{c}$, with $b^{1}<\ldots<b^{N}$, and $a^{1}<\ldots<a^{N}$, then the optimal coupling equals $1/N\times I_{N}$ where $I_{N}$ denotes the $N\times N$ identity matrix. Lemma 4 extends this simple case to the general case of datasets of arbitrary orderings and sizes, see Deshpande et al. (2018) for a proof. It is easy to see that the optimal coupling $T_{b,c}^{*}$ is sparse and has at most ${\cal O}(N_{b}+N_{c})$ nonzero entries (see Cuturi (2013)). As a consequence, the computation of $\nabla_{\bm{\theta}}J_{\mathcal{W}_{1}}({\bm{\theta}})$ can be performed in linear time {\cal O}\big{(}\sum_{{\bm{a}}}(N_{\bm{a}}+\bar{N})\big{)} where $N_{{\bm{a}}}=|\mathcal{D}_{{\bm{a}}}|$. In the computation of $\nabla_{\bm{\theta}}J_{\mathcal{W}_{1}}({\bm{\theta}})$ only the nonzero entries of $T_{b,c}^{*}$ matter.

We compute the empirical barycenter $\hat{p}_{\bar{S}}$ and $\{\bar{s}^{i}\}_{i=1}^{\bar{N}}$, using the POT library by Flamary and Courty (2017). We fix the support of potential barycenters to bins of equal-width spanning the $$ interval, and use the iterative KL-projection method proposed by Benamou et al. (2015). We then generate a number of samples from the normalized probability distribution of the computed barycenter.

Demographically-Blind Wasserstein-1 Penalized Logistic Regression.

In real-world applications, the use of sensitive attributes might be prohibited when deploying a system. We therefore consider the variation where ${\bm{w}}^{n}=({\bm{x}}^{n},1)^{\top}$. This variation still uses the sensitive attributes to calculate the Wasserstein-1 loss but, by not including them into the feature set, does not require knowledge of sensitive information at test time.

3 WASSERSTEIN-1 POST-PROCESSING

In this section, we propose a simple, fast quantile matching method to post-process the beliefs of a classifier trained on $\mathcal{D}$. This method corresponds to an approximate Wasserstein-1 optimal transport map by the formulation of Rachev and Rüschendorf (1998):

The procedure is detailed in Algorithm 2. For each group ${\bm{a}}$, we compute quantiles of $\hat{p}_{S_{{\bm{a}}}}$ and map all group beliefs belonging in each quantile bin to the supremum of those belonging to the corresponding quantile bin of $\hat{p}_{\bar{S}}$.

4 GENERALIZATION

The following lemma addresses generalization of the Wasserstein-1 objective. Assume $\mathcal{W}_{1}(p_{S_{\bm{a}}},p_{\bar{S}})\leq L$ for all ${\bm{a}}\in\mathcal{A}$. Let $P_{S},P_{S_{\bm{a}}}$ and $P_{\bar{S}}$ be the cumulative density functions of $S$, $S_{\bm{a}}$ and $\bar{S}$. Assume these random variables all have domain $\Omega=$ and that all $P\in\{P_{S},P_{\bar{S}}\}\cup\{P_{S_{\bm{a}}}\}_{{\bm{a}}\in\mathcal{A}}$ are continuous, then:

For any $\epsilon,\delta>0$, if \min\big{[}\bar{N},\min_{{\bm{a}}}\big{[}N_{\bm{a}}\big{]}\big{]}\geq\frac{16\log(2|\mathcal{A}|/\delta)|\mathcal{A}|^{2}\max[1,L]^{2}}{\epsilon^{2}}, with probability $1-\delta$:

In other words, provided access to sufficient samples, a low value of $\sum_{{\bm{a}}}\hat{p}_{{\bm{a}}}\mathcal{W}_{1}(\hat{p}_{S_{\bm{a}}},\hat{p}_{\bar{S}})$ implies a low value for $\sum_{{\bm{a}}}p_{{\bm{a}}}\mathcal{W}_{1}(p_{S_{\bm{a}}},p_{\bar{S}})$ with high probability and therefore good performance at test time.

Lemma 5 implies that under appropriate conditions, the value of the population objective of the Wasserstein cost is upper bounded by the empirical Wasserstein cost plus a small constant.

RELATED WORK

Broadly speaking, we can group current literature on fair classification and regression into three main approaches. The first approach consists in pre-processing the data to remove bias, or in extracting representations that do not contain sensitive information during training (Beutel et al., 2017; Calders et al., 2009; Calmon et al., 2017; Edwards and Storkey, 2016; Feldman et al., 2015; Fish et al., 2015; Kamiran and Calders, 2009, 2012; Louizos et al., 2016; Zemel et al., 2013; Žliobaite et al., 2011). This approach includes current methods to fairness using Wasserstein distances consisting in achieving SDP through transportation of features (Del Barrio et al., 2019; Johndrow and Lum, 2019). The second approach consists in performing a post-processing of the model outputs (Chiappa, 2019; Doherty et al., 2012; Feldman, 2015; Hardt et al., 2016; Kusner et al., 2017). The third approach consists in enforcing fairness notions by imposing constraints into the optimization, or by using an adversary. Some methods transform the constrained optimization problem via the method of Lagrange multipliers (Goh et al., 2016; Zafar et al., 2017; Wu et al., 2018; Agarwal et al., 2018; Cotter et al., 2018; Corbett-Davies et al., 2017; Narasimhan, 2018). Other work similar in spirit adds penalties to the objective (Komiyama et al., 2018; Donini et al., 2018). Adversarial methods maximize the system ability to predict $Y$ while minimizing the ability to predict $\bm{A}$ (Zhang et al., 2018).

EXPERIMENTS

In this section, we evaluate the methods introduced in Sections 3.2 and 3.3 on four datasets from the UCI repository (Lichman, 2013). For penalized logistic regression, we refer to the method in which sensitive information is included in the feature set, i.e. ${\bm{w}}^{n}=({\bm{x}}^{n},{\bm{a}}^{n},1)^{\top}$, as Wass-1 Penalty; and to the demographically-blind variant in which sensitive information is not included, i.e. ${\bm{w}}^{n}=({\bm{x}}^{n},1)^{\top}$, as Wass-1 Penalty DB. We refer to the post-processing method as Wass-1 Post-Process. We also include a variant of this method using $\hat{p}_{S}$ instead of the barycenter $\hat{p}_{\bar{S}}$ (Wass-1 Post-Process $\hat{p}_{S}$), which gives a simpler algorithm that only requires computing basic quantile functions. We compare these methods with the following baselines:

Logistic regression with no fairness constraints.

Post-processing of the logistic regression beliefs $s^{n}$ of all individuals in group ${\bm{a}}$ by adding $0.5-\tau_{{\bm{a}}}$, where the threshold $\tau_{{\bm{a}}}$ is found using the method of Hardt et al. (2016). This ensures that DP is satisfied at threshold $\tau=0.5$.

Lagrangian-based method (see e.g. Eban et al. (2017); Goh et al. (2016)) using a linear model as the underlying predictor and equal positive prediction rate between each group $\mathcal{D}_{{\bm{a}}}$ and $\mathcal{D}$ as fairness constraints with threshold $\tau=0$.

The same as the previous method, but with more fairness constraints. Specifically, the fairness constraints are equal positive prediction rates for a set of thresholds from $-2$ to $2$ in increments of $0.2$ on the output of the linear model.

In the approaches Unconstrained, Hardt’s Post-Process, Wass-1 Penalty, and Wass-1 Post-Process, we trained a logistic regression model using Scikit-Learn with default hyper-parameters (Pedregosa and et al., 2011).

For Wass-1 Penalty (Algorithm 1), as initial model parameters ${\bm{\theta}}_{0}$ we used the ones given by the trained logistic regression. We swept over penalization coefficients $\alpha=[0,0.5]$, $\beta=[10^{-2},3\cdot 10^{-2},10^{-1},3\cdot 10^{-1},1,3,10,30,10^{2}]$, gradient step sizes $\eta=[10^{-4},10^{-3},10^{-2},10^{-1}]$, set the maximum number of training steps to $M=80,000$, and computed the barycenter once every $K>M$ steps, effectively only once after the initialization of ${\bm{\theta}}_{0}$. In the computation of the barycenter (using the POT library by Flamary and Courty (2017)), we swept over numbers of bins $B=$, entropy penalty $\delta=[10^{-3},5\cdot 10^{-3},10^{-2}]$, and used number of iterations $M=1,000$. The time complexity of our implementation is $\mathcal{O}(N\log(N))$. Our gradient steps take on average $\sim$0.02 seconds.

For Wass-1 Post-Process (Algorithm 2), we used a number of bins $|{\cal B}|=100$.

For Constrained Optimization, we used the hinge loss as objective and the hinge relaxation for the fairness constraints. We trained by jointly optimizing the model parameters and Lagrange multipliers on the Lagrangian using ADAM with the default step-size of $0.001$ and mini-batch size of $100$, and trained for $50$ steps. We allowed an additive slack of $0.05$ on the constraints, as otherwise we found feasibility issues leading to degenerate classifiers.

2 DATASETS

The UCI Adult Dataset. The Adult dataset contains 14 attributes including age, working class, education level, marital status, occupation, relationship, race, gender, capital gain and loss, working hours, and nationality for 48,842 individuals; 32,561 and 16,281 for the training and test sets respectively. The goal is to predict whether the individual’s annual income is above or below $50,000.

Pre-processing and Sensitive Attributes. We pre-processed the data in the same way as done in Zafar et al. (2017); Goh et al. (2016). The categorical features were encoded into binary features (one for each category), and the continuous features were transformed into binary encodings depending on five quantile values, obtaining a total of $122$ features. As sensitive attributes, we considered race (Black and White) and gender (female and male), obtaining four groups corresponding to black females, white females, black males, and white males.

The UCI German Credit Dataset. This dataset contains 20 attributes for 1,000 individuals applying for loans. Each applicant is classified as a good or bad credit risk, i.e. as likely or not likely to repay the loan. We randomly divided the dataset into training and test sets of sizes 670 and 330 respectively.

Pre-processing and Sensitive Attributes. We did not do any pre-processing. As sensitive attributes, we considered age ($\leq 30$ and $>30$ years old), obtaining two groups.

The UCI Bank Marketing Dataset. This dataset contains 20 attributes for 41,188 individuals. Each individual is classified as subscribed or not to a term deposit. We divided the dataset into train and test sets of sizes 32,950 and 8,238 respectively.

Pre-processing and Sensitive Attributes. We pre-processed the data as for the Adult dataset. We transformed the categorical features into binary ones, and the continuous features into five binary features based on five quantile bins, obtaining a total of 60 features. We also subtracted the mean from cons.price.idx, cons.conf.idx, euribor3m, and nr.employed to make them zero-centered. As sensitive attributes, we considered age, which was discretized based on five quantiles leading to five groups.

The UCI Communities & Crime Dataset. This dataset contains 135 attributes for 1994 communities; 1495 and 499 for the training and test sets respectively. The goal is to predict whether a community has high (above the 70-th percentile) crime rate.

Pre-processing and Sensitive Attributes. We pre-processed the data as in Wu et al. (2018). As sensitive attributes, we considered race (Black, White, Asian and Hispanic), thresholded at the median to form height groups.

3 RESULTS

We compared the different methods using the following metrics:

As above, but averaging over 100 uniformly-spaced thresholds $\tau\in$.

Figure 1 shows overlaying model belief histograms for four demographic groups and their barycenter in the Adult dataset. Wasserstein-1 Penalty effectively matches all group histograms to the barycenter after training for 10,000 steps with $\beta=100$.

The main experiment results are shown in Tables 1 and 2Given the deterministic baseline logistic regression model, all standard deviations are on the order of $10^{-4}$ or below.. Focusing on the three more relevant metrics – namely Err-Exp as the robust error measure, SDD as the conventional fairness comparison metric, and SPDD as the target-neural, preferred fairness metric (according to which we picked the best hyperparameter settings) – we can see that Wass-1 Penalty and Wass-1 Penalty DB have lowest SDD and SPDD (blue) on the German and Crime datasets and on the Adult and Bank datasets respectively. The fairness performance of these two methods are followed closely by the simpler Wass-1 Post-Process methods on all datasets. Hardt’s Post-Process method incurs largest errors (red) on all datasets. After the Unconstrained baseline, Constrained Optimization and Adv. Contr. Opt. give lowest error on the Adult, Bank and Crime datasets, whilst Constrained Optimization and Wass-1 Penalty (DB) give lowest error on the German dataset. Overall the Wasserstein-1 methods gave best fairness performance on all the datasets with similar or lower compromise on accuracy than the baselines.

Since Wass-1 Penalty is trained by gradient descent, early-stopping can be an effective way to control trade-off between accuracy and fairness. Figure 2 shows a typical example of two trade-off curves between SDD/SPDD and Err-Exp. Though not always the case, often as the learning model moves towards the fairness goal of SDP, model accuracy decreases (Err-Exp increases).

CONCLUSIONS

We introduced an approach to ensure that the output of a classification system does not depend on sensitive information using the Wasserstein-1 distance. We demonstrated that using the Wasserstein-1 barycenter enables us to reach independence with minimal modifications of the model decisions. We introduced two methods with different desirable properties, a Wasserstein-1 constrained method that does not necessarily require access to sensitive information at deployment time, and an alternative fast and practical approximation method that requires knowledge of sensitive information at test time. We showed that these methods outperform previous approaches in the literature.

The authors would like to thank Mark Rowland for useful feedback on the manuscript.

References

Appendix A Empirical Estimates

As $|\mathcal{D}|\rightarrow\infty$, if $\mathcal{W}_{1}(p_{S},p_{S_{{\bm{a}}}})<\infty$ for all ${\bm{a}}$, the empirical barycenter satisfies $\lim\sum_{{\bm{a}}}\hat{p}_{{\bm{a}}}\mathcal{W}_{1}(\hat{p}_{\bar{S}},\hat{p}_{S_{\bm{a}}})\rightarrow\sum_{{\bm{a}}}p_{{\bm{a}}}\mathcal{W}_{1}(p_{\bar{S}},p_{S_{\bm{a}}})$ almost surelySee Klenke (2013) for a formal definition of almost sure convergence of random variables..

Since $p_{\bar{S}}$ and $\hat{p}_{\bar{S}}$ are the weighted barycenters of $\{p_{S_{{\bm{a}}}}\}$ and $\{\hat{p}_{S_{{\bm{a}}}}\}$ respectively:

Combining Eqs. (4) and (6), and (5) and (7):

Therefore the following inequality holds almost surely:

Since $\mathcal{W}_{1}(p_{S_{\bm{a}}},\hat{p}_{S_{{\bm{a}}}})\rightarrow 0$ almost surely for all ${\bm{a}}$ (see Weed and Bach (2017)), and $\hat{p}_{{\bm{a}}}\rightarrow p_{{{\bm{a}}}}$ almost surely (by the strong law of large numbers) and $\mathcal{W}_{1}(p_{S},p_{S_{{\bm{a}}}})<\infty$ for all ${\bm{a}}$, the result follows:

Appendix B Generalization

The following lemma addresses generalization of the Wasserstein-1 objective. Assume $\mathcal{W}_{1}(p_{S_{\bm{a}}},p_{\bar{S}})\leq L$ for all ${\bm{a}}\in\mathcal{A}$. Let $P_{S},P_{S_{\bm{a}}}$ and $P_{\bar{S}}$ be the cumulative density functions of $S$, $S_{\bm{a}}$ and $\bar{S}$. Assume these random variables all have domain $\Omega=$ and that all $P\in\{P_{S},P_{\bar{S}}\}\cup\{P_{S_{\bm{a}}}\}_{{\bm{a}}\in\mathcal{A}}$ are continuous, then:

For any $\epsilon,\delta>0$, if \min\big{[}\bar{N},\min_{{\bm{a}}}\big{[}N_{\bm{a}}\big{]}\big{]}\geq\frac{16\log(2|\mathcal{A}|/\delta)|\mathcal{A}|^{2}\max[1,L]^{2}}{\epsilon^{2}}, with probability $1-\delta$:

In other words, provided access to sufficient samples, a low value of $\sum_{{\bm{a}}}\hat{p}_{{\bm{a}}}\mathcal{W}_{1}(\hat{p}_{S_{\bm{a}}},\hat{p}_{\bar{S}})$ implies a low value for $\sum_{{\bm{a}}}p_{{\bm{a}}}\mathcal{W}_{1}(p_{S_{\bm{a}}},p_{\bar{S}})$ with high probability and therefore good performance at test time.

We start with the case when $p_{\bar{S}}=p_{S}$. By the triangle inequality for Wasserstein-1 distances, for all ${\bm{a}}\in\mathcal{A}$:

Let $\hat{P}$ for $P\in\{P_{S},P_{\bar{S}}\}\cup\{P_{S_{\bm{a}}}\}_{{\bm{a}}\in\mathcal{A}}$ denote the empirical CDF of $P$. Since their domain is restricted to $$ and are one dimensional random variables:

For $S_{*}\in\{S,{\bar{S}}\}\cup\{{S_{\bm{a}}}\}_{{\bm{a}}\in\mathcal{A}}$. Since $P\in\{P_{S},P_{\bar{S}}\}\cup\{P_{S_{\bm{a}}}\}_{{\bm{a}}\in\mathcal{A}}$ are all continuous, the Dvorestky-Kiefer-Wolfowitz theorem (see main theorem in Massart (1990) ) and the condition \min\big{[}\bar{N},\min_{{\bm{a}}}\big{[}N_{\bm{a}}\big{]}\big{]}\geq\frac{16\log(2|\mathcal{A}|/\delta)|\mathcal{A}|^{2}\max[1,L]^{2}}{\epsilon^{2}} implies that:

Since all the random variables have domain $$this in turn implies that for all$S_{*}\in\{S,{\bar{S}}\}\cup\{{S_{\bm{a}}}\}_{{\bm{a}}\in\mathcal{A}}$:

And therefore that with probability $\geq 1-\frac{\delta}{2}$ the following inequalities hold simultaneously for all ${\bm{a}}\in\mathcal{A}$:

Summing Eq. (8) over ${\bm{a}}$ and applying the last observation yields

Recall that we assume $\forall{\bm{a}}\in\mathcal{A}$,

By concentration of measure of Bernoulli random variables, with probability $\geq 1-\frac{\delta}{2}$ the following inequality holds simultaneously for all ${\bm{a}}\in\mathcal{A}$:

If $p_{\bar{S}}$ equals the weighted barycenter of the population level distributions $\{p_{S_{a}}\}$, then

Since $\hat{p}_{{\bm{a}}}\mathcal{W}_{1}(p_{S_{{\bm{a}}}},\hat{p}_{\bar{S}})\leq\hat{p}_{{\bm{a}}}\mathcal{W}_{1}(\hat{p}_{S_{\bm{a}}},\hat{p}_{\bar{S}})+\hat{p}_{{\bm{a}}}\mathcal{W}_{1}(\hat{p}_{S_{{\bm{a}}}},p_{S_{a}})$, with probability $1-\delta$:

The first inequality follows from Eq. (11), and the third one by Eq. (10). The result follows.

Appendix C Inverse CDFs

Given two differentiable and invertible cumulative distribution functions $f,g$ over the probability space $\Omega=$, thus $f,g:\rightarrow$, we have

Intuitively, we see that the left and right side of Eq. (12) correspond to two ways of computing the same shaded area in Figure 3. Here is a complete proof.

Invertible CDFs $f,g$ are strictly increasing functions due to being bijective and non-decreasing. Furthermore, we have $f(0)=0,f(1)=1$ by definition of CDFs and $\Omega=$, since $P(X\leq 0)=0,P(X\leq 1)=1$ where $X$ is the corresponding random variable. The same holds for the function $g$. Given an interval $(x_{1},x_{2})\subset$, let $y_{1}=f(x_{1}),y_{2}=f(x_{2})$. Since $f$ is differentiable, we have

The proof of Eq. (13) is the following (see also Laisant (1905)).

Consider the interval $(a_{i},b_{i})$ for some $i>0$, by Eq.13 we have

Notice that if $f>g$ on $[a_{i},b_{i}]$, then $f^{-1}<g^{-1}$ on $[f(a_{i}),f(b_{i})]$. This is due to the following. Given any $y\in[f(a_{i}),f(b_{i})]=[g(a_{i}),g(b_{i})]$, we have $g^{-1}(y)\in[a_{i},b_{i}]$ and $f(g^{-1}(y))>g(g^{-1}(y))=y=f(f^{-1}(y))$. Thus $g^{-1}>f^{-1}$ since $f$ is strictly increasing. The contrary holds by the same reasoning, i.e. if $f<g$ on $[a_{i},b_{i}]$, then $f^{-1}>g^{-1}$ on $[f(a_{i}),f(b_{i})]$. Therefore,

which holds for all intervals $(a_{i},b_{i})$. Summing over $i$ on both sides, we have