Introduction
Explainable AI (XAI) aims to provide human-understandable reasons for model predictions. A rigorous way to do this is through Abductive Explanations (AXp), which identify a minimal set of feature values sufficient to trigger a specific prediction. However, traditional AXps are often too specific—for instance, citing a patient's exact height and weight rather than a range. This paper introduces the Maximum Inflated Abductive Explanation (Max-iAXp), a framework to find the single most general explanation that covers the largest possible portion of the input space while remaining a mathematically guaranteed "sufficient reason."
Methodology: Implicit Hitting Set Dualization
The authors propose an algorithmic framework based on Implicit Hitting Set Dualization. The search for the most general explanation is treated as an optimization problem solved by two interacting "oracles":
- The Master Oracle: Suggests candidate explanations using MaxSAT or Mixed-Integer Programming (MIP) to maximize a coverage score.
- The Checker Oracle: Verifies the candidate against a formal encoding of the Tree Ensemble to ensure no counterexamples exist.
The paper explores three encodings: Naive MaxSAT, Bounds-based MaxSAT (using lower/upper bound variables), and a MIP encoding. The MIP approach, utilizing solvers like Gurobi, proved most effective due to its advanced optimization techniques. Generality is measured by the log-size of feature space coverage, which can be weighted by uniform or data-driven distributions.
Key Results and Empirical Evaluation
The framework was evaluated on 12 numerical datasets from the UCI and Penn ML repositories. The results demonstrate that Max-iAXps provide massive coverage gains over standard inflated explanations without sacrificing succinctness.
As shown in the table above, the Coverage Ratio (Max-iAXp vs. baseline) can be extraordinary. For the bupa dataset, the Max-iAXp was over 98,000 times more general than the baseline. Despite the computational complexity, the MIP-based approach is efficient, with an average computation time of approximately 33 seconds across all datasets.
Conclusion
This research provides a robust foundation for generating "most general" explanations for tree ensembles. By defining the boundaries of a decision rather than just a single point, Max-iAXps offer more intuitive and applicable insights. Future work will focus on extending these metrics to categorical data and improving real-time performance for high-throughput systems.
Summary updated