Auditing Predictive Models for Intersectional Biases

## Abstract

Abstract Predictive models that satisfy group fairness criteria in aggregate for members of a protected class, but do not guarantee subgroup fairness, could produce biased predictions for individuals at the intersection of two or more protected classes. To address this risk, we propose Conditional Bias Scan (CBS), a flexible auditing framework for detecting intersectional biases in classification models. CBS identifies the subgroup for which there is the most significant bias against the protected class, as compared to the equivalent subgroup in the non-protected class, and can incorporate multiple commonly used fairness definitions for both probabilistic and binarized predictions.
We show that this methodology can detect previously unidentified intersectional and contextual biases in the COMPAS pre-trial risk assessment tool and has higher bias detection power compared to similar methods that audit for subgroup fairness.

## 1 Introduction

Predictive models are increasingly used to assist in high-stakes decisions with significant impacts on individuals’ lives and livelihoods. However, recent studies have revealed numerous models whose predictions contain biases, in the form of group fairness violations, against disadvantaged and marginalized groups (Angwin et al., ; Obermeyer et al., ).
When auditing a predictive model for bias, typical group fairness definitions (Mitchell et al., ) rely on univariate measurements of the difference between the distributions of predictions or outcomes for individuals in a “protected class”, typically defined by a sensitive attribute such as race or gender, as compared to those in the non-protected class. Since these approaches only detect biases for a predetermined subpopulation at an aggregate level, e.g., a bias against Black individuals, they may fail to detect biases that adversely affect a subset of individuals in a protected class, e.g., Black females. While it is possible to define a specific multidimensional subgroup and then audit a classifier for biases impacting that subgroup, this approach does not scale to the combinatorial number of subgroups. Therefore, group fairness measurements cannot reliably detect if there are *any* subgroups within a given population that are adversely impacted by predictive biases, and as a result, intersectional biases in model predictions often go unaddressed.

In this paper, we present a novel methodology for bias detection called Conditional Bias Scan (CBS). Given
a classifier’s probabilistic *predictions* or binarized *recommendations* based on those predictions, CBS discovers systematic biases impacting any *subgroups* of a predefined subpopulation of interest (the *protected class*).
More precisely, CBS aims to discover subgroups of the protected class for whom the classifier’s predictions or recommendations systematically deviate from the corresponding subgroup of individuals who are not a part of the protected class. Subgroups are defined by a non-empty subset of attribute values for each observed attribute, excluding the *sensitive attribute* which determines whether or not individuals belong to the protected class. The detected subgroups can represent both *intersectional* biases, defined by membership in two or more protected classes, as well as *contextual* biases that may only be present for certain decision situations (Runyan, ).

The contributions of our research include:

- [noitemsep,topsep=0pt,parsep=0pt,partopsep=0pt,leftmargin=5mm]
- •
The first methodological framework that can reliably detect intersectional and contextual biases and flexibly accommodates multiple common group-fairness definitions.
- •
A novel and computationally efficient pattern detection algorithm to audit classifiers for fairness violations in the exponentially many subgroups of a prespecified protected class.
- •
An interpretable tool for detecting fairness violations that demonstrates significantly improved bias detection accuracy, as compared to other tools used to audit classifiers for subgroup fairness.
- •
A robust simulation study and real-world case study that compare results across various group-fairness metrics, demonstrating substantial differences between separation and sufficiency metrics.

## 2 Related Work

The original Bias Scan proposed by Zhang and Neill Zhang and Neill () uses a multidimensional subset scan to search exponentially many subgroups of data, identifying the subgroup with the most significantly miscalibrated probabilistic predictions as compared to the observed outcomes. Bias Scan lacks the functionality of traditional group fairness techniques to define a protected class and to determine whether those individuals are impacted by biased predictions, and is thus limited to asking, “Which subgroup has the most miscalibrated predictions?" In contrast, given a protected class $A$, CBS can reliably identify biases impacting $A$ or any subgroup of $A$.
CBS searches for subgroups within the protected class with the most significant deviation in their predictions and observed outcomes as compared to the predictions and observed outcomes for the corresponding subgroup of the non-protected class (for example, a racial bias against Black females as compared to non-Black females). Since Bias Scan solely focuses on the deviation between the predictions and observed outcomes within a subgroup, it would not be able to detect such a bias unless the subgroup was also biased as compared to the population as a whole. Furthermore, CBS generalizes to both separation-based and sufficiency-based group fairness metrics, and to both probabilistic and binarized predictions. To enable these new functionalities, CBS deviates from Bias Scan’s methodology in substantial ways including new preprocessing techniques, new and altered hypotheses, and resulting score functions.

GerryFair and Multiaccuracy Boost (Kearns et al., ; Kim et al., ) are two methods that use an auditor to iteratively detect subgroups while training or correcting a classifier to guarantee subgroup fairness. GerryFair’s auditor relies on linear regressions trained to predict differences between the predictions and the observed global error rate of a dataset. Multiaccuracy Boost iteratively forms subgroups by evaluating rows with predictions above and below a threshold to determine which predictions to adjust. CBS’s methodology for forming subgroups is more complex because it does not assume a linear relationship between covariates and the difference between the predictions and baseline error rate. Unlike CBS, these methods provide limited fairness definitions to use for auditing, and do not return interpretable subgroups that are defined by discrete attribute values of the covariates, but rather identify all rows that have a fairness violation on a given iteration. Since both methods incorporate the predictions in forming subgroups and enable auditing, they are directly comparable to CBS. In Section [4](#S4), we show that CBS has substantially higher bias detection accuracy than GerryFair and Multiaccuracy Boost.

## 3 Methods

CBS begins by defining the dataset $D=(A,X,Y,P,P_{bin})=\{(A_{i},X_{i},Y_{i},P_{i},P_{i,bin})\}_{i=1}^{n}$, for $n$ individuals indexed as $i=1..n$. $A_{i}$ is a binary variable representing whether individual $i$ belongs to the protected class. $X_{i}=(X_{i}^{1}\ldots X_{i}^{m})$ are other covariates for individual $i$. We assume that all covariates are discrete-valued; continuous covariates can be discretized as a preprocessing step. The protected class attribute $A$ and the sensitive attribute of the data from which $A$ was derived are not included in $X$. $Y_{i}$ is individual $i$’s observed binary outcome, $P_{i}\in[0,1]$ is the classifier’s probabilistic prediction of individual $i$’s outcome, and $P_{i,bin}\in\{0,1\}$ is the binary recommendation corresponding to $P_{i}$.
Given these data, CBS searches for subgroups of the protected class, defined by a non-empty subset of values for each covariate $X^{1}\ldots X^{m}$, for whom some *group fairness definition* (contained in Table [1](#S3.T1)) is violated. Each fairness definition can be viewed as a conditional independence relationship between an individual’s membership in the protected class $A_{i}$ and their value of an *event variable* $I_{i}$, conditioned on their covariates $X_{i}$ and their value of a *conditional variable* $C_{i}$. We define the null hypothesis, $H_{0}$, that $I\perp A\>|\>(C,X)$, and use CBS to search for subgroups with statistically significant violations of this conditional independence relationship, correctly adjusting for multiple hypothesis testing, allowing us to reject $H_{0}$ for the alternative hypothesis $H_{1}$ that $I\not\perp A\>|\>(C,X)$ .

The CBS framework has four sequential steps. (1) Given a fairness definition, CBS chooses $I\in\{Y,P,P_{bin}\}$ and $C\in\{Y,P,P_{bin}\}$. In Section [3.1](#S3.SS1), we describe how
different group fairness criteria in the literature map to particular choices of event variable $I$ and conditional variable $C$. (2) Next, we estimate the expected value of $I_{i}$ for each individual in the protected class under the null hypothesis $H_{0}$ that $I$ and $A$ are conditionally independent. We denote these expectations as $\hat{I}_{i}$. Our procedure to estimate $\hat{I}$, which builds on the econometric literature for estimation of heterogeneous treatment effects, is described in Section [3.2](#S3.SS2). (3) Then we use a novel multidimensional subset scan algorithm to search for subgroups $S$ where for $i\in S$, $I_{i}$ deviates systematically from its expectation $\hat{I}_{i}$ in the direction of interest. This scan step to *detect $S^{*}$* is described in detail in Section [3.3](#S3.SS3). (4) The final step to *evaluate statistical significance* of the detected subgroup $S^{\ast}$ (Section [3.3](#S3.SS3)) involves using permutation testing, described in Appendix [A.3](#A1.SS3), to adjust for multiple hypothesis testing and determine if $S^{*}$’s deviation between protected class and non-protected class is statistically significant.

### 3.1 Define ( I , C ) 𝐼 𝐶 (I,C) ( italic_I , italic_C ) : Overview of Scan Types

Many of the group fairness criteria proposed in the fairness literature fall into two categories of statistical fairness called sufficiency and separation. An intuitive way to distinguish between these concepts is that *sufficiency* is focused on equivalency in the rate of an outcome (for comparable individuals with the same prediction or recommendation) regardless of protected class membership ($Y\perp A\>|\>P,X$), whereas *separation* is focused on equivalency of the expected prediction or recommendation (for comparable individuals with the same outcome) regardless of protected class membership ($P\perp A\>|\>Y,X$). In our CBS framework, the choice between separation and sufficiency determines whether outcome $Y$ is the event variable of interest $I$ or the conditional variable $C$, where bias exists if $\mathbb{E}[I\>|\>C,X,A=1]\neq\mathbb{E}[I\>|\>C,X,A=0]$. The combination of fairness metric (sufficiency or separation) and prediction type (continuous prediction or binary recommendation) produces four general classes of fairness scans: separation for predictions ($I=P$, $C=Y$), separation for recommendations ($I=P_{bin}$, $C=Y$), sufficiency for predictions ($I=Y$, $C=P$), and sufficiency for recommendations ($I=Y$, $C=P_{bin}$).

**Table 1: Table of all scan types for CBS for different group fairness definitions. The notation $\bot$ refers to conditional independence from membership in the protected class ($A$). For example, for the False Discovery Rate scan, $\mbox{Pr}(Y=0\>|\>P_{bin}=1,X)\bot A$ is shorthand for $\mbox{Pr}(Y=0\>|\>P_{bin}=1,X,A=1)=\mbox{Pr}(Y=0\>|\>P_{bin}=1,X,A=0)$.**
|  | Predictions ($P\in[0,1]$) | Recommendations ($P_{bin}\in\{0,1\}$) |  |  |  |
| --- | --- | --- | --- | --- | --- |
|  |  | $P_{bin}=1$ | $P_{bin}=0$ | $P_{bin}$ |  |
|  | $Y=1$ | $\mathbb{E}[P\>|\>Y=1,X]\bot A$ | $\mbox{Pr}(P_{bin}=1\>|\>Y=1,X)\bot A$ | $\mbox{Pr}(P_{bin}=0\>|\>Y=1,X)\bot A$ |  |
|  |  | *Balance for Positive Class* | *True Positive Rate* | *False Negative Rate* |  |
|  | $Y=0$ | $\mathbb{E}[P\>|\>Y=0,X]\bot A$ | $\mbox{Pr}(P_{bin}=1\>|\>Y=0,X)\bot A$ | $\mbox{Pr}(P_{bin}=0\>|\>Y=0,X)\bot A$ |  |
|  |  | *Balance for Negative Class* | *False Positive Rate* | *True Negative Rate* |  |
| Separation | $Y$ | $\mathbb{E}[P\>|\>Y,X]\bot A$ | $\mbox{Pr}(P_{bin}=1\>|\>Y,X)\bot A$ | $\mbox{Pr}(P_{bin}=0\>|\>Y,X)\bot A$ |  |
|  | $Y=1$ | $\mbox{Pr}(Y=1\>|\>P,X)\bot A$ | $\mbox{Pr}(Y=1\>|\>P_{bin}=1,X)\bot A$ | $\mbox{Pr}(Y=1\>|\>P_{bin}=0,X)\bot A$ | $\mbox{Pr}(Y=1\>|\>P_{bin},X)\bot A$ |
|  |  |  | *Positive Predictive Value* | *False Omission Rate* |  |
|  | $Y=0$ | $\mbox{Pr}(Y=0\>|\>P,X)\bot A$ | $\mbox{Pr}(Y=0\>|\>P_{bin}=1,X)\bot A$ | $\mbox{Pr}(Y=0\>|\>P_{bin}=0,X)\bot A$ | $\mbox{Pr}(Y=0\>|\>P_{bin},X)\bot A$ |
| Sufficiency |  |  | *False Discovery Rate* | *Negative Predictive Value* |  |

Depending on the particular bias of interest, we can also perform “value-conditional” scans by restricting the value of the conditional variable. For example, we scan for subgroups with increased false positive rate (FPR) by restricting the data to individuals with $Y=0$ and performing a separation scan for recommendations. All of the scan options for CBS are displayed in Table [1](#S3.T1). As we discuss below, each scan displayed in Table [1](#S3.T1) can be used to detect bias in either direction, e.g., searching for subgroups with either increased or decreased FPR.

### 3.2 Generate Expectations I ^ ^ 𝐼 \hat{I} over^ start_ARG italic_I end_ARG of the Event Variable

Once we have defined the event variable $I$ and conditional variable $C$, we wish to detect fairness violations by assessing whether there exist subgroups of the protected class where
$\mathbb{E}[I\>|\>C,X,A=1]$ differs systematically from $\mathbb{E}[I\>|\>C,X,A=0]$. For each individual $i$ in the protected class, $I_{i}\>|\>C_{i},X_{i},A_{i}=1$ is observed but $I_{i}\>|\>C_{i},X_{i},A_{i}=0$ is unobserved. Thus we must calculate an estimate $\hat{I}_{i}=\mathbb{E}_{H_{0}}[I_{i}\>|\>C_{i},X_{i},A_{i}=1]$, under the null hypothesis, $H_{0}$: $(I\perp A\>|\>C,X$), and compare $\hat{I}_{i}$ to the observed $I_{i}$. To calculate $\hat{I}$ we use the following method from the econometric literature on heterogeneous treatment effects, which controls for non-random selection into the protected class $A$ based on observed covariates $X$: (1) Learn a probabilistic model for estimating $\mbox{Pr}(A=1\>|\>X)$, and use it to produce propensity scores, $p_{j}^{A}$, for each individual $j$ in the non-protected class; (2) For each individual $j$ in the non-protected class, use the observed $\mathbb{E}[I_{j}\>|\>C_{j},X_{j},A_{j}=0]$ weighted by the odds of the propensity score for individual $j$, $\frac{p_{j}^{A}}{1-p_{j}^{A}}$, to learn a probabilistic model for $\mathbb{E}_{H_{0}}[I\>|\>C,X,A=1]$; (3) For each individual $i$ in the protected class, use the model of $\mathbb{E}_{H_{0}}[I\>|\>C,X,A=1]$ to calculate $\hat{I}_{i}=\mathbb{E}_{H_{0}}[I_{i}=1\>|\>C_{i},X_{i},A_{i}=1]$. For a more detailed description of this method, modifications for value-conditional scans, and a discussion of its limitations, please reference Appendix [A.1](#A1.SS1).

### 3.3 Detect the Most Significant Subgroup S * superscript 𝑆 S^{*} italic_S start_POSTSUPERSCRIPT * end_POSTSUPERSCRIPT and Evaluate its Statistical Significance

**Table 2: Null and alternative hypotheses, $H_{0}$ and $H_{1}(S)$, and corresponding log-likelihood ratio score functions, $F(S)$, used to measure a subgroup’s degree of anomalousness (comparing the event variable $I$ to its expectation $\hat{I}$ under $H_{0}$) for all four variants of CBS. Here, over-estimation (under-estimation) bias means that the expectations $\hat{I}_{i}$ are larger (smaller) than $I_{i}$.**
| Scan Types | Hypotheses | Distribution for $F(S)$ | $F(S)$ |  |  |
| --- | --- | --- | --- | --- | --- |
|  |  | Null Hypothesis | $H_{0}:\Delta_{i}\sim N(0,\sigma)$, $\forall i\in D_{1}$ |  |  |
|  |  | Alternative Hypothesis | $H_{1}(S):\Delta_{i}\sim N(\mu,\sigma)$ |  |  |
|  |  |  | where $\Delta_{i}=\log\left(\frac{I_{i}}{1-I_{i}}\right)-\log\left(\frac{\hat{I_{i}}}<br>{1-\hat{I_{i}}}\right)$ |  |  |
|  |  | Over-estimation Bias: | $\mu<0$, $\forall i\in S$, and $\mu=0$, $\forall i\notin S$. |  |  |
|  | Predictions | Under-estimation Bias: | $\mu>0$, $\forall i\in S$, and $\mu=0$, $\forall i\notin S$. | Gaussian | $\max_{\mu}\frac{2\mu\left(\sum_{i\in S}\Delta_{i}\right)-|S|\mu^{2}}{2\sigma^{<br>2}}$ |
| Separation | Recommendations | Null Hypothesis | $H_{0}:odds(I_{i})=\frac{\hat{I_{i}}}{1-\hat{I_{i}}}$, $\forall i\in D_{1}$ | Bernoulli |  |
|  | Predictions | Alternative Hypothesis | $H_{1}(S):odds(I_{i})=q\frac{\hat{I_{i}}}{1-\hat{I_{i}}}$ | $\max_{q}\sum_{i\in S}(I_{i}\log(q)$ |  |
|  |  | Over-estimation Bias: | $q<1$, $\forall i\in S$, and $q=1$, $\forall i\notin S$. | $-\log(q\hat{I_{i}}-\hat{I_{i}}+1))$ |  |
| Sufficiency | Recommendations | Under-estimation Bias: | $q>1$, $\forall i\in S$, and $q=1$, $\forall i\notin S$. |  |  |

Given the observed event variables $I_{i}$ and the expectations $\hat{I}_{i}$ of the event variable under the null hypothesis ($I\perp A\>|\>C,X$) for the protected class, we define a score function measuring *subgroup bias*, $F:S\to\mathbb{R}_{\geq 0}$, that can be efficiently optimized over exponentially many subgroups to identify $S^{\ast}=\arg\max_{S}F(S)$. To do so, we follow the literature on spatial and subset scan statistics Kulldorff (); Neill () by defining score functions $F(S)$ that take the general form of a log-likelihood ratio (LLR) test statistic, $F(S)=\log\left(\frac{\Pr(D\>|\>H_{1}(S))}{\Pr(D\>|\>H_{0})}\right)$. Here the denominator represents the likelihood of seeing the observed values of event variable $I$ for subgroup $S$ of the protected class under the null hypothesis $H_{0}$ of no bias. The numerator represents the likelihood of seeing the observed values of $I$ for subgroup $S$ of the protected class under the alternative hypothesis $H_{1}(S)$, where the $I_{i}$ values are systematically increased or decreased as compared to $\hat{I}_{i}$. For $H_{1}(S)$ to represent a deviation from $H_{0}$, $H_{1}$ contains a free parameter ($q$ or $\mu$) that is determined by maximum likelihood estimation. Under-estimation bias ($I_{i}>\hat{I}_{i}$) or over-estimation bias ($I_{i}<\hat{I}_{i}$) can be detected using different constraints for $q$ or $\mu$ as shown in Table [2](#S3.T2). When $I$ is a probabilistic prediction (i.e., for separation scan for predictions), the hypotheses are in the form of a difference of log-odds between $I$ and $\hat{I}$ sampled from a Gaussian distribution. Here the free parameter $\mu$ in $H_{1}$ represents a mean shift ($\mu\neq 0$) of the Gaussian distribution. For all other scans, under $H_{0}$, each observed $I_{i}$ is assumed to be drawn from a Bernoulli distribution centered at the corresponding expectation $\hat{I}_{i}$. Under $H_{1}$, the free parameter $q$ represents a multiplicative increase or decrease ($q\neq 1$) of the odds of $I$ as compared to $\hat{I}$.

As in Zhang and Neill (), a penalty term can be added to $F(S)$ equal to a prespecified scalar times the total number of attribute values included in subgroup $S$, summed across all covariates $X^{1}\ldots X^{m}$. Note that there is no penalty for a given attribute if all attribute values are included, since this is equivalent to ignoring the attribute when defining subgroup $S$. This penalty term encourages more interpretable subgroups and reduces overfitting for high-arity attributes.

We now consider how CBS is able to efficiently maximize $F(S)$ over subgroups $S$ of the protected class, returning $S^{\ast}=\arg\max_{S}F(S)$ and the corresponding score $F(S^{\ast})$. The scan procedure for CBS takes as inputs a dataset $D_{1}=(I,\hat{I},X)$ consisting of the event variable $I_{i}$, the estimated expectation of $I_{i}$ under the null hypothesis $\hat{I}_{i}$, and the covariates $X_{i}$, for each individual in the protected class ($A_{i}=1$), along with several parameters: the type of scan (Gaussian or Bernoulli), the direction of bias to scan for (over- or under-estimation), complexity penalty, and number of iterations. It then searches for the highest-scoring subgroup (consisting of a non-empty subset of values $V^{j}$ for each covariate $X^{j}$), starting with a random initialization on each iteration, and proceeding by *coordinate ascent*. The coordinate ascent step identifies the highest-scoring non-empty subset of values $V^{j}$ for a given covariate $X^{j}$, conditioned on the current subsets of values $V^{-j}$ for all other attributes. As shown in McFowland III et al. (), each individual coordinate ascent step can provably find the optimal subset of attribute values while evaluating only $|X^{j}|$ of the $2^{|X^{j}|}$ subsets of values, where $|X^{j}|$ is the arity of covariate $X^{j}$. This efficient subroutine follows from the fact that the score functions above satisfy the additive linear-time subset scanning property Neill (); Speakman et al. (). The coordinate ascent step is repeated with different, randomly selected covariates until convergence to a local optimum of the score function, and multiple random restarts enable the scan to approach the global optimum McFowland III et al. ().
For an in-depth, self-contained description of the scan algorithm, including pseudocode, and how it exploits an additive property of the score functions to achieve linear-time efficiency for each scan step, see Appendix [A.2](#A1.SS2).

Finally, as described in detail in Appendix [A.3](#A1.SS3), we perform *permutation testing* to compute the p-value of the detected subgroup, comparing its score to the distribution of maximum subgroup scores under $H_{0}$, and report whether it is significant at a given level $\alpha$ (e.g., $\alpha=.05$).

## 4 Evaluation

We evaluate the CBS framework through semi-synthetic simulations. We generate 100 semi-synthetic datasets using the COMPAS data, described in Section [5](#S5), where for each dataset, we randomly select an attribute and value to define the protected class $A$, remove that attribute from $X$, and randomly select a subgroup of the protected class $S_{bias}$ (defined by a non-empty subset of values for each attribute $X^{1}\ldots X^{m}$) into which we will inject biases or base rate shifts. We pick $S_{bias}$ by randomly choosing two attributes ($n_{bias}=2$) and then independently including or excluding each value of those attributes with probability $p_{bias}$ of being included in $S_{bias}$, with $p_{bias}=0.5$. For each attribute-value of the covariates, we draw a weight from a Gaussian distribution, $\mathcal{N}(0,0.2)$. We use these weights to produce the true log-odds of a positive outcome ($Y_{i}=1$) for each individual $i$ by a linear combination of the attribute values with these weights. Additionally, for each individual, we add $\epsilon_{i}^{true}\sim\mathcal{N}(0,\sigma_{true})$ to their true log-odds, representing variation between individuals that arises from factors other than the set of scan attributes, and is incorporated into the predictive model.(^1^11Rudin et al. Rudin et al. () state that COMPAS relies on up to 137 variables collected from a questionnaire. Some of these additional predictors may be informative, but as they note, this complexity creates numerous additional problems ranging from lack of transparency to adverse impacts from data entry errors.)
Given the true log-odds of $Y_{i}=1$ for each individual, we draw each outcome $Y_{i}$ from a Bernoulli distribution with the corresponding probability. Next, we set each individual’s predicted log-odds equal to their true log-odds plus $\epsilon_{i}^{predict}\sim\mathcal{N}(0,\sigma_{predict})$, representing non-systematic errors (random noise) in the predictive model. We use default values of $\sigma_{true}=0.6$ and $\sigma_{predict}=0.2$, but examine the robustness of our results to these parameter values in Appendix [B.4](#A2.SS4); see also Appendix [B.2](#A2.SS2) for discussion of the impact of $\sigma_{true}$ on sufficiency-based definitions of fairness. Finally, we threshold the probabilities to produce binarized recommendations $P_{i,bin}=\mathbbm{1}{(P_{i}\geq 0.5)}$ for each individual $i$. Using covariates from the COMPAS data with synthetic outcomes, predictions, and recommendations enables us to quantify and compare the detection performance of CBS and competing methods for known biases injected into the data.

We compare the four variants of CBS to GerryFair (Kearns et al., ), a framework for detecting biases and learning classifiers that guarantee subgroup fairness, and Multiaccuracy Boost Kim et al. (), a method for auditing subgroup inaccuracies and post-processing classifiers to improve performance to ensure subgroup accuracy. For more information about the modifications we made to both methods to make them more comparable to CBS for these simulations, see Appendix [B.1](#A2.SS1).
We use the same settings for CBS as described in Section [5](#S5), with the exception of running all scans with all conditional variable values rather than as value-conditional scans.
We designed the evaluation to answer three questions:

- [label=(Q0),noitemsep,topsep=0pt,parsep=0pt,partopsep=0pt,leftmargin=*]
- 1.
How well do the four variants of CBS (and competing methods) detect *biases* injected into subgroup $S_{bias}$ of the protected class, in the form of a systematic difference between the predicted and true log-odds of the event variable $I$ for $S_{bias}$?
- 2.
How do the four variants of CBS (and competing methods) respond to a *base rate shift* for subgroup $S_{bias}$ of the protected class, in the form of concurrently shifting both the predicted and true log-odds of the event variable $I$ for $S_{bias}$, assuming no injected bias?
- 3.
To what extent do answers for [1](#S4.I1.i1) and [2](#S4.I1.i2) vary depending on the characteristics of $S_{bias}$?

To address [1](#S4.I1.i1), we inject bias into subgroup $S_{bias}$ of the protected class, keeping the corresponding subgroup of the non-protected class unchanged, in one of two ways:
(1) increasing the predicted log-odds by $\mu_{sep}$ for each individual in $S_{bias}$, and recomputing the model’s predicted probabilities $P_{i}$ and recommendations $P_{i,bin}$; or
(2) reducing the true log-odds by $\mu_{suf}$ for each individual in $S_{bias}$, and redrawing the outcomes $Y_{i}$. Both of these shifts result in a bias in which the predicted values ($P$ or $P_{bin}$) overestimate the outcomes ($Y$) for the given subgroup of the protected class. We distinguish between these two biases because $\mu_{sep}$ corresponds to a shift of the predicted log-odds (the alternative hypothesis for separation scans) and $\mu_{suf}$ corresponds to a shift of the outcomes (the alternative hypothesis for sufficiency scans). To address [2](#S4.I1.i2), we inject a base rate shift into subgroup $S_{bias}$ of the protected class, keeping the corresponding subgroup of the non-protected class unchanged. This is done by increasing *both* the true log-odds and the predicted log-odds by $\delta$, then redrawing outcomes $Y_{i}$ and recomputing predictions $P_{i}$ and recommendations $P_{i,bin}$. For positive $\delta$, this creates a higher base rate of a positive outcome for subgroup $S_{bias}$ of the protected class, as compared to the corresponding subgroup of the non-protected class, while maintaining well-calibrated predictions. For [3](#S4.I1.i3), we vary the size of $S_{bias}$ in two ways. First, we vary the number of attributes, $n_{bias}$, that the attribute-values can be chosen from, between 1 and 4. Second, we vary the probability, $p_{bias}$, that each value of the chosen attributes is included in $S_{bias}$. We run three experiments ($\mu_{sep}=1$, $\mu_{suf}=1$, and $\delta=0.5$) while varying $n_{bias}$ and $p_{bias}$.

Once we inject bias into or shift the base rates of $S_{bias}$ in the protected class, we run all our scans and GerryFair and Multiaccuracy Boost on our data. We measure the accuracy of the detected subset, which we refer to as $S^{\ast}$, for all the scans and methods with the following accuracy measurement: $\frac{\>|\>S_{bias}\cap S^{\ast}\>|\>}{\>|\>S_{bias}\cup S^{\ast}\>|\>}$, or Jaccard similarity between the injected and detected subsets. Accuracies are averaged over 100 semi-synthetic datasets for each experiment.

Figure: Figure 1: Average accuracy (with 95% CI) as a function of the amount of bias injected into subgroup $S_{bias}$ of the protected class, for four variants of CBS, GerryFair, and Multiaccuracy Boost. Left: increasing predicted log-odds by $\mu_{sep}$. Right: decreasing true log-odds by $\mu_{suf}$.
Refer to caption: x1.png

Figure: Figure 2: Average accuracy (with 95% CI) as a function of the base rate difference $\delta$ between protected and non-protected class for subgroup $S_{bias}$, for four variants of CBS, GerryFair, and Multiaccuracy Boost. Note that predictions are well calibrated, $\mu_{sep}=\mu_{suf}=0$.
Refer to caption: x2.png

In Figure [1](#S4.F1), which addresses [1](#S4.I1.i1), we observe that all four variants of CBS are able to detect the injected bias (for subgroup $S_{bias}$ of the protected class) with higher accuracy than GerryFair or Multiaccuracy Boost. Sufficiency scans had highest accuracy for a shift in true log-odds ($\mu_{suf}$), and separation scans had highest accuracy for a shift in predicted log-odds ($\mu_{sep}$). Scans for predictions generally outperformed scans for recommendations, due to the loss of information from binarizing the probabilistic predictions. Interestingly, sufficiency scan for predictions (but not for recommendations) converged to perfect accuracy for $\mu_{sep}$, while separation scans did not converge to perfect accuracy for $\mu_{suf}$. Sufficiency scan for predictions is conditioned on a real-valued variable ($P_{i}$) rather than a binary variable ($P_{i,bin}$ or $Y_{i}$), allowing more flexible modeling of $\mathbb{E}[Y\>|\>P,X]$ and thus greater sensitivity to shifts in predicted log-odds.

In Figure [2](#S4.F2), which addresses [2](#S4.I1.i2), shifting the base rate for subgroup $S_{bias}$ of the protected class results in separation scans detecting a base rate shift when $\delta>0$, while sufficiency scans and competing methods are robust to this shift. This finding aligns with previous research proving that differences in base rates between two populations will result in a higher false positive rate for the population with a higher base rate when using a well-calibrated classifier (Chouldechova, ).
Interestingly, sufficiency scan for recommendations detects a base rate shift for $\delta\ll 0$. In this case, $\mathbb{E}[Y\>|\>P_{bin},X]$ is lower for individuals in the protected class than for individuals with negative recommendations in the non-protected class. Thus conditioning on the binary indicator $P_{i,bin}$ is not sufficient to capture this decrease in the true log-odds, while conditioning on the real-valued prediction $P_{i}$ allows sufficiency scan for predictions to extrapolate reasonably well to these cases.

In Figure [4](#A2.F4) in Appendix [B.3](#A2.SS3), which addresses [3](#S4.I1.i3), we see that increasing the number of affected dimensions $n_{bias}$ generally decreases performance, with the relative accuracies for scans and competing methods similar to those in Figures [1](#S4.F1) and [2](#S4.F2). Interestingly, increasing $p_{bias}$ to 1 (meaning that bias is injected into the entire protected class) enables GerryFair (for $\mu_{sep}$) and Multiaccuracy Boost (for $\mu_{sep}$ and $\mu_{suf}$) to achieve similar accuracy to CBS, but both methods underperform for smaller, more subtle, subgroup biases. Additional robustness checks are described in Appendix [B.4](#A2.SS4), and for estimates of compute power needed for the simulations see Appendix [B.5](#A2.SS5).

## 5 Case Study of COMPAS

The COMPAS algorithm is used in various jurisdictions across the United States as a decision support tool to predict individuals’ risk of recidivism. It is commonly used by judges when deciding whether an arrested individual should be released prior to their trial (Angwin et al., ). We define each defendant’s predicted probability of reoffending, $P_{i}$, by mapping their COMPAS risk score to the proportion of all defendants with the given risk score who reoffended. Defendants with COMPAS risk scores of 5+ are considered “high risk” ($P_{i,bin}=1$) since COMPAS instructs that defendants in this score range should be considered carefully by supervision agencies  (Larson et al., ). For more details about the COMPAS data, as well as critiques of this dataset, please see Appendix [C.1](#A3.SS1) and Appendix [C.3](#A3.SS3) respectively.

We chose the parameters for each of the four variants of CBS (value of the conditioning variable, if it is binary, and direction of effect) in order to search for systematic biases in the COMPAS predictions and recommendations which disadvantage the protected class. For the separation scans, we detect positive deviations for the protected class attribute in the $\mathbb{E}(P\>|\>Y=0,X)$ and $\mbox{Pr}(P_{bin}=1\>|\>Y=0,X)$, i.e., increase in predicted risk and increase in FPR for non-reoffending defendants, respectively. For the sufficiency scans, we detect a negative deviation for the protected class in the $\mbox{Pr}(Y=1\>|\>P,X)$ and $\mbox{Pr}(Y=1\>|\>P_{bin}=1,X)$, i.e., decreased probability of reoffending conditional on predicted risk and on being flagged as high-risk, respectively. For a discussion on the considerations for using COMPAS in this case study and for choosing different group fairness definitions for pre-trial tools, please reference Appendix [C.3](#A3.SS3).
For all scans, we use all attributes except for the sensitive attribute when calculating the probability of being a member of the protected class (for the propensity score weighting step) and when generating the predicted values $\hat{I}$ in Section [3.2](#S3.SS2). All scans were run for 500 iterations with a penalty equal to 1.

Figure: Figure 3: Scores of the subgroups found when running four variants of CBS on COMPAS data for different choices of protected class. A text description of the subgroup $S^{\ast}$ found for each scan is provided if the subgroup score $F(S^{\ast})$ is greater than 0. *** indicates the subgroup’s score is statistically significant with p-value < .05 measured by permutation testing described in Appendix [A.3](#A1.SS3).
Refer to caption: x3.png

Figure [3](#S5.F3) contains the detected subgroups $S^{\ast}$, and their associated log-likelihood ratio scores $F(S^{\ast}$) and corresponding indicators of statistical significance, found by each of the four variants of CBS, for various choices of the protected class: Black, white, younger (under the age of 25) and older (age 25+) defendants. Please see Appendix [A.3](#A1.SS3) for the permutation test procedure used to determine statistical significance of CBS’s detected biases. For the full set of results for all CBS scans when treating each attribute value as the protected class, please see Table [4](#A3.T4) in Appendix [C.2](#A3.SS2). This table also includes information about the number of individuals and the observed rate (e.g., proportion of reoffending), both for the detected subgroup of the protected class, and for the corresponding (comparison) subgroup of the non-protected class.

Below we discuss statistically significant racial and age biases that CBS found in COMPAS’s predictions and recommendations, comparing subgroups found by separation and sufficiency scans:

Racial bias in COMPAS. Figure [3](#S5.F3) shows that the separation scans identify highly significant biases against a subgroup of Black defendants, while the sufficiency scans do not. These results support and complement the previous findings by ProPublica Angwin et al. () and follow-up analyses Chouldechova (), which concluded that COMPAS has large error rate disparities which negatively impact Black defendants (corresponding to large scores for separation scans), and that its predictions are well-calibrated for Black defendants (corresponding to small scores for sufficiency scans). However, CBS’s detected subgroup for the two separation scans adds a useful finding to this discussion: the large FPR disparity of COMPAS against Black defendants is even more significant in the intersectional subgroup of Black males. Non-reoffending Black male defendants have an FPR of 0.44, compared to non-reoffending non-Black male defendants’ FPR of 0.19, whereas non-reoffending Black defendants have an FPR of 0.42, compared to non-reoffending non-Black defendants’ FPR of 0.20.

Age bias in COMPAS. Previous research on COMPAS has argued that it relies heavily on age, and specifically, the assumption that younger defendants are more likely to reoffend (Rudin et al., ), when computing risk scores. Younger defendants have a higher reoffending rate compared to older defendants (0.56 vs. 0.46), and thus, well-calibrated predictions and recommendations would result in younger defendants having higher FPR than older defendants. Our separation scans identify non-reoffending defendants under age 25 arrested on felony charges as the subgroup with the largest FPR disparity.
On the other hand, our sufficiency scans identify a large subgroup bias within the protected class of older (age 25+) defendants: older male defendants with 0-5 priors have a lower rate of reoffending, as compared to younger male defendants with 0-5 priors, both for flagged high-risk defendants (sufficiency for recommendations) and for defendants with similar risk scores (sufficiency for predictions). This finding highlights the scenario described in Section [1](#S1) that CBS is designed to detect: predictions are well-calibrated between older and younger defendants, in aggregate, but not for the detected subgroup of older males with 0-5 priors.

## 6 Limitations

Our CBS framework is designed to audit a classifier’s predictions and recommendations for biases with respect to subgroups of a protected class, whereas competing methods provide mechanisms for both auditing and correcting classifiers. Combining auditors with correction and training presents two challenges, one being how to quantify the inherent trade-offs between performance and fairness when correcting for subgroup biases. Another, more subtle implication of designing auditors that are linked to correction and training methods is that it reinforces the framing that the primary solution to subgroup biases is to correct the models. Given that fairness is often context-specific, ideas of fairness could differ between stakeholders, and upstream biases exist in data sources used in many socio-technical settings, designing an optimally fair model is not always feasible. We endorse exploring larger policy shifts to address biases that auditing tools like CBS might unearth that are correlated with broader societal issues, as well as exploring different ways (not limited to model correction) to address these biases.

CBS is designed to detect biases that take the form of group fairness violations represented as conditional independence relationships. While CBS is easily generalizable to other objectives that can be represented as group-level conditional independence relationships, it is less generalizable to other fairness definitions such as individual and counterfactual fairness definitions (Dwork et al., ; Kusner et al., ). Our technique for estimating the expectations $\hat{I}$ for individuals under the null hypothesis of no bias has the limitation (which is commonly cited in the average treatment effects literature) of only being reliable when using well-specified models for estimating the propensity scores of protected class membership and for estimating $\hat{I}$. Given the consistency of our COMPAS results in Section [5](#S5) with other researchers’ findings about COMPAS, the process of estimating $\hat{I}$ seems to model the COMPAS data well. With that said, we encourage users of CBS to check estimates of $\hat{I}$ and if necessary, employ procedures common in the econometric literature (such as (Imbens, ; Schuler and Rose, )) or calibration methods within the computer science literature. Lastly, there are various limitations to permutation testing, some of which are discussed in Berger (), such as the conservatism of p-values obtained by permutation tests. For CBS specifically, if $\hat{I}$ is poorly estimated during permutation testing, this could result in higher type II errors where CBS is more likely to erroneously accept the null hypothesis $H_{0}$ of no bias.

Our simulation experiments in Section [4](#S4) account for bias in the form of shifts in the predicted and true log-odds (separately and jointly) – which produces predictive and aggregation biases – for a prescribed set of covariate attribute values in the protected class. In real-world scenarios, the generative process of bias might differ from the assumptions made in our simulations in various ways including: (1) noisy biased subgroups in the protected class not easily defined by discrete sets of covariate attribute values; (2) irregular shifts in the predicted and true log-odds within a biased subgroup that are not related to covariate attributes; (3) other forms of predictive bias not defined by conditional independence statements (i.e., outside of separation and sufficiency group fairness metrics). Future research could determine and (if necessary) improve CBS’s robustness to different generative schemas of bias.

In summary, CBS is a framework that works with most group-level fairness definitions to detect intersectional and contextual biases within subgroups of the protected class. CBS overcomes some of the issues that arise when only considering fairness violations in aggregate for singular protected attribute values. We showed that the CBS framework can discover previously undocumented intersectional and contextual biases in COMPAS scores, and that it outperforms similar methods that audit classifiers for subgroup fairness. Despite the limitations above, we hope that this work will be useful to practitioners wishing to identify and correct more subtle subgroup biases in decision-support tools.

## Acknowledgments and Disclosure of Funding

This material is based upon work supported by the National Science Foundation Program on Fairness in Artificial Intelligence in Collaboration with Amazon, grant IIS-2040898. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation or Amazon.

## Appendix A Methods Appendices

### A.1 Details about the Method for Generating I ^ ^ 𝐼 \hat{I} over^ start_ARG italic_I end_ARG used in Section 3.2 and its Limitations

The method presented in Section [3.2](#S3.SS2) describes how to estimate $\hat{I_{i}}$, the expectation of the event variable $I_{i}$ for each individual $i$ in the protected class, under the null hypothesis, $H_{0}$, of no bias (i.e., $I\perp A\>|\>C,X$). Using the estimated $\hat{I}$ and observed $I$, we can determine which subgroups in the protected class have the largest deviations in $I$ as compared to what we would expect if there was no bias, $\hat{I}$. The method to generate $\hat{I}$ borrows from the literature on causal inference in observational settings, where propensity score reweighting is used to account for the selection of individuals into a “treatment” condition (here, membership in the protected class) given their observed covariates $X$.

The method to estimate $\hat{I}$ consists of the following steps:

- 1.
Train a predictive model using all the individuals in the data to estimate $\mbox{Pr}(A=1\>|\>X)$.
- 2.
Use this model to produce the probabilities, $p_{i}^{A}=\mbox{Pr}(A_{i}=1\>|\>X_{i})$, and the corresponding propensity score weights, $w_{i}^{A}=\frac{p_{i}^{A}}{1-p_{i}^{A}}$, for each individual $i$ in the non-protected class ($A_{i}=0$). Intuitively, individuals in the non-protected class whose attributes $X_{i}$ are more similar to individuals in the protected class have higher weights $w_{i}^{A}$.
This weighting scheme is used in the literature to produce causal effect estimates that can be interpreted as the average treatment effect on treated individuals (ATT) under typical assumptions of positivity and strong ignorability.
- 3.
If the event variable, $I$, is binary (i.e., for all sufficiency scans and separation scan for recommendations), we train a model using only data for individuals in the non-protected class ($A_{i}=0$) to estimate $\mathbb{E}_{H_{0}}[I\>|\>C,X]$ by weighting each individual $i$ in the non-protected class by $w_{i}^{A}$. The trained model is used to estimate the expectations $\hat{I}_{i}=\mathbb{E}_{H_{0}}[I_{i}\>|\>C_{i},X_{i}]$ for each individual in the protected class ($A_{i}=1$) under the null hypothesis, $H_{0}$, of $I\perp A\>|\>(C,X)$.
- 4.
For the separation scan for predictions, we have a real-valued event variable, the probabilistic predictions $P$, rather than a binary event variable. We use a similar but modified process to estimate $\mathbb{E}_{H_{0}}[I\>|\>C,X]$, where $I=P$ and $C=Y$. For each individual $i$ in the non-protected class, we create two training records containing the same covariates $X_{i}$, but different labels and associated weights:
(a)
For the first record, we set the label, $I_{i_{+}}^{temp}$, equal to 1, and set the weight to $w_{i}^{A}P_{i}$.
(b)
For the second record, we set the label, $I_{i_{-}}^{temp}$, equal to 0, and set the weight to $w_{i}^{A}(1-P_{i})$
We create a dataset that includes both records for each individual in the non-protected class and their associated weights, and use this concatenated data set to train a model that estimates $\mathbb{E}_{H_{0}}[I^{temp}\>|\>C,X]$, by weighting each individual $i$ in the non-protected class by either $w_{i}^{A}P_{i}$ or $w_{i}^{A}(1-P_{i})$ as described above. This approach is consistent with other CBS variants and enforces the desired constraint $0\leq\hat{I}_{i}\leq 1$, unlike alternative approaches such as using regression models to predict $P$.

For value-conditional scans, CBS audits for biases in the subset of data where $C=z$, for $z\in\{0,1\}$. Dataset $D$ is filtered before Step [3](#A1.I1.i3) to only include individuals where $C=z$. For example, for the value-conditional scan for FPR, we filter the data to only include individuals where $C=0$ (or equivalently, $Y=0$).

A probabilistic model can be used to estimate $\mbox{Pr}(A=1\>|\>X)$ in Step [1](#A1.I1.i1), and a probabilistic model that allows for weighting of instances during training can be used to estimate $\mathbb{E}_{H_{0}}[I\>|\>C,X]$ in Steps [3](#A1.I1.i3) and [4](#A1.I1.i4). For Sections [4](#S4) and [5](#S5), as well as Appendices [B.3](#A2.SS3) and [B.4](#A2.SS4), we use logistic regression to estimate $\mbox{Pr}(A=1\>|\>X)$ and weighted logistic regression to estimate $\mathbb{E}_{H_{0}}[I\>|\>C,X]$. When estimating $\mathbb{E}_{H_{0}}[Y\>|\>P,X]$ (the realized expectation of $\mathbb{E}_{H_{0}}[I\>|\>C,X]$) for sufficiency scan for predictions, we transform the conditional variable, $P_{i}$, to its corresponding log-odds, $\log\frac{P_{i}}{1-P_{i}}$, prior to training, since we expect $\log\frac{Y_{i}}{1-Y_{i}}$ (the target of the logistic regression) to be approximately $\log\frac{P_{i}}{1-P_{i}}$ for well-calibrated classifiers.
Alternative prediction models, such as random forests with Platt scaling for calibration of probability estimates, could also be used in place of logistic regression.

The method described above has the limitation of only producing accurate estimates of $\hat{I}$ when both the model for $\mbox{Pr}(A=1\>|\>X)$ and $\mathbb{E}_{H_{0}}[I\>|\>C,X]$ are well-specified. Accurate estimates of $\hat{I}$ are essential for CBS to accurately detect the subgroup in the protected class with the most deviation between the observed $I$ and estimated $\hat{I}$ under the null hypothesis of no bias. Given the consistency of our findings for the COMPAS case study in Section [5](#S5) with other researchers’ findings about COMPAS, as well as other checks we have performed to examine $\hat{I}$, we believe the method above suffices for our research purposes. We encourage others using CBS to be aware of this limitation, pay special consideration to estimates of $\hat{I}$, and if necessary, employ methods from the causal inference literature on doubly robust estimation (such as (Imbens, ; Schuler and Rose, )) or methods from the computer science literature for model calibration when producing estimates of $\hat{I}$.

### A.2 Fast Subset Scanning for Conditional Bias Scan

In this section, we explain the fast subset scanning (FSS) algorithm that CBS uses to find the subgroup of the protected class with the most biased predictions or recommendations (Neill, ). We will introduce FSS using a simplified example, for illustrative purposes, to highlight the computational difficulties inherent in subset scanning, the additive property of the score functions for CBS that enable computationally feasible subset scanning, and the implementation of FSS for CBS.

Let us assume a dataset of individuals in the protected class ($A=1$), denoted as $Q=\{(X^{1},I,\hat{I})\}$, that contains values of the event variable $I_{i}$, estimates $\hat{I}_{i}$ of the expected value of the event variable under the null hypothesis of no bias, and
a single categorical covariate attribute $X_{i}^{1}$ for each individual $i$.
For concreteness, we perform a sufficiency scan for predictions, therefore, the event variable $I_{i}$ is the observed binary outcome $Y_{i}$ for individual $i$, and the corresponding $\hat{I}_{i}$ is the estimated $\Pr(Y_{i}=1\>|\>P_{i},X_{i})$ under the null hypothesis $H_{0}$ that $Y\perp A\>|\>(P,X)$. $S$ refers to a subgroup of $Q$, which in our simple example is a non-empty subset of values for attribute $X^{1}$. Since our event variable is binary, we use the Bernoulli likelihood function to represent the hypotheses in the score function, $F(S)$, used to determine the level of anomalousness of a subgroup $S$ of $Q$.

In the worst-case scenario, $X^{1}$ could be a categorical variable with distinct values for each of the $n$ rows of data in $Q$. If we were to score all of the possible $S\subseteq Q$ using $F(S)$, this method would have a runtime of $O(2^{n}$), which would be computationally infeasible. To overcome this computational barrier, FSS relies on its score functions, $F(S)$, being a part of an efficiently optimizable class of functions in order to find the most anomalous subset $S^{\ast}=\arg\max_{S\subseteq Q}F(S)$ without the need to evaluate all of the subsets of $Q$. The property that determines if a function is a part of this class that enables fast subset scanning is called Additive Linear-Time Subset Scanning (ALTSS) (Speakman et al., ) and is formally defined in Appendix [A.2.1](#A1.SS2.SSS1). Informally, if $F(S)$ can be represented as an additive set function over all instances $i\in S$ when conditioning on the free parameter ($q$ for the Bernoulli distribution or $\mu$ for the Gaussian distribution in Table [2](#S3.T2)), it satisfies this property (Speakman et al., ).

To explore how FSS exploits the ALTSS property for computationally efficient subset scanning, assume that the categorical covariate $X^{1}$ for each individual $i$ can only be equal to one of four values, $X_{i}^{1}\in\{a,b,c,d\}$. FSS constructs a subset for each attribute value of $X^{1}$ such that $S_{a}=\{i\in Q:X_{i}^{1}=a\}$, $S_{b}=\{i\in Q:X_{i}^{1}=b\}$, $S_{c}=\{i\in Q:X_{i}^{1}=c\}$, $S_{d}=\{i\in Q:X_{i}^{1}=d\}$. Since we are using the likelihood function for the Bernoulli distribution for $F(S)$, $F(S)$ is a concave function of the free parameter $q$, and for illustrative purposes, we will assume that $\max_{q}F(S)$ is positive for all subsets $S_{a},S_{b},S_{c}$ and $S_{d}$. Therefore, for each subset $S_{a},S_{b},S_{c}$ and $S_{d}$, $F(S)$ is a function over the domain of $q$, where as $q$ increases from $-\infty$, $F(S)$ eventually equals 0 0 and then the global maximum for $F(S)$ for that given subset, and then starts decreasing until it again reaches a point where $F(S)=0$, and then remains negative as $q$ approaches $\infty$. FSS identifies three $q$ values for each subset, $S\in\{S_{a},S_{b},S_{c},S_{d}\}$:

- 1.
The first value of $q$ where $F(S)=0$ as $q$ increases from $-\infty$ to $\infty$, which we will refer to as $q_{min}$.
- 2.
The second value of $q$ where $F(S)=0$ as $q$ increases from $-\infty$ to $\infty$, which we will refer to as $q_{max}$.
- 3.
The value of $q$ for $\operatorname*{argmax}_{q}F(S)$, which we will refer to as $q_{\text{MLE}}$.

Each distinct $q_{min}$ and $q_{max}$ value for subsets ($S_{a}$, $S_{b}$, $S_{c}$, $S_{d}$) is a value of $q$ where the score function $F(S)$ becomes negative or positive for at least one of these four subsets. By sorting all of the distinct $q_{min}$ and $q_{max}$ values across all the subsets ($S_{a}$, $S_{b}$, $S_{c}$, $S_{d}$) in ascending order, we construct a list of $q$ values, $\{q_{(1)},...,q_{(m)}\}$, where each pair of adjacent values, $q_{(k)}$ and $q_{(k+1)}$, represents an interval of the $q$ domain, $(q_{(k)},q_{(k+1)})$, for which each subset $S\in\{S_{a},S_{b},S_{c},S_{d}\}$ has either $F(S)>0$ for the entire interval or $F(S)<0$ for the entire interval.
For each interval, we perform the following:

- 1.
Find the midpoint of the interval (average of $q_{(k)}$ and $q_{(k+1)}$), which we refer to as $q_{k}^{\text{mid}}$.
- 2.
Create a new subset $S_{k}^{\text{aggregate}}$ by aggregating all subsets $S\in\{S_{a},S_{b},S_{c},S_{d}\}$ where the subset’s $q_{min}<q_{k}^{\text{mid}}$ and the subset’s $q_{max}>q_{k}^{\text{mid}}$, i.e., $F(S)>0$ when $q=q_{k}^{\text{mid}}$ and therefore for the entire interval ($q_{(k)}$, $q_{(k+1)}$).
Since the score function is additive, conditioned on $q$, we know that a subset $S$ will make a positive contribution to the score $F(S_{k}^{\text{aggregate}})$ if and only if $F(S)>0$ for that value of $q$. Thus, we know that the highest scoring subset $S_{k}^{\text{aggregate}}$ for that interval $[q_{(k)},q_{(k+1)}]$ contains all and only those subsets $S$ with $F(S)>0$ at $q=q_{k}^{\text{mid}}$.
- 3.
Find the maximum likelihood estimate of $q$, $q_{\text{MLE}}^{\text{aggregate}}=\operatorname*{argmax}_{q}F(S_{k}^{\text{
aggregate}})$, and the corresponding score $F(S_{k}^{\text{aggregate}})$.

The aggregate subset, $S_{k}^{\text{aggregate}}$, with the highest score for $F(S)$ using its associated $q_{\text{MLE}}^{\text{aggregate}}$ is the most anomalous subset when considering subsets formed by combinations of different attribute-values of $X^{1}$.

For our simplified example, there are at most 8 distinct $q_{min}$ or $q_{max}$ values from the four subsets ($S_{a}$, $S_{b}$, $S_{c}$, $S_{d}$), and thus at most 7 distinct intervals $(q_{(k)},q_{(k+1)})$ that must be considered. For a given interval, we need to evaluate only a single subset $S_{k}^{\text{aggregate}}$, and thus, only 7 of the 15 non-empty subsets of $\{S_{a},S_{b},S_{c},S_{d}\}$. More generally, if $n$ is the arity (number of attribute values) of categorical attribute $X^{1}$, at most $2n-1$ of the $2^{n}-1$ non-empty subsets of attribute values must be evaluated to identify the highest-scoring subgroup.

The scenario where the covariates consist of a single categorical attribute is a simplified example, where only a single iteration of FSS is needed to find the optimal subset, $S^{*}$, of $Q$. When there are two or more attributes for the covariates, multiple iterations of FSS must be performed to find the optimal subset. On each iteration the following is performed:

- 1.
We define an initial subset, $S_{temp}$ where:
(a)
If it is the first iteration, all of the attribute values for each attribute are included in $S_{temp}$.
(b)
Otherwise, a random subset of attribute values for each attribute are chosen to be included in $S_{temp}$.
- 2.
For each attribute $X^{i}$, in random order, we construct subsets by partitioning $S_{temp}$ by the distinct attribute values of $X^{i}$, form intervals across the domain of $q$ for $F(S)$, and then assemble and score the subsets for each interval (as described above). $S_{temp}$ is updated as higher scoring subsets using $F(S)$ are found. Therefore, when an attribute is evaluated, $S_{temp}$ contains only rows of $Q$ that fit the found criteria (in the form of attribute values) from previously evaluated attributes, excluding the attribute currently under consideration. This iterative ascent procedure is repeated until convergence.

Multiple iterations are performed with the final optimal subset being the subset with the highest score using $F(S)$ found across all the iterations, $S^{\ast}$. For the pseudocode of FSS for CBS, reference Appendix [A.2.2](#A1.SS2.SSS2). The final results from FSS are the optimal subset, $S^{*}$, in the form of attribute-values that form the criteria for the subgroup in the protected class with the most anomalous bias detected, the parameter $q$ or $\mu$ that maximizes $F(S^{*})$, and the score $F(S^{*})$ given the parameter $q$ or $\mu$.

#### A.2.1 Formal Definition of Additive Linear-Time Subset Scanning Property (ALTSS)

Below we provide a formal definition of the Additive Linear-Time Subset Scanning Property. The score functions, $F(S)$, used to evaluate subgroups are a log-likelihood ratio formed from two different hypotheses whose likelihoods are modeled by likelihood functions for either the Bernoulli distribution or Gaussian distribution, both of which satisfy the Additive Linear-time Subset Scanning Property Speakman et al. (); Zhang and Neill ().

###### Definition A.1 (Additive Linear-time Subset Scanning Property) .

A function, $F:S\times\theta\to\mathbb{R}_{\geq 0}$, that produces a score for a subset $S\subseteq D$, where $D$ is a set of data and $\theta=\operatorname*{argmax}_{\theta}F(S\>|\>\theta)$, satisfies the Additive Linear-time Subset Scanning Property if $F(S\>|\>\theta)=\sum_{s_{i}\in S}F(s_{i}\>|\>\theta)$ where $s_{i}$ is a subset of $S$ and $\forall s_{i},s_{j}\in S$, where $s_{i}\neq s_{j}$, we have $s_{i}\cap s_{j}=\emptyset$.

We refer to the score functions, $F(S)$, contained in the rightmost column of Table [2](#S3.T2) as $F(S\>|\>\mu)$ for the score functions that use the Gaussian likelihood function to form hypotheses and $F(S\>|\>q)$ for the score functions that use the Bernoulli likelihood function to form hypotheses. $F(S\>|\>q)$ contains a summation, $\sum_{i\in S}(I_{i}\log q-\log(q\hat{I_{i}}-\hat{I_{i}}+1))$, that is the sum of individual-specific values derived from $I_{i}$, $\hat{I_{i}}$, and $q$. Given that each individual is distinct, $F(S\>|\>q)=\sum_{i\in S}F(s_{i}\>|\>q)$, where $s_{i}$ is the subset of $S$ that contains only individual $i$, satisfies the ALTSS property. Similarly, $F(S\>|\>\mu)$ contains a summation, $\sum_{i\in S}\Delta_{i}$, that is the sum of individual-specific values $\Delta_{i}$ derived from $I_{i}$, $\hat{I_{i}}$, and $\mu$. Therefore $F(S\>|\>\mu)=\sum_{s_{i}\in S}F(s_{i}\>|\>\mu)$, where $s_{i}$ is the subset of $S$ that contains only individual $i$, satisfies the ALTSS property.

###### Definition A.1 (Additive Linear-time Subset Scanning Property) .

#### A.2.2 Pseudocode of Fast Subset Scan Algorithm for Conditional Bias Scan

Figure: Algorithm 1 Fast Subset Scan for Conditional Bias Scan

Algorithm [1](#alg1) is the pseudocode for the Fast Subset Scan (FSS) algorithm used in the CBS framework (Neill, ). The algorithm finds the subgroup, $S^{\ast}$, with the most anomalous signal (i.e., the highest score $F(S^{\ast})$) in a dataset. For CBS, this signal is in the form of a bias (according to one of the fairness definitions in Table [1](#S3.T1)) against members of the protected class ($A=1$) for subgroup $S^{\ast}$. The dataset passed to the FSS algorithm by CBS contains only individuals $i$ in the protected class, and FSS compares their values of the event variable $I_{i}$ to the estimated expectations $\hat{I}_{i}$ under the null hypothesis of no bias.

At the initialization of FSS, placeholder variables are created that will hold the most anomalous subset ($S^{*}$), and the subset’s corresponding information ($\theta^{\ast}$, $Score^{\ast}$), across all iterations (Lines [2](#alg1.l2)-[4](#alg1.l4)). At the beginning of an iteration, a random subset is picked (set of attribute-values) as the starting subset, $S_{temp}$, with the exception of the first iteration where the starting subset includes all attribute values, as shown in the if-else statement starting on Line [6](#alg1.l6).
For each iteration of this algorithm, we repeatedly choose a random attribute to scan (i.e., we scan over subsets of its attribute values) as shown in Lines [15](#alg1.l15)-[16](#alg1.l16), until convergence (i.e., when all attributes have been scanned without increasing the score $F(S_{temp})$).

For each attribute $X_{temp}$ to be scanned, for each of its attribute values $X_{{temp}_{i}}$, we score the subset $S_{X_{{temp}_{i}}}$ containing only the records with the given value of that attribute ($X_{temp}=X_{{temp}_{i}}$), and matching subset $S_{temp}$ on all other attributes in $X$. We write this as $S_{X_{{temp}_{i}}}\leftarrow S_{temp}^{relaxed}\cap\{i\in D:X_{temp}=X_{temp_{
i}}\}$, where
$S_{temp}^{relaxed}$ is the relaxation of subset $S_{temp}$ to include all values for attribute $X_{temp}$. Along with scoring this attribute-value subset $S_{X_{{temp}_{i}}}$, we find the two values of $\theta$ where $F(S_{X_{{temp}_{i}}})=0$, $\theta_{min_{i}}$ and $\theta_{max_{i}}$, and the $\theta$ that maximizes $F(S_{X_{{temp}_{i}}})$, $\theta_{MLE_{i}}$, with the exception of attribute-value subsets $S_{X_{{temp}_{i}}}$ that are not positive for any value of $\theta$. This is shown in the for-loop in Lines [17](#alg1.l17)-[22](#alg1.l22).

Line [22](#alg1.l22) states that $\theta_{min_{i}}$ and $\theta_{max_{i}}$ must be adjusted according to the direction of the scan to enforce that the found parameters $\theta_{min_{i}}$ and $\theta_{max_{i}}$ adhere to the restrictions set by the direction of the scan. The constraints necessary for the scans to detect biases in the positive and negative directions are fully specified in Table [2](#S3.T2). For positive scans that have score functions that utilize the Gaussian likelihood function to form hypotheses, $\theta_{min_{i}}=\max(0,\theta_{min_{i}}$) and for negative scans that utilize the Gaussian likelihood function, $\theta_{max_{i}}=\min(0,\theta_{max_{i}}$). For positive scans that have score functions that utilize the Bernoulli likelihood function to form hypotheses, $\theta_{min_{i}}=\max(1,\theta_{min_{i}}$) and for negative scans that utilize the Bernoulli likelihood function, $\theta_{max_{i}}=\min(1,\theta_{max_{i}}$). Attribute-value subsets $S_{X_{{temp}_{i}}}$ should not be considered when choosing subsets for $S^{\text{aggregate}}$ for positive scans where $\theta_{max_{i}}<0$ or $\theta_{max_{i}}<1$ for scans using the Gaussian likelihood function or Bernoulli likelihood function in $F(S)$, respectively. Conversely, attribute-value subsets $S_{X_{{temp}_{i}}}$ should not be considered when choosing subsets for $S^{\text{aggregate}}$ for negative scans where $\theta_{min_{i}}>0$ or $\theta_{min_{i}}>1$ for scans using the Gaussian likelihood function or Bernoulli likelihood function in $F(S)$, respectively.

We sort the $\theta_{min_{i}}$ and $\theta_{max_{i}}$ values found across all the attribute values of the attribute we are scanning in ascending order in Line [24](#alg1.l24). These form a list of intervals over the domain of $\theta$. For each interval, we calculate a midpoint of that interval, and aggregate all the attribute-value subsets that have a positive score, $F(S)$, when $\theta$ equals the midpoint of that interval in Lines [31](#alg1.l31)-[34](#alg1.l34). If the aggregated subset of attribute values with the maximum score across all the intervals is greater than the score of $S_{temp}$, we update $S_{temp}$ and all of its accompanying information ($\theta_{temp}$, $Score_{temp}$) to equal the maximum-scoring subset of aggregated attribute-values across all the intervals and its accompanying information. $S_{temp}$ is continuously updated as higher scoring subsets are found as we scan over all the attributes and their attribute values.

At the end of an iteration, if the found subset, $S_{temp}$, has a higher score than the global maximum scoring subset $S^{\ast}$, then $S^{\ast}$ and its accompanying information ($\theta^{\ast}$, $Score^{\ast}$) are replaced with $S_{temp}$ and $S_{temp}$’s accompanying information. Once all the iterations have completed, the subset with the maximum score found across all iterations is returned, $S^{\ast}$, with its score $F(S^{\ast}\>|\>\theta^{\ast})$ and accompanying $\theta^{\ast}$ parameter.

McFowland et al. show that a similar multidimensional scan algorithm, used for heterogeneous treatment effect estimation, will converge with high probability to a near-optimal subset when run with multiple iterations (McFowland III et al., ).

### A.3 Permutation Testing to Determine Statistical Significance of Detected Subgroups

As discussed in Section [3.3](#S3.SS3), the statistical significance ($p$-value) of the discovered subgroup $S^{\ast}$ can be obtained by *permutation testing*, which correctly adjusts for the multiple testing resulting from searching over subgroups. To do so, we generate a large number of simulated datasets under the null hypothesis $H_{0}$, perform the same CBS scan for each null dataset (maximizing the log-likelihood ratio score over subgroups, exactly as performed for the original dataset), and compare the maximum score $F(S^{\ast})$ for the true dataset to the distribution of maximum scores $F(S^{\ast})$ for the simulated datasets. The detected subgroup is significant at level $\alpha$ if its score exceeds the $1-\alpha$ quantile of the $F(S^{\ast})$ values for the simulated datasets. To generate each simulated dataset, we copy the original dataset and randomly permute the values of $A_{i}$ (whether or not each individual is
a member of the protected class), thus testing the null hypothesis that $A$ is conditionally independent of the event variable $I$.

This permutation testing approach is computationally expensive, multiplying the runtime by the total number of datasets (original and simulated) on which the CBS scan is performed, but it has the benefit of bounding the overall false positive rate (family-wise type I error rate) of the scan while maintaining high detection power. (In comparison, a simpler approach like Bonferroni correction would also bound the overall false positive rate, and would require much less runtime, but would suffer from dramatically reduced detection power.) For a given dataset, the score threshold for significance at a fixed level $\alpha=.05$ will differ for different choices of the sensitive attribute and protected class. Thus, if CBS is used to audit a classifier for possible biases against multiple protected classes, a separate permutation test must be performed for each protected class value.

### A.4 Conditional Bias Scan Framework Parameters

**Table 3: Table with all parameters needed to run Conditional Bias Scan. The table lists the parameter, purpose of the parameter, possible values of the parameter, when applicable, and the sections in our paper where this parameter is described in further detail.**
| Parameter | Purpose | Parameter Attribute Values | Sections for Reference |
| --- | --- | --- | --- |
| Membership in Protected Class Indicator Variable ($A$) | Binary attribute which defines whether each individual is a member of the protected class. We wish to identify any biases that are present in the classifier’s predictions or recommendations that impact the protected class. |  | [3](#S3) |
| Scan Type | The subcategory of the scan type | Separation scan for recommendations; Separation scan for predictions;<br>Sufficiency scan for recommendations;<br>Sufficiency scan for predictions | [3.1](#S3.SS1) |
| Event Variable ($I$) | The event of interest for the scan. The abstracted event variable must be defined as either the outcome, prediction, or recommendation variable. | $Y$; $P$; $P_{bin}$ | [3](#S3), [3.1](#S3.SS1) |
| Conditional Variable ($C$) | The conditional variable for the scan. The abstracted conditional variable must be defined as either the outcome, prediction, or recommendation variable. | $Y$; $P$; $P_{bin}$ | [3](#S3), [3.1](#S3.SS1) |
| Field value ($z$) of Conditional Variable ($C=z$) | For value-conditional scans, this is the value on which we are conditioning the conditional variable ($C$). Defining a field value results in scans that detect different forms of fairness violations. | None; 0; 1 | [3](#S3), [3.2](#S3.SS2), [3.3](#S3.SS3), [A.2](#A1.SS2) |
| List of Attributes for forming subgroups ($X$) | List of attributes to scan over to form subgroups |  | [3](#S3), [3.1](#S3.SS1), [A.2](#A1.SS2) |
| Direction of Bias | Specifying whether we are detecting under-estimation bias (positive direction) or over-estimation bias (negative direction) | Positive; Negative | [3.1](#S3.SS1), [3.3](#S3.SS3), [A.2](#A1.SS2) |
| List of Attributes for estimating $\hat{I}$ ($X$) | List of attributes used for conditioning when producing $\hat{I}$. In this paper we use the same attributes to form subgroups and produce $\hat{I}$. This does not necessarily have to be the case for all applications of CBS. |  | [3.2](#S3.SS2), [A.1](#A1.SS1) |
| Subgroup Complexity Penalty | The non-negative integer-valued scalar penalty that is subtracted from the score function for each subgroup, depending on the subgroup’s total number of included values for each covariate $X^{1}\ldots X^{m}$, not including covariates for which all values are included. | $0+$ | [3.3](#S3.SS3) |
| Scan Iterations | Specifies the number of iterations to run the fast subset scanning algorithm | $1+$ | [3.3](#S3.SS3), [A.2](#A1.SS2) |

## Appendix B Evaluation Appendices

### B.1 Adaptions of the Competing Methods used as Benchmarks

Both GerryFair and Multiaccuracy Boost provide implementations of their methods on GitHub Neel et al. (); Kim et al. (). Our goal was to use their provided code with minimal changes as benchmarks in Section [4](#S4). However, GerryFair and Multiaccuracy Boost do not provide the functionality to indicate whether to audit for bias in the positive direction (under-estimation bias) or bias in the negative direction (over-estimation bias). This lack of functionality makes the results from CBS substantially different than those returned by GerryFair and Multiaccuracy Boost.

For GerryFair’s auditor, given the type of error rate to audit (false negative rate or false positive rate), they train four linear regressions using the features ($X$) as dependent variables with the following four sets of labels:

- 1.
Two linear regressions with the zero set as labels.
- 2.
One linear regression with the labels set to a measurement that assigns positive costs for predictions that deviate in the *positive* direction (when the predictions are greater than the observed global error rate), and negative costs otherwise.
- 3.
One linear regression with the labels set to a measurement that assigns positive costs for predictions that deviate in the *negative* direction (when the predictions are less than the observed global error rate), and negative costs otherwise.

They use the predictions from the linear regressions to flag a subset of data where the predictions from the linear regression trained with the zero set labels are greater than the values predicted by the linear regression trained with the costs representing deviations of the predictions from the observed baseline error rate metric of interest as labels. Two linear regressions are used to estimate deviations of the predictions from the observed error rate baseline, and therefore they form two subgroups: (1) a subgroup with rows that are estimated to have predictions that are greater than the baseline for the metric of interest; and (2) a subgroup with rows that are estimated to have predictions that are less than the baseline for the metric of interest. The original GerryFair implementation uses a heuristic to decide which subgroup has more significant biases and returns that subgroup accordingly. The subgroup with the rows that are estimated to have predictions that are greater than the metric of interest more closely aligns with the concept of auditing for bias in the positive direction or auditing for under-estimation bias. Since CBS provides the functionality of auditing for biases of a specific direction, we add an option to GerryFair that allows the user to determine which direction of bias they are interested in, making GerryFair’s results more comparable to CBS.

For each simulation, we ran GerryFair two times, once to detect bias in the form of systematic increases in the false positive rate, and once to detect bias in the form of systematic increases in the false negative rate. In each case, we allow GerryFair to use all covariates ($X$) to make the predictions used to form subgroups, including the protected class category.
This resulted in two result sets for GerryFair for each simulation. We present the result set in Section [4](#S4) that had the highest overall accuracy for most of the simulations, which is the GerryFair setup for detecting increased false positive rate. GerryFair returns a subgroup that could contain individuals in both the protected class and the non-protected class. To have the accuracy measurements for GerryFair and CBS be comparable, we filter the subgroup returned by GerryFair to only include individuals in the protected class before calculating the subgroup’s accuracy.

Multiaccuracy Boost is an iterative algorithm, where on each iteration it audits for a subgroup with inaccuracies and then corrects that subgroup’s predicted log-odds. More specifically, for each iteration:

- 1.
A custom heuristic is calculated for all rows of data, similar to an absolute residual, where larger values represent a larger deviation between the observed labels and predictions.
- 2.
The residuals of all the rows’ predictions and observed outcomes are calculated.
- 3.
The full data is split into a training and holdout set.
- 4.
Three partitions of data are created for the training data, hold out data, and the full dataset:
(a)
A partition containing all the rows.
(b)
A partition containing all the rows with predictions greater than 0.50.
(c)
A partition containing all the rows with predictions less than or equal to 0.50.
- 5.
For each of the partitions of data constructed in Step [4](#A2.I2.i4):
(a)
A ridge regression classifier (using $\alpha=1.0$) is trained using the respective partition in the training data, with the covariates $X$ as features and the custom heuristic calculated in Step [1](#A2.I2.i1) as labels.
(b)
The ridge regression classifier is used to make predictions for the respective partition in the holdout data.
(c)
If the average of the predictions multiplied by the residuals for the partition set in the hold out data is greater than $10^{-4}$, then the predicted log-odds for the respective partition in the full dataset is shifted by the predictions multiplied by 0.1.
(d)
If the predicted log-odds are updated, the iteration terminates and no other partitions of data are evaluated for that iteration.

The steps above are slightly modified for the scenario of a classifier that produces a singular probability of a positive outcome whereas the original Multiaccuracy Boost was designed for was a bivariate outcome vector from a Inception-ResNet-v1 model. To make Multiaccuracy Boost audit for bias in one direction, when calculating whether a partition of the data’s predicted log-odds should be updated using the holdout data to remove an inaccuracy, we override the residuals that are negative with 0. In effect, we only consider rows with negative outcomes when deciding which partition of predictions have inaccuracies that need to be corrected on a given iteration. This was the least invasive modification we could make to Multiaccuracy Boost to have it solely consider bias in the positive direction when deciding which subgroup’s predicted log-odds to update.

Since the auditor and correction method are functioning in tandem, we run all iterations of the algorithm and log each subgroup (i.e., partition) that was detected as needing a correction to its predicted log-odds and its associated score calculated in Step [5c](#A2.I2.i5.I1.i3). After the algorithm terminates, we find the partition with the highest score and return its associated partition in the full data set. The decision to return the partition with the highest score across all the iterations of Multiaccuracy Boost in the simulations is motivated by the fact that Multiaccuracy Boost’s auditor has no theoretical guarantees of detecting the most inaccurate partition on a specific iteration of the algorithm, but given our intuition of the algorithm this partition is most likely to be found on the first iteration of the algorithm. Similarly to GerryFair, Multiaccuracy Boost detects a subgroup that contains members of the protected class and non-protected class. We filter all the individuals in the returned subgroup to only contain individuals who are part of the protected class before calculating the accuracy of the returned partition.

One distinction between these methods and CBS is that their auditors were intended to be used in conjunction with another process to improve a classifier or predictions. Therefore, their auditors were designed to have the level of detection accuracy necessary to discern which subgroups or partitions of data need to be corrected, either by modifying the classifier or by post-processing their predicted log-odds. Given that both methods suggest that they can be used for auditing purposes, they are appropriate choices as benchmarks for CBS, but it is important to note that CBS was specifically designed to have a high accuracy for bias detection, whereas that was not necessarily an explicit intention of GerryFair or Multiaccuracy Boost.

### B.2 Explanation of the Additive Term ( ϵ t ⁢ r ⁢ u ⁢ e superscript italic-ϵ 𝑡 𝑟 𝑢 𝑒 \epsilon^{true} italic_ϵ start_POSTSUPERSCRIPT italic_t italic_r italic_u italic_e end_POSTSUPERSCRIPT ) for the True Log-Odds used in the Generative Model for the Semi-synthetic Data

For the evaluation simulations described in Section [4](#S4), when producing the true log-odds that are used to determine the outcomes and predicted values, we add a term to each row’s true log-odds of a value drawn from a Gaussian distribution $\epsilon_{i}^{true}\sim\mathcal{N}(0,\sigma_{true})$ where $\sigma_{true}=0.6$. We add this term to the true log-odds to ensure that when the true log-odds for the rows of $S_{bias}$ in the protected class are injected with $\mu_{suf}$, this results in a violation of the fairness definition for sufficiency.

For the remainder of this section we will focus on sufficiency scan for predictions, but our explanation below is applicable for sufficiency scan for recommendations as well. Sufficiency implies that the outcomes $Y$ are conditionally independent of membership in the protected class $A$ given the predictions $P$ and covariates $X$, that is, $Y\perp A\>|\>(P,X)$.
Assume that we have predictions that are independent of the outcome conditional on the covariates, $Y\perp P\>|\>X$. Since the outcome is independent of the predictions conditional on the covariates, the definition of sufficiency simplifies to $Y\perp A\>|\>X$. This simplification of sufficiency reduces sufficiency scans to finding the subgroup in the protected class with the biggest base rate difference from its corresponding subgroup in the non-protected class regardless of that subgroup’s predictions. Therefore, it is not evaluating sufficiency violations because these base rate differences are independent of the predictions. Consequentially, when there is *no* base rate difference between the protected and non-protected class conditional on the covariates, ($Y\perp A\>|\>X$), in order for sufficiency to be violated, $Y\not\perp A\>|\>(P,X)$, we must also have $Y\not\perp P\>|\>X$. This is formally stated in Theorem [B.1](#A2.Thmtheorem1).

###### Theorem B.1 .

To have violations of the sufficiency definition, $Y\not\perp A\>|\>(P,X)$, when there are no base rate differences between the protected class and non-protected class conditional on the covariates, $Y\perp A\>|\>X$, the predictions and outcomes must be conditionally dependent given the covariates, $Y\not\perp P\>|\>X$.

###### Proof.

Let us assume that (i) there are no base rate differences between protected and non-protected class conditional on the covariates, $Y\perp A\>|\>X$; (ii) outcomes are independent of the predictions conditional
on the covariates, $Y\perp P\>|\>X$; and (iii) violations of the sufficiency definition exist, $Y\not\perp A\>|\>(P,X)$. We will show that these three statements lead to a contradiction. First,
$(Y\perp P\>|\>X)$ and $(Y\perp A\>|\>X)$ together imply that $Y\perp(P,A)\>|\>X$. Furthermore, using the weak union axiom for conditional independence, $Y\perp(P,A)\>|\>X$ implies that $Y\perp A\>|\>(P,X)$, which contradicts (iii). Since these three statements cannot all be true, we know that no base rate differences (i) and violations of sufficiency (iii) together imply that the outcomes cannot be independent of the predictions conditional on the covariates, $Y\not\perp P\>|\>X$.
∎

To ensure that $Y\not\perp P\>|\>X$, the predictions $P$ must carry information about the outcomes $Y$ that is not carried in $X$. By adding the term $\epsilon_{i}^{true}$ to the true log-odds for each row, given that the predicted log-odds (and the corresponding predicted probabilities $P_{i}$ and binarized recommendations $P_{i,bin}$) and the outcomes $Y$ are both derived from the true log-odds, this ensures that $Y\not\perp P\>|\>X$ in the evaluation simulations because $P$ carries information about $Y$, in the form of the added row-wise terms (drawn from a Gaussian distribution), that are captured in $Y$, but are not captured in $X$.

###### Theorem B.1 .

###### Proof.

### B.3 Additional Evaluation Simulations

Figure: Figure 4: Average accuracy (with 95% CI) for biases and base rate shifts injected into subgroup $S_{bias}$ of the protected class, for CBS, GerryFair, and Multiaccuracy Boost, as a function of varying parameters $n_{bias}$ (top row) and $p_{bias}$ (bottom row). Left: increasing predicted log-odds by $\mu_{sep}=1$. Center: decreasing true log-odds by $\mu_{suf}=1$. Right: base rate difference $\delta=0.5$, for $\mu_{sep}=\mu_{suf}=0$.
Refer to caption: x4.png

Figure: Figure 5: Average accuracy (with 95% CI) for biases injected into subgroup $S_{bias}$ of the protected class, for CBS, GerryFair, and Multiaccuracy Boost, as a function of varying base rate difference $\delta$ between protected and non-protected class for subgroup $S_{bias}$. Left: increasing predicted log-odds by $\mu_{sep}=1$. Right: decreasing true log-odds by $\mu_{suf}=1$.
Refer to caption: x5.png

To evaluate [3](#S4.I1.i3) in Section [4](#S4), we modify the characteristics of $S_{bias}$, by varying $n_{bias}$ and $p_{bias}$ for three settings, when $\mu_{sep}=1$, $\mu_{suf}=1$, and $\delta=0.5$. For each setting, we perform two simulations: (1) by varying the number of attribute categories to choose attribute-values from ($n_{bias}$) between 1 and 4, when $p_{bias}=0.50$; and (2) by varying the probability ($p_{bias}$) of an attribute-value being included in $S_{bias}$ between 0 and 1, when $n_{bias}=2$. The results of these simulations are shown in Figure [4](#A2.F4). We observe that, when varying $n_{bias}$, CBS has similar accuracy results to the simulations shown in Figures [1](#S4.F1) and [2](#S4.F2), with separation scans and sufficiency scan for predictions having higher bias detection accuracy when $\mu_{sep}=1$, and sufficiency scans having higher bias detection accuracy when $\mu_{suf}=1$, as compared to competing methods across all settings of $n_{bias}$.
Interestingly, GerryFair and Multiaccuracy Boost have improved bias detection accuracy, approaching that of CBS, when $p_{bias}$ approaches 1 (i.e., more individuals in the protected class are included in $S_{bias}$), but perform poorly for low values of $p_{bias}$. This suggests that CBS is better at detecting smaller, more subtle subgroups $S_{bias}$ than the competing methods.

Additionally, we investigated the case where we have both an injected bias ($\mu_{sep}=1$ or $\mu_{suf}=1$) and a base rate shift $\delta$ in subgroup $S_{bias}$ for the protected class. We examined the extent to which positive and negative shifts $\delta$ either help or harm the detection accuracy of the various methods. Thus we run two separate sets of experiments with injected bias $\mu_{sep}=1$ and injected bias $\mu_{suf}=1$, while varying the base rate shift $\delta$ from -1 to +1 for each experiment. A positive $\delta$ means $S_{bias}$ in the protected class has a higher base rate, while a negative $\delta$ means $S_{bias}$ in the protected class has a lower base rate, as compared to $S_{bias}$ in the non-protected class.

In Figure [5](#A2.F5), we observe that the detection accuracy of the separation scans
monotonically increases with $\delta$. This relationship is particularly strong for the experiments with injected bias $\mu_{suf}=1$, in which the separation scans show near-perfect accuracy for large positive $\delta$ and near-zero accuracy for large negative $\delta$. These results are not surprising given the separation scans’ sensitivity to positive base rate differences for $S_{bias}$ in the protected class even when no injected bias is present (see Figure [2](#S4.F2) above).
We observe that the detection accuracy of the sufficiency scan for recommendations monotonically decreases with $\delta$. This
relationship is particularly strong for the experiments with injected bias $\mu_{sep}=1$, in which the sufficiency scan for recommendations shows near-perfect accuracy for large negative $\delta$ and near-zero accuracy for large positive $\delta$. Again, these results are not surprising given the sufficiency scan for recommendations’ sensitivity to negative base rate differences for $S_{bias}$ in the protected class even when no injected bias is present (see Figure [2](#S4.F2) above). Finally, we observe that the sufficiency scan for predictions maintains high accuracy for both $\mu_{sep}=1$ and $\mu_{suf}=1$ regardless of the base rate difference $\delta$ for $S_{bias}$ in the protected class.

### B.4 Robustness Analyses of Evaluation Simulations for Parameters σ t ⁢ r ⁢ u ⁢ e subscript 𝜎 𝑡 𝑟 𝑢 𝑒 \sigma_{true} italic_σ start_POSTSUBSCRIPT italic_t italic_r italic_u italic_e end_POSTSUBSCRIPT and σ p ⁢ r ⁢ e ⁢ d ⁢ i ⁢ c ⁢ t subscript 𝜎 𝑝 𝑟 𝑒 𝑑 𝑖 𝑐 𝑡 \sigma_{predict} italic_σ start_POSTSUBSCRIPT italic_p italic_r italic_e italic_d italic_i italic_c italic_t end_POSTSUBSCRIPT

Figure: Figure 6: Average accuracy (with 95% CI) for biases and base rate shifts injected into subgroup $S_{bias}$ of the protected class, for CBS, GerryFair, and Multiaccuracy Boost, as a function of varying parameter $\sigma_{predict}$. Left: increasing predicted log-odds by $\mu_{sep}=1$. Center: decreasing true log-odds by $\mu_{suf}=1$. Right: base rate difference $\delta=0.5$, for $\mu_{sep}=\mu_{suf}=0$.
Refer to caption: x6.png

In this section, we examine the robustness of our results in Section [4](#S4) by varying the parameters $\sigma_{predict}$ and $\sigma_{true}$ from their default values of 0.2 and 0.6 respectively.

First, we examine the impact of varying $\sigma_{predict}$. Recall that each predicted log-odds is drawn from a Gaussian distribution centered at the true log-odds, with standard deviation $\sigma_{predict}$. Thus $\sigma_{predict}$ can be interpreted as the average amount of random error in the classifier’s predictions as compared to the true log-odds values. We run three separate sets of experiments where we alter $S_{bias}$ in the protected class by injecting a bias of $\mu_{sep}=1$, injecting a bias of $\mu_{suf}=1$, and creating a base rate difference of $\delta=0.5$ respectively, while varying $\sigma_{predict}$ between 0 and 2. Accuracies are averaged over 100 semi-synthetic datasets for each experiment. The experiments where $\mu_{sep}=1$ and $\mu_{suf}=1$ analyze the robustness to $\sigma_{predict}$ of the evaluation simulations for [1](#S4.I1.i1), whereas the experiments where $\delta=0.5$ analyze the robustness to $\sigma_{predict}$ of the evaluation simulations for [2](#S4.I1.i2).

In Figure [6](#A2.F6), we observe that large amounts of noise $\sigma_{predict}$ harm the accuracy of the separation scans for injected biases $\mu_{suf}=1$ which shift the true log-odds in subgroup $S_{bias}$ for the protected class, as well as reducing their detection of base rate shifts $\delta>0$ in subgroup $S_{bias}$ for the protected class. Most interestingly, when $\sigma_{predict}$ is large, we see a substantial reduction in accuracy for the sufficiency scans for injected biases $\mu_{sep}=1$ which shift the predicted log-odds in subgroup $S_{bias}$ for the protected class. We believe that the combination of noisy predictions and a relatively small dataset size is causing CBS’s logistic regression model (used to estimate $\hat{I}$) to underestimate the strength of the relationship between the predictions $P_{i}$ (or recommendations $P_{i,bin}$) and the outcomes $Y_{i}$ for the non-protected class. Thus, when we have a large shift in $P_{i}$ in subgroup $S_{bias}$ for the protected class, the model predicts a much smaller shift in $\mathbb{E}[Y_{i}\>|\>X_{i},P_{i}]$. As a result, the difference between the expected $\hat{I}_{i}$ and true $I_{i}$ values and the corresponding CBS scores for the sufficiency scans are reduced, leading to reduced detection accuracy.

Figure: Figure 7: Average accuracy (with 95% CI) for biases and base rate shifts injected into subgroup $S_{bias}$ of the protected class, for CBS, GerryFair, and Multiaccuracy Boost, as a function of varying parameter $\sigma_{true}$. Left: increasing predicted log-odds by $\mu_{sep}=1$. Center: decreasing true log-odds by $\mu_{suf}=1$. Right: base rate difference $\delta=0.5$, for $\mu_{sep}=\mu_{suf}=0$.
Refer to caption: x7.png

Second, we examine the impact of varying $\sigma_{true}$. Recall that each individual’s true log-odds is a deterministic (linear) function of their covariate values $X_{i}$ plus a term, $\epsilon_{i}^{true}$, drawn from a Gaussian distribution centered at 0 with a standard deviation of $\sigma_{true}$. Thus the parameter $\sigma_{true}$ represents the variation between individuals’ true log-odds based on characteristics other than the covariate values $X_{i}$ used by CBS. Moreover, since each individual’s predicted log-odds is drawn from a Gaussian distribution centered at the true log-odds, these characteristics are assumed to be known and incorporated into the classifier, thus creating the dependency $Y\not\perp P\>|\>X$ when $\sigma_{true}>0$. In other words, $\sigma_{true}$ represents the average amount of signal in the predictions $P$ (for predicting the outcome $Y$) that is not already present in the covariates $X$.
We run three separate sets of experiments where we alter $S_{bias}$ in the protected class by injecting a bias of $\mu_{sep}=1$, injecting a bias of $\mu_{suf}=1$, and creating a base rate difference of $\delta=0.5$ respectively, while varying $\sigma_{true}$ between 0 and 2 for each experiment. Accuracies are averaged over 100 semi-synthetic datasets for each experiment. The experiments where $\mu_{sep}=1$ and $\mu_{suf}=1$ analyze the robustness to $\sigma_{true}$ of the evaluation simulations for [1](#S4.I1.i1), whereas the experiments where $\delta=0.5$ analyze the robustness to $\sigma_{true}$ of the evaluation simulations for [2](#S4.I1.i2).

In Figure [7](#A2.F7), we observe that small values of $\sigma_{true}$ harm the accuracy of the separation scans for injected bias $\mu_{suf}=1$ while making them more likely to detect base rate shifts $\delta>0$ in subgroup $S_{bias}$ for the protected class.
Most interestingly, when $\sigma_{true}$ is small, we see a substantial reduction in accuracy for the sufficiency scans for injected bias $\mu_{sep}=1$. This reduced performance for $\sigma_{true}\approx 0$ follows from our argument in Section [B.2](#A2.SS2) above: $\sigma_{true}=0$ implies $Y\perp P\>|\>X$, and if we also have no base rate difference between the protected and non-protected classes ($Y\perp A\>|\>X$), this implies
$Y\perp A\>|\>P,X$. In other words, even if a bias is injected into the predicted probabilities (and recommendations) in subgroup $S_{bias}$ for the protected class, the sufficiency-based definition of fairness is not violated, and thus the injected bias cannot be accurately detected.

### B.5 Estimates of Compute Power

For all of the experiments in Section [4](#S4), Appendix [B.3](#A2.SS3), and Appendix [B.4](#A2.SS4), we used 15 shared, university compute servers running CentOS with 16-64 cores and 16-256 GB of memory. Each server performed 15-120 runs of CBS concurrently, and ran for approximately 9 days. We estimate that, to run all of the simulations (1,504 CBS runs in total) for a single data set, this would take approximately 32.5 hours. Lastly, to run an individual CBS scan for the COMPAS data (150 iterations), it takes on average approximately 90 seconds.

## Appendix C Case Study of COMPAS Appendices

### C.1 Additional Information about Preprocessing of COMPAS Data

We follow many of the processing decisions made in the initial ProPublica analysis, including removing traffic offenses and defining recidivism as a new arrest within two years of the initial arrest for a defendant (Larson et al., ; Larson and Roswell, ). After preprocessing the initial data set, we have 6,172 defendants, their gender, race, age (Under 25 or 25+), charge degree (Misdemeanor or Felony), prior offenses (None, 1 to 5, or Over 5), predicted recidivism risk score (1-10), and whether they were re-arrested within two years of the initial arrest.

### C.2 Full Results of COMPAS Case Study

**Table 4: Full table of results for COMPAS case study. Each of the four variants of CBS was run using each observed attribute value as the protected class. Detected subgroup $S^{\ast}$ of the protected class and corresponding (comparison) subgroup of the non-protected class; numbers of defendants for each subgroup are shown in parentheses. All runs with log-likelihood ratio score $F(S^{\ast})>0$ are shown, sorted in descending order by score for each method. Separation scan for predictions: “observed rate” is average predicted probability of reoffending, $\mathbb{E}[P_{i}]$, for defendants who did not reoffend ($Y_{i}=0$). Separation scan for recommendations: “observed rate” is false positive rate, i.e., proportion of individuals predicted as “high risk” ($P_{i,bin}=1$) for defendants who did not reoffend ($Y_{i}=0$). Sufficiency scan for predictions: “observed rate” is proportion of reoffending individuals ($Y_{i}=1$), controlling for predicted risk. Sufficiency scan for recommendations: “observed rate” is positive predictive value, i.e., proportion of reoffending individuals ($Y_{i}=1$) for defendants who were predicted as “high risk” ($P_{i,bin}=1$). Bolded scores are statistically significant with p-value <.05 measured by permutation testing, as described in Appendix [A.3](#A1.SS3).**
| Scan Type | Protected Class Attribute Value | Detected Subgroup | Comparison Subgroup | Score | Observed Rate (Detected) | Observed Rate (Comparison) |
| --- | --- | --- | --- | --- | --- | --- |
|  | Under age 25 | Defendants under age 25 arrested on felony charges (403) | Defendants age 25+ arrested on felony charges (1583) | 114.1 | 0.52 | 0.39 |
|  | 6+ priors | All defendants with 6+ priors (349) | All defendants with 0-5 priors (3014) | 83.1 | 0.54 | 0.38 |
|  | Black | Black male defendants (1168) | Non-Black male defendants (1433) | 41.9 | 0.45 | 0.35 |
| Separation Scan for Predictions | Female | Female defendants with 6+ priors (40) | Male defendants with 6+ priors (309) | 25.3 | 0.59 | 0.54 |
|  | 1 to 5 priors | Defendants under age 25 with 1 to 5 priors (227) | Defendants under age 25 with 0 or 6+ priors (366) | 3.23 | 0.54 | 0.49 |
|  | Felony | White female defendants arrested on felony charges (139) | White female defendants arrested on misdemeanor charges (173) | 2.40 | 0.42 | 0.34 |
|  | Male | Asian male defendants (22) | Asian female defendants (1) | 0.62 | 0.30 | 0.22 |
|  | Native American | All Native American defendants (6) | All non-Native American defendants (3357) | 0.15 | 0.49 | 0.39 |
|  | Under age 25 | Defendants under age 25 arrested on felony charges (403) | Defendants age 25+ arrested on felony charges (1583) | 149.2 | 0.55 | 0.29 |
|  | 6+ priors | All defendants with 6+ priors (349) | All defendants with 0-5 priors (3014) | 125.5 | 0.66 | 0.26 |
|  | Black | Black male defendants (1168) | Non-Black male defendants (1433) | 100.9 | 0.44 | 0.19 |
|  | Female | Female defendants with 6+ priors (40) | Male defendants with 6+ priors (309) | 46.9 | 0.80 | 0.65 |
| Separation Scan for Recommendations | Male | Asian and Hispanic male defendants (286) | Asian and Hispanic female defendants (57) | 22.3 | 0.21 | 0.05 |
|  | 1 to 5 priors | Defendants under age 25 with 1 to 5 priors (227) | Defendants under age 25 with 0 or 6+ priors (366) | 12.5 | 0.64 | 0.47 |
|  | Felony | White female defendants arrested on felony charges (139) | White female defendants arrested on misdemeanor charges (173) | 9.40 | 0.38 | 0.21 |
|  | White | White female defendants under age 25 with no priors (31) | Non-white female defendants under age 25 with no priors (70) | 1.98 | 0.71 | 0.56 |
|  | Misde-meanor | Native American defendants with 1 to 5 priors arrested on misdemeanor charges (2) | Native American defendants with 1 to 5 priors arrested on felony charges (1) | 1.67 | 1.00 | 0.00 |
|  | Age 25+ | Asian defendants age 25+ arrested on felony charges (10) | Asian defendants under age 25 arrested on felony charges (1) | 0.75 | 0.20 | 0.00 |
|  | Native American | All Native American defendants (6) | All non-Native American defendants (3357) | 0.20 | 0.50 | 0.30 |
|  | No priors | All defendants with no priors (2085) | All defendants with 1+ priors (4087) | 111.5 | 0.29 | 0.54 |
|  | Age 25+ | Male defendants age 25+ with 0-5 priors (2867) | Male defendants under age 25 with 0-5 priors (1041) | 92.6 | 0.35 | 0.59 |
|  | Male | Male Native American defendants of age 25+ (7) | Female Native American defendants of age 25+ (2) | 31.2 | 0.14 | 1.00 |
|  | Female | Female defendants under age 25 (246) | Male defendants under age 25 (1101) | 18.7 | 0.38 | 0.60 |
| Sufficiency Scan for Predictions | Misde-meanor | Female defendants arrested on misdemeanor charges (491) | Female defendants arrested on felony charges (684) | 3.51 | 0.26 | 0.41 |
|  | Asian | Asian defendants arrested on misdemeanor charges (12) | Non-Asian defendants arrested on misdemeanor charges (2190) | 3.20 | 0.00 | 0.38 |
|  | White | White defendants under age 25 (347) | Non-white defendants under age 25 (1000) | 2.36 | 0.49 | 0.58 |
|  | Black | Black female defendants (549) | Non-Black female defendants (626) | 2.22 | 0.37 | 0.34 |
|  | 1 to 5 priors | Black defendants of age 25+ with 1 to 5 priors (1038) | Black defendants of age 25+ with 0 or 6+ priors (1328) | 2.18 | 0.42 | 0.55 |
|  | Hispanic | All Hispanic defendants (509) | All non-Hispanic defendants (5663) | 0.27 | 0.37 | 0.46 |
|  | Native American | All Native American defendants (11) | All non-Native American defendants (6161) | 0.17 | 0.45 | 0.46 |
|  | Age 25+ | Male defendants of age 25+ with 0-5 priors (772) | Male defendants under age 25 with 0-5 priors (641) | 52.9 | 0.52 | 0.67 |
|  | No priors | All defendants with no priors (553) | All defendants with 1+ priors (2198) | 51.0 | 0.46 | 0.67 |
|  | Female | Female defendants with no priors (150) | Male defendants with no priors (403) | 35.3 | 0.33 | 0.50 |
|  | Misde-meanor | Male defendants with 0-5 priors arrested on misdemeanor charges (398) | Male defendants with 0-5 priors arrested on felony charges (1015) | 28.2 | 0.52 | 0.61 |
| Sufficiency Scan for Recommendations | 1 to 5 priors | Male defendants of age 25+ with 1 to 5 priors (595) | Male defendants of age 25+ with 0 or 6+ priors (981) | 26.8 | 0.54 | 0.70 |
|  | Male | Male Native American defendants of age 25+ (4) | Female Native American defendants of age 25+ (2) | 14.1 | 0.25 | 1.00 |
|  | Hispanic | All Hispanic defendants (141) | All non-Hispanic defendants (2610) | 2.40 | 0.56 | 0.63 |
|  | 6+ priors | Asian defendants with 6+ priors (1) | Asian defendants with 0-5 priors (6) | 0.41 | 0.00 | 0.83 |
|  | White | White female defendants under age 25 (57) | Non-white female defendants under age 25 (110) | 0.40 | 0.39 | 0.47 |
|  | Black | Black defendants of age 25+ with 0-5 priors (581) | Non-Black defendants of age 25+ with 0-5 priors (404) | 0.34 | 0.50 | 0.52 |

### C.3 Considerations and Limitations of COMPAS Data and Fairness Definitions in our COMPAS Case Study

Following the initial investigation by ProPublica about fairness issues in COMPAS risk predictions (Angwin et al., ), ProPublica’s COMPAS dataset has been used as a benchmark in the fairness literature. While we use the COMPAS data because of its familiarity and supporting research, we also note the value of alternative framings of the evaluation of automated decision support tools in the criminal justice systems, such as examining the risks that the system poses to defendants rather than the risk of the defendants to public safety Mitchell et al. (); Meyer et al. (); Green (). Beyond the implications of the traditional framing of pre-trial risk assessment tools, there have been specific critiques of the COMPAS data that range from questioning the accuracy of the sensitive attributes (specifically race), noting missing features in the ProPublica dataset that the COMPAS creators claim are important for score calculations, and most importantly, a lack of evaluation of the biases that exist in the outcome variable of whether a defendant is rearrested within two years of arrest.(^2^22See, for example, Fabris et al., “Algorithmic fairness datasets: the story so far”, *Data Mining and Knowledge Discovery* 36(6), 2074-2152, 2022.) Given that certain types of individuals are arrested at a higher rate than others, the outcome variable of re-arrest most likely under- and over-represents certain subpopulations of defendants.

In our COMPAS case study, for the separation scans, we search for subgroups of the protected class with the most significant *increase*, either in the probabilistic predictions or in the probability that the binarized recommendation equals 1, conditional on the defendant’s covariates. Moreover, we perform value-conditional scans, focusing specifically on the subset of defendants who did not reoffend ($Y_{i}=0$).
For the separation scan for recommendations, this results in CBS detecting subgroups of the protected class for whom the *false positive rate* is most significantly increased. For the sufficiency scans, we search for subgroups of the protected class with the most significant *decrease* in the observed rate of reoffending, conditional on the defendant’s covariates and their COMPAS prediction or recommendation. For the sufficiency scan for recommendations, we also perform a value-conditional scan. We focus specifically on the subset of defendants who were predicted to be “high risk” by COMPAS ($P_{i,bin}=1$) because this labeling could negatively impact the defendant, e.g., by decreasing their likelihood of pre-trial release. This results in CBS detecting subgroups of the protected class for whom the *false discovery rate* is most significantly increased. These fairness definitions neglect bias detection for defendants who reoffend (for separation scans) and defendants who are not flagged as high-risk (for sufficiency scan for recommendations). These choices were made to ensure our ability to verify our findings based on previous research on COMPAS which commonly focus on similar fairness violations to those used in our case study. With that said, we strongly encourage auditing for predictive biases that affect reoffending defendants and low-risk defendants as well, if using CBS to audit an algorithmic risk assessment tool in practice. For example, auditing for the increased probability of being flagged as high-risk for reoffending defendants could help to uncover subpopulations that are over-prosecuted in comparison to other populations of reoffending defendants. Therefore, expanding the fairness definitions used to audit pre-trial risk assessment tools for biases could have beneficial findings.

## Peer Reviews

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: 1. How difficult does it appear to be to extend this framework to a multi-label setting?
2. How computationally expensive does this method get when scaling the number of groups to be evaluated over? As it stands it appears that the maximum number of intersectional groups is 4 in these experiments?
soundness: 3
strengths: - The method proposed is relatively simple to implement and rigorously grounded in the hypothesis testing literature
- The method is flexible for the commonly discussed fairness metrics
- The synthetic experiments are designed well to demonstrate the efficacy of the method in different scenarios and metrics
summary: This study develops a new statistical test for identifying bias in prediction models across four different axes based on both the probabilistic outputs and the binarized classifications. This test builds upon likelihood ratio tests developed in the spatial and subset scan statistics literature. At it's core this test is examining when the quantity of interest deviates significantly from its expectation across multiple intersectional subgroups. The test is then evaluated on a semi synthetic dataset based on COMPAS and then COMPAS itself. Demonstrating its ability to identify bias and the most significantly impacted groups.
weaknesses: - The methods that are compared against seem to be quite old and I would be interested to see how they compare to newer methods in the literature (e.g. [1])
- More real world dataset studies would improve the study (e.g. folktables [2])
- The writing is verbose at times and could benefit from being more concise. This is especially true in Section 3 when describing the methods.

[1] Cherian, John J., and Emmanuel J. Candès. "Statistical inference for fairness auditing." Journal of Machine Learning Research 25.149 (2024): 1-49.
[2] https://github.com/socialfoundations/folktables

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 1
questions: Could the authors please address my concerns in the above section?
soundness: 2
strengths: - **[Problem Importance]** The authors study an important problem.

- **[Practicality]** The proposed method can accommodate a large number of fairness definitions that prior works are not able to accommodate.
summary: The authors investigate the problem of intersectional bias in classification and develop a novel search method for identifying intersectional bias. The authors compare their method to other auditing methods on semi-synthetic data.
weaknesses: - **[Clarity]** Several important aspects of the paper are not articulated clearly. In particular, I found it difficult to follow the authors’ experimental design, a few examples include:
     - Section 4: What is a “row”? The authors refer to specific rows or “row $i$” without defining this term. Is the row a particular data point, or is it a row of the covariates?
     - When defining the true log-odds in their semi-sythetic data the authors say, “We use these weights to produce the true log-odds of a positive outcome $(Y_i = 1)$ for each row $i$ by a linear combination of the attribute values with these weights.”
This statement is quite vague and does not rigorously outline how the log-odds are computed. The authors denote the true log-odds as $L_i^{\text{true}}$; perhaps a definition could be given for this quantity.


- **[Narrative vs Experiments]** There is a strong disconnect between the authors' results and the discussion/motivation of the paper. For example, the authors spend substantial time going over different fairness metrics and discussing the applicability of their method to each metric. However, no experimental results are shown for any such metrics. The authors simply shift the predicted probabilities, or true probabilities, of some individuals by some value and measure whether their algorithm, or the baseline, can identify those individuals. I would have liked to see some results showing the accuracy of the authors' method as a function of subgroup unfairness under a particular metric. 

- **[Synthetic Data]** Due to the way in which the synthetic data is constructed, I find it difficult to appreciate some of the authors’ results. In particular, the authors randomly select sensitive attributes among all attributes in the data and change the true labels to have a noisy linear relationship with the features. Both choices destroy the innate relationships between features, sensitive attributes, and true labels, which cause unfairness in the base datasets (e.g., COMPAS). Further, it is not clear to me why we need synthetic data in the first place. The authors are working with two datasets that are known to possess innate bias both at the group level and the subgroup level; this begs the question as to why we are not shown results comparing the authors' method to SotA methods on these datasets without any synthetic modifications.


- **[Simplistic Experiments]** In addition to the issues with synthetic data above, the authors only show experiments for two datasets and two classifier types.

- **[Evaluation Metric]** When comparing to the baseline, the authors measure the IOU of the predicted subgroups $S^*$ and the subgroups with injected bias $S_{\text{bias}}$, given on line 371. Without knowing whether or not the subgroups in $S_{\text{bias}}$ are disadvantaged (and to what degree), it is difficult to appreciate the use of this metric. 

- **[Comparisons to Baselines]** When comparing their method to baselines, e.g., in Figure 1, the authors find that their method is only superior to baselines for relatively large amounts of bias. Moreover, in results such as Figure 2, it seems that the authors’ methods can achieve extremely poor accuracy depending on the type of bias present (negative or positive delta). Without apriori knowing the type of bias, it may be difficult to meaningfully apply these methods in practice. Lastly, the results in each of the aforementioned, and similar plots are difficult to interpret because we cannot understand how much bias a specific value of $\delta$ or $\mu$ corresponds to. It would be helpful to see the level of bias converted into actual fairness metrics.

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 2
questions: I have a few questions for the authors.

* q1) Could the authors clarify my doubts regarding W1)? In particular, what are the authors' considerations regarding the emergence of the Yule effect?
* q2) From Figure 3, it seems to me that the final results are heavily affected by which is the protected class specified.  E.g., if we specify the "Black defendants" as the starting protected class, the subgroup with the highest F score  (on Separation Scan for Recommendations) is "Black Male Defendants", while if we set "Male Defendants" as the starting class, the subgroup with the highest F score is "Male Asian and Hispanic Defendants". Even if I see why this occurs (in the first case, we refer to non-Black as the reference group, and in the second case, we refer to Females as the reference group), I would argue that this affects the ability of CBS to assess the intersectional biases occurring on a dataset. Can you comment on my observation further?
soundness: 2
strengths: The main strengths of the paper are:

S1) the motivation of the methodology is relevant, as identifying intersectional biases (in a tractable manner) is an open issue in the fairness literature;

S2) the empirical evaluation supports the effectiveness of the method; 

S3) the algorithmic procedure for detecting the most significant subgroup seems novel.
summary: The paper presents a novel approach to auditing and detecting fairness biases in predictive models. The method, called Conditional Bias Scan (CBS), allows for identifying the subgroup with the most significant bias and comparing it with the equivalent subgroup in the non-protected class. Empirical evaluation suggests the effectiveness of the approach.
weaknesses: The main shortcomings of the current version of the paper are:


W1) I think a few arguments should be taken into account and need further clarification:
* in [Ruggieri et al., 2023], the authors show that algorithmic fairness objectives are not compositional, i.e., even if the classifier is fair on some of the regions of the input space, due to the emergence of Yule’s effect, the overall system is not necessarily fair. This could hinder CBS's ability to evaluate the overall fairness of the system.
* in lines 183-184, the authors consider propensity score estimates for $Pr(A=1|X)$. This assumes (implicitly) that the protected group can be seen as a treatment variable, while this has been largely debated in the literature (see e.g., for gender [Hu and Kohler-Hausman, 2020]). A proper discussion of this aspect should be provided.

W2) The overall presentation can be improved. For instance, I find the empirical evaluation in section 4 quite dense and difficult to follow.  E.g., starting the whole section from lines 310-319 can help the reader better understand the purpose of the experimental evaluation and help describe the evaluation setup (e.g., datasets, baselines, hyperparameters and metrics).  

W3) The empirical evaluation can be improved. Currently, the evaluation is limited to the COMPAS and German Credit datasets, which are rather small scale. I would argue that testing CBS on larger-scale datasets such as $\texttt{folktables}$ [Ding et al., 2023] and $\texttt{WCLD}$ [Ash et al, 2023] would make the results more compelling. Moreover, I do think CBS can be exploited to audit different classifiers and their relative biases, even though such an experiment is not performed.


[Hu and Kohler-Hausman, 2019] - Hu, Lily, and Issa Kohler-Hausmann. "What's sex got to do with machine learning?." In Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency, pp. 513-513. 2020.

[Ruggieri et al., 2023] - Ruggieri, Salvatore, Jose M. Alvarez, Andrea Pugnana, Laura State and Franco Turini. "Can we trust fair-AI?." In Proceedings of the AAAI Conference on Artificial Intelligence, vol. 37, no. 13, pp. 15421-15430. 2023.

[Ding et al., 2021] - Ding, Frances, Moritz Hardt, John Miller, and Ludwig Schmidt. "Retiring adult: New datasets for fair machine learning." Advances in neural information processing systems 34 (2021): 6478-6490.

[Ash et al., 2023] - Ash, Elliott, Naman Goel, Nianyun Li, Claudia Marangon, and Peiyao Sun. "WCLD: curated large dataset of criminal cases from Wisconsin circuit courts." Advances in Neural Information Processing Systems 36 (2023): 12626-12643.

---

confidence: 2
contribution: 3
initial_rating: 5
presentation: 2
questions: 1. How does CBS handle scenarios with continuous covariates without discretization, and how does it address the potential loss of valuable information during this process?
2. What are the implications of using different models for estimating conditional expectations on the detection of biases? Beyond modeling the COMPAS data, is there additional evidence of real-world datasets to support the effectiveness of this method? See also weakness 2. 
3. Could you clarify the distinction between auditing the COMPAS dataset and the model itself? The explanation in Section 5 is not entirely clear.
4. Regarding Figure 3: Does the framework detect the entire group of defendants under the age of 25? What is the role of the conditional variable C in the null hypothesis in this case?
5. Consider making the tables more consistent in terms of formatting and presentation for easier comparison.
soundness: 2
strengths: 1. The paper provides a framework for auditing intersectional biases, a crucial area often overlooked in fairness assessments (detection of gerrymandering). 
2. The proposed method can accommodate different group fairness metrics and can effectively scan numerous subgroups.
summary: The authors address the challenge of auditing machine learning models for intersectional biases (fairness gerrymandering). They introduce a methodology called Conditional Bias Scan (CBS) for detecting biases that affect specific subgroups, which may arise from intersectional factors (membership in two or more protected classes) or contextual factors (decision situations). The CBS methodology involves four stages: (1) initializing the event variable I, protected class A, covariates X, and conditional variable C based on the input parameters and chosen fairness definition; (2) estimating the expected value of I under the null hypothesis; (3) using a multidimensional subset scan to identify subgroups that systematically deviate from the expected values computed in step (2) and selecting the most significant ones; and (4) assessing the statistical significance of the detected subgroups. The paper includes a comprehensive experimental evaluation to validate the approach.
weaknesses: 1. The reliability of the estimation of expectations I under the null hypothesis depends on having well-specified models for estimating the propensity scores of the protected class. 
2. The paper is quite dense and challenging to follow. It would benefit from providing more intuitive explanations or examples to illustrate why the overall method is effective in real-world scenarios. This would help readers better understand the practical implications and the rationale behind the approach.