Rafael Pass: Explorations into Algorithmic Fairness

Abstract:

 

Fairness in classification has become an increasingly relevant and controversial issue as computers replace humans in many of today’s classification tasks. In particular, following the work of Dwork et al (ITCS'12), a subject of much debate is that of finding suitable definitions of fairness in an algorithmic context. In this work in progress, we explore such algorithmic notions of fairness.

 

We first introduce new definitions that formalize two of the most notable recent definitions of fairness in classification. Roughly speaking, *fair treatment* formalizes the intuition that “equal” individuals (i.e. individuals having the same class) from different groups (e.g. races) are similarly treated, whereas *fair predictivity* formalizes the intuition that the classifier’s accuracy is similar among the different groups. Our first main result---which strengthens earlier results by Chouldechova (FATML’16) and Kleinberg et al. (ITCS’17)---shows that these two notions of fairness are largely incompatible.

 

Consequently, we need to give up on acheiving one of them, and we focus our attention on acheiving fair treatment. Our second main result shows how to take any (possibly unfair) classifier C over a finite outcome space, and transform it---by just perturbing the output of C---according to some distribution learned by just having black-box access to samples of labeled, and previously classified, data, into a "near-optimal" classifier C′ satisfying fair treatment. Our approach relies on, and generalizes, an LP-based characterization of fair treatment due to Hardt et al (NIPS'16).

 

Joint work with Andrew Morgan