,

# Certifying Robustness to Programmable Data Bias in Decision Trees

Anna P. Meyer
Department of Computer Sciences
University of Wisconsin - Madison
Madison, WI 53706
<EMAIL_ADDRESS>
Use footnote for providing further information about author (webpage,
alternative address)— _not_ for acknowledging funding agencies.

###### Abstract

Datasets can be biased due to societal inequities, human biases, under-
representation of minorities, etc. Our goal is to _certify_ that models
produced by a learning algorithm are _pointwise-robust_ to potential dataset
biases. This is a challenging problem: it entails learning models for a large,
or even infinite, number of datasets, ensuring that they all produce the same
prediction. We focus on decision-tree learning due to the interpretable nature
of the models. Our approach allows programmatically specifying _bias models_
across a variety of dimensions (e.g., missing data for minorities), composing
types of bias, and targeting bias towards a specific group. To certify
robustness, we use a novel symbolic technique to evaluate a decision-tree
learner on a large, or infinite, number of datasets, certifying that each and
every dataset produces the same prediction for a specific test point. We
evaluate our approach on datasets that are commonly used in the fairness
literature, and demonstrate our approach’s viability on a range of bias
models.

##  1 Introduction

The proliferation of machine-learning algorithms has raised alarming questions
about fairness in automated decision-making [barocas-hardt-narayanan]. In this
paper, we focus our attention on bias in training data. Data can be biased due
to societal inequities, human biases, under-representation of minorities,
malicious data _poisoning_ , etc. For instance, historical data can contain
human biases, e.g., certain individuals’ loan requests get rejected, although
(if discrimination were not present) they should have been approved, or women
in certain departments are consistently given lower performance scores by
managers.

Given biased training data, we are often unable to de-bias it because we do
not know which samples are affected. This paper asks, _can we certify (prove)
that our predictions are robust under a given form and degree of bias in the
training data?_ We aim to answer this question without having to show which
data are biased (i.e., poisoned). Techniques for certifying poisoning
robustness (_i_) focus on specific poisoning forms, e.g., label-flipping
[rosenfeld-randomized], or (_ii_) perform certification using defenses that
create complex, uninterpretable classifiers, e.g., due to randomization or
ensembling [jia2021intrinsic, levine2020deep, rosenfeld-randomized]. To
address limitation (_i_), we present _programmable bias definitions_ that
model nuanced biases in practical domains. To address (_ii_), we target
_existing_ decision-tree learners—considered interpretable and desirable for
sensitive decision-making [Rudin2019Why]—and exactly certify their robustness,
i.e., provide proofs that the bias in the data will not affect the outcome of
the trained model on a given point.

We begin by presenting a _language_ for programmatically defining _bias
models_. A bias model allows us to flexibly specify what sort of bias we
suspect to be in the data, e.g., up to $n\%$ of the women _may have_ wrongly
received a negative job evaluation. Our bias-model language is generic,
allowing us to _compose_ simpler bias models into more complex ones, e.g., up
to $n\%$ of the women may have wrongly received a negative evaluation _and_ up
to $m\%$ of Black men’s records may have been completely missed. The choice of
bias model depends on the provenance of the data and the task.

After specifying a bias model, our goal is to certify _pointwise robustness to
data bias_ : Given an input $x$, we want to ensure that no matter whether the
training data is biased or not, the resulting model’s prediction for $x$
remains the same. Certifying pointwise robustness is challenging. One can
train a model for every perturbation (as per a bias model) of a dataset and
make sure they all agree. But this is generally not feasible, because the set
of possible perturbations can be large or infinite. Recall the bias model
where up to $n\%$ of women may have wrongly received a negative label. For a
dataset with 1000 women and $n=1\%$, there are more than $10^{23}$ possible
perturbed datasets.

To perform bias-robustness certification on decision-tree learners, we employ
_abstract interpretation_ [cousot1977abstract] to symbolically run the
decision-tree-learning algorithm on a large or infinite set of datasets
simultaneously, thus learning a _set_ of possible decision trees, represented
compactly. The crux of our approach is a technique that lifts operations of
decision-tree learning to symbolically operate over a _set of datasets_
defined using our bias-model language. As a starting point, we build upon
Drews et al.’s [drews-pldi] demonstration of poisoning-robustness
certification for the simple bias model where an adversary may have added fake
training data. Our approach completely reworks and extends their technique to
target the bias-robustness problem and handle complex bias models, including
ones that may result in an infinite number of datasets.

Figure 1: A simple, hypothetical running example

#### Contributions

We make three contributions: (1) We formalize the bias-robustness-
certification problem and present a language to compositionally define bias
models. (2) We present a symbolic technique that performs decision-tree
learning on a set of datasets defined by a bias model, allowing us to perform
certification. (3) We evaluate our approach on a number of bias models and
datasets from the fairness literature. Our tool can certify pointwise
robustness for a variety of bias models; we also show that some datasets have
_unequal robustness-certification rates_ across demographics groups.

#### Running example

Consider the example in Fig. 1; our goal is to classify who should be hired
based on a test score. A standard decision-tree-learning algorithm would
choose the split (predicate) $\emph{score}\leqslant 3$, assuming we restrict
tree depth to 1. As shown in Fig. 1 (middle), the classification depends on
the data split; e.g., on the right hand side, we see that a person with
$\emph{score}>3$ is accepted, because the proportion (“probability”) of the
data with positive labels and $\emph{score}>3$ is $4/5$ ($>1/2$).

Now suppose that our bias model says that up to one Black person in the
dataset may have received a wrongful rejection. Our goal is to show that even
if that is the case, the prediction of a new test sample $x$ will not change.
As described above, training decision trees for all possible modified datasets
is generally intractable. Instead, we symbolically learn a set of possible
decision trees compactly, as illustrated in Fig. 1 (right). In this case the
learning algorithm always chooses $\emph{score}\leqslant 3$ (generally, our
algorithm can capture all viable splits). However, the proportion of labels on
either branch varies. For example, on the right, if the highlighted sample is
wrongly labeled, then the ratio changes from $0.8$ to $1$. To efficiently
perform this calculation, we lift the learning algorithm’s operations to
_interval arithmetic_ and represent the probability as $[0.8,1]$. Given a new
test sample $x=\langle$_race_ =Black, _score_ =7$\rangle$, we follow the right
branch and, since the interval is always larger than 0.5, we certify that the
algorithm is robust for $x$. In general, however, due to the use of
abstraction, our approach may fail to find tight intervals, and therefore be
unable to certify robustness for all robust inputs.

##  2 Related work

#### Ties to poisoning

Our dataset bias language captures existing definitions of _data poisoning_ ,
where an attacker is assumed to have maliciously modified training data.
Poisoning has been studied extensively. Most works have focused on attacks
[biggio2012poisoning, cheng2018queryefficient, li_dt_instability,
shafahi2018poison, turney-instability, xiao-label-flipping, zhang-label-
flipping] or on training models that are empirically less vulnerable
(defenses) [andriushchenko-stumps, chen-robust, dwyer_dt_instability, paudice-
label-sanitation, rosenfeld-randomized, steinhardt-certified]. Our work
differs along a number of dimensions: (1) We allow programmatic, custom,
composable definitions of bias models; notably, to our knowledge, no other
work in this space allows for _targeted_ bias, i.e., restricting bias to a
particular subgroup. (2) Our work aims to certify and quantify robustness of
an existing decision-tree algorithm, not to modify it (e.g., via bagging or
randomized smoothing) to improve robustness [jia2021intrinsic, levine2020deep,
rosenfeld-randomized].

Statistical defenses show that a learner is robust _with high probability_ ,
often by modifying a base learner using, e.g., randomized smoothing
[rosenfeld-randomized], outlier detection [steinhardt-certified], or bagging
[jia2021certified, jia2021intrinsic]. Non-statistical certification (including
abstract interpretation) has mainly focused on _test-time_ robustness, where
the vicinity (e.g., within an $\ell_{p}$ norm) of an input is proved to
receive the same prediction [anderson-neuralnets-robustness, gehr-neuralNet-
robustness, ranzato_abstract, singh-neuralNet-robustness, tornblom-abstract,
albarghouthi-book]. Test-time robustness is a simpler problem than our _train-
time_ robustness problem because it does not have to consider the mechanics of
the learner on sets of datasets. The only work we know of that certifies
train-time robustness of decision trees is by Drews et al. [drews-pldi] and
focuses on poisoning attacks where an adversary _adds fake data_. Our work
makes a number of significant leaps beyond this work: (1) We frame data bias
as programmable, rather than fixed, to mimic real-world bias scenarios, an
idea that has gained traction in a variety of domains, e.g., NLP [yuhao]. (2)
We lift a decision-tree-learning algorithm to operate over sets of datasets
represented via our bias-model language. (3) We investigate the bias-
robustness problem through a fairness lens, particularly with an eye towards
robustness rates for various demographic groups.

#### Ties to fairness

The notion of _individual fairness_ specifies that _similar individuals_
should receive similar predictions [dwork-fairness]; by contrast, we certify
that no individual should receive different predictions under models trained
by _similar datasets_. Black and Fredrickson explore the problem of how
individuals’ predictions change under models trained by similar datasets, but
their concept of similarity is limited to removing a _single_ data point
[black-leaveoneout]. Data bias, in particular, has received some attention in
the fairness literature. Chen et al. suggest adding missing data as an
effective approach to remedying bias in machine learning [chen-irene], which
is one operation that our bias language captures. Mandal et al. build on the
field of _distributional robustness_ [ben-tal-distribution, namkoong-
distribution, shafieezadeh-distribution] to build classifiers that are
empirically group-fair across a variety of nearby distributions [mandal-
fairness-checking]. Our problem domain is related to distributional robustness
because we certify robustness over a family of similar datasets; however, we
define specific data-transformation operators to define similarity, and,
unlike Mandal et al., we certify existing learners instead of building
empirically robust models.

#### Ties to robust statistics

There has been renewed interest in robust statistics for machine learning
[diakonikolas2019recent, DBLP:journals/cacm/DiakonikolasKKL21]. Much of the
work concerns outlier detection for various learning settings, e.g.,
estimating parameters of a Gaussian. The distinctions are two-fold: (1) We
deal with rich, nuanced bias models, as opposed to out-of-distribution
samples, and (2) we aim to certify that predictions are robust for a specific
input, a guarantee that cannot be made by robust-statistics-based techniques
[diakonikolas2019sever].

##  3 Defining data bias programmatically

We define the _bias-robustness problem_ and a language for defining bias
models _programmatically_.

#### Bias models

A dataset $T\subseteq\mathcal{X}\times\mathcal{Y}$ is a set of pairs of
samples and labels, where $\mathcal{Y}=\\{0,\ldots,n-1\\}$. For a dataset $T$,
we will use $T_{\mathcal{X}}$ to denote $\\{x\mid(x,y)\in T\\}$. A _bias
model_ $B$ is a function that takes a dataset and returns a _set of datasets_.
We call $B(T)\subseteq 2^{\mathcal{X}\times\mathcal{Y}}$ a _bias set_. We
assume that $T\in B(T)$. Intuitively, $B(T)$ represents _all datasets that
could have existed had there been no bias._

#### Pointwise data-bias robustness

Assume we have a learning algorithm $A$ that, given a training dataset $T$,
deterministically returns a classifier $h_{T}$ from some hypothesis class
$\mathcal{H}$. Fix a dataset $T$ and bias model $B$. Given a sample
$x\in\mathcal{X}$, we say that $A$ is _pointwise robust_ (or robust for short)
on $x$ iff

there is a label $i$ such that for all $T^{\prime}\in B(T)$, we have
$h_{T^{\prime}}(x)=i$ (1)

#### Basic components of a bias model

We begin with basic bias models.

_Missing data_ : A common bias in datasets is missing data, which can occur
via poor historical representation of a subgroup (e.g., women in CS-department
admissions data), or from present-day biases or shortsightedness (e.g., a
survey that bypasses low-income neighborhoods). Using the parameter $m$ as the
maximum number of missing elements, we formally define:

$\textsc{miss}_{m}(T)=\\{T^{\prime}\mid T^{\prime}{\supseteq}T,\
|T^{\prime}{\setminus}T|\leqslant m\\}$

$\textsc{miss}_{m}(T)$ defines an _infinite_ number datasets when the sample
space is infinite (e.g., $\mathbb{R}$-valued).

######  Example 3.1.

Using $T^{\mathsf{ex}}$ from Fig. 1, $\textsc{miss}_{1}(T^{\mathsf{ex}})$ is
the set of all datasets that are either $T^{\mathsf{ex}}$ or $T^{\mathsf{ex}}$
plus any new element $(x,y)$ with arbitrary race, score, and label.

_Label flipping_ : Historical data can contain human biases, e.g., in loan
financing, certain individuals’ loan requests get rejected due to
discrimination. Or consider employee-performance data, where women in certain
departments are consistently given lower scores by managers. We model such
biases as label flipping, where labels of up to $l$ individuals in the dataset
may be incorrect:

$\textsc{flip}_{l}(T)=\\{T^{\prime}\mid|T|{=}|T^{\prime}|,\
|T{\setminus}T^{\prime}|\leqslant l,\
T_{\mathcal{X}}=T^{\prime}_{\mathcal{X}}\\}$

######  Example 3.2.

Using $T^{\mathsf{ex}}$ from Fig. 1 and a bias model $\textsc{flip}_{1}$, we
have
$\textsc{flip}_{1}(T^{\mathsf{ex}})=\\{T^{\mathsf{ex}}_{0},\ldots,T^{\mathsf{ex}}_{3},$
$T^{\mathsf{ex}}_{5},\ldots,T^{\mathsf{ex}}_{9},T^{\mathsf{ex}}\\}$, where
$T^{\mathsf{ex}}_{i}$ is $T^{\mathsf{ex}}$ with the label of the element with
$\emph{score}=i$ _changed_.

_Fake data_ : Our final bias model assumes the dataset may contain _fake_
data. One cause may be a malicious user who enters fraudulent data into a
system (often referred to as _poisoning_). Alternatively, this model can be
thought of as the inverse of miss, e.g., we over-collected data for men.

$\textsc{fake}_{k}(T)=\\{T^{\prime}\mid T^{\prime}{\subseteq}T,\
|T{\setminus}T^{\prime}|\leqslant k\\}$

######  Example 3.3.

Using $T^{\mathsf{ex}}$ from Fig. 1 and a bias model $\textsc{fake}_{1}$, we
get
$\textsc{fake}_{1}(T^{\mathsf{ex}})=\\{T^{\mathsf{ex}}_{\downarrow{0}},\ldots,T^{\mathsf{ex}}_{\downarrow{3}},$
$T^{\mathsf{ex}}_{\downarrow 5},\ldots,T^{\mathsf{ex}}_{\downarrow
9},T^{\mathsf{ex}}\\}$ where $T^{\mathsf{ex}}_{\downarrow i}$ is
$T^{\mathsf{ex}}$ such that the element with $\emph{score}=i$ has been
_removed_.

#### Targeted bias models

Each bias model has a _targeted_ version that limits the bias to a specified
group of data points. For example, consider the missing data transformation.
If we suspect that data about women is missing from an HR database, we can
limit the miss transformation to only add data points with
$\emph{gender}=\textrm{female}$. Formally, we define a predicate
$g:\mathcal{X}\times\mathcal{Y}\to\mathbb{B}$, where
$\mathbb{B}=\\{\emph{true},\ \emph{false}\\}$.

$\textsc{miss}_{m}^{g}(T)=\\{T^{\prime}\mid T^{\prime}\supseteq T,\
|T^{\prime}\setminus T|\leqslant m,\ \underbrace{\forall(x,y)\in
T^{\prime}\setminus T\ldotp g(x,y)}_{\textrm{restrict}\ T^{\prime}}\\}$

Targeted versions of label-flipping and fake data can be defined in a similar
way.

######  Example 3.4.

In Fig. 1 (right), we used bias model $\textsc{flip}_{1}^{g}$, where $g$
targets Black people with negative labels. This results in the bias set
$\textsc{flip}_{1}^{g}(T^{\mathsf{ex}})=\\{T^{\mathsf{ex}}_{1},T^{\mathsf{ex}}_{8},T^{\mathsf{ex}}\\}$,
where $T^{\mathsf{ex}}_{i}$ is $T^{\mathsf{ex}}$ with the label of the element
with $\mathit{score}=i$ _changed_ (recall that scores 1 and 8 belong to Black
people in $T^{\mathsf{ex}}$).

#### Composite bias models

We can compose basic components to generate a _composite model_. Specifically,
we define a composite model $B$ as a finite set of arbitrary basic components,
that is,

$\displaystyle
B=[\textsc{miss}_{m_{1}}^{g_{1}},\ldots,\textsc{miss}_{m_{j}}^{g_{j}},\textsc{flip}_{l_{1}}^{g_{j+1}},\ldots,\textsc{flip}_{l_{p}}^{g_{j+p}},\textsc{fake}_{k_{1}}^{g_{j+p+1}},\ldots,\textsc{fake}_{k_{q}}^{g_{j+p+q}}]$
(2)

$B(T)$ is generated from $T$ by applying the basic components of $B$
iteratively. We must apply the constituent components in an optimal order,
i.e., one that generates all datasets that can be created through applying the
transformers in _any_ order. To do this, we apply components of the same type
in any order and apply transformers of different types in the order miss,
flip, fake (see Appendix).

######  Example 3.5.

Suppose $B=[\textsc{miss}_{2}^{g_{1}},\textsc{fake}_{1}]$. Then $B(T)$ is the
set of all datasets obtained by adding up to $2$ arbitrary data points that
satisfy $g_{1}$ to $T$, and then removing any up to $1$ data point.

##  4 Certifying robustness for decision-tree learning

We begin with a simplified version of the CART algorithm [cart], which is our
target for certification.

Given a dataset $T$ and a Boolean function (predicate)
$\phi:\mathcal{X}\to\mathbb{B}$, we define $T_{\phi}=\\{(x,y)\in
T\mid\phi(x)\\}$, i.e., $T_{\phi}$ is the set of elements satisfying $\phi$.
Analogously, $T_{\neg\phi}=\\{(x,y)\in T\mid\neg\phi(x)\\}$.

######  Example 4.1.

Using $\phi\triangleq\textit{score}\leqslant 3$, we have
$T^{\mathsf{ex}}_{\phi}=\\{0,1,2,3\\}$ and
$T^{\mathsf{ex}}_{\neg\phi}=\\{5,6,7,8,9\\}$.

#### Learning algorithm

To formalize our approach, it suffices to consider a simple algorithm that
learns a decision stump, i.e., a tree of depth 1. Therefore, the job of the
algorithm is to choose a predicate (splitting rule) $\phi$ from a set of
predicates $\Phi$ that optimally splits the dataset $T$ into two datasets.
Formally, we define $\mathsf{pr}_{i}(T)$ as the proportion of $T$ with label
$i$, i.e.,

$\mathsf{pr}_{i}(T)=|\\{(x,i)\in T\\}|\ /\ {|T|}$ (3)

We use $\mathsf{pr}$ to calculate _Gini impurity_ ($\mathsf{imp}$), that is,
$\mathsf{imp}(T)=\sum_{i=0}^{n-1}\mathsf{pr}_{i}(T)(1-\mathsf{pr}_{i}(T))$.

Using $\mathsf{imp}$, we assign each dataset-predicate pair a $\mathsf{cost}$,
where a low value indicates that $\phi$ splits $T$ _cleanly_ , i.e., elements
of $T_{\phi}$ (conversely, $T_{\neg\phi}$) have mostly the same label:
$\mathsf{cost}(T,\phi)=|T_{\phi}|\cdot\mathsf{imp}(T_{\phi})+|T_{\neg\phi}|\cdot\mathsf{imp}(T_{\neg\phi})$.

Finally, we select the predicate that results in the lowest $\mathsf{cost}$
(we break ties arbitrarily), as defined by the $\mathsf{split}$ operator:
$\mathsf{split}(T)=\operatorname*{argmin}_{\phi\in\Phi}\
\mathsf{cost}(T,\phi)$.

######  Example 4.2.

For $\phi\triangleq\mathit{score}\leqslant 3$,
$\mathsf{cost}(T^{\mathsf{ex}},\phi)=4\times 0+5\times 0.32=1.6$.

#### Inference

Given an optimal predicate $\phi$ and a new sample $x$ to classify, we return
the label with the highest proportion in the branch of the tree that $x$
takes. Formally, $\mathsf{infer}(T,\phi,x)=\operatorname*{argmax}_{i}\
\mathsf{pr}_{i}(T_{\phi^{\prime}})$, where $\phi^{\prime}$ is $\phi$ if
$\phi(x)=\emph{true}$; otherwise, $\phi^{\prime}$ is $\neg\phi$.

###  4.1 Certifying bias robustness with abstraction

Given a dataset $T$, bias model $B$, and sample $x$, our goal is to prove
robustness (Eq. 1): no matter which dataset in $B(T)$ was used to learn a
decision tree, the predicted label of $x$ is the same. Formally,

$\text{there is a label $i$ s.t. for all }T^{\prime}\in
B(T),\mathsf{infer}(T^{\prime},\phi^{\prime},x)=i,\ \text{ where
}\phi^{\prime}=\mathsf{split}(T^{\prime})$ (4)

The naïve way to prove this is to learn a decision tree using each dataset in
$B(T)$ and compare the results. This approach is intractable or impossible, as
$|B(T)|$ may be combinatorially large or infinite.

Instead, we _abstractly evaluate_ the decision-tree-learning algorithm on the
entire bias set $B(T)$ in a symbolic fashion, without having to enumerate all
datasets. Specifically, for each operator in the decision-tree-learning
algorithm, we define an abstract analogue, called an _abstract transformer_
[cousot1977abstract], that operates over _sets of training sets_ symbolically.
An abstract transformer is an approximation of the original operator, in that
it _over-approximates_ the set of possible outputs on the set $B(T)$.

#### Sound abstract transformers

Consider the $\mathsf{pr}_{i}$ operator, which takes a dataset and returns a
real number. We define an abstract transformer $\mathsf{pr}^{a}_{i}(B(T))$
that takes a set of datasets (defined as a bias set) and returns an interval,
i.e., a _subset_ of $\mathbb{R}$. The resulting interval defines a range of
possible values for the probability of class $i$. E.g., an interval
$\mathsf{pr}^{a}_{i}(B(T))$ may be $[0.1,0.3]$, meaning that the proportion of
$i$-labeled elements in datasets in $B(T)$ is between $0.1$ and $0.3$,
inclusive.

Given intervals computed by $\mathsf{pr}^{a}_{i}$, downstream operators will
be lifted into interval arithmetic, which is fairly standard. E.g., for
$a,b,c,d\in\mathbb{R}$, $[a,b]+[c,d]=[a+c,b+d]$. It will be clear from context
when we are applying arithmetic operators to intervals. For a sequence
$\\{x_{i}\\}_{i}$ of intervals, $\operatorname*{argmax}_{i}x_{i}$ returns a
_set of possible indices_ , as intervals may overlap and there may be no
unique maximum.

For the entire certification procedure to be correct, $\mathsf{pr}^{a}$ and
all other abstract transformers must be _sound_. That is, they should over-
approximate the set of possible outputs. Formally, $\mathsf{pr}^{a}_{i}$ is a
sound approximation of $\mathsf{pr}_{i}$ iff for all $i$ and all
$T^{\prime}\in B(T)$, we have
$\mathsf{pr}_{i}(T^{\prime})\in\mathsf{pr}^{a}_{i}(B(T))$.

#### Certification process

To perform certification, we use an abstract transformer
$\mathsf{split}^{a}(B(T))$ to compute a _set_ of best predicates $\Phi^{a}$
for $B(T)$. The reason $\mathsf{split}^{a}$ returns a set of predicates is
because its input is a set of datasets that may result in different optimal
splits. Then, we use an abstract transformer
$\mathsf{infer}^{a}(B(T),\Phi^{a},x)$ to compute a _set_ of labels for $x$. If
$\mathsf{infer}^{a}$ returns a singleton set, then we have proven pointwise
robustness for $x$ (Eq. 4); otherwise, we have an inconclusive result—we
cannot falsify robustness because abstract transformers are over-approximate.

###  4.2 Abstract transformers for $\mathsf{pr}$

We focus on the most challenging transformer, $\mathsf{pr}^{a}$; in § 4.3, we
show the rest of the transformers.

#### Abstracting missing data

We begin by describing $\mathsf{pr}^{a}$ for missing data bias,
$B=\textsc{miss}_{m}$. From now on, we use $c_{i}$ to denote the number of
samples $(x,y)\in T$ with $y=i$. We define $\mathsf{pr}^{a}_{i}$ by
considering how we can add data to _minimize_ the fraction of $i$’s in $T$ for
the lower bound of the interval, and _maximize_ the fraction of $i$’s in $T$
for the upper bound. To minimize the fraction of $i$’s, we add $m$ elements
with label $j\neq i$; to maximize the fraction of $i$’s, we add $m$ elements
with label $i$.

$\mathsf{pr}^{a}_{i}(\textsc{miss}_{m}(T))=\left[\frac{c_{i}}{|T|+m}\ ,\
\frac{c_{i}+m}{|T|+m}\right]$ (5)

######  Example 4.3.

Given $B=\textsc{miss}_{1}$, we have
$\mathsf{pr}^{a}_{\color[rgb]{0,0.88,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.88,0}\pgfsys@color@cmyk@stroke{0.91}{0}{0.88}{0.12}\pgfsys@color@cmyk@fill{0.91}{0}{0.88}{0.12}\checkmark}(B(T^{\mathsf{ex}}))=\left[\frac{4}{10},\frac{6}{10}\right]$.

#### Abstracting label-flipping

Next, we define $\mathsf{pr}^{a}_{i}$ for label-flipping bias, where
$B=\textsc{flip}_{l}$. Intuitively, we can minimize the proportion of $i$’s by
flipping $l$ labels from $i$ to $j\neq i$, and maximize the proportion of
$i$’s by flipping $l$ labels from $j\neq i$ to $i$. The caveat here is that if
there are fewer than $l$ of whichever label we want to flip, we are limited by
$c_{i}$ or $\sum_{j\neq i}c_{j}$, depending on flipping direction.

$\mathsf{pr}^{a}_{i}(\textsc{flip}_{l}(T))=\left[\frac{c_{i}-\min(l,c_{i})}{|T|},\frac{c_{i}+\min(l,\sum_{j\neq
i}c_{j})}{|T|}\right]$ (6)

######  Example 4.4.

Given $B=\textsc{flip}_{1}$, we have
$\mathsf{pr}^{a}_{\color[rgb]{0,0.88,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.88,0}\pgfsys@color@cmyk@stroke{0.91}{0}{0.88}{0.12}\pgfsys@color@cmyk@fill{0.91}{0}{0.88}{0.12}\checkmark}(B(T^{\mathsf{ex}}))=\left[\frac{4}{9},\frac{6}{9}\right]$.

Fake data bias models can be abstracted similarly (see Appendix).

#### Abstracting targeted bias models

We now show how to abstract targeted bias models, where a function $g$
restricts the affected samples. To begin, we limit $g$ to only condition on
features, not the label. In the case of $\textsc{miss}^{g}$, the definition of
$\mathsf{pr}^{a}$ does not change, because even if we restrict the
characteristics of the elements that we can add, we can still add up to $m$
elements with any label.

In the case of label-flipping, we constrain the parameter $l$ to be no larger
than $|T_{g}|$. Formally, we define $l_{i}=\min(l,|\\{(x,i)\in T:g(x)\\}|)$
and then

$\mathsf{pr}^{a}_{i}(\textsc{flip}_{l}^{g}(T))=\left[\frac{c_{i}-l_{i}}{|T|},\
\frac{c_{i}+\min(\sum_{j\neq i}l_{j},l)}{|T|}\right]$ (7)

The definition for fake data is similar (see Appendix). The above definition
is sound when $g$ conditions on the label; however, the Appendix includes a
more precise definition of $\mathsf{pr}^{a}$ for that scenario.

#### Abstracting composite bias models

Now consider a composite bias model consisting of all the basic bias models.
Intuitively, $\mathsf{pr}^{a}_{i}$ will need to reflect changes in $c_{i}$
that occur from adding data, flipping labels, and removing data. First, we
consider a bias model with just one instance of each miss, flip, and fake,
i.e.,
$B=[\textsc{miss}_{m}^{g_{1}},\textsc{flip}_{l}^{g_{2}},\textsc{fake}_{k}^{g_{3}}]$.
We define auxiliary variables $l_{i}=\min(l,|\\{(x,i)\in T:g_{2}(x,i)\\}|)$
and $k_{i}=\min(k,|\\{(x,i)\in T:g_{3}(x,i)\\}|)$. Intuitively, these
variables represent the number of elements with label $i$ that we can alter.
Conversely, to represent the elements with a label other than $i$, we will use
$l^{\prime}_{i}=\min(l,\Sigma_{j\neq i}l_{j})$ and
$k^{\prime}_{i}=\min(k,\Sigma_{j\neq i}c_{j})$.

$\mathsf{pr}^{a}_{i}(B(T))=\left[\max\left(0,\frac{c_{i}-l_{i}-k_{i}}{|T|-k_{i}+m}\right),\min\left(1,\frac{c_{i}+l^{\prime}_{i}+m}{|T|-k^{\prime}_{i}+m}\right)\right]$
(8)

Extending the above definition to allow multiple uses of the same basic model,
e.g., $\\{\textsc{flip}_{l_{1}}^{g_{1}},\textsc{flip}_{l_{2}}^{g_{2}}\\}$ is
simple: essentially, we just sum $l_{1}$ and $l_{2}$. A full formal definition
is in the Appendix.

######  Theorem 1.

$\mathsf{pr}^{a}$ is a sound abstract transformer. (In the Appendix, we also
show that $\mathsf{pr}^{a}$ is precise.)

###  4.3 An abstract decision-tree algorithm

We define the remaining abstract transformers, with the goal of certification.
Our definitions are based on Drews et al. [drews-pldi]; the key difference is
the $T_{\phi}$ operation, which is dependent on the bias model.

#### Filtering

We need $B(T)_{\phi}$, the abstract analogue of $T_{\phi}$. For flip and fake,
we define $B(T)_{\phi}$ = $B(T_{\phi})$. But for miss, we have to alter the
bias model, too, since after filtering on $\phi$ we only want to add new
elements that satisfy $\phi$. We define
$\textsc{miss}_{m}^{g}(T)_{\phi}=\textsc{miss}_{m}^{g\land\phi}(T_{\phi})$.
Filtering composite bias models applies these definitions piece-wise (see a
full definition and soundness proof in the Appendix).

#### Gini impurity

We lift $\mathsf{imp}$ to interval arithmetic:
$\mathsf{imp}^{a}(T)=\sum_{i=1}^{n}\mathsf{pr}^{a}_{i}(T)([1,1]-\mathsf{pr}^{a}_{i}(T))$.

#### Cost

Recall that $\mathsf{cost}$ relies on $|T_{\phi}|$. We want an abstract
analogue of $|T_{\phi}|$ that represents the range of sizes of datasets in
$B(T)_{\phi}$ and not the number of datasets in $B(T)_{\phi}$. To this end, we
define an auxiliary function $\mathsf{size}$ where
$\mathsf{size}(B(T)_{\phi})=[a,b]$ such that
$a=\min\\{|T^{\prime}|:T^{\prime}\in B(T)_{\phi}\\}$ and
$b=\max\\{|T^{\prime}|:T^{\prime}\in B(T)_{\phi}\\}$.

Then, we define the cost of splitting on $\phi$ as follows (recall that the
operators use interval arithmetic):

$\mathsf{cost}^{a}(B(T),\phi)=\mathsf{size}(B(T)_{\phi})\times\mathsf{imp}^{a}(B(T)_{\phi})+\mathsf{size}(B(T)_{\neg\phi})\times\mathsf{imp}^{a}(B(T)_{\neg\phi})$
(9)

Since $\mathsf{size}$ and $\mathsf{imp}^{a}$ return intervals,
$\mathsf{cost}^{a}$ will be an interval, as well.

#### Best split

To find the set of best predicates, we identify the _least upper bound_
($\mathit{lub}$) of any predicate’s $\mathsf{cost}$. Then, any predicate whose
$\mathsf{cost}$ overlaps with $\mathit{lub}$ will be a member of the set of
best predicates, too. Formally, $\mathit{lub}=\min_{\phi\in\Phi}b_{\phi}$,
where $\mathsf{cost}^{a}(\phi)=[a_{\phi},b_{\phi}]$ Then, we define
$\mathsf{split}^{a}(B(T))=\\{\phi\in\Phi\mid
a_{\phi}\leqslant\mathit{lub}\\}$.

#### Inference

Finally, for inference, we evaluate every predicate computed by
$\mathsf{split}^{a}$ on $x$ and collect all possible prediction labels, as
follows:

$\mathsf{infer}^{a}(B(T),\Phi^{a},x)=\bigcup_{\phi(x)}\operatorname*{argmax}_{i}\
\mathsf{pr}^{a}_{i}(B(T)_{\phi})\ \cup\
\bigcup_{\neg\phi(x)}\operatorname*{argmax}_{i}\
\mathsf{pr}^{a}_{i}(B(T)_{\neg\phi})$ (10)

where the range of $\cup$ is over predicates in $\Phi^{a}$. Since our goal is
to prove robustness, we only care if
$|\mathsf{infer}^{a}(B(T),\Phi^{a},x)|=1$, i.e., all datasets produce the same
prediction.

######  Theorem 2.

If $|\mathsf{infer}^{a}(B(T),\Phi^{a},x)|=1$, where
$\Phi^{a}=\mathsf{split}^{a}(B(T))$, then $x$ is robust (Eq. 4).

######  Example 4.5.

Recall Fig. 1 with bias model $B=\textsc{flip}^{g}_{1}$, where $g$ targets
Black people with
$\color[rgb]{0.68,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.68,0,0}\pgfsys@color@cmyk@stroke{0}{0.87}{0.68}{0.32}\pgfsys@color<EMAIL_ADDRESS>label. $\mathsf{split}^{a}(B(T^{\mathsf{ex}}))$ returns the singleton set
$\Phi^{a}=\\{\mathit{score}\leqslant 3\\}$. Then, given input
$x=\langle\mathit{race}=\textrm{Black},\mathit{score}=7\rangle$,
$\mathsf{infer}^{a}(B(T^{\mathsf{ex}}),\Phi^{a},x)=\\{{\color[rgb]{0,0.88,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.88,0}\pgfsys@color@cmyk@stroke{0.91}{0}{0.88}{0.12}\pgfsys@color<EMAIL_ADDRESS>since
$\mathsf{pr}^{a}_{\color[rgb]{0,0.88,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.88,0}\pgfsys@color@cmyk@stroke{0.91}{0}{0.88}{0.12}\pgfsys@color@cmyk@fill{0.91}{0}{0.88}{0.12}\checkmark}(B(T^{\mathsf{ex}})_{\mathit{score}>3})=[0.8,1]$,
which is greater than
$\mathsf{pr}^{a}_{\color[rgb]{0.68,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.68,0,0}\pgfsys@color@cmyk@stroke{0}{0.87}{0.68}{0.32}\pgfsys@color@cmyk@fill{0}{0.87}{0.68}{0.32}\times}(B(T^{\mathsf{ex}})_{\mathit{score}>3})=[0,0.2]$.
Therefore, the learner is robust on $x$.

##  5 Experimental evaluation

We implement our certification technique in C++ and call it Antidote-P, as it
extends Antidote [drews-pldi] to programmable bias models. To learn trees with
depth $>1$, we apply the presented procedure recursively. We use Antidote’s
_disjunctive domain_ , which is beneficial for certification [drews-pldi] but
requires a large amount of memory because it keeps track of many different
datasets on each decision-tree path. We evaluate on Adult Income [uci-data]
(training $n$=32561), COMPAS [compas] ($n$=4629), and Drug Consumption [drug-
data] ($n$=1262). A fourth dataset, MNIST 1/7 ($n$=13007), is in the Appendix.

For each dataset, we choose the smallest tree depth where accuracy improves no
more than 1% at the next-highest depth. For Adult Income and MNIST 1/7, this
threshold is depth 2 (accuracy 83% and 97%, respectively); for COMPAS and Drug
Consumption it is depth 1 (accuracy 64% and 76%, respectively). We run
additional experiments on COMPAS and Drug Consumption at depths 2 and 3 to
evaluate how tree depth influences Antidote-P’s efficiency (see Appendix).

A natural baseline is enumerating all datasets in the bias set but that is
infeasible—see bias-set sizes in LABEL:tab:all_data. To our knowledge, our
technique (extended from [drews-pldi]), is the only method to certify bias
robustness of decision-tree learners.

###  5.1 Effectiveness at certifying robustness

Table LABEL:tab:all_data shows the results. Each entry in the table indicates
the percentage of test samples for which Antidote-P can prove robustness with
a given bias model and the shading indicates the size of the bias set,
$|B(T)|$. We see that even though the perturbation sets are very
large—sometimes infinite—we are able to certify robustness for a significant
percentage of elements.

#### By dataset

Certification rates vary from 98.8% robustness for $\textsc{miss}_{0.05\%}$ on
Adult Income (i.e., the predictions of 98.8% of the points in the test set do
not change if up to 0.05% new points are added to the training set) to just 3%
robustness for $\textsc{flip}_{1\%}$ on COMPAS. Even for a single bias model,
the certification rates vary widely: under $\textsc{flip}_{0.2\%}$, we can
verify 94.5% of samples as robust for Drug Consumption, but only 70.2% for
Adult Income and 47.8% for COMPAS. We posit that these differences stem from
inherent properties of the datasets. The optimal top-most split has
$\mathsf{cost}=0.30$ for Adult Income, $\mathsf{cost}=0.35$ for Drug
Consumption, and $\mathsf{cost}=0.45$ for COMPAS (recall that a lower
$\mathsf{cost}$ corresponds to greater information gain). As a result, biasing
a fixed percentage of data yields greater instability for COMPAS, since the
data already exhibited poorer separation.

#### By bias model

There are also differences in certification rates between bias models. flip is
more destructive to robustness because flipping a single label results in a
symmetric difference of 2 from the original dataset (as if we removed an
element from the set and then inserted a new one with a flipped label), while
adding a single item results in a symmetric difference of 1.

The composite bias models display similar dataset- and bias model-based
trends. Notably, miss \+ fake yields a lower certifiable-robustness rate than
flip. E.g., under $\textsc{flip}_{0.1\%}$, we can certify 71.5% of COMPAS test
samples as robust. But for $\textsc{miss}_{0.1\%}$ \+ $\textsc{fake}_{0.1\%}$
(that is, 0.2% bias total), we are only able to certify 50.5% of test samples
as robust. This shows that flip is a useful modeling tool for situations where
we believe the features of all data points to be trustworthy, but suspect that
some labels may be incorrect. The targeted bias models allow for greater
certification rates than the non-targeted versions; this is expected because
they result in smaller bias sets.

In summary, Antidote-P can effectively certify robustness across a variety of
bias models, but its success depends on properties of the dataset such as
separability.

###  5.2 Demographic variations

We evaluated differences in certifiable-robustness rates across demographic
groups in all three datasets. We present results from COMPAS and Adult Income
in LABEL:fig:demo (results for Drug Consumption are in the Appendix; they are
less interesting due to a lack of representation in the dataset).

#### COMPAS

LABEL:fig:demoa shows that under flip, White women are robust at a higher rate
than any other demographic group, and that Black men and women are the least
robust. Notably, for $\textsc{flip}_{0.4\%}$, we are able to certify
robustness for 50.4% of White women, but 0% of Black people. There is also a
significant gap between White women and White men at this threshold (50.4% vs.
38.8%). We can explain the gaps in certification rates of different subgroups
by looking at the training data. In the COMPAS dataset, the same predicate
provides the optimal split for every race-gender subgroup, but for White women
the resulting split has $\mathsf{cost}=0.41$ versus $\mathsf{cost}=0.46$ for
Black people. It is not clear whether this difference stems from sampling
techniques or inherent differences in the population, but regardless, the end
result is that predictions made about Black people from decision trees trained
on COMPAS are more likely to be vulnerable to data bias.

To validate that the disparities in certifiable-robustness rates are due to
inherent dataset properties rather than the abstraction, we performed random
testing by perturbing the COMPAS dataset to try to find robustness
counterexamples, i.e., datasets in the bias set that yield conflicting
predictions on a given input. We found more counterexamples to robustness for
Black people than for White people, which is further evidence for our claim
that the robustness disparities are inherent to the dataset.

#### Targeted bias models (COMPAS)

If we choose
$g\triangleq(\emph{race}=\textrm{Black}\land\emph{label}=\textrm{positive})$
(LABEL:fig:demob) in $\textsc{flip}^{g}$ to model the real-world situation
where structural or individual racism can lead to increased policing and
convictions among Black people in the U.S., then there are generally higher
robustness rates at moderate bias levels (e.g., $\sim$50% robustness for all
demographic groups at 0.4% poisoning). However, as the amount of bias
increases, a gap between White and Black certification rates emerges (in exact
terms, 32.9% of White test samples are certifiably robust versus 0% of Black
test samples starting at 1.1% bias and continuing through, at least, 10.8%
bias). It is unclear whether this trend stems from inherent dataset
properties, or is due to the over-approximate nature of the abstraction.

By contrast, using
$g\triangleq(\emph{race}=\textrm{White}\land\emph{label}=\textrm{negative})$
(LABEL:fig:democ) to describe that White people may be under-policed or under-
convicted due to White privilege nearly eliminates discrepancies between
demographic groups. In particular, Black men (previously the least-robust
subgroup) are the most robust of any population. $\textsc{flip}^{g}$ and
$\textsc{flip}^{g^{\prime}}$ differ only on how they describe societal
inequities: are White people under-policed, or are Black people over-policed?
However, the vast differences in demographic-level robustness rates between
$\textsc{flip}^{g}$ and $\textsc{flip}^{g^{\prime}}$ shows that the choice of
predicate is crucial when using targeted bias models. While understanding why
this phenomenon occurs is beyond the scope of this paper, these results show
how Antidote-P could be a useful tool for social scientists to understand how
data bias can affect the reliability of machine-learning outcomes.

#### Adult Income

LABEL:fig:demod shows robustness by demographic group for flip. We see that
Black men have about a 5% lower robustness rate than other demographic groups
and that at higher bias levels, White women also have about a 5% lower
robustness rate than White men or Black women. Using $\textsc{flip}^{g}$ where
$g=(\emph{race}=\textrm{Female}\land\emph{Label}=\textrm{negative})$ led to
similar results (see Appendix).

##  6 Conclusions and broader impacts

We saw that our decision-tree-learner abstraction is able to verify pointwise
robustness over large and even infinite bias sets. These guarantees permit
increased confidence in the trees’ outputs because they certify that data bias
has not affected the outcome (within a certain threshold). However, a tricky
aspect—and one that we do not attempt to address—is knowing whether the
assumptions underlying the bias model are correct. If the user does not
specify the bias model correctly, then any proofs may not be representative.
Also, our tool only certifies robustness, not accuracy. Therefore, it may
certify that a model will always output the _wrong_ label on a given data
point. This is linked to a shortcoming of many machine-learning audits: our
tool cannot determine what is an appropriate use of machine learning. Machine
learning is often used to promote and legitimize uses of technology that are
harmful or unethical. In particular, we want to call out our use of the COMPAS
dataset: we feel that it is illustrative to show how certifiable-robustness
rates can vary widely between different demographic groups and be sensitive to
subtle shifts in the bias model. However, this use should not be taken as an
endorsement for the deployment of recidivism-prediction models.

Returning to our work, Antidote-P has a place in data scientists’ tool-kits as
a powerful technique to understand robustness, and potential vulnerabilities,
of data bias in decision-tree algorithms. Future work can improve our
approach’s utility by developing effective techniques for falsification of
robustness (i.e., techniques to find minimal dataset perturbations that break
robustness), by tightening the analytic bounds, such as by abstracting over a
more complex domain than intervals, and by extending the same ideas to allow
for verification of other machine-learning algorithms.

## Acknowledgments and Disclosure of Funding

Acknowledgements go here (currently hidden)

## Checklist

  1. 1.

For all authors…

    1. (a)

Do the main claims made in the abstract and introduction accurately reflect
the paper’s contributions and scope? [Yes]

    2. (b)

Did you describe the limitations of your work? [Yes] See § 6.

    3. (c)

Did you discuss any potential negative societal impacts of your work? [Yes]
See § 6.

    4. (d)

Have you read the ethics review guidelines and ensured that your paper
conforms to them? [Yes]

  2. 2.

If you are including theoretical results…

    1. (a)

Did you state the full set of assumptions of all theoretical results? [Yes]

    2. (b)

Did you include complete proofs of all theoretical results? [Yes] We include
proofs in the Appendix.

  3. 3.

If you ran experiments…

    1. (a)

Did you include the code, data, and instructions needed to reproduce the main
experimental results (either in the supplemental material or as a URL)? [Yes]
We include the code, data, and instructions as supplementary material.

    2. (b)

Did you specify all the training details (e.g., data splits, hyperparameters,
how they were chosen)? [Yes] To the extent this question is relevant (we only
use decision trees and we do not modify hyperparameters other than depth), all
details are included in the paper (e.g., depth of models) or in the
supplemental material (e.g., data splits).

    3. (c)

Did you report error bars (e.g., with respect to the random seed after running
experiments multiple times)? [N/A]

    4. (d)

Did you include the total amount of compute and the type of resources used
(e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] Details are
in the Appendix.

  4. 4.

If you are using existing assets (e.g., code, data, models) or
curating/releasing new assets…

    1. (a)

If your work uses existing assets, did you cite the creators? [Yes] See § 5
for dataset citations, and see [drews-pldi] (cited throughout) for the
starting place for the Antidote-P implementation.

    2. (b)

Did you mention the license of the assets? [No] We use commonly-used datasets
that are available for research use with proper citation, so we do not mention
their licenses in the text of the paper. We do not mention the license of
Antidote-P either, but this information will be included with code in the
supplemental material.

    3. (c)

Did you include any new assets either in the supplemental material or as a
URL? [Yes] Our code (the Antidote-P prototype) is included as part of the
supplemental material.

    4. (d)

Did you discuss whether and how consent was obtained from people whose data
you’re using/curating? [N/A] We used publicly-available datasets.

    5. (e)

Did you discuss whether the data you are using/curating contains personally
identifiable information or offensive content? [No] Of the datasets we use,
only COMPAS contains PII (a fact that is generally known). To mitigate this,
we use (and include in the supplementary material) a version of the code that
is stripped of names, birthdates, and other directly identifying information.

  5. 5.

If you used crowdsourcing or conducted research with human subjects…

    1. (a)

Did you include the full text of instructions given to participants and
screenshots, if applicable? [N/A]

    2. (b)

Did you describe any potential participant risks, with links to Institutional
Review Board (IRB) approvals, if applicable? [N/A]

    3. (c)

Did you include the estimated hourly wage paid to participants and the total
amount spent on participant compensation? [N/A]

##  Appendix A Additional details and definitions

Throughout the appendices, we use square brackets, rather than braces, to
denote composite bias models: this is to emphasize that the transformers are
ordered, and that alternate orderings often result in distinct bias sets.

#### Filtering composite bias models

Filtering a composite bias model requires us to apply filter piece-wise, i.e.,
$[\textsc{miss}_{m}^{g_{1}},\textsc{flip}_{l}^{g_{2}},\textsc{fake}_{k}^{g_{3}}](T)_{\phi}=[\textsc{miss}_{m}^{g_{1}\land\phi},\textsc{flip}_{l}^{g_{2}},\textsc{fake}_{k}^{g_{3}}](T_{\phi})$.

####  $\mathsf{pr}^{a}$ for fake

Given $c_{i}$ samples in $T$ with label $i$, we use $k_{i}=\min(k,c_{i})$ and
then define

$\mathsf{pr}^{a}_{i}(\textsc{fake}_{k}(T))=\left[\frac{c_{i}-k_{i}}{|T|-k_{i}},\frac{c_{i}}{|T|-\sum_{j\neq
i}k_{j}}\right]$ (11)

For the edge case where $c_{i}=|T|$ and $c_{i}\leqslant k$ for any $i$, we
define $\mathsf{pr}^{a}_{j}(T)=[0,1]$ for all $j\in[1,n]$. A similar edge case
applies, when necessary, to the composite definition.

#### Optimizing $\mathsf{pr}^{a}$ when $g$ looks at the label

If $g$ conditions on the label, then we can improve the precision of
$\mathsf{pr}^{a}$ by defining each component individually. Suppose
$g(x,y)=y\in S\land g^{\prime}(x)$, where $S\subset\\{1,\cdots,n\\}$ and
$g^{\prime}$ is a predicate that only conditions on features.

For $\textsc{miss}_{m}^{g}$, we define

$\mathsf{pr}^{a}_{i}(\textsc{miss}_{m}^{g})=\begin{cases}\left[\frac{c_{i}}{|T|},\frac{c_{i}+m}{|T|+m}\right]&\text{if}\,i\in
S\text{ and }|S|=1\\\
\left[\frac{c_{i}}{|T|+m},\frac{c_{i}+m}{|T|+m}\right]\quad&\text{if}\,i\in
S\text{ and }|S|\geq 2\\\
\left[\frac{c_{i}}{|T|+m},\frac{c_{i}}{|T|}\right]\quad&\text{else}\\\
\end{cases}$ (12)

For $\textsc{flip}_{l}^{g}$, we use $l_{a_{i}}=\min(l,|\\{(x,y)\in T\mid
y=i\land g(x,y)\\}|)$ and $l_{b_{i}}=\min(l,|\\{(x,y)\in T\mid y\neq i\land
g(x,y)\\}|)$. Then, we define

$\mathsf{pr}^{a}_{i}(\textsc{flip}_{l}^{g})=\begin{cases}\left[\frac{c_{i}-l_{a_{i}}}{|T|},\frac{c_{i}}{|T|}\right]&\text{if}\,i\in
S\text{ and }|S|=1\\\
\left[\frac{c_{i}-l_{a_{i}}}{|T|},\frac{c_{i}+l_{b_{i}}}{|T|}\right]&\text{if}\,i\in
S\text{ and }|S|\geq 2\\\
\left[\frac{c_{i}}{|T|},\frac{c_{i}+l_{b_{i}}}{|T|}\right]&\text{else}\\\
\end{cases}$ (13)

For $\textsc{fake}_{k}^{g}$, we use $k_{a_{i}}=\min(k,|\\{(x,y)\in T\mid
y=i\land g(x,y)\\}|)$ and $k_{b_{i}}=\min(k,|\\{(x,y)\in T\mid y\neq i\land
g(x,y)\\}|)$. Then, we define

$\mathsf{pr}^{a}_{i}(\textsc{fake}_{k}^{g})=\begin{cases}\left[\frac{c_{i}-k_{a_{i}}}{|T|-k_{a_{i}}},\frac{c_{i}}{|T|}\right]&\text{if}\,i\in
S\text{ and }|S|=1\\\
\left[\frac{c_{i}-k_{a_{i}}}{|T|-k},\frac{c_{i}}{|T|-k_{b_{i}}}\right]&\text{if}\,i\in
S\text{ and }|S|\geq 2\\\
\left[\frac{c_{i}}{|T|},\frac{c_{i}}{|T|-k_{b_{i}}}\right]&\text{else}\\\
\end{cases}$ (14)

We prove that the above definitions are sound and precise in Appendix D. If
desired, the above definitions can be pieced together to provide a more
precise definition for composite bias models. However, we limit ourselves to
just the singleton transformers because notation becomes very messy, as we
have to keep track of many variables indicating how many data elements satisfy
the various conditions.

####  $\mathsf{pr}^{a}$ for composite bias models with multiple versions of
the same transformer

If a bias model contains multiple instances of the same transformer, e.g.,
$B=[\textsc{flip}_{l_{1}}^{g_{1}},\textsc{flip}_{l_{2}}^{g_{2}}]$, we can
combine everything into a single transformer. Formally, given

$\displaystyle
B=[\textsc{miss}_{m_{1}}^{g^{\prime}_{1}},\ldots,\textsc{miss}_{m_{j}}^{g^{\prime}_{j}},\textsc{flip}_{l_{1}}^{g^{\prime}_{j+1}},\ldots,\textsc{flip}_{l_{p}}^{g^{\prime}_{j+p}},\textsc{fake}_{k_{1}}^{g^{\prime}_{j+p+1}},\ldots,\textsc{fake}_{k_{q}}^{g^{\prime}_{j+p+q}}]$
(15)

we define

$m=m_{1}+\ldots+m_{j}$ $g_{1}=g^{\prime}_{1}\lor\cdots\lor g^{\prime}_{j}$
$l_{i}=\min(l_{1}+\ldots+l_{p},|\cup_{i\in[1,p]}T_{g_{j+i}(x,y)\land y=i}|)$
$g_{2}=g^{\prime}_{j+1}\lor\cdots\lor g^{\prime}_{j+p}$
$k_{i}=\min(k_{1}+\ldots+k_{p},|\cup_{i\in[1,q]}T_{g_{j+p+i}(x,y)\land y=i}|)$

and

$g_{3}=g^{\prime}_{j+p+1}\lor\cdots\lor g^{\prime}_{j+p+1}$

Then, we can use the formula shown in Equation 8 to compute $\mathsf{pr}^{a}$.
We show in Appendix C that these definitions are sound.

#### Size ($\mathsf{size}$)

We define $\mathsf{size}(\textsc{miss}_{m}^{g})=[|T|,|T|+m]$,
$\mathsf{size}(\textsc{flip}_{l}^{g})=[|T|,|T|]$, and
$\mathsf{size}(\textsc{fake}_{k}^{g})=[|T|-k,|T|]$. Putting this all together,
we have
$\mathsf{size}([\textsc{miss}_{m}^{g_{1}},\textsc{flip}_{l}^{g_{2}},\textsc{fake}_{k}^{g_{3}}])=[|T|-k,|T|+m]$.

##  Appendix B Proof of optimal composition of transformers

As stated in § 3, when composing transformers we want to apply them in an
order that results in the largest composite bias model. To illustrate the
concept of composite bias models’ relative size, consider
$B=[\textsc{miss}_{1}^{g_{1}},\textsc{flip}_{1}^{g_{2}}]$ and
$B^{\prime}=[\textsc{flip}_{1}^{g_{2}},\textsc{miss}_{1}^{g_{1}}]$ where
$g_{1}\triangleq$(_gender_ =female $\land$ _label_ =1) and
$g_{2}\triangleq$(_gender_ =female). I.e., $B$ adds one data point subject to
$g_{1}$ and then flips the label of one data point subject to $g_{2}$, whereas
$B^{\prime}$ performs these two operations in the opposite order. Under $B$,
we can use miss to add the data point $(x,y)=\langle$_gender_ =female,_label_
=1$\rangle$ and then use flip to change $y$ to 0. However, under $B^{\prime}$,
we cannot alter the point that miss adds, so $B$ and $B^{\prime}$ are not
equivalent. In this case, $B$ can construct every dataset that $B^{\prime}$
can construct (but not vice-versa), so we write $B^{\prime}\subset B$ and say
that $B$ is larger than $B^{\prime}$.

First we consider the case when there are multiple transformers of the same
type.

######  Theorem 3.

The bias models
$B_{1}=[\textsc{miss}_{m_{1}}^{g_{1}},\textsc{miss}_{m_{2}}^{g_{2}}]$ and
$B_{2}=[\textsc{miss}_{m_{2}}^{g_{2}},\textsc{miss}_{m_{1}}^{g_{1}}]$ are
equivalent (and likewise for fake and flip, as long as no flip predicate
conditions on the label).

###### Proof.

#### Missing data

The choice of what missing data to add has no bearing on what is already in
(or not in) the dataset. Thus we can add $m_{1}$ elements that satisfy $g_{1}$
followed by $m_{2}$ elements that satisfy $g_{2}$, or do the operators in the
reverse order, but the end result is the same.

#### Label-flipping

Suppose $B=[\textsc{flip}_{l_{1}}^{g_{1}},\textsc{flip}_{l_{2}}^{g_{2}}]$,
where $g_{1}$ and $g_{2}$ do not condition on the label. We want to show that
$B$ is equivalent to
$B^{\prime}=[\textsc{flip}_{l_{2}}^{g_{2}},\textsc{flip}_{l_{1}}^{g_{1}}]$.

Consider an arbitrary $T^{\prime}\in B(T)$. Each data point in $T^{\prime}$ is
either (1) untouched by $\textsc{flip}_{l_{1}}^{g_{1}}$ and
$\textsc{flip}_{l_{2}}^{g_{2}}$, (2) flipped only by
$\textsc{flip}_{l_{1}}^{g_{1}}$, (3) flipped only by
$\textsc{flip}_{l_{2}}^{g_{2}}$, or (4) flipped by both
$\textsc{flip}_{l_{1}}^{g_{1}}$ and $\textsc{flip}_{l_{2}}^{g_{2}}$. If (1),
clearly this is obtainable by $B^{\prime}$ since we did nothing. If (2), then
since the data point is untouched by $\textsc{flip}_{l_{2}}^{g_{2}}$, the data
point can be flipped uninterrupted by $\textsc{flip}_{l_{1}}^{g_{1}}$
(similarly for (3)). If (4), then – since neither $g_{1}$ nor $g_{2}$
conditions on the label nor specifies what the new label can be – we can still
flip the label twice and end up with the same configuration. The same
arguments hold had we started with $T^{\prime\prime}\in B^{\prime}$.
Therefore, $B$ and $B^{\prime}$ are equivalent.

#### Fake data

The argument for fake data is similar. ∎

We can extend the proof of Theorem 3 to arbitrarily many transformers of the
same type.

Note that if flip conditions on the label, this proof does not hold. To
continue with the terminology from the proof, if $g_{i}\triangleq$(_label_
=$a$), then applying $\textsc{flip}_{l_{j}}^{g_{j}}$ first to some element
$(x,a)$ yields $(x,a^{\prime})$, which may no longer eligible to be flipped by
$\textsc{flip}_{l_{i}}^{g_{i}}$.

Next, we show that there is an optimal way to compose transformers of
different types. We define _optimal_ as largest, that is, some $B^{\prime}$ is
optimal compared to $B$ if $B\subseteq B^{\prime}$. In other words, this
notation says that every dataset created by $B$ can also be created by
$B^{\prime}$. For the next theorem and its proof we assume there is only one
instance of each transformer type; however, in conjunction with Theorem 3 we
can extend it to include multiple instances of the same transformer type.

######  Theorem 4.

$B=[\textsc{miss},\textsc{flip},\textsc{fake}]$ is the optimal order to apply
the transformers miss, flip, and fake (i.e., any other ordering $B^{\prime}$
of these transformers will satisfy $B^{\prime}\subseteq B$).

###### Proof.

We will show that other orderings of miss, flip, fake do not produce any
biased datasets that do not also occur in
$[\textsc{miss},\textsc{flip},\textsc{fake}]$. For conciseness, we will write
$[\textsc{miss},\textsc{flip},\textsc{fake}]$ as $\mathsf{OPT}$.

1\. $[\textsc{miss},\textsc{fake},\textsc{flip}]$: We consider the set of
datasets $S$ achieved after applying miss, fake, and then flip. Fix an
arbitrary $T^{\prime}\in S$. $T^{\prime}$ was constructed from $T$ by some
sequence of adding, removing, and flipping data points. We have these
categories for (potential) data points in $T^{\prime}$: (1) untouched data
points, (2) added data points, (3) added then removed data points, (4) added
then flipped data points, (5) removed data points, and (6) flipped data
points. (1), (2), (5), and (6) apply single (or no) operators, so clearly are
also attainable through $\mathsf{OPT}$. miss occurs before both flip and fake
in $\mathsf{OPT}$, so (3) and (4) are attainable, as well.

2\. $[\textsc{flip},\textsc{miss},\textsc{fake}]$: We consider the set of
datasets $S$ achieved after applying flip, miss, and then fake. Fix an
arbitrary $T^{\prime}\in S$. $T^{\prime}$ was constructed from $T$ by some
sequence of flipping, adding, and removing data points. We have these
categories: (1) untouched data points, (2) flipped data points, (3) flipped
then removed data points, (4) added data points, (5) added then removed data
points, and (6) removed data points. (1), (2), (4), and (6) apply single (or
no) operators, so clearly they are also attainable through $\mathsf{OPT}$.
Since flipping and adding each come before removing in $\mathsf{OPT}$, (3) and
(5) are obtainable as well.

3\. $[\textsc{flip},\textsc{fake},\textsc{miss}]$: We consider the set of
datasets $S$ achieved after applying flip, fake, and then miss. Fix an
arbitrary $T^{\prime}\in S$. $T^{\prime}$ was constructed from $T$ by some
sequence of flipping, removing, and adding data points. We have these
categories: (1) untouched data points, (2) flipped data points, (3) flipped
then removed data points, (4) removed data points, and (5) added data points.
(1), (2), (4), and (5) apply single (or no) operators, so clearly they are
also attainable through $\mathsf{OPT}$. Since flipping comes before removing
in $\mathsf{OPT}$, (3) is obtainable as well.

4\. $[\textsc{fake},\textsc{miss},\textsc{flip}]$: We consider the set of
datasets $S$ achieved after applying fake, miss, and then flip. Fix an
arbitrary $T^{\prime}\in S$. $T^{\prime}$ was constructed from $T$ by some
sequence of removing, adding, and flipping data points. We have these
categories: (1) untouched data points, (2) removed data points, (3) added data
points, (4) added then flipped data points, and (5) added data points. (1),
(2), (4), and (5) apply single (or no) operators, so clearly they are also
attainable through $\mathsf{OPT}$. Since flipping comes before removing in
$\mathsf{OPT}$, (3) is obtainable as well.

5\. $[\textsc{fake},\textsc{flip},\textsc{miss}]$: We consider the set of
datasets $S$ achieved after applying fake, flip, and then miss. Fix an
arbitrary $T^{\prime}\in S$. $T^{\prime}$ was constructed from $T$ by some
sequence of removing, flipping, and adding data points. We have these
categories: (1) untouched data points, (2) removed data points, (3) flipped
data points, and (4) added data points, Each of these apply single (or no)
operators, so clearly they are also attainable through $\mathsf{OPT}$.

We were not able to construct a dataset not also in $\mathsf{OPT}$ through any
other ordering of the operators, therefore, $\mathsf{OPT}$ is optimal. ∎

##  Appendix C Proofs of soundness

#### Proof of Theorem 1

$\mathsf{pr}^{a}$ is sound.

###### Proof.

We show miss as a simple example to illustrate our approach, and then we show
the proof for composite bias. We omit the proofs for flip and fake because
they (like miss) are special cases of composite.

#### Missing data

Given a dataset $T$ with $n$ classes, suppose our bias set is
$\textsc{miss}_{m}^{g}(T)$. Furthermore, suppose that $c_{i}$ samples in $T$
have label $i$. We define $m_{i}\in[0,m]$ to be the number elements we add
with label $i$, and $m^{\prime}_{i}=\sum_{j\neq i}m_{j}$. Then, we can write
the proportion of $i$’s as a function

$F(m_{i},m^{\prime}_{i})=\frac{c_{i}+m_{i}}{|T|+m_{i}+m^{\prime}_{i}}$ (16)

The partial derivatives of $F$ have values $\frac{\delta F}{\delta m_{i}}>0$
and $\frac{\delta F}{\delta m^{\prime}_{i}}<0$ over the entire domain $[0,m]$,
therefore, any conclusions we draw over $\mathbb{R}$ will also apply over the
discrete integer domain. Therefore, to minimize $F$ we choose $m_{i}=0$ and
$m^{\prime}_{i}=m$, and do the reverse to maximize $F$. Thus,
$F_{\min}=\frac{c_{i}}{|T|+m}$ and $F_{\max}=\frac{c_{i}+m}{|T|+m}$. Since
$[F_{\min},F_{\max}]\subseteq\mathsf{pr}^{a}_{i}(\textsc{miss}_{m}^{g}(T))$,
$\mathsf{pr}^{a}$ is sound.

#### Composite

Given a dataset $T$ with $n$ classes, suppose that our bias model is
$B=[\textsc{miss}_{m}^{g_{1}},\textsc{flip}_{l}^{g_{2}},\textsc{fake}_{k}^{g_{3}}]$.
Furthermore, suppose that in $T$, $c_{i}$ samples have label $i$.

First, we consider how many elements we can add, flip, or remove of each
label. Under miss, we can add $m$ of label $i$ for all $i$. Under flip, we can
flip up to $l$ labels from label $i$ to some $j\neq i$, assuming that there
are at least $l$ elements $(x,y)$ that satisfy $g_{2}(x,y)$ and $y=i$.
Similarly, the maximum number of labels we can flip from any label $j\neq i$
to $i$ is bounded both by $l$ and by the number of elements that satisfy
$g_{2}$ and have label $j$. Note that the elements we can flip are not just
limited to $T$: we can also flip any of the newly-added $m$ elements.
Formally, we define $l_{a_{i}}=\min(|\\{(x,y)\in T\mid y=i\land
g_{2}(x,y)\\}|+m,l)$, and $l_{b_{i}}=\min(|\\{(x,y)\in T\mid y\neq i\land
g_{2}(x,y)\\}|+m,l)$. Similarly, under fake we must also consider the elements
added by miss and those flipped from $j\neq i$ to $i$ by flip. Therefore, we
define $k_{a_{i}}=\min(|\\{(x,y)\in T\mid y=i\land
g_{3}(x,y)\\}|+m+l_{b_{i}},k)$ and $k_{b_{i}}=\min(|\\{(x,y)\in T\mid y\neq
i\land g_{3}(x,y)\\}|+m+l_{a_{i}},k)$.

We will show that under the specified bias model, the proportion of $i$’s in
the dataset is always between $(c_{i}-l_{a_{i}}-k_{a_{i}})/(|T|-k_{a_{i}}+m)$
and $(c_{i}+m+l_{b_{i}})/(|T|-k_{b_{i}}+m)$.

Intuitively, we consider how to modify the proportion of $i$’s in $T$. This
proportion decreases by (1) flipping elements from class $i$ to some class
$j\neq i$, (2) removing elements of class $i$, and (3) adding elements of a
class other than $i$. Therefore, the fraction is minimized by doing (1), (2),
and (3) as much as the bias model allows.

Formally, let $m_{i}\in[0,m]$ be the number of elements added with label $i$,
$m^{\prime}_{i}\in[0,m]=\sum_{j\neq i}m_{j}$, $l_{i}\in[0,l_{a_{i}}]$ be the
number of elements flipped from class $i$ to any other class,
$l^{\prime}_{i}\in[0,l_{b_{i}}]=\sum_{j\neq i}l_{i}$, $k_{i}\in[0,k_{a_{i}}]$
be the number of elements removed with label $i$,
$k^{\prime}_{i}\in[0,k_{b_{i}}]=\sum_{j\neq i}k_{i}$.

Then, we can write the proportion of $i$’s as a function

$F(m_{i},m^{\prime}_{i},l_{i},l^{\prime}_{i},k_{i},k^{\prime}_{i})=\frac{c_{i}+m_{i}-l_{i}+l^{\prime}_{i}-k_{i}}{|T|+m_{i}+m^{\prime}_{i}-k_{i}-k^{\prime}_{i}}$
(17)

We consider the partial derivative of $F$ with respect to each variable. For
all input in the domain, we have $\frac{\delta F}{\delta m_{i}}>0$,
$\frac{\delta F}{\delta m^{\prime}_{i}}$ < 0, $\frac{\delta F}{\delta
l_{i}}<0$, $\frac{\delta F}{\delta l^{\prime}_{i}}>0$, $\frac{\delta F}{\delta
k_{i}}<0$, and $\frac{\delta F}{\delta k^{\prime}_{i}}>0$.

Note that each partial derivatives is monotone over all values in the domain.
Thus, they are also monotone over integers, so any conclusions we yield over
the real numbers can be relaxed to integers, as well. To minimize $F$, we will
maximize each variable whose partial derivative is negative, and minimize each
variable whose partial derivative is positive. That is, we choose $m_{i}=0$,
$m^{\prime}_{i}=m$, $l_{i}=l_{a_{i}}$, $l^{\prime}_{i}=0$, $k_{i}=k_{a_{i}}$,
and $k^{\prime}_{i}=0$ to minimize $F$, yielding

$F_{\min}=\frac{c_{i}-l_{a_{i}}-k_{a_{i}}}{|T|+m-k_{a_{i}}}$

Conversely, to maximize $F$ we maximize each variable whose partial derivative
is positive and minimize each variable whose partial derivative is negative,
yielding

$F_{\max}=\frac{c_{i}+m+l_{b_{i}}}{|T|+m-k_{b_{i}}}$

$[F_{\min},F_{\max}]\subseteq\mathsf{pr}^{a}_{i}(B(T)$, therefore,
$\mathsf{pr}^{a}$ is sound.

#### Multiple composite bias models

Suppose

$B=[\textsc{miss}_{m_{1}}^{g^{\prime}_{1}},\ldots,\textsc{miss}_{m_{j}}^{g^{\prime}_{j}},\textsc{flip}_{l_{1}}^{g^{\prime}_{j+1}},\ldots,\textsc{flip}_{l_{p}}^{g^{\prime}_{j+p}},\textsc{fake}_{k_{1}}^{g^{\prime}_{j+p+1}},\ldots,\textsc{fake}_{k_{q}}^{g^{\prime}_{j+p+q}}]$

and

$B^{\prime}=\left[\textsc{miss}_{\sum_{i\in[1,j]}m_{i}}^{\bigvee_{i\in[1,j]}g_{i}},\textsc{flip}_{\sum_{i\in[1,p]}l_{i}}^{\bigvee_{i\in[j+1,j+p]}g_{i}},\textsc{fake}_{\sum_{i\in[1,q]}k_{i}}^{\bigvee_{i\in[j+p+1,j+p+q]}g_{i}}\right]$

We want to show that if $(x,y)\in T\cup T^{\prime}$ is altered by $B$, it can
be altered by $B^{\prime}$ (in other words, we want to show that $B\subseteq
B^{\prime}$).

Case 1: $(x,y)$ was added by a transformer $\textsc{miss}_{m_{i}}^{g_{i}}$ for
$i\in[1,j]$. Therefore, $g_{i}(x)$ and $(\bigvee_{i\in[1,j]}g_{i})(x)$, as
well, so $x$ can be added by
$\textsc{miss}_{\sum_{i\in[1,j]}m_{i}}^{\bigvee_{i\in[1,j]}g_{i}}$.

Case 2: $(x,y)\in T$ was flipped to $(x,y^{\prime})\in T^{\prime}$ by
$\textsc{flip}_{l_{i}}^{g_{j+i}}$ for $i\in[1,p]$. This means that
$g_{j+i}(x)$, so by extension, $(\bigvee_{i\in[j+1,j+p]}g_{i})(x)$, which
means that $x$’s label can be flipped by
$\textsc{flip}_{\sum_{i\in[1,p]}l_{i}}^{\bigvee_{i\in[j+1,j+p]}g_{i}}$.

Case 3: $(x,y)\in T$ was removed by $\textsc{flip}_{k_{i}}^{g_{j+p+i}}$ for
$i\in[1,q]$. This means that $g_{j+p+i}(x)$, and thus
$\bigvee_{i\in[j+p+1,j+p+q]}g_{i}(x)$. Therefore $(x,y)$ can be removed by
$\textsc{fake}_{\sum_{i\in[1,q]}k_{i}}^{\bigvee_{i\in[j+p+1,j+p+q]}g_{i}}$.

To conclude, any modification to $T$ that we can make under $B$ is also
attainable under $B^{\prime}$, therefore, if $B^{\prime}$ is sound, then $B$
is sound, as well. ∎

######  Proposition 1.

Abstract filtering is sound.

###### Proof.

To prove soundness for filtering, we need to show that $T^{\prime}\in
B(T)\implies T^{\prime}_{\phi}\in B(T)_{\phi}$.

#### Missing data

Consider $T^{\prime}\in\textsc{miss}_{m}^{g}(T)$. Since
$T^{\prime}\in\textsc{miss}_{m}^{g}$, we have $T^{\prime}=T\cup S$ where
$|S|\leqslant m$ and $\forall(x,y)\in S.g(x,y)$. Therefore,
$T^{\prime}_{\phi}=T_{\phi}\cup S_{\phi}$. Since $S_{\phi}\subseteq S$, then
$|S_{\phi}|\leqslant m$ and $\forall(x,y)\in S_{\phi}.g(x,y)$. then
$T_{\phi}\cup S_{\phi}\in\textsc{miss}_{m}^{g\land\phi}$, satisfying the
claim.

#### Label flipping

Consider $T^{\prime}\in\textsc{flip}_{l}^{g}(T)$. Since
$T^{\prime}\in\textsc{flip}_{l}^{g}(T)$, we know that $T^{\prime}=R\cup S$
where $R\subseteq T$, $|S|\leqslant l$, and
$T=R\cup\\{(x,y)\mid(x,y^{\prime})\in S\\}$. Additionally, we have $(x,y)\in
S\implies g(x,y)$. Consider $T^{\prime}_{\phi}=R_{\phi}\cup S_{\phi}$. Since
$R\subseteq T$, then $R_{\phi}\subseteq T_{\phi}$. Since $(x,y)\in
S\implies(x,y^{\prime})\in T$ and $\phi$ does not condition on the label, then
$(x,y)\in S_{\phi}\implies(x,y^{\prime})\in T_{\phi}$. Since
$S_{\phi}\subseteq S$, we have $|S_{\phi}|\leqslant l$. In total, this means
that $T_{\phi}\in\textsc{flip}_{l}^{g}(T_{\phi})$.

#### Fake data

See [drews-pldi].

#### Composite

Suppose
$B=[\textsc{miss}_{m}^{g_{1}},\textsc{flip}_{l}^{g_{2}},\textsc{fake}_{k}^{g_{3}}]$.
We want to show that $B(T)_{\phi}\subseteq B^{\prime}(T_{\phi})$, where
$B^{\prime}=[\textsc{miss}_{m}^{g_{1}\land\phi},\textsc{flip}_{l}^{g_{2}},\textsc{fake}_{k}^{g_{3}}]$.
Consider $T^{\prime}\in B(T)$. Each $(x,y)\in T^{\prime}$ satisfies either (i)
$(x,y)\in T$, (ii), $(x,y^{\prime})\in T$ (for $y^{\prime}\neq y$), or (iii)
$(x,y^{\prime})\notin T$. If (i), then $x\in T^{\prime}_{\phi}\implies x\in
T_{\phi}$, and likewise for $\neg\phi$. If (ii), $x\in
T^{\prime}_{\phi}\implies x\in T_{\phi}$ (since $\phi$ ignores the label), and
likewise for $\neg\phi$. If (iii), the $x$ was added by miss. $x\in
T^{\prime}_{\phi}\implies\phi(x)\implies$ $x$ can be added by
$\textsc{miss}_{m}^{g_{1}\land\phi}$, and if $x\notin T_{\phi}$, this means
that $x$ cannot be added by $\textsc{miss}_{m}^{g_{1}\land\phi}$. Finally,
there is a fourth category of elements: those in $T\setminus T^{\prime}$. If
$x\in T\setminus T^{\prime}$, then $x$ was removed by fake. If $\phi(x)$, then
$x$ can be removed from $T$ to make $T^{\prime}$, otherwise, $x$ cannot be
removed from $T$, so it must also be contained in $T^{\prime}$.

Thus we have shown that $T^{\prime}_{\phi}$ can be constructed from $T_{\phi}$
using $B^{\prime}$, therefore, filtering is sound. ∎

######  Proposition 2.

$\mathsf{imp}^{a}$ is sound

###### Proof.

To show that $\mathsf{imp}^{a}$ is sound, we must show that $T^{\prime}\in
B(T)\implies\mathsf{imp}(T^{\prime})\in\mathsf{imp}^{a}(B(T))$. By Theorem 1,
$\mathsf{pr}(T^{\prime})\in\mathsf{pr}(B(T))$. It follows from interval
arithmetic $\mathsf{imp}(T^{\prime})\in\mathsf{imp}^{a}(B(T))$. ∎

######  Proposition 3.

$\mathsf{size}$ is sound.

###### Proof.

Given a bias model $B=[\textsc{miss}_{m}^{g_{1}}$,
$\textsc{flip}_{l}^{g_{2}},\textsc{fake}_{k}^{g_{3}}]$ and a dataset $T$, we
can write the size of $T^{\prime}\in B(T)$ as $|T|-k^{\prime}+m^{\prime}$,
where $k^{\prime}\in[0,k]$ and $m^{\prime}\in[0,m]$. Clearly,
$|T|-k^{\prime}+m^{\prime}$ is minimized by choosing $k^{\prime}=k$ and
$m^{\prime}=0$, and maximized by choosing $k^{\prime}=0$ and $m^{\prime}=m$.
Since $|T|-k\in\mathsf{size}(B)$ and $|T|+m\in\mathsf{size}(B)$, we see that
$\mathsf{size}$ is sound. ∎

######  Proposition 4.

$\mathsf{cost}^{a}$ is sound.

###### Proof.

We need to show that if $T^{\prime}\in B(T)$ and $\phi\in\Phi$, then
$\mathsf{cost}(T^{\prime},\phi)\in\mathsf{cost}^{a}(B(T),\phi)$. By
Proposition 1, we know that $T^{\prime}_{\phi}\in B(T)_{\phi}$, which means
that by Proposition 3, $|T^{\prime}_{\phi}|\in\mathsf{size}(B(T)_{\phi})$, and
similarly we can derive that
$|T^{\prime}_{\neg\phi}|\in\mathsf{size}(B(T)_{\neg\phi})$. Additionally, by
Proposition 2, we know that
$\mathsf{imp}(T^{\prime}_{\phi})\in\mathsf{imp}^{a}(B(T)_{\phi})$ and
$\mathsf{imp}(T^{\prime}_{\neg\phi})\in\mathsf{imp}^{a}(B(T)_{\neg\phi})$. By
the rules of interval arithmetic, if $a\in[a_{0},a_{1}]$ and
$b\in[b_{0},b_{1}]$, then $ab\in[a_{0},a_{1}]\times[b_{0},b_{1}]$ and
$a+b\in[a_{0},a_{1}]+[b_{0},b_{1}]$. Therefore we can conclude that
$\mathsf{cost}(T^{\prime},\phi)\in\mathsf{cost}^{a}(B(T),\phi)$, i.e.,
$\mathsf{cost}^{a}$ is sound. ∎

######  Proposition 5.

$\mathsf{split}^{a}$ is sound.

###### Proof.

We want to show that if $T^{\prime}\in B(T)$, then
$\mathsf{split}(T^{\prime})\in\mathsf{split}^{a}(B(T))$.

Suppose $\gamma=\mathsf{split}(T^{\prime})$. Then, $\forall\phi\in\Phi$,
$\mathsf{cost}(T^{\prime},\phi)\geq\mathsf{cost}(T^{\prime},\gamma)$.

Define $\phi^{*}$ such that $\mathit{lub}=ub(\mathsf{cost}(T,\phi^{*}))$,
where $ub$ takes the upper bound of an interval. Since $\phi^{*}\in\Phi$,
$\mathsf{cost}(T^{\prime},\gamma)\leqslant\mathsf{cost}(T^{\prime},\phi^{*})$.
By Proposition 4, $\mathsf{cost}$ is sound, therefore
$\mathsf{cost}(T^{\prime},\gamma)\in\mathsf{cost}^{a}(B(T),\gamma)$ and
$\mathsf{cost}(T^{\prime},\phi^{*})\in\mathsf{cost}^{a}(B(T),\phi^{*})$. And
thus we have $lb(\mathsf{cost}^{a}(B(T),\gamma))\leqslant
ub(\mathsf{cost}^{a}(B(T),\phi^{*}))=\mathit{lub}$. Thus,
$\gamma\in\mathsf{split}^{a}(B(T))$. ∎

#### Proof of Theorem 2

###### Proof.

Given $\Phi^{a}=\mathsf{split}^{a}(B(T))$, if
$|\mathsf{infer}^{a}(B(T),\Phi^{a},x)|=1$, then we know

$\exists y.\forall\phi\in\Phi^{a}.\begin{cases}\textrm{if }\phi(x)\textrm{
then }\operatorname*{argmax}_{i}\mathsf{pr}^{a}_{i}(B(T)_{\phi})=y\\\
\textrm{if }\neg\phi(x)\textrm{ then
}\operatorname*{argmax}_{i}\mathsf{pr}^{a}_{i}(B(T)_{\neg\phi})=y\end{cases}$

Given $T^{\prime}\in B(T)$, we know from Proposition 5 that
$\mathsf{split}(T^{\prime})\in\mathsf{split}^{a}(T)=\Phi^{a}(T)$. Therefore,
$\mathsf{infer}(T^{\prime},\mathsf{split}(T^{\prime}),x)=y$, so the algorithm
is robust on $x$. (Note that we defined $B(T)$ such that $T\in B(T)$,
therefore, the original prediction is also $y$.) ∎

##  Appendix D Precision

Intuitively, an abstraction is precise if the abstraction cannot be improved.
Formally, our abstraction is precise iff, it is sound and given
$\mathsf{pr}^{a}_{i}(B(T))=[a_{i},b_{i}]$, then for each $i$ there is some
$T^{\prime}\in B(T)$ such that $\mathsf{pr}_{i}(T^{\prime})=a_{i}$ and some
$T^{\prime\prime}\in B(T)$ such that
$\mathsf{pr}_{i}(T^{\prime\prime})=b_{i}$.

######  Theorem 5.

$\mathsf{pr}^{a}$ is precise for missing data, label-flipping, and fake data.

###### Proof.

#### Missing data (non-targeted)

In the proof of Theorem 1, we show that the minimum proportion of $i$’s is
$\frac{c_{i}}{|T|+m}$ and the maximum proportion of $i$’s is
$\frac{c_{i}+m}{|T|+m}$. Since these bounds are equal to $\mathsf{pr}^{a}$’s
minimum and maximum, the interval is precise.

Proofs for label-flipping and fake data (non-targeted) similarly follow from
Theorem 1.

#### Targeted

Next, we will show that the definitions of $\mathsf{pr}^{a}$ provided in
Equations 12-14 are precise. First, we must show that these definitions are
sound (as soundness is a prerequisite for precision).

To show that Eq. 12 is sound, we need to consider three cases (we use $S$ such
that $g(x,y)=y\in S\land g^{\prime}(x)$): first, $i\in S$ and $|S|=1$. In this
case, we can add up to $m$ elements of class $i$, and no elements of class
$j\neq i$. Therefore, the minimum proportion of $i$’s is the original
proportion: $\frac{c_{i}}{|T|}$, and the maximum is $\frac{c_{i}+m}{|T|}$.
Second, $i\in S$ and $|S|\geq 2$. In this case, we can add elements with label
$i$ but we can also add elements with label $j\neq i$. As such, the minimum
proportion of $i$’s is achieved by adding $m$ elements with label $j$, and the
maximum proportion of $i$’s is achieved by adding $m$ elements with label $i$.
Therefore, the minimum proportion of $i$’s is $\frac{c_{i}}{|T|+m}$ and the
maximum proportion of $i$’s is $\frac{c_{i}+m}{|T|+m}$.

Proofs of soundness for Equations 13 and 14 follow similarly.

To show precision, note that in the soundness proof we described exactly how
to achieve the minimum and maximum bounds of $\mathsf{pr}^{a}_{i}$. As such,
we have shown that the $\mathsf{pr}^{a}$ definition in Eq. 12 is precise.
(Similar conclusions can be drawn based on the proofs for label-flipping and
fake data.) ∎

$\mathsf{pr}^{a}$ is not precise for composite bias because the auxiliary
variables $l_{a_{i}},l_{b_{i}},k_{a_{i}}$, and $k_{b_{i}}$ are over-
approximate. As a motivating example, consider a bias model
$[\textsc{miss}_{1},\textsc{flip}_{2}^{g}]$ over dataset $T$ with classes
$\\{0,1\\}$ where $c_{0}=2$, $c_{1}=5$, and $|\\{(x,y)\in T:g(x,y)\land
i=0\\}|=1$. By definition, $l_{a_{0}}=2$, yielding a minimum proportion of 0’s
to be $\frac{2-2}{7+2}=0$. However, the precise lower bound is $\frac{1}{9}$:
to minimize the proportion of 0’s, we add 2 elements with label 1 and flip the
element that satisfies $g$ from label 0 to label 1.

##  Appendix E Additional experimental data

###  E.1 MNIST 1/7 Binary

We used MNIST 1/7 (the limitation of MNIST to just 1’s and 7’s, with training
$n$=13007, as has been used in works including [drews-pldi, steinhardt-
certified]). We round each pixel to 0 or 1 (i.e., used a black-and-white image
rather than a grayscale one). The accuracy of MNIST 1/7 binary (97.4% at depth
2) is comparable to that of MNIST 1/7, but the time and memory requirements on
Antidote-P are much less.

LABEL:tab:mnist_data shows effectiveness data for MNIST 1/7 binary. We see
that we are able to achieve high robustness certification rates, despite
incredibly large perturbation set sizes. Notable, for $\textsc{miss}_{0.1\%}$,
we achieve 100% robustness even with a perturbation set size of over
$10^{3058}$, and for $\textsc{miss}_{1\%}$, we achieve 68% robustness with a
perturbation set size larger than $10^{30460}$.

###  E.2 Performance

We performed experiments on a HTCondor system, allowing us to perform many
experiments in parallel. Each experiment ran a robustness test on a given bias
model and dataset for between one and 1000 test samples (depending on the bias
model and dataset). We used a single CPU for each experiment, and requested
between 1 and 96GB of memory, depending on the bias model and dataset.

#### Bias model

Time and memory requirements increase exponentially as the amount of bias
increases (e.g., 0.5 seconds for $\textsc{miss}_{0.05\%}$ and 810 seconds for
$\textsc{miss}_{0.4\%}$ on Adult Income). Additionally, bias models that yield
lower certifiable robustness for a given bias threshold have correspondingly
larger time and memory requirements (e.g., 810s and 9.7GB of memory to yield
34.8% robustness for $\textsc{flip}_{0.4\%}$ as compared with 77s and 1.3GB of
memory to yield 60.3% robustness for $\textsc{miss}_{0.4\%}$).

#### Datasets

The size and complexity of the feature space is most influential in
determining time and memory requirements. Experiments on the Adult Income
dataset were more resource-intensive than those on Drug Consumption or COMPAS,
a fact that can be explained by Adult Income having more unique feature values
than the other datasets (22,100 for Adult Income vs. 219 for Drug Consumption
and 53 for COMPAS). For each unique value of any feature, the algorithm checks
an additional predicate, which explains the additional time and memory needs.

#### Complexity of decision-tree algorithm

Increasing the depth of the decision tree not only requires additional time to
essentially re-run the algorithm at each internal node, but also leads to
lower certifiable-robustness rates, as shown in Table 1. This is because we
must assume worst-case bias in each node. Intuitively, a depth 2 tree with
0.1% bias may initially split the data into two children nodes, each with 50%
of the data. Our abstraction captures both the case where all bias occurs in
the left child, and the case when all bias occurs in the right child.
Therefore, we end up with an effective bias rate of 0.2% in either child,
yielding lower robustness.

Table 1: Robustness certification rates of COMPAS and Drug-Consumption datasets under flip for different decision-tree depths. Poisoning amount (%) | COMPAS | Drug Consumption
---|---|---
depth 1 | 2 | 3 | depth 1 | 2 | 3
0.10 | 71.5 | 51.5 | 34.0 | 94.5 | 83.8 | 8.5
0.20 | 47.8 | 27.7 | 23.9 | 94.5 | 55.9 | 4.5
0.50 | 9.3 | 2.5 | 0.7 | 85.1 | 27.5 | 0.5
1.00 | 3.0 | 0.7 | 0 | 7.1 | 0.8 | 0

###  E.3 Additional experimental data

#### General data

LABEL:fig:all_data shows the certifiable robustness rates for each dataset and
each main bias model (miss, flip, miss \+ fake, and miss \+ flip).

#### Demographic data

LABEL:fig:extra_demo shows robustness levels stratified by demographic groups
on various bias models. We see that COMPAS under miss (LABEL:fig:extra_demob)
displays similar robustness gaps to flip; namely, White people, and
particularly White women, are robust at a higher rate than Black people. Adult
Income under miss (LABEL:fig:extra_democ) and under $\textsc{flip}^{g}$ where
$g\triangleq(\emph{gender}=\textrm{female}\land\emph{label}=\textrm{negative}$)
(LABEL:fig:extra_demod) behaves similarly to Adult Income under flip
(LABEL:fig:demo). That is, all demographic groups have roughly comparable
robustness rates. Drug consumption under flip (LABEL:fig:extra_demoa) yields
comparable robustness rates between men and women (we do not graph robustness
rates by racial group because the dataset is over 91% White).

###  E.4 Additional details on random testing

On a random subset of 100 test elements from the COMPAS dataset, we tested
10000 dataset perturbations under $\textsc{flip}_{0.5\%}$,
$\textsc{flip}_{1\%}$, $\textsc{flip}_{2\%}$, and $\textsc{flip}_{3\%}$. The
number of elements for which we found a counter-example to robustness (i.e., a
dataset perturbation that resulted in a different classification) is shown in
Table 2. We see that we are able to find counterexamples to robustness for a
non-trivial portion of test samples. However, the gap between certified-
robustness and proved-non-robust rates is still wide (the gap ranges from
86.7% for $\textsc{flip}_{0.5\%}$ to 68.0% for $\textsc{flip}_{3\%}$). As a
result, there are many test samples that we cannot prove robustness for, but
cannot find counterexamples for either. Future work to use a more precise
abstract domain, or to better identify counterexamples to robustness could
help to narrow this gap.

Table 2: Number of elements with counterexamples to robustness after 10000 iterations of random testing from a subset of 100 test samples from COMPAS. All bias models are flip, and bias level refers to number of affected elements as a percentage of training dataset size. Bias level | # of elements with counterexample
---|---
0.5 | 4
1.0 | 15
2.0 | 27
3.0 | 32

Breaking down the results for $\textsc{flip}_{3\%}$ further, we found
counterexamples to robustness for 50% of Black women, 37% of Black men, 29% of
White women, and 27% of White men. Similarly, we found more counter-examples
to robustness for Black people using other bias models. The empirical result
of having more counterexamples for test instances representing Black people
combined with the fact that we are able to certify a smaller percentage of
test instances representing Black people (§ 5.2) suggests that the robustness
differences are inherent to the data, rather than a property of the
abstraction.