PaperlayerView exact revision on arXiv

Source-linked AI summary

Conformal Classification with Equalized Coverage for Adaptively Selected Groups

Yanfei Zhou, Matteo Sesia

arXiv:2405.15106v2stat.MLcs.LG

TL;DR

Marginal coverage can conceal subgroup errors, while exhaustive equalized coverage can leave small calibration subsets and uninformative predictions. AFCP adaptively selects sensitive attributes and constructs prediction sets with coverage conditional on the selected attributes. In experiments, it outperformed benchmarks with more informative sets and higher conditional coverage for an African-American subgroup, though limited samples can impede attribute selection.

  • Problem

    Marginal coverage can fail to reflect miscoverage concentrated among groups, while exhaustive equalized coverage can make calibration subsets too small for informative prediction sets.

    Source: §1.2 · p. 2

  • Method

    AFCP adaptively selects sensitive attributes associated with bias and constructs prediction sets with coverage conditional on the selected attribute.

    Source: §1.3 · p. 3, §2.2 · p. 6

  • Results

    AFCP outperformed the considered benchmarks, producing more informative prediction sets with higher conditional coverage for the African-American subgroup.

    Source: A7.1.3 COMPAS data · p. 45

  • Takeaways & Limitations

    AFCP offers a practical compromise between informative prediction sets and equalized coverage for applications involving multiple sensitive attributes.

    Source: §4 · p. 10

    AFCP cannot guarantee equalized coverage for all sensitive groups.

    Source: §1.1 · p. 2

Abstract

from arXiv · show

This paper introduces a conformal inference method to evaluate uncertainty in classification by generating prediction sets with valid coverage conditional on adaptively chosen features. These features are carefully selected to reflect potential model limitations or biases. This can be useful to find a practical compromise between efficiency -- by providing informative predictions -- and algorithmic fairness -- by ensuring equalized coverage for the most sensitive groups. We demonstrate the validity and effectiveness of this method on simulated and real data sets.

1 Introduction

Conformal prediction quantifies uncertainty, but marginal coverage may conceal subgroup errors, while exhaustive equalized coverage can become uninformative with many sensitive attributes. AFCP adaptively selects attributes for coverage guarantees, aiming to balance informativeness and subgroup coverage.

1.1 Uncertainty, Fairness, and Efficiency in Machine Learning

  • Conformal prediction sets quantify casewise uncertainty, but marginal coverage can conceal subgroup errors and exhaustive equalized coverage scales poorly across multiple sensitive attributes.Exhaustive conditioning can reduce effective sample sizes and produce less informative predictions.Source: §1.1 · pp. 1–2

1.2 Background on Conformal Inference for Classification

  • Exact feature-conditional coverage is generally unachievable without additional assumptions, while exhaustive group conditioning can leave calibration subsets too small for informative predictions.Equalized coverage offers a practical middle ground between marginal and feature-conditional coverage.Source: §1.2 · p. 2

1.3 Preview of Our Contributions: Adaptive Equalized Coverage

  • AFCP adaptively selects a sensitive attribute associated with bias and constructs prediction sets with coverage conditional on the selected attribute, reducing to marginal coverage when none is selected.The method targets groups needing stronger guarantees rather than conditioning on every sensitive attribute.Source: §1.3 · p. 3
  • In a simulated example, marginal sets missed true labels for patients in the critical group, whereas AFCP produced prediction sets described as both efficient and fair.Exhaustive equalized-coverage sets were too conservative to be informative in that example.Source: §1.3 · p. 3
  • Using the same data for attribute selection and calibration creates potential selection bias, making informative sets with adaptive equalized coverage challenging without additional sample splitting.The paper states that it presents a solution to this challenge.Source: §1.3 · p. 3

1.4 Table of Contents

  • The paper presents AFCP, empirical evaluations, limitations and future work, extensions, proofs, implementation details, and additional experiments.The extensions include selecting multiple sensitive attributes and coverage conditional on the true test label.Source: §1.4 · p. 4

1.5 Related Works

  • Closest equalized-coverage methods [45] [46] do not automatically select groups; [47] identifies unfairly treated groups, while [48] studies different rules for adaptively selected test subsets.Other discussed work targets complementary goals or different coverage settings.Source: §1.5 · p. 4

2 Method

AFCP uses leave-one-out miscoverage across candidate sensitive attributes and placeholder labels to select an attribute, then combines marginal and group-conditional prediction sets. Under exchangeability, the resulting sets satisfy adaptive equalized coverage.

2.1 Automatic Attribute Selection

  • For each placeholder label, AFCP uses leave-one-out conformal sets to assess miscoverage and finds each attribute’s worst-off group rate.The maximum miscoverage rate for an attribute is used as evidence that one of its groups may experience algorithmic bias.Source: §2.1 · p. 5
  • A one-sided test selects an attribute when its miscoverage statistic exceeds α; the final selection must be consistent across all placeholder labels.If the test does not reject, no attribute is selected.Source: §2.1 · p. 5

2.2 Constructing the Adaptive Prediction Sets

  • AFCP unions the marginal prediction set with sets constructed for the attributes selected under each placeholder label.The marginal set is always retained, which the authors identify as essential to validity.Source: §2.2 · p. 6
  • With sufficiently large samples, attribute selection is described as stable across test points and placeholder labels, so the union typically does not make prediction sets very large.The method is also described as efficiently implementable, with cross-validation as a possible alternative to leave-one-out when n is very large.Source: §2.1 · p. 5, §2.2 · p. 6
  • Under exchangeability, AFCP’s prediction sets and selected attribute satisfy adaptive equalized coverage.The proof addresses the lack of exchangeability introduced by adaptive selection.Source: §2.2 · p. 6

3 Numerical Experiments

Across synthetic and Nursery experiments, AFCP balances conditional coverage with informative prediction sets, while its attribute selection and performance vary with sample size and prior knowledge of bias.

3.1 Setup and Benchmarks

  • The evaluation compares AFCP with marginal, exhaustive equalized, and partial equalized benchmarks using the same data, model, and conformity scores.AFCP selects at most one sensitive attribute; AFCP1 always selects one, regardless of the significance test.Source: §3.1 · p. 7

3.2 Synthetic Data

  • AFCP and AFCP1 achieve valid coverage for the Blue group with sets not much larger than marginal sets, while exhaustive and partial benchmarks can be conservative.AFCP1 is slightly more robust at very small sample sizes because it always selects a sensitive attribute; AFCP selection becomes more consistent for Color as sample size grows.Source: §3.2 · pp. 7–8, Figure 3 · p. 8, Figure 4 · p. 8

3.3 Nursery data

  • On Nursery data, AFCP produces smaller prediction sets than the partial benchmark while maintaining valid coverage for the hardest-to-predict group.The marginal benchmark has very low coverage for the first Parents’ occupation category, while the exhaustive benchmark produces very large sets unless the sample is very large.Source: §3.3 · p. 9, Figure 5 · p. 9

3.4 Additional Numerical Experiments

  • Additional experiments cover COMPAS, synthetic and Adult Income data, outlier detection, and an Adult Income extension selecting multiple sensitive attributes.Source: §3.4 · p. 9

3.5 Performance of AFCP with Different Sample Sizes

  • As sample size grows, AFCP more effectively identifies the attribute with the lowest conditional coverage and achieves high coverage with relatively small sets.At small sample sizes, fitting a model, assessing conditional coverage, and identifying the lowest-coverage attribute are difficult; AFCP often improves conditional coverage over the marginal benchmark with only a slight increase in average set size.Source: §3.5 · p. 9

3.6 Comparison between AFCP and AFCP1

  • AFCP suits settings where significant bias is uncertain, while AFCP1 suits settings where prior knowledge suggests at least one attribute may be biased.In the synthetic Color-Blue example, AFCP1 has slightly higher conditional coverage; AFCP may fail to select an attribute in small samples when evidence of bias is insufficient.Source: §3.6 · p. 10

4 Discussion

The discussion presents AFCP as a practical method for balancing informative prediction sets with conditional coverage, while noting that limited samples can impede sensitive-attribute selection.

  • AFCP constructs informative conformal prediction sets with valid coverage conditional on adaptively selected features, balancing efficiency and equalized coverage.The approach can integrate prior knowledge about sensitive attributes that may need protection.Source: §4 · p. 10
  • With limited sample sizes, AFCP may not identify the most relevant sensitive attribute; the reported mitigation of significant bias is effective when sample size is adequate.Source: §4 · p. 10
  • Future work includes theory for reliable attribute selection, alternative selection procedures, other fairness criteria, high-class-count settings, ordered outcomes, distribution shifts, robustness, and regression.The paper also notes computational challenges for regression with continuous outcomes.Source: §4 · p. 10
  • The experiments used less than 25 minutes and 5 GB of memory per specified run on a single CPU; implementation and data-experiment software are available online.The specified runs used 1,000 calibration samples and 500 test samples.Source: §4 · p. 10

A1 Review of Existing Conformal Classification Methods

The reviewed classification procedure constructs conformal prediction sets using a fixed list of protected attributes; with no protected attributes, it reduces to marginal coverage.

A2 Methodology Extension: AFCP with Multiple Selected Attributes

AFCP is extended to select up to two sensitive attributes, then construct prediction sets with adaptive equalized coverage. Under exchangeability, the resulting sets and selected attributes satisfy the stated coverage guarantee.

A2 Methodology Extension: AFCP with Multiple Selected Attributes

A2.1 Automatic Multiple Attribute Selections

  • For each placeholder label, AFCP selects a first attribute and, if one is selected, repeats selection after excluding it.The resulting attribute set is the union of the selections from the two rounds.Source: A2.1 Automatic Multiple Attribute… · p. 16

A2.2 Constructing the Adaptive Prediction Sets

A3 Methodology Extension: AFCP with Label Conditional Coverage

AFCP extends adaptive equalized coverage to condition on the true test label. It selects attributes using label-restricted calibration data and constructs prediction sets that satisfy the label-conditional guarantee under exchangeability.

A3 Methodology Extension: AFCP with Label Conditional Coverage

  • Exhaustive label-conditional equalized coverage calibrates separately for every combination of sensitive attributes and test labels, and can become overly conservative with many attributes or labels.Source: A3 Methodology Extension: AFCP with… · p. 17

A3.1 Automatic Attribute Selection

A3.2 Constructing the Adaptive Prediction Sets

A4 Methodology Extension: AFCP for Outlier Detection

AFCP extends adaptive conformal prediction to outlier detection by selecting potentially affected groups and evaluating a conformal p-value within the selected group. Under exchangeability, this controls false-positive rates conditionally on selected groups.

A4.2 Evaluating the Adaptive Conformal P-Value

A4.1 Automatic Attribute Selection

  • Attribute selection uses leave-one-out tests to estimate each attribute’s worst-group false-positive rate and flags an attribute when the no-bias null is rejected.If the null is not rejected, no attribute is selected.Source: A4.1 Automatic Attribute Selection · p. 19

A4.2 Evaluating the Adaptive Conformal P-Value

A4.3 AFCP for Outlier Detection with Multiple Selected Attributes

A5 Mathematical Proofs

The proofs establish the coverage and false-positive guarantees by connecting adaptive selection to fixed-attribute conformal procedures. Their arguments use exchangeability, permutation-invariant selection, and coverage-preserving set constructions.

  • Theorem 1 compares the practical prediction set with an oracle-selected set and a marginal set, whose coverage bounds support the adaptive coverage guarantee.The proof relies on the practical set containing these component sets.Source: A5 Mathematical Proofs · pp. 21–22
  • For two selected attributes, Theorem A1 bounds coverage by connecting the practical set to an oracle set and marginal and single-attribute equalized sets.The proof separately lower-bounds the coverage contributions of those component sets.Source: A5 Mathematical Proofs · pp. 22–23
  • Theorem A2 uses label-restricted exchangeability and a fixed oracle-selected attribute to establish label-conditional adaptive coverage.The practical attribute is either empty or matches the oracle selection.Source: A5 Mathematical Proofs · pp. 23–24
  • Theorem A3 obtains a super-uniform conformal p-value by showing the selected-group nonconformity scores are exchangeable, making the test score’s rank uniform or super-uniform.The proof uses permutation invariance of the attribute-selection procedure.Source: A5 Mathematical Proofs · p. 24
  • Lemma A1 establishes coverage for a fixed placeholder-label selection by exchangeability of the restricted scores and the conformal quantile bound.Source: A5 Mathematical Proofs · pp. 24–25

A6 Computational Shortcuts and Efficient Implementation

The appendix gives computational costs for AFCP outlier detection and multi-class classification, for both single and multiple test points. Reusing calibration-group subsets keeps attribute selection tractable as test points are processed.

A6.1 Outlier Detection

  • For outlier detection, Algorithm A7 costs O(n log n + nKM) per test point and O(n log n + nm + MK(n + m)) for m test points.Here n is calibration-set size, K the number of sensitive attributes, and M the maximum number of values per attribute.Source: Analysis for a single test point · pp. 25–26

Analysis for a single test point

  • For outlier detection across m test points, calibration subsets D(k, m) are identified once and reused to compute false-positive rates for each test point.This reuse contributes to the stated O(n log n + nm + MK(n + m)) total cost.Source: Analysis for a single test point · p. 26

A6.2 Multi-Class Classification

Analysis for a single test point

  • For multi-class classification across m test points, the same calibration subsets are reused across test samples and placeholder labels when computing miscoverage rates.The resulting total cost is O(n log n + Lnm + MK(n + Lm)).Source: Analysis for a single test point · pp. 26–27

A7 Additional Results from Numerical Experiments

The additional synthetic and Nursery experiments examine conditional coverage and prediction-set size across groups and sample sizes. AFCP and AFCP1 address undercoverage in the biased groups while maintaining informative sets; several unbiased groups show similar performance across methods.

A7.1.1 Synthetic Data

  • For the synthetic Blue group, AFCP and AFCP1 correct undercoverage while maintaining small prediction sets; Marginal misses the undercoverage and Exhaustive is too conservative.The synthetic Age group and Region groups have similar performance by design and show no unfairness or undercoverage.Source: Figure A1 · p. 28, Figure A2 · p. 28, Figure A3 · p. 28

A7.1.2 Nursery Data

  • For Nursery Parents’ Occupation 1, AFCP and AFCP1 correct undercoverage while maintaining small sets; Marginal misses it and Exhaustive is too conservative.The Children, Finance, Social, and Health groups have similar performance and no unfairness or undercoverage.Source: Figure A8 · p. 35, Figure A9 · p. 35, Figure A10 · p. 36
  • On Nursery data, AFCP produces lower average width and higher conditional coverage on the Pretentious group as training and calibration points increase.The figure reports error bars of 2 standard errors.Source: Figure A13 · p. 40, Table A15 · p. 40

A7.1.3 COMPAS data

The COMPAS experiments evaluate AFCP on recidivism-risk classification after preprocessing and deliberately increasing difficulty for African-American samples. AFCP methods outperform the considered benchmarks on prediction-set informativeness and conditional coverage for that subgroup.

A7.1.3 COMPAS data

  • The COMPAS dataset contains 6,172 instances, and the experiments add uniform label noise to African-American samples and undersample that group to 200.The other reported group counts are Caucasian 2,103, Hispanic 509, and Others 385.Source: A7.1.3 COMPAS data · p. 45
  • AFCP methods outperform the considered benchmarks, producing more informative prediction sets with higher conditional coverage for the African-American subgroup.Figure A19 varies total training and calibration data from 200 to 1,000 points; Figure A20 varies restricted calibration size.Source: A7.1.3 COMPAS data · p. 45, Figure A19 · p. 45, Figure A20 · p. 45
  • As sample size increases, AFCP and AFCP1 more consistently select Race as the most sensitive attribute.The experiments also report that African-American test accuracy is significantly below average.Source: A7.1.3 COMPAS data · p. 45, Figure A21 · p. 46, Table A21 · p. 46

A7.2 AFCP for Outlier Detection

The outlier-detection experiments compare AFCP with marginal, exhaustive, and partial equalized benchmarks using FPR and TPR. On synthetic data, AFCP improves both measures for the undercovered Blue group, while all methods keep average FPR below the target.

A7.2.1 Setup and Benchmarks

  • The benchmarks are Marginal, Exhaustive equalized across all sensitive attributes, and Partial equalized separately across each attribute; AFCP1 skips the significance test.The experiments use a three-layer neural network and set the miscoverage target to α = 0.1.Source: A7.2.1 Setup and Benchmarks · p. 46

A7.2.2 Synthetic Data

  • The synthetic setup designates Color as sensitive for the undercovered Blue group, while Age Group and Region are unbiased in this setting.The experiments also examine how the percentage of Blue samples, which controls bias severity, relates to attribute-selection frequency.Source: A7.2.2 Synthetic Data · pp. 46–47, Figure A26 · p. 48
  • On synthetic data, AFCP has higher TPR and lower FPR on the Blue group as training and calibration sample size varies.The plotted error bars indicate 2 standard errors.Source: Figure A22 · p. 47
  • Across all test samples, AFCP and AFCP1, along with Marginal, achieve the highest TPR while all methods control FPR below 0.1.Results are averaged over 500 independent test points and 30 experiments.Source: A7.2.1 Setup and Benchmarks · p. 46, Table A22 · p. 47

A7.2.3 Adult Income Data

On Adult Income, AFCP variants identify and correct protected attributes associated with groups with significantly higher FPR under the Marginal method. Across test samples, all methods keep average FPR below 0.1, while AFCP methods generally achieve higher TPR.

A7.2.3 Adult Income Data

  • Adult Income preprocessing treats categorical variables as sensitive attributes and groups levels with small samples; income above $50,000 defines outliers.The listed attributes include Country (United-States, Others), Education, Work Class, Marital Status, Occupation, Relationship, Race, and Sex.Source: A7.2.3 Adult Income Data · p. 50
  • The comparison evaluates AFCP, AFCP1, and AFCP+ against benchmark methods, averaging over 500 test points and 30 independent experiments.AFCP+ can select multiple protected attributes.Source: A7.2.3 Adult Income Data · p. 50
  • AFCP, AFPC1, and AFCP+ identify and correct protected attributes corresponding to groups with significantly higher FPR under the Marginal method.The groups experiencing bias are unknown in this dataset; Figure A27 examines groups observed to have higher FPR with Marginal.Source: A7.2.3 Adult Income Data · p. 50, Figure A27 · p. 50
  • All methods keep average FPR below 0.1, while AFCP methods generally achieve higher TPR; Marginal is an exception but suffers from unfairness.The comparison averages results across all test samples.Source: A7.2.3 Adult Income Data · p. 50, Figure A28 · p. 51, Table A26 · p. 51
  • Figures A29–A36 and Tables A27–A34 separately assess the FPR and TPR of conformal p-values for each protected attribute.Source: A7.2.3 Adult Income Data · p. 50
Loading 2405.15106v2…