Computing Coverage-Based Prime Implicant Explanations for Tree-Based Models

1 Introduction

During the last decade, the rise of ML-driven AI techniques has led to outstanding advancements across numerous fields. However, the most accurate ML models are black boxes: their decision-making processes are opaque [Molnar, 2019]. To deal with the demand for more transparency in AI systems, eXplainable AI (XAI) methods have been developed in recent years [Gunning, 2019]. In particular, many notions of explanations suited to various ML models and inputs (tabular data, images, texts, etc.) have been pointed out so far (see [Hsieh et al., 2024; Bodria et al., 2023; Arrieta et al., 2020; Guidotti et al., 2019; Molnar, 2019] for surveys).

In the following, we focus on coverage-based prime implicant explanations [Cooper and Amgoud, 2024; Cooper and Amgoud, 2023] in the specific case of tree-based models f used for binary classification. Coverage-based prime implicant explanations are abductive explanations that are local and post-hoc explanations. As such, they are about the prediction made by an already trained ML model f for a given input instance x. They aim to answer the "why?" question [Miller, 2019; Ignatiev et al., 2020] by identifying a subset t of the characteristics of x such that every instance sharing those characteristics is ensured to be classified by the ML model f in the same way as x.

While no consensus exists about what a "good" explanation should be [Miller, 2019; Molnar, 2019], many criteria can be considered for evaluating the quality of an explanation (see e.g., [Nauta et al., 2023]). Coverage-based prime implicant explanations [Cooper and Amgoud, 2024; Cooper and Amgoud, 2023] are faithful explanations that take advantage of a domain theory Σf not only for ensuring that explanations comply with it, but also for the sake of generality: only explanations that are as general as possible given Σf , i.e., that are implied by other explanations when Σf is assumed, are selected. [Cooper and Amgoud, 2024; Cooper and Amgoud, 2023] have shown that ignoring some consequences of Σf (especially, dependency constraints among features) may lead to the generation of superfluous abductive explanations and to exponentially many redundant abductive explanations. Coverage-based prime implicant explanations do not suffer from these impediments.

However, there is a price to be paid, and this price is computational: though deciding whether a given term is an abductive explanation is coNP-complete [Cooper and MarquesSilva, 2023] in general, deciding whether it is a coveragebased prime implicant explanation is Πp2 -complete in general [Cooper and Amgoud, 2024; Cooper and Amgoud, 2023]. While an algorithm for computing a coverage-based prime implicant explanation for a given instance has been presented in the appendix of [Cooper and Amgoud, 2024], as far as we know, this algorithm has not been implemented so far. As a consequence, given the high complexity of the problem, the question of the practical efficiency of the computation of such explanations remains open.

In this paper, we present a greedy algorithm for computing coverage-based prime implicant explanations when dealing with a tree-based model f (a decision tree [Breiman et al., 1984], a random forest [Breiman, 2001] or a boosted tree [Freund and Schapire, 1997]). We show that the specific nature of the domain theory linking the Boolean conditions in such models makes the problem computationally easier (only polynomially many calls to an NP oracle are needed). We also present an empirical evaluation of this algorithm and a comparison with our implementation of the algorithm given in [Cooper and Amgoud, 2024]. This evaluation shows that the computation of coverage-based prime implicant explanations for tree-based models is practical enough to deal with "mildly complex" tree-based models (i.e., based on hundreds of Boolean conditions). As expected, experiments also show that our algorithm is much more efficient than the generalpurpose algorithm for coverage-based prime implicant explanations presented in [Cooper and Amgoud, 2024] when applied to such tree-based models.

The rest of the paper is organized as follows. Formal preliminaries are given in Section 2. Our algorithm for computing coverage-based prime implicant explanations for treebased models is presented in Section 3. Experiments are reported in Section 4. The proofs of the results presented in the paper, as well as additional empirical results and the code used in our experiments are furnished as a supplementary material available from [Audemard et al., 2026].

2 Formal Preliminaries

Classification and tree-based models. Let A = {A1, . . . , An} be a finite set of attributes, where each attribute is Boolean, categorical, or numerical. An instance x over A is a vector from D1 × . . . × Dn. Its set of characteristics indicates for each Ai ∈ A the value x takes in Di. X is the set of all instances. A classifier f over A is a mapping from X to a finite set L of classes. A binary classifier f over A is a mapping from X to L = {0, 1}. An instance x ∈ X is positive when f(x) = 1 and it is negative when f(x) = 0.

A decision tree (resp. regression tree) over A [Breiman et al., 1984; Quinlan, 1986] is a binary tree T , each of whose internal nodes (aka decision nodes) is labelled with a Boolean condition over Ai ∈ A, and each leaf is labelled by an element of L (resp. a decimal floating-point number).

Decision trees (DTs), sets of decision trees (alias random forests (RFs)), and sets of regression trees (alias boosted trees (BTs)) can be used for solving binary classification problems.

The value T(x) of T on an input instance x ∈ X is given by the label of the leaf reached from the root. When T is a decision tree, this value is 1 when the leaf reached is a 1-leaf (i.e., a leaf labelled by 1) and it is 0 when the leaf reached is a 0-leaf (i.e., a leaf labelled by 0). The unique path characterising the leaf that is met is defined as follows: at each decision node go to the left (resp. right) child if the Boolean condition labelling the node is evaluated to 0 (resp. 1) for x.

A random forest over A [Breiman, 2001] is an ensemble RF = {T1, · · · , Tm}, where each Ti (i ∈ [m]) is a decision tree over A, and such that the value RF(x) is given by

A boosted tree over A [Freund and Schapire, 1997; Friedman, 2001; Schapire and Freund, 2014] is an ensemble BT = {T1, · · · , Tm}, where each Ti (i ∈ [m]) is a regression tree over A, and such that the value BT(x) is given by

Let B = {B1, . . . ,Bm} be the set of Boolean conditions occurring in a tree-based model f (a decision tree, a random forest or a boosted tree over A). Those conditions can also be viewed as Boolean attributes. Therefore f can also be considered as a Boolean function over B. The Boolean attributes in B are not always pairwise independent because several conditions can be generated from a single numerical or categorical attribute from A. A domain theory Σf is a propositional formula over B indicating how the corresponding attributes occurring in f are logically connected. Accordingly, beyond X, another set of instances can be considered given f: the subset XB of {0, 1}m containing Boolean vectors that correspond to the truth assignments over B satisfying Σ. Every instance x ∈ X corresponds to a unique instance xB ∈ XB and this instance xB is such that f(xB) = f(x). Unlike X that is (in general) infinite, XB is a finite set.

Considering instances over Boolean attributes B = {B1, . . . , Bm} that are connected by a domain theory Σf , treebased models f can thus be viewed as Boolean functions mapping the truth assignments x fromXB, i.e., the truth assignments over B that satisfy Σ (aka the models of Σ), to a Boolean value that is 1 when x is a positive instance and 0 when it is a negative instance. Furthermore, every instance x = (x1, . . . , xm) from XB can be viewed and be represented as a canonical term tx (i.e., a conjunctively-interpreted set of literals over B in which every variable occurs once) such that tx = ∧mi=1 x∗i where x∗i = xi (i ∈ [m]) when the ith coordinate of x is 1 and x∗i = xi when the ith coordinate of x is 0.

Example 1. As a matter of illustration, Figure 1 presents a very simple random forest RF = {T1, T2, T3} over A = {A1, A2}, where A1 is a numerical attribute (say, the annual income in $k of a loan applicant) and A2 is a Boolean attribute (indicating whether the applicant holds a permanent position). The instance x = (33, 1) from X is such that T (x) = 1.

contains three Boolean conditions. The two conditions B1 = (A1 > 20) and B2 = (A1 > 30) about A1 are obviously not independent: they are logically connected by a domain theory Σf equivalent to B2 ⇒ B1. x = (23, 1) (and more generally, every instance from X for which B1, B2, and B3 hold) corresponds to the instance xB = (1, 1, 1) from XB. It is easy to check that f is equivalent to the CNF formula B1 ∨ B2 ∨ B3.

Abductive explanations. Abductive explanations are local explanations that aim to explain why the instance at hand has been classified as such by the ML model f. Formally, an abductive explanation for x ∈ XB given f is a subset t of tx such that every instance x′ ∈ XB such that t ⊆ tx′ satisfies f(x′ ) = f(x). Such explanations t offer correctness guarantees in the sense that any instance x′ covered by t is ensured to be classified by f in the same way as x.

Let Σf , α, β be three formulae over B. We note α |=Σf β precisely when Σf ∧ α |= β and α ≡Σf β precisely when α |=Σf β and β |=Σf α. When α |=Σf β holds, we say that β is at least as general as α modulo Σf . When α ≡Σf β holds, α and β are equivalent modulo Σf .

To clarify the landscape of abductive explanations, Table 1 summarizes the hierarchy of the core concepts used in this paper. Starting from base explanations (wAXp), domain constraints are added (wAXpc), minimality is enforced (AXp/AXpc), and finally, coverage is maximized modulo the domain theory Σf (CPI-Xp/mCPI-Xp).

Definition 1. Let f be a Boolean function over a set B of Boolean conditions, x an instance from XB. Let f ∗ = f if f(x) = 1 and f ∗ = ¬f if f(x) = 0. Let t be a term over B:

• t is an abductive explanation (wAXp) for x given f iff t ⊆ tx and t |= f ∗ ;
• t is a subset-minimal abductive explanation (AXp) for x given f iff t is an abductive explanation for x given f and no proper subset of t is an abductive explanation for x given f ;
• Let Σf be a formula over B (a domain theory, representing constraints over the Boolean conditions occurring in f) such that tx |= Σf holds:
• t is an abductive explanation (wAXpc) for x given f and Σf iff t ⊆ tx and t |=Σf f ∗ ;
• t is a subset-minimal abductive explanation (AXpc) for x given f and Σf iff t is an abductive explanation for x given f and Σf and no proper subset of t is an abductive explanation for x given f and Σf ;
• t is a coverage-based prime implicant explanation (CPI-Xp) for x given f and Σf iff t ⊆ tx, t |=Σf f ∗ and if there exists t′ ⊆ tx such that t′ |=Σf f ∗ and t |=Σf t′ , then t ≡Σf t′ ;
• t is a minimal coverage-based prime implicant explanation (mCPI-Xp) for x given f and Σf iff t is a coverage-based prime implicant explanation for x given f and Σf and no proper subset of t is a coverage-based prime implicant explanation for x given f and Σf .

Example 2 (Example 1 cont'ed). Let us recall that B = {B1, B2, B3}, f ≡ B1 ∨ B2 ∨ B3 and that Σf = B2 ⇒ B1.

• Consider first the instance x = (1, 1, 1). We have f (x) = 1. tx = {B1, B2, B3} is a wAXp (and a wAXpc) for x given f, but not an AXp. {B1}, {B2}, and {B3} are the AXps for x given f. They are also the AXpcs for x given f and Σf . Among them {B1} and {B3} are the CPI-Xps and the mCPI-Xps for x given f and Σf .
• Consider now the instance x′ = (0, 0, 0). We have f(x′ ) = 0. tx′ = {B1,B2,B3} is the unique AXp for x′ given f, but it is not an AXpc for x′ given f and Σf . {B1,B3} is the unique AXpc for x′ given f and Σf . It is also the unique CPI-Xp and mCPI-Xp for x′ given f and Σf .

mCPI-Xps of minimal size can be arbitrarily larger than AXps (or AXpcs) of minimal size. Unlike what happens with AXps, the generality criterion may conflict with the interpretability one. Indeed, minimal-size wAXps are AXps, thus are as general as possible while being more interpretable than other wAXps. Contrastingly, CPI-Xps (and even mCPI-Xps) are (by definition) more general than other wAXps but they can be less interpretable (they may contain many more characteristics).

3 Computing CPI-Xps

In order to derive CPI-Xps suited to tree-based models, we present a greedy algorithm CPI-Xp-TBM (see Algorithm 1). This algorithm leverages the specific nature of the domain theory Σf linking the Boolean conditions in tree-based models to make the search for CPI-Xps more efficient.

CPI-Xp-TBM takes as input an instance x ∈ XB. The goal is to explain the classification of x achieved by the binary classifier f over B. Here f is a tree-based model (a decision tree, a random forest, or a boosted tree). Another part of the input is the domain theory Σf associated with f:

is the conjunction of the domain theories ΣfAi associated with the primitive attributes from A. Each ΣfAi (Ai ∈ A) is defined as follows. When Ai is a numerical attribute such that the set of conditions about Ai occurring in f is {Ai > v1 i , . . . ,Ai > vc(i) i } where vc(i) i > . . . > v1 i (i.e., there are c(i) thresholds considered for Ai), ΣfAi is given by the following CNF formula based on the Boolean variables B1 i , . . . ,Bc(i) i from B, where each Bj i (j ∈ [c(i)]) stands for Ai > vj i :

When Ai is a categorical attribute such that the set of conditions about Ai occurring in f is {Ai = v1 i , . . . ,Ai = vc(i) i }, ΣfAi is given by the following CNF formula based on the Boolean variables B1 i , . . . ,Bc(i) i from B, where each Bj i (j ∈ [c(i)]) stands for Ai = vj i :

Thus, when Ai is a numerical attribute, ΣfAi is a chain of implications that simply reflects the linear ordering over the threshold values vj i for Ai that have been found by the learning algorithm used to generate f. When Ai is a categorical attribute, ΣfAi is a mutual exclusion constraint that states that the values found for Ai by the learning algorithm used to generate f are mutually exclusive. Accordingly, the (running) domain of each categorical attribute Ai is considered as open: it is not assumed that the sole possible values for Ai are in {v1 i , . . . , vc(i) i } (v1 i , . . . , vc(i) i are those values found when f was learned but this does not preclude the existence of other possible values for Ai, especially because such values do not necessarily occur in the training set used to learn f). Finally, the Boolean attributes Ai from A do not give rise to any specific domain theory: ΣfAi is the empty CNF formula, represented by the Boolean constant always true ⊤.

It can be easily checked that the domain theory Σf associated with a tree-based model f is decomposable: whenever Ai and Aj are two distinct attributes from A, then {B1 i , . . . ,Bc(i) i } ∩ {B1 j , . . . , Bc(j) j } = ∅.

In order to compute a CPI-Xp for x ∈ XB given f and Σf , a space of explanation candidates is explored:

Definition 2. An explanation candidate t for x ∈ XB is a subset of literals from tx.

Given that x satisfies Σf , every explanation candidate t for x is consistent with Σf .

Explanation candidates (when viewed up to equivalence modulo Σf ) are ordered by the generality relation |=Σ that is a (partial) ordering, i.e., a reflexive, transitive, and antisymmetric relation. If t and t′ are two explanation candidates for x ordered by the strict part of this ordering, i.e., such that t |=Σf t′ and t′ ̸|=Σf t hold, we say that t′ is a (strict) generalisation of t given Σf .

When looking for a CPI-Xp for x given f and Σf , the exploration of the space of explanation candidates can be guided by |=Σf . To define the exploration strategy, the following notion of Ai-part of an explanation candidate will be useful:

Definition 3. The Ai-part of an explanation candidate t for x ∈ XB is the subset tAi of literals ℓ from t that are about Ai ∈ A, i.e., the variable of ℓ corresponds to a condition Ai > vj i or Ai = vj i (j ∈ [c(i)]).

Algorithm 1 CPI-Xp-TBM

Require: x an instance fromXB satisfying Σ, f a tree-based classifier over B, Σf a formula over B (the corresponding domain theory).

Ensure: a CPI-Xp cx for x given f and Σf .

1: f ∗ ← (f(x) = 1) ? f : f 2: t ← tx 3: cx ← ∅ 4: for each Ai ∈ A do 5: t′ ← tAi 6: while true do 7: if t′ = ∅ then 8: exit-while 9: else 10: found ← false 11: gs ← msg(t′ , Σf ) 12: for each g ∈ gs do 13: gs ← gs \ {g} 14: if imp(cx ∪ g ∪ ⋃j>i tAj , f ∗ , Σf ) then 15: t′ ← g 16: found ← true 17: exit-for 18: if notfound then 19: cx ← cx ∪ t′ 20: exit-while 21: return cx

Because the domain theories ΣfAi (Ai ∈ A) are based on Boolean variables that are pairwise disjoint, it is easy to show that the generality relation |=Σf over explanation candidates can be decomposed over the primitive attributes:

Proposition 1. Let t, t′ be two explanation candidates for x ∈XB. We have t |=Σf t′ if and only if ∀Ai ∈ A, tAi |=Σf t′Ai if and only if ∀Ai ∈ A, tAi |=ΣfAi t′Ai .

CPI-Xp-TBM is an iterative algorithm: each primitive attribute Ai from A is considered in sequence, and the Ai-part of the explanation candidate tx is generalised as much as possible in a greedy fashion, i.e., while the resulting explanation is a wAXpc for x given f and Σf .

CPI-Xp-TBM takes advantage of two main functions: msg and imp. imp is used to achieve implicant tests and the goal of msg is to guide the search for a CPI-Xp for x given f and Σf by deriving at each step the most specific generalisations of the current explanation candidate:

Definition 4. Given Σf , a most specific generalisation of an explanation candidate t for x is an explanation candidate t′ for x such that t |=Σf t′ , t′ ̸|=Σf t and for every explanation candidate t′′ for x such that t |=Σf t′′ and t′′ ̸|=Σf t, if t′′ |=Σf t′ , then t′ |=Σf t′′ .

In the set msg(t,Σf ) of the most specific generalisations of t given Σf , only one representative per equivalence class modulo Σf must be kept. This set is empty precisely when t = ∅ because of the specific nature of Σf when f is a tree ensemble.

Due to the decomposability of Σf , a most specific generalisation msg(t, Σf ) of an explanation candidate can be characterised by computing a most specific generalisation of one of its parts:

Proposition 2. Let Ai ∈ A be such that ∃t′Ai ∈ msg(tAi , Σf ). Then ⋃Aj∈A|j̸=i tAj ∪ t′Ai is a most specific generalisation of the explanation candidate t for x given Σf .

The decomposability of Σf and the specific nature of each ΣfAi (Ai ∈ A) ensures that msg(tAi ,Σf ) can be computed in time polynomial in the size of tAi plus the size of ΣfAi :

Proposition 3. Let t be an explanation candidate for x ∈ XB and let Ai ∈ A.

• When Ai is numerical, ΣfAi = ∧c(i) j=2 (¬Bj i ∨Bj-1 i ) has the form of a chain of implications. Let M = max ({j ∈ [c(i)] | Bj i ∈ t}) if tAi contains a positive literal and let m = min({j ∈ [c(i)] | Bj i ∈ t}) if tAi contains a negative literal. Let G+ = {BM-1 i } if M ̸= 1 and G+ = ∅ if M = 1, and let G- = {Bm+1 i } if m ̸= c(i) and G- = ∅ if m = c(i).
• If tAi contains a positive literal and a negative literal, then msg(tAi ,Σf ) = {(tAi \ {BM i }) ∪ G+, (tAi \ {Bm i }) ∪G-}.
• If tAi contains a positive literal and no negative literals, then msg(tAi ,Σf ) = {(tAi \ {BM i }) ∪ G+}.
• If tAi contains no positive literals and a negative literal, then msg(tAi ,Σf ) = {(tAi \ {Bm i }) ∪ G-}.
• When Ai is categorical, ΣfAi = ∧j,k∈[c(i)]|j̸=k (¬Bj i ∨ ¬Bk i ) has the form of a mutual exclusion constraint.
• If tAi contains a positive literal Bj i , then msg(tAi , Σf ) = {{Bk i | k ∈ [c(i)] \ {j}}}.
• If tAi does not contain any positive literal then msg(tAi , Σf ) = {tAi \ {Bj i } | Bj i ∈ tAi }.

A second important component of CPI-Xp-TBM is the implicant test imp. Indeed, when such a test fails, i.e., when an explanation candidate t is not an abductive explanation for x given f and Σf , it is useless to consider any explanation candidate that generalises t.

Deciding whether an explanation candidate t is an abductive explanation (i.e., determining whether t is an implicant of f ∗ modulo Σf ) amounts to testing the inconsistency of Σf ∧ t ∧ f ∗ . This can be done using various kinds of solvers (for instance, an SMT solver [Ignatiev et al., 2019], a MIP solver [Cui et al., 2015; Parmentier and Vidal, 2021], a SAT solver [Audemard et al., 2022] or a MaxSAT solver [Ignatiev et al., 2022] can be used).

Exploring in a greedy fashion the set of most specific generalisations of the current explanation candidate t (starting with t = tx) until the implicant test fails ensures that no relevant part of the search space is left unexplored for generating a CPI-Xp for x given f and Σf . Algorithm 1 is explained in the following example.

Example 3 (Example 1 cont'ed). Suppose that x = (1, 1, 1). Since f(x) = 1, we have f ∗ = f. At start (line 2), t is equal to {B1 = (A1 > 20),B2 = (A1 > 30),B3 = (A2 = 1)}. Suppose that A2 is processed before A1 in the main for-loop (line 4). One first looks for the most specific generalisations of t′ = tA2 = {B3 = (A2 = 1)} given Σf . Since msg(t′ ,Σf ) = {∅}, there is a single generalisation of t′ to be considered at line 12 (the inner for-loop), namely ∅. Since {B1 = (A1 > 20),B2 = (A1 > 30)} is an implicant of f ∗ modulo Σf , t′ is set to ∅ at line 15. Then one looks for the most specific generalisations of t′ = ∅. Since t′ = ∅, the test at line 7 leads to leave the while-loop. At that stage, cx is still equal to ∅.

Then A1 is processed in the main for-loop. One first looks for the most specific generalisations of t′ = tA1 = {B1 = (A1 > 20),B2 = (A1 > 30)} given Σf . Since msg(t′ ,Σf ) = {{B1 = (A1 > 20)}}, there is a single generalisation of t′ to be considered at line 12 (the inner for-loop), namely {B1 = (A1 > 20)}. Since {B1 = (A1 > 20)} is an implicant of f ∗ modulo Σf , t′ is set to {B1 = (A1 > 20)} at line 15. Then one looks for the most specific generalisations of t′ = {B1 = (A1 > 20)}. Since msg(t′ , Σf ) = {∅}, there is a single generalisation of t′ to be considered at line 12 (the inner for-loop), namely ∅. Since ∅ is not an implicant of f ∗ modulo Σf , found remains false, so that cx is updated to {B1 = (A1 > 20)} (line 19). Finally, since t′ = ∅, the test at line 7 leads to leave the while-loop. At that stage, cx is equal to {B1 = (A1 > 20)}. Since every attribute Ai ∈ A has been processed in the main for loop, cx = {B1 = (A1 > 20)} is returned at line 21.

Proposition 4. CPI-Xp-TBM is correct w.r.t. its specification: it always terminates and returns a CPI-Xp for x given f and Σf .

For each attribute Ai ∈ A, the number of calls to the implicant test imp at line 14 is upper bounded by c(i), thus linear in the number of Boolean conditions in B that are about Ai. Therefore, the total number of calls to the implicant test is linear in the number of Boolean conditions in B. Given that the implicant test can be achieved in time polynomial in |f| + |Σf | when f is a decision tree [Audemard et al., 2024], CPI-Xp-TBM is a polynomial-time algorithm when f is a decision tree. In the case of random forests or boosted trees, the implicant test is coNP-complete, making unlikely the existence of a (deterministic) polynomial-time algorithm for it. Thus, CPI-Xp-TBM does not run in polynomial time when such models are considered as input. However, if one is ready to lose a bit of generality in the explanations in order to ensure a polynomial-time behaviour of CPI-Xp-TBM (thus, to improve its scalability), a way consists in replacing the test imp(cx ∪ g ∪ ⋃j>i tAj , f ∗ , Σf ) by a lower approximation of it that can be evaluated efficiently. Such polynomialtime approximations exist for random forests (resp. boosted trees) leading to the characterisation of abductive explanations called majoritary (resp. tree-specific) explanations (see [Audemard et al., 2022; Audemard et al., 2023] for details). The resulting explanations would not be CPI-Xps in general but the fact that they are abductive (wAXpc) would be guaranteed.

Our algorithm CPI-Xp-TBM (Algorithm 1) differs from the general-purpose procedure introduced in [Cooper and Amgoud, 2024] in several key aspects. While the latter is designed for any classifier and relies on a counter-example search strategy to iteratively replace weak explanations with strictly more general ones, our approach specifically exploits the structural properties of tree-based models and their associated domain theories. This specialization reduces the computational complexity from Πp2 -completeness in the general case to a problem solvable with only polynomially many calls to an NP oracle when dealing with tree ensembles.

Finally, as this is the case for the CPI-Xps derived using the algorithm presented in [Cooper and Amgoud, 2024], it is easy to show that the CPI-Xps that are generated by Algorithm 1 are not necessarily minimal ones. However, we know that for every CPI-Xp t for x given f and Σf , there exists a mCPI-Xp tmin ⊆ t for x given f and Σf such that tmin ≡Σf t. The point is that tmin can be easily extracted from t using a greedy "deletion-based" algorithm (see [Cooper and Amgoud, 2024] for details).

4 Experiments

Empirical protocol. In our experiments, we considered 21 datasets for binary classification, coming from standard repositories: UCI (https://archive.ics.uci.edu/ml/index.php), openML (https://www.openml.org/), and UCR (https://www. timeseriesclassification.com/). Instances of these datasets are based on primitive attributes of various types (numerical, categorical, Boolean) forming a set A.

Categorical attributes have been one-hot encoded and numerical attributes have been binarized on-the-fly by the learning algorithm used to generate the classifier f, given by a tree-based model f .

Decision trees and random forests f have been learned using the version 1.6.1 of the Scikit-Learn library [Pedregosa et al., 2011]. All hyperparameters are set to their default values. As for decision trees, the Gini impurity is used as the splitting criterion, and no maximum depth is enforced (nodes are expanded until all leaves are pure or contain fewer than 2 samples). Regarding random forests, 100 trees per forest are generated, and the same default node expansion strategy is applied (nodes are expanded until all leaves are pure or until all leaves contain less than min samples split samples, set to 2). Finally, regarding boosted trees, we used the XGBoost implementation (version 1.7.3) [Chen and Guestrin, 2016] with its default configuration: the model consists of 100 boosting rounds, a learning rate of 0.3, and a maximum tree depth of 6. For every dataset, a 10-fold cross validation process has been performed: for each model under consideration, 10 classifiers have been learned from a training set representing a specific subset (picked up uniformly at random) of 9 10 of the total number of instances in the dataset. For each classifier, 10 instances satisfying the corresponding domain theory Σf have been generated, leading to 100 instances per dataset.

The implicant test imp(cx ∪ g ∪ ⋃j>i tAj , f ∗ , Σf ) is one of the core components of Algorithm 1. In our implementation of imp, we use a SAT encoding when f is a decision tree or a random forest (extra variables that are existentially quantified are used in the latter case) to exploit highly optimized Boolean logic; a MIP encoding (close to those presented in [Cui et al., 2015; Parmentier and Vidal, 2021]) is used when f is a boosted tree to natively and efficiently handle its continuous linear sum constraints (∑i Ti(x) > 0). Based on those encodings, the implicant tests achieved in the experiments are performed, respectively, using the Glucose 3.0 SAT solver [Audemard et al., 2013] and the SCIP solver [Achterberg, 2009] (via the OR-Tools wrapper).

For each classifier f and instance x, the time spent by CPI-Xp-TBM to generate one CPI-Xp for x given f and Σf has been measured. Similar measurements have also been achieved using this time our implementation of the generic algorithm Cooper-Amgoud for deriving CPI-Xps, as presented in [Cooper and Amgoud, 2024]. To make a fair comparison between the two algorithms, the implicant test required by Cooper-Amgoud has been implemented using the same function imp as used in CPI-Xp-TBM. A timeout of 60 seconds has been considered for each computation.

Empirical results. Table 2 summarizes the characteristics of the datasets used in our experiments. Column |D| reports the total number of instances, while |A| represents the count of primitive features. |BDT |, |BRF | and |BBT | denote respectively the average number of binary features occurring in the decision trees, random forests and boosted trees that have been generated. In our approach, combinatorial hardness is driven by the number of primitive features and resulting Boolean conditions rather than the number of instances.

Performance comparisons are then detailed in the subsequent tables. Table 3 focuses on DTs, comparing our approach (CPI-Xp-TBM) against the generic algorithm proposed by Cooper and Amgoud. It reports for each dataset the average computation time (Time, in seconds) and the corresponding standard deviation (Std). Only the instances (out of the 100 instances generated for the dataset) for which the approach terminated in due time have been considered in the computation of Time and Std. Table 3 also reports the percentage of instances reaching the 60-second timeout (TO%). Finally, Tables 4 and 5 present similar measurements for RFs and for BTs, respectively.

The results show that for each dataset used in the experiments and each of the three tree-based models under consideration, Cooper-Amgoud never succeeded in solving more instances than CPI-Xp-TBM within 60 seconds. When the computations succeeded, Cooper-Amgoud turned out to be slightly more efficient on average than CPI-Xp-TBM only for a couple of datasets when f is a DT, while CPI-Xp- TBMwas more efficient than Cooper-Amgoud in all the remaining cases when f is an RF or a BT. This comparison highlights the robustness of our approach, particularly in the cases of RFs and BTs where the increased number of implicant tests and the computational cost of those tests cause the generic method to timeout for the majority of datasets and instances tested. Thus, in our experiments, the computation of a CPI-Xp using Cooper-Amgoud succeeded in due time (60 seconds) for 61.29% of the instances tested in the DT case, 19.81% in the RF case, and 29.43% in the BT case. In contrast, CPI-Xp-TBM maintains quite a high efficiency across "mildly more complex" tree-based models (i.e., based on hundreds of Boolean conditions). Consequently, the computation of a CPI-Xp using CPI-Xp-TBM succeeded in due time for 100% of the instances tested in the DT case, 80.95% in the RF case, and 75.52% in the BT case. Timeouts in CPIXp-TBM are entirely due to the calls to the imp oracle: while our approach reduces the number of oracle calls, each implicant test remains inherently intractable for RFs and BTs.

5 Conclusion

We presented a greedy algorithm that exploits the specific domain theory of tree-based models to efficiently derive CPIXps. Unlike what happens when the domain theory under consideration is not constrained, our algorithm requires only polynomially many calls to the implicant test. An empirical evaluation across tree ensembles confirms that our approach scales better than the existing general-purpose algorithm for deriving CPI-Xps.

Several perspectives for further research can be envisioned. One of them is to look for alternative conditions on the domain theory that would be sufficient to preserve the correctness of the algorithm. Another perspective is to exploit local CPI-Xps as building blocks for deriving more global explanations via set-cover algorithms.

Acknowledgements

Many thanks to the anonymous reviewers for their numerous comments and insights. This work has benefited from the support of the AI Chair EXPEKCTATION (ANR-19-CHIA0005-01) and of the France 2030 MAIA Project (ANR22-EXES-0009) of the French National Research Agency (ANR).