# Enhancing the intelligibility of decision trees with concise and reliable probabilistic explanations

Louenas Bounia, Insaf Setitra

► To cite this version:

Louenas Bounia, Insaf Setitra. Enhancing the intelligibility of decision trees with concise and reliable probabilistic explanations. Data and Knowledge Engineering, 2025, 156, pp.102394. 10.1016/j.datak.2024.102394. hal-05486082

HAL Id: hal-05486082

https://hal.science/hal-05486082v1

Submitted on 2 Feb 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
<figure><img src="image_2.png" /></figure>

# Enhancing the intelligibility of decision trees with concise and reliable probabilistic explanations☆

Louenas Bounia *, Insaf Setitra

UTC de Compiègne, Laboratoire Heudiasyc-UMR-CNRS 7253, France

## ARTICLE INFO

**Keywords:**

eXplainable AI

Decision trees

Probabilistic explanations

Greedy algorithms

Tweet Sentiment Extraction

## ABSTRACT

This work deals with explainable artificial intelligence (XAI), specifically focusing on improving the intelligibility of decision trees through reliable and concise probabilistic explanations. Decision trees are popular because they are considered highly interpretable. Due to cognitive limitations, abductive explanations can be too large to be interpretable by human users. When this happens, decision trees are far from being easily interpretable. In this context, our goal is to enhance the intelligibility of decision trees by using probabilistic explanations. Drawing inspiration from previous work on approximating probabilistic explanations, we propose a greedy algorithm that enables us to derive concise and reliable probabilistic explanations for decision trees. We provide a detailed description of this algorithm and compare it to the state-of-the-art SAT encoding. In the order to highlight the gains in intelligibility while emphasizing its empirical effectiveness, we will conduct in-depth experiments on binary decision trees as well as on cases of multi-class classification. We expect significant gains in intelligibility. Finally, to demonstrate the usefulness of such an approach in a practical context, we chose to carry out additional experiments focused on text classification, in particular the detection of emotions in tweets. Our objective is to determine the set of words explaining the emotion predicted by the decision tree.

## 1. Introduction

Basically, the classification problem is to extrapolate from a set of labeled data instances a hypothesis, or classifier, that accurately predicts the labels of new incoming data instances. Decision trees, random forests, support vector machines, and neural nets, are common examples of classifiers for which theoretical properties have been extensively studied in the machine learning literature. The spectrum of applications for these classifiers is wide, ranging from document and image classification, to customer profiling and medical diagnosis. However, with the increasing deployment of data-driven learning models in our society comes the issue of explaining predictions in human intelligible terms. As a key topic of eXplainable Artificial Intelligence (XAI), this issue is exacerbated in sensitive domains, such as cybersecurity and healthcare, where explanations are crucial for building trust and confidence in the classifier [2-7].

Context. Among the various types of explanations proposed in the XAI literature, formal explanations stand out as particularly intriguing due to their potential for mathematical validation [8]. Notably, in cases where the classifier *h* takes the form of a Boolean function, a common approach involves providing an *abductive* explanation, also referred to as a *sufficient reason*, which

<footnote>☆ This is an extended and revised version of a selected paper (Bounia, 2024) [1] (in French) from EGC'24.</footnote>

<footnote>* Corresponding author.
E-mail address: bounia@lipn.univ-paris13.fr (L. Bounia).</footnote>
is logically sound [9,10]. This explanation entails identifying a subset-minimal collection of features *I* such that the restricted data instance *x*<sub>*I*</sub> determines the output *h*(*x*) [11]. While finding such explanations is generally hard, tractable cases exist for various hypothesis classes [12,13]. The need for explanations becomes critical in the context of opaque machine learning models like random forests, boosted trees, support vector machines, and deep neural networks, where understanding the decision-making process is challenging [14,15]. This growing reliance on machine learning techniques underscores the importance of research in Explainable Artificial Intelligence (XAI), which aims to develop effective methods for interpreting and explaining model decisions. While model-agnostic methods like LIME [16], SHAP [17], and Anchors [18] are commonly used, despite some limitations in the reliability of model-agnostic methods as reported by [19].

However, the soundness of explanations is not the only criterion for clarifying in intelligible terms predictions made by classifiers. The *conciseness* property is also important, since an abductive explanation involving too many features cannot be understood by human users. Indeed, in cognitive psychology, it has long been recognized that there is an upper limit on our ability to reason about simultaneously interacting elements. As conjectured by [20], this limit is seven plus or minus two elements and, since then, it has been confirmed by many experiments in cognitive science. Thus, restricting the size of explanations appears as a *constraint* for ensuring their intelligibility.

Formal approaches in XAI have a significant limitation, namely that the size of explanations can be large. It is important to keep in mind that explanation is a social process [4,6], where users are human beings with inherent cognitive limitations. In his seminal article [20], psychologist **G. Miller** introduced the idea of “chunking” objects by people (i.e., grouping them into a unit) and argued that, due to limitations in human memory, the size of chunks is limited to 7±2, and if this size exceeds 7±2, then memory does not memorize these objects well. Recent work has investigated probabilistic explanations as a mechanism to reduce the size of explanations and make them more concise and suitable for explaining the uncertain real world [21]. The decision problem involves checking whether an instance **x** admits a **δ**-probable reason of size *k* under a Boolean function *f*, where *f* is specified as a CNF formula, which is NP<sup>PP</sup>-complete [21]. This result shows the complexity of the problem. Indeed, finding a probabilistic explanation (subset of features *S*) subject to a cardinality constraint is NP-hard, even for the restricted class of decision trees [22]. As indicated by [23], this difficulty remains, even when *S* is a subset of a given sufficient reason *I*, in the case of decision trees.

**Motivation.** Decision trees are generally considered interpretable due to the existence of a unique explanation for each instance x, known as the direct reason [24] (or path explanation [25]). However, due to the significant size of these explanations (see [24]), it is challenging to consider them easily understandable by humans. Our goal is to improve the interpretability of decision trees using probabilistic explanations. We drew inspiration from previous work on approximating probabilistic explanations [23]. Based on these results, we propose a greedy algorithm to generate concise and reliable probabilistic explanations for decision trees, in both binary and multi-class classification scenarios. We describe this algorithm in detail and empirically compare it to state-of-the-art SAT encoding [22], highlighting the enhancement of interpretability and emphasizing its effectiveness.

*Organization of the paper.* We introduce the main terms as well as the decision tree model and the family of orthogonal DNF in Section 2. In Section 3, we recall the concepts of abductive explanations and define *δ*-probable explanations, as well as sufficient reasons. Section 4 provides further clarification on the case of generating probabilistic explanations in both the multi-class classification and binary classification scenarios. The two greedy algorithms used will also be presented in detail in this section, while Section 5 will be dedicated to experiments. These experiments have two main objectives: firstly, to demonstrate that our probabilistic explanations are reliable and concise, and secondly, to show, through an application on text classification, how our explanations can be used to explain emotion detection in tweets while leveraging user expertise. A discussion on related work has been initiated to examine and compare various methods that could be used to obtain probabilistic explanations in Section 6. We conclude this work in Section 7.

## 2. Decision tree, orthogonal DNF, abductive explanations

### 2.1. Preliminaries

**Boolean functions.** For an integer $n$, let $[n]$ be the set $\{1, \dots, n\}$. By $F_n$ we denote the class of all Boolean functions from $\{0, 1\}^n$ to $\{0, 1\}$, and we use $X_n = \{x_1, \dots, x_n\}$ to denote the set of input Boolean variables, corresponding to the features under consideration. Any assignment $x \in \{0, 1\}^n$ is called an instance. If $f(x) = 1$ for some $f \in F_n$, then $x$ is called a model of $f$. $x$ is a positive instance when $f(x) = 1$ and a negative instance when $f(x) = 0$.

We refer to *f* as a *propositional formula* when it is described using the Boolean connectives **^** (conjunction), **v** (disjunction), and **¬** (negation), together with the Boolean constants 1 (true) and 0 (false). Other connectives, like material implication → can also be considered. As usual, a *literal* *l* is a variable $x_i$ (a positive literal) or its negation $\neg x_i$, also denoted $\bar{x}_i$ (a negative literal). $x_i$ and $\bar{x}_i$ are complementary literals. A positive literal $x_i$ is associated with a positive feature (i.e., $x_i$ is set to 1), while a negative literal $\bar{x}_i$ is associated with a negative feature (i.e., $x_i$ is set to 0). A *term* (or *monomial*) *t* is a conjunction of literals, and a *clause* *c* is a disjunction of literals. A term is typically considered as a set of literals interpreted conjunctively, whereas a clause is viewed as a set of literals interpreted disjunctively. A *DNF formula* (Disjunctive Normal Form) consists of a disjunction of terms, while a *CNF formula* (Conjunctive Normal Form) consists of a conjunction of clauses. Frequently, a DNF formula a disjunction of terms, and a CNF formula is a conjunction of clauses. The set of variables occurring in a formula *f* is denoted *Var*(*f*) (*Lit*(*f*) is the set of literals of *f*). A formula *f* is *consistent* if and only if it has a model. A CNF formula is *monotone* whenever every literal over a given variable in the formula has the same polarity (i.e., whenever a literal occurs in the formula, the complementary literal has no occurrence in
the formula). A formula $f_1$ implies a formula $f_2$, noted $f_1 \models f_2$, if and only if every model of $f_1$ is a model of $f_2$. Two formulae $f_1$ and $f_2$ are equivalent, noted $f_1 \equiv f_2$ whenever they have the same models.

Given an instance $z \in \{0,1\}^n$, the corresponding term is defined as

$$t_z = \bigwedge_{i=1}^{n} x_i^{z_i} \quad \text{where} \quad x_i^0 = \bar{x}_i \text{ and } x_i^1 = x_i$$

A term $t$ covers an instance $z$ if $t \subseteq t_z$. An implicant of a Boolean function $f$ is a term that implies $f$. A prime implicant of $f$ is an implicant $t$ of $f$ such that no proper subset of $t$ is an implicant of $f$. Dually, an implicate of a Boolean function $f$ is a clause that is implied by $f$, and a prime implicate of $f$ is an implicate $c$ of $f$ such that no proper subset of $c$ is an implicate of $f$.

We define $|y|_{\perp} = |\{i \in \{1, ..., n\} : y[i] = \perp\}|$, where $\perp$ represents a missing value. The restriction of $x$ to $S$, denoted $x_S$, is the partial instance in $\{0, 1, \perp\}^n$ such that, for each $i \in [n]$, $(x_S)_i = x_i$ if $i \in S$, and $(x_S)_i = \perp$ otherwise. Any instance $y \in \{0, 1\}^n$ is covered by $x_S$ if and only if $y_S = x_S$.

Let us illustrate the previous notions on the following example:

**Example 1.** The DNF formula $f_1 = (x_1 \land x_2) \lor (\bar{x}_2 \land x_3)$ and the CNF formula $f_2 = (x_1 \lor x_2) \land (x_1 \lor x_2 \lor x_3)$ represent two Boolean functions from $F_3$. We have $\text{Var}(f_1) = \text{Var}(f_2) = \{x_1, x_2, x_3\}$. $f_1$ and $f_2$ are consistent since $x = (1, 1, 1)$ is a model of $f_1$ and a model of $f_2$. $f_2$ is monotone while $f_1$ is not since $f_1$ contains an occurrence of the positive literal $x_2$ and an occurrence of the negative literal $x_2$ (which is complementary to $x_2$). We can see that $f_1$ implies $f_2$, but $f_1$ and $f_2$ are not equivalent since $f_2$ does not imply $f_1$. Indeed, $(0, 1, 0)$ is a model of $f_2$ but not a model of $f_1$. The term $x_1 \land x_3$ is an implicant of $f_1$ that covers $x$ since the set of literals $\{x_1, x_2, x_3\}$ corresponding to $t_x$ is a superset of the set of literals $\{x_1, x_3\}$. More specifically, $x_1 \land x_3$ is a prime implicant of $f_1$ since neither $x_1$ nor $x_3$ is an implicant of $f_1$. $f_1$ has three prime implicants: $x_1 \land x_2$, $x_2 \land x_3$, and $x_1 \land x_3$. The clause $x_1 \lor x_2 \lor x_3$ is an implicant of $f_2$, but not a prime one, since the clause $x_1 \lor x_2$ is an implicant of $f_2$. In fact, $x_1 \lor x_2$ is the unique prime implicant of $f_2$.

## 2.2. Decision trees

With these basic notions in hand, we now focus on the model addressed in this article, namely decision trees, which are a representation class of Boolean functions.

**Definition 1 (Decision Tree).** A (Binary) decision tree over $X_n$ is a binary tree $T$, each of whose internal nodes is labeled with one of $n$ input Boolean variables from $X_n$, and whose leaves are labeled 0 or 1. Every variable is assumed to appear at most once on any root-to-leaf path (read-once property). The value $T(x) \in \{0, 1\}$ of $T$ on an input instance $x$ is given by the label of the leaf reached from the root as follows: at each node, go to the left or right child depending on whether the input value of the corresponding variable is 0 or 1, respectively. The size of $T$, denoted $|T|$, is given by the number of its nodes.

**Remark 1.** A (Binary) decision tree over $X_n$ for multi-class classification is a binary tree $T$, where each internal node is labeled with one of $n$ input Boolean variables from $X_n$, and each leaf is labeled with one of $k$ classes, where $k$ is the number of classes in the classification task. The leaves are labeled with class identifiers ranging from 0 to $k-1$. Similar to binary classification, every variable is assumed to appear at most once on any root-to-leaf path (read-once property). The value $T(x) \in \{0, 1, ..., k-1\}$ of $T$ on an input instance $x$ is determined by the label of the leaf reached from the root node.

The class of decision trees over $X_n$ is denoted $\text{DT}_n$. It is well-known that any decision tree $T \in \text{DT}_n$ can be transformed in linear time into an equivalent disjunction of terms, denoted DNF($T$) (This DNF is an orthogonal DNF 2.), where each term corresponds to a path from the root to a leaf labeled with 1 (or to the predicted class $c$ where $T(x) = c$, in the case of multi-class classification). Dually, $T$ can be transformed in linear time into a conjunction of clauses, denoted CNF($T$), where each clause is the negation of the term describing a path from the root to a leaf labeled with 0 [24,25] (or labeled with another class than the predicted class, in the case of multi-class classification).

**Remark 2.** In the following, we use set notation to describe the term associated with a subset $S$ of input features, denoted as $t_S$. For example, for the instance $x = (1, 1, 0)$, we write $t_x = x_1 \land x_2 \land \neg x_3 = \{x_1, x_2, \neg x_3\}$.

## 2.3. Orthogonal DNF

A classical problem in Boolean theory is to derive an orthogonal disjunctive normal form of an arbitrary Boolean function. Let's consider the DNF:

$$\phi = \bigvee_{k=1}^{m} \left( \bigwedge_{i \in A_k} x_i \bigwedge_{j \in B_k} \overline{x_j} \right) \qquad (1)$$

Where $A_k \cap B_k = \emptyset$ for all $k = 1, 2, ..., m$. $C_k = (\bigwedge_{i \in A_k} x_i \bigwedge_{j \in B_k} \overline{x_j})$ is the $k$th term of the DNF.
<figure><img src="image_3.png" /><figcaption>Fig. 1. A decision tree T over {$x_1, x_2, x_3$}.</figcaption></figure>

**Definition 2 (Orthogonal DNF).** A DNF of the form (1) is said to be orthogonal if $(A_k \cap B_l) \cup (A_l \cap B_k) \neq \emptyset$ for all $k, l \in \{1, 2, \dots, m\}$ and $k \neq l$.

**Proposition 1.** Let $\phi$ be an orthogonal DNF of the form (1), then the number of its models is equal to:

$$w(\phi) = \sum_{k=1}^{m} 2^{n-|A_k|-|B_k|} = \sum_{k=1}^{m} \alpha_k$$

where $\alpha_k = 2^{n-|A_k|-|B_k|}$ for each term $C_k$ of the DNF formula $\phi$.

**Remark 3.** For an instance $x$ and a decision tree $T \in \mathcal{DT}_n$ such that $T(x) = 1$, let $t$ be a subterm of $t_x$. The conditioning of DNF($T$) by a term $t$, denoted $\text{DNF}(T) | t$, remains a DNF orthogonal formula [26].

**Example 2.** The decision tree in Fig. 1 separates Cattleya orchids from other orchids using the following features: $x_1$: “has fragrant flowers”, $x_2$: “has one or two leaves”, $x_3$: “has large flowers”.

A DNF representation of $T$ is given by:

$$\text{DNF}(T) = \{x_1 \wedge x_2, x_1 \wedge \overline{x_2} \wedge \overline{x_3}, \overline{x_1} \wedge x_2\}$$

The DNF($T$) is an orthogonal DNF because it satisfies Definition 2, and the number of models of DNF($T$) is: $w(\text{DNF}(T)) = 2^1+2^0+2^1 = 2+1+2=5$.

Given an instance $a = (1, 1, 0)$ such that $T(a) = 1$, then for $t_S = \{x_1, \overline{x_3}\}$, the formula $\text{DNF}(T) | t_S = \{x_1 \wedge x_2 \wedge \overline{x_3}, x_1 \wedge \overline{x_2} \wedge \overline{x_3}\}$ is a DNF formula, and this DNF is orthogonal. The number of models of DNF($T$) $| t_S$ is $w(\text{DNF}(T) | t_S) = 2^0+2^0=2$.

## 2.4. Abductive explanations

The abductive explanation aims to answer the question of why a particular instance was classified as it was by the classifier, particularly in the context of decision trees. A notable feature of decision trees is that they provide a single explicit abductive explanation for classifying any input instance $x$, known as its direct reason (denoted as $P_x^T$) [24]. $P_x^T$ corresponds to the unique root-to-leaf path of $T$ that is compatible with $x$, representing the path-restricted explanation for $x$ given $T$. Generally, this reason may differ from the instance itself (although it may coincide with it).

Another important notion of abductive explanations corresponds to the following concept of sufficient reason [9]. Unlike sufficient reasons that are subset-minimal abductive explanations, direct reasons may contain arbitrarily many redundant features [25]. By “redundant”, we mean features that are redundant for making a decision.

**Definition 3 (Sufficient Reason).** Let $T \in \mathcal{DT}_n$ and $x \in \{0, 1\}^n$ such that $T(x) = 1$ (resp. $T(x) = 0$). A sufficient reason for $x$ given $T$ is a prime implicant $t$ of $T$ (resp. $\neg T$) that covers $x$. A minimum-size sufficient reason for $x$ given $T$ is a sufficient reason for $x$ given $T$ that contains a minimal number of literals.

Thus, a sufficient reason for an instance $x$ given a class described by a Boolean function $f$ is a subset $t$ of the characteristics of $x$ that is minimal with respect to set inclusion, and such that any instance $x_0$ sharing this set $t$ of characteristics is classified by $f$ as $x$ is. Thus, when $f(x) = 1$, $t$ is a sufficient reason for $x$ given $f$ if and only if $t$ is a prime implicant of $f$ such that $t$ covers $x$, and when $f(x) = 0$, $t$ is a sufficient reason for $x$ given $f$ if and only if $t$ is a prime implicant of $\neg f$ such that $t$ covers $x$. Accordingly, sufficient reasons are suited to explain why the instance at hand $x$ has been classified by $f$ as it has been classified. In the case of multi-class classification for the tree $T$, we can consider a one-versus-all approach to reduce it to the binary case.
<caption>**Table 1**</caption>

Statistics for 7 benchmarks and their corresponding decision trees. Columns represent: name (dataset name), F (number of features), I (number of instances), %A (accuracy of the decision trees), |T| (size of the decision tree), and $P_x^T$ (average size of direct reasons).

<table><thead><tr><th colspan="3">Benchmark</th><th colspan="3">Decision trees</th></tr><tr><th>name</th><th>F</th><th>I</th><th>%A</th><th>|T|</th><th>P<sub>x</sub><sup>T</sup></th></tr></thead><tbody><tr><td>compas</td><td>11</td><td>6172</td><td>65.12</td><td>550</td><td>10.94 (±2.18)</td></tr><tr><td>gisette</td><td>5000</td><td>7000</td><td>93.43</td><td>151</td><td>25.15 (±10.95)</td></tr><tr><td>farm-ads</td><td>54876</td><td>4143</td><td>87.13</td><td>222</td><td>21.59 (±17.55)</td></tr><tr><td>mnist49</td><td>784</td><td>13782</td><td>95.28</td><td>231</td><td>18.91 (±5.02)</td></tr><tr><td>mnist38</td><td>784</td><td>13966</td><td>95.78</td><td>209</td><td>17.47 (±4.67)</td></tr><tr><td>bank</td><td>20</td><td>41188</td><td>88.77</td><td>2116</td><td>14.89 (±2.39)</td></tr><tr><td>christine</td><td>1636</td><td>5418</td><td>61.32</td><td>322</td><td>15.57 (±8.42)</td></tr></tbody></table>

**Example 3.** Let $T$ be the tree in Fig. 1 and the instance $a = (1,0,0)$. We observe that $T(a) = 1$. The direct reason for $a$ given $T$ is $P_a^T = x_1 \wedge \bar{x}_2 \wedge \bar{x}_3$, which is a sufficient reason for $a$, and it is the unique minimum-size sufficient reason. Thus, the instance $a' = (1,1,0)$ that differs from $a$ only in $x_2$ is classified by $T$ as $a$, but they don't have the same sufficient reason or direct reason. $P_{a'}^T = x_1 \wedge x_2$ is the direct reason for $a'$ given $T$, and $x_2$ is a minimum-size sufficient reason for $a'$ given $T$.

## 2.5. Some statistics on decision trees

Although decision trees are known for their interpretability, they are not immune to certain limitations in practice. It is therefore essential to examine statistics related to these models to better understand the vital need to improve their interpretability. In this section, we will particularly examine statistics regarding the size of trees generated by [27] and the size of direct reasons. It is common to observe that these trees can become excessively deep or contain a large number of nodes, which can compromise their interpretability. A concrete example is provided by a decision tree trained on the Gisette benchmark, showing that it is difficult to understand the so-called direct reason [24,28] due to its high size.

In summary, this exploration of statistics related to decision trees will allow us to better understand the limits of interpretability of these models and highlight the need to develop explanatory mechanisms to make them more understandable and useful in real-world applications.

*Some statistics.* The Table 1 presents some statistics on decision tree models that have been learned on a set of 7 benchmarks using their implementation in [27]. The leftmost column gives the name of the benchmark, $F$ and $I$ respectively provide the number of features and the number of instances of each benchmark in the table. The column $P_x^T$ indicates the average size of the direct reasons.

The Fig. 2 presents histograms representing the size of direct reasons [24] calculated for 250 instances from 4 different benchmarks. It can be observed that, for all benchmarks, the size of the direct reasons exceeds 7 for the majority of instances, making these explanations hard to interpret by the human [20].

By analyzing the sizes of decision trees, it is observed that they are generally large, implying more nodes and learned rules. This increase in tree size can also make their interpretation more complex. Furthermore, the average size of the direct reasons ($P_x^T$) for each benchmark is considerable, exceeding an average of 10.5. This observation highlights the potential difficulty in explaining such large and deep trees. It is noteworthy that this average size significantly exceeds the cognitive limit of 7 [20]. These observations underscore the necessity of enhancing the intelligibility of decision trees with concise and reliable explanations.

To complete the analysis of our statistics, it is evident that due to cognitive limitations, abductive explanations (minimum-size sufficient reasons included) are often too large to be interpretable, even for decision trees (see [24,25]). In such cases, there is a need to reduce the size of abductive explanations while still accurately determining the predicted label with high probability. In the remainder of this article, we will shed light on probabilistic explanations.

## 3. Probabilistic explanations

The concept of sufficient reason is often considered a natural concept for explaining the result of a classifier, but it imposes a strict restriction by requiring that all completions of a partial instance be classified in the same way, and these reasons can also be of large size. To relax this limitation, a probabilistic generalization of explanations has been proposed by [21].

Now, given a classifier $C$ and an instance $x$ for which the prediction $C(x)$ must be explained, we define the concept of a $\delta$-probable reason.

**Definition 4 (δ-probable Reason).** Let $\delta \in (0,1]$, a $\delta$-probable reason for $x$ given a Boolean function $f \in F_n$ such that $f(x) = 1$ is a set $S$ of features where $t_S$ is a partial term $t_S \subseteq t_x$, and:

$$ \mathbb{P}_{[f(z)=f(x)|t_S \subseteq t_z]} = \frac{|\{z \in \{0,1\}^n : f(z) = f(x), z_S = x_S\}|}{2^{|S|}} = \frac{h(S)}{2^{|S|}} \ge \delta \quad (2) $$
<figure><img src="image_4.png" /><figcaption>Fig. 2. Histogram of the sizes of direct reasons for 4 benchmarks.</figcaption></figure>

If $f$ is represented by a decision tree $T$, Eq. (2) can be rewritten as:

$$ \frac{w(\phi | t_S)}{2^{|S|_{\perp}}} \ge \delta \qquad (3) $$

$\phi = \text{DNF}(T)$ and $t_S = \bigcup_{i=1}^n \{x_i : (x_S)_i = 1\} \cup \{\bar{x}_i : (x_S)_i = 0\}, |S|_{\perp} = n - |S|$, and $h_x(S) = w(\phi | t_S)$ is the number of models of the formula $\phi | t_S$.

**Proposition 2.** Given a decision tree $T \in \mathcal{DT}_n$, an instance $x \in \{0, 1\}^n$, and a set $S$ of features, evaluating $w(\text{DNF}(T) | t_S)$ can be done in $O(|S| \cdot |T|)$ time.

**Algorithm 1 Compute $w(\text{DNF}(T) | t_S)$**

**Input:** Decision tree $T$, instance $x \in \{0, 1\}^n$, set of literals $S$

**Output:** Number of models of $\text{DNF}(T) | t_S$

$w \leftarrow 0$ {Initialize the number of models}

**for** each term $t_{\text{dnf}}$ in $\text{DNF}(T)$ **do**

if no literal in $t_S$ has its negation in $t_{\text{dnf}}$ **then**

$$ C \leftarrow t_{\text{dnf}} \cup t_S $$

$$ w \leftarrow w + 2^{(n-|C|)} \text{ {Exploiting the orthogonality for counting.}} $$

end if

end for

return $w$

Algorithm 1 illustrates how to count the number of models of the formula $\text{DNF}(T) | t_S$ in linear time, taking into account the orthogonality of this formula.
<figure><img src="image_5.png" /><figcaption>Fig. 3. A decision tree *T* to predict the long-term success of a product on an online market (failure: 0, moderate success: 1, great success: 2).</figcaption></figure>

**Remark 4.** In the case of **multi-class classification**, the results of **Proposition 2** remain valid, and the evaluation of the function $h_x(S)$ can be done in linear time. We would like to point out that our results, unlike those presented in [23], are adapted to the case of multi-class classification for decision trees. Indeed, in the authors of [23] studied only the case of binary classification.

3.1. *Connection between the user and probabilistic explanations*

The connection between the user and the provided explanations is at the heart of **XAI** issues. When a user interacts with a classification model, it is crucial to find a subset of features that maximizes confidence in the probabilistic explanation while relying on a subset of inputs provided by the user [29]. This process highlights the user's prior knowledge and, more importantly, the complex relationship between the user, the model's performance, and the reliability of probabilistic explanations.

**Problem 1.** Given a decision tree $T \in \mathcal{DT}_n$, an instance $x \in \{0, 1\}^n$, a set $E$ of features (given by a user), a size limit $k \le |E|$, one can express the connection between the user's prior knowledge and probabilistic explanations by searching for the subset $S \subseteq E$ of size at most $k$ such that $h_x(S)$ is maximized.

**Problem 1** formalizes how to establish a connection between the user's knowledge and the provided probabilistic explanations, by identifying a subset of input features deemed by the user as most useful for explaining the decision made by the classifier. The primary objective of this process is to improve the reliability of the probabilistic explanations we offer to the user. It's important to highlight that **Problem 1** has been proven to be NP-hard in [23]. In Section 4, we present a greedy algorithm designed to find approximate solutions.

**Example 4.** Consider the tree in Fig. 3 predicts long-term success using the following variables: $x_1$: Number of views per month greater than $10^6$, $x_2$: Number of comments greater than $10^5$, $x_3$: Price (Cheap or Not cheap), and $x_4$: Brand Type (public or luxury).

Let the instances $\mathbf{x} = (1, 1, 1, 1)$ and $\mathbf{x}' = (0, 0, 1, 1)$ where ($T(\mathbf{x}) = 1$ and $T(\mathbf{x}') = 0$). The direct reason for $\mathbf{x}$ given $T$ is the term $P_{\mathbf{x}}^T = \{x_1, x_2, x_3, x_4\}$, which coincides with the term $t_{\mathbf{x}}$. In contrast, the direct reason for $\mathbf{x}'$ given $T$ is the term $P_{\mathbf{x}'}^T = \{\bar{x}_1, \bar{x}_2\}$, which does not coincide with $t_{\mathbf{x}'}$.

The sets $\{x_1, x_4\}$ and $\{x_2, x_3, x_4\}$ are sufficient reasons for $\mathbf{x}$ given $T$. The set $\{x_1, x_4\}$ is the unique minimum-size sufficient reason for $\mathbf{x}$ given $T$. The set $\{\bar{x}_1, \bar{x}_2\}$ is the unique sufficient reason for $\mathbf{x}'$ given $T$.

We now focus on probabilistic explanations. Let's take, for example, the instance $\mathbf{x} = (1, 1, 1, 1)$ and the sufficient reason $\{x_2, x_3, x_4\}$ for $\mathbf{x}$ given $T$. We have: $\frac{h(\{x_2\})}{2^4-1} = \frac{3}{8}$, $\frac{h(\{x_3\})}{2^4-1} = \frac{3}{8}$, $\frac{h(\{x_4\})}{4-1} = \frac{5}{8}$, $\frac{h(\{x_2,x_3\})}{2^4-2} = \frac{1}{2}$, $\frac{h(\{x_2,x_4\})}{2^4-2} = \frac{3}{4}$, $\frac{h(\{x_3,x_4\})}{2^4-2} = \frac{3}{4}$.

We observe that $\{x_4\}$ is a 0.5-probable reason for the instance $\mathbf{x}$ given $\bar{T}$. The sets $\{x_3, x_4\}$ and $\{x_2, \bar{x}_4\}$ are 0.75-probable reasons for $\mathbf{x}$ given $T$.
## 4. Greedy algorithms

After providing an overview of probabilistic explanations, we now briefly recall the complexity of computing them.

The decision problem verifying whether $x$ admits a $\delta$-probable reason of certain size $k$ for a Boolean function $f$, where $f$ is presented by a CNF formula, is NP$^{PP}$-complete [30], and NP-hard when $f$ is a decision tree [22]. The authors of [23] also showed that Problem 1 remains NP-hard for decision trees. A SAT encoding was proposed by [22] to derive a $\delta$-probable reason for $x$ given $T$. This encoding can also be extended to derive an exact solution of Problem 1 using binary search. However, the time required to obtain results using this method is high in many cases, as pointed out in [23].

Indeed, when the size of the tree $|T|$ is large or the dimension $n$ of the input instance $x$ is very large, the encoding proposed by [22] explodes, preventing us from obtaining results in a reasonable time [31,32]. We now present a greedy algorithm for Problem 1 and a greedy algorithm for deriving a $\delta$-probable explanation.

### 4.1. Greedy algorithm

In the following, we use the greedy algorithm 2 to derive a set $S$ based on an features set $E \subseteq t_x$ of exactly size $k \le |E|$ (or at most size $k$) and a confidence parameter $\delta \in (0, 1]$ to determine. For a decision tree $T \in \mathcal{DT}_n$, let $\phi = \text{DNF}(T)$. We exploit the fact that this DNF is orthogonal [24,33] to perform calculations in the most cost-effective way possible. The orthogonality of $\phi$ allows us to count the models of $T$ in linear time, and thus evaluate the function $h_x(S)$ in linear time as well. Consequently, checking the inequality $\frac{w(\phi|t_x)}{2^{n-|S|}} \ge \delta$ can be done in linear time. We now explicitly detail our greedy algorithm.

**Algorithm 2**

**Input:** A tree $T$, a set $E \subseteq t_x$, and $k \le |E|$

**Output:** A $\delta^*$-probable reason

$$S \leftarrow \emptyset$$

$$\phi \leftarrow \text{DNF}(T)$$

$$E \leftarrow t_x \{E \text{ can be the instance } t_x \text{ or the direct reason } p_x^T, \text{ or a subset } E \subseteq t_x\}$$

**for** $l \in \{1, \dots, k\}$ **do**

$$e^* \leftarrow \operatorname*{argmax}_{c \in E} h(S \cup \{c\})$$

$$S \leftarrow S \cup \{e^*\}$$

$$E \leftarrow E - \{e^*\}$$

**end for**

$$\delta^* \leftarrow \frac{w(\phi \wedge t_S)}{2^{n-k}}$$

**return** $S$, $\delta^*$

Algorithm 2 is an adapted version of the GA algorithm proposed in [23]. This algorithm aims to find a probabilistic explanation of size $k$ (or at most $k$) that minimizes the classification error (maximizes the value of $\delta$) [23].

**Proposition 3.** Let a decision tree $T \in \mathcal{DT}_n$ and an instance $x$, Algorithm 2 runs in time $O(k \cdot n^2 |T|)$.

**Example 5.** Let us illustrate Algorithm 2 on our running example focusing on the tree $T$ in Fig. 3 and instance $x = (1, 1, 1, 1)$ where $T(x) = 1$.

We are looking for a probabilistic explanation that maximizes the associated confidence parameter $\delta$ and has an exact size of $k = 2$.

The steps of Algorithm 2: We initialize the set $S \leftarrow \emptyset$. The subsequent steps involve selecting the elements one by one. $x_4 = \operatorname*{argmax}_{e \in \{e_1, x_2, x_3, x_4\}} h(e)$, then $S \leftarrow \{x_4\}$ and $x_1 = \operatorname*{argmax}_{e \in \{e_1, x_2, x_3\}} h(e)$, $x_2 = \operatorname*{argmax}_{e \in \{e_1, x_2, x_3\}} h(e)$, and $x_3 = \operatorname*{argmax}_{e \in \{e_1, x_2, x_3\}} h(e)$. We obtain $S \leftarrow \{x_1, x_4\}$ and $\delta^* \leftarrow h_x(S) = \frac{w(\phi \wedge t_S)}{2^{4-|S|}} = 1$.

Algorithm 2 has captured the unique minimum-size sufficient reason, which means that $\delta^* = 1$ (the optimal value).

### 4.2. Deriving a $\delta$-probable reason

Finally, and given that Algorithm 2 has the advantage of executing in linear time. Moreover, it is effective in most practical cases for capturing the most reliable probabilistic explanation possible, with a parameter $\delta$ reaching its maximum or being close to it. This efficiency and reliability make this algorithm a valuable tool for rapid and accurate generation of probabilistic explanations in various application contexts. Now, we will make some modifications to Algorithm 2 in order to derive a probabilistic explanation for the instance $x$ given $T$ and a confidence parameter $\delta$ that lies in the interval $(0, 1]$. It is also possible to compute a specific probabilistic explanation based on a subset of literals $E \subseteq t_x$. To do this, we adapt the input of Algorithm 3 using a subset $E$ of our choice as the input.
**Algorithm 3 Derivation of a δ-probable reason**

**Input:** A decision tree $T$, $\delta \in (0, 1]$, an instance $t_x$

**Output:** A δ-probable reason

$$ \phi \leftarrow \text{DNF}(T) $$

$$ S \leftarrow \emptyset $$

$$ E \leftarrow t_x $$

**for** $l \in \{1, ..., n\}$ **do**

$$ e^* \leftarrow \underset{c \in E}{\operatorname{argmax}} h(S \cup \{c\}) $$

$$ S \leftarrow S \cup \{e^*\} $$

**if** $\frac{h_x(S)}{2^{n-l}} \ge \delta$ **then**

**break**

**return** $S$

**end if**

$$ E \leftarrow E - \{e^*\} $$

**end for**

**return** $S$

*Comments on Algorithm 3.* Algorithm 3 is a very effective heuristic. Its advantage lies in its ability to provide the most reliable and concise probabilistic explanation possible (as demonstrated by the experiments in Section 5). It is well known that there may exist other probabilistic explanations for the same instance $x$, depending on a parameter $\delta$. Compared to a naive iterative algorithm for deriving a probabilistic explanation, which would start with the complete instance, arbitrarily eliminate a literal at each iteration of the main loop, and test whether the resulting subset constitutes a probabilistic explanation, such a naive algorithm risks increasing the probability of reaching a poor local optimum. In contrast, Algorithm 3 selects a local optimum at each iteration of the main loop, as indicated by our experiments in Section 5. All of this helps the algorithm perform better, making it an effective and reliable alternative for obtaining a concise and robust probabilistic explanation.

# 5. Experiments

This section is divided into two parts. The first part is dedicated to various experiments, mainly aimed at evaluating the empirical performance of our algorithms and highlighting the gain in intelligibility. The second part is an application-oriented section, aiming to show that we can use our approach to extract a set of keywords that best explain the classification of emotions in tweets.

## 5.1. Experiments

We conducted several experiments to evaluate the performance of our two algorithms. Our objectives are as follows:

* Measure the exactitude of the results from Algorithm 2 in computing a probable reason of a certain size $k$ and of size at most $k$. In particular, we compared the value of $\delta^*$ associated with the reason found by Algorithm 2 to the optimal value $\delta_{opt}$ obtained through binary search of the SAT encoding [22].

* Evaluate the gain in intelligibility resulting from the emphasis on the size of probabilistic explanations (computed using Algorithm 3) compared to the size of direct ($P_x^T$), sufficient ($SR$), and minimum-size ($MR$) reasons for an instance $x$ given a decision tree $T$. Our discovery indicates that Algorithm 2 is more time-efficient than the SAT method for computing $\delta$-probable reasons and can effectively manage larger-scale problems where the SAT method struggles with computational efficiency.

### 5.1.1. Empirical setting

We considered 33 datasets, which are standard benchmarks from the well-known Kaggle,<fnref n="1" /> OpenML,<fnref n="2" /> and UCI<fnref n="3" /> websites. Notably, mnist38 and mnist49 are subsets of the mnist dataset, containing instances of digits 3 and 8 (respectively, 4 and 9). As some datasets are suitable for multi-label classification, we employed the standard “one versus all” approach to handle them: all classes except the target one are treated as the complementary class to the target. Categorical features were treated as arbitrary numbers (the scale being nominal). For numeric features, no data preprocessing occurred, these features were binarized dynamically by the decision tree learning algorithm used.

For each benchmark $b$. The CART algorithm, specifically its implementation provided by the Scikit-Learn library [27], was used to learn decision trees $T_b$. All hyperparameters of the learning algorithm were set to their default values. Notably, decision trees were learned using the Gini criterion, without any maximum depth or other manual limitations. Classification performances for $T_b$ were measured as the average accuracy achieved on a test set of over 150 instances.

<footnote n="1">¹ www.kaggle.com</footnote>

<footnote n="2">² www.openml.org</footnote>

<footnote n="3">³ https://archive.ics.uci.edu/ml/</footnote>
<caption>**Table 2**</caption>

Statistics of the reliability of probabilistic explanations generated by the algorithm 2 based on different types of input reasons (direct, sufficient, and minimum-size sufficient) with the SAT method, evaluated in terms of size and precision.

<table><thead><tr><th colspan="3">Dataset</th><th colspan="3">Decision tree</th><th colspan="3">[Reason]</th><th colspan="4">|δ<sub>opt</sub> - δ<sup>*</sup><sub>al,go<sub>1</sub></sub>|</th><th colspan="2">SAT</th></tr><tr><th>name</th><th>F</th><th>I</th><th>%A</th><th>|T|</th><th>Depth</th><th>ρ<sub>x</sub><sup>T</sup></th><th>SR</th><th>MR</th><th>k</th><th>t<sub>x</sub></th><th>ρ<sub>x</sub><sup>T</sup></th><th>SR</th><th>Time (s)</th></tr></thead><tbody><tr><td>horse</td><td>29</td><td>299</td><td>84.44</td><td>34</td><td>13</td><td>6.0</td><td>6.6</td><td>5.2</td><td>5</td><td>0.0085</td><td>0.0004</td><td>0.0004</td><td>20.45</td></tr><tr><td>hungarian</td><td>13</td><td>294</td><td>68.54</td><td>62</td><td>12</td><td>6.0</td><td>5.8</td><td>4.9</td><td>5</td><td>0.008</td><td>0.002</td><td>0.002</td><td>5.53</td></tr><tr><td>primary, t</td><td>23</td><td>399</td><td>87.25</td><td>53</td><td>14</td><td>6.0</td><td>7.1</td><td>4.8</td><td>5</td><td>0.0294</td><td>0.0004</td><td>0.0004</td><td>17.25</td></tr><tr><td>mushroom</td><td>17</td><td>8124</td><td>100.0</td><td>20</td><td>7</td><td>5.0</td><td>4.7</td><td>4.4</td><td>5</td><td>0.0002</td><td>0.0002</td><td>0.0002</td><td>2.53</td></tr><tr><td>cars</td><td>21</td><td>406</td><td>97.54</td><td>30</td><td>10</td><td>4.4</td><td>5.5</td><td>4</td><td>4</td><td>0.0506</td><td>0.0026</td><td>0.0026</td><td>9.46</td></tr><tr><td>glass</td><td>31</td><td>214</td><td>83.08</td><td>36</td><td>11</td><td>6.9</td><td>8.4</td><td>6.4</td><td>5</td><td>0.009</td><td>0.0047</td><td>0.0051</td><td>3.82</td></tr><tr><td>placement</td><td>18</td><td>215</td><td>95.38</td><td>19</td><td>10</td><td>4.0</td><td>4.4</td><td>3.2</td><td>3</td><td>0.0001</td><td>0.0001</td><td>0.0001</td><td>0.72</td></tr><tr><td>spect</td><td>19</td><td>265</td><td>78.75</td><td>42</td><td>15</td><td>6.3</td><td>6.3</td><td>4.7</td><td>5</td><td>0.04</td><td>0.002</td><td>0.002</td><td>3.71</td></tr><tr><td>colic</td><td>40</td><td>368</td><td>80.18</td><td>55</td><td>13</td><td>8.0</td><td>10.2</td><td>7.5</td><td>6</td><td>0.0003</td><td>0.0002</td><td>0.0004</td><td>19.23</td></tr><tr><td>biomed</td><td>15</td><td>209</td><td>98.41</td><td>21</td><td>11</td><td>4.6</td><td>4.1</td><td>3.7</td><td>4</td><td>0.0004</td><td>0.0001</td><td>0.0001</td><td>0.67</td></tr><tr><td>student-por</td><td>30</td><td>649</td><td>91.79</td><td>33</td><td>9</td><td>5.0</td><td>6.3</td><td>4.9</td><td>4</td><td>0.0037</td><td>0.0007</td><td>0.0007</td><td>41.67</td></tr><tr><td>tic-tac-toe</td><td>9</td><td>958</td><td>97.92</td><td>83</td><td>9</td><td>5.8</td><td>4.8</td><td>4.4</td><td>4</td><td>0.0062</td><td>0.0005</td><td>0.0001</td><td>1.22</td></tr><tr><td>schizo</td><td>33</td><td>340</td><td>93.14</td><td>34</td><td>11</td><td>5.9</td><td>5.3</td><td>4.7</td><td>5</td><td>0.0019</td><td>0.0002</td><td>0.0002</td><td>4.53</td></tr><tr><td>vehicle</td><td>23</td><td>846</td><td>96.06</td><td>31</td><td>12</td><td>5.7</td><td>6.6</td><td>5.2</td><td>5</td><td>0.0005</td><td>0.0007</td><td>0.0006</td><td>3.34</td></tr><tr><td>balance</td><td>17</td><td>625</td><td>86.7</td><td>77</td><td>12</td><td>5.6</td><td>5.8</td><td>4.7</td><td>5</td><td>0.0048</td><td>0.0005</td><td>0.0005</td><td>13.17</td></tr><tr><td>compas</td><td>40</td><td>6172</td><td>66.14</td><td>570</td><td>20</td><td>11.1</td><td>9.4</td><td>6.6</td><td>7</td><td>0.006</td><td>0.006</td><td>0.006</td><td>1482.32</td></tr><tr><td>employee</td><td>63</td><td>4653</td><td>82.45</td><td>653</td><td>20</td><td>10.4</td><td>12.0</td><td>8.1</td><td>7</td><td>0.13</td><td>0.08</td><td>0.06</td><td>1314.84</td></tr><tr><td>fetal, h</td><td>93</td><td>2127</td><td>93.42</td><td>110</td><td>19</td><td>12.2</td><td>17.3</td><td>10.8</td><td>7</td><td>0.18</td><td>0.12</td><td>0.14</td><td>1125.83</td></tr></tbody></table>

<figure><img src="image_6.png" /><figcaption>**Fig. 4.** Box plots for 4 benchmarks *compas*, *employee*, *bank* and *spambase*, representing the sizes of direct reasons, sufficient reasons, minimum-size sufficient reasons, and {75%, 90%, 95%}-probable reasons.</figcaption></figure>

For each dataset *b*, each decision tree $T_b$, and each instance *x* from the corresponding test set, aiming to test the reliability of our algorithm, we calculated the $\delta^*$ corresponding to a probable reason of size at most *k*. To do this, we started by using the instance $E = t_x$, then the direct reason $E = P_x^T$, and finally a sufficient reason $E = SR(x)$, which we compared to $\delta_{opt}$ (see Table 2). We
specify that the value of *k* in Fig. 4 was chosen in the interval $7 \pm 2$, but in such a way that the value of *k* is always less than the average size of the inputs of Algorithm 2, namely $P_x^T$, $SR$, and $MR$. All these reasons were calculated using the library [34].

To compute a $\delta_{opt}$ corresponding to a probable reason of exact size $k$, we performed a binary search by extending the SAT encoding proposed by [22] to include the CNF encoding of the cardinality constraint $\text{CNF}(\sum_{x_i \in E} x_i = k)$. Regarding the $\delta_{opt}$ corresponding to a probable reason of size at most $k$, the SAT encoding is also extended [22] by adding the clause $C_E = \{x_i : (x_E)_i = 1\} \lor \{\bar{x}_i : (x_E)_i = 0\}$ to the CNF of the original encoding. The binary search was performed with an error precision of $10^{-3}$ and a time limit of 1800 (s) by instance, which amounts to 10 SAT calls. Regarding Table 3, it is noteworthy that the SAT encoding does not scale well due to memory consumption explosion caused by the big number of clauses generated by the SAT encoding, or when the set time limit is exceeded for all instances. Therefore, for comparison (for $k = 7$), we restricted ourselves to the direct reason. For the computation of $\delta_{opt}$, we used an exact algorithm consisting of testing all $\frac{h_x(S)}{2^{n-7}}$ combinations of subsets $S$ of $P_x^T$ of exact size $k = 7$, and taking the maximum value.

In order to assess the **improvement in intelligibility** resulting from the emphasis on the size of probabilistic explanations, we reported the sizes of a direct reason, a sufficient reason for *x* given $T_b$, and a minimum-size sufficient reason for *x* given $T_b$, calculated using the **PyXAI** tool [34]. We then reported the computation times required to find $\delta_{opt}$ using binary search of the SAT encoding. For this, we used the *Pysat* [35] library,<fnref n="4" /> which provides the implementation of the solver *GLUCOSE 4* (we set a time limit of 1800 seconds by instance). And to calculate minimum-size sufficient reasons, we used the *Pysat* library, which allows using the **PARTIAL MAXSAT** solver *RC2*. This solver was run using the parameters corresponding to the “Glucose” configuration.

The experiments were conducted on a computer equipped with an Intel(R) Core(TM) i9-9900 processor, running at 3.10 GHz, and with 64 GiB of memory.

### 5.1.2. Results

The Table 2 presents an excerpt of our results for 18 datasets. The first column gives the name of the dataset *b*. *F* represents the number of binary features, *I* the number of instances, %A the accuracy of tree $T_b$, $|T|$ its size, and *Depth* represents the depth of the tree. The column *|Reason|* indicates the average size of different calculated reasons: $P_x^T$, $SR$, $MR$ respectively represent the size of the direct reason, the size of the sufficient reason, and the size of the minimum-size sufficient reason. $|\delta_{opt} - \delta_{alg01}|$ indicates the average error of $\delta$ corresponding to the reason returned by algorithm 2 for a size at most $k$, starting respectively from the complete instance $t_x$, from the direct reason $P_x^T$, and from the sufficient reason $SR$. **SAT** indicates the average computation times of the dichotomous search starting from the direct reason. The datasets in magenta indicate that the 1800 seconds time limit was reached at least once. We notice that the average error $|\delta_{opt} - \delta_{alg01}|$ is generally of the order of $10^{-3}$, especially when the input to the algorithm is $P_x^T$ and $SR$. However, the accuracy slightly decreases when the input is the complete instance *x*. This shows that our greedy algorithm generally finds a probable reason of size at most $k$, nearly with the highest possible confidence parameter $\delta$. We also note that the error $|\delta_{opt} - \delta_{alg01}|$ is high for datasets where the time limit is exceeded (dataset in magenta). This is because the dichotomous search stopped before reaching a precision of $\epsilon = 10^{-3}$, and consequently, we have no guarantee of accuracy compared to the optimal solution. It is even highly likely that the dichotomous search returned a solution far from the optimal one, which explains the high error difference. To improve the intelligibility of our explanations, we calculated, using Algorithm 3 (Fig. 4), $\delta$-probable reasons for $\delta = 0.75$, $\delta = 0.9$, and $\delta = 0.95$. Our results show that probabilistic explanations are generally more concise than abductive explanations, including those of minimum-size (“minimum-size sufficient reasons”).

Regarding the computation time required by the dichotomous search of the SAT encoding, we noticed that this time was very high, reaching up to 25 minutes in some cases, especially when the size of the tree $|T|$ is large (as in the case of “Compas” and “Employee”) or when the number of binary features is high (as in the case of “Fetal. h”). We did not include the computation times of our greedy algorithm, as the average time per instance required for all our experiments does not exceed 0.5 s, demonstrating the computational efficiency of our algorithm compared to the SAT encoding. It is interesting to note that probable reasons of a certain size *k* (or at most *k*) offer users the possibility to control the size of the explanation based on a subset of variables of their choice. It is also essential to emphasize that these reasons are much more relevant to the user than a randomly selected reason.

The results of our experiments in Table 3 highlight the difficulty of computing probabilistic reasons using the SAT encoding, with the 1800-second time limit consistently reached. We included datasets of large dimensions, for which the SAT encoding fails to scale. We used the direct reason $P_x^T$ as input to algorithm 2 and set the output size to $k = 7$. We notice that algorithm 2 is very efficient on these datasets of large dimensions, and the error does not exceed the order of $10^{-3}$. This confirms the reliability of our results, as presented in Table 2. It is also worth noting that this gives an advantage to our approach, especially when the SAT encoding fails to scale.

To illustrate the **gain in intelligibility** achieved when transitioning from abductive explanations (direct reasons and sufficient reasons) to probabilistic reasons ($\delta$-probable reasons) for 150 instances, we created several box plots for two datasets: *compas* (on the right), which illustrates the transition from direct reasons to {75%, 90%, 95%}-probable reasons, and *spambase* (on the left), which illustrates the transition from sufficient reasons to {75%, 90%, 95%}-probable reasons. Fig. 4 presents these box plots. We can observe a significant reduction in the number of features used in direct reasons during the transition to a 0.75-probable reason, as well as for sufficient reasons. For example, for the *compas* benchmark, we can clearly observe a significant reduction in the average sizes of direct reasons and sufficient reasons, and even minimum-size sufficient reasons, compared to the 0.75-probable reasons (see Fig. 5).

<footnote n="4">⁴ https://pysathq.github.io/</footnote>
<caption>**Table 3**</caption>

Table of results for 15 datasets: number of instances *I*, number of binary features *F*, accuracy %A, and average error of |δ<sub>opt</sub> - δ<sup>*</sup>| for *k* = 7.

<table><thead><tr><th>Dataset</th><th>I</th><th>F</th><th>%A</th><th>|δ<sub>opt</sub> - δ<sup>*</sup>|</th><th>|P<sub>i</sub><sup>T</sup>|</th></tr></thead><tbody><tr><td>Gisette</td><td>5000</td><td>7000</td><td>98.56</td><td>0</td><td>21.42</td></tr><tr><td>Mnist38</td><td>13 966</td><td>784</td><td>95.44</td><td>0.0003</td><td>17.89</td></tr><tr><td>Mnist49</td><td>13 782</td><td>784</td><td>95.48</td><td>0</td><td>15.57</td></tr><tr><td>Christine</td><td>1636</td><td>5418</td><td>61.25</td><td>0.001</td><td>9.47</td></tr><tr><td>Bank</td><td>41 188</td><td>882</td><td>89.49</td><td>0.0003</td><td>13</td></tr><tr><td>Dexter</td><td>20 000</td><td>600</td><td>90.70</td><td>0</td><td>8.32</td></tr><tr><td>Gina-agnostic</td><td>970</td><td>48 842</td><td>85.84</td><td>0.0001</td><td>9.84</td></tr><tr><td>Gina</td><td>970</td><td>3468</td><td>84.53</td><td>0.0001</td><td>9.69</td></tr><tr><td>Farm-ads</td><td>54 877</td><td>1543</td><td>86.8</td><td>0.0003</td><td>23.15</td></tr><tr><td>Cnae</td><td>1080</td><td>856</td><td>92.59</td><td>0.0006</td><td>19.07</td></tr><tr><td>Dorothea</td><td>1150</td><td>10<sup>5</sup></td><td>91.8</td><td>0</td><td>12.9</td></tr><tr><td>Adult</td><td>48 842</td><td>2974</td><td>81.16</td><td>0.001</td><td>16.43</td></tr><tr><td>Spambase</td><td>4601</td><td>236</td><td>92.11</td><td>0.0002</td><td>16.09</td></tr><tr><td>Ad-data</td><td>5000</td><td>1023</td><td>99.19</td><td>0</td><td>9.29</td></tr><tr><td>Madelon</td><td>2000</td><td>8.33</td><td>71.03</td><td>0.001</td><td>9.29</td></tr></tbody></table>

<figure><img src="image_7.png" /><figcaption>**Fig. 5.** Variation in the average size of δ-probable reasons when δ varies from 0.5 to 1 (sufficient reasons) for the datasets *mnist38*, *mnist49* and *gina*.</figcaption></figure>

Finally, since the reduction in the size of reasons obtained by considering 75%-probable reasons compared to direct reasons and sufficient reasons seemed significant, we also conducted additional experiments to gain a clearer view of the reduction that can be achieved with variations in δ Fig. 5. We calculated the sizes of δ-probable reasons for instances as δ varies from 0.5 to 1. The figure presents such plots for the datasets *mnist38*, *mnist49* and *gina*. As expected, we can observe that the average size of δ-probable reasons gradually increases as δ increases and stabilizes when the algorithm captures a sufficient reason. This clearly demonstrates the gain in intelligibility obtained.

## 5.2. Application for sentiment analysis of text data (keyword extraction from tweets)

**Motivation.** We decided to apply our approach to sentiment analysis because of the rapid increase in interactions on online platforms like social networks. These platforms generate vast volumes of sentiment-rich data from tweets, statuses, comments, and reviews. Companies use this data to understand consumer needs, while users increasingly rely on user-generated content for their purchasing decisions. Various techniques are used to extract and classify users' attitudes, opinions, and emotions on different topics.

Sentiment analysis is a prevalent text classification tool that discerns whether a message is positive, negative, or neutral. Understanding customer emotions is pivotal for businesses, as customers are expressing their thoughts more openly than ever. Technology now enables the automation of customer feedback analysis, from surveys to conversations on social media, empowering brands to tailor their products and services to customer needs.

**Context.** With all the tweets circulating every second, it's challenging to predict whether the sentiment behind a specific tweet will impact a business or an individual's brand, potentially going viral (positive) or harming profits by conveying a negative tone. Capturing sentiment in language is crucial in an era where decisions and reactions are made and updated within seconds. But which words actually lead to describing the sentiment? In this application, we will select the part of the tweet (word or phrase) that reflects
the sentiment. This application is inspired by a Kaggle competition offered in 2020.<fnref n="5" /> The goal of this competition is to **build a model that examines the labeled sentiment for a given tweet and determine which word or phrase best supports it.**

### 5.2.1. Proposed approach

Initially, we acquire the dataset and partition it into training and test datasets. We use a decision tree to classify the tweets, and then we employ algorithm 3 to find a subset of words. Tweets can be filled with slang words and spelling mistakes. Thus, we need to perform a sentence-level analysis for all these tweets. This is done in multiple phases. In the first phase, preprocessing is performed, mainly to eliminate slang words, stop words, spelling mistakes, and other defects. In the second phase, we create a word dictionary to encode the texts into numerical form. Finally, after using the decision tree to classify the tweets, we identify the set of words that best support the sentiment by using the algorithm 3.

**Acquisition of the dataset.** We use the **Tweet Sentiment Extraction** dataset [36] proposed in a Kaggle competition that took place in 2020. The **Tweet Sentiment Extraction** dataset consists of a total of 27480 tweets. Each tweet is represented by three columns: the first column contains the tweet text (**text**), the second column is labeled **selected text** and contains the set of words (**text**) that supports the sentiment expressed in the tweet, while the third column (**sentiment**) indicates the overall sentiment of the tweet (positive, negative, neutral).

**Disclaimer.** As stated by the authors of this competition, this dataset contains text that may be considered profane, vulgar, or offensive.

**Preprocessing of tweets.** Keyword extraction is challenging on Twitter due to spelling mistakes and slang words. To mitigate this, a preprocessing step is performed before feature extraction. Preprocessing steps include removing URLs, handling spelling mistakes, abbreviations, and slang words. Spelling mistakes are corrected and abbreviations are replaced with their full meaning using the NLTK package.<fnref n="6" /> Slang words significantly contribute to the emotion of a tweet. Therefore, they cannot simply be removed. A slang word dictionary is maintained to replace the slang words present in the tweets with their associated meanings. Domain knowledge largely contributes to the formation of the slang word dictionary.

**Example 6.** In this example, we present a preprocessing example to better illustrate it. We provide here three tweets extracted from the dataset used:

tweet 1: I am sooo tired

tweet 2: SEe waT I Mean B0uT FoLL0w fRiiDaYs... It'S cALLed LoSe f0LloWeRs FridAy

tweet 3: Gonna read a stry bout Adam Lambert online then head to bed. Goodnight!

Now, the sentences after preprocessing using the NLTK package:

tweet1: I am so tired

tweet2: See what I mean about Follow Fridays. It's called Lose Followers Friday

tweet3: Gonna read a story about Adam Lambert online then bed. nighty night

This preprocessing is important. For example, in the third sentence, we notice that the word **stry** should mean **story**. Correcting this spelling mistake is important for the model to detect the existence of the word **story**, which gives meaning to the sentence.

**Creating of $\mathcal{L}$**. Feature extraction occurs in two steps. In the first step, Twitter-specific features are extracted. Hashtags and emojis are relevant Twitter-specific features. Emojis can be positive, negative, or even neutral. Then, each tweet is treated as plain text. Subsequently, using the unigram approach, tweets are represented as a collection of words. In unigrams, a dictionary of dimension $n$ (a fixed number of words) is created, containing all the words present in the tweet after preprocessing and cleaning. This set of words is denoted as the initial vocabulary $\mathcal{X}$.

Our goal now is to project the input text into a numerical space denoted $\mathcal{L}$, aiming to construct a space where each tweet is represented by a vector to encode all available information. Additionally, the $\mathcal{L}$ is generally of lower dimensionality than the majority of input texts. To construct $\mathcal{L}$, we draw inspiration from the article [37].

The following steps were taken to derive $\mathcal{L}$:

* Initially, retain a number of $k$-words (initially 3000 words) that are the most frequent in the dictionary and are included in the set of tweets.

* Analyze $N$-grams (2-grams or 3-grams, 4-grams, 5-grams) and add words related to the most frequent $N$-grams.

* Remove single digits, as they generally do not reflect emotion.

* Add hashtags and emojis, and rare words (a number $j$ of rare words to enrich the space $\mathcal{L}$) found in the tweets.

<footnote n="5">⁵ https://www.kaggle.com/competitions/tweet-sentiment-extraction/overview</footnote>

<footnote n="6">⁶ https://www.nltk.org/</footnote>
<figure><img src="image_8.png" /><figcaption>Fig. 6. An example of a decision tree for classifying tweets.</figcaption></figure>

**Text Encoding.** In this final step, we build the database that represents the tweets, where each word in the tweet is assigned a 1 if it appears in the space $\mathcal{L}$ and 0 otherwise (One-hot encoding). Thus, a tweet is represented by a vector of dimension $p$, where the columns indicate the words and the rows the encoding of the tweets into a numerical vector.

**Example 7.** In this example, we provide a simple illustration of how we encode our tweets into numerical vectors.

tweet1 : εI love catε

tweet2 : εI hate when the cat sat in the hate

tweet3 : εThe cat with the hate

**document** : ["I love cat", "I hate when the cat sat in the hat", "The cat with the hat"]

Here, our dictionary is defined as $\mathcal{X}$ = {the, love, hate, cat, sat, when, in, hat, with} and our space is defined as $\mathcal{L}$ = {love, cat, sat, hate, hat, with}.

<table><thead><tr><th>Tweets/ℓ</th><th>love</th><th>cat</th><th>sat</th><th>hate</th><th>hat</th><th>with</th></tr></thead><tbody><tr><td>tweet 1</td><td>1</td><td>1</td><td>1</td><td>0</td><td>0</td><td>0</td></tr><tr><td>tweet 2</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>0</td></tr><tr><td>tweet 3</td><td>1</td><td>1</td><td>0</td><td>0</td><td>1</td><td>1</td></tr></tbody></table>

*Sentiment analysis and extraction of keywords supporting the sentiment.* After creating $\mathcal{L}$ and encoding the tweets, sentiment classification is performed using a decision tree. Subsequently, we use algorithm 3 to find the set of keywords supporting the associated sentiment.

**Example 8.** Let's consider the tree *T* in Fig. 6 and the tweet "I hate when the cat sat in the hat". Fig. 6 clearly shows that the tweet reflects a negative emotion.

We are looking for the set of words that support the negative sentiment predicted by *T*. To do this, we provide the set of words. Of course, the tree may use words that do not appear in the tweet given the space $\mathcal{L}$, but our idea is to focus only on those in the original tweet. In this example, we consider the input to algorithm 3 as $S$ = {cat, hate, sat} (the words appearing in the path leading to the solution) and we set $k$ = 2.

Algorithm 3 returns the following set of words $S^* = \{\text{hate, cat}\}$.

**Evaluation.** To assess the effectiveness of our approach, we start by evaluating the performance in terms of classification to identify the correct sentiments reflected by the tweets. Then, to evaluate the relevance of our approach, we use the same evaluation proposed in the following Kaggle competition: .
<table><caption>**Table 4**
Excerpt of the results obtained for a set of 6 tweets.</caption><thead><tr><th>Tweet</th><th>Sentiment</th><th>k</th><th>Selected words</th></tr></thead><tbody><tr><td>my boss is bullying me...</td><td>negative</td><td>2</td><td>bullying me</td></tr><tr><td>Sooo SAD I will miss you here in San Diego</td><td>negative</td><td>2</td><td>Sooo SAD</td></tr><tr><td>my boss. She's moving to NYC</td><td>neutral</td><td>7</td><td>my boss. She's moving to NYC</td></tr><tr><td>Both of you</td><td>neutral</td><td>3</td><td>Both of you</td></tr><tr><td>thanks, none close to me.</td><td>positive</td><td>1</td><td>thanks</td></tr><tr><td>Congrats on the knottie man!</td><td>positive</td><td>1</td><td>Congrats</td></tr></tbody></table>

The metric for this competition is **the word-level Jaccard similarity score**. The formula for the overall metric is as follows:

$$ score = \frac{1}{n} \sum_{i=1}^{n} jaccard(gt_i, dt_i) $$

where:

* n = number of tweets

* jaccard = Jaccard similarity score

* gtᵢ = the ith set of words from the test set

* dtᵢ = the ith set of words found by the algorithm 3

### 5.2.2. Empirical setting

We used, as specified, the dataset provided in the Kaggle competition **Tweet Sentiment Extraction**. We performed preprocessing<fnref n="7" /> of the tweets as explained in Section 5.2.1. We specify that the same preprocessing was performed for the target word set (the selected text column). We then assigned a sentiment to each individual tweet. At the tweet level, it is categorized as positive, negative, or neutral. To do this, we use a decision tree *T*.

The CART algorithm, specifically its implementation via the Scikit-Learn library, was used for learning the decision tree *T*. Hyperparameters were optimized by searching for the best parameters using the **GridSearchCV** function from the Scikit-Learn package, with cv = 10 fixed. The tree *T* learns to classify tweets on a training portion of our input database representing 70% of the input instances. The training and testing portions are uniformly and randomly selected.

The performance of tree *T* was calculated using the classic precision measure, which is the number of correct predictions compared to the number of instances in the test set. The test set represents 30% of the input data set. Algorithm 2 was used to derive a set of words that support the sentiment predicted by the tree. To focus solely on extracting words that support tweets, this experimental protocol avoids searching for the correct number of words *k* that support the prediction made by tree *T*. We assume that *k* is known (the number of words present in each row of the selected text column). Just like in the competition, the **Jaccard similarity score at the word level** was used to measure the effectiveness of the results obtained and compare them to the competition results.

The experiments<fnref n="8" /> were also conducted on a computer equipped with an Intel(R) Core(TM) i9-9900 processor, 3.10 GHz, and 64 GiB of memory.

### 5.2.3. Results

The distribution of tweet sentiments in the dataset is illustrated as follows: neutral (11117 tweets), positive (8582 tweets), and negative (7781 tweets). We observe that the distribution of tweets is fairly balanced: the number of neutral tweets is slightly higher at 40.45% compared to the positive tweets at 31.23% and the negative tweets at 28.32%. The counts of negative and positive tweets are relatively close.

Our experimental results show that the decision tree *T* generally manages to classify tweets well, with an accuracy of 72.73% on the test set. The overall computation time (including preprocessing) to find the words supporting the tweet sentiment does not exceed 10 minutes, which is well below the time limit set by the competition (3 hours). The **Jaccard** score is equal to 0.71754. This **Jaccard** score ranks us between the 100th and 110th positions, which means among the top 5%.

The Table 5 shows the Jaccard score and the mean error ($|\delta_{opt}(S) - \delta^*(S)|$) made by algorithm 2 for tweets correctly classified as neutral, positive, or negative. Unsurprisingly, the mean error $|\delta_{opt}(S) - \delta^*(S)|$ is very close to zero, reaching even an order of magnitude of $10^{-4}$. Regarding the Jaccard score, it can be noticed that the Jaccard score is lower for positive sentiments than for negative ones. Table 4 shows an excerpt of the results obtained for 6 tweets that are correctly classified by the tree *T*. The columns of the table are defined as follows: **Tweet** represents the tweet to be processed, **Sentiment** indicates the sentiment of the tweet, *k* is the number of words supporting the tweet, and **Selected Words** are the selected words supporting the sentiment of the tweet. For example, for the tweet **my boss is bullying me...**, with *k* = 2, algorithm 2 returns bullying me, these words indeed support the negative sentiment predicted by the tree. Whereas for the tweet **im an avid fan of **** magazine and i love your magazines**,

<footnote n="7">⁷ For more details on preprocessing tweets, we invite the reader to read the article [37] and to consult the Kaggle competition website</footnote>

<footnote n="8">⁸ The code will be available on GitHub https://github.com/Lounesbo once the article is accepted and published.</footnote>
<table><caption>**Table 5**
Results obtained based on the types of tweet sentiments.</caption><thead><tr><td>Sentiment</td><td>Jaccard</td><td>|δ<sub>opt</sub>(S) - δ<sup>*</sup>(S)|</td></tr></thead><tbody><tr><td>Positive</td><td>0.511</td><td>0.0003</td></tr><tr><td>Negative</td><td>0.619</td><td>0.00007</td></tr></tbody></table>

with $k = 3$, our algorithm returns an avid fan, while the correct answer is avid fan of. However, it can still be said that the words returned by our method indeed support the positive sentiment of the tweets. Hence the difficulty of the competition in finding the right words set by the organizers.

**Remark 5.** The Jaccard score for neutral tweets is exceptionally high, nearing its maximum value, as all words in these tweets reinforce their neutrality. Consequently, the entire set of words is selected to reflect this neutrality.<fnref n="9" /> That's why we have only presented the results for tweets with negative and positive sentiments in Table 5.

It is true that in the context of the competition, we do not know the number of words that will be found and that will support the tweet (i.e., $k$). The task of finding the perfect set of words that support the sentiment of the tweet remains possible without prior knowledge of $k$, but it requires extensive pre-processing of the data. However, the objective of this section is simply to demonstrate that our approach can be effectively applied to the extraction of key words in tweets. Nonetheless, our results demonstrate the effectiveness of our approach for several reasons. First, the decision tree offers high accuracy while remaining interpretable. Second, the computation time required for extracting the words supporting the sentiments is very short. Finally, the high Jaccard score indicates that our method consistently and reliably identifies the key words that reflect the sentiments of the tweets, thereby contributing to more accurate and explainable sentiment analyses.

## 6. Discussion and related work

The problem of searching for abductive explanations has prompted numerous studies, recently summarized in [8]. However, due to cognitive limitations, one of the major weaknesses of abductive explanations is their potentially uncontrollable size. To overcome this obstacle, a common approach is to seek minimal-sized abductive explanations. However, the corresponding optimization problem is NP-hard for decision trees [22], and $\Sigma_2^P$-hard in general [21]. Even if the shortest abductive explanations could be found in a reasonable amount of time, their size could still remain excessive.

Probabilistic explanations, which offer a natural compromise between conciseness and precision, have been the subject of increasing interest over the past three years [21–23,38–41]. The search for such explanations is NP$^{PP}$-hard, and NP-hard for decision trees. In the study by [23], it has been demonstrated that this problem remains NP-hard for decision trees, even assuming that $S$ is a subset of a given abductive explanation $I$. Heuristic approaches for probabilistic explanations have been explored in [39,41]. The optimization task is symmetric to that of Problem 1: given a decision tree $T$, an instance $x$, a feature set $I$, and an error parameter $\epsilon$, the objective is to find a $(1 - \epsilon)$-probable explanation $S \subseteq I$ that minimizes $|S|$. For this problem, the authors proposed a greedy algorithm that runs in polynomial time when $I$ is a path-based explanation for $x$ and $T$. However, this algorithm does not provide any approximation guarantees regarding the optimal solution size. The authors of [38] proposed a method to find $|S|$ that maximizes a sufficiency probability $P(\cdot | z)$ by choosing $z$, but, like the previous approaches, the algorithm used does not guarantee an approximate bound.

To our knowledge, approximation methods for probabilistic explanations have only been explored in [23,40]. In [40], the problem is to find a $(1 - \epsilon)$-probable explanation $S$ that minimizes $|S|$. The authors proposed a PAC (Probably Approximately Correct) style algorithm that runs in polynomial time, taking as input a classifier $h$, an instance $x$, a confidence parameter $\delta$, and a precision parameter $\epsilon$, and producing a set $S \subseteq [n]$ with probabilistic guarantees based on the distribution used to randomly draw $x$ from $\{0, 1\}^n$. However, this algorithm is primarily of theoretical interest, as $|S|$ is on the order of $O\left(\left(\frac{1}{\delta}\right)^9 \cdot \left(\frac{1}{\epsilon}\right)^{12}\right)$, which is often too large for practical applications. Thus, the added value of the work in [23] lies in the approximation guarantees provided, allowing for the minimization of the explanation error caused by selecting a minimal subset $S$, with size guarantees relative to the optimal set. This justifies our choice to draw inspiration from the work of [23] to derive reliable and concise probabilistic explanations, thereby improving the intelligibility of decision trees.

## 7. Conclusion

In this paper, we have leveraged recent work on the approximation of probabilistic explanations to improve intelligibility, particularly in the context of decision trees. By nature, probabilistic explanations cannot be larger than sufficient reasons, but they prove to be valuable concepts for obtaining more understandable explanations for human users. All these reasons are smaller

<footnote n="9">⁹ All the teams in the Kaggle competition exploited this fact to increase their scores and refine their models by focusing solely on positive and negative sentiments.</footnote>
than the instances themselves. Although the minimal-sized sufficient reasons are the shortest possible abductive explanations, our experiments have shown that further size reduction can be achieved with δ-probable reasons. Moreover, we find that our greedy algorithm allows for deriving reliable and concise probable reasons with a remarkably low computational cost compared to the SAT method. We can assert that deriving reliable probable reasons is significantly simplified using our greedy algorithm, making the gain in intelligibility they provide almost free. We have also observed that our approach can be used in a sentiment analysis context. It can constitute a highly effective alternative method for extracting a set of words that support the sentiment expressed by a tweet. In our future work, we first plan to identify approximation bounds in the case of multi-class classification and to extend our study to other types of classifiers considered more challenging to explain, such as random forests, boosted trees, and ensemble-based classifiers.

## CRediT authorship contribution statement

Louenas Bounia: Writing – original draft, Methodology, Formal analysis. Insaf Setitra: Writing – review & editing.

## Declaration of competing interest

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

## Acknowledgments

Many thanks to the anonymous reviewers for their comments and insights. This work has benefited from the support of the AI Chair SAFE IA (funded by the UTC Foundation for Innovation, France).

## Data availability

Data will be made available on request.

## References

[1] L. Bounia, Améliorer l'intelligibilité des arbres de décision avec des explications probabilistes concises et fiables, Extraction et Gestion des Connaissances (2024) 23–34.

[2] R. Guidotti, A. Monreale, S. Ruggieri, F. Turini, F. Giannotti, D. Pedreschi, A survey of methods for explaining black box models, ACM Comput. Surv. 51 (5) (2019) 93:1–93:42.

[3] F. Doshi-Velez, B. Kim, Towards a rigorous science of interpretable machine learning, CoRR abs/1702.08608. URL http://arxiv.org/abs/1702.08608.

[4] T. Miller, Explanation in artificial intelligence: Insights from the social sciences, Artificial Intelligence 267 (2019) 1–38.

[5] W. Samek, T. Wiegand, K.R. Müller, Explainable artificial intelligence: Understanding, visualizing and interpreting deep learning models, 2017, ArXiv, abs/1708.08296.

[6] C. Molnar, Interpretable Machine Learning - A Guide for Making Black Box Models Explainable, Leanpub, 2019.

[7] Z.C. Lipton, The mythos of model interpretability, Commun. ACM 61 (10) (2018) 36–43.

[8] J.M. Silva, Logic-based explainability in machine learning, 2022, ArXiv abs/2211.00541. n. pag.

[9] A. Darwiche, A. Hirth, On the reasons behind decisions, in: Proc. of ECAI'20, 2020, pp. 712–720.

[10] A. Ignatiev, N. Narodytska, J. Marques-Silva, On relating explanations and adversarial examples, Neural Inf. Process. Syst. (2019).

[11] A. Shih, A. Choi, A. Darwiche, A symbolic approach to explaining Bayesian network classifiers, in: Proc. of LIJCAI'18, 2018, pp. 5103–5111.

[12] G. Audemard, S. Bellart, L. Bounia, F. Koriche, J. Lagniez, P. Marquis, On the computational intelligibility of boolean classifiers, in: Proc. of KR'21, 2021, pp. 74–86, http://dx.doi.org/10.24963/kr.2021/8.

[13] M.C. Cooper, J. Marques-Silva, Tractability of explaining classifier decisions, Artificial Intelligence 316 (2022) 103841.

[14] L. Breiman, Random forests, Mach. Learn. 45 (1) (2001) 5–32.

[15] T. Chen, C. Guestrin, XGBoost: A scalable tree boosting system, in: Proc. of KDD'16, 2016, pp. 785–794.

[16] M.T. Ribeiro, S. Singh, C. Guestrin, Why should I trust you?: Explaining the predictions of any classifier, in: Proc. of SIGKDD'16, 2016, pp. 1135–1144.

[17] S. Lundberg, S.-I. Lee, A unified approach to interpreting model predictions, in: Proc. of NIPS'17, 2017, pp. 4765–4774.

[18] M.T. Ribeiro, S. Singh, C. Guestrin, Anchors: High-precision model-agnostic explanations, in: Proc. of AAAI'18, 2018, pp. 1527–1535.

[19] A. Ignatiev, N. Narodytska, J. Marques-Silva, Abduction-based explanations for machine learning models, in: Proc. of AAAI'19, 2019, pp. 1511–1519.

[20] G.A. Miller, The magical number seven plus or minus two: some limits on our capacity for processing information, Psychol. Rev. 63 (2) (1956) 81–97.

[21] S. Waeldchen, J. Macdonald, S. Hauch, G. Kutyniok, The computational complexity of understanding binary classifier decisions, J. Artificial Intelligence Res. 70 (2021) 351–387.

[22] M. Arenas, P. Barceló, M. Romero, B. Subercaseaux, On computing probabilistic explanations for decision trees, in: Advances in Neural Information Processing Systems (NeurIPS 2022), 2022.

[23] L. Bounia, F. Koriche, Approximating probabilistic explanations via supermodular minimization, in: Conference on Uncertainty in Artificial Intelligence (UIAI 2023).

[24] G. Audemard, S. Bellart, L. Bounia, F. Koriche, J.M. Lagniez, P. Marquis, On the explanatory power of Boolean decision trees, Data Knowl. Eng. 142 (2022) 102088.

[25] Y. Izza, A. Ignatiev, J. Marques-Silva, On explaining decision trees, CoRR abs/2010.11034.

[26] A. Darwiche, Compiling knowledge into decomposable negation normal form, in: International Joint Conference on Artificial Intelligence, 1999.

[27] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, E. Duchesnay, Scikit-learn: Machine learning in Python, J. Mach. Learn. Res. 12 (2011) 2825–2830.
[28] G. Audemard, S. Bellart, L. Bounia, F. Koriche, J.M. Lagniez, P. Marquis, Sur le pouvoir explicatif des arbres de décision, in: Conférence Extraction et Gestion des Connaissances, 2022.

[29] G. Audemard, S. Bellart, L. Bounia, F. Koriche, J.-M. Lagniez, P. Marquis, On preferred abductive explanations for decision trees and random forests, in: Proc. of IJCAI'22, 2022.

[30] S. Waeldchen, J. Macdonald, S. Hauch, G. Kutyniok, The computational complexity of understanding network decisions, 2019, ArXiv 1905.09163: n. pag.

[31] L. Bounia, Enhancing the intelligibility of Boolean decision trees with concise and reliable probabilistic explanations, in: Proceedings of the 20th International Conference on Information Processing and Management of Uncertainty in Knowledge-Based Systems (IPMU 2024), 2024.

[32] L. Bounia, Modèles formels pour l'IA explicable: des explications pour les arbres de décision (Thèse de doctorat), Université d'Artois, 2023, Disponible sur hal.science.

[33] L. Bounia, M. Goliot, A. Chafik, Impact of weight functions on preferred abductive explanations for decision trees, in: ICCBR Workshops, 2023.

[34] G. Audemard, S. Bellart, L. Bounia, J.M. Lagniez, P. Marquis, N. Szczepanski, PyXAI : calculer en Python des explications pour des modèles d'apprentissage supervisé, in: Extraction et la Gestion des Connaissances EGC, 2023.

[35] A. Ignatiev, A. Morgado, J. Marques-Silva, [PySAT:] A Python toolkit for prototyping with SAT oracles, in: Proc. of SAT'18, 2018, pp. 428–437.

[36] P.C. Maggie, W. Chen, Tweet sentiment extraction, 2020, Kaggle. https://kaggle.com/competitions/tweet-sentiment-extraction.

[37] A. Abdaoui, J. Azé, S. Bringay, P. Poncelet, FEEL: a French expanded emotion lexicon, Lang. Resour. Eval. 51 (2016) 833–855.

[38] Eric Wang, et al., Probabilistic sufficient explanations, in: International Joint Conference on Artificial Intelligence, 2021.

[39] Y. Izza, X. Huang, A. Ignatiev, N. Narodytska, M.C. Cooper, J. Marques-Silva, On computing probabilistic abductive explanations, Internat. J. Approx. Reason. 159 (2022) 108939.

[40] G. Blanc, J. Lange, L. Tan, Provably efficient, succinct, and precise explanations, in: Neural Information Processing Systems, 2021.

[41] Y. Izza, K.S. Meel, J. Marques-Silva, Locally-minimal probabilistic explanations, in: European Conference on Artificial Intelligence, 2024.

**Louenas Bounia** is currently a young researcher in artificial intelligence at the Heuristics and Diagnostics of Complex Systems laboratory, Heudiasyc UMR-CNRS 7253, France, and a part-time lecturer at the Université de Technologie de Compiègne (UTC). He holds a master's degree in statistics and machine learning from Sorbonne Université and a Ph.D. in Explainable Artificial Intelligence (XAI) from the University of Artois in France. He has worked on explaining machine learning models, specifically formal XAI methods. His main research areas include explainable XAI, combinatorial optimization, knowledge representation, and NLP.

**Insaf Setitra** is a Lecturer in the Department of Computer Science at the Université de Technologie de Compiègne (UTC), France, and a Research Associate at Heuristique et Diagnostic des Systèmes Complexes, Heudiasyc UMR-CNRS 7253, France. Previously, she worked as a research engineer at the Research Center of Scientific and Technical Information (CERIST) before becoming an Associate Professor at the University of Science and Technology Houari Boumediene (USTHB), Algeria. She earned a Ph.D. in Artificial Intelligence, a Master's degree in Software Engineering, and a Bachelor's degree in Information Systems and Software Engineering from USTHB in 2008, 2010, and 2019, respectively. Her primary research interests include computer vision and deep learning.