Counterfactual explanations

What ARE Counterfactual Explanations?

Why these three criteria?

• Proximity: If changes are huge, the explanation isn't useful ("To get approved, become a different person").
• Validity: $f(\mathbf{x}')$ must actually produce $y'$ (not just be close).
• Plausibility: $\mathbf{x}'$ must be realistic (age can't be negative, you can't "uncomplete" a degree).

HOW to Generate Counterfactuals

Derivation from First Principles

Problem setup: We have $\mathbf{x} \in \mathbb{R}^d$ and black-box $f: \mathbb{R}^d \to \{0,1\}$ with $f(\mathbf{x}) = 0$ (loan denied). We want $\mathbf{x}'$ where $f(\mathbf{x}') = 1$ (approved).

Step 1: Define the loss function

We need to balance three competing goals:

$\mathcal{L}(\mathbf{x}') = \underbrace{\|\mathbf{x}' - \mathbf{x}\|_1}_{\text{sparsity}} + \lambda \underbrace{\text{hinge}(f(\mathbf{x}'))}_{\text{prediction loss}} + \gamma \underbrace{d_{\text{manifold}}(\mathbf{x}')}_{\text{realism}}$

Why each term?

1. $L_1$ distance ($\|\mathbf{x}' - \mathbf{x}\|_1$): Encourages changing few features. $L_1$ gives sparse solutions (many components stay at zero change). Why not $L_2$? $L_2 = \sqrt{\sum (x_i' - x_i)^2}$ spreads change across many features; $L_1= \sum |x_i' - x_i|$ concentrates it.

2. Hinge loss on prediction: For binary classifier outputing probability $p = f(\mathbf{x}')$: $\text{hinge}(p) = \max(0, 0.5 - p)$ This is zero when $p > 0.5$ (desired class), positive otherwise. Why hinge? Differentiable, pushes $p$ past decision boundary.

3. Manifold distance: Penalizes unrealistic combinations. Could use:

   • Distance to nearest training point: $\min_{\mathbf{x}_i \in \text{train}} \|\mathbf{x'} - \mathbf{x}_i\|$
   • VAE reconstruction error: $\|\text{VAE-decode}(\text{VAE-encode}(\mathbf{x}')) - \mathbf{x}'\|$
   • Feature validity constraints (age $\geq 0$, categorical levels)

Step 2: Optimization

Gradient-based (Wachter et al. 2017): $\mathbf{x}'^{(t+1)} = \mathbf{x}'^{(t)} - \alpha \nabla_{\mathbf{x}'} \mathcal{L}(\mathbf{x}'^{(t)})$

Start with $\mathbf{x}'^{(0)} = \mathbf{x}$, iterate until $f(\mathbf{x}') = y'$ or max steps.

For categorical features: Use one-hot encoding, then round to nearest valid category after optimization.

For constraints (e.g., age $\geq 18$): Project $\mathbf{x}'$ onto feasible set after each step: $\mathbf{x}' \leftarrow \text{clip}(\mathbf{x}', \text{lower}_i, \text{upper}_i) \text{ for each feature } i$

WHY This Works: The Geometry of Decision Boundaries

Consider a linear classifier: $f(\mathbf{x}) = \text{sign}(\mathbf{w}^\top \mathbf{x} + b)$.

The decision boundary is $\mathbf{w}^\top \mathbf{x} + b = 0$. If $\mathbf{x}$ is on the negative side, the closest point on the boundary is: $\mathbf{x}_{\text{boundary}} = \mathbf{x} - \frac{\mathbf{w}^\top \mathbf{x} + b}{\|\mathbf{w}\|^2} \mathbf{w}$

Derivation: We want to minimize $\|\mathbf{x}' - \mathbf{x}\|^2$ subject to $\mathbf{w}^\top \mathbf{x}' + b = 0$. Use Lagrange multipliers: $\mathcal{L} = \|\mathbf{x}' - \mathbf{x}\|^2 + \mu(\mathbf{w}^\top \mathbf{x}' + b)$

Take $\nabla_{\mathbf{x}'} \mathcal{L} = 2(\mathbf{x}' - \mathbf{x}) + \mu \mathbf{w} = 0 \implies \mathbf{x}' = \mathbf{x} - \frac{\mu}{2}\mathbf{w}$.

Substitute into constraint: $\mathbf{w}^\top(\mathbf{x} - \frac{\mu}{2}\mathbf{w}) + b = 0 \implies \mu = \frac{2(\mathbf{w}^\top \mathbf{x} + b)}{\|\mathbf{w}\|^2}$.

Thus: $\mathbf{x}' = \mathbf{x} - \frac{\mathbf{w}^\top \mathbf{x} + b}{\|\mathbf{w}\|^2}\mathbf{w}$. ✓

For neural networks: The boundary is nonlinear, so we use gradient descent to "walk toward" it.

Methods for Generating Counterfactuals

1. Gradient-Based (Wachter et al.)

Algorithm:

Initialize x' = x
for t = 1 to max_iter:
    loss = ||x' - x||₁ + λ·hinge(f(x')) + γ·plausibility(x')
    x' = x' - α·∇(loss)
    x' = project_to_valid(x')  # enforce constraints
    if f(x') == y_target: break
return x'

Pros: Fast, works with any differentiable model. Cons: Can find adversarial (implausible) examples.

2. DiCE (Diverse Counterfactual Explanations)

Idea: Generate multiple diverse counterfactuals, not just one.

Why? Users want options: "Either increase income by $10k OR improve credit score by 40 points."

Method: Add diversity term to loss: $\mathcal{L} = \sum_{i=1}^k \|\mathbf{x}_i' - \mathbf{x}\|_1 + \lambda \sum_i \text{hinge}(f(\mathbf{x}_i')) - \gamma \sum_{i<j} \|\mathbf{x}_i' - \mathbf{x}_j'\|_1$

The last term penalizes counterfactuals being similar to each other. We want $\mathbf{x}_1', \mathbf{x}_2', \ldots$ to be far apart.

3. FACE (Feasible and Actionable Counterfactuals)

Adds causal constraints: Some features can't change (race, gender) or can only increase (education level).

Directed acyclic graph (DAG) $G$ encodes causal structure. Only allow changes consistent with $G$.

Evaluation Metrics for Counterfactuals

How do we measure counterfactual quality?

Trade-offs: Proximity vs. plausibility (closest counterfactual might be unrealistic). Sparsity vs. validity (changing1 feature might not suffice).

Connections LIME: Both provide local explanations, but LIME approximates with linear model, counterfactuals show specific input changes

• SHAP: SHAP explains "why this prediction?", counterfactuals explain "what to change?"
• Adversarial Examples: Counterfactuals are "good" adversarial examples (realistic, interpretable); adversarials are "bad" (minimal imperceptible noise)
• Causal Inference: Counterfactuals respect causal structure (do-calculus), unlike correlation-based methods
• Recourse: Algorithmic recourse = actionable counterfactuals subject to constraints (cost, feasibility)
• Model Debugging: Out-of-distribution counterfactuals reveal model flaws and biases

#flashcards/ai-ml

What are the three key properties a counterfactual explanation must satisfy? :: (1) Validity: $f(\mathbf{x}') = y'$ (different prediction), (2) Proximity: $\mathbf{x}'$ is close to $\mathbf{x}$ (minimal change), (3) Plausibility: $\mathbf{x}'$ is realistic/actionable

Write the optimization objective for generating a counterfactual $\mathbf{x}'$ from $\mathbf{x}$ :: $$\min_{\mathbf{x}'} |\mathbf{x}' - \mathbf{x}|1 + \lambda \cdot \text{hinge}(f(\mathbf{x}')) + \gamma \cdot d{\text{manifold}}(\mathbf{x}') \text{ where the three terms balance proximity, prediction validity, and realism.}

How does DiCE (Diverse Counterfactual Explanations) differ from single-counterfactual methods? :: DiCE generates multiple diverse counterfactuals by adding a diversity term -\gamma \sum_{i<j} |\mathbf{x}_i' - \mathbf{x}_j'| that penalizes similarity between counterfactuals. This gives users options: "Either increase income OR improve credit score."

For a linear classifier f(\mathbf{x}) = \text{sign}(\mathbf{w}^\top \mathbf{x} + b), what is the closest point on the decision boundary to \mathbf{x}? :::$\mathbf{x}_{\text{boundary}} = \mathbf{x} - \frac{\mathbf{w}^\top \mathbf{x} + b}{\|\mathbf{w}\|^2} \mathbf{w}$ This is derived by minimizing $\|\mathbf{x}' - \mathbf{x}\|^2$ subject to $\mathbf{w}^\top \mathbf{x}' + b = 0$ using Lagrange multipliers.

Concept Map

Hinglish (regional understanding)