Joint Distribution-Informed Shapley Values for Sparse Counterfactual Explanations

The paper introduces COLA, a model-agnostic post-hoc framework that leverages optimal transport and Shapley-based attribution to refine counterfactual explanations, significantly reducing the number of required feature edits while preserving prediction changes and ensuring proximity to the original input.

The Gist

Imagine you are trying to get a loan approved by a bank's AI system. The AI says "No." You ask, "What do I need to change to get a 'Yes'?"

The AI gives you a counterfactual explanation: "If you increased your income by $50,000, bought a new car, changed your job, and moved to a different city, you would get approved."

While technically correct, this advice is useless. It asks you to change everything. You can't just move to a new city or buy a car overnight. You need a realistic, minimal plan: "Just increase your income by $5,000."

This paper introduces a new tool called COLA (Counterfactuals with Limited Actions) to fix this problem. It turns a messy, overwhelming list of changes into a simple, actionable to-do list.

Here is how it works, using simple analogies:

1. The Problem: The "Kitchen Remodel" vs. The "Paint Job"

Current AI methods often act like a contractor who, when asked to fix a leaky faucet, decides to tear out the whole kitchen and install a new island. They find a solution that works, but it's overkill. They change too many features (income, job, location, car) when only one or two needed tweaking.

The goal of this paper is to find the "Paint Job" solution: the smallest, cheapest set of changes that still gets you the "Yes" from the bank.

2. The Solution: COLA (The Smart Editor)

COLA is a "post-hoc" framework. This means it doesn't replace the AI that gave you the bad advice; it acts as a smart editor that takes the AI's long, messy list of changes and trims it down.

It does this in two main steps:

Step A: The "Dance Partner" Match (Optimal Transport)

Imagine you have a group of people who got rejected (Factuals) and a group of people who got accepted (Counterfactuals).

• Old Method: The AI might randomly pair a rejected person with an accepted person just because they are in the same room. This leads to weird advice (e.g., telling a 20-year-old student to copy the habits of a 60-year-old CEO).
• COLA's Method (Optimal Transport): COLA acts like a strict dance instructor. It uses math to find the perfect partner for each rejected person. It asks: "Who is the most similar person in the 'Accepted' group to this specific 'Rejected' person?"
  • It pairs the 20-year-old student with a 22-year-old junior employee who got accepted.
  • It pairs the 60-year-old CEO with a retired executive who got accepted.
  • Why this matters: By matching similar people, the advice becomes realistic. You aren't told to copy a stranger; you are told to make small tweaks to match someone just like you who succeeded.

Step B: The "Shapley Scorecard" (p-SHAP)

Once the partners are matched, we need to know exactly what changed.

• The Old Way: Sometimes, AI just looks at which features are generally important (e.g., "Income is always important!"). But maybe for this specific person, income isn't the issue; it's their debt-to-income ratio.
• COLA's Way (p-SHAP): This is a special scoring system. It looks at the specific "Dance Partner" pair and calculates exactly how much each feature contributed to the success.
  • It says: "For this specific pair, changing the income by $5k was 80% of the reason they got approved. Changing the car was 0%."
  • It then picks the top few changes that give the biggest "bang for the buck."

3. The Result: The Minimal Action Plan

After COLA does its work, the advice changes from:

"Change your job, move cities, buy a car, and double your income."

To:

"Just increase your savings by $2,000."

The Key Takeaways

• Less is More: In experiments, COLA achieved the same "Yes" result as other methods but required only 26% to 45% of the changes. It cut out the fluff.
• It Works Everywhere: It doesn't care what kind of AI model you are using (neural networks, decision trees, etc.) or how the original explanation was generated. It just takes the output and refines it.
• Theoretical Guarantee: The math proves that COLA's refined advice will never be further away from your current reality than the original, messy advice. It's a safe bet.

In a Nutshell

Think of COLA as a personal stylist for AI advice. If the AI says, "To look good, you need a new wardrobe, a new haircut, and a new car," COLA steps in and says, "Actually, you just need to swap your shirt and tie. You'll look great, and you'll save a lot of money."

It makes AI explanations actionable, realistic, and human-friendly.

Technical Summary

1. Problem Definition

The paper addresses a critical limitation in Counterfactual Explanations (CE): existing methods often suggest changes to too many features to flip a model's prediction, reducing the clarity and actionability of the explanation. While Feature Attribution (FA) methods (like Shapley values) identify important features, they are often decoupled from CE, leading to suboptimal or misleading action plans.

The core problem is formulated as an optimization task:
Given a factual instance $x$ and a target outcome $y^*$, find a counterfactual instance $z$ that achieves the target while minimizing the number of feature modifications (sparsity).
$$\min_{c, z} D(f(z), y^*) \quad \text{s.t.} \quad D(z, x) \le \epsilon, \quad \sum c_{ik} \le C$$
Where $c$ is a binary indicator for feature changes, and $C$ is the maximum allowed changes. The challenge lies in the NP-hard nature of this discrete sparsity problem and the lack of a unified framework that works across different CE generators and model types without strong assumptions (e.g., differentiability).

2. Methodology: The COLA Framework

The authors propose COLA (COunterfactuals with Limited Actions), a model- and generator-agnostic post-hoc framework. COLA refines any existing counterfactual set $r$ (generated by an arbitrary CE algorithm) into a sparse set $z$ using a novel attribution method called p-SHAP.

The framework operates in four main steps:

1. Counterfactual Generation (ACE): An arbitrary CE algorithm generates a set of counterfactuals $r$ close to the factual data $x$.
2. Optimal Transport (OT) Coupling: Instead of assuming a random or fixed alignment between factuals and counterfactuals, COLA computes a joint distribution (coupling) $p$ between $x$ and $r$ using Optimal Transport (OT).
   • The OT plan $p_{OT}$ minimizes the transportation cost (feature modification distance) between the factual and counterfactual distributions.
   • This step solves the "alignment problem," determining which counterfactual $r_j$ best corresponds to which factual $x_i$ to minimize the cost of transition.
3. p-SHAP Attribution: The authors introduce p-SHAP, a generalized Shapley value method.
   • Unlike standard Shapley methods that use a random baseline or a specific counterfactual distribution, p-SHAP uses the OT-derived joint distribution $p$ to define the background distribution for the Shapley calculation.
   • This unifies various Shapley methods (Baseline, Random, Counterfactual) under a single framework where the coupling $p$ dictates the alignment.
   • Theoretically, p-SHAP minimizes an upper bound on the $W_1$ (Wasserstein-1) divergence between the factual outcome and the target, ensuring that the selected features are the most efficient path to the target.
4. Sparse Action Selection:
   • The Shapley values are normalized to form a probability matrix $\phi$.
   • A greedy selection process samples $C$ feature indices based on $\phi$ to determine which features to modify.
   • The values for these features are updated using a value assignment strategy (e.g., $A_{max}^{Value}$ or $A_{avg}^{Value}$) derived from the aligned counterfactuals $r$.

3. Key Contributions

• Novel Framework (COLA): The first post-hoc framework to systematically refine CE for sparsity without being tied to a specific CE generator or model architecture.
• p-SHAP Method: A new Shapley attribution method that integrates Optimal Transport to handle the alignment between factual and counterfactual distributions. It theoretically guarantees that the refined counterfactuals do not move farther from the factuals than the original proposals.
• Theoretical Guarantees:
  • Theorem 4.1: Proves that the OT coupling minimizes an upper bound on the $W_1$ divergence between the factual and target outcomes, linking feature modification cost directly to the counterfactual effect.
  • Theorem 5.1: Proves that the refined counterfactual $z$ is strictly closer (or equal) to the factual $x$ than the aligned reference $q$, ensuring no additional divergence is introduced.
• Agnostic Design: Works with any black-box model and any CE generator (e.g., DiCE, AReS, KNN, GlobeCE).

4. Experimental Results

The authors evaluated COLA across 4 datasets (HELOC, German Credit, Hotel Bookings, COMPAS), 12 models (ranging from Linear Regression to Deep Neural Networks), and 5 CE generators.

• Action Reduction: COLA achieves the same target counterfactual effects (80–100%) using only 26%–45% of the original feature edits required by the baseline CE methods. In some scenarios, it reduces edits to as low as 13%.
• Superiority of p-SHAP: Ablation studies show that p-SHAP (using OT coupling) significantly outperforms other Shapley variants (Baseline, Random, and standard Counterfactual Shapley) in terms of sparsity and achieving the target effect.
• Near-Optimality: On a small-scale benchmark (German Credit) where the optimal solution was computed via Mixed Integer Linear Programming (MILP), COLA demonstrated near-optimal performance, validating its effectiveness in solving the NP-hard sparsity problem.
• Robustness: The method performs consistently across different divergence metrics (OT, MMD, Mean Difference) and model types.

5. Significance and Impact

• Practical Actionability: By drastically reducing the number of required feature changes, COLA makes counterfactual explanations more actionable for end-users (e.g., a loan applicant needs to change fewer variables to get approved).
• Theoretical Unification: It bridges the gap between Feature Attribution and Counterfactual Explanations, showing that proper alignment (via OT) is crucial for effective attribution.
• General Applicability: As a post-hoc framework, it can be retrofitted to existing CE pipelines, enhancing their performance without requiring retraining of the underlying models or the CE generators.
• Ethical Considerations: The paper explicitly addresses ethical risks, noting that while COLA reduces the number of edits, it does not inherently guarantee fairness or causal validity. It emphasizes the need for constraints on immutable attributes (e.g., race, gender) and human oversight in high-stakes domains.

In summary, COLA provides a mathematically grounded, efficient, and flexible solution to the problem of "sparse counterfactuals," leveraging Optimal Transport to guide Shapley values toward the most cost-effective action plans.