Metric-Fair Classifier Derandomization

Abstract

We study the problem of classifier derandomization in machine learning: given a stochastic binary classifier f: X [0,1], sample a deterministic classifier f: X \0,1\ that approximates the output of f in aggregate over any data distribution. Recent work revealed how to efficiently derandomize a stochastic classifier with strong output approximation guarantees, but at the cost of individual fairness -- that is, if f treated similar inputs similarly, f did not. In this paper, we initiate a systematic study of classifier derandomization with metric fairness guarantees. We show that the prior derandomization approach is almost maximally metric-unfair, and that a simple ``random threshold'' derandomization achieves optimal fairness preservation but with weaker output approximation. We then devise a derandomization procedure that provides an appealing tradeoff between these two: if f is -metric fair according to a metric d with a locality-sensitive hash (LSH) family, then our derandomized f is, with high probability, O()-metric fair and a close approximation of f. We also prove generic results applicable to all (fair and unfair) classifier derandomization procedures, including a bias-variance decomposition and reductions between various notions of metric fairness.

Tasks

Reproductions