Learning Certified Individually Fair Representations

Anian Ruoss, Mislav Balunovic, Marc Fischer, Martin T. Vechev

Introduction

In sensitive domains like credit scoring or criminal risk assessment, machine learning models can easily reinforce human biases. To combat this, the field of "fair representation learning" proposes a pipeline with three actors: a data regulator who defines what fairness means, a data producer who transforms sensitive raw data into a sanitized representation, and a data consumer who uses that representation for downstream prediction tasks.

Historically, most work in this area has focused on statistical (group) fairness (e.g., ensuring equal approval rates across different demographic groups). However, group fairness offers no guarantees for individuals. Individual fairness—the principle that similar individuals should be treated similarly—is highly desirable but notoriously difficult to enforce and certify. Previous methods either relied on probabilistic guarantees or required the data consumer to know the exact fairness rules, breaking the modularity of the pipeline.

This paper introduces the first end-to-end framework that allows machine learning practitioners to learn and mathematically certify individual fairness in data representations. By framing individual fairness as a local robustness problem in the latent space, the authors provide a modular way for data producers to encode sensitive data and for data consumers to train classifiers with deterministic fairness guarantees.

Methodology

The authors bridge the gap between fairness and adversarial robustness using a clever two-step approach that preserves the separation of concerns between data owners and downstream users.

Overview of the modular fairness certification pipeline.
  1. Defining Similarity via Logic: The data regulator defines similarity using interpretable logical constraints. For example, a rule might state: "Two individuals are similar if all categorical attributes except race are identical, and their incomes differ by no more than $5,000."
  2. The Data Producer (Encoder): The producer trains an encoder network to map all "similar" individuals to points that are very close to each other in the latent space (specifically, within a bounded $L_\infty$ distance). They translate the logical constraints into a differentiable loss function, optimizing the encoder via min-max optimization to penalize counterexamples.
  3. The Data Consumer (Classifier): The consumer receives the latent representations and trains a classifier. Because similar individuals are now clustered tightly in the latent space, the consumer simply trains their classifier to be adversarially robust to small local perturbations.
  4. Modular Certification: To prove fairness for a specific data point, the producer uses Mixed-Integer Linear Programming (MILP) to calculate the exact radius ($\epsilon$) of the bounding box containing all similar individuals in the latent space. The consumer then uses MILP to prove that their classifier outputs the exact same label for every possible point within that $\epsilon$-radius.

Key Insights

  • Fairness is Latent Robustness: The most elegant insight of the paper is translating the abstract concept of "individual fairness" into the well-studied mechanical problem of "adversarial robustness." If similar people are mapped to the same neighborhood in latent space, a robust classifier is inherently a fair classifier.
  • True Modularity: The data consumer never needs to know the specific logical rules defining fairness, nor do they need to see the raw sensitive data. They only receive a latent vector $z$ and a radius $\epsilon$.
  • Expressive Fairness: By using logical constraints rather than simple distance metrics, regulators can define highly nuanced, domain-specific fairness rules that handle both categorical and numerical data naturally.

Key Results

The authors evaluate their method (LCIFR) on several standard tabular datasets commonly used in fairness research, including Adult, Compas, Crime, German, Health, and Law School.

Experimental results comparing baseline and LCIFR models.
  • Massive Boost in Certification: The method drastically increases the percentage of individuals who can be mathematically certified as treated fairly. For example, on the Adult dataset under a noise-based similarity constraint, the baseline model certified 59.0% of individuals. LCIFR certified 97.8%, with only a minor drop in accuracy (83.0% down to 81.4%).
  • 100% Certification on Categorical Rules: For constraints based purely on categorical similarities, the method frequently achieved 100% certified individual fairness across multiple datasets (Adult, Compas, Crime, German).
  • Transferability: The authors demonstrated that these fair representations transfer well to unknown downstream tasks. On the Health dataset, a representation trained to predict the Charlson Index was used to predict five different primary condition groups, maintaining certified fairness rates between 86.1% and 98.4%.
  • Speed: Despite using MILP, the certification process is fast for these tabular networks, averaging less than a second per input (e.g., 0.29s on Adult).

Limitations and Future Work

While highly effective, the framework does have limitations. First, it assumes the data regulator defines a perfectly ethical similarity metric; if the logical constraints unconsciously encode human bias, the system will perfectly and certifiably enforce that bias. Second, the method assumes the data producer acts in good faith and does not intentionally learn a discriminatory representation. Finally, because exact MILP solving scales exponentially, applying this exact certification to massive networks (like ResNets for images) would be computationally prohibitive. Future work could leverage linear relaxations or abstract interpretation to scale the certification to larger models.

Summary updated

Abstract

Fair representation learning provides an effective way of enforcing fairness constraints without compromising utility for downstream users. A desirable family of such fairness constraints, each requiring similar treatment for similar individuals, is known as individual fairness. In this work, we introduce the first method that enables data consumers to obtain certificates of individual fairness for existing and new data points. The key idea is to map similar individuals to close latent representations and leverage this latent proximity to certify individual fairness. That is, our method enables the data producer to learn and certify a representation where for a data point all similar individuals are at l-infinity distance at most epsilon, thus allowing data consumers to certify individual fairness by proving epsilon-robustness of their classifier. Our experimental evaluation on five real-world datasets and several fairness constraints demonstrates the expressivity and scalability of our approach.
BibTeX
@inproceedings{ruoss2020learning,
  author = {Anian Ruoss and Mislav Balunovic and Marc Fischer and Martin T. Vechev},
  title = {{Learning Certified Individually Fair Representations}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=Pe-aGb1XfF},
}
Figure