TL;DR
Researchers from Delft University of Technology have developed DPF (Dynamic Programming Fair), a new algorithm that finds optimal decision trees under global fairness constraints up to 10,000 times faster than previous state-of-the-art methods. By cleverly using bounding techniques to maintain subproblem independence, DPF allows practitioners to map the entire "Pareto front"—the perfect trade-off between accuracy and fairness—even for large datasets.
The Challenge of Fair and Optimal Decision Trees
In high-stakes domains like criminal justice or credit scoring, machine learning models must be two things: interpretable and fair. Small decision trees are the gold standard for interpretability, but finding the optimal tree (the one with the highest possible accuracy for a given size) is an NP-hard problem.
While recent years have seen progress in finding optimal trees using Dynamic Programming (DP), adding a global fairness constraint (like demographic parity) creates a massive technical hurdle. Standard DP relies on the "separability" of subproblems—the idea that you can optimize the left branch of a tree independently of the right. Fairness constraints break this: if the left branch of your tree is slightly biased against a protected group, the right branch must "compensate" to keep the overall model fair.
This dependency usually makes DP unusable, forcing researchers to rely on Mixed Integer Programming (MIP) models that are notoriously slow and fail to scale beyond a few thousand data instances.
How DPF Works: Bounding Fairness
The authors introduce DPF, which successfully incorporates global fairness into a DP framework. The key innovation is the use of upper and lower bounds on fairness.
- Fairness Bounding: Instead of trying to solve for a single fairness value, the algorithm calculates the range of possible imbalance values a partial subtree could contribute.
- Redefined Dominance: In standard DP, a solution is "dominated" (and discarded) if another solution is better in every way. DPF redefines this: a solution is only discarded if it has a worse misclassification score and its fairness bounds are strictly worse than another candidate.
- Pruning and Merging: By tracking these bounds, the algorithm can prune large sections of the search space early if it determines a branch can never lead to a solution that satisfies the global fairness threshold ($\delta$).
- Pareto Optimization: Because the algorithm is so efficient, it doesn't just find one fair tree; it can find the set of all "non-dominated" trees, allowing users to see exactly how much accuracy they must sacrifice to achieve a specific level of fairness.
Key Insights: Breaking the Independence Trap
- Rethinking Independence: The most significant breakthrough is the realization that you don't need subproblems to be perfectly independent to use DP. By passing fairness bounds between subproblems, you can maintain enough "global context" to prune effectively without losing the optimality guarantee.
- MIP vs. DP Scalability: MIP models scale poorly because they typically create a binary variable for every single data instance. DPF’s complexity is tied more to the number of unique features and the number of "nondominated" partial solutions, making it much more robust for datasets with tens of thousands of rows.
- The Value of the Pareto Front: Fairness isn't a binary "yes/no" toggle. By visualizing the full Pareto front, the authors show that we can often achieve significant gains in fairness with only negligible losses in accuracy—information that was previously too computationally expensive to generate.
Performance and Key Results
The authors evaluated DPF on 12 real-world datasets commonly used in fairness research, including Adult, COMPAS, and Bank Marketing. The results demonstrate a paradigm shift in performance:
- Massive Speedups: As shown in the runtime table, DPF is consistently 4 to 5 orders of magnitude faster than FairOCT (the leading MIP-based model). For example, on the COMPAS viol. dataset, DPF found an optimal depth-2 tree in under a second, while the MIP model took nearly 27 minutes (1594 seconds).
- Handling Large Data: DPF successfully processed the Adult dataset (over 45,000 instances) at depth 4 in roughly 17 minutes (1012 seconds). Previous state-of-the-art models couldn't even handle this dataset at depth 2 within a one-hour time limit.
- Depth Breakthroughs: For many datasets, DPF is the first algorithm capable of finding provably optimal fair trees at depth 4, whereas previous methods were limited to very shallow (depth 2 or 3) trees.
Limitations and Future Directions
While DPF represents a massive leap forward, the authors note several areas for future improvement:
- Binary Constraints: The current implementation is limited to binary features and binary classification. Extending this to multi-class problems or continuous features remains a challenge.
- Feature Scaling: While DPF handles many instances well, the runtime still grows exponentially with the number of features.
- Fairness Metrics: The paper focuses on "Demographic Parity." While the authors suggest the method can be adapted for "Equal Opportunity," this hasn't been fully implemented or tested yet.
- Unbalanced Data: For highly skewed datasets, accuracy might be a poor objective. Future versions should explore optimizing for balanced accuracy or F1-scores.
Summary updated