Algorithmic Fairness, Metric Embedding, and Metric Learning

Abstract

As algorithms are increasingly used to classify people in contexts like criminal justice, college admissions, and advertising, it is important to ensure that these algorithms are socially responsible and treat people the way they should be treated. To formalize this idea, many notions of algorithmic fairness have been proposed. One fairness notion is individual fairness, which proposes that fair algorithms treat similar individuals similarly. A key question in formulating individual fairness is ``which individuals are similar?'' Answering this question requires knowing a distance function, or metric, on the individuals who are to be classified that tells us which individuals should be treated similarly. To learn this metric, we can ask questions to fair-minded human experts about the distances or relative distances between individuals. Stitching the responses to these questions into a metric is what we will call metric learning problem for individual fairness. In this thesis, we begin by providing a survey of various notions of algorithmic fairness and their relative strengths and weaknesses. Adopting individual fairness as a goal, we continue by providing an exposition about forms of metrics that are amenable to simple representations. As a central theme, we will show that many metrics can be represented as embeddings into Euclidean space. We then survey a variety of approaches to learning metrics, focusing on metrics which are representable as embeddings. Then, we introduce a novel approach for learning Mahalanobis distances from relative distance information that follows the Bradley-Terry data-generating model. We provide analysis showing that gradient descent with respect to a natural loss function converges quickly, given a suitable initialization point. Because our algorithm has formal accuracy guarantees and learns an interpretable metric, it has potential for use in practice as a way to learn metrics for individual fairness.