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:
- Mistake: The user believes a certain feature is more influential than it actually is.
- 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