Mondrian Conformal Prediction

The primary objective of Mondrian conformal prediction. Unlike marginal coverage, which guarantees validity only on average across all data, conditional coverage aims to ensure the prediction set contains the true label with the specified probability within each pre-defined category or stratum. This is critical for fairness in high-stakes applications, preventing a model from being systematically less accurate for a protected subgroup. While exact conditional coverage is statistically impossible without strong assumptions, Mondrian conformal prediction provides a practical, distribution-free approximation by partitioning the calibration data.

A specific type of conditional coverage where the data is partitioned based on the value of the label Y. A Mondrian conformal predictor achieves label-conditional validity by computing nonconformity score quantiles independently for each class in a classification problem. This guarantees that the marginal coverage property holds separately for every class:

• Class 1: P(Y ∈ C(X) | Y=1) ≥ 1-α
• Class 2: P(Y ∈ C(X) | Y=2) ≥ 1-α This prevents the predictor from producing empty or infinitely large sets for minority classes, a common failure mode of standard conformal prediction on imbalanced datasets.

The heuristic function A(z, S) that scores how unusual a data point z = (x, y) is relative to a multiset S. In Mondrian conformal prediction, the choice of nonconformity measure is critical and can be tailored per category. Common choices include:

• Classification: 1 - softmax_score(x)_y (one minus the predicted probability for the true class)
• Regression: The absolute residual |y - μ(x)| normalized by a local dispersion estimate σ(x) The nonconformity scores for calibration data within each Mondrian category are ranked to determine the category-specific threshold for prediction set inclusion.

The pre-defined partitioning scheme that gives Mondrian conformal prediction its name, inspired by the grid-like paintings of Piet Mondrian. A taxonomy κ maps each data point to a category κ(x, y). The calibration is then performed independently within each cell of this partition. Common taxonomies include:

• Class-conditional: κ(x, y) = y (the label itself)
• Feature-binned: κ(x, y) = bin(x_feature) (e.g., age group, income bracket)
• Joint: κ(x, y) = (y, bin(x_feature)) (a combination of label and feature strata) The granularity of the taxonomy trades off conditional validity against statistical efficiency, as finer partitions reduce the calibration data per cell.

The foundational, computationally efficient algorithm that Mondrian conformal prediction extends. The standard split conformal process:

1. Split the training data into a proper training set and a disjoint calibration set.
2. Train a model on the proper training set.
3. Score each point in the calibration set using a nonconformity measure.
4. Compute the (1-α) empirical quantile of the scores.
5. For a new test point, form a prediction set by including all labels with a nonconformity score below the quantile threshold. Mondrian conformal prediction modifies step 4 by computing a separate quantile for each category defined by the taxonomy.

The most common instantiation of Mondrian conformal prediction, where the taxonomy is simply the class label. This method directly addresses the problem of imbalanced classification. Standard conformal prediction might produce empty prediction sets for rare classes because the global quantile threshold is dominated by the majority class's nonconformity scores. By computing a separate threshold q_y for each class y, class-conditional conformal prediction ensures that a test point is assigned class y if its nonconformity score for that class is below q_y. This guarantees that the true class is included in the prediction set with probability 1-α regardless of its prevalence.