Fairness & Explainability

Background

ProPublica COMPAS analysis (2016) showed a recidivism prediction model was biased against Black defendants - triggering the algorithmic fairness research field
Chouldechova (2017) proved that three intuitive fairness criteria are mutually incompatible except in degenerate cases
GDPR (2018) mandated the right to explanation for algorithmic decisions in the EU

The Concept

Algorithmic fairness requires that model predictions do not systematically disadvantage protected groups (demographic parity, equal opportunity). Explainability requires that model decisions can be understood and audited. SHAP, LIME, and integrated gradients are the main post-hoc explanation methods.

How it Links

Fairness metrics connect to evaluation metrics - they are performance metrics disaggregated by group
SHAP values connect to game theory (Shapley values from cooperative game theory)
Differential privacy and federated learning are technical tools for privacy-preserving fairness

Concrete Example

A loan approval model: audit by computing approval rates separately for each demographic group (demographic parity). Find the model approves 80% of white applicants but only 60% of Black applicants with identical financial profiles. This disparity may reflect biased training data, biased features, or proxy discrimination through correlated features like zip code.

Prerequisites

Evaluation Metrics, Classical ML, MLOps

Learning outcomes

Define demographic parity, equalized odds, equal opportunity, and calibration and state which pairs are mutually exclusive.
Sketch the proof of the fairness impossibility theorem (Chouldechova / Kleinberg) and state when the constraints can all hold.
Derive the Shapley value formula from first principles and explain how SHAP estimates it for ML models.
Distinguish integrated gradients from vanilla gradients and explain the completeness and sensitivity axioms.
State the epsilon-delta definition of differential privacy and explain the privacy-accuracy trade-off in DP-SGD.

TL;DR

Fairness and explainability are complementary safety concerns for deployed ML systems. Fairness definitions formalise what it means for a model to treat groups equitably, but Chouldechova [1] and Kleinberg et al. [2] proved that several natural fairness criteria are mathematically incompatible when base rates differ across groups. Explainability methods---SHAP [3], LIME [4], Integrated Gradients [5]---attribute model predictions to input features, but Jain and Wallace [6] showed that attention weights are not faithful explanations of model behaviour. Privacy-preserving learning (differential privacy [7], federated learning [8]) addresses data governance rather than model behaviour, but is increasingly required alongside fairness and explainability for regulatory compliance.

Fairness definitions

A fairness criterion is a mathematical constraint on the joint distribution of predictions, true labels, and sensitive attributes (race, gender, age, etc.). Different criteria formalise different conceptions of fairness.

Demographic parity (statistical parity): the prediction $\hat{Y}$ is independent of the sensitive attribute $A$ :

P(\hat{Y} = 1 | A = 0) = P(\hat{Y} = 1 | A = 1).

Both groups receive positive predictions at equal rates. This is the baseline intuition for “equal treatment” but ignores whether the base rates of the true outcome differ.

Equal opportunity (Hardt et al. 2016): the true positive rate is equal across groups:

P(\hat{Y} = 1 | Y = 1, A = 0) = P(\hat{Y} = 1 | Y = 1, A = 1).

Qualified members of each group are equally likely to receive a positive prediction.

Equalized odds: both the true positive rate AND the false positive rate are equal across groups:

P(\hat{Y} = 1 | Y = y, A = 0) = P(\hat{Y} = 1 | Y = y, A = 1) \quad \text{for } y \in \{0, 1\}.

This is stricter than equal opportunity.

Calibration: the predicted probability equals the empirical fraction of positives, separately for each group:

P(Y = 1 | \hat{P} = p, A = a) = p \quad \text{for all } p, a.

A calibrated model means “if I say there’s a 70% chance, 70% of such cases really do belong to the positive class”, within each group.

The fairness impossibility theorem

Chouldechova [1] and Kleinberg et al. [2] independently proved that calibration, balance for the positive class, and balance for the negative class cannot all hold simultaneously unless the base rates are equal across groups.

Informal proof sketch. For group $a$ , let:

$b_a = P(Y = 1 | A = a)$ (base rate)
$\text{PPV}_a = P(Y = 1 | \hat{Y} = 1, A = a)$ (positive predictive value)
$\text{FPR}_a = P(\hat{Y} = 1 | Y = 0, A = a)$ (false positive rate)
$\text{FNR}_a = P(\hat{Y} = 0 | Y = 1, A = a)$ (false negative rate)

From Bayes’ theorem and basic probability identities, one can derive:

\text{PPV}_a = \frac{b_a (1 - \text{FNR}_a)}{b_a (1 - \text{FNR}_a) + (1 - b_a) \text{FPR}_a}.

If both groups have equal FPR and FNR (equalized odds), but $b_0 \neq b_1$ , then the PPV values differ across groups. A model that satisfies equalized odds therefore cannot satisfy predictive parity (equal PPV) unless $b_0 = b_1$ .

Conversely, if both groups have equal PPV (calibration) and the false positive rates are equal, then the false negative rates must differ when the base rates differ.

Practical implication. In criminal recidivism prediction: if Black defendants have a higher base rate of recidivism (due to structural factors including prior over-policing), a calibrated model will have equal PPV across groups but will have higher false positive rates for white defendants or higher false negative rates for Black defendants, or some combination. There is no statistically fair solution if the base rates reflect historical injustice.

The theorem does not say that fairness is impossible; it says that you must choose which fairness criterion to optimise, and that choice is a value judgment, not a technical one.

SHAP: Shapley value attribution

SHAP [3] attributes the prediction $f(x)$ to individual input features by computing Shapley values from cooperative game theory.

Shapley value derivation

For a model $f: \mathbb{R}^d \to \mathbb{R}$ and an input $x$ , the Shapley value of feature $i$ is defined as the average marginal contribution of feature $i$ across all possible orderings of features:

\phi_i(f, x) = \sum_{S \subseteq \{1,\dots,d\} \setminus \{i\}} \frac{|S|! (d - |S| - 1)!}{d!} \left[ v(S \cup \{i\}) - v(S) \right],

where $v(S) = \mathbb{E}[f(X) | X_S = x_S]$ is the expected model output when the features in $S$ are observed and the rest are marginalised out.

Four axioms uniquely characterise the Shapley value:

Efficiency: $\sum_i \phi_i = f(x) - \mathbb{E}[f(X)]$ . Attributions sum to the model’s output relative to the base value.
Symmetry: if features $i$ and $j$ contribute equally to all subsets, $\phi_i = \phi_j$ .
Dummy: if feature $i$ never changes the output, $\phi_i = 0$ .
Additivity: for two models $f = g + h$ , $\phi_i^f = \phi_i^g + \phi_i^h$ .

Computational complexity. The exact Shapley value requires $2^d$ evaluations of $v(S)$ ---exponential in the number of features. SHAP approximates it:

KernelSHAP: model-agnostic; samples subsets $S$ and fits a weighted linear model. $O(2^d)$ worst case but efficient in practice for $d < 50$ .
TreeSHAP: exact for tree-based models (decision trees, XGBoost, LightGBM) in $O(TLD^2)$ where $T$ is the number of trees, $L$ is the number of leaves, and $D$ is the tree depth. This is the production workhorse for tabular ML.
DeepSHAP: uses DeepLIFT-style backpropagation to approximate Shapley values for neural networks.

LIME: local linear approximations

LIME [4] explains a single prediction by approximating the model locally with an interpretable model (a linear model or decision tree).

For an input $x$ and a black-box model $f$ , LIME:

Samples $N$ perturbed inputs $z_1, \dots, z_N$ near $x$ (for text: randomly mask tokens; for images: randomly grey-out superpixels).
Gets model predictions $f(z_j)$ for each perturbed input.
Weights each $z_j$ by its proximity to $x$ : $\pi_x(z_j) = \exp(-d(x, z_j)^2 / \sigma^2)$ .
Fits a linear model $g$ to minimise $\sum_j \pi_x(z_j) (f(z_j) - g(z_j))^2$ plus a complexity penalty.

The coefficients of $g$ are the local feature importances. LIME is model-agnostic and local: it explains one prediction at a time and makes no assumptions about $f$ .

Limitations: (1) Instability---the explanation can vary significantly between runs because the perturbation is random. (2) Distribution shift---perturbed samples may be out-of-distribution (grey-ed out pixels do not look like realistic images), so $f(z_j)$ may not reflect model behaviour on realistic inputs. (3) Approximation error---the local linear approximation may be poor if $f$ is highly nonlinear near $x$ .

Integrated gradients

Integrated Gradients (IG) [5] attributes predictions using the path integral of gradients from a baseline input $x'$ (e.g., all zeros) to the actual input $x$ :

\text{IG}_i(x) = (x_i - x'_i) \times \int_0^1 \frac{\partial f(x' + \alpha (x - x'))}{\partial x_i} \,d\alpha.

In practice the integral is approximated by summing over $m$ evenly-spaced steps along the path from $x'$ to $x$ .

Axioms satisfied by IG:

Completeness: $\sum_i \text{IG}_i(x) = f(x) - f(x')$ . The attributions sum to the model output difference between input and baseline. This is the key advantage over vanilla gradients, which only reflect local sensitivity and do not integrate to the output.
Sensitivity: if $f(x) \neq f(x')$ and $x$ and $x'$ differ in exactly one feature, that feature gets a nonzero attribution.
Implementation invariance: two functionally equivalent networks (same input-output behaviour) get the same attributions.

Compared to attention: Jain and Wallace [6] showed that attention weights do not satisfy completeness or sensitivity and can be adversarially modified while preserving predictions. IG is a more faithful attribution method for transformer models.

Comparison of attribution methods

Method	Granularity	Faithfulness	Compute	Applicable to	Output
Vanilla gradients	Feature-level	Low (local only, no completeness)	One backward pass	Any differentiable model	Gradient map
Integrated Gradients	Feature-level	High (completeness, sensitivity axioms)	O(m) backward passes	Any differentiable model	Attribution map summing to output diff
SHAP (KernelSHAP)	Feature-level	High (Shapley axioms: efficiency, symmetry, dummy, additivity)	O(2^d) samples; fast in practice with TreeSHAP	Any model (model-agnostic)	Additive feature importances summing to output
LIME	Feature-level (superpixel / token)	Medium (local approximation may be poor)	O(N) model evaluations	Any model (model-agnostic)	Linear model coefficients
Attention weights	Token-level	Low (not faithful per Jain & Wallace 2019)	Free (already computed)	Transformer models only	Weight distribution over input tokens

Differential privacy

Differential privacy (DP) provides a mathematical guarantee that an individual’s data cannot be significantly inferred from a model or statistic, even by a computationally unbounded adversary.

Formal definition. A randomised mechanism $\mathcal{M}: \mathcal{D} \to \mathcal{R}$ is $(\epsilon, \delta)$ -DP if for all adjacent datasets $D, D'$ (differing in one individual’s record) and all output subsets $S \subseteq \mathcal{R}$ :

P[\mathcal{M}(D) \in S] \le e^\epsilon \cdot P[\mathcal{M}(D') \in S] + \delta.

The parameter $\epsilon$ (epsilon) is the privacy budget: smaller $\epsilon$ means stronger privacy. $\delta$ is a small failure probability (typically $10^{-5}$ ). The constraint says: the output distribution is nearly the same whether or not any single individual’s data is included.

DP-SGD [7] achieves differential privacy during neural network training by: (1) gradient clipping: clip each per-sample gradient to norm at most $C$ ; (2) Gaussian noise addition: add noise $\mathcal{N}(0, \sigma^2 C^2 I)$ to the sum of clipped gradients before the weight update. The privacy cost accumulates with training steps and is tracked with the moments accountant.

Privacy-accuracy trade-off. Adding noise degrades model accuracy. The optimal noise level depends on the dataset size $N$ , the sensitivity (clip norm $C$ ), and the number of training steps $T$ . For large $N$ the noise is small relative to the gradient signal; DP-SGD at $\epsilon = 8$ loses only 1-2% accuracy on CIFAR-10. For small $N$ (medical datasets with thousands of records) the trade-off is severe.

Federated learning

Federated learning [8] trains a model across multiple devices or organisations without centralising the raw data. The canonical algorithm is FedAvg:

A central server sends the current model weights $w_t$ to a subset of $K$ clients.
Each client trains locally for $E$ epochs on its private data, producing updated weights $w_t^k$ .
The server aggregates: $w_{t+1} = \sum_k \frac{n_k}{N} w_t^k$ , where $n_k$ is client $k$ ‘s dataset size and $N = \sum_k n_k$ .
Repeat.

Raw data never leaves the client. This addresses both privacy regulations (GDPR) and practical constraints (edge devices that cannot upload data). Combining federated learning with DP-SGD provides formal privacy guarantees even against a malicious server.

Challenges: communication cost (sending model weights to thousands of clients), statistical heterogeneity (client data is non-iid), and system heterogeneity (devices have different compute and battery constraints).

Pitfalls

Choosing the wrong fairness criterion

Demographic parity sounds intuitive but can require the model to make less accurate predictions for one group to equalise prediction rates. If Group A has a 5% positive rate and Group B has a 20% positive rate in the data, enforcing demographic parity forces the model to either over-predict for Group A or under-predict for Group B. In a loan application setting, this directly harms accuracy and may not actually benefit the disadvantaged group. Always state explicitly which fairness criterion you are optimising and why it is appropriate for the specific decision context.

Attention weights are not faithful explanations

A common mistake is to visualise attention weights and conclude “the model is looking at these words when making its prediction.” Jain and Wallace [6] showed that attention distributions can be adversarially perturbed without changing model predictions, and that different attention distributions produce the same output. Attention reflects what the model attends to, not what it uses. Use Integrated Gradients or SHAP for faithful attribution in transformer models.

Use TreeSHAP for tabular models in production

For tree-based models (XGBoost, LightGBM, sklearn RandomForest), TreeSHAP computes exact Shapley values in polynomial time and is production-fast. For a 100-tree XGBoost model with depth 6, TreeSHAP computes 10,000 SHAP values in under 1 second. Use this rather than KernelSHAP (which is slow and approximate) for feature attribution at inference time.

Pop quiz

Check yourself

Score: 0 / 4(0 answered)

1. The fairness impossibility theorem states that:
2. The Shapley value efficiency axiom states that:
3. Integrated Gradients satisfies completeness, meaning:
4. In (epsilon, delta)-differential privacy, smaller epsilon means:

Interview Q&A

Sketch the fairness impossibility theorem. When can all three criteria hold simultaneously?onsite

Consider a binary classifier predicting recidivism (positive = will reoffend) for two groups with base rates $b_0 < b_1$ . Define:

PPV (precision): $P(Y=1 | \hat{Y}=1)$
FPR: $P(\hat{Y}=1 | Y=0)$
FNR: $P(\hat{Y}=0 | Y=1)$

From Bayes: $\text{PPV} = b(1-\text{FNR}) / [b(1-\text{FNR}) + (1-b)\text{FPR}]$ .

If FPR and FNR are equal across groups (equalized odds), but $b_0 \neq b_1$ , plugging into the Bayes equation shows $\text{PPV}_0 \neq \text{PPV}_1$ .

So equalized odds implies unequal PPV (predictive parity violation). Conversely, equal PPV across groups (calibration) combined with equal FPR implies unequal FNR when base rates differ.

When can all hold? Only when $b_0 = b_1$ (equal base rates) or when the classifier is perfect (FPR = FNR = 0 for both groups, so PPV = 1 trivially).

Implication: the choice of fairness criterion is a value judgment. Equal opportunity favours Group 1 (qualified applicants in each group have equal chance of acceptance). Demographic parity favours equal acceptance rates. Calibration favours accuracy within each group. Each criterion privileges different stakeholders.

Derive the Shapley value formula and explain why it is the unique fair attribution satisfying the four axioms.staff

The Shapley value allocates the total “payout” $v(N)$ of a coalition game among $d$ players. For ML, the “game” is predicting $f(x)$ and each “player” is an input feature. The coalition value $v(S) = \mathbb{E}[f(X) | X_S = x_S]$ is the expected prediction when only features $S$ are known.

\phi_i = \sum_{S \subseteq N \setminus \{i\}} \frac{|S|!(d-|S|-1)!}{d!} [v(S \cup \{i\}) - v(S)].

The weight $|S|!(d-|S|-1)!/d!$ is the probability that coalition $S$ forms before feature $i$ joins, under a uniformly random ordering. The value $v(S \cup \{i\}) - v(S)$ is feature $i$ ‘s marginal contribution given $S$ .

Uniqueness. Shapley proved that the four axioms (efficiency, symmetry, dummy, additivity) uniquely determine this formula. Proof sketch by efficiency + linearity: efficiency forces the sum to equal $f(x) - \mathbb{E}[f]$ . Symmetry forces interchangeable features to get equal shares. Dummy forces non-contributing features to get zero. Additivity forces the attribution to decompose across additive model components. Together these four constraints have exactly one solution, which is the Shapley formula.

For an interview follow-up. TreeSHAP computes exact Shapley values for tree ensembles in $O(TLD^2)$ by recursive tree traversal. KernelSHAP approximates them for any model by sampling feature coalitions and fitting a weighted linear regression. Both are guaranteed to satisfy all four Shapley axioms.

Interactive Demo

Fairness Metrics Explorer

Explore how demographic parity, equal opportunity, and predictive parity relate - and why they cannot all be satisfied simultaneously when base rates differ.

Group A base rate0.50

Group B base rate0.30

Model threshold0.50

Demographic Parity

Selection Rate equal?

0.45 vs 0.31

UNEQUAL

Equal Opportunity

True Positive Rate equal?

0.80 vs 0.80

EQUAL

Predictive Parity

PPV equal?

0.89 vs 0.77

UNEQUAL

Group A Confusion Matrix

TP=40

FP=5

FN=10

TN=45

Group B Confusion Matrix

TP=24

FP=7

FN=6

TN=63

Impossibility Theorem: Because Group A and Group B have different base rates, it is mathematically impossible to satisfy all three fairness criteria simultaneously (Chouldechova, 2017). At least one metric will be unequal.

Tip: Set different base rates for Group A and B and notice that you cannot make all three metrics equal simultaneously - this is the fairness impossibility theorem.

References

Chouldechova, A. (2017). Fair Prediction with Disparate Impact: A Study of Bias in Recidivism Prediction Instruments. Big Data. arXiv:1610.07524
Kleinberg, J., Mullainathan, S., and Raghavan, M. (2016). Inherent Trade-Offs in the Fair Determination of Risk Scores. ITCS 2017. arXiv:1609.05807
Lundberg, S. M., and Lee, S.-I. (2017). A Unified Approach to Interpreting Model Predictions. NeurIPS 2017. arXiv:1705.07874
Ribeiro, M. T., Singh, S., and Guestrin, C. (2016). "Why Should I Trust You?": Explaining the Predictions of Any Classifier. KDD 2016. arXiv:1602.04938
Sundararajan, M., Taly, A., and Yan, Q. (2017). Axiomatic Attribution for Deep Networks. ICML 2017. arXiv:1703.01365
Jain, S., and Wallace, B. C. (2019). Attention is not Explanation. NAACL 2019. arXiv:1902.10186
Abadi, M., Chu, A., Goodfellow, I., McMahan, H. B., Mironov, I., Talwar, K., and Zhang, L. (2016). Deep Learning with Differential Privacy. CCS 2016. arXiv:1607.00133
McMahan, H. B., Moore, E., Ramage, D., Hampson, S., and y Arcas, B. A. (2017). Communication-Efficient Learning of Deep Networks from Decentralized Data. AISTATS 2017. arXiv:1602.05629

Safety & Alignment