A differentially private distributed collaborative XGBoost method

1.   Introduction

With the rapid development of information and communication technologies including AI, Internet of Things (IoT) ^[1,2,3], and bioinformatics, mining and analyzing valuable information from real-world medical data has been successfully applied in various healthcare scenarios, such as auxiliary diagnosis, health monitoring, disease classification and prediction ^[4], and so on.

For multiple healthcare participants, there is a strong need to collaboratively build accurate models for disease classification due to limited local data of each participant. However, healthcare data often contains sensitive information of users and improper sharing may discourse users' privacy. Currently, for analysis of large scale medical data ^[5,6,7], distributed ensemble learning provides a possible solution for different participants to collaborate in building high-quality learning models in condition of preserving users' privacy. Therefore, the development of privacy-preserving distributed ensemble learning algorithms is in high demand.

In distributed ensemble learning scenarios, the participants in each task are usually fixed. The initial assumption behind is that all the participants equally contribute to the training process ^[8] and provide the local models with same level of quality. However, this assumption does not correspond to reality. In practice, participants with low quality local models can seriously affect the accuracy of the global model. Correctly selecting participants with high quality local models is crucial for the stability of the learning scenario and the fast convergence of the global model. Reputation based participant selection schemes can be applied for solving this problem. However, many existing reputation-based participant selection schemes adopt multi-weight subjective logic models to compute reputation ^[9], which may introduce the unfair subjective judgment and lead to inaccurate reputation evaluation.

Based on the above analysis, our motivation of this paper is to design a trustworthy reputation evaluation scheme for selecting proper participants and then build a privacy preserving ensemble learning algorithm for disease classification.

Leveraging the XGBoost (eXtreme Gradient Boosting) algorithm, a DP-DCXGBoost method is proposed in the paper, which is under a distributed collaborative learning scenario consisting of a central server and a set of healthcare participants. The contributions of this paper can be summarized as follows:

(1) A reputation based participant selection algorithm is designed, which evaluates the contribution of a participant's final local model to the global model to alleviate the negative effects of participants with low quality local model and improve the accuracy of the global model.

(2) The central server and the selected participants adopts the vertical learning process to collaboratively train a global classification model based on XGBoost. First-order gradients and second-order gradients are interchanged. Local samples of each participant are divided into buckets and local differential privacy is applied to preserve the data privacy of buckets.

(3) Experiments were conducted on two real datasets, and the findings exhibit the efficacy of the proposed method.

The rest of the paper is structured as follows: In Section 2, related work is discussed. Section 3 provides a review of preliminary knowledge about local differential privacy (LDP) and XGBoost algorithm. The design of the DP-DCXGBoost method is presented in Section 4. In Section 5, the results of experiments conducted on two real datasets are analyzed. Section 6 concludes the paper.

2.   Related work

2.1.   Ensemble learning based disease classification and prediction

By analyzing large amounts of medical data, machine learning algorithms can identify potential disease patterns and risk factors, for auxiliary disease classification and prediction. This improves not only the probability of early diagnosis for better personalized treatment, but also the survival rate and the life quality of patients.

Wibawa et al. ^[10] used correlation based feature selection strategy to select appropriate features, and applied AdaBoost to improve the diagnosis of chronic kidney disease. KNN, Naive Bayes, and Support Vector Machine algorithms are chosen as the base classifiers in the designed ensemble learning framework. Yang et al. ^[11] constructed a two-stage learning model based on stacking ensemble learning, which combines several complementary base classifiers to achieve better classification performance. Mahesh et al. ^[12] adopted six supervised machine learning algorithms as base classifiers to construct ensemble learning models on the breast cancer dataset. They compared the final ensemble classifier with those base classifiers and observed a significant improvement of the ensemble classifier with the evaluation metrics of accuracy and recall. Kannan ^[13] introduced a novel ensemble model for early prediction of heart disease using random subspace and the RSS-KNN algorithm. An outlier removal mechanism is first designed to eliminated noise and outliers in the dataset. Subsequently, the extracted features recognized by RSS are input into the KNN algorithm for accurate classification of heart disease.

2.2.   Differentially private ensemble learning

In recent years, researchers have applied various privacy preservation methods for privacy preserving ensemble learning, including data anonymization, data encryption, and data perturbation. Differential privacy ^[14] is an important method of data perturbation with strong mathematic guarantee. The basic principle of differential privacy is to add a certain amount of noise to the original data without affecting the data statistics, so that attackers cannot infer personal information from the noisy data.

Li et al. ^[15] proposed a privacy-preserving gradient boosting decision tree (GBDT) training algorithm, which achieved tighter sensitivity bound and efficient privacy budget allocation. Specifically, they designed gradient-based data filtering to ensure sensitivity bound and further introduced geometric leaf clipping to achieve tighter sensitivity bound. Chaudhary et al. ^[16] presented a differentially private ensemble learning classification model, while maintaining its utility and accuracy, which evaluated the medical health record and classified the patient's medical disease from the given data in a way that required very little human involvement. Li et al. ^[17] proposed a differentially private ensemble learning algorithm for classification. The bag of little bootstrap technique and the Jaccard similarity coefficient are first adopted to generate training datasets. And then the differentially private base classifiers are constructed and selected based on some criterion functions with corresponding weights. The final result of the classification is obtained by a weighted voting scheme. Tian et al. ^[18] proposed a framework named FederBoost for private federated learning of GBDT. The designed framework supported both horizontally and vertically partitioned data. The whole training process of GBDT relies on the ordering of the data instead of the values. Zhao et al. ^[19] designed a privacy preserving GBDT schema that allows differentially private regression trees trained by different data owners, to be sequentially integrated into a GBDT model. However, both the internal nodes and the leaf nodes in the decision tree were perturbed with equal noise, which seriously degraded the performance of the model. Besides, the training order of the participants in the proposed schema was fixed and did not consider the impact of computational resources of the participants.

3.   Preliminaries

3.1.   Local differential privacy

Centralized differential privacy requires a trusted third-party data collector to collect user data and perform privacy processing on it. LDP, on the other hand, assumes that the server is untrustworthy and that each user can process individual data independently. That is, privacy processing is shifted from the data collector to the user side, without the intervention of a trusted third party.

Definition 1 ($\varepsilon$-LDP) Given a random function $f$, for any two input tuples $t, t' \in Dom\left( f \right)$, and any possible output ${t^*}$ of function $f$, if:

Then, the random function $f$ is said to satisfy $\varepsilon$-LDP, where $\varepsilon$ is the parameter of privacy budget. It can be seen from above definition, $\varepsilon$-LDP controls the similarity of the output results of any two records, so as to ensure that the random function $f$ satisfies $\varepsilon$-LDP.

The two combination theorems of $\varepsilon$-LDP are given as follows:

Theorem 1 (Serial combination theorem). Suppose there is a set of random algorithms $\left\{ {{M_1}, {M_2}, ..., {M_n}} \right\}$, each of ${M_i}\left( {1 \leqslant i \leqslant n} \right)$ satisfies ${\varepsilon _i}$-LDP on the dataset $D$. Then the set of ${M_i}$ sequence privacy mechanisms provides $\left( {\sum\limits_{i = 1}^n {{\varepsilon _i}} } \right)$-LDP.

Theorem 2 (Parallel combination theorem). Suppose dataset $D$ can be divided into a series of independent and non-overlapped subsets $\left\{ {{D_1}, {D_2}, ..., {D_n}} \right\}$ and there is a set of random algorithms $\left\{ {{M_1}, {M_2}, ..., {M_n}} \right\}$. If each privacy mechanism ${M_i}\left( {1 \leqslant i \leqslant n} \right)$ satisfies ${\varepsilon _i}$-LDP on ${D_i}\left( {1 \leqslant i \leqslant n} \right)$, then the set of randomized algorithm can achieve ${\text{max}}\left\{ {{\varepsilon _i}} \right\}$-LDP on $D$.

3.2.   XGBoost algorithm

XGBoost is a machine learning algorithm used for regression, classification, and ranking. It is an efficient implementation of GBDT that can operate on large-scale datasets and exhibits strong generalization capabilities. The core of the algorithm lies in using multiple weak learners to construct a strong learner by gradually optimizing the loss function. Specifically, each weak learner is a decision tree model, and XGBoost employs a custom loss function that allows simultaneous consideration of error magnitude and complexity when building each tree. Additionally, XGBoost utilizes a regularization technique, namely L1 and L2 regularization, to prevent overfitting.

At each iteration, XGBoost computes the gradient and Hessian matrix for each sample, which are used to build the decision tree. Then, based on the gradient and Hessian matrix of the loss function, it calculates the split gain for each node to determine which feature and threshold can minimize the loss function. Finally, a new decision tree is generated by greedy selecting the split points. After a certain number of iterations, XGBoost combines multiple decision trees to form a strong learner.

4.   The DP-DCXGBoost method

4.1.   Framework

In this paper, we consider a distributed collaborative learning scenario consisting of a central server and a set of healthcare participants. The central server is honest but curious. While each healthcare participant owns an unshared private local dataset, the dataset is vertically partitioned according to features. The goal of the DP-DCXGBoost method is twofold: (1) To allow the participants to collaboratively train the disease classification model without disclosing the privacy information of each participant; and (2) participants with more positive contributions are more likely selected for collaborative learning. The overall framework of the proposed method is shown in Figure 1.

For the first time of distributed collaborative model learning task, the central server randomly selects some of the participants to release the initialized global model parameters, and the selected participants receive the model parameters and perform the local model training based on the corresponding private data. When one round of local model training is completed, each participant uploads the local model parameters to the central server. The central server searches for the global optimal split point according to the aggregation of local model parameters uploaded by the participants. The optimal split point is then sent down to the participants for the next round of iterations, and the model training task is completed when the global model parameters have converged or the number of iterations have reached the maximum number. After the task is completed, the central server evaluates the final local model quality of each participant and adjusts the reputation of each participant. In subsequent model training tasks, the central server will prioritize the participants with higher reputation for better collaborative learning.

4.2.   Reputation based participant selection

Aiming at the problem that the performance of the global model suffers due to the differences in model quality of each participant in distributed learning, the DP-DCXGBoost method designs a participant selection algorithm based on the reputation of participant, which is calculated according to the local model quality of the participant.

Supposing there is a central server and $n$ participants, a collaborative training task requires $m(m < n)$ participants to take part in, and each task trains up to $T$ decision trees to obtain the final XGBoost global model. After a task is completed, the central server assigns different reputation values to the participants based on the quality of their final local models. Before the start of the next task, the central server selects suitable participants to join the task based on their reputation. Since there is no a priori knowledge about the local model quality of the participants, the central server initializes the reputation of each participant with the same constant value.

The central server also maintains a test dataset locally, and scores participants based on the final models it receives. This scoring is done by comparing the difference of the two global models whether a certain participant's final local model is aggregated or not. The scoring function is defined as follows:

where ${D_s}$ is the test dataset, ${G_k}({D_s})$ represents the prediction accuracy of the global model (aggregating the participant $i's$ final local model) on the test dataset in the $kth$ task, while $G_k^{ - i}({D_s})$ denotes the prediction accuracy of the global model without aggregating the participant $i's$ final local model, and ${E_{i, k}}$ is score value. Additionally, a quality metric is introduced to normalize the participant's score into quality value, which takes the reciprocal of ${E_{i, k}}$ and normalizes it to obtain the participant's model quality metric, denoted by ${l_{i, k}}$:

where $m$ is the number of candidate participants. It can be noted that ${l_{i, k}}$ is a real number belonging to (0, 1) and $\sum\nolimits_{i = 1}^m {{l_{i, k}} = 1}$. After evaluating the final models of the participants, the selection of participants is based on their historical reputation. The reputation of participants gradually increases if they consistently provide high quality models. However, if a participant contributes a poor model in a single training task, their reputation will rapidly decrease. The evaluation strategy also provides incentives for each participant to offer high quality local model in each training task.

The DP-DCXGBoost method adopts the Richard's Curve to update the participant's reputation, which is defined as follows:

where $A$ represents the lower asymptotic bound of the curve, $K$ is the upper asymptotic bound of the curve, $B$ is the exponential growth rate of the curve, $D$ determines the maximum growth of the curve, $Q$ is related to the initial value ${R_{i, k}}(0)$ and typically in [0.1, 2], $C$ is a constant value and typically set to 1, and $v$ determines the asymptotic maximum growth point.

At the end of each task, after the central server has evaluated the quality of the participant's local model, the participant's reputation is updated according to formula 4, where the output ${R_{i, k}}(l_{i, k}^{'}) \in (0, 1)$ is the updated reputation value of the $ith$ participant after completing the $kth$ task. The input variable $l_{i, k}^{'}$ of the Richard curve is calculated according to the following formula:

where $n$ is the number of participants, ${x_{i, j}}{\text{ = }}1$ indicates that participant $i$ takes part in the $jth$ model training task, otherwise ${x_{i, j}}{\text{ = 0}}$. When evaluating the reputation of participant $i$ in the $kth$ task, a basic idea is to sum the indicators of the local model quality that this participant owns in the previous $k - 1$ tasks. It is important to note that the increase gradient of reputation and the decrease gradient of reputation should not be measured in the same way. In particular, the decreased gradient of reputation for participants should be greater than the increased gradient of reputation.

After considering the reputation of the participants, the central server selects the participants with higher reputation for the next training task. The pseudo code of reputation based participant selection algorithm is shown in Algorithm 1.

4.3.   Model training and prediction

For each model training task, the central server first selects a set of candidate participants, denoted by $Par = \{ {P_1}, {P_2}, ..., {P_m}\}$ using algorithm 1. In each task, both the central server and participants owns different feature sets $\{{X}_{c, }\text{ }{X}_{1, }\text{ }{X}_{2}, \mathrm{...}, \text{ }{X}_{m}\}$. Each feature set ${X_i}$ consists of $K$ features denoted by ${X_i} = [{x^1}, {x^2}, ...{x^K}]$, and each feature ${x^k}$ contains all $r$ data samples ${x^k} = [x_1^k, x_2^k, ..., x_r^k]$. However, only the central server has the class labels $y = [{y_1}, {y_{2, }}...{y_r}]$ for these $r$ samples.

During the model training phase of the DP-DCXGBoost method, the goal is to obtain the final XGBoost ensemble model. To preserve data privacy during the vertically federated training process, both the central server and the participants follow the learning strategies:

(1) First-order gradient ${g_i}$ and second-order gradient ${h_i}$ for samples are calculated based on the sample class labels ${y_i}$. When seeking the global optimal splitting point in the training process, only the central server possesses the sample class label values, while participants cannot have access. If the central server was to directly transmit ${g_i}$ and ${h_i}$ to the participants, the participants could calculate the optimal splitting point for their local data using the information gain formula. However, if participants have knowledge of ${g_i}$ and ${h_i}$, they could easily infer the class label values, thereby compromising data privacy. Therefore, the central server should send ${g_i}$ and ${h_i}$ in a privacy preserving way. Initially, the central server independently constructs the first decision tree, with no involvement of the participants. Then, participants can only access to the gradients ${g_i}$ and ${h_i}$ after residual update in the first tree. This ensures that malicious participants cannot infer the class label information.

(2) For each feature, participants sort the samples based on their feature values and place these samples into $l$ buckets. After receiving gradient aggregation information from the participants regarding the buckets, the central server knows only the relative order of bucket sizes and has no knowledge about the order of samples within each bucket. However, it is possible for information to leak between two samples in different buckets. The DP-DCXGBoost method uses LDP to add noise for each bucket, ensuring the data privacy of participants.

The training process of the DP-DCXGBoost method is described as follows:

1. The central server initializes parameters, calculates the first-order gradient ${g_i}$ and second-order gradient ${h_i}$ for each sample, and uses the approximate split-finding algorithm to independently generate the first decision tree;

2. Based on the first decision tree's leaf node weights, the central server updates the values of ${y_i}$, the gradients ${g_i}$ and ${h_i}$ for the samples. Then, ${g_i}$ and ${h_i}$ are sent to $m$ participants.

3. Each participant receives ${g_i}$ and ${h_i}$, divides samples into buckets based on candidate quantile points for each feature, adds differential privacy noise to each bucket, and calculates the ${G_{kv}}$ and ${H_{kv}}$, which are the sum of ${g_i}$ and ${h_i}$ for each bucket, respectively. These two sum values are then sent back to the central server.

4. The central server traverses all the features and thresholds, computes the feature ${k_{opt}}$ and the threshold ${v_{opt}}$ corresponding to the globally optimal split point, and sends them to the participants. A participant splits the current sample space based on the values of ${k_{opt}}$ and ${v_{opt}}$. Due to the separation on features, a participant is required to store specific information for each split, generates a lookup table of node split information [feature $k$, threshold $v$] with a unique sample number ID as an index of the table based on ${k_{opt}}$ and ${v_{opt}}$, in order to predict new samples later. A participant then sends the sample number ID and $\{ {G_k}, {H_k}\} _{k = 1}^K$ to the central server.

5. The central server splits the current node based on the received $\{ {G_k}, {H_k}\} _{k = 1}^K$ from the participants and calculates the leaf node weight. Afterward, it associates the current node with [participant ID, sample ID].

6. Repeat this process until the global model converges or the maximum number of decision trees for iteration is reached. Stop splitting and obtain the final model.

7. The central server evaluates the quality of the local models provided by each participant and updates the reputation values.

From the perspective of a participant, upon receiving ${g_i}$ and ${h_i}$, a participant sorts the samples and places them into $l$ buckets based on candidate quantile points for each feature. Then, differential privacy noise is added to each bucket. Specifically, for a sample initially assigned to the a bucket, there is a probability $p = \frac{{{e^\varepsilon }}}{{{e^\varepsilon } + l - 1}}$ that the sample remains in the same bucket, and a probability $q = \frac{1}{{{e^\varepsilon } + l - 1}}$ that it is moved to another bucket. Subsequently, they calculate the sums $G_{kv}^m$ and $H_{kv}^m$ of ${g_i}$ and ${h_i}$ within each bucket and send them to the central server. The participant's execution process is illustrated in Algorithm 2.

From the central server's perspective, the central server independently generates a decision tree and calculates ${g_i}$ and ${h_i}$ for each sample. First, locally compute aggregation information ${G_{kv}}$ and ${H_{kv}}$ for different bins based on each feature's candidate quantile points. Then, send ${g_i}$ and ${h_i}$ to the participants. After receiving the gradient aggregation information from the participants, the central server calculates the local optimal split points for the participants. Next, it compares the information gain of the global optimal split point with the local optimal split points and selects the global optimal split point. The process is illustrated in Algorithm 3.

In the prediction process, each participant has only complete information about the local feature split points, and multiple participants must work together to determine the leaf nodes of the sample in the prediction process. Initially, when a sample enters the root node of the first decision tree, the central server queries the [participant ID, sample ID] associated with the current node, and then sends a message to the corresponding participant to ask whether this sample should enter the left subtree or the right subtree. After receiving the message, the corresponding participant compares the sample value with the threshold value in the local split information lookup table, and sends the decision information (whether the sample should enter the left subtree or not) to the central server. The central server then allows the sample to enter the related subtree. The above steps are repeated until the sample reaches a leaf node. After determining the leaf node of the sample, the central server calculates the predicted value of the sample based on the weights of the leaf nodes of each tree.

Supposing $d$ is the max depth of decision trees, $T$ is the number of decision trees, ${\left\| x \right\|_0}$ is the number of non-missing items in the whole training dataset, since quantile sketch strategy is applied in the training process, the time complexity of training process is $O(dT{\left\| x \right\|_0} + {\left\| x \right\|_0}\log Kmr)$, where $K$ is the number of features, $m$ is the number of selected participants, and $r$ is the number of samples on each participant.

4.4.   Privacy analysis

In this section, we briefly prove that the DP-DCXGBoost method satisfies $\varepsilon$-differential privacy.

Initially, we give the definition of neighbor data of two local samples $x = [{x_1}, {x_2}, ..., {x_k}]$ and $x' = [x_1^{'}, x_2^{'}, ..., x_k^i]$, respectively. If there is only one element difference between $x$ and $x'$, then $x$ and $x'$ is called neighbor data.

In the distributed collaborative training phase, after each participant receives ${g_i}$ and ${h_i}$, the samples are sorted and put into $l$ buckets according to the candidate quantile points of each feature, and differential privacy noise is added for each bucket. For any two samples $x$, $x'$ and a bucket $B$, it can be obtained:

Therefore, the proposed method satisfies $\varepsilon$-differential privacy, where $\Pr [bucketize(x) \in B]$ denotes the probability that sample $x$ is placed in the bucket $B$.

5.   Experiments

5.1.   Experimental settings

We implemented the proposed method in Python programming language (version 3.9), and conducted experiments on a machine with Intel (R) i7-11700 CPU @ 2.50GHz, 16G RAM, 512 SSD + 1T hardware configuration and a 64-bit Windows 10 operating system.

We utilized two real datasets, Cardiovascular diseases dataset from Kaggle public database ^[20] and Diabetes 130-US hospitals for years 1999–2008 dataset from UCI public database ^[21]. Table 1 outlines the statistics of the two datasets.

5.2.   Experimental results

In order to test the performance of the proposed method, three groups of comparative experiments are carried out. For each dataset above, it is divided into two parts for training and testing. The training part contains two thirds of the samples and the testing part contains the remaining.

Figure 2(a), (b) show the area under curve (AUC) of the feature values trained using the Cardiovascular diseases dataset and Diabetes diseases dataset under different number of buckets, respectively. DCXGBoost is the non-privacy-preserving version of the proposed method, which removes the differential privacy noise. Moreover, XGBoost is run in a centralized environment using the same dataset and the result is adopted as a baseline for comparison with DCXGBoost. The results show that the change in AUC varies little as the number of buckets increases. Furthermore, DCXGBoost achieves almost the same AUC value as that of XGBoost with the same number of buckets. Vibrations can be observed with DCXGBoost in Figure 2 when the bucket number is small. One possible reason is that buckets are used for samples division and sort, the efficiency of parallel computing is not high or stable when the bucket number is small.

In order to verify the effect of privacy budget $\varepsilon$ to the proposed method, the number of buckets with the best AUC is fixed. The DP-DCXGBoost method is compared with FedDPXGB (Federal Differential Privacy XGBoost) ^[22] under different privacy budgets, and the result of DCXGBoost is used as a base line. The experimental results on the cardiovascular disease dataset and the diabetes disease dataset are shown in Figure 3(a), (b), respectively. It can be seen from Figure 3 that with the increase of privacy budget, the AUC value of both DP-DCXGBoost and FedDPXGB display an increasing trend. This result is expected because the error generated by differential privacy decreases as privacy budget increases. Furthermore, the AUC value of both DP-DCXGBoost and FedDPXGB become stabilize when privacy budget is greater than 1.25. When the privacy budget is greater than 0.9, the performance of the proposed method achieves better than that of the FedDPXGB method.

The efficiency of the DP-DCXGBoost method can also be influenced by the indicator of running time. To investigate running time under different numbers of participants, the DP-DCXGBoost method is compared with DCXGBoost and FedDPXGB. The experimental results for the Cardiovascular Diseases dataset and the Diabetes Diseases dataset are shown in Figure 4(a), (b), respectively. The results show that the running time of all three methods increases as the number of participants increases. The running time of the DCXGboost method is always lower than that of the DP-DCXGboost method. Besides, the running tiem of the FedDPXGB method is better than that of DP-DCXGboost under the same conditions, which is due to the fact that the proposed method spends some time on the reputation based participant selection before model training. As a whole, the proposed method meets the design expectations.

6.   Conclusions

In this paper, we propose the DP-DCXGBoost method to address the privacy preserving collaborative learning problem in the scenario where participants' medical data is vertically partitioned. To alleviate the negative effects of participants with low quality local model and improve the accuracy of the global model, a reputation based participant selection algorithm is first designed, which evaluates the contribution of a participant's final local model to the global model. Then, the central server and the selected participants, collaboratively train a global classification model based on XGBoost. Local samples of each participant are divided into buckets and local differential privacy is applied preserve the data privacy of buckets. Experimental results for two real disease datasets validate the effectiveness of the proposed method.

In the future, we plan to consider the selection of participants based on their communication conditions and computational resources and improve the efficiency of participant selection algorithm. In addition, the proposed method does not introduce noise when the gradients of the participants is uploaded to the central server. We will try to apply mixed differential privacy technology to the proposed method.

Use of AI tools declaration

The authors declare that they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

This research was funded by "Key Research and Development Program of Shaanxi Province", grant number 2021GY-090.

Conflict of interest

The authors declare there is no conflict of interest.