Abstract
Explainable AI (XAI) often faces a trade-off between formal rigor and human interpretability. This paper introduces "example-based abductive explanations" for Random Forests, which combine logical proofs of a decision with real-world reference examples. By "anchoring" these proofs, the authors ensure explanations are both mathematically sound and persuasive to users. We explore the computational complexity of this approach and demonstrate a scalable algorithm for practical use.
Introduction
Machine Learning models, particularly Random Forests, are frequently criticized as "black boxes." While they offer high predictive performance, understanding the underlying reasoning for a specific classification remains a challenge. Current XAI methods generally fall into two categories: Formal XAI, which uses logic to provide "abductive explanations" (sufficient reasons) that guarantee a classification, and Example-based XAI, which uses past cases to explain decisions through analogy.
While formal explanations are 100% correct, they can be abstract. Conversely, example-based methods are intuitive but often lack formal guarantees. This research bridges the gap by proposing $k$-anchored abductive explanations, which are logical terms that guarantee a model's prediction while being supported by at least $k$ similar reference instances from the training data.
Methodology
A $k$-anchored abductive explanation is defined as a set of feature conditions that:
- Guarantees the model's prediction for the current instance.
- Covers at least $k$ "reference instances" (anchors) classified the same way.
- Covers zero reference instances classified differently.
Finding these explanations is computationally demanding, as the authors prove the problem resides at the second level of the polynomial hierarchy ($\Sigma_2^p$). To address this, they propose a Counter-Example Guided Refinement Abstraction (CEGAR) algorithm. The algorithm operates in a loop:
- Generation: A SAT solver identifies a candidate explanation covering $k$ anchors.
- Verification: An NP oracle verifies if the candidate is a true abductive explanation.
- Refinement: If a counter-example is found, the candidate is blocked, and the process repeats.
- Minimization: The final valid explanation is reduced to the smallest possible feature set using a greedy approach.
Experimental Setup
The approach was evaluated on 14 diverse datasets, ranging from social and tabular data to high-dimensional image data. Random Forests consisting of 100 trees were trained for each dataset to establish a baseline for explanation generation.
The researchers used varying percentages (5%, 10%, and 20%) of the training data as potential "anchors" to test the algorithm's performance and the availability of anchored explanations across different levels of required support.
Key Results and Insights
The experiments demonstrated that the CEGAR-based framework is computationally feasible for practical Random Forests across a wide variety of domains.
Efficiency and Scalability
For datasets with up to 1,000 Boolean conditions, the algorithm typically found the "most anchored" explanation in under a second. Even on high-dimensional datasets like mnist38 or gisette, the system successfully provided explanations or proved their absence for over 72% of instances within a 60-second timeout.
Anchor Density and Persuasiveness
A key finding was the variation in "anchor density." Some classifications are "common" and easily supported by many examples, enhancing their persuasiveness. Others are "outliers" that can only be explained through purely logical (0-anchored) reasons. This distinction helps identify which model decisions are well-supported by historical data and which are based on more isolated logic.
Conclusion
This work demonstrates that combining formal logic with example-based reasoning is not only theoretically sound but also practically achievable for Random Forests. While computational limits were reached on the most complex datasets (e.g., christine), the CEGAR framework provides a robust foundation for future XAI research. Future work will focus on improving search heuristics and extending the framework to other binary classifiers like Boosted Trees and Neural Networks.
Summary updated