Technical Summary: P2CE – Model-Agnostic Plausible Pareto-Optimal Counterfactual Explanations

Problem Statement

The increasing deployment of machine learning in high-stakes domains (e.g., credit scoring, hiring, health diagnosis) necessitates transparency and fairness. Counterfactual explanations (CEs) address this by suggesting minimal changes to input features ($x \to x'$) that would alter a model's prediction from an undesired outcome to a desired one. However, existing methods face three critical challenges:

1. Plausibility: Many algorithms generate solutions that are mathematically close to the input but lie outside the natural data distribution (outliers), rendering them unrealistic for individuals to achieve.
2. Feasibility Trade-offs: There is no single metric for "feasibility." Users may prefer small changes across many features or moderate changes across few features. Single-objective optimization fails to capture these diverse preferences.
3. Model Agnosticism and Efficiency: While some methods are model-agnostic, they often struggle with computational efficiency or rely on assumptions (like model monotonicity) that do not hold for complex non-linear models (e.g., Neural Networks, SVMs).

Methodology

The authors propose P2CE, an algorithm designed to generate Plausible Pareto-Optimal Counterfactual Explanations. The approach combines a branch-and-bound search strategy with two key innovations to ensure plausibility and efficiency across any black-box model.

1. Search Strategy and Multi-Objective Optimization

P2CE searches a discretized grid of possible feature changes ($A = A^{(1)} \times \dots \times A^{(d)}$) to find a set of actions $a$ such that $f(x+a) \geq \tau$. It optimizes multiple objectives simultaneously:

• Average Continuous Distance ($c_1$): The normalized average magnitude of changes in numerical features.
• Maximum Continuous Distance ($c_2$): The maximum magnitude of change in any single numerical feature.
• Number of Changes ($c_3$): The count of features altered (sparsity).

The algorithm returns a Pareto-optimal set, ensuring no other solution exists that is better or equal in all objectives.

2. Ensuring Plausibility via Outlier Detection

To prevent the generation of outliers (solutions outside the data distribution), P2CE integrates an Isolation Forest outlier detector ($u$).

• During the search, whenever a candidate solution $x+a$ is found, $u(x+a)$ is evaluated.
• If $u(x+a)$ indicates an outlier, the solution is discarded.
• Efficiency Gain: P2CE leverages the Isolation Forest's ability to handle missing values. If a partial solution (with some features undefined) is already classified as an outlier, the algorithm prunes the entire branch of the search tree, avoiding unnecessary computations.

3. Model-Agnostic Branch-and-Bound Pruning

To maintain computational efficiency without assuming model monotonicity (which limits previous methods like MAPOCAM), P2CE estimates the maximum possible prediction ($f_a$) reachable from a partial action $a$.

• SHAP-Based Estimation: The algorithm utilizes the additive property of SHAP values: $f(x) = E[f(x)] + \sum \phi_i$.
• It calculates an upper bound for the prediction by assuming the "best-case" scenario for the remaining open features (those not yet fixed in the search).
• The bound is formulated as:
  $$\max f(x+\tilde{a}) \leq f(x) - \sum_{i \in O_k} \phi_i(x) + \sum_{i \in O_k} \bar{\phi}_i + R(x, O_k)$$
  Where $O_k$ represents the $k$ features with the highest potential attribution, $\bar{\phi}_i$ is the maximum possible attribution for feature $i$, and $R$ is a residual term.
• If this upper bound is below the decision threshold $\tau$, the branch is pruned. This allows P2CE to function efficiently with non-monotonic models like Neural Networks.

Key Contributions

1. P2CE Algorithm: A novel, model-agnostic algorithm that generates Pareto-optimal counterfactual explanations while strictly enforcing data distribution plausibility via outlier detection.
2. SHAP Property Exploration: The introduction of a method to use SHAP values for estimating maximum predictions in a branch-and-bound context, removing the monotonicity constraint required by previous state-of-the-art methods.
3. Comprehensive Evaluation: An extensive empirical study across three datasets (German Credit, Taiwan Credit, Adult) and three classifiers (Logistic Regression, LightGBM, MLP), comparing P2CE against MAPOCAM, DiCE, and NICE.
4. Open Source: The release of the implementation to facilitate reproducibility.

Experimental Results

The evaluation focused on solution quality (hypervolume of the Pareto frontier), plausibility (percentage of outliers), and computational efficiency.

• Plausibility: P2CE consistently generated significantly fewer outlier solutions compared to competitors. For instance, on the Adult dataset with an MLP, P2CE produced only 11% outliers, whereas DiCE produced 87% and MAPOCAM produced 58%. In some cases, DiCE suggested impossible scenarios (e.g., 97 hours of work per week).
• Solution Quality: P2CE achieved hypervolume scores comparable to MAPOCAM (the theoretical gold standard for Pareto optimality) and significantly outperformed DiCE and NICE. While MAPOCAM occasionally achieved slightly higher hypervolumes, this came at a steep computational cost.
• Efficiency: P2CE demonstrated superior computational efficiency, particularly with complex non-linear models.
  • On the Taiwan dataset with an MLP, MAPOCAM took an average of 118.5 seconds, whereas P2CE took 0.81 seconds.
  • On the Adult dataset with an MLP, MAPOCAM took 6.24 seconds, while P2CE took 2.34 seconds.
  • P2CE was slower than DiCE and NICE in raw time but provided the crucial guarantee of Pareto optimality and plausibility, which the faster methods lacked.

Significance and Claims

The paper positions P2CE as a practical solution for real-world applications where counterfactual explanations must be both actionable (feasible for the user) and plausible (consistent with real-world data).

The authors claim that P2CE successfully bridges the gap between theoretical optimality and practical utility. By ensuring solutions are "inliers," the algorithm prevents the generation of misleading advice (e.g., suggesting a user increase their income by 1000% or work impossible hours). Furthermore, by leveraging SHAP values for pruning, P2CE extends the capability of generating optimal counterfactuals to any black-box model, overcoming the limitations of previous methods that were restricted to monotonic or specific model types.

The work concludes that P2CE enables faster, more informed decision-making in real-world applications by providing a diverse set of high-quality, plausible trade-offs without requiring model-specific adaptations.

Limitations and Future Work

The authors acknowledge two primary limitations:

1. SHAP Dependency: The efficiency of the pruning strategy relies on SHAP approximations. Calculating exact Shapley values is computationally expensive (exponential in the number of features), though approximations are used. Errors in these approximations could theoretically affect pruning, though empirical results suggest the impact is minimal compared to the gains in speed.
2. Discretized Grid: The search is constrained to a discrete grid. While this is practical for most applications (e.g., suggesting an income increase of 1,000 dollars vs. 998 dollars is functionally similar), extremely fine granularity increases search time. The authors suggest future work on adaptive grids that adjust granularity based on feature impact, potentially guided by SHAP values.