Despite the progress observed with model-agnostic explainable AI (XAI), it is the case that model-agnostic XAI can produce incorrect explanations. One alternative are the so-called formal approaches to XAI, that include abductive explanations. Unfortunately, abductive explanations also exhibit important drawbacks, the most visible of which is arguably their size. The computation of relevant features serves to trade of probabilistic precision for the number of features in an explanation. However, even for very simple classifiers, the complexity of computing sets of relevant features is prohibitive. This paper investigates the computation of relevant sets for Naive Bayes Classifiers (NBCs), and shows that, in practice, these are easy to compute. Furthermore, the experiments confirm that succinct sets of relevant features can be obtained with NBCs.
explanation can be consistent with diferent predicted classes. For example, for a bank loan application, The advances in Machine Learning (ML) in recent years might be consistent with an approved loan application, motivate an ever increasing range of practical applica- but also with a declined loan application. An explanation tions of Artificial Intelligence (AI) systems. In some do- that is consistent with both a declined and an approved mains, the use of AI systems is premised on the avail- loan applications ofers no insight to why one of the loan ability of mechanisms for explaining the often opaque applications was declined. There have been recent eforts operation of ML models. Some uses of ML models are on rigorous XAI approaches [18, 19, 20, 21, 22, 23, 24, 25, deemed high-risk given the impact that their operation 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40], most can have on people [2]. (Other authors refer to high- of which are based on feature attribution, namely the stakes applications [3].) For high-risk AI systems, a crit- computation of so-called abductive explanations (AXp’s). ical requirement is rigor, either when reasoning about However, these eforts have mostly focused on the scalthese systems, or when explaining their predictions. ability of computing rigorous explanations, with more
Recent years have witnessed a growing interest in recent work investigating input distributions [34]. NeveXplainable AI (XAI) [4, 5, 6, 7, 8, 9]. The best-known ertheless, another important limitation of rigorous XAI XAI approaches can be broadly categorized as model- approaches is the often unwieldy size of explanations. Reagnostic methods, that include for example LIME [10], cent work studied probabilistic explanations, as a mechaSHAP [11] and Anchor [12], and intrinsic interpretabil- nism to reduce the size of rigorous explanations [41, 42]. ity [3, 8], for which the explanation is represented by the Probabilistic explanations have extended model-agnostic actual (interpretable) ML model. Intrinsic interpretabil- approaches [41], and so can sufer from unsoundness. ity may not represent a viable option in some uses of Alternatively, more rigorous approaches to computing AI systems. On the other hand, model-agnostic meth- probabilistic explanations have been shown to be compuods, although locally accurate, can produce explanations tationally hard, concretely hard for NP , and so most that are unsound [13], in addition to displaying several likely beyond the reach of modern automated reasoners. other drawbacks [14, 15, 16, 17]. Unsound explanations This paper builds on recent work [42] on rigorous are hopeless whenever rigor is a key requirement; thus, probabilistic explanations, and investigates their pracmodel-agnostic explanations ought not be used in high- tical scalability. However, instead of considering classirisk settings. Indeed, it has been reported [13] that an ifers represented as boolean circuits (as in [ 42]), the paper specifically considers the family of naive Bayes classifiers ENIGMA-23, September 03–04, 2023, Rhodes, Greece (NBCs). Earlier work showed that rigorous explanations ⋆ A longer version of this paper has been published at Int. J. Approx. of NBCs, concretely AXp’s, are computed in polynomial Reason. Vol 159 (2023) [1]. time, and that their enumeration is achieved with polyno("J. Mizzaarq@uceosm-Spil.vnau)s.edu.sg (Y. Izza); joao.marques-silva@irit.fr mial delay [43]. Unfortunately, the size of explanations 0000-0002-7774-1945 (Y. Izza); 0000-0002-6632-3086 was not investigated in this earlier work. This paper (J. Marques-Silva) studies probabilistic explanations for the concrete case of © 2023 Copyright for this paper by its authors. Use permitted under Creative Commons License NBCs. For the case of categorical features, the paper reCPWrEooUrckReshdoinpgs IhStpN:/c1e6u1r3-w-0s.o7r3g ACttEribUutRion W4.0oInrtekrnsahtioonpal (PCCroBYce4.0e).dings (CEUR-WS.org) 2. Preliminaries 2.1. Classification problems
lates probabilistic explanations of NBCs with the problem use the term instance to refer to v, leaving implicit.)
of counting the models of (restricted forms) of integer
programming constraints, and proposes a dynamic pro- 2.2. Formal explanations
gramming based, pseudo-polynomial algorithm for
computing approximate (or locally-minimal) explanations. We now define formal explanations. In contrast with the
Such approximate explanations ofer important theoreti- well-known model-agnostic approaches to XAI [10, 11,
cal guarantees: i) approximate explanations are not larger 12, 5], formal explanations are model-precise, i.e. their
than some rigorous explanation; ii) approximate explana- definition reflects the model’s computed function. Prime
tions are not smaller than some rigorous probabilistic ex- implicant (PI) explanations [18] denote a minimal set of
planation; and iii) approximate explanations ofer strong literals (relating a feature value and a constant ∈
probabilistic guarantees on their precision. More impor- D) that are suficient for the prediction. PI-explanations
tantly, the experimental results demonstrate that succinct are related with abduction, and so are also referred to
explanations, with sizes that can be deemed within the as abductive explanations (AXp) [19]. Formally, given
grasp of human decision makers [44], can be very efi- v = (1, . . . , ) ∈ F with (v) = , an AXp is any
ciently computed with most often a small decrease in the minimal subset ⊆ ℱ such that,
preTchiseiopnapoefrtihseoregxapnlaizneadtiaosnf.ollows. Section 2 introduces ∀(x ∈ F). [︁⋀︁ ( = )]︁ →( (x) = ) (
Section 3 summarizes the computation of explanations for NBCs proposed in earlier work [43]. Section 4 details the approach proposed in this paper for computing locally-minimal probabilistic AXp’s. Section 5 presents experimental results confirming that precise short locallyminimal AXp’s can be eficiently computed. Section 6 concludes the paper.
∈
i.e. the features in are suficient for the prediction
when these take the values dictated by v, and is
irreducible. Also, a non-minimal set such that (
Each feature ∈ ℱ takes values from a domain D. In general, domains can be categorical or ordinal, with values that can be boolean, integer or real-valued but in this paper we restrict = {0, 1}, i.e. binary classiifers, and all features are categorical. (Throughout the rpeasppe.r,clwases a0lsaonduscelatshse1n.)otFaetiaotnusre⊖ spaancde i⊕s dtoefindeednaoste, Prx((x)) = |{x∈|F{:x∈(Fx})|=1}| bFe=roDf1p o×inDts2i×n F. .i.f × noDneo;f|Fth|erefperaetsuernetss itsheretaolt-avlanluuemd-. Prx((x) | (x)) = |{x∈|F{:x∈(xF):=(1x∧)=(1x})|=1}| (2) For boolean domains, D = {0, 1} = B, = 1, . . . , , (Similar to earlier work, it is assumed that the features are and F = B. The notation x = (1, . . . , ) denotes independent and uniformly distributed [42]. Moreover, an arbitrary point in feature space, where each is a the definitions above can be adapted in case some of variable taking values from D. The set of variables associ- the features are real-valued. As noted earlier, the paper ated with features is = {1, . . . , }. Moreover, the studies only categorical features.) notation v = (1, . . . , ) represents a specific point in feature space, where each is a constant represent- Definition 2.1 ( -relevant set [42]). Consider : B → ing one concrete value from D. An ML classifier M is = B, v ∈ B, (v) = ∈ B, and ∈ [0, 1]. ⊆ ℱ characterized by a (non-constant) classification function is a -relevant set for and v if, that maps feature space F into the set of classes , i.e. Prx( (x) = | x = v ) ≥ (3) : F → . An instance (or observation) denotes a pair (v, ), where v ∈ F and ∈ , with = (v). (We also -relevant sets were proposed in more recent work [42] as a generalized formalization of explanations. -relevant sets can be viewed as probabilistic PIs, with AXp’s representing a special case of -relevant sets where = 1, i.e. probabilistic PIs that are actual PIs. We briefly overview the definitions related with relevant sets. The assumptions regarding the probabilities of logical propositions are those made in earlier work [42]. Let Prx((x)) denote the probability of some proposition defined on the vector of variables x = (1, . . . , ), i.e. (where the restriction of x to the variables with indices in is represented by x = ()∈ ). predicted class is given by: ized by strong conditional independence assumptions among the features. Given some observation x ∈ F, the (x) = argmax∈
(Pr(|x)) Using the Bayes theorem, Pr(|x) can be computed as follows: Pr(|x) = Pr(,x)/Pr(x). In practice, we compute only the numerator of the fraction, since the denominator Pr(x) is constant for every ∈ . Moreover, given the conditional mutual independency of the features, we have: getting:
Pr(, x) = Pr() ×
∏︁ Pr(|) Furthermore, it is also common in practice to apply logarithmic transformations on probabilities of Pr(, x), thus log Pr(, x) = log Pr() + ∑︁ log Pr(|)
Therefore, (4) can be rewritten as follows: (x) = argmax∈ ︁(
︁) log Pr() + ∑︁ log Pr(|)
For simplicity, and following the notations used in [43], we use lPr to denote the logarithmic probabilities, thus getting: (x) = argmax∈ ︁(
︁) lPr() + ∑︁ lPr(|)
(Note that also for simplicity, it is common in practice to add a suficiently large positive threshold probability and then use only positive values.)
to each that the probability of the prediction being the same as the one for v is no less than .
Definition 2.2 (Min- -relevant set). Given , v ∈ B, and ∈ [0, 1], find the smallest , such that there exists
, with || = , and is a -relevant set for and
With the goal of proving the computational complexity relevant set, earlier work [42] restricted the definition to the case where is represented as a boolean circuit.
(Boolean circuits were restricted to propositional for- predict ⊕ . mulas defined using the operators a set of variables representing the inputs; this explains the choice of inputs over sets in earlier work [42].) ∨, ∧ and ¬, and using or not that radio station. Random variable denotes an age class, which can take values Y and O, denoting young and older listeners, respectively. The target class ⊕ denotes the prediction yes (i.e. the listener likes the radio station) and ⊖
denotes the prediction no (i.e. the listerner does not like the radio station). Thus, = {⊖ , ⊕} . Let us consider v = (1, 2, 3, 4, 5) = (t, f , f , f , t).
We associate to each literal ( = t) and ¬ to literals (Note that to use positive values, we added =
+4 to each lPr(· ).) As can be concluded, the classifier will
of finding a minimum-size set of features that is a - ( = f ). Using (
This section overviews the approach proposed in [43] NBC [46] is a Bayesian Network model [47] character- for computing AXp’s for binary NBCs. The general idea (Observe that Prx( (x) = | x = v ) is often re- Running Example.
Consider the NBC depicted graphferred to as the precision of [12, 21].) Thus, a -relevant set represents a set of features which, if fixed to some preically in Figure 1 1. The features are the discrete random variables 1, 2, 3, 4 and 5. Each can take valdefined value (taken from a reference vector
ues t or f denoting, respectively, whether a listener likes
(5)
(
(i.e. D = {1, . . . , }). Let, We consider an XLC with categorical features. (Recall that the paper considers NBCs with binary classes and categorical data.) Each feature ∈ ℱ has ∈ {1, . . . , },
∈ℱ (x) ≜ 0 + ∑︁ (, 1, 2, . . . , )
(
0.
The reduction of a binary NBC, with categorical features, to an XLC is completed by setting: 0 ≜ lPr(⊕ ) − ≜ lPr( =
1|⊕ ) − lPr( = ≜ lPr( = 2|⊕ ) − lPr( = 2|⊖ ), . . . , lPr( = |⊕ )
− lPr( = |⊖ ). Hence, the argmax
in (
∑︁= (lPr( = |⊕ ) − =1
=1 lPr( = |⊖ ))( = ) > 0
(
2 ⊕ ⊖
Pr(3|) 0.02 0.34 ⊕ ⊖
Pr(4|)
0.20
0.75
⊕
⊖
Example 1. Figure 3a shows the resulting XLC formula- under the assumption that (a) > 0. Thus, the
purtion for the example in Figure 2. We also let f be associ- pose is to find the smallest slack that can be achieved
ated with value 1 and t be associated with value 2, and by allowing the feature not in to take any value (i.e.
= 2. universal/free features), given that the literals in are
ifxed by a (i.e. ⋀︀∈ ( = )).
3.2. Explaining XLCs Let denote the smallest (or worst-case) value
associated with . Then, by letting every take any value,
We now describe how AXp’s can be computed for XLCs. the worst-case value of (e) is,
For a given instance x = a, define a constant slack (or
gap) value Γ given by, Γ = 0 + ∑︁ (
(
Computing an AXp corresponds to finding a
subsetminimal set of literals ⊆ ℱ such that (
∈ℱ
Moreover, from (
. The
Γ
=
=
0 + ∑︀∈ℱ −
Γ − ∑︀∈ℱ = − Φ
∑︀
∈ℱ ( −
)
(
Pr(5|) 0.95 0.03 where ≜ − , and Φ ≜ ∑︀∈ℱ − Γ = − Γ.
Recall the goal is to find a subset-minimal set such that the prediction is still (whatever the values of the other features): 0 + ∑︁∈ + ∑︁ ∈/ = − Φ + ∑︁
(
> 0 min such that ∑︀
=1 ∑︀=1 > Φ ∈ {0, 1}
(
Example 2. Figure 3b shows the values used for computing explanations for the example in Figure 2. For this example, the sorted ’s become ⟨ 1, 5, 2, 4, 3⟩.
By picking 1, 2 and 5, we ensure that the prediction is ⊕ , independently of the values assigned to features 3 and 4. Thus {1, 2, 5} is an AXp for the NBC shown in Figure 1, with the input instance (1, 2, 3, 4, 5) = (t, f , f , f , t). (It is easy to observe that ((t, f , f , t, t)) = ((t, f , t, f , t)) = ((t, f , t, t, t)) = ((t, t, f , f , t)) = ((t, t, f , t, t)) = ((t, t, t, f , t)) = ⊕ .)
This section investigates the computation of -relevant sets in the concrete case of NBCs.
Observe that Definition 2.2 imposes no restriction on the representation of the classifier that is assumed in earlier work [42], i.e. the logical representation of need not be a boolean circuit. As a result, we extend the definitions from earlier work [42], as detailed below.
A weak probabilistic AXp (WeakPAXp) is a set of fixed
features for which the conditional probability of
predicting the correct class exceeds , given = (v). Thus,
is a WeakPAXp if,
WeakPAXp(; F, , v, )
:= Prx( (x) = | x = v ) ≥
:= |{x ∈ F : (x) = ∧ (x = v )}|
|{x ∈ F : (x = v )}|
(
PAXp( ; F, , v, ) :=
WeakPAXp( ; F, , v, ) ∧
∀( ′ ⊊ ).¬WeakPAXp( ′; F, , v, )
(
WeakPAXp( ; F, , v, ) ∧
∀( ∖ {}).¬WeakPAXp( ∖ {}; F, , v, )
(
As stated earlier, the main purpose of this paper is to investigate the computation of LmPAXp explanations. The next section introduces a pseudo-polynomial time algorithm for computing LmPAXp’s. Although, LmPAXp are not minimal subset/cardinality, our experiments show that the proposed approach computes (in pseudo-polynomial time) succinct [44] and highly precise approximate explanations.
Earlier work [50, 51, 52, 53] proposed the use of dynamic programming (DP) for approximating the number of feasible solutions of the 0-1 knapsack constraint, i.e. the #knapsack problem. Here we propose an extension of the basic formulation, to allow counting feasible solutions of XLCs.
We are interested in the number of solutions of, ∑︁ ∈ℱ ( , , 2 , . . . , ) > − 0
1 where we assume all to be integer-valued, and nonnegative (e.g. this is what the translation from NBCs to XLCs yields). Moreover, (18) can be written as follows: ∑︁ ∈ℱ ( , − , − 2 , . . . , − ) < 0
1 which reveals the relationship with the Knapsack constraint.
(18) (19)
For each , let us sort the − in non-decreasing or- Table 1 der, collapsing duplicates, and counting the number of DP table for Example 3 duplicates, obtaining two sequences: ′ and each ≥ 1 gives such that 1 < 2 < . . . < the number of repetitions of weight .
We require the weights to be integer and non-negative, Counting. Let (, ) denote the number of solu- and so we sum to each the complement of the most tions of (19) when the subset of features considered is negative plus 1. Therefore, we add +4 to each and {1, . . . , } and the sum of picked weights is at most . +16 to right-hand side of the inequality. Thus, we get To define the solution for the first features, taking into account the solution for the first − 1 features, we must ∑︁ ( , 3, 2, 1) < 9 consider that the solution for can be obtained due to ∈{1,2,3,4} any of the possible values of . As a result, for an XLC the general recursive definition of (, ) becomes,
′ (, ) = ∑︁ × ( − 1, − )
=1 Moreover, (1, ) is given by, ⎧ 0 ⎪ ⎪ ⎪ ⎪⎪ 11 ⎪ ⎪ ⎪ ⎨ (1, ) = if < 11 if 11 ≤ < 12
By default, the dynamic programming formulation 11 + 12 if 12 ≤ < 13 assumes that features can take any value. However, the ⎪⎪⎪ . . . same formulation can be adapted when features take a ⎩⎪⎪⎪⎪⎪ ∑︀=′1 1 1 if 1′1 ≤ fgoivrecnom(fixpedu)tivnagluLem.OPbAsXerpv’es.that this will be instrumental Consider that feature is fixed to value . Then, the In addition, if < 0, then (, ) = 0, for = 1, . . . , . formulation for (, ) becomes: Finally, the dimensions of the (, ) table are as follows: 1. The number of rows is . (, ) = × ( − 1, − ) = ( − 1, − ) 2. The (worst-case) number of columns is given by: For this formulation, = 1 picks value 3. (For example, we can pick two with value 1, but not 3, as expected.)
In this case, the DP table size will be 4 × 12, even
though we are interested in entry (
Given that is fixed, then it is the case that = 1.
Example 4. For Example 3, assume that 2 = 1 and 4 = 3. Then, the constraint we want to satisfy is:
∑︁ ( , 1, 2, 3) > 3 ∈{1,3} ∈{1,3} Following a similar transformation into knapsack formulation, we get
∑︁ ( , 3, 2, 1) < 5
After updating the DP table, with fixing features 2 and 4, we get the DP table shown in Table 2. As a result, we can conclude that the number of solutions is 6.
The table (, ) can be filled out in pseudopolynomial time. The number of rows is . The number of columns is (see (20)). Moreover, the computation of each entry uses the values of at most other entries.
Thus, the total running time is: Θ(2 × ). ′ = ∑︁ ′ ×
′ ∈ℱ ′ represents the largest possible value, in theory. However, in practice, it sufices to set the number of columns to = 0 + , which is often much smaller than ′.
Example 3. Consider the following problem. There are 4 features, ℱ = {1, 2, 3, 4}. Each feature takes values in {1, 2, 3}, i.e. ∈ {1, 2, 3}. The prediction should be 1 when the sum of the values of the variables is no less than 8. We set 0 = − 7, and get the formulation,
∑︁ ∈{1,2,3,4}
( , 1, 2, 3) > 7 where each picks value in {1, 2, 3}. We translate to the extended knapsack formulation and obtain:
∑︁ ∈{1,2,3,4} ( , − 1, − 2, − 3) < − 7
Algorithm 1 depicts our method for computing 0 1 2 3 4 5 6 7 8 9 10 11 12 LmPAXp’s given a prediction function of an NBC, an input instance v and a threshold . The procedure Lm1 0 1 2 3 3 3 3 3 3 – – – – PAXp is referred to as a deletion-based algorithm3; it 2 0 0 0 0 1 2 3 3 3 – – – – starts from a set of features , e.g. initialized to ℱ and 3 0 0 0 0 0 1 3 6 8 – – – – then it iteratively drops features while the updated set 4 0 0 0 0 0 0 1 3 6 – – – – remains a WeakPAXp. The function isWeakPAXp implements the approach described in the previous section, which measures explanation precision by exploitFrom XLCs to Positive Integer Knapsacks. To as- ing a pseudo-polynomial algorithm for model countsess heuristic explainers, we consider NBCs, and use a ing. Hence, it is implicit that the DP table is updated standard transformation from probabilities to positive at each iteration of the loop in the LmPAXp procedure. real values [54]. Afterwards, we convert the real values More specifically, when a feature is newly set univerto integer values by scaling the numbers. However, to sal, its associated cells (, ) are recalculated such that faovloloidwbinugilodpintigmaizvaetrioynl.aTrghee DnuPmtabbelre,owfdeeicmimpalelmpleanctesthoef fixe(d,,i.e). = ∑∈︀=′,1then× ((,)− =1,(− − 1,);a− ndw)hwenheries the probabilities is reduced while there is no decrease in ≜ lPr( = |) − lPr( = |¬). Furthermore, we the accuracy of the classifier both on training and on test point out that in our experiment, is initialized to an data. In our experiments, we observed that there is no AXp that we compute initially for all tested instances loss of accuracy if four decimal places are used, and that using the outlined (polynomial) algorithm in Section 3. there is a negligible loss of accuracy with three decimal It is easy to observe that features not belonging to do places. not contribute in the decision of (v) (i.e. their removal does not change the value of ⊖ that equals to zero) and Assessing explanation precision. Given a Naive thus can be set universal at the initialisation step, which Bayes classifier, expressed as an XLC, we can assess ex- allows us to improve the performance of Algorithm 1. planation accuracy in pseudo-polynomial time. Given Moreover, we apply an heuristic order over that aims an instance v, a prediction (v) = ⊕ , and an ap- to remove earlier less relevant features and thus to proproximate explanation S, we can use the approach de- duce shorter approximate explanations. Typically, we orscribed in this section to count the number of instances der following the increasing order of values, namely consistent with the explanation for which the predic- the reverse order applied to compute the AXp. Contion remains unchanged (i.e. number of points x ∈ F ducted preliminary experiments using a (naive heuristic) s.t. ( (x) = (v) ∧ (x = v ))). Let this number lexicographic order over the features show less succinct be ⊕ (given the assumption that the prediction is ⊕ ). explanations.
Let the number of instances with a diferent prediction Finally, notice that Algorithm 1 can be used to com(⊖ ̸ = (v))2 be ⊖ . Hence, the conditional probabil- pute an AXp, i.e. an LmPAXp with = 1. Nevertheless, ity (2) can be defined, in the case of NBCs, as follow: the polynomial time algorithm for computing AXp’s proposed in [43] remains a better choice to use in case of AXp’s than Algorithm 1 which runs in pseudo polynoPrx( (x) = ⊕ | x = v ) = mial time.
⊕ |{x ∈ F : (x = v )}|
Observe that the numerator |{x ∈ F : (x) = ⊕ ∧ (x = v )}| is expressed by the number of models ⊕ , i.e. the points x in feature space that are consistent with v given and with prediction ⊕ . Further, we have Prx( (x) = ⊕ | x =v ) = 1 − Prx( (x) = ⊖ |
x = v ) = 1 −
⊖ |{x ∈ F : (x = v )}|
Example 5. Let us consider again the NBC of the running example (Example 1) and v = (t, f , f , f , t). The corresponding XLC is shown in Figure 3b (Example 2).
Also, consider the AXp {1, 2, 5} of v and = 0.85. The resulting DP table for = {1, 2, 5} is shown in Table 3.
Note that for illustrating small tables, we set the number of decimal places to zero (greater number of decimal places, i.e. 1,2, etc, were tested and return the results). (Also, note that the DP table reports “—” if the cell is not calculated during the running of Algorithm 1.) Moreover, where ⊖ = |{x ∈ F : (x) = ⊖ ∧
(x = v )}|. 2As we are in binary setting, then ⊖ = ¬⊕ = ¬ (v)). 3This sort of algorithm can be traced at least to the work of Valiant[55], but some authors [56] argue that it is also implicit in works from the 19th century [57].
Output: LmPAXp
← ∖ {
return
1: procedure LmPAXp(, v, )
2: ← { 1, . . . , }
3: for ∈ {1, . . . , } do
4: if isWeakPAXp( ∖ {}, (x) = , ) then
5:
}
then the number of models of ′ must not exceed the
number of models of . So, we can argue that there is
monotonicity in the number of models, but not on the
precision.
Properties of LmPAXp’s. In addition to the comments
we convert the probabilities into positive integers, so we above, and by carefully computing LmPAXp’s, these can
sum to each the complement of the most negative exhibit important properties. Let denote an AXp. Then,
plus 1. The resulting weights are shown in Figure 4. for any LmPAXp obtained using as the seed, i.e. is
Thus, we get ∑︀∈{1,2,3,4,5} (, 1, 2) < 17. Ob- required to be a subset of , then we have the following
serve that the number of models ⊕ = (
In summary, Algorithm 1 starts with = {1, 2, 5}, then 5.1. Experimental setup at iteration#1, feature 1 is tested and since {2, 5} is not WeakPAXp then 1 is kept in ; at iteration#2, feature 2 is tested and since {1, 5} is a WeakPAXp, then is updated (i.e. = {1, 5}); at iteration#3, feature 5 is tested and since {1} is not a WeakPAXp, then 5 is saved in .
As a result, the delivered LmPAXp is {1, 5}.
The benchmarks used in the experiments comprise publicly available and widely used datasets that originate from UCI ML Repository4 and Penn ML Benchmarks5.
The number of training data (resp. features) in the target datasets varies from 336 to 14113 (resp. 10 to 37) and on average is 3999.1 (resp. 20.0). All the NBCs are trained
Let us underline that we could initialize to ℱ , in using the learning tool scikit-learn6. The data split for which case the number of models would be 1. However, training and test data is set to 80% and 20%, respectively. we opt instead to always start from an AXp. In the exam- Model accuracies are above 80% for the training accuracy ple, the AXp is {1, 2, 5} which, because it is an AXp, the and above 75% for the test accuracy. number of models must be 4 (i.e. 22, since two features A prototype implementation of the proposed approach are free). for computing relevant sets is developed in Python. To
For any proper subset of the AXp, with free variables, compute AXp’s, we use the Perl script implemented by it must be the case that the number of models is strictly [43].The prototype implementation was tested with varyless than 2. Otherwise, we would have an AXp as a ing the threshold ∈ {0.90, 0.93, 0.95, 0.98}. When proper subset of another AXp; but this would contradict the definition of AXp. The fact that the number of models is strictly less than 2 is confirmed by the examples of converting probabilities from real values to integer val- instance when its AXp is larger than the target size ues, the selected number of decimal places is 3. (As out- (recall that is initialized to ); otherwise we consider lined earlier, we observed that there is a negligible ac- the AXp is succinct and the explainer returns . For curacy loss from using three decimal places.) In order example, assume the target size is 7, an instance v1 with to produce explanations of size admissible for the cogni- an AXp 1 of 5 features and an second instance v2 with tive capacity of human decision makers [44], we selected an AXp 2 of 8 features, then for v1 the output will be three diferent target sizes for the explanations to com- 1 and for v2 the output will be a subset of 2. pute: 9, 7 and 4, and we compute a LmPAXp for the input For each dataset, we run the explainer on 200 instances 1 — — — — 2 — — — — 1 — — — — 1 — — — — — 1 — — — — 2 — — — — 2 — — — — 2 — — — — — 2 — — — — 3 — — — — 3 — — — — 3 — — — — — — — — — — — — — — — — — — — — — — — — 2 — — — — 3 — — — — 4 — — — — 4 — — — — — 4 — — — — 6 — — — — 7 — — — — 7 — — — — — 4 — — — — 6 — — — — 7 — — — — 9 Assessing ApproxPAXp explanations for NBCs. Columns m and #I show, respectively, number of features and tested instances in the Dataset. Column A% reports in (%) the training accuracy of the classifier. Column reports in (%) the used value of and Precision report, respectively, the average explanation length and the average explanation precision (± results obtained with the remaining parameters, i.e. ∈ 4.) As can be observed in practice the algorithm is efective and scales for large datasets. As can be seen, the runtimes are negligible for all datasets, never exceeding 2 seconds for the largest datasets (i.e. agaricus or mushroom) and the average is 0.33 seconds for all tested instances across all datasets and all settings. Furthermore, we point out that the implemented prototype was tested with 4 decimal places to assess further the scalability of the algorithm on larger DP tables, and the results show that computing LmPAXp’s is still feasible, e.g. with agaricus the average runtime when for all considered settings, the locally-minimal explana- the target size set to 7 is 10.08 seconds. tions are succinct, in particular the average sizes of the The table also reports the number of explanations beexplanations are invariably lower than the target sizes. ing shorter than or of size equal to the target size over to 7 Moreover, theses explanations ofer strong guarantees of precision, as their average precisions are strictly greater than with significant gaps (e.g. above 97%, in column LmPAXp≤ 7, for datasets adult, vote, threeOf9, xd6, mamo and tumor and above 95% for chess and kr-vs-kp). An important observation from the results, is the gain of succinctness (explanation size) when comparing AXp’s with LmPAXp’s. In fact, for some datasets, the AXp’s are too large (e.g. for chess and kr-vs-kp datasets, the average number of features in the AXp’s is 12), exceeding the cognitive limits of human decision makers [44] (limited
2 features). To illustrate that, one can focus on the dataset agaricus or mushroom and see that for a target size equals to 7, the average length of the LmPAXp’s (i.e. 5.3 and 5.1, resp.) is 2 times less than the average length of the AXp’s (i.e. 10.3 and 10.7, resp.). Besides, the results show that = 0.95 is a good probability threshthe total number of tested instances. We observe that for both settings LmPAXp≤ 9 and LmPAXp≤ 7 and for the majority of datasets and with a few exceptions the fraction is significantly high, e.g. varying for 96% to 100% for adult dataset. However, in our assessment we observed that for LmPAXp≤ 4 despite the poor percentage of wins for some datasets, it is the case that the average lengths of computed explanations are close to 4 (see Table 13 in [1]).
Overall, the experiments demonstrate that our
approach eficiently computes succinct and provably precise
explanations for NBCs. The results also showcase
empirically the advantage of the algorithm, i.e. in practice one
may rely on the computation of LmPAXp’s, which pays
of in terms of (
This paper builds on recent work on computing rigorous probabilistic explanations [42], and investigates the concrete case of NBCs. The paper proposes a pseudopolynomial algorithm for computing the number of points in feature space predicting a specific class, and relates this problem with that of computing a rigorous probabilistic explanation. Furthermore, the paper proposes an algorithm for computing locally minimal probabilistic explanations, which ofers strong guarantees in terms of precision. The experimental results confirm that short and precise probabilistic explanations can be eficiently computed in the case of NBCs.
Two lines of future work can be envisioned. One line is to investigate the complexity of explaining multi-class NBCs and extend the approach for computing locally minimal probabilistic explanations for multi-class Naive Bayes models. Furthermore, one might be interested in computing smallest probabilistic explanations instead of approximates. Hence, another line of research is to devise a logical (Satisfiability Modulo Theories, SMT) encoding for computing cardinality minimal probabilistic explanations.
This work was supported by the AI Interdisciplinary Institute ANITI, funded by the French program “Investing for the Future – PIA3” under Grant agreement no. ANR19-PI3A-0004, and by the H2020-ICT38 project COALA “Cognitive Assisted agile manufacturing for a Labor force supported by trustworthy Artificial intelligence”, and by the National Research Foundation, Prime Minister’s Ofifce, Singapore under its Campus for Research Excellence and Technological Enterprise (CREATE) programme.