Individually fair optimal decision trees

Using a dynamic programming approach

Bachelor thesis (2023)

Authors

C. KINDYNIS Electrical Engineering, Mathematics and Computer Science

Contributors

J.G.M. van der Linden Algorithmics - EEMCS (supervisor 1)
E. Demirović Algorithmics - EEMCS (supervisor 1)
Burcu Kulahcioglu Ozkan Software Engineering - EEMCS (supervisor 2)
Faculty
Electrical Engineering, Mathematics and Computer Science
Copyright: © 2023 Chrysanthos KINDYNIS
Optimal Decision Tree Dynamic Programming Algorithms Individual Fairness Interpretable Machine Learning Separability
More Info
expand_more

Published Date

22-06-2023

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Electrical Engineering, Mathematics and Computer Science

Abstract

In this paper, we tackle the problem of creating decision trees that are both optimal and individually fair. While decision trees are popular due to their interpretability, achieving optimality can be difficult. Existing approaches either lack scalability or fail to consider individual fairness. To address this, we define individual fairness as a separable optimization task by analyzing the fairness gained and lost within a sub-tree. Using the Streed framework, we implement an algorithm that constructs optimal decision trees with the lowest misclassification score and individual fairness value above a certain threshold. Our algorithm has been tested on various datasets, demonstrating its effectiveness and scalability. This research is a significant step towards creating fair decision trees that are optimal, fair, and scalable.