Search papers, labs, and topics across Lattice.
This paper introduces ExplAIner, a declarative query language designed to enhance the expressiveness and efficiency of explanations for classification models, addressing limitations in existing frameworks like FOIL. The authors demonstrate that ExplAIner can articulate a wide range of explanation types, including abductive and contrastive queries, while ensuring that the evaluation of these queries remains computationally feasible within the Boolean hierarchy. Additionally, the introduction of Opt-FOIL allows for the computation of minimal explanations with a polynomial number of calls to SAT solvers, significantly improving the practicality of formal XAI applications.
ExplAIner can express a diverse array of explanation types while ensuring efficient evaluation, transforming how we approach interpretability in machine learning models.
The XAI community has studied a wide range of queries and scores for explaining predictions of ML models. From a data management perspective, this proliferation of explanation notions calls for declarative query languages in which such notions can be specified, combined, and analyzed uniformly. In this paper, we develop such a framework for Boolean models. We first revisit FOIL, an interpretability query language for black-box models, and show that it has two fundamental limitations: it cannot express central optimality-based explanation queries, and its evaluation problem over decision trees is hard for every level of the polynomial hierarchy. We then introduce ExplAIner, a query language based on FOIL with an extended vocabulary and a layered structure. We show that ExplAIner can express a broad family of explanation notions, including abductive, contrastive, feature-based, and distance-based queries. We also prove that the evaluation problem for each query in ExplAIner belongs to the Boolean hierarchy over every class of Boolean models for which some basic predicates can be evaluated in polynomial time. In particular, that property holds for deterministic and decomposable Boolean circuits. Finally, we introduce Opt-FOIL, an optimization-oriented fragment of ExplAIner for computing explanations that are minimal with respect to strict partial orders, and prove that its evaluation problem is in $\mathrm{FP}^{\mathrm{NP}}$ under the same tractability assumptions. These complexity results have a direct algorithmic consequence: a fixed ExplAIner query can be evaluated with a fixed number of calls to a SAT solver, while a notion of explanation specified in Opt-FOIL can be computed with a polynomial number of such calls. This is particularly relevant in formal XAI, where SAT solvers have been successfully used to compute explanations for several classes of ML models.
CMU ML