Sparse Counterfactual

The defining characteristic is the explicit optimization for the L0 norm—the count of non-zero changes—rather than just minimizing the magnitude of change (L1/L2). This forces the algorithm to identify the single most influential lever or a minimal set of levers.

• Objective: Minimize ||x_cf - x_orig||_0 subject to f(x_cf) == target.
• Contrast: A dense counterfactual might suggest tiny adjustments to 50 features, which is operationally useless. A sparse one suggests changing 1-3 features.

Sparsity is not just a mathematical convenience; it is a human-factors requirement. Working memory is limited, and a recommendation to change 7 things is often ignored or bungled.

• Actionability: A loan officer can easily verify 'increase income by $5k' and 'reduce debt ratio by 2%'. They cannot manually re-optimize 30 variables.
• Trust: Users trust explanations they can mentally simulate. A sparse change is a causal story that is easy to verify.

Achieving true sparsity is computationally hard (NP-hard), so practical systems use convex relaxations or dedicated solvers.

• L1 Regularization: Adding a penalty λ||x_cf - x_orig||_1 to the loss function encourages sparsity as a proxy for the L0 norm.
• Mixed-Integer Programming (MIP): For tabular data, MIP solvers can explicitly model the binary decision to change a feature or not, guaranteeing exact sparsity.

Sparsity (number of features changed) and Proximity (distance in feature space) are distinct and often conflicting objectives.

• Trade-off: A very close counterfactual (low L2 distance) might require changing many features slightly. A sparse one might require a larger jump in a single feature.
• Example: To flip a credit denial, a sparse explanation might say 'Increase savings by $20,000'. A proximate but dense one might say 'Increase savings by $10, change spending habits by 0.1%, and move to a different zip code'.

Sparsity naturally complements feasibility constraints. If a user can only change 2 out of 100 features, the algorithm must be sparse by definition.

• Action Sets: By pre-defining an action set of mutable features, the sparsity constraint forces the model to find a solution strictly within the user's limited sphere of control.
• Causal Sparse Counterfactuals: The most robust approaches combine sparsity with a structural causal model (SCM) to ensure the few changed features don't violate causal laws (e.g., changing 'age' to increase 'education level').

Sparsity is a primary quantitative metric in benchmarking counterfactual generation algorithms.

• Mean Sparsity: The average number of features changed across a test set of generated counterfactuals.
• Sparsity vs. Validity: A critical diagnostic plot. If a method achieves high validity but low sparsity, it's likely generating trivial, dense noise rather than insightful explanations.

The end-goal of sparse counterfactuals. Algorithmic recourse translates a model's decision flip into a set of actionable recommendations for the end-user. Sparse counterfactuals are preferred for recourse because they minimize the cognitive load and effort required to change a decision.

• Goal: Provide a path to a favorable outcome.
• Sparsity Link: Fewer feature changes = easier recourse.
• Constraint: Must respect real-world actionability.

A metric quantifying the distance between the original input and the counterfactual. While standard proximity uses dense L1/L2 norms, sparse counterfactuals optimize for the L0 norm, which counts the number of features changed.

• L0 Norm: Penalizes the count of altered features.
• Trade-off: Often a balance between proximity and sparsity.
• Objective: Minimize feature changes, not just vector distance.

A formal specification of permissible modifications for each feature. Sparse counterfactuals must operate within this boundary to ensure recommendations are realistic. An action set defines which features are mutable and the valid range of change.

• Immutable Features: Locked from modification (e.g., age).
• Mutable Features: Can be changed within defined limits.
• Sparsity Constraint: The algorithm selects the minimal subset of mutable features.

A counterfactual that lies within the high-density region of the training data distribution. Sparse changes risk creating implausible outliers if not constrained. Plausibility ensures the sparse explanation is a realistic, in-distribution instance.

• Density Check: Uses Mahalanobis distance or autoencoder loss.
• Avoids Artifacts: Prevents adversarial, unrealistic combinations.
• Sparsity Synergy: Sparse changes are more likely to stay plausible.

Generating a set of distinct sparse counterfactuals rather than a single explanation. This provides users with multiple minimal-change paths to a desired outcome, increasing the chance that at least one recommendation is feasible.

• Diversity Metric: Measures feature set dissimilarity between explanations.
• User Choice: Empowers the user to select the easiest path.
• Sparse Diversity: Each option in the set should change a different, small subset of features.

A binary evaluation metric verifying that the sparse counterfactual successfully flips the model's prediction to the target outcome. Validity is non-negotiable; a sparse explanation that doesn't change the decision is useless.

• Binary Check: Pass or fail.
• Precision: Must exactly match the desired target class.
• Sparsity Trade-off: Extreme sparsity constraints can reduce validity rates.