Arbitrariness and Social Prediction:
The Confounding Role of Variance in Fair Classification

Consider a distribution $q(\cdot)$ from which we can sample examples $({\bm{x}},{\bm{g}},o)$. The ${\bm{x}}\in{\mathbb{X}}\subseteq\mathbb{R}^{m}$ are feature instances and ${\bm{g}}\in{\mathbb{G}}$ is a group of protected attributes that we do not use for learning (e.g., race, gender).¹¹1We examine the common setting in which $|{\bm{g}}|=1$, and abuse notation by treating ${\bm{g}}$ like a scalar with ${\mathbb{G}}=\{0,1\}$. The $o\in{\mathbb{O}}$ are the associated observed labels, and ${\mathbb{O}}\subseteq{\mathbb{Y}}$, where ${\mathbb{Y}}=\{0,1\}$ is the label space. From $q(\cdot)$ we can sample training datasets $\{({\bm{x}},{\bm{g}},o)\}_{i=1}^{n}$, with ${\mathbb{D}}$ representing the set of all $n$-sized datasets. To reason about the possible models of a hypothesis class ${\mathbb{H}}$ that could be learned from the different subsampled datasets ${\bm{D}}_{k}\in{\mathbb{D}}$, we define a learning process:

Reasoning about $\mu$, rather than individual models $h_{{\bm{D}}_{k}}$, enables us to contextualize arbitrariness in the data, which, in turn, is captured by learned models (Section 3).²²2Model multiplicity has similar aims, but ultimately relocates the arbitrariness we describe to model selection (Section 6; Appendix C.3). Each particular model $h_{{\bm{D}}_{k}}\sim\mu$ deterministically produces classifications $\hat{y}=h_{{\bm{D}}_{k}}({\bm{x}})$. The classification rule is $h_{{\bm{D}}_{k}}({\bm{x}})=\bm{1}[r_{{\bm{D}}_{k}}({\bm{x}})\geq\tau]$, for some threshold $\tau$, where regressor $r_{{\bm{D}}_{k}}:{\mathbb{X}}\rightarrow[0,1]$ computes the probability of positive classification. Executing $\mathcal{A}({\bm{D}}_{k})$ produces $h_{{\bm{D}}_{k}}\sim\mu$ by minimizing the loss of predictions $\hat{y}$ with respect to their associated observed labels $o$ in ${\bm{D}}_{k}$. This loss is computed by a chosen loss function $f:{\mathbb{Y}}\times{\mathbb{Y}}\mapsto\mathbb{R}$. We compute predictions for a test set of fresh examples and calculate their loss. The loss is an estimate of the error of $h_{{\bm{D}}_{k}}$, which is dependent on the specific dataset ${\bm{D}}_{k}$ used for training. To generalize to the error of all possible models produced by a specific learning process (Definition 1), we consider the expected error, $\texttt{Err}(\mathcal{A},{\mathbb{D}},({\bm{x}},\;{\bm{g}},\;o))=\mathbb{E}_{{\mathbf{D}}}[f(o,\;\hat{y})|{\mathbf{x}}={\bm{x}}]$.

In fair classification, it is common to use 0-1 loss $\triangleq\bm{1}[\hat{y}\neq o]$ or cost-sensitive loss, which assigns asymmetric costs $C_{\text{01}}$ for false positives FP and $C_{\text{10}}$ for false negatives FN [25]. These costs are related to the classifier threshold $\tau=\frac{C_{\text{01}}}{C_{\text{01}}+C_{\text{10}}}$, with $C_{\text{01}},C_{\text{10}}\in\mathbb{R}^{+}$ (Appendix A.3). Common fairness metrics, such as Equality of Opportunity [34], further analyze error by computing disparities across group-specific error rates $\texttt{FPR}_{{\bm{g}}}{}$ and $\texttt{FNR}_{{\bm{g}}}$. For example, $\texttt{FPR}_{\bm{g}}\triangleq p_{\mu}[r_{{\mathbf{D}}}({\mathbf{x}})\geq\tau|o=0,{\mathbf{g}}={\bm{g}}]=p_{\mu}[\hat{y}=1|o=0,{\mathbf{g}}={\bm{g}}]$. Model-specific $\texttt{FPR}_{\bm{g}}$ and $\texttt{FNR}_{\bm{g}}$ are further-conditioned on the dataset used in training, i.e., ${\mathbf{D}}={\bm{D}}_{k}$.

We typically only have access to one dataset, not the data distribution $q(\cdot)$. In fair binary classification experiments, it is common to estimate expected error by performing cross validation (CV) on this dataset to produce a small handful of models [11, 38, 17, e.g.]. CV can be unreliable when there is high variance; it can produce error estimates that are themselves high variance, and does not reliably estimate expected error with respect to possible models $\mu$ (Section 5). For more details, see Efron and Tibshirani [23, 24] and Wager [57].

To get around these reliability issues, one can bootstrap.³³3We could use MCMC [60], but optimization is the standard tool that allows use of standard models in fairness. Bootstrapping splits the available data into train and test sets, and simulates drawing different training datasets from a distribution by resampling the train set $\hat{{\bm{D}}}$, generating replicates $\hat{{\bm{D}}}_{1},\hat{{\bm{D}}}_{2},\ldots,\hat{{\bm{D}}}_{B}\coloneqq\hat{{\mathbb{D}}}$. We use these replicates $\hat{{\mathbb{D}}}$ to approximate the learning process on ${\mathbb{D}}$ (Def. 1). We treat the resulting $\hat{h}_{\hat{{\bm{D}}}_{1}},\hat{h}_{\hat{{\bm{D}}}_{2}},\ldots,\hat{h}_{\hat{{\bm{D}}}_{B}}$ as our empirical estimate for the distribution $\hat{\mu}$, and evaluate their predictions for the same reserved test set. This enables us to produce comparisons of classifications across test instances like in Fig. 1 (Appendix A.4).

In Section 2, we discussed how common fairness metrics analyze error by computing false positive rate (FPR) and false negative rate (FNR). Another common way to formalize error is as a decomposition of different statistical sources: noise-, bias-, and variance-induced error [2, 32]. To understand our metric for self-consistency (Section 3.2), we first describe how the arbitrariness in Figure 1 (almost, but not quite) resembles variance.

Informally, variance-induced error quantifies fluctuations in individual example predictions for different models $h_{{\bm{D}}_{k}}\sim\mu$. Variance is the error in the learning process that comes from training on different datasets ${\bm{D}}_{k}\in{\mathbb{D}}$. In theory, we measure variance by imagining training all possible $h_{{\bm{D}}_{k}}\sim\mu$, testing them all on the same test instance $({\bm{x}},{\bm{g}})$, and then quantifying how much the resulting classifications for $({\bm{x}},{\bm{g}})$ deviate from each other. More formally,

We can approximate variance directly by using the bootstrap method (Section 2.2, Appendix  B.1). For 0-1 and cost-sensitive loss with costs $C_{\text{01}},C_{\text{10}}\in\mathbb{R}^{+}$ (Section 2.1), we can generate $B$ replicates to train $B$ concrete models that serve as our approximation for the distribution $\hat{\mu}$. For $B=B_{0}+B_{1}>1$, where $B_{0}$ and $B_{1}$ denote the number of $0$- and $1$-class predictions for $({\bm{x}},{\bm{g}})$,

We derive (1) in Appendix  B.2 and show that, for increasingly large $B$, $\hat{\texttt{var}}$ is defined on $[0,\frac{C_{\text{01}}+C_{\text{10}}}{4}+\epsilon]$.

It is clear from above that, in general, variance (1) is unbounded. We can always increase the maximum possible $\hat{\texttt{var}}$ by increasing the magnitudes of our chosen $C_{\text{01}}$ and $C_{\text{10}}$.⁴⁴4Because $\tau=\frac{C_{\text{01}}}{C_{\text{01}}+C_{\text{10}}}$, for a given $\tau$ we can scale costs arbitrarily and have the same decision rule (Section 2.1). Relative, not absolute, costs affect the number of classifications $B_{0}$ and $B_{1}$. However, as we can see from our intuition for arbitrariness in Figure 1, the most important takeaway is the amount of (dis)agreement, reflected in the counts $B_{0}$ and $B_{1}$. Here, there is no notion of the cost of misclassifications. So, variance (1) does not exactly measure what we want to capture. Instead, we want to focus unambiguously on the (dis)agreement part of variance, which we call self-consistency of the learning process:

In words, (2) models the probability that two models produced by the same learning process on different $n$-sized training datasets agree on their predictions for the same test instance.⁵⁵5(2) follows from it being equally likely to draw any two ${\bm{D}}_{i},{\bm{D}}_{j}\in{\mathbb{D}}$ in a learning process (Appendix  B.3). Like variance, we can derive an empirical approximation of SC. Using the bootstrap method with $B=B_{0}+B_{1}>1$,

For increasingly large $B$, $\hat{\texttt{SC}}$ is defined on $[0.5-\epsilon,1]$ (Appendix B.3). Throughout, we use the shorthand self-consistency, but it is important to note that Definition 3 is a property of the distribution over possible models $\mu$ produced by the learning process, not of individual models. We summarize other important takeaways below:

$\hat{\texttt{SC}}$ enables us to evaluate arbitrariness in classification experiments. It is straightforward to compute $\hat{\texttt{SC}}$ (3) with respect to multiple test instances $({\bm{x}},{\bm{g}})$ — for all instances in a test set or for all instances conditioned on membership in ${\bm{g}}$. Therefore, beyond visualizing $\hat{\texttt{SC}}$ for individuals (Figure 1), we can also do so across sets of individuals. We plot the cumulative distribution (CDF) of $\hat{\texttt{SC}}$ for the groups ${\bm{g}}$ in the test set (i.e., the $x$-axis shows the range of $\hat{\texttt{SC}}$ for $B=101$, $[\approx 0.495,1]$). In Figure 2, we provide illustrative examples from two of the most common fair classification benchmarks [26], COMPAS and Old Adult using random forests (RFs). We split the available data into train and test sets, and bootstrap the train set $B=101$ times to train models $\hat{h_{1}},\hat{h_{2}},\ldots,\hat{h_{101}}$ (Section 2.2). We repeat this process on 10 train/test splits, and the resulting confidence intervals (shown in the inset) indicate that our $\hat{\texttt{SC}}$ estimates are stable. We group observations regarding these examples into two categories:

We highlight results for two illustrative examples: Old Adult and HMDA-NY-2017 for ethnicity (Hispanic or Latino (HL), Non-Hispanic or Latino (NHL)). We plot $\hat{\texttt{SC}}$ CDFs and show $\hat{\texttt{FNR}}$ metrics using random forests (RFs). For Old Adult, the expected disparity of the RF baseline is $\Delta\hat{\texttt{FNR}}=6.3\%$. The dashed set of curves plots the underlying $\hat{\texttt{SC}}$ for these RFs (Figure 3). When we apply simple to these RFs, overall $\hat{\texttt{Err}}$ decreases (Appendix  E), shown in part by the decrease in $\hat{\texttt{FNR}}_{\text{F}}$ and $\hat{\texttt{FNR}}_{\text{M}}$. Fairness also improves: $\Delta\hat{\texttt{FNR}}$ decreases to $4.1\%$. However, the corresponding $\hat{\texttt{AR}}$ is quite high, especially for the Male subgroup (${\bm{g}}=\text{M}$, Figure 4(a)).

As expected, super improves overall $\hat{\texttt{SC}}$ through a first pass of variance reduction (Section 4). The $\hat{\texttt{SC}}$ CDF curves are brought down, indicating a lower proportion of the test set exhibits low $\hat{\texttt{SC}}$. Abstention rate $\hat{\texttt{AR}}$ is lower and more equal (Figure 4(a)); however, error, while still lower than the baseline RFs, has gone up for all metrics. There is also a decrease in systematic arbitrariness (Section 3.3): the dark gray area for super ($\hat{\mathcal{W}_{1}}=.014$) is smaller than the light gray area for simple ($\hat{\mathcal{W}_{1}}=.063$) (B.3, E.4).

For HMDA (Figure 3), simple similarly improves $\hat{\texttt{FNR}}$, but has a less beneficial effect on fairness ($\Delta\hat{\texttt{FNR}}$). However, note that since the baseline is the empirical expected error over thousands of RF models, the specific $\Delta\hat{\texttt{FNR}}$ is not necessarily attainable by any individual model. In this respect, simple has the benefit of actually obtaining a specific (ensemble) model that yields this disparity reliably in practice: $\Delta\hat{\texttt{FNR}}=1.1\%$ is the mean over $10$ simple ensembles. Notably, this is extremely low, even without applying traditional fairness techniques. Similar to Old Adult, simple exhibits high $\hat{\texttt{AR}}$, which decreases with super at the cost of higher error. $\hat{\texttt{FNR}}$ still improves for both ${\bm{g}}$ in comparison to the baseline, but the benefits are unequally applied: $\hat{\texttt{FNR}}_{\text{W}}$ has a larger benefit, so $\Delta\hat{\texttt{FNR}}$ increases slightly.

We also highlight results for COMPAS, 1 of the 3 most common fairness datasets [26]. Algorithm 1 is similarly very effective at reducing arbitrariness (Figure 5), and is able to obtain state-of-the-art accuracy [45] with $\Delta\hat{\texttt{FPR}}$ between $1.8-3\%$. Analogous results for German Credit indicate statistical equivalence in fairness metrics (Appendices  E.4.3 and E.4.7).

These low-single-digit disparities do not cohere with much of the literature on fair binary classification, which often reports much larger fairness violations [44, notably]. However, most work on fair classification examines individual models, selected via cross-validation with a handful of random seeds (Section 2). Our results suggest that selecting between a few individual models in fair binary classification experiments is unreliable. When we instead estimate expected error by ensembling, we have difficulty reproducing unfairness in practice. Variance in the underlying models in $\hat{\mu}$ seems to be the culprit. The individual models we train on these tasks exhibit radically different group-specific error rates (Appendix E.4.7). Our strategy of shifting focus to the overall behavior of the distribution $\hat{\mu}$ provides a solution: we not only mitigate arbitrariness, we also improve accuracy and usually average away most underlying, individual-model unfairness (Appendix  E.5).

While the field has put forth numerous theoretical results about (un)fairness regarding single models — impossibility of satisfying multiple metrics [40], post-processing individual models to achieve a particular metric [34] — these results seem to miss the point. By examining individual models, arbitrariness remains latent; when we account for arbitrariness in practice, most measurements of unfairness vanish.

We are not suggesting that there are no reasons to be concerned with the fairness of machine-learning models. We are not challenging the idea that actual, reliable violations of standard fairness metrics should be of concern. Instead, we are suggesting that common formalisms and methods for measuring fairness can lead to false conclusions about the degree to which such violations are happening in practice (Appendix F). Worse, they can conceal a tremendous amount of arbitrariness, which should itself be an important concern when examining the social impact of automated decision-making.

On common research benchmarks, we show that many classification decisions are effectively arbitrary. Intuitively, this is unfair, but is a type of unfairness that largely has gone unnoticed in the algorithmic-fairness community. Such arbitrariness raises serious concerns about the legitimacy of automated decision-making. Fully examining these implications is the subject of current work that our team is completing. Complementing prior work on ML and arbitrariness [18, 15], we are working on a law-review piece that clarifies the due process implications of arbitrariness in ML-decision outcomes. For additional notes on future work in this area, see Appendix F.

Much prior work has emphasized theoretical contributions and problem formulations for how to study fairness in ML. A common pattern is to study unequal model error rates between demographic subgroups in the available data. Typically, experimental validation of these ideas has relied on using just a handful of models. Our work shows that this is not empirically sound: it can lead to drawing unreliable conclusions about the degree of unfairness (defined in terms of error rates). Most observable unfairness seems due to inadequately modeling or measuring the role of variance in learned models on common benchmark tasks.

Other than indicating serious concerns about the rigor of experiments in fairness research, our findings suggest ethical issues about the role of mismeasurement in identifying and allocating resources to specific research problems [37]. A lot of resources and research effort have been allocated to the study of these problem formulations. In turn, they have had profound social influence and impact, both in research and in the real world, with respect to how we reason broadly about fairness in automated decision-making.

In response to the heavy investment in these ideas, many have noted that there are normative and ethical reasons why such formulations are inadequate for the task of aligning with more just or equitable outcomes in practice. Our work shows that normative and ethical considerations extend even further. Even if we take these formulations at face value in theory, they are very difficult to replicate in practice on common fairness benchmarks when we account for variance in predictions across trained models. When we perform due diligence with our experiments, we have trouble validating the hypothesis that popular ML-theoretical formulations of fairness are capturing a meaningful practical phenomenon.

This should be an incredibly alarming finding to anyone in the community that is concerned about the practice, not just the theory, of fairness research. Using bootstrapping, we observe serious problems with respect to the reliability of how fairness and accuracy are measured in work that relies on cross-validation of just a few models. We also find little empirical evidence of a trade-off between fairness and accuracy (another common formulation in the community), which complements prior work that has made similar observations [53].

We emphasize that this was an unintended outcome of our original research objectives. We aimed to study arbitrariness as a latent issue in problem formulations that have to do with fair classification. This included broader methodological aims: studying many sources of non-determinism that could impact arbitrariness in practice (e.g., minibatching, example ordering). Instead, our initial results of close-to-fair expected performance for individual models made us refocus our work on issues of mismeasurement and fairness.

We did not expect to find that dealing with arbitrariness would make almost all unfairness (again, as measured by common definitions) vanish in practice. Regardless of our intention, these results indicate the limits of theory in a domain that, by centering social values like fairness, cannot be separated from practice. We believe that problem formulations are only as good as they are useful. Based on our work, it is unclear how useful our existing formulations are if they do not bear out in experiments.

In the course of this study, we also tried to reproduce the experiments of many well-cited theory-focused works. We almost always could not do so: code was almost always unavailable. We therefore pivoted from making reproducibility an explicit aspect of the present paper, which we will pursue in future work that focuses solely on reproducibility and fairness. Nevertheless, our work raises concerns about the validity of some of this past work. At the very least, past work that makes claims about baseline unfairness in fairness benchmarks (in order to demonstrate that proposed methods improve upon these baselines) should be subject to experimental scrutiny.

Further along these lines, in our opinion, this project should not have been possible or necessary in 2022. We believe that the novel findings we present here should have surfaced long ago, and likely would have surfaced if experimental contributions had been more evenly balanced with theoretical work.

Lastly, it has not escaped our notice that our results signal severe limits to prediction in social settings. It is true that our method performs reasonably well with respect to both fairness and accuracy metrics; however, arbitrariness is such a rampant problem, it is arguably unreasonable to assign these metrics much value in practice.