Counterfactual Explanations for Optimization-Based Decisions in the Context of the GDPR

Anton Korikov, Alexander Shleyfman, J. Christopher BeckIJCAI 2021 · DOI

TL;DR

This paper tackles the challenge of providing "why not" explanations for decisions made by optimization models, particularly in the context of GDPR's right to explanation. They introduce a novel framework based on inverse combinatorial optimization to generate counterfactual explanations that identify minimal changes to parameters leading to a desired alternative outcome. This work offers a computationally efficient way to explain complex optimization decisions to individuals.

What Problem Does This Paper Address?

The General Data Protection Regulation (GDPR) grants individuals the right to an explanation for automated decisions that affect them. While this right is legally established, its practical implementation, especially for complex decision-making systems, remains a significant challenge. Many high-impact decisions in areas like healthcare, social services, and finance are made using optimization models. Explaining why a specific decision was made by these models, and more importantly, what would have needed to be different for a different outcome (a counterfactual explanation), is crucial for user understanding, contesting decisions, and ensuring fairness. Existing explainable AI (XAI) methods often focus on making model internals understandable or providing local approximations, which may not directly address the "what if" scenario required by regulations like GDPR. This paper specifically addresses the gap in providing counterfactual explanations for decisions derived from declarative optimization models.

Methods

The core contribution of this paper is the formulation of the Nearest Counterfactual Explanation (NCE) problem for optimization-based decisions. This problem is framed as a generalization of inverse combinatorial optimization. Given an optimization model, its parameters, and a decision made, the NCE problem seeks to find the minimal change to the model's parameters that would make a specific alternative (foil) decision optimal.

The authors define the NCE problem formally: $$ \min ||\bar{c} - c|| \quad \text{s.t.} \quad \min_{x \in X_{\psi}} f(\bar{c}, x) = \min_{x \in X} f(\bar{c}, x) $$ where $c$ are the original parameters, $\bar{c}$ are the modified parameters, $f$ is the objective function, $X$ is the feasible set of decisions, and $X_{\psi}$ is the subset of $X$ satisfying a foil constraint $\psi$.

They then focus on two common objective functions:

  1. Weighted Sum of Binary Variables (WSBV): For problems like weighted MaxSAT or 0-1 knapsack, they show that the NCE problem can be solved in closed-form by solving a slightly modified version of the original optimization problem. Specifically, for a foil constraint $\psi: x_j = 1$, the optimal parameter change $\bar{c}_j$ is $c_j + \Delta(c)$, where $\Delta(c)$ is the difference between the optimal objective values of the foil and factual solutions.
  2. Weighted Sum of Integer Variables (WSIV): For problems like medical appointment scheduling, where variables are integers, the NCE problem is more complex. They demonstrate that the problem can be solved using binary search over potential parameter values. This is achieved by proving that the difference in objective values ($\Delta(y)$) is a monotonically non-increasing function of the parameter being modified, allowing for efficient search.

Datasets

Not discussed in the paper. The paper focuses on theoretical development and algorithmic approaches rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Bridging GDPR and Optimization: The paper provides a concrete algorithmic framework for fulfilling the GDPR's right to explanation for a class of widely used decision-making systems (optimization models).
  • Inverse Optimization for "Why Not": By framing the problem as inverse optimization, they elegantly capture the essence of counterfactual explanations – finding the minimal parameter change to achieve an alternative outcome.
  • Efficiency for Binary Problems: The closed-form solution for WSBV problems is a significant finding, implying that generating explanations for these models can be nearly as efficient as solving the original optimization problem itself.
  • Binary Search for Integer Problems: The application of binary search for WSIV problems is a clever way to handle the increased complexity, ensuring that explanations can still be generated efficiently, albeit with a logarithmic overhead.
  • Focus on Minimal Changes: The emphasis on finding the minimal perturbation to parameters aligns with the intuitive understanding of a counterfactual explanation – what's the smallest change that would have led to a different outcome?

Key Results

  • Closed-form solution for WSBV: For problems with weighted sums of binary variables, the optimal parameter change for a counterfactual explanation can be computed directly.
  • Logarithmic complexity for WSIV: For problems with weighted sums of integer variables, counterfactual explanations can be found using binary search, requiring a logarithmic number of forward optimization problem solves.
  • Theoretical guarantees: The paper provides theoretical proofs for the monotonicity of the objective difference function in WSIV problems, which underpins the binary search approach.

Limitations and Future Work

The authors acknowledge several limitations and suggest future research directions:

  • Single Parameter Restriction: The current framework primarily focuses on explaining changes related to a single parameter of the questioner. Extending this to multiple parameters concerning the questioner would require advancements in general partial inverse optimization, which is a challenging area, especially for discrete variables.
  • Foil Must Be Sub-optimal: The current approach assumes that the foil decision is not optimal for the original parameters. The paper notes that it's unclear what a meaningful explanation would be if the foil is already optimal or infeasible.
  • Parameters Not in Constraints: The framework assumes that parameters only appear in the objective function, not in constraints. Lifting this restriction would significantly complicate the mathematical framework and is an important area for future research.
  • Understanding Input Weights: The paper assumes users understand their assigned weights (e.g., acuity scores). If users don't understand how these weights are determined, they need explanations about the input assignment process, which is beyond the scope of this work.
  • Broader Optimization Models: While WSBV and WSIV cover many important cases, extending the framework to other types of optimization models (e.g., non-linear objectives, different constraint types) is a natural next step.
  • Empirical Evaluation: The paper is primarily theoretical. Future work could involve implementing these methods and evaluating their performance and user-perceived usefulness on real-world optimization problems.

Summary updated

BibTeX
@inproceedings{korikov2021counterfactual,
  author = {Anton Korikov and Alexander Shleyfman and J. Christopher Beck},
  title = {{Counterfactual Explanations for Optimization-Based Decisions in the Context of the GDPR}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.24963/ijcai.2021/564},
}
Figure