Certifying Robustness to Programmable Data Bias in Decision Trees

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.

arXiv commentTo be published at NeurIPS 2021. 22 pages, 4 figures

References in corpus (8)

• Poisoning Attacks against Support Vector Machines
• Distributionally Robust Logistic Regression
• Sever: A Robust Meta-Algorithm for Stochastic Optimization
• Recent Advances in Algorithmic High-Dimensional Robust Statistics
• Optimization and Abstraction: A Synergistic Approach for Analyzing Neural Network Robustness
• Robust Decision Trees Against Adversarial Examples
• Intrinsic Certified Robustness of Bagging against Data Poisoning Attacks
• Deep Partition Aggregation: Provable Defense against General Poisoning Attacks