Privacy-Preserving Stacking with Application to Cross-organizational Diabetes Prediction

1 Introduction

In recent years, data privacy has become a serious concern in both academia and industry [Dwork et al., 2006; Chaudhuri et al., 2011; Dwork and Roth, 2014; Abadi et al., 2016]. There are now privacy laws, such as Europe's General Data Protection Regulation (GDPR), which regulates the protection of private data and restricts data transmission between organizations. These raise challenges for crossorganizational machine learning [Pathak et al., 2010; Hamm et al., 2016; Papernot et al., 2017; Xie et al., 2017], in which data have to be distributed to different organizations, and the learning model needs to make predictions in private.

A number of approaches have been proposed to ensure privacy protection. In machine learning, differential privacy [Dwork and Roth, 2014] is often used to allow data be exchanged among organizations. To design a differentially private algorithm, carefully designed noise is usually added to the original data to disambiguate the algorithms. Many standard learning algorithms have been extended for differential privacy. These include logistic regression [Chaudhuri et al., 2011], trees [Emekc¸i et al., 2007; Fong and Weber-Jahnke, 2012], and deep networks [Shokri and Shmatikov, 2015; Abadi et al., 2016]. In particular, linear models are simple and easy to understand, and their differentially private variants (such as privacy-preserving logistic regression (PLR)) [Chaudhuri et al., 2011]) have rigorous theoretical guarantees [Chaudhuri et al., 2011; Bassily et al., 2014; Hamm et al., 2016; Kasiviswanathan and Jin, 2016]. However, the injection of noise often degrades prediction performance.

1 Correspondence to X. Guo at guoxiawei@4paradigm.com

Ensemble learning can often signficantly improve the performance of a single learning model [Zhou, 2012]. Popular examples include bagging [Breiman, 1996a], boosting [Friedman et al., 2000], and stacking [Wolpert, 1992]. These motivate us to develop an ensemble-based method which can benefit from data protection, while enjoying good prediction performance. Bagging and boosting are based on partitioning of training samples, and use pre-defined rules (majority or weighted voting) to combine predictions from models trained on different partitions. Bagging improves learning performance by reducing the variance. Boosting, on the other hand, is useful in converting weak models to a strong one. However, the logistic regression model, which is the focus in this paper, often has good performance in many applications, and is a relatively strong classifier. Besides, it is a convex model and relatively stable.

Thus, in this paper, we focus on stacking. While stacking also partitions the training data, this can be based on either samples [Breiman, 1996b; Smyth and Wolpert, 1999; Ozay and Vural, 2012] or features [Boyd et al., 2011]. Multiple low-level models are then learned on the different data partitions, and a high-level model (typically, a logistic regression model) is used to combine their predictions. By combining with PLR, we show how differential privacy can be ensured in stacking. Besides, when the importance of features is known a priori, they can be easily incorporated in feature-based partitioning. We further analyze the learning guarantee of sample-based and feature-based stacking, and show theoretically that feature-based partitioning can have lower sample complexity (than sample-based partitioning), and thus better performance. By adapting the feature importance, its learning performance can be further boosted.

To demonstrate the superiority of the proposed method, we perform experiments on two benchmark data sets (MNIST and NEWS20). Empirical results confirm that feature-based stacking performs better than sample-based stacking. It is also better than directly using PLR on the training data set. Besides, the prediction performance is further boosted when feature importance is used. Finally, we apply the proposed approach for cross-organizational diabetes prediction in the transfer learning setting. The experiment is performed on the RUIJIN data set, which contains over ten thousands diabetes records from across China. Results show significantly improved diabetes prediction performance over the state-of-theart, while still protecting data privacy.

Notation. In the sequel, vectors are denoted by lowercase boldface, and (·)⊤ denotes transpose of a vector/matrix; σ(a) = exp(a)/(1+exp(a)) is the sigmoid function. A function g is µ-strongly convex if g(αw+(1-α)u) ≤ αg(w)+(1α)g(u) - µ2 α(1 - α)‖w - u‖2 for any α ∈ (0, 1).

2 RelatedWorks

2.1 Differential Privacy

Differential privacy [Dwork et al., 2006; Dwork and Roth, 2014] has been established as a rigorous standard to guarantee privacy for algorithms that access private data. Intuitively, given a privacy budget ϵ, an algorithm preserves ϵdifferentially privacy if changing one entry in the data set does not change the likelihood of any of the algorithm's output by more than ϵ. Formally, it is defined as follows.

Definition 1 ([Dwork et al., 2006]). A randomized mechanismM is ϵ-differentially private if for all output t of M and for all input data D1, D2 differing by one element, Pr(M(D1) = t) ≤ eϵ Pr(M(D2) = t).

To meet the ϵ-differentially privacy guarantee, careful perturbation or noise usually needs to be added to the learning algorithm. A smaller ϵ provides stricter privacy guarantee but at the expense of heavier noise, leading to larger performance deterioration [Chaudhuri et al., 2011; Bassily et al., 2014]. A relaxed version of ϵ-differentially private, called (ϵ, δ)- differentially privacy in which δ measures the loss in privacy, is proposed [Dwork and Roth, 2014]. However, we focus on the more stringent Definition 1 in this paper.

2.2 Privacy-preserving Logistic Regression (PLR)

Logistic regression has been popularly used in machine learning [Friedman et al., 2012]. Various differential privacy approaches have been developed for logistic regression. Examples include output perturbation [Dwork et al., 2006; Chaudhuri et al., 2011], gradient perturbation [Abadi et al., 2016] and objective perturbation [Chaudhuri et al., 2011; Bassily et al., 2014]. In particular, objective perturbation, which adds designed and random noise to the learning objective, has both privacy and learning guarantees as well as good empirical performance.

Privacy-preserving logistic regression (PLR) [Chaudhuri et al., 2011] is the state-of-the-art model based on objective perturbation. Given a data set D = {xi, yi}ni=1 , where xi ∈ Rd is the sample and yi the corresponding class label, we first consider the regularized risk minimization problem:

where w is a vector of the model parameter, ℓ(ˆ y, y) = log(1+ e-y ˆ y ) is the logistic loss (with predicted label ˆ y and given label y), g is the regularizer and λ ≥ 0 is a hyperparameter. To guarantee privacy, Chaudhuri et al. (2011) added two extra terms to (1), leading to:

where b is random noise drawn from h(b) ∝ exp(ϵ′/2‖b‖) with E(‖b‖) = 2d/ϵ′ , ϵ′ is a privacy budget modified from ϵ, and ∆ is a scalar depending on λ, n, ϵ. The whole PLR procedure is shown in Algorithm 1.

Algorithm 1 PLR: Privacy-preserving logistic regression.

Require: privacy budget ϵ, data set D; 1: ϵ′ = ϵ - log(1+ 1/2nλ + 1/16n2 λ2 ); 2: if ϵ′ > 0 then 3: ∆= 0; 4: else 5: ∆= (4n(exp(ϵ/4) -1))-1 -λ and ϵ′ = ϵ/2; 6: end if 7: scale ‖x‖ ≤ 1 for all x ∈ D; 8: pick a random vector b from h(b) ∝ exp (ϵ′ ‖b‖/2);

• 9: obtain w by solving (2);
• 10: return w.

Proposition 1 ([Chaudhuri et al., 2011]). If the regularizer g is strongly convex, Algorithm 1 provides ϵ-differential privacy.

While privacy guarantee is desirable, the resultant privacypreserving machine learning model may not have good learning performance. In practice, the performance typically degrades dramatically because of the introduction of noise [Chaudhuri et al., 2011; Rajkumar and Agarwal, 2012; Bassily et al., 2014; Shokri and Shmatikov, 2015]. Assume that samples from D are drawn i.i.d. from an underlying distribution P. Let L(w; P) = E(x,y)∼P [ℓ(w⊤x, y)] be the expected loss of the model. The following Proposition shows the number of samples needed for PLR to have comparable performance as a given baseline model.

Proposition 2 ([Chaudhuri et al., 2011]). Let g(·) = 1/2‖·‖2 , and v be a reference model parameter. Given δ > 0 and ϵg > 0, there exists a constant C1 such that when

w from Algorithm 1 meets Pr[L(w,P ) ≤L(v,P )+ϵg ] ≥1-δ.

2.3 Multi-Party Data Learning

Ensemble learning has been considered with differential privacy under multi-party data learning (MPL). The task is to combine predictors from multiple parties with privacy [Pathak et al., 2010]. Pathak et al. [2010] first proposed a specially designed protocol to privately combine multiple predictions. The performance is later surpassed by [Hamm et al., 2016; Papernot et al., 2017], which uses another classifier built on auxiliary unlabeled data. However, all these combination methods rely on extra, privacy-insensitive public data, which may not be always available. Moreover, the aggregated prediction may not be better than the best single party's prediction. There are also MPL methods that do not use ensemble learning. Rajkumar and Agarwal [2012] used stochastic gradient descent, and Xie et al. [2017] proposed a multi-task learning method. While these improve the performance of the previous ones based on aggregation, they gradually lose the privacy guarantee after more and more iterations.

3 Privacy-preserving Ensemble

In this section, we propose to improve the learning guarantee of PLR by ensemble learning [Zhou, 2012]. Popular examples include bagging [Breiman, 1996a], boosting [Friedman et al., 2000], and stacking [Wolpert, 1992]. Bagging and boosting are based on partitioning of training samples, and use pre-defined rules (majority or weighted voting) to combine predictions from models trained on different partitions. Bagging improves learning performance by reducing the variance. However, logistic regression is a convex model and relatively stable. Boosting, on the other hand, is useful in combining weak models to a strong one, while logistic regression is a relatively strong classifier and often has good performance in many applications.

3.1 Privacy-preserving Stacking with Sample Partitioning (SP)

We first consider using stacking with SP, and PLR is used as both the low-level and high-level models (Algorithm 2). As stacking does not impose restriction on the usage of classifiers on each partition of the training data, a simple combination of stacking and PLR can be used to provide privacy guarantee.

Algorithm 2 PST-S: Privacy-preserving stacking with SP.

Require: privacy budget ϵ, data set D;

• 1: partition D into disjoint sets Dl and Dh , for training of the lowlevel and high-level models, respectively;
• 2: partition samples in Dl to K disjoint sets {S1, . . . , SK};
• 3: for k = 1, . . . ,K do
• 4: train PLR (Algorithm 1) with privacy budget ϵ on Sk, and obtain the low-level model parameter wlk;
• 5: end for
• 6: construct meta-data setMs = {[σ(x⊤wl1);. . . ;σ(x⊤wlK)], y} using all samples {x, y} ∈ Dh ;
• 7: train PLR (Algorithm 1) with privacy budget ϵ on Ms , and obtain the high-level model parameter wh ;
• 8: return {wlk} and wh .

Proposition 3. If the regularizer g is strongly convex, Algorithm 2 provides ϵ-differential privacy.

However, while the high-level model can be better than any of the single low-level models [Dˇzeroski and ˇZenko, 2004], Algorithm 2 may not perform better than directly using PLR on the whole D for the following two reasons. First, each low-level model uses only Sk (step 4), which is about 1/K the size of D (assuming that the data set D is partitioned uniformly). This smaller sample size may not satisfy condition (3) in Proposition 2. Second, in many realworld applications, features are not of equal importance. For example, for diabetes prediction using the RUIJIN data set (Table 3), Glu120 and Glu0, which directly measure glucose levels in the blood, are more relevant than features such as age and number of children. However, during training of the low-level models, Algorithm 2 adds equal amounts of noise to all features. If we can add less noise to the more important features while keeping the same privacy guarantee, we are likely to get better learning performance.

3.2 Privacy-preserving Stacking with Feature Partitioning (FP)

To address the above problems, we propose to partition the data based on features instead of samples in training the lowlevel models. The proposed feature-based stacking approach is shown in Algorithm 3. Features are partitioned into K subsets, and Dl is split correspondingly into K disjoint sets {F1, . . . ,FK}. Obviously, as the number of training samples is not reduced, the sample size condition for learning performance guarantee is easier to be satisfied (details will be established in Theorem 4).

Algorithm 3 PST-F: Privacy-preserving stacking with FP.

Require: privacy budget ϵ, data set D, feature importance {qk}Kk=1 where qk ≥ 0 and ∑Kk=1 qk = 1; 2

• 1: partition D into disjoint sets Dl and Dh , for training of the lowlevel model and high-level model, respectively;
• 2: partitionDl toK disjoint sets {F1, . . . , FK} based on features;
• 3: ϵ′ = ϵ - ∑Kk=1 log(1+ q2k/2nλk + q4k/16n2 λ2k );
• 4: for k = 1, . . . ,K do
• 5: scale ‖x‖ ≤ qk for all x ∈ Fk;
• 6: if ϵ′ > 0 then
• 7: ∆k = 0 and ϵk = ϵ′ ;
• 8: else
• 9: ∆k = q2k/4n(exp(ϵqk/4)-1) -λk and ϵk = ϵ/2;
• 10: end if
• 11: pick a randombk from h(b) ∝ exp(ϵk‖b‖/2);
• 12: wlk = argminw 1/n ∑xi∈Fk ℓ(w⊤xi, yi) + b⊤k w/n + ∆‖w‖2/2 + λkgk(w);
• 13: end for
• 14: construct meta-data setMf = {[σ(x⊤(1)wl1),. . . ,σ(x⊤(K)wlK)], y} using all {x, y} ∈ Dh , where x(k) is a vector made from x by taking features covered by Fk;
• 15: train PLR (Algorithm 1) with privacy budget ϵ on Mf , and obtain the high-level model parameter wh ;
• 16: return {wlk} and wh .

When the relative importance of feature subsets is known, Algorithm 3 adds less noise to the more important features. Specifically, let the importance 3 of Fk (with dk features) be qk, where qk ≥ 0 and ∑k=1 qk = 1, and is independent with D. Assume that ϵ′ > 0 in step 6 (and thus ϵk = ϵ′ ). Recall from Section 2.2 that E(‖bk‖) = 2dk/ϵk = 2dk/ϵ′ . By scaling the samples in each Fk as in step 5, the injected noise level in Fk is given by E(‖bk‖)/‖x‖ = 2dk/ϵ′ qk. This is thus inversely proportional to the importance qk.

3 When feature importance is not known, q1 = · · · = qK = 1/K.

Remark 1. In the special case where only one feature group has nonzero importance, Algorithm 3 reduces Algorithm 1 on that group, and privacy is still guaranteed.

Finally, a privacy-preserving low-level logistic regression model is obtained in step 12, and a privacy-preserving highlevel logistic regression model is obtained in step 15. Theorem 4 guarantees privacy of Algorithm 3. Note that the proofs in [Chaudhuri et al., 2011; Bassily et al., 2014] cannot be directly used, as they consider neither stacking nor feature importance.

Theorem 4. If all gk's are strongly convex, Algorithm 3 provides ϵ-differential privacy.

Analogous to Proposition 1, the following bounds the learning performance of each low-level model.

Theorem 5. gk = 1/2‖ · -uk‖2 , where uk is any constant vector, and vk is a reference model parameter. Let ak = qk‖vk‖. given δ > 0 and ϵg > 0, there exists a constant C1 such that when

Remark 2. When K = 1 (a single low-level model trained with all features) and uk = 0, Theorem 5 reduces to Proposition 2.

Note that, to keep the same bound L(vk, P) + ϵg, since xs' are scaled by qk, vk should be scaled by 1/qk, so E(ak) = E(qk‖vk‖) remains the same as qk changes. Thus, Theorem 5 shows that low-level models on more important features can indeed learn better, if these features are assigned with larger qk. Since stacking can have better performance than any single model [Ting and Witten, 1999; Dˇzeroski and ˇZenko, 2004] and Theorem 5 can offer better learning guarantee than Proposition 2, Algorithm 3 can have better performance than Algorithm 1. Finally, compared with Proposition 1, gk in theorem 5 is more flexible in allowing an extra uk. We will show in Section 3.3 that this is useful for transfer learning.

Since the learning performance of stacking itself is still an open issue [Ting and Witten, 1999], we leave the guarantee for the whole Algorithm 3 as future work. A potential problem with FP is that possible correlations among feature subsets can no longer be utilized. However, as the highlevel model can combine information from various low-level models, empirical results in Section 4.1 show that this is not problematic unless K is very large.

3.3 Application to Transfer Learning

Transfer learning [Pan and Yang, 2010] is a powerful and promising method to extract useful knowledge from a source domain to a target domain. A popular transfer learning approach is hypothesis transfer learning (HTL) [Kuzborskij and Orabona, 2013], which encourages the hypothesis learned in the target domain to be similar with that in the source domain. For application to (1), HTL adds an extra regularizer as:

Here, η is a hyperparameter, Dtgt is the target domain data, and wsrc is obtained from the source domain. Algorithm 4 shows how PST-F can be extended with HTL using privacy budgets ϵsrc and ϵtgt for the source and target domains, respectively. The same feature partitioning is used on both the source and target data. PLR is trained on each source domain data subset to obtain (wsrc)k (steps 2-4). This is then transferred to the target domain using PST-F with gk(w) = 12 ‖w-(wsrc)k‖2 (step 5).

Algorithm 4 PST-H: Privacy-preserving stacking with HTL.

Require: source data sets Dsrc, target data set Dtgt, and corresponding privacy budgets ϵsrc and ϵtgt, respectively. (source domain processing)

• 1: partition Dsrc to K disjoint sets {F1, . . . ,FK} based on features;
• 2: for k = 1, . . . ,K do
• 3: train PLR with privacy budget ϵsrc on Fk and obtain (wsrc)k;
• 4: end for
• (target domain processing)
• 5: obtain {(wtgt)lk } and whtgt from PST-F (Algorithm 3) by taking gk(w)=1/2‖w-(wsrc)k‖2 and privacy budget ϵtgt on Dtgt;
• 6: return {(wsrc)k} for source domain, {(wtgt)lk } and whtgt for target domain.

The following provides privacy guarantees on both the source and target domains. Recently, privacy-preserving HTL is also proposed in [Wang et al., 2018]. However, it does not consider stacking and ignores feature importance.

Corollary 6. Algorithm 4 provides ϵsrc- and ϵtgt-differential privacy guarantees for the source and target domains.

4 Experiments

4.1 Benchmark Datasets

Experiments are performed on two popular benchmark data sets for evaluating privacy-preserving learning algorithms [Shokri and Shmatikov, 2015; Papernot et al., 2017; Wang et al., 2018]: MNIST [LeCun et al., 1998] and NEWS20 [Lang, 1995] (Table 1). The MNIST data set contains images of handwritten digits. Here, we use the digits 0 and 8. We randomly select 5000 samples. 60% of them are used for training (with 1/3 of this used for validation), and the remaining 20% for testing. The NEWS20 data set is a collection of newsgroup documents. Documents belonging to the topic "sci" are taken as positive samples, while those in the topic "talk" are taken as negative. Finally, we use PCA to reduce the feature dimensionality to 100, as original dimensionality for MINIST/NEWS20 is too high for differentially private algorithms to handle as the noise will be extremely large. Note that we use PCA for simplicity of the ablation study. However, note that the importance scores should be obtained from side information independent from the data or from experts' opinions (as in diabetes example). Otherwise, ϵ-differential privacy will not be guaranteed.

The following algorithms are compared: (i) PLR, which applies Algorithm 1 on the training data; (ii) PST-S: Algorithm 2, based on SP; and (iii) PST-F: Algorithm 3, based on FP. We use K = 5 and 50% of the data for Dl and the remaining for Dh . Two PST-F variants are compared: PST-F(U), with random FP and equal feature importance. And PST-F(W), with partitioning based on the PCA feature scores; and the importance of the kth group Fk is

where vi is the variance of the ith feature fi. Gradient perturbation is worse than objective perturbation in logistic regression [Bassily et al., 2014], thus is not compared.

The area-under-the-ROC-curve (AUC) [Hanley and McNeil, 1983] on the testing set is used for performance evaluation. Hyper-parameters are tuned using the validation set. To reduce statistical variations, the experiment is repeated 10 times, and the results averaged.

Varying Privacy Budget ϵ

Figure 1 shows the testing AUC's when the privacy budget ϵ is varied. As can be seen, the AUCs for all methods improve when the privacy requirement is relaxed (ϵ is large and less noise is added). Moreover, PST-S can be inferior to PLR, due to insufficient training samples caused by SP. Both PSTF(W) and PST-F(U) have better AUCs than PST-S and PLR. In particular, PST-F(W) is the best as it can utilize feature importance. Since PST-S is inferior to PST-F(U), we only consider PST-F(U) in the following experiments.

Varying Number of Partitions K

In this experiment, we fix ϵ = 1, and vary K. As can be seen from Figure 2(a)-(b), when K is very small, ensemble learning is not effective. When K is too large, a lot of feature correlation information is lost and the testing AUC also decreases.

Changing the Feature Importance

In the above experiments, feature importance is defined based on the variance from PCA. Here, we show how feature importance influences prediction performance. In real-world applications, we may not know the exact importance of features. Thus, we replace variance vi by the ith power of α (αi ), where α is a positive constant, and use (6) for assigning weights. Note that when α < 1, more importance features have larger weights; and vice versa when α > 1. Note that PST-F(W) does not reduce to PST-F(U) when α = 1, as more important features are still grouped together. Figure 2(c)-(d) show the testing AUCs at different α's. As can be seen, with proper assigned weights (i.e., α < 1 and more important features have larger qk's), the testing AUC can get higher. If less important features are more valued, the testing AUC decreases and may not be better than PST-F(U), which uses uniform weights. Moreover, we see that PST-F(W) is not sensitive to the weights once they are properly assigned.

Choice of High-Level Model

We compare different high-level models in combining predictions from the low-level models. The following methods are compared: (i) major voting (C-mv) from low-level models; (ii) weighted major voting (C-wmv), which uses {qk} as the weights; and (iii) by a high-level model in PST-F (denoted "C-hl"). Figure 3 shows results on NEWS20 with ϵ = 1.0. As can be seen, C-0 in Figure 3(b) has the best performance among all single low-level models, as it contains the most important features. Besides, stacking (i.e., C-hl), is the best way to combine predictions from C-{0-4}, which also offers better performance than any single low-level models.

4.2 Diabetes Prediction

Diabetes is a group of metabolic disorders with high blood sugar levels over a prolonged period. The RUIJIN diabetes data set is collected by the Shanghai Ruijin Hospital during two investigations (in 2010 and 2013), conducted by the main hospital in Shanghai and 16 branches across China. The first investigation consists of questionnaires and laboratory tests collecting demographics, life-styles, disease information, and physical examination results. The second investigation includes diabetes diagnosis. Some collected features are shown in Table 3. Table 4 shows a total of 105,763 participants who appear in both two investigations. The smaller branches may not have sufficient labeled medical records for good prediction. Hence, it will be useful to borrow knowledge learned by the main hospital. However, users' privacy is a major concern, and patients' personal medical records in the main hospital should not be leaked to the branches.

In this section, we apply the method in Section 3.3 for diabetes prediction. Specifically, based on the patient data collected during the first investigation in 2010, we predict whether he/she will have diabetes diagnosed in 2013. The main hospital serves as the source domain, and the branches are the target domains. We set ϵsrc = ϵtgt = 1.0. The following methods are also compared: (i) PLR(target), which directly uses PLR on the target data; (ii) PPHTL [Wang et al., 2018]: a recently proposed privacy-preserving HTL method based on PLR; (iii) PST-F(U): There are 50 features, and they are randomly split into five groups, i.e., K = 5, and each group have equal weights; (iv) PST-F(W): Features are first sorted by importance, and then grouped as follows: The top 10 features are placed in the first group, the next 10 features go to the second group, and so on. qk is set based on (6), with vi being the importance values provided by the doctors. The other settings are the same as in Section 4.1.

Results are shown in Table 2. PPHTL may not have better performance than PLR(target), which is perhaps due to noise introduced in features. However, PST-F(U) improves over PPHTL by feature splitting, and consistently outperforms PLR(target). PST-F(W), which considers features importance, is the best.

5 Conclusion

In this paper, we propose a new privacy-preserving machine learning method, which improves privacy-preserving logistic regression by stacking. This can be done by either sample-based or feature-based partitioning of the data set. We provide theoretical justifications that the feature-based approach is better and requires a smaller sample complexity. Besides, when the importance of features is available, this can further boost the feature-based approach both in theory and practice. Effectiveness of the proposed method is verified on both standard benchmark data sets and a real-world crossorganizational diabetes prediction application.

Acknowledgments

We acknowledge the support of Hong Kong CERG16209715. The first author also thanks Bo Han from Riken for helpful suggestions.