Explainable Artificial Intelligence (XAI) is essential in machine learning and artificial intelligence as it improves transparency, accountability, trust, and the ability to enhance and debug AI systems. As AI technologies expand to various sectors, from healthcare to finance, the complexity and opacity of these models often prevent their deployment in critical decision-making processes. XAI seeks to mitigate this issue by providing insights into how AI algorithms reason and how they arrive at specific conclusions, enabling users to validate and comprehend model behaviors. Most of XAI research today focuses on post-hoc explanations for black-box models. These models have complex internal workings that are difficult for humans to interpret or understand. Various forms of analysis, from surrogate models to gradient credit assignment, are often used to explain these models and their decisions. However, these post-hoc explanations have several drawbacks. For example, they often fail to capture the true inner workings of the model, TempXAI@ECML-PKDD'24: Explainable AI for Time Series and Data Streams Tutorial-Workshop, Sep. 9 th , 2024, Vilnius, Lithunia Envelope parisa.jamshidi@hh.se (P. Jamshidi); slawomir.nowaczyk@hh.se (S. Nowaczyk); mahmoud.rahat@hh.se (M. Rahat); zahra.taghiyarrenani@hh.se (Z. Taghiyarrenani) Orcid 0000-0001-7055-2706 (P. Jamshidi); 0000-0002-7796-5201 (S. Nowaczyk); 0000-0003-2590-6661 (M. Rahat); 0000-0002-1759-8593 (Z. Taghiyarrenani)
providing only surface-level insights that might not be trustworthy [1,2]. Furthermore, they are vulnerable to adversarial attacks that can manipulate the explanations without changing the model's predictions [3,4]. Such limitations make them a questionable choice in applications where transparency is a priority. Conversely, white-box models are inherently explainable models designed to be transparent and interpretable from the outset. These models allow users to understand their decision-making processes without the need for additional interpretability techniques [1].
Federated learning (FL) is a technique in machine learning in which multiple devices record local data and share their model with a server. The server forms a global model and shares it without exchanging raw data. This method is more efficient regarding bandwidth and computing resources because it does not need to transfer large amounts of raw data to a central server.
Although this approach has gained much attention due to its capacity, most of the underlying models for FL are Artificial Neural Networks (ANNs). Post-hoc explainability methods can be applied to black-box models of FL. For example, [5] used feature importance methods to add explainability to their models, while [6] presented counterfactual explanation techniques. However, there is a surprising lack of FL techniques suitable for inherently interpretable models.
In this paper, we focus on Decision Tree (DT) classifiers. Shallow DTs, in contrast to NNs and complex models, are designed in a way that their internal workings are easily understandable to humans. This allows for straightforward tracing of how inputs are transformed into outputs, facilitating immediate insight into the decision-making process. Such transparency is crucial for validating the model's logic, ensuring ethical compliance, and fostering trust among users. This makes DTs particularly suitable for the identification and correction of biases and errors within the model: their transparent nature enables users to pinpoint specific aspects of the model that contribute to undesirable outcomes, facilitating targeted improvements. Moreover, some research indicates that tree-based models outperform ANNs in some applications, specifically tabular data [7,8].
The typical approach in ML is batch learning, also known as offline learning, which involves training a model on a fixed dataset all at once. On the other hand, online learning, or incremental learning, continuously updates the model as new data becomes available. This makes it suitable for dynamic environments where data arrives sequentially. Much less research has been done with incremental learning in FL fashion than batch learning.
Therefore, there is a gap when clients have access to streaming data and aim to achieve an inherently explainable global model with better performance than their local model through collaboration in a federated mode. We proposed our method to aggregate the incremental decision trees from clients' sides in an FL framework, which can achieve higher performance compared to local ones, and as the client's models are DTs, they are inherently explainable. Our contributions are as follows:
• We created a global model without centralizing raw data, using statistical information stored in EFDTs. • In our proposed method, EFDTs are trained locally and aggregated in each round. • We have introduced three aggregation methods on the server to aggregate clients' EFDTs.
• Furthermore, we maintain both local and global models as a single tree to make them inherently explainable.
The rest of the paper is organized as follows: Related work summarizes previous research intersection of FL and tree-based methods. Then, in Preliminaries, we introduce some basic concepts of incremental decision trees and tree similarity methods. The proposed method is described in Methodology. The experimental setup is found in Section Experimental Setup followed by the result in Results. Finally, we draw some conclusions in Conclusion
Within this distributed learning paradigm, horizontal federated learning (HFL) and vertical federated learning (VFL) represent two approaches. Each client has different data samples in HFL, but the feature set is the same. VFL, however, uses data samples shared among clients with different features [9]. SecureBoost [10] is a VFL framework in which only one of the clients has the label of samples, called active party, and the rest, without labels, called passive parties. This method works with a gradient-tree boosting algorithm in which the active party shares the gradient and Hessian values with the passive party. After that, the passive party categorizes the samples based on local features into buckets and provides the total values of each bucket to the active party in the form of a histogram. The active party then performs local calculations to find the best way to split the nodes and directly coordinate updates with the passive parties. Other methods, like OpBoost [11], were proposed to optimize SecureBoost. There are other methods categorized on tree-based VFL, including FEDXGB [12] and VF2Boost [13], which are Homomor Encryption (HE)-based.
There is also research on the conjugation of tree-based models and HFL. [14] proposed a method based on GBDT(Gradient-boosted decision trees), in which each client trains a decision tree using their local dataset and adds it to the global model in turn. Boosting-based Federated Random Forest (BOFRF) [15] proposed a boosting framework for random forests in a federated manner. Each client forms their RFs and, on the server side, considers those as weak classifiers and proposes a method to calculate their weights. Our approach involves explicitly training a single tree, which is explainable, whereas using the bagging approach in the server to form the global model will result in a loss of explainability.
Another approach is to train a tree-based model collaboratively in a server. Clients share local statistical information with the server, and the server decides on node partitioning in each round.
There are few works of conjugation of incremental decision trees and FL. [16] and [17] are two methods to train an IDT in VFL and HFL, respectively. The first method encrypts samples from clients' streaming data and passes them to the server. In the latter method, the Data Collector collected the raw data from the client and aggregated them. In both, the server uses that information to train a VFDT.
Our proposed method falls under the category of HFL, and the features are consistent across all clients. Additionally, we do not share raw data with the server. Instead, we train trees on the client side, and the server is responsible for aggregating the trees.
The Hoeffding Tree (HT) [18] is one of the fundamental research studies that proposed the Incremental Decision Tree (IDT) for efficient data stream mining. The HT uses the Hoeffding bound to determine when a statistically significant decision about splitting a node can be made based on the amount of data collected. The inequality for a random variable 𝑟 with range 𝑅 is expressed as follows:
where 𝜖 represents the margin of error, 𝛿 is the confidence level, and 𝑛 is the number of observations. In 2018, [19] proposed the Hoeffding Anytime Tree, also known as the Extremely Fast Decision Tree (EFDT). EFDT, in contrast, enhances the capabilities of HT by including an "anytime" aspect. This means it can continuously update and revise its model as new data becomes available without revisiting old data. While HT makes decisions based on accumulated data up to a certain point, EFDT continuously improves its decisions, resulting in better performance in dynamic data streams.
An important step in Federated Learning is an aggregation of models from different clients, and a crucial component in that process is based on the similarity between them. Decision tree similarity methods aim to quantify the similarity between different decision trees. Over the years, several approaches have been proposed, typically divided into two main categories: syntactic and semantic similarities.
Syntactic similarity methods compare and analyze decision trees based on their structure. Techniques such as tree edit distance, which calculates the minimal changes needed to transform one tree into another, and structural similarity measures, which compare the arrangement and features of nodes, are commonly used [20,21,22].
Semantic similarity methods aim to capture the functional similarity between trees by considering the decisions made by each tree, which means they look at the similarity in the prediction distributions [23,22]. This can consider the similarity of decisions made by each tree on a set of instances.
Our methodology consists of two phases: training and aggregation. Training occurs on the clients' sides, while aggregation occurs on the server's side. Our training process is incremental since we are in the streaming setting. Our main contribution resides in the aggregation phase, in which we put different aggregation strategies into contrast.
Assume we have 𝑘 clients 𝑐 1 ⋯ 𝑐 𝑘 where each one has access to a different streaming dataset 𝐷 1 ⋯ 𝐷 𝑘 . Given that we are in a horizontal federated setting, the feature set is the same for all datasets 𝑓 1 ⋯ 𝑓 𝑚 .
In particular, in order to maintain the inherent interpretability of the global model, we require that the final result be limited to a single decision tree. While aggregating a number of trees into a forest is a natural way to extend DT learning to a federated setting, our work is one of the very few attempts to collaboratively create a single tree among all the clients.
In our proposed method, the server only aggregates the clients' trees without training them, so there's no need to share raw data with the server.
Each client(𝑐 𝑖 ) trains its own decision tree on its local dataset(𝐷 𝑖 ). As a new data point arrives, they use incremental learning to update their tree. After a predefined number of data points are received by each client, they send their trained decision trees to the server. Then, each one will receive a new tree from the server and continue using and training this new tree by the next part of their streaming data.
Each node of EFDT stores a 𝑛 𝑖𝑗𝑘 table, which can be interpreted as the number of instances where the 𝑖 − 𝑡ℎ attribute has the 𝑗 − 𝑡ℎ value, and the class label is 𝑘. This table is used to calculate metrics such as information gain or Gini index, which determine the best attribute for splitting the data at a node. Each client will share their tree with this information instead of raw data.
The aggregation process begins when the server receives decision trees from the clients. We have proposed three different strategies for the server side. However, the aggregation process remains consistent across all strategies, but each strategy differs in its approach to selecting the base tree. Before delving into the specifics of each strategy, let's first explore how the aggregation process operates.
As mentioned earlier, every node in EFDT contains an 𝑛 𝑖𝑗𝑘 table. As part of the aggregation process, we merge the tables of nodes along the same path into two trees. Algorithm 1 outlines this method in detail. Specifically, when two nodes from two trees share common parents, they can be effectively combined, even if they have opted for different features. This is possible because the table contains aggregated information before the split. traverse(𝑇 1 .root, 𝑇 2 .root) 16: end function As mentioned earlier, the strategies differ in terms of how the base tree is chosen to combine the clients' models. Below are the details of three proposed strategies.
In this approach, the base tree is the most representative syntactic tree among the clients' trees, meaning it is the tree that requires the fewest changes to match the other trees. By using the edit distance on the bracket format of the trees, we can identify this tree, which we refer to as "Syn" in Algorithm 2. Then, the aggregation method is applied to "Syn" along with the other clients' trees. Finally, the server broadcasts the Syn tree to all clients.
The base tree in this strategy is that tree with minimum disagreement with other clients on predictions. In Algorithm 3, the server uses a proxy dataset, 𝐷 𝑠 , to identify this tree, referred to as "Sem". Then, it iterates through all client trees, aggregating information from matching paths in each tree into the Sem tree to update it. Finally, the server broadcasts the Sem tree to all clients.
Algorithm 2 Syntactic strategy (Syn)
In contrast to previous strategies, this strategy constructs one tree per client. It compares each client's tree with the trees of all other clients and aggregates information from matching paths into the final tree for that client (Algorithm 4). After updating all trees, the server will pass the updated trees to their owners. aggregation(𝐼 𝑛𝑑, 𝐶 𝑖 ) ▷ Each tree would be aggregated with the other trees' common path. end for 10: end for We used centralized learning and local learning to establish upper-bound and lower-bound, respectively, for the mentioned strategies. In centralized learning, all the data exist in a single location, and a single model is trained. In contrast, in local learning, each client trains a model with its own data without interacting with other clients.
We use two datasets with categorical features, which lets us better control the experiment and analyze the results. Below is a brief description of each.
Mushroom dataset: This dataset contains 8124 descriptions of hypothetical samples representing 23 species of gilled mushrooms in the Agaricus and Lepiota Family. Each species is classified as edible or poisonous. There are 22 features and 8124 data points 1 .
Chess (King-Rook vs. King-Pawn): This dataset contains two classes: white-can-win ("won") and white-cannot-win ("nowin"). The classes are mostly balanced at 52% and 48%, respectively. There are 36 features and 3196 data points2 .
To share the data across clients, we used stratified splitting so that the ratio of the classes was the same for all clients. Moreover, the amount of data each client receives is the same as other clients. To address the uncertainty, we randomly performed this data-sharing schema 10 times with different seeds, and the result was averaged.
It's important to note that before dividing the data among clients, 1% of the data is set aside to be stored on the server side. This data, referred to as 𝐷 𝑠 in this paper, is used to identify the representative semantic tree.
Our model choice is Extremely Fast Decision Tree (EFDT) [19], which is the same for all clients. For stable results, we resorted to the River library in Python [24]. The parameters for EFDT are set to be the default parameters; only the binary_split is set to True. To construct the representative syntactic tree used in SynRoot and SynPath, the APTED library is utilized [20,21].
For the federated learning setting, we consider 4 clients and 200 rounds of communication between the clients and the server. Accordingly, each client's data is divided by 200 and fed in a streaming manner to clients' EFDT. This learning procedure is repeated for each strategy mentioned in 4.
In this section, we present the results obtained using the proposed method. We compare the result of the proposed method with different strategies against centralized and local learning. We present two tables, Tables 1 and 2, showing the accuracy of five strategies after some communication rounds for the mushroom and chess datasets, respectively. In almost all cases, the performance of the proposed strategies falls between the performance of local and centralized learning, as expected. These strategies benefit from aggregation, allowing them to access more information at each point compared to local learning. However, their access to information is still not as extensive as centralized learning. Then, we look deeper at the results on the mushroom dataset shown in Figure 2. We observe that the speed of performance improvement in the three methods presented is initially higher than that of local learning (refer to the dashed box in the lower left part of Figure 2). However, this difference decreases after several stages, eventually reaching less than 5% in the last rounds (see the dashed box in the upper right part of Figure 2). This suggests that a client with initially limited data cannot effectively compete with aggregated methods. With access to more data, the client may better understand the problem and achieve strong performance independently close to aggregated methods.
In all the experiments with the chess dataset, there are significant differences between the performance of the proposed methods and local learning performance. If you compare the dashed boxes in Figure 3, you'll notice that individual clients cannot achieve the same performance as aggregated methods even after 200 rounds. However, similar to the results of the mushroom dataset, the performance of the aggregated methods improves quickly in the initial rounds in this dataset as well.
This paper introduces a framework for horizontal federated learning using an Extremely Fast Decision Tree (EFDT) as the underlying model and streaming data on the client side. We propose three strategies to aggregate this type of underlying method. With our strategies, you can merge the information on multiple EFDTs at each round, which helps to enhance the performance at the client level. We also insist on having only one tree on the client side because a single (shallow) tree is inherently explainable. We avoid using black-box models due to concerns about using post-hoc explanation methods. We compared these three strategies with local and centralized learning. All three strategies produce similar results, and their performance is higher than local learning and close (yet low) to centralized learning. Experiments show that although, in some cases, the performance of the proposed methods might not differ too much from local learning after some rounds, they always grow very fast in the first rounds.
The work was carried out with support from The Knowledge Foundation and from Vinnova (Sweden's innovation agency) through the Vehicle Strategic Research and Innovation Programme, FFI.