Learning Optimal and Fair Decision Trees for Non-Discriminative Decision-Making

By Sina Aghaei, Javad Azizi, Phebe Vayanos. 2019

192 citations recorded by the source corpus.

In recent years, automated data-driven decision-making systems have enjoyed a tremendous success in a variety of fields (e.g., to make product recommendations, or to guide the production of entertainment). More recently, these algorithms are increasingly being used to assist socially sensitive decisionmaking (e.g., to decide who to admit into a degree program or to prioritize individuals for public housing). Yet, these automated tools may result in discriminative decision-making in the sense that they may treat individuals unfairly or unequally based on membership to a category or a minority, resulting in disparate treatment or disparate impact and violating both moral and ethical standards. This may happen when the training dataset is itself biased (e.g., if individuals belonging to a particular group have historically been discriminated upon). However, it may also happen when the training dataset is unbiased, if the errors made by the system affect individuals belonging to a category or minority differently (e.g., if misclassification rates for Blacks are higher than for Whites). In this paper, we unify the definitions of unfairness across classification and regression. We propose a versatile mixed-integer optimization framework for learning optimal and fair decision trees and variants thereof to prevent disparate treatment and/or disparate impact as appropriate. This translates to a flexible schema for designing fair and interpretable policies suitable for socially sensitive decision-making. We conduct extensive computational studies that show that our framework improves the state-of-the-art in the field (which typically relies on heuristics) to yield non-discriminative decisions at lower cost to overall accuracy.

Subfields: Safety Research, Sociology and Political Science, Statistics and Probability, Statistical Learning Theory, AI Ethics, Fairness & Society

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Safety Research

In Sociology and Political Science

In Statistics and Probability

In Statistical Learning Theory

In AI Ethics, Fairness & Society

Citations in the corpus

Mathematical optimization in classification and regression trees (2021, methodology): “…and Tang 2014; Turney 1995), fairness of the method avoiding the discrimination of groups that share sensitive features such as gender and race (Aghaei et al. 2019; Miron et al. 2020; Romei and Ruggieri 2014; Zafar et al. 2017), and explainability properties, e.g., sparsity and local…”
MurTree: Optimal Decision Trees via Dynamic Programming and Search (2020, methodology): “Aghaei et al. (2019) used a mixed-integer programming formulation for optimal decision trees that supported fairness metrics.”
Learning Optimal Decision Trees Using Caching Branch-and-Bound Search (2020, background): “Most attention has been given in recent years and in prominent venues to approaches based on mixed integer programming (Bertsimas and Dunn 2017; Verwer and Zhang 2019; Aghaei, Azizi, and Vayanos 2019).”
Learning Optimal Classification Trees: Strong Max-Flow Formulations (2020, methodology): “The works of Bertsimas and Dunn (2017), Günlük et al. (2018), Aghaei et al. (2019), and Verwer and Zhang (2019) have served to showcase the modeling power of using MIP to learn decision trees and the potential suboptimality of traditional algorithms.”
Learning Fair Rule Lists (2019, background): “Finally, Aghaei, Azizi and Vayanos (2019) [2] proposed MIP-DT which adds regularization terms to a mixed-integer programming model to penalize unfairness for creating a generic class of fair decision trees according to individual fairness.”
Market Segmentation Trees (2019, methodology): “Decision trees provide a simple way to visualize the decision-making stream and have been used in a variety of settings (Kallus 2017, Elmachtoub et al. 2017, Ciocan and Mišić 2022, Bertsimas et al. 2019, Aghaei et al. 2019).”
Lagrangian Duality for Constrained Deep Learning (2020, background): “[2], to quantify the disparate impact in a dataset.”
Decision Trees for Decision-Making under the Predict-then-Optimize Framework (2020, methodology): “Aghaei et al. (2019) propose methodology for training decision trees for decision-making problems using a loss function which penalizes predictions that discriminate on sensitive features such as race or gender. However, their loss function does not consider the impact of predictions on downstream d”
FAHT: An Adaptive Fairness-aware Decision Tree Classifier (2019, background): “For example, [ Aghaei et al. , 2019 ] added regularization terms to the Mixed-Integer Programming model to penalize discrimination.”
Fairness in Machine Learning: A Survey (2020, unknown): “When extending the classifier’s (convex) loss function with fairness terms, researchers typically seek to balance fairness and accuracy (e.g., References [5, 26, 36, 52, 57, 98, 119, 141, 153, 168, 208, 314]).”
Learning Binary Trees via Sparse Relaxation (2020, result): “This resulted in a line of recent follow-up works (Günlük et al., 2018; Aghaei et al., 2019; Verwer & Zhang, 2019; Hu et al., 2019; Aghaei et al., 2020; Lin et al., 2020).”
A Scalable MIP-based Method for Learning Optimal Multivariate Decision Trees (2020, methodology): “…results, our SVM1-ODT formulation is abbreviated as “S1O”, “OCT-H” is the MIP formulation to train multivariate ODT in [Bertsimas and Dunn, 2017], “Fair” is the MIP formulation from [Aghaei et al., 2019] without the fairness term in objective, and “BinOCT” is from [Verwer and Zhang, 2019].”
Optimal Decision Trees for Nonlinear Metrics (2020, background): “Aghaei, Azizi, and Vayanos (2019) encoded fairness metrics within a mixed-integer programming formulation for optimal decision trees in socially sensitive contexts, which aims to deliver fair and accurate decision trees.”
Recent advances in decision trees: an updated survey (2022, methodology): “3.1) have also been adapted to the optimal framework, such as OCT-H (Bertsimas and Dunn 2017), ORCT (Blanquero et al. 2021, 2020), SVM-1 ODT (Zhu et al. 2020) and the formulation by Aghaei et al. (2019).”
Robust Optimization for Fairness with Noisy Protected Groups (2020, background): “Enforcing group-based fairness with credit default predictions has been considered in a variety of prior works [32, 10, 51, 3, 9, 28, 25, 6].”
Learning optimal decision trees using constraint programming (2020, background): “Constraints can be added, as long as they are linear; this includes constraints on fairness [Aghaei et al., 2019] or on the number of examples in the leafs [Bertsimas and Dunn, 2017].”
Trustworthy AI: From Principles to Practices (2021, unknown): “For instance, quantitative fairness metrics can be used as regularization [7] or constraints for the optimization of the model parameters [67].”
MurTree: Optimal Classification Trees via Dynamic Programming and Search (2020, methodology): “These approaches use generic optimisation methods, namely integer programming (Bertsimas and Dunn (2017); Verwer and Zhang (2017, 2019); Aghaei et al. (2019)), constraint programming (Verhaeghe et al. (2019)), and SAT (Narodytska et al. (2018)), and algorithms tailored to the decision tree problem…”