Source-linked AI summary
Learning Optimal and Fair Decision Trees for Non-Discriminative Decision-Making
Sina Aghaei, Mohammad Javad Azizi, Phebe Vayanos
TL;DR
Socially sensitive machine-learning decisions can produce disparate treatment or impact, including when protected attributes are omitted because correlated unprotected attributes remain. The paper unifies fairness definitions across classification and regression and develops mixed-integer optimization for fair decision trees, improving the state of the art with lower accuracy cost.
Problem
Socially sensitive machine-learning decision-making must balance predictive accuracy with fairness across classification and regression while avoiding disparate treatment and impact.
Method
The paper mathematically unifies disparate-treatment and disparate-impact measures and learns optimal fair decision trees by augmenting predictive loss with a discrimination regularizer.
Results
The framework improves the state of the art by yielding nondiscriminating decisions at lower cost to overall accuracy.
Takeaways & Limitations
A single user-selected parameter tunes the trade-off between accuracy and fairness in interpretable classification and regression trees.
Takeaways & Limitations
Fairness is restricted to equality in the first moment because requiring equality of continuous distributions would make the models computationally intractable, and the tree depth must be selected in advance.
Abstract
from arXiv · showhide
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 decision-making (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.
1 Introduction
Machine learning increasingly supports socially sensitive decisions, but biased data and unequal error effects can produce disparate treatment or impact. The paper addresses this with a unified, exact framework for fair and interpretable decision trees across classification and regression.
- Motivation: Socially sensitive uses of machine learning include credit, public services, sentencing, employment, and college-admissions decisions.
- Motivation: Discrimination can arise from historically biased training data or from errors affecting protected groups differently, even when the data are unbiased.
- Motivation: Fair decision-support tools must balance predictive accuracy with fairness in settings involving protected attributes and socially sensitive resource allocation.
- Contributions: The paper mathematically formalizes disparate treatment and disparate impact for both classification and regression and defines indices to quantify them.
- Contributions: A unifying mixed-integer optimization framework learns optimal and fair decision trees while tuning the accuracy–fairness trade-off with one user-selected parameter.
- Contributions: The framework supports customizable tree structures, branching rules, and leaf models, and computational studies report nondiscriminating decisions at lower overall-accuracy cost than the state of the art.
2 A Unifying Framework for Fairness in Classification and Regression
The paper unifies fairness definitions for supervised classification and regression by formalizing disparate impact and disparate treatment, then introduces indices to quantify both. These definitions support analyzing whether learned decision systems treat protected groups differently.
- Supervised learning maps feature vectors to labels, with categorical or unordered labels defining classification and continuous or ordered labels defining regression.
- Disparate impact concerns systematic group differences without explicitly using sensitive attributes, while disparate treatment concerns different outputs for similar individuals differing in protected characteristics.
- Disparate impact: DIDI quantifies disparate impact for classification and regression datasets, with zero indicating no disparate impact and larger values indicating more discrimination.
- Disparate impact: For classification, unbiased labels combined with protected-attribute-independent misclassification probabilities imply protected-attribute-independent predictions.
- Disparate impact: For regression disparate impact, the framework requires predicted expected values not to change after observing protected features, while acknowledging that matching entire continuous distributions is computationally intractable.
- Disparate treatment: DTDI quantifies disparate treatment using locally weighted comparisons, assigning greater weight to pairs whose protected attributes are closer.
3 Mixed Integer Optimization Framework for Learning Fair Decision Trees
The framework learns fair decision trees by minimizing predictive loss augmented with a discrimination regularizer, with λ tuning the accuracy–fairness trade-off. Its mixed-integer formulation supports classical trees and extensions with linear branching, linear leafing, and categorical features.
- 3.1 Overview: The MILP-based approach trades off prediction quality and fairness by augmenting classification or regression loss with a discrimination regularizer.Classification uses misclassification rate, while regression uses mean absolute error; discrimination can target disparate impact, disparate treatment, or both.
- 3.1 Overview: A user-selected parameter λ tunes the trade-off between accuracy and fairness in the tree-learning objective.The parameter is constrained to λ ≥ 0.
- 3.1 Overview: The optimization introduces variables for branching structure, leaf assignments, and predictions, then chooses their values to minimize the regularized loss.Branching variables select features, assignment variables identify each data point’s leaf, and prediction variables determine outputs.
- 3.2 General Classes of Decision-Trees: The tree depth K is selected by the decision-maker, and the resulting model classes are formulated as MILP-representable sets.The framework generalizes tree structures previously proposed for policy design to generic decision- and policy-making tasks.
- 3.2 General Classes of Decision-Trees: The framework covers classical decision trees and variants with linear branching, linear leafing, or both.Classical trees branch on a single feature and assign one prediction per leaf, whereas extensions use linear rules for branches or leaf predictions.
- 3.2 General Classes of Decision-Trees: Categorical branching assigns feature levels to branches without requiring one-hot encoding, yielding more interpretable and flexible trees than cited alternatives.The binary variables sνjk indicate which categorical levels go left; the authors contrast this with methods requiring one-hot encoding.
4 Numerical Results
The experiments evaluate the proposed methods on classification and regression datasets using cross-validation and compare accuracy–fairness trade-offs across approach families. The reported figures examine these trade-offs, tree-depth effects, optimization bounds, and maximally non-discriminative models.
- Datasets: The evaluation covers three classification datasets—Default, Adult, and COMPAS—and a regression dataset, Crime.The Default dataset contains 30,000 observations and 23 features; Adult contains 45,000 observations and 13 features in the supplied passage.
- Compared approaches: The study compares MIP-DT and MIP-DT-A with CART and linear regression methods using individual- and group-fairness penalties.The comparison includes regular linear regression, LR-ind, and LR-grp.
- Evaluation procedure: Cross-validation assesses the fairness–accuracy trade-off by selecting λ⋆ for each fold and approach from a grid of candidate regularization values.The study uses 5-fold cross-validation for classification and 4-fold cross-validation for regression.
- Accuracy and fairness: Figure 1 plots accuracy against discrimination across approach families, with dots representing cross-validation samples and shaded regions representing convex hulls.The figure contains separate panels for Default, Adult, COMPAS, and Crime.
- Optimization and depth analysis: The numerical analysis also examines objective value, accuracy and fairness by tree depth, MILP upper and lower bounds, and empirical γ(x) distributions for CART and MIP.Figure 2 includes these four analyses from left to right.