  There has been much discussion recently about how fairness should be measured
or enforced in classification. Individual Fairness [Dwork, Hardt, Pitassi,
Reingold, Zemel, 2012], which requires that similar individuals be treated
similarly, is a highly appealing definition as it gives strong guarantees on
treatment of individuals. Unfortunately, the need for a task-specific
similarity metric has prevented its use in practice. In this work, we propose a
solution to the problem of approximating a metric for Individual Fairness based
on human judgments. Our model assumes that we have access to a human fairness
arbiter, who can answer a limited set of queries concerning similarity of
individuals for a particular task, is free of explicit biases and possesses
sufficient domain knowledge to evaluate similarity. Our contributions include
definitions for metric approximation relevant for Individual Fairness,
constructions for approximations from a limited number of realistic queries to
the arbiter on a sample of individuals, and learning procedures to construct
hypotheses for metric approximations which generalize to unseen samples under
certain assumptions of learnability of distance threshold functions.
