Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
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?

Evaluation:
-	Can 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. 
-	Can you give an idea of how long the procedure takes?
-	I’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? 
limitations_and_societal_impact: The authors explained about their choice of the datasets they used; I don't have concerns here.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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. 
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. 

Detailed Review:
- Authors mention that their method certifies robustness but not accuracy. It would be interesting if the method can be extended to certify accuracy.  
- 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. 
limitations_and_societal_impact: NA
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: 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.  
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.

The paper is well-written.

Specific comments:

p. 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.

p. 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.

p. 5  The text states that argmax returns a set of possible indices.  It should also describe which possible indices are returned.

p. 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,

p. 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.

p. 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.  
limitations_and_societal_impact: - See comment (9) above.  
- 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_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.

Main Contributions:
 - Sec 3: A language to characterise data bias.
 - Sec 4: The transformed components of the decision tree algorithm.
 - Experimental evaluation of the proposed certification.
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.

Originality & 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.

Quality & Clarity: The theoretical and empirical results seem to be sound. The paper is well written with high clarity.

Strengths:
 - The "language" of data bias models is interesting (and could perhaps have use in distributional robustness outside of certification).
 - The certification (Thm 2) and the abstract transformers provide a nice counter part to the regular CART components.
 - The experiments and discussion presents useful inferences for the datasets.

Suggestions/Weaknesses/Questions:
 - 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?)
 - The pointwise robustness condition seems to be quite restrictive. Is there an easy generalization for approximate pointwise robustness?
 - I think it might be worth reiterating that CART decision trees are the target of certification in Sec 6/limitations.
limitations_and_societal_impact: The authors have adequately addressed the limitations and potential negative societal impact.
review_title: null

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)