Most General Explanations of Tree Ensembles

Yacine Izza, Alexey Ignatiev, Sasha Rubin, João Marques-Silva, Peter J. Stuckey

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":

  1. The Master Oracle: Suggests candidate explanations using MaxSAT or Mixed-Integer Programming (MIP) to maximize a coverage score.
  2. The Checker Oracle: Verifies the candidate against a formal encoding of the Tree Ensemble to ensure no counterexamples exist.
The iterative algorithm for computing Max-iAXp using dual oracles.

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.

Experimental results comparing standard iAXp and Max-iAXp across 12 datasets.

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

Abstract

Explainable Artificial Intelligence (XAI) is critical for attaining trust in the operation of AI systems. A key question of an AI system is ``why was this decision made this way''. Formal approaches to XAI use a formal model of the AI system to identify abductive explanations. While abductive explanations may be applicable to a large number of inputs sharing the same concrete values, more general explanations may be preferred for numeric inputs. So-called inflated abductive explanations give intervals for each feature ensuring that any input whose values fall withing these intervals is still guaranteed to make the same prediction. Inflated explanations cover a larger portion of the input space, and hence are deemed more general explanations. But there can be many (inflated) abductive explanations for an instance. Which is the best? In this paper, we show how to find a most general abductive explanation for an AI decision. This explanation covers as much of the input space as possible, while still being a correct formal explanation of the model's behaviour. Given that we only want to give a human one explanation for a decision, the most general explanation gives us the explanation with the broadest applicability, and hence the one most likely to seem sensible.
BibTeX
@inproceedings{izza2025most,
  author = {Yacine Izza and Alexey Ignatiev and Sasha Rubin and João Marques-Silva and Peter J. Stuckey},
  title = {{Most General Explanations of Tree Ensembles}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.24963/ijcai.2025/608},
}
Figure