Explainable Artificial Intelligence (XAI) is crucial in ensuring transparency, accountability, and trust in machine learning models, especially in applications involving high-stakes decision-making. This paper focuses on addressing the research gap in federated learning (FL), specifically emphasizing the use of inherently interpretable underlying models. While most FL frameworks rely on complex, black-box models such as Artificial Neural Networks (ANNs), we propose using Decision Tree (DT) classifiers to maintain explainability. More specifically, we introduce a novel framework for horizontal federated learning using Extremely Fast Decision Trees (EFDTs) with streaming data on the client side. Our approach involves aggregating clients' EFDTs on the server side without centralizing raw data, and the training process occurs on the clients' sides. We outline three aggregation strategies and demonstrate that our methods outperform local models and achieve performance levels close to centralized models while retaining inherent explainability.
CEUR ceur-ws.org
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 dificult 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,
Lithunia
providing only surface-level insights that might not be trustw1o,r2]t.hFyu[rthermore, they
are vulnerable to adversarial attacks that can manipulate the explanations without changing
the model’s predictions3,[
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 eficient 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 example5,][used feature importance methods to add explainability to their models, whi6l]ep[resented 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 data7,[
The typical approach in ML is batch learning, also known as ofline 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 followResl:ated worksummarizes previous research intersection of FL and tree-based methods. ThenPr,ienliminarie,swe introduce some basic concepts of incremental decision trees and tree similarity methods. The proposed method is described inMethodology. The experimental setup is found in SectiEoxnperimental Setup followed by the result iRnesults. Finally, we draw some conclusions iCnonclusion
Within this distributed learning paradigm, horizontal federated learning (HFL) and vertical federated learning (VFL) represent two approaches. Each client has diferent data samples in HFL, but the feature set is the same. VFL, however, uses data samples shared among clients with diferent features9[].
SecureBoost1[0] 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 [
There is also research on the conjugation of tree-based models and1H4]FLp.r[oposed 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)1[
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 an1d6]FaLn.[d [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 Hoefding Tree (HT) [ 18] is one of the fundamental research studies that proposed the Incremental Decision Tree (IDT) for eficient data stream mining. The HT uses the Hoefding 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 varwiiatbhlerange is expressed as follows:
2 ln (1/ ) = , (1)
√ 2 where represents the margin of err oirs, the confidence level, and is the number of observations.
In 2018, [19] proposed the Hoefding 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 diferent 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 diferent 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 use2d0[, 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 distribution2s3,[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 diferent aggregation strategies into contrast.
Clinets’s sides (training)
Server’s side (aggregation) C1 C2 Ck ...
Assume we have clients 1 ⋯ where each one has access to a diferent streaming dataset 1 ⋯ . Given that we are in a horizontal federated setting, the feature set is the same for all datasets1 ⋯ .
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 data)s.eAts( 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 th−e ℎ 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 diferent strategies for the server side. However, the aggregation process remains consistent across all strategies, but each strategy difers 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 contain s antable. As part of the aggregation process, we merge the tables of nodes along the same path into two trees. Alg1ooruithlimnes this method in detail. Specifically, when two nodes from two trees share common parents, they can be efectively combined, even if they have opted for diferent features. This is possible because the table contains aggregated information before the split.
Algorithm 1 Aggregation Function
As mentioned earlier, the strategies difer 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 Algorithm2. 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 Algorith3m, the server uses a proxy data set,,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) 1: Input: List of clients’ tre s =
e [ 1, 2, … , ]
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 (Algori4t)h. mAfter updating all trees, the server will pass the updated trees to their owners.
Algorithm 4 Individual strategy (Ind)
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 po1.ints
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 p2o.ints
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 diferent 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 toinasthis paper, is used to identify the representative semantic tree.
Our model choice is Extremely Fast Decision Tree (EFD1T9)][, which is the same for all clients. For stable results, we resorted to the River library in P2y4t].hTohne[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 in4.
In this section, we present the results obtained using the proposed method. We compare the result of the proposed method with diferent strategies against centralized and local learning. We present two tables, Tabl1esand 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. 1https://archive.ics.uci.edu/dataset/73/mushroom 2https://archive.ics.uci.edu/dataset/22/chess+king+rook+vs+king+pawn
Then, we look deeper at the results on the mushroom dataset shown in 2F.igWuereobserve 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 of2F).igHuorweever, this diference decreases after several stages, eventually reaching less than 5% in the last rounds (see the dashed box in the upper right part of Fig2)u.rTehis suggests that a client with initially limited data cannot efectively 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 diferences between the performance of the proposed methods and local learning performance. If you compare the dashed boxes in Figur3e, 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. Type Centralized Local Ind Syn Sem Type Centralized Local Ind Syn Sem 0 25 50 75 100 #round 125 150 175 200
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 difer 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. federated tree boosting framework based on order-preserving desensitization, arXiv preprint arXiv:2210.01318 (2022). [12] Y. Liu, Z. Ma, X. Liu, S. Ma, S. Nepal, R. H. Deng, K. Ren, Boosting privately: Federated extreme gradient boosting for mobile crowdsensing, in: 2020 IEEE 40th international conference on distributed computing systems (ICDCS), IEEE, 2020, pp. 1–11. [13] F. Fu, Y. Shao, L. Yu, J. Jiang, H. Xue, Y. Tao, B. Cui, Vf2boost: Very fast vertical federated gradient boosting for cross-enterprise learning, in: Proceedings of the 2021 International Conference on Management of Data, 2021, pp. 563–576. [14] L. Zhao, L. Ni, S. Hu, Y. Chen, P. Zhou, F. Xiao, L. Wu, Inprivate digging: Enabling tree-based distributed data mining with diferential privacy, in: IEEE INFOCOM 2018-IEEE Conference on Computer Communications, IEEE, 2018, pp. 2087–2095. [15] M. Gencturk, A. A. Sinaci, N. K. Cicekli, Bofrf: A novel boosting-based federated random forest algorithm on horizontally partitioned data, IEEE Access 10 (2022) 89835–89851. [16] Z. Han, C. Ge, B. Wu, Z. Liu, Lightweight privacy-preserving federated incremental decision trees, IEEE Transactions on Services Computing (2022). [17] S. Sharma, K. Arora, P. S. Thakur, Horizontal federating decision tree learning from data streams: Building intelligence in iot edge networks, in: 2022 IEEE 8th World Forum on Internet of Things (WF-IoT), IEEE, 2022, pp. 1–6. [18] P. Domingos, G. Hulten, Mining high-speed data streams, in: Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, 2000, pp. 71–80. [19] C. Manapragada, G. I. Webb, M. Salehi, Extremely fast decision tree, in: Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2018, pp. 1953–1962. [20] M. Pawlik, N. Augsten, Eficient computation of the tree edit distance, ACM Transactions on Database Systems (TODS) 40 (2015) 1–40. [21] M. Pawlik, N. Augsten, Tree edit distance: Robust and memory-eficient, Information
Systems 56 (2016) 157–173. [22] A. I. Weinberg, M. Last, Selecting a representative decision tree from an ensemble of decision-tree models for fast big data classification, Journal of Big Data 6 (2019) 1–17. [23] R. Miglio, G. Sofritti, The comparison between classification trees through proximity measures, Computational statistics & data analysis 45 (2004) 577–593. [24] J. Montiel, M. Halford, S. M. Mastelini, G. Bolmier, R. Sourty, R. Vaysse, A. Zouitine, H. M.
Gomes, J. Read, T. Abdessalem, et al., River: machine learning for streaming data in python (2021).