Fairness Through Computationally-Bounded Awareness

By Michael P. Kim, Omer Reingold, Guy N. Rothblum. 2018

154 citations recorded by the source corpus.

We study the problem of fair classification within the versatile framework of Dwork et al. [ITCS 2012], which assumes the existence of a metric that measures similarity between pairs of individuals. Unlike previous works on metric-based fairness, we do not assume that the entire metric is known to the learning algorithm. Instead, we study the setting where a learning algorithm can query this metric a bounded number of times to ascertain similarities between particular pairs of individuals. For example, the queries might be answered by a panel of specialists spanning social scientists, statisticians, demographers, and ethicists. We propose "metric multifairness," a new definition of fairness that is parameterized by a similarity metric $\delta$ on pairs of individuals and a collection ${\cal C}$ of"comparison sets" over pairs of individuals. One way to view this collection is as the family of comparisons that can be expressed within some computational bound. With this interpretation, metric multifairnesss loosely guarantees that similar subpopulations are treated similarly, as long as these subpopulations can be identified within this bound. In particular, metric multifairness implies that a rich class of subpopulations are protected from a multitude of discriminatory behaviors. We provide a general-purpose framework for learning a metric multifair hypothesis that achieves near-optimal loss from a small number of random samples from the metric $\delta$. We study the sample complexity and time complexity of learning a metric multifair hypothesis (providing rather tight upper and lower bounds) by connecting it to the task of learning the class ${\cal C}$. In particular, if the class ${\cal C}$ admits an efficient agnostic learner, then we can learn such a metric multifair hypothesis efficiently.

Subfields: Artificial Intelligence, Safety Research, AI Ethics, Fairness & Society

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Safety Research

In AI Ethics, Fairness & Society

Citations in the corpus

Explainable Artificial Intelligence (XAI): Concepts, Taxonomies, Opportunities and Challenges toward Responsible AI (2019, neutral): “Finally, CERTI-FAI (Counterfactual Explanations for Robustness, Transparency, Inter-pretability, and Fairness of Artiﬁcial Intelligence models) [402] uses a customized genetic algorithm to generate counterfactuals that can help to see the robustness of a ML model, generate explanations, and examine ”
Prediction-Based Decisions and Fairness: A Catalogue of Choices, Assumptions, and Definitions (2018, background): “But in subsequent research, the metric is often defined over the variables input to the classifier [109, 71].”
The Frontiers of Fairness in Machine Learning (2018, background): “[KRR18] assume that the algorithm has access to an oracle which can return an unbiased estimator for the distance between two randomly drawn individuals according to an unknown fairness metric, and show how to use this to ensure a statistical notion of fairness related to [KNRW18b, HJKRR18] which…”
An Empirical Study of Rich Subgroup Fairness for Machine Learning (2018, background): “also extend it to metric fairness constraints [12], converting”
Multicalibration: Calibration for the (Computationally-Identifiable) Masses (2018, background): “…how to interpolate between statistical and individual notions of “metric fairness” for general similarity metrics (Kim et al., 2018b), as well as further theoretical and empirical investigations of multi-accuracyin-expectation in the context of binary classification (Kim et al., 2018a).”
Eliciting and Enforcing Subjective Individual Fairness (2019, background): “Kim et al. [2018] consider a group-fairness like relaxation of individual metric-fairness, asking that on average, individuals in pre-speciﬁed groups are classiﬁed with probabilities proportional to the average distance between individuals in those groups.”
Fairness in Machine Learning: A Survey (2020, background): “[5, 57, 65, 124, 195, 209, 210, 288, 112, 208, 75, 284, 164]) have similar objectives to fairness regularization approaches, and hence we present them together.”
Aligning AI With Shared Human Values (2020, background): “However, similarity has been defined in terms of an arbitrary metric; some have proposed learning this metric from data (Kim et al., 2018; Gillen et al., 2018; Rothblum and Yona, 2018), but we are not aware of any practical implementations of this, and the required metrics may be unintuitive to…”
Average Individual Fairness: Algorithms, Generalization and Experiments (2019, background): “This line includes Hébert-Johnson et al. (2018) (focusing on calibration), Kearns et al. (2018) (focusing on false positive and negative rates), and Kim et al. (2018b) (focusing on error rates).”
Online Learning with an Unknown Fairness Metric (2018, background): “Kim et al. [2018] considers a group-fairness like relaxation of metricfairness, asking that on average, individuals in pre-specified groups are classified with probabilities proportional to the average distance between individuals in those groups.”
Trustworthy AI: From Principles to Practices (2021, background): “, constraint optimization) can be applied to train a smaller model to transform model outputs or calibrate model confidence [186].”
Fairness Under Composition (2018, background): “To that end, concerns about the treatment of socially meaningful subgroups are addressed in several lines of work using more granular group requirements in order to provide more meaningful guarantees for sufficiently sized subgroups [13, 9, 15].”
Algorithm fairness in artificial intelligence for medicine and healthcare (2023, background): “And bias-mitigation strategies that consider the inclusion of protected attributes are few 94,168–171 .”
Algorithmic Fairness: Choices, Assumptions, and Definitions (2021, background): “But in subsequent research, the metric is often defined over the variables input to the classifier (Kim et al. 2018, Rothblum & Yona 2018).”
Individual Fairness in Pipelines (2020, background): “17 We exhibit mechanisms robust to two broad classes of policies: (1) Individual interchangeability: replacing a single individual in the cohort does not change treatment of the cohort too much, i.e. policies like δ F 2 .”
Noise-tolerant fair classification (2019, background): “Individual-level fairness Dwork et al. (2011); Kusner et al. (2017); Kim et al. (2018) asks the treatment of two individuals similar if they are similar according to some distance measure.”
Fairness without Demographics through Adversarially Reweighted Learning (2020, background): “Computational-Identifiability: Related to our algorithm, a number of works [33, 35, 23, 36] address intersectional fairness by optimizing for group fairness between all computationally identifiable groups in the input space.”