On Integrating Logical Analysis of Data into Random Forests

1 Introduction

Random Forests [Breiman, 2001] are among the widely used classifiers in the field of Machine Learning (ML). RF is an ensemble learning method that combines multiple Decision Trees (DTs) into a unified model through a specific process of aggregation and is widely used across various fields. By combining the predictions of many different DTs, RFs offer more robust and accurate models than a single DT, making them a well-known tool in many ML tasks. Despite its high performance, one of the shortcomings of RF is the use of many features during the construction of different DTs, which makes it difficult to extract short and concise explanations for end users. Indeed, the recent advancements in ML and the expected rise in ML-driven applications, particularly those sensitive applications that affect people or involve safety-critical systems, have highlighted the growing need to understand and explain the predictions made by these models. Therefore, in recent years, the field of eXplainable Artificial Intelligence (XAI) has experienced significant growth (see e.g. [Ribeiro et al., 2016; Guidotti et al., 2018; Ignatiev et al., 2019; Audemard et al., 2020; Ignatiev et al., 2020; Ignatiev and Marques-Silva, 2021]). Explaining RFs has recently been investigated, and different approaches have been proposed to extract the smallest explanations for a given example or instance (see e.g. [Izza and Marques-Silva, 2021; Audemard et al., 2022a; Audemard et al., 2022b; Izza et al., 2023; Audemard et al., 2023]) by considering minimal subsets of features that explain the classification, known as Abductive eXplanations (AXps), or those that allow to change the class, known as Contrastive eXplanations (CXps). Despite recent advancements, the sizes of the explanations for RFs trained on datasets containing numerous features are still too large, since the limited size of an explanation that can be understood as a whole by humans or end users is usually set to 7±2 [Miller, 1956]. Therefore, it is important to emphasize that minimizing the number of features required to build RFs can significantly impact the succinctness and comprehensibility of the derived explanations. This is the main goal addressed in this work.

To achieve the aforementioned objective, in this paper, we follow the recent advancement made for building Optimal Decision Trees thanks to Logical Analysis of Data (LAD) [Ing et al., 2024]. More precisely, we propose an original integration of LAD [Crama et al., 1988; Hammer, 1986] into the classical RF algorithm. LAD is a logic-based data analysis methodology that combines optimization, Boolean functions, and combinatorial theory. The primary aspects of LAD involve identifying minimal support sets (MSSes) necessary for explaining observations and uncovering hidden data patterns that differentiate observations among various groups of data. Explicitly, we demonstrate how to enhance the classical RF algorithm by randomly choosing MSSes rather than randomly choosing feature subsets that potentially contain irrelevant features for building different DTs. By doing this, the DTs of the RFs are built on randomly chosen MSSes to avoid DTs with irrelevant features. Experiments on standard benchmark datasets show that integrating MSSes of LAD into classical RFs can maintain similar performance in terms of accuracy, produce forests of similar size, decrease the set of used features, and enable us to derive considerably shorter explanations compared to classical RFs.

The remaining sections of this paper are structured as follows. Section 2 provides some preliminaries, including ML classification, explainable AI, LAD and MSSes enumeration problem. In Section 3, we describe how to integrate LAD into the classical RF. We conduct the comparative experimental evaluation for RF methods in Section 4. Finally, Section 5 concludes the paper and addresses potential future works.

2 Preliminaries

In this section, we briefly present a formal background to introduce necessary notations used throughout the paper.

2.1 Machine Learning Classification

This paper focuses on classification for data with binary features. Using the fairly standard one-hot encoding and other standard techniques (e.g. [Fayyad and Irani, 1993; Perner and Trautzsch, 1998; Kotsiantis and Kanellopoulos, 2006; Garc´ıa et al., 2013]), non-binary categorical and numerical features of a dataset can be transformed into binary values.

Let F = {x1, . . . , xt} be a set of t binary features, all of them take value in {0, 1}. Let E = E + ∪ E - be a binary dataset partitioned into a set of positive instances E + and a set of negative instances E -. To refer to a binary observation vector of t features, we use the notation v = (v1, . . . , vt), where vi ∈ {0, 1}, i = 1, . . . , t. An instance denotes a pair ϵq = (vq, cq) ∈ E, where vq ∈ {0, 1}t and cq ∈ {0, 1} is the class value. We have cq = 1 if ϵq ∈ E + and cq = 0 if ϵq ∈ E -. We denote a binary dataset as a set of n training instances E = {(v1, c1), . . . , (vn, cn)}.

The classification problem aims to learn some function f (the classifier) mapping binary observation vectors to class values, matching as accurately as possible the actual function τ on the training data (i.e. τ(vq) = cq, q = 1, . . . , n) and tries to generalize well to new and unseen data. In this paper, we focus on Decision Tree and Random Forest classifiers.

For Decision Tree (DT), the function f is represented by a binary and full DT, where every internal node has exactly two children. Every internal node is associated with a feature or its negation and every leaf node is associated with a class.

Random Forest (RF) is an ensemble method that constructs multiple decision trees (DTs) on various subsamples of the training set and uses averaging to improve the accuracy. RF mitigates overfitting by combining diverse DTs, where each DT might have high variance, into a more robust and generalized model. Formally, let RF = {T1, T2, . . . , TK} be a collection of K DTs. Each tree Ti ∈ RF is trained on a different bootstrap sample from the training set and is constructed recursively based on a random subset of features. Given an observation vector v, each tree Ti predicts a class label Ti(v) ∈ {0, 1}. The final prediction of the RF, f(v) depends on a voting mechanism among the K DTs:

In this study, we consider two different voting mechanisms: majority-vote and soft-vote. These two mechanisms can produce different results as described in Example 1.

Example 1. Consider a case where a soft-vote produces a different outcome compared to a majority-vote. Suppose we have a random forest made of three DTs, RF = {T1, T2, T3}. The predictions of those three DTs are given as follows:

1. T1 predicts class 0 with probability 0.7 for class 0 and 0.3 for class 1.
2. T2 predicts class 1 with probability 0.4 for class 0 and 0.6 for class 1.
3. T3 predicts class 1 with probability 0.45 for class 0 and 0.55 for class 1.

Majority-vote: class 0 is predicted by T1, class 1 is predicted by T2 and T3. Thus, the final prediction of RF is class 1. Soft-vote: The mean probability for class 0 = 0.7+0.4+0.45 3 ≃ 0.5167 and the mean probability for class 1 = 0.3+0.6+0.55 3 ≃ 0.4833. In this case, class 0 has a higher mean probability of 0.5167. Thus, the final prediction of RF is class 0.

2.2 Explainable Artificial Intelligence

Explainable Artificial Intelligence (XAI) has recently received significant attention and has emerged as a fundamental field, aiming to allow human users to understand and trust the results produced by AI/ML systems [Barredo Arrieta et al., 2020]. Explainability for AI systems has grown along with the success and adoption of deep learning systems, which are applied in many fields where trustworthiness is critically needed, such as in legal systems [Lipton, 2018; Rudin, 2019], autonomous driving [Tian et al., 2018], cybersecurity [Shone et al., 2018], health care and criminal justice [Rudin and Ustun, 2018], financial risk assessment [Chen et al., 2018], detecting heart attacks [Weng et al., 2017], surveillance systems [Ding et al., 2018], among others.

In this paper, we focus on two well-known explanations, abductive explanation (AXp) as an answer to a "why?" question and contrastive explanation (CXp) as an answer to "why not?" question, subject of recent works for explaining RFs [Izza and Marques-Silva, 2021; Audemard et al., 2022b].

Given an ML model, computing a classification function τ on feature space F = {0, 1}t , a specific point v ∈ F, with prediction c = τ(v), where v = (v1, . . . , vt). To refer to an arbitrary point in F, we use the notation u = (u1, . . . , ut).

1. A PI-explanation or Abductive eXplanation (AXp) is any minimal subset X ⊆ F such that:

1. A Contrastive eXplanation (CXp) is any minimal subset Y ⊆ F such that:

2.3 Logical Analysis of Data

Logical Analysis of Data (LAD) is a logic-based data analysis methodology combining ideas and concepts from discrete optimization, combinatorics and the theory of Boolean functions. The idea of LAD was first described by Peter L. Hammer in a lecture given in 1986 [Hammer, 1986] and was later expanded and developed in [Crama et al., 1988]. The central concepts behind LAD are the computation of minimal support sets of features for explaining all observations, and the discovery of hidden data patterns capable of distinguishing positive and negative sets of observations. A collection of such patterns is used for building a classification procedure, clustering, feature selection and other related problems.

LAD has undergone continuous development in various domains, including medical applications [Hammer and Bonates, 2006], financial applications [Hammer et al., 2007], the airline industry [Mortada et al., 2012], condition-based maintenance applications [Yacout et al., 2017], industrial chemical processes [Ragab et al., 2018], among others. For more details on LAD, we refer the reader to [Boros et al., 2000; Hammer and Bonates, 2006]. Our goal in this paper is to utilize the main first step of LAD, which involves discovering support sets that distinguish observations among various groups of data, and to integrate these support sets into RFs.

Example 2. Consider dataset in Figure 1. The projection of E + and E - on S = {x1, x2} is E + S = {(0, 0), (1, 1)} and E - S = {(1, 0)}, respectively. Moreover, {x1, x2}, {x2, x3}, {x3, x4, x5}, and {x1, x4, x5} are minimal (w.r.t. inclusion) support sets. Concretely, {x1, x2} and {x2, x3} are the minimum size support sets (w.r.t. cardinality).

In the sequel, we use similar notations and definitions to those of [Hammer and Bonates, 2006]. Given a set of binary features S ⊆ F, let E + S (resp. E - S ) be the projection of E + (resp. E -) on S. S is called a support set if E + S ∩ E - S = ∅. Moreover, S is called irredundant or minimal if no proper subset of it is a support set. To compute minimum support sets in E, we associate with every feature xk ∈ F a new binary variable yk, where k = 1, . . . , t, yk = 1 if xk is part of the support set, and yk = 0 otherwise. Let v = (v1, . . . , vt) and v′ = (v′1 , . . . , v′t ) be the binary observation vectors of t features associated with E + and E -, respectively. We further associate the vectors v and v′ with a vector w(v, v′ ) = (w1(v, v′ ), . . . , wt(v, v′ )), where wk(v, v′ ) = vk ⊕ v′k (mod 2), i.e. wk(v, v′ ) = 1 if vk ̸= v′k , and wk(v, v′ ) = 0 otherwise. We can obtain the minimum support sets by solving the following set covering problem:

Example 3. For the dataset in Figure 1, the formulation of LAD Minimum Support Sets (LAD-MSS) is given by:

The above problem is a known NP-hard and involves a quadratic number of linear inequalities. For large datasets, solving this optimization problem is difficult in practice. In Section 2.4, we circumvent this problem by proposing a more efficient alternative, formulating it as the problem of generating minimal hitting sets.

2.4 Minimal Support Sets Enumeration

We first provide a relation between minimal support sets (MSSes) and minimal hitting sets (MHSes), and then describe how to enumerate them. We begin by recalling the minimal hitting set problem.

Definition 1. Given a collection H = {H1, . . . , Hm} of subsets over a universe U. A hitting set (traversal) T of H is a subset of U that intersects (hits) every set Hi ∈ H i.e. T ∩Hi ̸= ∅. Moreove, T is minimal if there is no T ′ ⊂ T s.t. T ′ is a hitting set.

The minimal hitting set problem is relevant to multiple fields, including Boolean algebra [Fredman and Khachiyan, 1996], computational biology [Ideker et al., 1999], data mining [Bailey et al., 2003], combinatorics [Eiter et al., 2008], and more.

In the literature, there exists several algorithms and efficient implementations to compute the set of MHSes [GainerDewar and Vera-Licona, 2016]. Murakami and Uno [Murakami and Uno, 2014] propose "pMMCS", a parallel implementation version of their first algorithm MMCS (Minimalto-Maximal Conversion Search), for solving the MHSes enumeration, whose complexity is in O(∥H∥) time per MHS and O(∥H∥) memory, ∥H∥ denotes the sum of the sizes of elements of H. The advantage of this algorithm is its ability to tackle large-scale problems involving millions of hyperedges, quickly producing numerous solutions, which influenced our decision. Additionally, it supports multithreaded implementations on systems with multiple CPUs.

Let F = {x1, . . . , xt} be a set of t binary features, E = E + ∪ E - a binary dataset, v and v′ the binary observation vectors associated with E + and E -, respectively. Using the result of Section 2.3, we can derive a set of binary vectors from E denoted as E + ⊕ E - = E⊕ = {w(v, v′ ), ∀(v, c) ∈ E + ∧∀(v′ , c′ ) ∈ E -}. We denote by H(E⊕) the following set H(E⊕) = {E (v,v′ ) ⊕ , ∀(v, c) ∈ E + ∧ ∀(v′ , c′ ) ∈ E -}, where E (v,v′ ) ⊕ = {xk ∈ F | k ∈ {1, . . . , t} and wk(v, v′ ) = 1}.

As proven in [Ing et al., 2024], the minimal support sets (MSSes) of E correspond to MHSes(H(E⊕)). Consequently, the MSSes generation can be performed as follows:

1. XOR Operations (E → E + ⊕ E -): execute XOR operations between every observation in E + and every observation in E - of E denoted as E⊕ = E + ⊕ E -, a set of binary vectors. For multi-class classification, we perform XOR operations between each pair of classes.
2. Generate MSSes for H(E⊕), noted as MSSes(H(E⊕)).

Example 4. From the formulation of LAD-MSS as a 0/1 linear program (Example 3), we can derive the following set of sets, where each subset corresponds to the set of features associated with the set of variables involved in each 0/1 linear inequality: H(E⊕) = {{x1, x3, x4, x5}, {x1, x3}, {x1, x3, x5}, {x1, x3, x4}, {x2, x4}, {x2, x5}}. Then MSSes(H(E⊕)) = {{x1, x2}, {x2, x3}, {x3, x4, x5}, {x1, x4, x5}} corresponds to the minimal supports sets in the Example 2.

Note that the number of MSSes can grow exponentially in the worst case. For practical purposes, in this paper, we propose generating only a subset for integration into RFs.

3 RandomForest Based LAD

A main result proved in [Ing et al., 2024] shows that for a minimal support set S, it is possible to build a perfect decision tree (see Definition 3) that correctly discriminates between positive and negative examples using only the features of S for a dataset without redundancy (see Definition 2). Nevertheless, the number of MSSes can be exponentially large, and choosing the most relevant MSS is a computationally hard task. Moreover, finding the smallest MSSes with respect to cardinality is also NP-hard. For this reason, the authors considered generating minimal support sets (w.r.t. inclusion) instead of generating minimum ones (w.r.t. cardinality), and a heuristic scoring method has been designed to select the most effective MSS for building a perfect decision tree.

Definition 2. Let F be a set of binary features and E = E + ∪ E - a binary dataset over F. S ⊂ F is called redundant if E + S ∩ E - S ̸= ∅.

Definition 3. A decision tree is perfect if it correctly classifies all the observations of E = E + ∪ E -.

Let us now discuss how MSSes can be leveraged within the RF algorithm. First, we recall that the classical RF (Algorithm 1) creates a bootstrap sample of the same size as the training data using the Bootstrap function, where rows from the training data are randomly selected with replacement (line 8). For each bootstrap sample, by default, √t features are randomly selected to form a feature subset, and a DT algorithm (e.g. CART) is then used to build a DT over the bootstrap sample based on that feature subset (line 9).

As stated in Section 2.3, a key advantage of LAD is its capability to generate minimal feature subsets that effectively distinguish between different classes. In contrast, one of the weaknesses of the classical RF is its sensitivity to noise, which can lead to the selection of irrelevant features when training on bootstrap samples, resulting in the use of too many features. To address this drawback, MSSes are valuable due to their discriminative power, focusing on relevant features. Algorithm 2 describes the proposed RF-LAD approach. In detail, NS MSSes are generated using the training

Algorithm 1: Classical Random Forest

• 1: Input:
• 2: E: Training dataset with n samples
• 3: K: Number of trees in the forest
• 4: t: Number of features
• 5: Output:
• 6: Ensemble of K decision trees
• 7: for i = 1 to K do
• 8: Ei ←Bootstrap(E)
• 9: Ti ←CART(Ei, √t)
• 10: end for
• 11: return RF = {T1, T2, . . . , TK}

data E (line 7). Among these MSSes, K MSSes are randomly pre-selected without replacement (i.e. no redundancy among them) to be associated with each bootstrap sample (line 8). Over each bootstrap sample, the tree is built using the features of its associated MSS (line 11). Note that each Si remains a support set of Ei but not necessarily minimal. In fact, since Ei is a subset of the training data E, each support set of E is a support set of Ei.

Since the number of MSSes is exponential in the worst case, limiting the enumeration to NS ones is useful to control this complexity. Additionally, as K MSSes are chosen among NS , NS must be large enough to ensure diversification and thus allow for a subset of MSSes that is representative of the considered data.

Let us note that using RF-LAD through MSSes ensures that important features have a high chance of being used. Moreover, using MSSes' features rather than randomly generated features for bootstrap samples can decrease the number of used features since minimality is required for support sets. Consequently, the abductive and contrastive explanations can also be significantly reduced accordingly.

As mentioned earlier, on data without redundancies, it is possible to classify all the training examples correctly by building perfect decision trees. Nonetheless, when using a classical Random Forest algorithm, we do not have guarantees in terms of perfect classification for each decision tree due to the randomization used to restrict the number of features for each bootstrap sample. Now, using RF-LAD, the trees are built over MSSes generated using the whole training data. Since MSSes remain support sets for the bootstraps, perfect trees can be built. For instance, this can be achieved by removing the restriction on depth in the CART classifier.

Next, we discuss how MSSes can be used to enforce some examples to be correctly classified.

Proposition 1. Let RF = {T1, ..., TK} be a set of K perfect decision trees built over a set of bootstraps {E1, ..., EK}. If ϵq = (vq, cq), s.t. vq appears at least ⌊ K2 ⌋ + 1 times in {E1, ..., EK}, then RF(vq) = cq, using the majority vote.

Proof. Assume that all the decision trees (DTs) of RF are perfect. Then, each Ti correctly classifies all the examples of Ei. If ϵq = (vq, cq) appears more than ⌊ K2 ⌋ times, using the majority vote for RF will classify vq as class cq with more than ⌊ K2 ⌋ DTs. Consequently, RF(vq) = cq.

Proposition 1 ensures that frequent examples among bootstraps are guaranteed to be well classified. However, classical RF uses a random policy to choose features in each bootstrap, which leads to redundancies, i.e. identical examples that appear in both positive and negative classes (Definition 2), preventing perfect classification for all variants of DT classifiers. In contrast, by using MSSes, we will be able to ensure that RF-LAD can classify the majority of frequent examples into their corresponding classes.

Algorithm 2: Random Forest Based LAD (RF-LAD)

• 1: Input:
• 2: E: Training dataset with n samples
• 3: K: Number of trees in the forest
• 4: NS: Number of MSSes to generate
• 5: Output:
• 6: RF: Ensemble of K decision trees
• 7: LS ← generate MSSes(E,NS)
• 8: {S1, . . . , SK} ← random select(LS,K)
• 9: for i = 1 to K do
• 10: Ei ←Bootstrap(E)
• 11: Ti ←CART(Ei, Si)
• 12: end for
• 13: return RF = {T1, T2, . . . , TK}

4 Experimental Results

In this section, we conduct comparative experiments between our Random Forest using MSSes of LAD (RF-LAD) and the state-of-the-art Random Forest (RF) (from the scikit-learn Python library [Pedregosa et al., 2011]). The parameters of RFs are kept at their default values (i.e. in a forest, K = 100 DTs), except for the maximum depth, where we set different depths d ∈ {3, 4, 5}. The assessment is performed on 23 datasets, which are standard benchmarks originating from well-known repositories such as CP4IM (https: //dtai-static.cs.kuleuven.be/CP4IM/datasets/), Kaggle (www. kaggle.com), OpenML (www.openml.org), and UCI (archive. ics.uci.edu/ml/). Some of them are original binary datasets, while others are numerical datasets that have been binarized using thresholds retrieved from CART [Breiman et al., 1984]. Let us note that, for certain datasets, instances appearing in both E + and E - are removed to maintain consistency. For every benchmark, a Repeated Stratified 10-fold cross-validation with 3 repetitions have been achieved to maintain the class distribution (i.e. to address imbalanced datasets). To enumerate the MSSes, we use the multithreaded implementations provided by the algorithm "pMMCS" [Murakami and Uno, 2014], and set the number of threads to 20 to ensure diversification in terms of the generated MSSes. To control the complexity, we modified "pMMCS" by limiting the number of MSSes to 100K (i.e. NS = 100K) for all the considered datasets. For a fair comparison, we randomly select 100 different MSSes (without redundancy) from the 100K generated MSSes, resulting in 100 different DTs to build our RF-LAD. Two voting mechanisms are used for RF-LAD approach: the majority-vote and the soft-vote. Experiments are conducted on a computer equipped with Intel(R) Core(TM) i9-10900 CPU @ 2.80GHz with 62Gib of memory.

The results are reported in Table 1. The first column shows the name of the dataset, the size of the dataset (#s), the number of features (#f), and the number of classes (#c). The second column displays different depth settings (d). The column RFsklearn represents the RF algorithm from sklearn (it utilizes the soft-voting mechanism), while the columns RFLAD(majority-vote) and RFLAD(soft-vote) represent our proposed RF-LAD using majority-vote and soft-vote, respectively. The column "Acc." stands for the testing or prediction accuracy along with its standard deviation, and the column "#nbNodes" is the average total number of nodes in a forest. The column "Time(s)" measures the average runtime for constructing our RF-LAD. This runtime includes encoding the dataset into an MHS problem, generating 100K MSSes, randomly selecting 100 MSSes, and building 100 DTs. Note that we do not report exact runtime for the RFsklearn because it takes only a few seconds. According to the experiments, RFsklearn and RF-LAD(s) perform similarly across most benchmarks in terms of accuracy, with differences often within only 1% to 2%. The higher accuracies with more than 2% are highlighted in bold. For the standard deviations, they seem to be very similar, with only slight differences (between 1% and 2%) for some datasets. In terms of #nbNodes, RFLAD(s) are able to produce smaller forests on 10 benchmarks across all depths (e.g. anneal, drilling, fetal-health, . . . ).

Our second comparison concerns the average number of features used in a forest between RFsklearn and RF-LAD(s). The top histogram of Figure 2 displays the average number of features used in RFsklearn and in RF-LAD(s) for d=4. The x-axis displays all the considered datasets, and the yaxis displays the average number of features used. As we can see in that histogram, for all the considered datasets, RF-LAD(s) used fewer features to build the entire forest compared to RFsklearn. Statistically, for all the benchmark datasets, RFLAD(majority-vote) used from 4.72% to 78% less than RFsklearn, whereas RFLAD(soft-vote) used from 3.92% to 78.83% less than RFsklearn. Furthermore, for the datasets with more than 200 features, such as "ad", "cnae", "pd-speech", "reuters", and "spambase", the reduction exceeds 50%, showing strong reduction. These results show that RF-LAD(s) are beneficial, notably for datasets containing numerous features.

Our final comparison focuses on the size of the explanations derived from RFsklearn and RF-LAD(s). To derive such explanations from those RFs, we utilized the recent Random Forest explanation tool (RFxpl: https://github.com/ izzayacine/RFxpl) proposed by Izza and Marques-Silva [Izza and Marques-Silva, 2021]. The authors proposed a propositional encoding for computing explanations of RFs, enabling the extraction of abductive explanations (AXps) and contrastive explanations (CXps) using a SAT solver. First, to obtain a model for each RF algorithm, we saved the best trained model based on the highest testing accuracy during the evaluation process of all 30 iterations (10-fold cross-validation with 3 repetitions). Then, to choose the examples for explanation, we followed the procedure in [Izza and MarquesSilva, 2021] by randomly picking fractions of the dataset, depending on its size. More precisely, for datasets containing fewer than 200, 200-999, and 1000-9999 examples, we randomly picked 40%, 20%, and 10% of the examples, respectively, to explain. To ensure a fair comparison in terms of the sizes of the explanations, for all datasets, we set a fixed randomized seed so that RFsklearn and RF-LAD(s) explain only the same examples. Finally, we report the average size of AXps and the average size of CXps. The middle histogram and the bottom histogram of Figure 2 represent the average size of AXps and the average size of CXps, respectively. The x-axis displays all the considered datasets, and the y-axis displays the average size of AXps (middle histogram) and the average size of CXps (bottom histogram). In these histograms, we can see that shorter AXps and CXps can be derived from RF-LAD(s) compared to RFsklearn for most considered datasets, except for a few datasets like "soybean" and "wdbc", where slightly longer AXps were derived from RF-LAD(s). Similarly, for datasets like "hepatitis" and "loan", slightly longer CXps were also derived from RF-LAD(s). Statistically, for RF-LAD(s), the average size of AXps are reduced by 17.72% to 90.28% and by 18.96% to 87.86% for RFLAD(majority-vote) and RFLAD(soft-vote), respectively. In a similar vein, the average size of CXps are reduced by 17.44% to 96.53% and by 3.23% to 94.14% for RFLAD(majority-vote) and RFLAD(soft-vote), respectively. Additionally, for at least 10 datasets and at least 14 datasets, the reduction in the average size of AXps and CXps exceeds 50%, respectively, which also shows a significant reduction.

To summarize, this section shows that building RFs using MSSes (RF-LAD) allows for a reduction in the set of used features while maintaining similar results in terms of prediction accuracy, produces forests of similar size with sometimes higher accuracy, and enables us to derive shorter explanations compared to the classical RF approach.

5 Conclusion and FutureWorks

In this paper, we have shown how to integrate the Logical Analysis of Data (LAD) framework to enhance classical random forests (RFs) using minimal support sets (MSSes) based on their discriminating property. Concretely, we have proposed to modify the classical RF algorithm by randomly choosing MSSes rather than randomly choosing feature subsets that likely contain irrelevant features for training bootstrap samples. Experiments on benchmark datasets show that our RF-LAD(s) are competitive with the classical RF in terms of prediction accuracy, while producing a forest of similar size, using limited features that lead to the extraction of shorter explanations compared to the classical RF.

In the future, we plan to extend LAD to handle numerical datasets directly, without relying on binarization techniques. Finally, it would be interesting to integrate LAD into other tree-based algorithms to evaluate whether it can also produce shorter and more concise explanations.

Acknowledgments

Many thanks to the anonymous reviewers for their insightful comments. This work has benefited from the support of the ANR HYCI Project (ANR-22-CE55-0010) and the support of the National Research Agency under France 2030 MAIA Project (ANR-22-EXES-0009).