Adequate and fair explanations

Nicholas Asher, Soumya Paul, Chris RussellarXiv 2020 · DOI · OpenReview

Abstract

Explaining sophisticated machine-learning systems is a foundational challenge in AI. While current methods range from local approximations to exact logical characterizations, a significant epistemological gap remains: exact explanations are often too complex for human comprehension. This paper addresses this by formalizing "adequate and fair" explanations using counterfactual logic. We define explanations as a pragmatic interaction designed to resolve a user’s specific "conundrum." By modeling this interaction as a game between an explainer and an explainee, we demonstrate that while finding adequate explanations is generally computationally intensive (PLS-complete), interactive "challenge games" can reduce this complexity to linear time while ensuring that hidden biases are exposed.

Introduction

The field of Explainable AI (XAI) is currently divided between two paradigms: local, human-interpretable approximations and rigorous, logical characterizations. The former offers accessibility at the cost of precision, while the latter offers precision at the cost of human graspability. This paper seeks to bridge this gap by defining what constitutes an "adequate" explanation—one that is both logically valid and epistemically accessible.

We argue that the utility of an explanation is inherently tied to the "conundrum" of the user—the specific misunderstanding or lack of information that prompted the query. Furthermore, we address the "Fairness Gap," where a model might provide a truthful but partial explanation that intentionally obscures prejudicial factors, such as race or gender, which influenced the decision.

Counterfactuals and Epistemic Accessibility

Following the work of Wachter et al. (2017), we utilize counterfactuals ("If feature $X$ were different, the outcome would be $Y$") as the primary vehicle for explanation. Counterfactuals are naturally "partial"; they do not list every causal factor, making them compact and readable.

We map David Lewis’s philosophical "possible worlds" logic onto machine learning feature spaces, showing that a counterfactual is essentially a minimal adversarial perturbation. However, because counterfactuals are partial, they can be used to hide explicit biases. To counter this, we explore the transition from local partial explanations to "complete local explanations" that characterize the decision boundary more fully.

The Pragmatics of Explanation: The Conundrum

An explanation is a response to a "Why?" question. We formalize the user's state of mind as a conundrum, which typically takes two forms:

  1. Mistake: The user believes a certain feature is more influential than it actually is.
  2. Incompleteness: The user is unaware of a feature that the model is utilizing.

An adequate explanation must resolve these specific states. We introduce the Flip Degree, a metric that measures the complexity of a model’s decision boundary around a specific data point. A high flip degree indicates a "messy" or non-convex logic, requiring more sophisticated explanations to resolve the user's conundrum.

Explanation Games and Fairness

To formalize the interaction between the system (the Explainer, $\mathcal{A}$) and the user (the Explainee, $\mathcal{E}$), we propose several "Explanation Games":

  • Forcing Games: The explainee requests different reasons until they find one that is satisfactory.
  • Challenge Games: The explainee provides a "challenge" (e.g., "I believe my income should have been sufficient for the loan"). The explainer must then either accept the challenge or provide a counter-reason.
  • Restriction Games: A variant where the explainer may be uncooperative or restricted in the information it can provide.

A "fair" explanation in this context is one that does not just solve the conundrum but also reveals if a "prejudicial factor" was an overdetermining cause. If a model's decision was influenced by a protected attribute, a fair explanation must expose this, even if a non-prejudicial counterfactual also exists.

Computational Complexity

Our analysis reveals significant differences in the computational cost of these interactions:

  • Logical Correspondence: We prove that counterfactual explanations can be converted into minimal, logically valid (LV) explanations in linear time relative to an NP oracle.
  • Search Complexity: Finding an adequate explanation in a Forcing Game is PLS-complete (Polynomial Local Search), indicating high complexity. In uncooperative Restriction Games, the complexity can become exponential.
  • The Power of Interaction: Crucially, in a Challenge Game, the explainee has a winning strategy that is linear time computable. By allowing the user to actively challenge the model's logic, the search for an adequate explanation becomes significantly more efficient.

Conclusion

By framing interpretability as a game-theoretic dialogue, we provide a rigorous foundation for "adequate and fair" explanations. This framework moves beyond static "nearby points" to a dynamic process that respects human cognitive limits while enforcing logical honesty. Future work will involve testing these "Challenge Games" with human subjects and extending the Boolean logic used in our proofs to continuous feature spaces, ultimately contributing to more robust and transparent interactive machine learning systems.

Summary updated

Abstract

Explaining sophisticated machine-learning based systems is an important issue at the foundations of AI. Recent efforts have shown various methods for providing explanations. These approaches can be broadly divided into two schools: those that provide a local and human interpreatable approximation of a machine learning algorithm, and logical approaches that exactly characterise one aspect of the decision. In this paper we focus upon the second school of exact explanations with a rigorous logical foundation. There is an epistemological problem with these exact methods. While they can furnish complete explanations, such explanations may be too complex for humans to understand or even to write down in human readable form. Interpretability requires epistemically accessible explanations, explanations humans can grasp. Yet what is a sufficiently complete epistemically accessible explanation still needs clarification. We do this here in terms of counterfactuals, following [Wachter et al., 2017]. With counterfactual explanations, many of the assumptions needed to provide a complete explanation are left implicit. To do so, counterfactual explanations exploit the properties of a particular data point or sample, and as such are also local as well as partial explanations. We explore how to move from local partial explanations to what we call complete local explanations and then to global ones. But to preserve accessibility we argue for the need for partiality. This partiality makes it possible to hide explicit biases present in the algorithm that may be injurious or unfair.We investigate how easy it is to uncover these biases in providing complete and fair explanations by exploiting the structure of the set of counterfactuals providing a complete local explanation.
BibTeX
@misc{asher2020adequate,
  author = {Nicholas Asher and Soumya Paul and Chris Russell},
  title = {{Adequate and fair explanations}},
  year = {2020},
  eprint = {2001.07578},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2001.07578},
}
Figure