An Empirical Study of Rich Subgroup Fairness for Machine Learning

Introduction

The most common definitions of fairness in machine learning are statistical in nature. They proceed by fixing a small number of “protected subgroups” (such as racial or gender groups), and then ask that some statistic of interest be approximately equalized across groups. Standard choices for these statistics include positive classification rates (Calders and Verwer, 2010), false positive or false negative rates (Hardt et al., 2016; Kleinberg et al., 2017; Chouldechova, 2017) and positive predictive value (Chouldechova, 2017; Kleinberg et al., 2017) — see Berk et al. (2018) for more examples. These definitions are pervasive in large part because they are easy to check, although there are interesting computational challenges in learning subject to these constraints in the worst case — see e.g. Woodworth et al. (2017).

Unfortunately, these statistical definitions are not very meaningful to individuals: because they are constraints only over averages taken over large populations, they promise essentially nothing about how an individual person will be treated. Dwork et al. (2012) enumerate a “catalogue of evils” which show how definitions of this sort can fail to provide meaningful guarantees. Kearns et al. (2018) identify a particularly troubling failure of standard statistical definitions of fairness, which can arise naturally without malicious intent, called “fairness gerrymandering”. They illustrate the idea with the following toy example shown in Figure 1, described as follows.

Suppose individuals each have two sensitive attributes: race (say blue and green) and gender (say male and female). Suppose that these two attributes are distributed independently and uniformly at random, and are uncorrelated with a binary label that is also distributed uniformly at random. If we view gender and race as defining classes of people that we wish to protect, we could take a standard statistical fairness definition from the literature — say the equal odds condition of Hardt et al. (2016), which asks to equalize false positive rates across protected groups, and instantiate it with the four protected groups: “Men”, “Women”, “blue people”, and “green people”. The following classifier satisfies this condition, although only by “cheating” and packing its unfairness into structured subgroups of the protected populations: it labels a person as positive only if they are a blue man or a green woman. This equalizes false positive rates across the four specified groups, but of course not over the finer-grained subgroups defined by the intersections of the two protected attributes.

Kearns et al. (2018) also proposed an approach to the problem of fairness gerrymandering: rather than asking for statistical definitions of fairness that hold over a small number of coarsely defined groups, ask for them to hold over a combinatorially or infinitely large collection of subgroups defined by a set of functions $\mathcal{G}$ of the protected attributes (Hébert-Johnson et al. (2018) independently made a similar proposal). For example, we could ask to equalize false positive rates across every subgroup that can be defined as the intersection or conjunction of $d$ protected attributes, for which there are $2^{d}$ such groups. Kearns et al. (2018) showed that as long as the class of functions defining these subgroups has bounded VC dimension, the statistical learning problem of finding the best (distribution over) classifiers in $\mathcal{H}$ subject to the constraint of equalizing the positive classification rate, the false positive rate, or the false negative rate over every subgroup defined over $\mathcal{G}$ is solvable whenever the dataset size is sufficiently large relative to the VC dimension of $\mathcal{G}$ and $\mathcal{H}$. Taking inspiration from the technique of Agarwal et al. (2018), they were able to show that even with combinatorially many subgroup fairness constraints, the computational problem of learning the optimal fair classifier is once again solvable efficiently whenever the learner has access to a black-box classifier (oracle) which can solve the unconstrained learning problems over $\mathcal{G}$ and $\mathcal{H}$ respectively. Similarly, given access to an oracle for $\mathcal{G}$, they were able to efficiently solve the problem of auditing for rich subgroup fairness: finding the $g\in\mathcal{G}$ that corresponds to the subgroup for whom the statistical fairness constraint was most violated.

While the work of Kearns et al. (2018) is satisfying from a theocratical point of view, it leaves open a number of pressing empirical questions. For example, their theory is built for an idealized setting with perfect learning oracles — in practice heuristic oracles may fail. Moreover, perhaps rich subgroup fairness is asking for too much in practice — maybe enforcing combinatorially many constraints leads to an untenable tradeoff with error. Finally, perhaps enforcing combinatorially many constraints is not necessary — perhaps on real data, it is enough to call upon the algorithm of Agarwal et al. (2018) for enforcing statistical fairness constraints on the small number of groups defined by the marginal protected attributes, and rich subgroup fairness will follow incidentally. Put another way: Is the so-called fairness gerrymandering problem only a theoretical curiosity, or does it arise organically when standard classifiers are optimized subject to marginal statistical fairness constraints?

In this paper, we conduct an extensive set of experiments to answer these questions. We study the algorithm from Kearns et al. (2018) — instantiated with fast heuristic learning oracles — when used to train a linear classifier subject to approximately equalizing false positive rates across a rich set of subgroups defined by linear threshold functions. On four real datasets, we characterize:

The basic convergence properties of the algorithm — although this algorithm has provable guarantees when instantiated with learning oracles for $\mathcal{G}$ and $\mathcal{H}$, when these oracles are (necessarily) replaced with heuristics, the guarantees of the algorithm become heuristic as well. We find that the algorithm typically converges (Subsection 3.2), and provides a controllable trade-off between fairness and accuracy despite its heuristic guarantees (Subsection 3.3). We visualize the optimization trajectory of the algorithm (Subsection 3.5), and discrimination heatmaps showing the evolution of the subgroup discrimination of the algorithm over time (Subsection 3.4).

The trade-off between subgroup fairness and accuracy. We find that for each dataset, there are appealing compromises between error and subgroup fairness. Thus achieving rich subgroup fairness may be possible in practice without a severe loss in predictive accuracy (Subsection 3.3).

The subgroup (unfairness) that can result when one applies more standard approaches, that either ignore fairness constraints all together, or equalize false positive rates only across a small number of subgroups defined by individual protected attributes. By auditing the models produced by these standard approaches with the rich subgroup auditor of Kearns et al. (2018), we find that often subgroup fairness constraints are violated, even by algorithms which are explicitly equalizing false positive rates across the groups defined on the marginal protected attributes.

In light of these findings, we submit that rich subgroup fairness constraints are both important, and can be satisfied at reasonable cost: both in terms of computation, and in terms of accuracy. We hope that algorithms like that of Kearns et al. (2018) which can be used to satisfy rich subgroup fairness become part of the standard toolkit for fair machine learning.

While Kearns et al. (2018) propose and study rich sub-group fairness for false positive and negative constraints, Hébert-Johnson et al. (2018) study the analogous notion for calibration constraints, which they call multi-calibration. Kim et al. (2018a) extend this style of analysis to accuracy constraints (asking that a classifier be equally accurate on a combinatorially large collection of subgroups). Kim et al. (2018b) also extend it to metric fairness constraints, converting the individual metric fairness constraint of Dwork et al. (2012) into a statistical constraint that asks that on average, individuals in (combinatorially many) subgroups should be treated differently only in proportion to the average difference between individuals in the subgroups, as measured with respect to some similarity metric.

Definitions

We begin with some definitions, following the notation in Kearns et al. (2018). We study the classification of individuals defined by a tuple $((x,x^{\prime}),y)$, where $x\in\mathcal{X}$ denotes a vector of protected attributes, $x^{\prime}\in\mathcal{X}^{\prime}$ denotes a vector of unprotected attributes, and $y\in\{0,1\}$ denotes a label. We will write $X=(x,x^{\prime})$ to denote the joint feature vector. We assume that points $(X,y)$ are drawn i.i.d. from an unknown distribution $\mathcal{P}$. Let $D$ be a binary classifier, and let $D(X)\in\{0,1\}$ denote the (possibly randomized) classification induced by $D$ on individual $(X,y)$.

Each fairness constraint is defined with respect to a set of protected groups. We define sets of protected groups via a family of indicator functions $\mathcal{G}$ for those groups, defined over protected attributes. Each $g:\mathcal{X}\to\{0,1\}\in\mathcal{G}$ has the semantics that $g(x)=1$ indicates that an individual with protected features $x$ is in group $g$. We now formally define false positive subgroup fairness.

Fix any classifier $D$, distribution $\mathcal{P}$, collection of group indicators $\mathcal{G}$, and parameter $\gamma\in$. For each $g\in\mathcal{G}$, define

We say $D$ satisfies $\gamma$-False Positive (FP) Fairness with respect to $\mathcal{P}$ and $\mathcal{G}$ if for every $g\in\mathcal{G}$

Since we do not consider other measures in this paper, we refer to this notion as simply “subgroup fairness.” Given a fixed subgroup $g\in\mathcal{G}$ we will refer to the quantity $\alpha_{FP}(g,\mathcal{P})\cdot\beta_{FP}(g,D,\mathcal{P})$ as the subgroup fairness wrt $g$, or alternately the $\gamma$-unfairness of $g$. The notion of subgroup fairness imposes a statistical constraint on combinatorially many groups definable by the protected attributes. This is in contrast to more common statistical fairness definitions, defined on coarse groups definable by a single protected attribute. Given a protected attribute $x_{i}$ and a value for that attribute $a$, define the function $g_{i,a}(x)=\textbf{1}\{x_{i}=a\}$ denoting the set of individuals who have that particular value of their protected attribute. In contrast to subgroup fairness, we refer to a classifier $D$ as marginally fair if it satisfies false positive subgroup fairness with respect to the functions $\{g_{i,a}\}$ for each protected attribute $x_{i}$ and realization $a$.

If the algorithm $D$ fails to satisfy the $\gamma$-subgroup fairness condition, then we say that $D$ is $\gamma$-unfair with respect to $\mathcal{P}$ and $\mathcal{G}$. We call any subgroup $g$ which witnesses this unfairness a $\gamma$-unfair certificate for $(D,\mathcal{P})$.

An auditing algorithm for a notion of fairness is given sample access to points from the underlying distribution, as well as the classification outcomes provided by $D$. It will either deem $D$ to be fair with respect to $\mathcal{P}$, or else produces a certificate of unfairness.

Following both Agarwal et al. (2018) and Kearns et al. (2018), in all of the experiments in this paper we take the classes $\mathcal{H}$ and $\mathcal{G}$ to be linear threshold functions, and we use a linear regression heuristic for both auditing and learning. The heuristic finds a linear threshold function as follows:

Train two linear regression models $r_{0}$, $r_{1}$ to predict $c_{0}$ and $c_{1}$ respectively.

Given a new point $x$, predict the cost of classifying $x$ as and $1$ using our regression models: these are $r_{0}(x)$ and $r_{1}(x)$ respectively.

Learner plays $h_{t}$ in $\mathcal{H}$ that minimizes objective function balancing error and unfairness on subgroups $g_{1},\ldots,g_{t-1}$ found by Auditor so far;

Auditor finds subgroup $g_{t}$ in $\mathcal{G}$ on which the uniform distribution over $h_{1},\ldots,h_{t}$ violates $\gamma$-fairness the most.

This can be done efficiently assuming access to oracles which solve the cost sensitive classification problem over $\mathcal{G}$ and $\mathcal{H}$ respectively.

Empirical Evaluation

Is the notion of subgroup fairness interesting empirically, in that there are palatable trade-offs between accuracy and subgroup fairness (as opposed to it being too strong a constraint, and thus resulting in a very steep error increase for even weak subgroup fairness)?

We ran experiments on $3$ datasets from the UCI Machine Learning Repository Dheeru and Karra Taniskidou (2017): Communities and Crime (Redmond and Baveja, 2002), Adult, and Student (Cortez and Silva, 2008), and the Law School dataset from the Law School Admission Council’s National Longitudinal Bar Passage Study (Wightman, 1998). These datasets were selected due to their potential fairness concerns, including:

Data points representing individual people (or in the case of Communities and Crimes, small U.S. communities of people);

The presence of features capturing properties often associated with possible discrimination, including race, gender, and age;

Potential sensitivity of the predictions being made, such as violent crime, income, or performance in school.

The properties of these datasets are summarized in Table 1, including the number of instances, the prediction being made, the overall number of features (which varies from 10 to 128), the number of protected features in the subgroup class (which varies from 3 to 18), the nature of the protected features, and the baseline (majority class) error rate.

We note that two of the datasets (Law School and Adult) were initially much larger but were extremely imbalanced with respect to the predicted label, making sensible error comparisons numerically difficult. We thus randomly downsampled these two datasets to obtain approximately balanced prediction problems on each.

All categorical variables have been preprocessed with a one-hot encoding.

But on other datasets the empirical convergence does not match the idealized theory as cleanly, presumably due to the use of imperfect Learner and Auditor heuristics. In panels (c) and (d) of Figure 2 we again plot $\varepsilon_{t}$ and $\gamma_{t}$, but now for the Adult dataset. Even after approximately 180,000 iterations, the algorithm does not appear to have converged, with $\varepsilon_{t}$ still showing long-term oscillatory behavior, $\gamma_{t}$ exhibiting extremely noisy dynamics (especially at smaller input $\gamma$ values), and there being no clear systematic, monotonic relationship between the input $\gamma$ and error acheived. But despite this departure from the theory, it remains the case that varying $\gamma$ still yields a diverse set of $\langle\varepsilon_{t},\gamma_{t}\rangle$ pairs, as we will see in the next section. In this sense, even in the absence of convergence the algorithm can be viewed as a valuable search tool for models trading off accuracy and fairness.

Overall, we found rather similar convergent behavior on the Communities and Crime and Law School datasets, and less convergent behavior on the Adult and Student datasets.

3 Subgroup Pareto Frontiers and Comparison to Marginal Fairness

4 Flattening the Discrimination Surface

We observe first that the unconstrained classifier in $t=1$ (panel (a)) shows a very systematic bias along the lines of our sensitive attributes. In particular groups with whitepct $>0$ and blackpct $<0$, e.g. communities with large numbers of white residents and relatively fewer black residents have a much higher false positive rate for being classified as violent. Conversely, majority black communities are less likely to be incorrectly labeled as violent. The mean $\gamma$-unfairness (base rate - community rate) for whitepct $>0$, blackpct $<0$ communities is $-0.0242$, whereas the mean for whitepct $<0$, blackpct $>0$ groups is $0.0247$. The maximum $\gamma$-unfairness in $t=1$ is $0.028$, and $61.25\%$ of the $400$ subgroups have $\gamma$-unfairness $>0.02$. Recall that this corresponds to e.g. a $20\%$ disparity of the false positive rate from the base rate, for groups as large as 10% of the population. We are thus far from perfect subgroup fairness.

5 Understanding the Dynamics

The plots in Figure 5 correspond to such trajectories for input $\gamma$ values of $0.001,0.005,0.009,$ and $0.022$ (panels (a), (b), (c) and (d) respectively), which are denoted by the dashed lines on the $\gamma_{t}$ axis of each figure. The $0.001$ and $0.005,0.009$ values correspond to small and intermediate $\gamma$ regimes, whereas $0.022$ is close to (but slightly below) the subgroup unfairness of the unconstrained classifier. The trajectories are color coded from colder to warmer colors according to their iteration number to give a sense of speed of convergence.

The first plot in all four trajectories corresponds to the $\langle\varepsilon_{0},\gamma_{0}\rangle$ of the unconstrained classifier. Furthermore, as long as the current $\gamma_{t}$ values remain above the horizontal dashed line representing the input $\gamma$, the trajectories remain identical, as the same subgroups are being presented to the learner in each trajectory. But when $\gamma_{t}$ falls below a given input $\gamma$, that trajectory will follow its own path going forward.

We first observe that the dynamics exhibit a fair amount of complexity and subtlety. They all begin with low error and large unfairness, and quickly follow a brief but large increase in $\varepsilon_{t}$ as fairness starts to be enforced. There are steps in which both $\varepsilon_{t}$ and $\gamma_{t}$ increase, and a large early loop in trajectory space is observed. But the first three trajectories (panels (a), (b) and (c), corresponding to the three smaller values of $\gamma$) quickly settle near the input $\gamma$ line, at which point begins a long, oscillatory “border war” around this line, as the Learner tries to minimize error, but is pushed back below the line by the Auditor anytime $\gamma$-fairness is violated. The idealized theory predicts that each trajectory should end at the input $\gamma$ line (subgroup fairness constraint saturated), and with larger input $\gamma$ (weaker fairness constraint) resulting in lower error. The empirical trajectories indeed conform nicely to the theory, with the final (red) points near the dashed lines, and further left for larger $\gamma$.

Panel (d), corresponding to a much larger input $\gamma$, diverges much earlier from the other three (on its second step), and early on sees unfairness driven far below the specified value. The dynamics then see a slow, gradual decrease of error and increase of unfairness back to the input value, with the trajectory ending up near where it began, but just slightly more fair, as specified by $\gamma$.

Conclusions

In this work we have established the empirical efficacy of the notion of rich subgroup fairness and the algorithm of Kearns et al. (2018) on four fairness-sensitive datasets, and the necessity of explicitly enforcing subgroup (as opposed to only marginal) fairness. There are a number of interesting directions for further experimental work we plan to pursue, including:

Experiments with richer Learner model classes $\mathcal{H}$, while keeping the Auditor subgroup class $\mathcal{G}$ relatively simple and fixed. One conjecture is that by making the hypothesis space richer, more appealing Pareto curves may be achieved. There is also some rationale for keeping $\mathcal{G}$ simple, since we would like to have some intuitive interpretation of what the subgroups represent, while the same constraint may not hold for $\mathcal{H}$.

Implementation and experimentation with the no-regret algorithm of Kearns et al. (2018), which may have superior convergence and other properties due to its stronger theoretical guarantees.

Experiments on the generalization performance of subgroup fairness in the form of test-set Pareto curves. While as mentioned, standard VC theory can be applied to obtain worst-case bounds, one might expect even better empirical generalization.

References

We here recall the main results of Kearns et al. . Let $S$ denote a set of $n$ labeled examples $\{z_{i}=(x_{i},x^{\prime}_{i}),y_{i})\}_{i=1}^{n}$, and let $\mathcal{P}$ denote the empirical distribution over this set of examples. Let $D$ denote a probability distribution over $\mathcal{H}$. Consider the following Fair ERM (Empirical Risk Minimization) problem:

Kearns et al. Kearns et al. prove the existence of an oracle-efficient algorithm for solving the Fair ERM problem:

The algorithm corresponding to Theorem A.1 is randomized, however, and hence less amenable to the sort of empirical investigation that we undertake in this paper. Fortunately, Kearns et al. also give another algorithm, with somewhat weaker guarantees. It has the same guarantees as Theorem , except the convergence guarantees hold only after an exponential, rather than a polynomial number of steps. However, it has the virtue of very simple per-step dynamics, and is the algorithm that we investigate in this paper. Its pseudo-code follows:

To briefly introduce the notations in the description above, we first note that we can rewrite the set of constraints in the Fair ERM problem as follows: for each $g\in\mathcal{G}(S)$,

Here $\mathcal{G}(S)$ and $\mathcal{H}(S)$ denote the set of all labellings on $S$ that are induced by $\mathcal{G}$ and $\mathcal{H}$ respectively, that is

Then, $\lambda$ is a vector with a coordinate $\lambda_{g}^{+}$ and $\lambda_{g}^{-}$ for every subgroup $g\in\mathcal{G}$ such that $\lambda_{g}^{+}$ and $\lambda_{g}^{-}$ are dual variables that corresponds the pair of constraints (4) and (5). The partial Lagrangian of the linear program is the following:

Similarly, the payoff function for the zero-sum game is then defined as: for any pair of actions $(h,\lambda)\in\mathcal{H}\times\Lambda_{\text{pure}}$,

We can find a best response for the Learner by making a call to the cost-sensitive classification oracle. In particular, we assign costs to each example $(X_{i},y_{i})$ as follows:

if $y_{i}=1$, then $c_{i}^{0}=0$ and $c_{i}^{1}=-\frac{1}{n}$;