Certifying Robustness to Programmable Data Bias in Decision Trees
Authors: Anna P. Meyer
Aws Albarghouthi
Loris D'Antoni
Venue: NeurIPS 2021 Poster (2021)
Keywords: data bias
data poisoning
robustness
decision trees
fairness

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 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 \emph{bias models} across a variety of dimensions (e.g., label-flipping or missing data), 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.

Certifying Robustness to Programmable Data Bias in Decision Trees
Anna P. Meyer, Aws Albarghouthi, and Loris D' D'Antoni
Department of Computer Sciences University of Wisconsin- Maddison
Madison, WI 53706 (annameyer, aws, loris @ecs. wisc.
Abstract
Datasets be biased due to societal inequities, human biases, under- representation of minorities, etc. Our goal is to certify that models produced by learning algorithm are pointwise-robus/ to potential dataset biases. This is challenging problem: it entails learning models for a large, or even infinite, num- ber 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 variety of dimensions (e.g., missing data for minorities), composing types of bias, and targeting bias towards specific group. To certify robustness, we use a novel symbolic technique to evaluate decision-tree tree learner on a large, or infinite, number of datasets, certi- fying 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 range of bias models.
1 Introduction
The proliferation of machine-learning algorithms has raised alarming questions about fairness in automated decision-making [4) In this paper, we focus attention on bias in training data. Data can be biased due to societal inequities, human biases, under-representation minorities, malicious data poisoning, etc. For instance, historical data can contain human biases, c.g., certain individuals' loan requests get rejected, although (if discrimination were not present) they should have been approved, women in certain departments consistently given lower performance scores by managers.
Given biased training data, we are often unable to de-bias because we not know which samples are affected. This paper asks, can we certify (prove) that our predictions are robust under given form and degree of bias 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-flippngg (31). or (ii) perform certification using defenses that create complex, uninterpretable classifiers, e.g., due to randomization
ensembling [3] 24 31).
To address limitation (i), we present programmable bias definitions that model nuanced biases in practical domains. To address (ii), target existing decision-tree carmers-considered interpretable and desirable for sensitive decision- decision-making (32 -and exactly certify their robustness, i.c., provide proof's 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. 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 generic, allowing
Author's 's name in native alphabet: الرغوق أوب
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Training data N
Decision frow learned from training dltta
Abstract deciston tree learned from blas model: up to black person may have recetved wrong negative label
Iscare 3]
true
fulse
true
falst
Sabal
K
Nete fiat no elenest of mrnning dats her score =4
x woth proB. 1
with prob. 0.8
x mith prohh [0.75.1]
of with prob. [0.8.1]
Figure 1: A simple, hypothetical running example
us to compase simpler bias models into more complex ones, e.g., up to n% of the women may have wrongly received negative evaluation and up to m% of Black men's 's records may have been completely missed. The choice of bias model depends on the provenance of the data and the task.
After specifying bias model, our goal is to certify pointwise robustness to data bias: Given input I, we want to ensure that no matter whether the training data is biased or not, the resulting model's s prediction for æ remains the same. Certifying pointwise robustness challenging. One can train a model for every perturbation (as per a bias model) of a dataset and make sure they all agrec. But this 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 102 possible perturbed datasets.
To perform bias-robustness certification on decision-tree learners, we employ abstract interpreta- tion [12 symbolically run the pecision-tree-leamiin algorithm on large or infinite of datasets simullaneously thus learning a sel 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 al.'s [16) demonstration of poisoning-robuss 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-robust problem and handle complex bias models, including ones that may result in an infinite number of datasets.
Contributions. We make three contributions: (1) We formalize the bias-robustness--crtfffclll problem and present a language to compositionally define bias models. (2) We present a symbolic technique that performs decision-tree learning on a of datasets defined by bias model, allowing us to perform certification. (3) We evaluate our approach on number of bias models and datasets from the fairness literature. Our tool can certify pointwise robustness for variety of bias models; we also show that some datasets have umequal abbusmess--erttficatte
rates across demographics groups.
Running example. Consider the example in Fig. 1 our goal is classify who should be hired based on a test score. A standard decision-tree. tree-learning algorithm would choose the split (predicate) score & 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 person with score >> 3 is accepted, because the proportion ("probability") of the data with positive labels and score 3 is 4/5 (> 1/2).
Now suppose that our bias model says that up to one Black person 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 I will not change. As described above, training decision trees for all possible modified datasets is generally intractable. Instead, we symbolically learn set of possible decision trees compactly, as illustrated in Fig. (right). In this case the learning algorithm always chooses score < 3 (generally, 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 1. To efficiently perform this calculation, we lift the learning algorithm's 's operations interval arithmetic and represent the probability as [0.8, 1]. Given a new test sample x = (race=Black, score=7), follow the right branch and, since the interval is always larger than 0.5, we certify that
*Other predicates, e.g., score & 4, will yield the same split. We choose a single split for illustrative purposes here. (The implementation considers all possible splits that yield distinct partitions, so it would consider score 3 and score & as single entity.)
2

---

the algorithm is robust for z. 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 [6
11
25
33
40 or on training models that 36 Our work differs along a number of
38
39
are empirically less vulnerable (defenses) 3
9 19
28
31
dimensions: (I) We allow programmatic, custom, composable definitions of bias models; notably, to our knowledge, no other work in this space allows for targeted bias, i.c., restricting bias to a particular subgroup. (2) Our work aims to certify and quantify robustness of an existing decision- algorithm, not to modify it (e.g., via bagging or randomized smoothing) to improve robustness [33 24 31).
Statistical defenses show that a learner is robust with high probability, often by modifying a base
learner using, e.g., randomized smoothing (31), outlier detection [36), or bagging [22] 23 Non-
statistical certification (including abstract interpretation) has mainly focused on test-time robustness, where the vicinity (e.g., within an l norm) of an input is proved to receive the same prediction (2) Test-time robustness is a simpler problem than our train-time robustness problem
21 30 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. (16) 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 programmable, rather than fixed, to mimic real- world bias scenarios, an idea that has gained traction in a variety of domains, e.g.. NLP (4T). (2) We lift algorithm 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.
35 37
Ties to fairness. The notion of individual fairness specifies that similar individuals should receive similar predictions [18]: 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
(7]. Data bias, in particular, has received some attention in the fairness literature. Chen et al. suggest adding missing data
effective approach to remedying bias in machine learning (10), which is one operation that our bias language captures.
Mandal al. build on the field of distributional robustness (5] 27 34 to build classifiers that
empirically group-fair across a variety of nearby distributions [66]. Our problem domain is related to
distributional robustness because we certify robustness over family of similar datasets; however, we define specific tito-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 B 14). Much of the work concerns outlier detection for various learning settings, e.g., estimating (1) We deal with rich, nuanced bias models,
parameters of a Gaussian. The distinctions are two-fold: as opposed to out-of -istrribbitt samples, and (2) we aim to certify that predictions are robust for specific input, a guarantee that cannot be made by robust-staatistic--ass techniques 15)
3 Defining data bias programmatically
We define the bias-robustness problem and a language for defining bias models programmatically;
Bias models. A dataset T C X x x is a set of pairs of samples and labels, where y = {0, , n 1}. For dataset T. we will use Tx to denote {a (z. y) E T A bias model B is function that takes dataset and returns set of datasets. We call B(T) C 2 a bias set. We assume that T E B(T). Intuitively, BT) represents all datasets that could have existed had there been bias.
Pointwise dita-bias robustness. Assume we have a learning algorithm that, given a training dataset T, deterministically returns a classifier hy from some hypothesis class H. Fix a dataset T and bias model B. Given a sample x E X, we say that is pointwise robust (or robust for short) on x iff
there is a label such that for all T' E B(T), we have (2)
(I)
3

---

Basic components of a bias model. We begin with basic bias models.
Missing data: A common bias in datasets is missing data, which can oceur via poor historical representation of a subgroup (e.g., women in CS-department admissions data), or from present-day biases or shortsightedness (e.g., survey that bypasses low-income neighborhoods). Using the parameter m as the maximum number of missing elements, we formally define:
MISS (7) = (T') T'2T, (T")T) & m}
MISS,, (T) defines an infinite number datasets when the sample space is infinite (e.g., R--alledd. Example 3.1. Using T from Fig. / I (Te) is the set of all datasets that are either T or Tex 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 amployee-perfrmmanee data, where women in certain departments are consistently given lower scores by managers. We model such biases label flipping, where labels of up to individuals in the dataset may be incorrect:
FLIP, (T) (T' 1T7- [T' < L, Tx Tx}
Example 3.2. Using T from Fig. 7 and bias model FLIP1, have FT.IP; (Te) (70%
73%
T5 ..... Tgx ]e),, where T is I with the label of the element with score = i changed.
Fake data: Our final bias model assumes the dataset may contain fake data. One cause may be 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, c.g,, we over-collected data for men.
(T) = (T' T'ST, ITTT < k}
Example 3.3. Using Tex from Fig. 1 and bias model FAKE get FAKE, (1 (T T Tg. } where Tyx is T such that the element with score i has been removed.
T
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 gender female. Formally, we define predicate g X x B, where B- = [true, false).
MISS m (T) = (T' 1' (T & m, and g(z, y) is true V(r v) E (T' T))
Targeted versions of label-flipping and fake data can be defined in a similar way.
Example 3.4. In Fig. (right), used bias model FLIP where g targets Black people with negative labels. This results in the bias set FLIP" = (TTx, Tex Tex, where T is T with the label of the element with score changed (recall that scores 1 and 8 belong Black people in )x))
Composite bias models. We can compose basic components to generate a composite model. Specifi- cally, we define a composite model B as a finite set of arbitrary basic components, that is, MISS m
B
MISS m, FLIP
FLIP,:*> FAKE ..... FAKE FAKE
(2)
B(T) is generated from T by applying the basic components of B iteratively. We must apply the constituent components an optimal order, i.c., 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 [MISS]] FAKE,] ]. Then B(T) is the set of all datasets obtained by adding up arbitrary data points that satisfy 9i to T, and then removing any up to 1 data point.
4 Certifying robustness for decision-tree learning
We begin with simplified version of the CART algorithm
88, which is our target for certification.
Given dataset T and Boolean function (predicate) X B, define:
T3 (0,,)) E T Φ(z)), i... T' is the set of elements satisfying ø. Analogously, T-2 {xx v) TTI -6(z)).

---

Example 4.1. Using & score & 3, we have T = (,,1,2.3 and T = 7,8,9.
Learning algorithm. To formalize our approach, it suffices to consider a simple algorithm that learns a decision stump, i.., a tree of depth Therefore, the job of the algorithm is to choose predicate (splitting rule) é from set of predicates & that optimally splits the dataset T into two datasets. Formally, we define pr, (T) as the proportion of with label i, i.c.
(T) = K(x, i) E /
(3)
We use pr to calculate Gini impurity (imp), that is,
imp(T) Σ pr pr, (rr(
Using imp, assign each dataset-predicat pair a cost, where a low value indicates that øi splits T cleanly, i... elements of To (conversely, T-2) have mostly the same label:
cost(T, 6) Tpl imp(TT) ) + (T-Øl imp(T-0)
Finally, we select the predicate that results in the lowest cost (we break ties arbitrarily), as defined by the split operator:
split(T) argmin cost(T, #
Example 4.2. For @ score & 3, cost (b) = 4 x 0 + x 0.32 1.6.
Inference. Given an optimal predicate & 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,
infer (T, o, x)) argmax pr, (Tx),
where o' is o if ((x) true; otherwise, o' is m
4.1 Certifying bias robustness with abstraction
Given a dataset T, bias model B, and sample r, our goal is to prove robustness (Eq. (T) no matter which dataset in (TT) was used to learn decision tree, the predicted label of is the same. Formally,
there is label s.t. for all T' B(T), infer(T', &', x)) i, where o' split(T')
(4)
The naive way prove this learn decision using each dataset B(') and compare the results. This approach is intractable or impossible, as [B"))) may be combinatorially large or infinite.
Instead, abstractly evaluate the ceeision-tree-leamiie algorithm the entire bias set B(T) in a symbolic fashion, without having to enumerate all datasets. Specifically, for each operator in the algorithm, we define abstract analogue, called abstract transformer (12). 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 the BTT).
Sound abstract transformers. Consider the pr, operator, which takes a dataset and returns a real number. We define abstract transformer pr; (B)))) that takes set of datasets (defined as bias set) and returns an interval, i.c., a subset of R. The resulting interval defines a range of possible values for the probability of class i. E.g., interval pr (B(T)) may be 10.1, 0.3], meaning that the proportion of i-labeled elements in datasets B(T) is between 0.1 and 0.3, inclusive.
Given intervals computed by pr² downstream operators will be lifted into interval arithmetic, which fairly standard. E.g., for a, b, c, E R, (a, b) [c, d]
c, b + d]. It will be clear from context when we are applying arithmetic operators to intervals. For a sequence {ara J. of intervals, argmax, x; returns a set of possible indices, as intervals may overlap and there may be no unique maximum.
Example 4.3. Let 1 {[1,2] 2), 8), [6, 7]. [4, 5]). Then max(T) ([4,8]. [6. 7]} because the greatest lower bound of 1, and [4, and [6, 7| the only intervals in I that contain 6.
5

---

For the entire certification procedure to be correct, pr" and all other abstract transformers must be sound. That is, they should aver-approximate the of possible outputs. Formally, pr is a sound approximation of pr, iff for all i and all T' E B(T),, we have (T)) E (B(T))
abstract transformer split" (B(T)) to compute a set of best predicates da for BT)). The reason split" returns a set of predicates is because its imput set of datasets that may result in different optimal splits. Then, we use an abstract transformer infer" (BTT), d" x) to compute a set of labels for x. If infer" returns a singleton set, then we have proven pointwise robustness for x (Eq. 44); otherwise, we have an inconclusive result we cannot falsify robustness because abstract transformers are over-approximate.
Certification process. To perform certification,
4.2 Abstract transformers for pr
We focus the most challenging transformer, pr"; in 4.3 we show the rest of the transformers.
Abstracting missing data. We begin by describing pr for missing data bias, B MISS From now on, we use G to denote the number of samples (x,1) v) E T with = i. We define prä 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 + i; to maximize the fraction of i's, we add m elements with label i.
C: m
Pr (MISS (T))
[ m
T + m
Example 4.4. Given B = J, we have pro (B(Te))) = + f
Abstracting subel-flipping. Next, we define pr for babel-flipping bias, where B = FLIP,. Intuitively, can minimize the proportion of i's by flipping I labels from to * and maximize the proportion of i's by flipping labels from j * to i. The caveat here that if there are fewer than I of whichever label want flip, we are limited by G; or Ejjs Cj. depending
flipping direction.
[ min(l, cs) 4: + min(1, Eÿzi ei)
Pr (FLIP, =
[T]
[T]
Example 4.5. Given B = FL we have pr (B(T*)) = 4 Q
9
Fake data bias models can be abstracted similarly (see Appendix).
Abstracting targeted bias models. We now show how to abstract targeted bias models, where function g restricts the affected samples. To begin, we limit g to only condition on features, not the label. In the case of MISSS, the definition of pr 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 / to be no larger than [Tyl. Formally, we define 4 min ( E T g))))) and then
C4 - 4 T
minnin min 1.11) [T]
(FLII(
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 pr for that scenario.
Abstracting composite bias models. Now consider composite bias model consisting of all the basic bias models. Intuitively, pr. will need to reflect changes in & that occur from adding data, flipping labels, and removing data. First,
consider bias model with just one instance of each MISS, FLIP, and FAKE, Le.. B = [MISS; FLIP FAKE ]. We define auxiliary variables 4 = min(t, K( i) T (z H) and K; = min(k, (xx i) T 9a(x, H)H Intuitively, these variables represent the number of elements with label that we can alter. Conversely, to represent the elements with label other than i, we will use min(l, Ejfs(l)) and K min Ej4ıC,).
pr pr(()) max 00,
C. 4 Ks
min
1
G 1
(8)
[T]
K; + m
K
Extending the above definition to allow multiple uses of the same basic model, e.g., {FLIP]) FLIP is simple: essentially, we just sum 4 and l2. A full formal definition is in the Appendix.

---

Theorem 1. pr is sound abstract transformer. (In the Appendix, we also show that pr 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. [16]: the key difference the Ta operation, which is dependent on the bias model.
Filtering. We need B(T),, the abstract analogue of To. For FLIP and FAKE, we define B(T), B(T)). But for MISS, have alter the bias model, too, since after filtering Φ only want to add new elements that satisfy 6. We define MISS, (T)) MISS (To). Filtering composite bias models applies these definitions piece-wise (see a full definition and soundness proof in the Appendix).
Gini impurity. We lift imp to interval arithmetic: imp" = pr (T7(1 - (T))
Cost. Recall that cost relies on [Tol. We want an abstract analogue of [To] that represents the range of sizes of datasets B(T), and not the number datasets in BT)) To this end, we define an auxiliary function size where size( (()))) = (a. bj such that = min T" E B(T))) and b max ([T : T' E B.
Then, we define the cost of splitting on ø as follows (recall that the operators use interval arithmetic):
cost (B(t) Φ) size(B(()) x (B()))) + (BT)) x imp" (B(()=p)
(9)
Since size and imp" return intervals, cost will be an interval, as well.
Best split. To find the set of best predicates, we identify the least upper bound (lub) of any predicate's 's cost. Then, any predicate whose cost overlaps with lub will be member of the set of best predicates. too. Formally, lub minse bø, where cost" = [as by] Then, we define split" (B(T)) {Ø
ag < lub).
Inference. Finally, for inference, we evaluate every predicate computed by split" on x and collect all possible prediction labels. Intuitively, we break the problem into two pieces: first, we evaluate all predicates & that satisfy ((x) (i.e., when x is sent down the left branch of the tree), and then predicates that satisfy ~)(x), (i.e., when æ is sent down the right branch of the tree). Formally, compute:
infer" (B(T), th ,x) = U argmax (B(T))) U U argmax (B(T)-
(10)
o(x)
labels predicates d(w)
labels prodicates & -o(x)
where the range of U is over predicates in 4a, Since our goal is to prove robustness, we only care whether linfer" (T),,, &" x:] i.e. all datasets produce the same prediction.
Theorem 2. If linfer" (T))), 6" x)1 where th split" (B(T)), then is robust (Eq. (4).
Example 4.6. Recall Fig. 7 with bias model B FLIP? where g targets Black people with label. split" (B(Te)) returns the singleton set tha = {score & 3). Then, given inpul x: (race Black, score 7), infer*(B(TT 66 x)) [V}. since pr" (B(Te) score>3) [0.8, which is greater than pr (B(T score>3) = 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 [16] to programmable bias models. To learn trees with depth recursively. We use Antidote's disjunctive domain, which is beneficial for certification [16] 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 [17] (training n=32,561), COMPAS (29 (n=4629), and Drug Consumption (20] (n=1262). A fourth dataset, MNIST 1/7 (x=13,007) is in the Appendix. For all datasets, we use the standard train/test split if one is provided; otherwise, we create our own train/test splits, which are available our code repository at wihhtps:://ggt thub. com annapmeyer/////
we apply the presented procedure
antidote-P
7

---

Table 1: Certification rates for various bias models. Targeted bias models use predicates (race Black and label = positive) for COMPAS and (gender female and label = negative) for Adult Income. Composite models show cumulative bias, e.g. 0.2% MISS FAKE bias equates to 0.1% 1% bias of each MISS and FAKE. Empty entries indicate tests that failed due to memory constraints (9GGB).
Bias amount as a percentage of training set
Bias type
Dataset
0.05
0.1
0.2
0.4
0.7
1.0
Drug Consumption
94.5
94.5
94.5
94.5
85.1
85.1
COMPAS
89.0
81.9
52.9
45.3
9.3
9.2
MISS (missing data)
Adult Income (AI)
96.0
86.9
72.8
60.9
COMPAS targeted
89.0
89.0
81.9
52.9
47.8
42.3
AT targeted
98.8
97.2
86.6
73.0
62.0
31.6
Drug Consumption
94.5
94.5
94.5
92.1
85.1
7.1
COMPAS
81.9
71.5
47.8
20.6
3.0
3.0
FL.IP (label- -lipppg))
Adult Income
95.8
72.9
70.2
34.8
COMPAS targeted
89.0
81.9
71.5
50.5
43.2
24.2
Al targeted
98.6
97.0
74.4
71.0
45.4
25.8
Drug Consumption
94.5
94.5
94.5
94.5
85.1
85.1
MISS + FAKE (missing fake)
COMPAS
81.9
76.2
52.9
43.2
9.3
9.3
Adult Income
96.0
95.6
72.8
68.3
36.2
Drug Consumption COMPAS
94.5
94.5
92.1
92.1
85.1
38.0
MISS + FLIP
81.9
71.5
50.5
41.6
9.3
3.0
(missing label-flpppnng
Adult Income
95.9
74.3
71.1
49.0
Bias-set size color scheme
10
10
10 00
<
500
10
infinite
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 (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 to evaluate how tree depth influences Antidote-P's efficiency (see Appendix).
natural baseline enumerating all datasets in the bias set but that is infeasible-see bias-set sizes in T To our knowledge, our technique (extended from 16) [6), is the only method to certify bias robustness of decision-tree learners.
5.1 Effectiveness certifying robustness
Table 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()) We see that even though the perturbation sets very large sometimes infinite- are able to certify robustness for significant percentage of elements.
By dataset. Certification rates vary from 100% robustness for MISS 91888.19 the predictions of each point in the test set does not change up to 0. new points are added to the training set) to just 3% robustness for FLIP 1% on COMPAS. Even for a single bias model, the certification rates vary widely: under 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 normalized cost of the optimal top-most split is 0.30 for Adult Income, 0.35 for Drug Consumption, and 0.45 for COMPAS (recall that lower 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.
Adult Income (i.e.,
By bias model. There are also differences certification rates between bias models. FLIP is more destructive to robustness because flipping single label results in symmetric difference of 2 from the original dataset (as if we removed an element from the set and then inserted a new one with flipped label), while adding single item results in symmetric difference of 1.

---

White men
Conitible mitueness (1B)
White women
80
60
Black
40
20
0.4
0.4
0.4
0.8
0.2
Bias amsount (%6
Figure 2: Left to right: Certifiable robustness by demographic group on (a) COMPAS under FLIP; (b) COMPAS under FLIP" where g - (race Black label = positive); (c) COMPAS under FLIP" where g - (race White A label negative); (d) Adult Income under FL.IP
The composite bias models display similar dataset- and bias model-based trends. Notably, MISS + FAKE yields lower certifiale-robustnees rate than FLIP. E.g., under FLIP 0.1% we can certify 71.5% of COMPAS test samples as robust. But for MISS NISSo.1% + FAKE 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 useful modeling tool for situations where we believe the features of all data points be trustworthy, but suspect that some labels may be incorrect. The targeted bias models allow for greater certification rates than the non-targee 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 properties of the dataset such as separability.
5.2 Demographie variations
We evaluated differences in certifiable-robustee rates across demographic groups all three datasets. We present results from COMPAS and Adult Income in Fig. 2 (results for Drug Consumption are in the Appendix: they are less interesting due a lack of representation the dataset).
COMPAS. Fig. 2 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 FLIP, 0.4%, FLIP. 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 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 cost = 0.41 versus 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 data bias
To validate that the disparities in crttfiiabl-robusttnn rather than the abstraction, we performed random testing by perturbing the COMPAS dataset try to find robustness counterexamples, i.e., datasets in the bias set that yield conflicting predictions on a given input. We found more counterexamples robustness for Black people than for White people, which is further evidence for our claim that the robustness disparities are inherent to the dataset.
rates are due to inherent dataset properties
Targeted bias models (COMPAS). If we choose g & (race = Black ^ label = positive) (Fig. 2)) in FLIP 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 moderate bias levels (e.g.. 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% 1.1% bias and continuing through, at least, 10.8% bias). is unclear whether this trend stems from inherent dataset properties, is due the over-approximate nature of the abstraction.
By contrast, using g A (race White A label negative) (Fig. 2c) to describe that White people may be under-porr moleced or under-convieted 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. FLIP and FLIP3' differ only how they describe socictal inequities:

---

are White people under-policedd or are Black people over- werrpooliedd? However, the vast differences in demographic-level robustness rates between FLIP and FL,IP" shows that the choice of predicate is crucial when using targeted bias models. More experimentation needed to understand why these results occur, and how consistent they are across different train/test splits of the data. However, our preliminary results indicate that Antidote-P could a useful tool for social scientists to understand how data bias can affect the reliability of machine-learning outcomes.
Adult Income. Fig. 2 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 Female A Label = negative) led to similar results (see Appendix).
FI.IP where g = (race
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 couple of tricky aspects and ones that do not attempt address are knowing whether the assumptions underlying the bias model are correct, or whether our bias framework is even capable of representing all instances of real-world bias. If the user does not specify the bias model faithfully, then any proofs may not be representative. Also, our tool only certifies robustness, not accuracy. Therefore, it may certify that model will always output the wrong label given data point. This behavior is linked to shortcoming of many machine-learning audits: our tool cannot determine what is an appropriate 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 illustrative to show how certifiable-robustees 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 -rreiiictioniiionn models.
Another limitation is that our framework can only certify decision-tre learners. In practice, many machine learning applications use more sophisticated algorithms that we do not address here. Future work to generalize our ideas to other machine learning architectures would increase the utility of this style of robustness certification.
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-tres algorithms. An important direction for future work is to develop effective techniques for falsification of robustness (i.e., techniques to find minimal dataset perturbations that break robustness). We performed initial experiments in this area using brute-force techniques (i.e., randomly perturb data points, train a new decision tree and see whether the test sample's ' classification changes under the tree the Appendix for more details). The results were promising in that we were able to find counter-examples to robustness for some data points, but there remain many data points that are neither certifiably robust via A nor falsified as robust using random testing. Random testing was an interesting proof of concept, but recommend that the future focus be developing techniques to identify these dataset perturbations in a more scalable and intelligent way. Other future work could also improve our approach's utility through tightening the analytical bounds, such as by abstracting over a more complex domain than intervals.
Acknowledgments and Disclosure of Funding
We thank the anonymous reviewers for commenting on earlier drafts and Sam Drews for the generous use of his code. This work is supported by the National Science Foundation grants CCF-1420866 CCF-1704117, CCF- 175--1700955, CCF- 176381,,, CCF-191822 CCF-1652140 a Microsoft Faculty Fellowship, and gifts and awards from Facebook and Amazon.
References
[1] Aws Albarghouthi, "Introduction to Neural Network Verification". In: CoRR abs/2109. (2021). aix: 2109. 10317 URL: https:/verifieedepleeeee
10

---

[2] Greg Anderson et al. "Optimization and Abstraction: A Synergistic Approach for Analyzing Neu- ral Network Robustness". In: Proceedings the 40th ACM SIGPLAN Conference Programming Language Design and Implementation. PLDI 2019. Phoenix, AZ, USA: Association for Computing Machinery, 2019, 731 734. ISBN; 978 1503671127 DOI: 10. 10e11114/3333 41445//334221.... 3314614 URL: https
org/10. 1145/331 3224211.11...11 3314614
[3] Maksym Andriushchenko and Matthias Hein. "Provably robust boosted decision stumps and trees against adversarial attacks". . In: Advances in Neural Information Processing Systems. Ed. by H. Wallach et al.
Vol. 32. Curran Associates, Inc., 2019. URL: https: http::://pooeeeeeeeeeee neurips wwtppppp/eeaaec/eecec / / (14442266888661e0022222266666633
Paper
[4] Solon Barocas, Moritz Hardt, and Arvind Narayanan. Fairness and Machine Learning. http: www
fairmlbook. org fairmlbook.ov 2019.
[5]
Aharon Ben-Tal al. "Rohust Solutions of Optimization Prohlems Affected by Uncertain Probabilities"
In: Management Science 59.2 (2013), pp. 341-357. not: 10. 1287/mmsc 1120. 1641 eprint: https
//doi. wtt.://g//....///1/...
1120. 1641 URL: httt::htps:// /doi http:/::///oo/////////////// 1287 /nac. 1120.1641
[6] Battista Biggio, Blaine Nelson, and Pavel Laskov. "Poisoning Attacks against Support Vector Machines". In: Proceedings of the 29th International Coference on International Conference on Machine Learning.
IC.I.12. Edinburgh, Scotland: Omnipress, 2012, 1467-1474, ISBN: 978145031 28511.
[7] Emily Black and Matt Fredrikson. "Leave-Onc-owd Unfairness". . In: Proceedings of the 2021 ACM Con- ference Faireess, Accountabilityy and Transparency. FAccT '21. Virtual Event, Canada: Association
for Computing Machinery, 2021, 285 295. ISBN: 9783450383 DOI: [0. 1145//442/8888... .3445994
URI.: (tRt::/ttpa//// //tps:///do http://doo..oorg//// org/10. 10 1144511444421888 34458944
[8] Leo Breiman et al. Classification and Regression Trees. 1st ed. Boca Raton, FL: Chapman & Hall/CRC. 1984.
[9] Hongge Chen et al. "Robust Decision Trees Against Adversarial Examples". In: Proceedings of the 36th International Conference on Machine Learning. Ed. by Kamalika Chaudhuri and Ruslan Salakhutdinov. Vol. 97. Proceedings of Machine Learning Research. PMLR. June 2019, pp. 1 1122-1131. URL: http: //proceedings.. mlr. wwwps//9esspp.pppppppppppp.pp chenn9/ html
[10] Irene Y. Chen, Fredrik D. Johansson, and David Sontag. "Why is My Classifier Discriminatory?" In: Proceedings of the 32nd International Conference on Neural Information Prucessing Systems. NIPS' 18. Montréal, Canada: Curran Associates Inc., 2018, 3543-3554.
[11] Minhao Cheng et al. "Query-Ffficient Hard-label Black-box Attack: An Optimizaation-uused Aptpaaai Approach". In: International Conference on Learning Representations. 2019. URL: httpp:://ppeeeeeeeieee net/ forum?id-r J1k6i RaKX
[12] Patrick Cousot and Radhia Cousot. "Abstract interpretation: a unified lattice model for static analysis of programs by construction or approx inpproximation of fixpoints". In: Proceedings of the 4th ACM SIGACT- SIGPIAN symposium on Principles of programming languages. 1977, pp. 238-252.
[13] Ilass Diakonikolas and Daniel M. Kane. Recent Advances in Algorithmic high--Dimensioal Robust Statistics. 2019. arXiv: 1911 05911 DS]
[14] Iliss Diakonikolas et al. "Robustness meets algorithms"" ". In: Commun. ACM 64.5 (2021), pp. 107-115. DOI: 110.1145/345399
URL: //attps:///oi. wwt/ 1145/3453935
[15] Tias Diakonikolas et al. "Sever: A robust meta-algorithm for stochastic optimization". In: International Conference on Machine Learning. PMLR. 2019, pp. 1596-1606.
[16] Samuel Drews. Aws Albarghouthi, and Loris D' Antoni. "Proving Data- Poisoninn Robustness in Decision Trees". Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation. PLDI 2020. London, UK: Association for Computing Machinery, 2020, 1083-1097.
ISBN: 9781 0888155376133 1366. DOT: 10. 1145/ 3385412. 3385975
URL: https: // org 10. 1145/
3385412. 3385975
[17]
Dheeru Dua and Casey Graff. UCI Machine Learning Repository. 2017. URL: http::///rchiiee..ee ics uci edu/ml
[18]
Cynthia Dwork et al. "Fairness through Awareness", In: Proceedings of the 3rd Innovations in Theoreti- cal Computer Science Conference. ITCS '12. Cambridge. Massachusetts: Association for Computing Machinery, 2012, 214-226. ISBN: 978 77814503111511 DOI: [0. 0001/111/200230 2090255
URL: https
//doi.org/100 1145 /145/2990266...... 2090255
[19] Kenneth Dwyer and Robert Holte. "Decision Tree Instability and Active Learning". In: Proceedings
of the 18th European Conference on Machine Learning. ECML '07. Warsaw, Poland: Springer-Verlae
2007, 128 139. ISBN; 9783540749578. DO1: 10. 1007 998 3- 540 - 74958 5_ 15 URL: https
//doi.
1007/970-0711 3-000- 74958- 5_15
[20] Elaine Fehrman et al. "The Five Factor Model of Personality and Evaluation of Drug Consumption Risk". In: Data Science. Ed. by Francesco Palumbo, Angela Montanari, and Maurizio Vichi. Cham: Springer International Publishing, 2017, pp. 231-242, ISBN: 978-3-339--5522--.

---

[21] Timon Gehr et al. "A12: Safety and Robustness Certification of Neural Networks with Abstract Interpre- tation". In: 2018 IEEE Symposium on Security and Privacy (SP). 2018, pp. 3-18. DOL: 10. 1109/SP 2018.00058
[22] Jinyuan Jia, Xianyu Cao, and Neil Zhenqiang Gong. Certified Robustness of Nearest Neighbors against Data Paisoning Attucks. 2021. arXiv: 22122. 03766 [cs. CR]
[23] Jinyuan Jia, Xiaoyu Cao, and Neil Zhenqiang Gong. "Intrinsic Certified Robustness of Bagging against Data Poisoning Attacks". In: AAAI. 2021.
[24]
Alexander Levine and Soheil Feizi. "Deep partition aggregation: Provable defense against general
poisoning attacks". In: arXiv preprint arXiv:2006. 14768 (2020).
[25]
Ruey-IIsia Li and Geneva G. Belford. "Instability of Decision Tree Classification Algorithms". In: Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. KDD '02. Edmonton, Alberta, Canada: Association for Computing Machinery, 2002, 570-575. org/10. 1145/175000
ISBN: 158113567A DOL: 10. 11e11114777/// 775131
URL: atttps///do .ea.doo..rrggg/
775131
[26]
Debmalya Mandal et al. "Ensuring Faimess Beyond the Training Data". In: Advances in Neu- ral Information Processing Systems. Ed. by H. Larochelle al. Vol. 33. Curran Associates, Inc.. 2020, pp. 18445- 1846.. URL: https / proceedings neurips cc paper / 2020 / file / 0ateae//1159bbbbbaa222222ooe0ee0
Paper pdr]
[27] Hongscok Namkoong and John C Duchi. "Stochastic Gradient Methods for Distributionally Robust Optimization with f-divergences". In: Advances in Neurul Information Processing Systems. Ed. by D. Lee et al. Vol. 29. Curran Associates, Inc.. 2016. URL: https http::://ppopeeeeeeeee http:///poeeeeee..////////./s neurips httpccppppp.o ca/paper/ 2016/E11e/4588e6744000 (rt.BBeer44.fffaafff554444...... Peweeeddddddddr..eeeeeeeee
[28] Andrea Paudice, Luis Muñoz Gonzäez, and Emil C. Lupu. "Label Sanitization Against Label Flipping Poisoning Attacks". In: ECML PKDD 2018 Workshops. Ed. by Carlos Alzate et al. Cham: Springer
International Publishing, 2019, pp. 5-15, ISBN: 978-3-030-13453-2
[29]
Propublica. Propublica Compas Analysis. URL.: https : // /////tthbb//// com http//popbbcca//// compas analysis
[30]
Francesco Ranzato and Marco Zanella. "Abstract Interpretation of Decision Tree Ensemble Classifiers". In: Proceedings of the AAAI Conference on Artificial Intelligence 34.04 (Apr. 2020), pp. 5478 5486. DO1: 10. /a00/ v34104. 5998 URL: https://ojss aaai org/ index.ndexx/.. php/ AAA.AAAAA/aaaaaaa /Attccctla/ttce///////
[31]
Elan Rosenfeld al. "Certified Robustness to Sabel-Flipping Attacks via Randomized Smoothing", In: Proceedings of the 37th International Conference on Machine Learning. Ed. by Hal Daumé IIII and Aarti Singh. Vol. 119. Proceedings of Machine Learning Research. PMLR, July 2020, pp. 8230-8800880 8241. URI.: ptt.:/tttp:/prrceeeiii
mlr .arrspres//// haaaassvvvii vv19/ htt/rrosenfelddde 1tt.e.h.mmmd....mmmmm.
[32] Cynthia Rudin and Joanna Radin. "Why Are We Using Black Box Models in Al When We Don't t Need To? A Lesson From An Explainable Al Competition". In: Harvard Data Science Review 1.2 (Nov. 2019). miip:/// www.eesss..iiieeec.mmoom mit.edd//uub//9kkriii DOL: 10. www.11166999990 5a8a3a3d
URL:
https://hdez: . mitpress..ss..... mit. edu. pub/ httppuuut/laiiippp
[33] Ali Shafahi al. "Poison Frogs! Targeted Clean-Label Poisoning Attacks on Neural Networks". In: Proceedings of the 32nd International Conference on Neural Information Processing Systems. NIPS' 18.
Montréal, Canada: Curran Associates Inc., 2018, 6106 6116.
[34] Soroosh Shafieezadeh-Abattee Abadeh, Peyman Mohajerin Esfahani, and Daniel Kuhn. "Distributionally Robust Logistic Regression". In: Proceedings of the 28th International Conference on Neural Information Processing Systems Volume 1. NIPS' 15. Montreal, Canada: MIT Press, 2015, 1576-1584.
[35] Gagandeep Singh et al. "An Abstract Domain for Certifying Neural Networks". In: Proc. ACM Program. URL: htttps://aoii..... org/ 1145/3290354
Lang. 3.POPL (Jan. 2019). DOI: 10. 1114/3299000
[36] Jacob Steinhardt, Pang Wei Koh, and Percy Liang. "Certified Defenses for Data Poisoning Attacks". In: Proceedings of the 31st International Conference Neural Information Processing Systems. NIPS' 17. Long Beach, California, USA: Curran Associates Inc., 2017, 3520-3532, ISBN: 978 15 510660964.
[37] John Tömblom and Simin Nadjm-Tehrani. Tehrani." "An DbstrrcttoonRReiiemment
Refinement Approach Formal Verification of Tree Ensembles". In: Computer Safety, Reliability, and Security. Ed. by Alexander Romanovsky et al. Cham: Springer International Publishing, 2019. pp. 301-313. ISBN: 778-3-030-2620--1
[38] Peter D. Turney. "Technical Note: Bias and the Quantification Stability".
In: Machine Learning 20 (1
1995). DOI: 10. 1023/1:22010 A: 1022820001117
[39] Han Xiao, Huang Xiao, and Claudia Eckert. "Adversarial Label Flips Attack on Support Vector Machines". In: Proceedings of the 20th European Conference on Artificial Intelligence. ECAI'12. Montpellier, France: IOS Press, 2012, 870-875. ISBN: 9781614990970.
[40] Chiyuan Zhang et al. "Understanding Deep Learning (Still) Requires Rethinking Generalization" In: Commun. ACM 64.3 (Feb. 2021), 107-115. ISSN; 0001-0782. DOI: 10. 1 1041111444444 1145/3446776 URL: https
//ddoi.org/0..1 10. 1141344411114//4477776
12

---

[41] Yuhao Zhang, Aws Albarghouthi, and Loris D' D'Antoni. "Robustness to Programmable String Transfor- mations via Augmented Abstract Training" In: Proceedings the 37th International Conference on Machine Learning. Ed. by Hal Daumé III and Aarti Singh. Vol. 119. Proceedings of Machine Learning Research. PMLR, July 2020, pp. 11023-11032. URL: http: / proceedigs.d...... mlr press/v119) Chang20b.htm)
13


Reviews:
[{"review_id": "suEK3eGyblZ", "reviewer": "Reviewer_FQR1", "summary": "The paper considers a method of certifying decision trees for pointwise robustness to data bias. More specifically, the paper introduces a language to encapsulates different types of data bias and then introduces a criterion for robustness for the CART algorithm.\n\nMain Contributions:\n - Sec 3: A language to characterise data bias.\n - Sec 4: The transformed components of the decision tree algorithm.\n - Experimental evaluation of the proposed certification.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, the paper presents an interesting method for certifying robustness for CART decision trees. The paper is well written and the running examples is greatly appreciated. The experimental section also helps elucidate how the certification process can be used to learn more about the datasets. The only concern is the translatability of such a tool, i.e., the simple change in splitting entropy.\n\nOriginality & Significance: The paper presents a novel method of certifying CART decision trees. Furthermore, the experiments show how the certification can be used to learn more about datasets. The significance is hurt by how the certification approach can only be used for a specific decision tree setup.\n\nQuality & Clarity: The theoretical and empirical results seem to be sound. The paper is well written with high clarity.\n\nStrengths:\n - The \"language\" of data bias models is interesting (and could perhaps have use in distributional robustness outside of certification).\n - The certification (Thm 2) and the abstract transformers provide a nice counter part to the regular CART components.\n - The experiments and discussion presents useful inferences for the datasets.\n\nSuggestions/Weaknesses/Questions:\n - Is there a concrete link between bias models and (say, group) fairness metrics? (i.e., is there an example of equating approximate equalized odds with a bias model?)\n - The pointwise robustness condition seems to be quite restrictive. Is there an easy generalization for approximate pointwise robustness?\n - I think it might be worth reiterating that CART decision trees are the target of certification in Sec 6/limitations.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have adequately addressed the limitations and potential negative societal impact.", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "OOZaJIIGs_1", "reviewer": "Reviewer_Ycxe", "summary": "The paper focuses on robustness against bias in training data. In particular, the main goal of the paper is to develop a method that can certify models produced are pointwise-robust to potential dataset biases. Authors focus on decision-tree learning due to the interpretable nature of the models. Authors propose using a novel symbolic technique to evaluate a decision-tree learner on a large number of datasets, certifying that each and every dataset produces the same prediction for a specific test point. ", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "General Assessment: Paper tackles a relevant problem, is well written and empirical evaluation is sound. Authors consider various models of biases and then develop methods to certify robustness on each of those. \n\nDetailed Review:\n- Authors mention that their method certifies robustness but not accuracy. It would be interesting if the method can be extended to certify accuracy.  \n- Authors currently need users to identify the assumptions underlying the biases. It would be interesting to see how this method might extend beyond this requirement. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NA", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "704m_wt8H_y", "reviewer": "Reviewer_ov7B", "summary": "This paper introduces and explores a framework for certifying that classification models produced by a machine learning algorithm are making predictions on examples that are robust to bias in the training data.  Certification is per example: a certification for an example means that the same prediction would have been made on that example if the training data used to train that model had been perturbed in ways that correspond to potentially eliminating a specified type of bias in the dataset.   The paper presents an algorithm aimed at certifying robustness for a standard decision tree learner and proves that it is sound.  It explores the algorithm in a series of experiments on standard datasets, with different bias definitions and across different demographic groups.  ", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The problem addressed in the paper is interesting and important.  The abstract framework and definition of robustness against bias is well-done and provides a valuable theoretical underpinning for future work on bias in training data.   The presented decision tree algorithm demonstrates that this abstract framework can be applied to specific learning algorithms.  I would view the experiments in this paper as preliminary.   As the authors acknowledge, there are important questions raised by the results.  Further experiments and analysis are needed.\n\nThe paper is well-written.\n\nSpecific comments:\n\np. 4 In the definition of $MISS_m^g(T)$, the \"restrict $T'$\" part of the definition uses the notation $.g(x,y)$.   Replace this dot notation with something more standard.\n\np. 5  The given definition of cost is not normalized, and can be bigger than 1 (as in Example 4.2).  However, in the experimental section, p. 7, the cost of the optimal top-most split is given as 0.30, 0.35, and 0.45, and these seem to be normalized.\n\np. 5  The text states that argmax returns a set of possible indices.  It should also describe which possible indices are returned.\n\np. 7 The definition of $infer^a$ is confusing, despite the explanation that \"the range of $\\cup$ is over predicates of $\\Phi^a$.  I believe that the first $\\cup$ is over all $\\phi$ in $\\Phi^a$ such that $\\phi(x)$ holds, and similarly for the second one.  Should explain more clearly or change the notation in the definition,\n\np. 7 The experimental evaluation section talks about \"the percentage of test samples\" but there is no explanation of how the test samples were chosen.  I did not find this information in the supplementary material either.\n\np. 9 \"Understanding why this phenomenon occurs is beyond the scope of this paper.\"   I appreciate that the authors performed these experiments on targeted bias models and acknowledged that they do not understand the reasons behind the results.    That said, this phenomenon (or more specifically, these particular experimental results) raises questions about how we should interpret any experimental results obtained using this system, including the other results presented in this paper.   The authors would have done better to explicitly say that the experiments they performed were preliminary, and that further experimentation is needed.  ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "- See comment (9) above.  \n- In the Checklist at the end of the paper, the authors state as an example that the data split is discussed in the supplemental material.  However, I could not find any discussion in the paper or the supplemental material of how the datasets were divided into train and test.  (Please let me know if I missed it.)  The authors appear to have used a single test set for each dataset, given that they said that error bars are N/A.  This needs to be clarified.  ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "-TsEDr_7bpi", "reviewer": "Reviewer_RG8X", "summary": "The paper proposes to certify that models are pointwise-robust to potential dataset biases using decision trees. The approach programmatically specifies bias models), i.e. models that specify suspected bias. Robustness is certified using a symbolic technique to evaluate a decision tree on a large number of datasets and certifying that all datasets provide the same decision for a test point.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The concept of bias models as proposed in this paper is interesting, but I would perhaps name it differently because ‘bias model’ is quite an overloaded word. The paper breaks down bias models into a few types: missing data, label flipping, fake data. Additionally the paper suggests targeted versions for each of the three types where only a specific group of data points experience that bias, and composite versions which are arbitrary combinations of missing, label, and/or fake. It may be good to state that these are not exhaustive and there are more potential issues that could lead to all datasets not providing the same decision for a test point. E.g. besides label flipping, what about feature flipping which could lead to a change in the label?\n\nEvaluation:\n-\tCan you do an approximate baseline by enumerating some datasets in the bias set, or any other baseline you can provide? It is hard to contextualize the results otherwise. \n-\tCan you give an idea of how long the procedure takes?\n-\tI’m a bit perplexed by the targeted bias results for COMPAS, where at first glance FLIP^g and FLIP^{g’} seem like they should be two sides of the same coin. For COMPAS with n=4629 to confirm, did you limit it to only white and black? What did the tree look like? ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors explained about their choice of the datasets they used; I don't have concerns here.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes to certify that machine learning models (in particular decision trees learned by the CART algorithm) are robust to potential dataset biases. This is a timely and important topic, given the widespread deployment of ML models in high stakes situations, and the difficulty of collecting data that are fully representative and free from biases.

Reviewers were in consensus that the paper makes an interesting contribution to the literature in this important problem space. Only minor concerns were raised in the initial reviews, and adequately addressed by the authors during the rebuttal.

I recommend acceptance and congratulate the authors on their timely and important research work.
Decision: Accept (Poster)