# Differentially Private Kernel Support Vector Machines Based on the Exponential and Laplace Hybrid Mechanism

Authors: Zhenlong Sun; Jing Yang; Xiaoye Li; Jianpei Zhang
Journal: Security and Communication Networks
 (2021)

---

## Abstract

Support vector machines (SVMs) are among the most robust and accurate methods in all well-known machine learning algorithms, especially for classification. The SVMs train a classification model by solving an optimization problem to decide which instances in the training datasets are the support vectors (SVs). However, SVs are intact instances taken from the training datasets and directly releasing the classification model of the SVMs will carry significant risk to the privacy of individuals, when the training datasets contain sensitive information. In this paper, we study the problem of how to release the classification model of kernel SVMs while preventing privacy leakage of the SVs and satisfying the requirement of privacy protection. We propose a new differentially private algorithm for the kernel SVMs based on the exponential and Laplace hybrid mechanism named DPKSVMEL. The DPKSVMEL algorithm has two major advantages compared with existing private SVM algorithms. One is that it protects the privacy of the SVs by postprocessing and the training process of the non-private kernel SVMs does not change. Another is that the scoring function values are directly derived from the symmetric kernel matrix generated during the training process and does not require additional storage space and complex sensitivity analysis. In the DPKSVMEL algorithm, we define a similarity parameter to denote the correlation or distance between the non-SVs and every SV. And then, every non-SV is divided into a group with one of the SVs according to the maximal value of the similarity. Under some certain similarity parameter value, we replace every SV with a mean value of the top-k randomly selected most similar non-SVs within the group by the exponential mechanism if the number of non-SVs is greater thank. Otherwise, we add random noise to the SVs by the Laplace mechanism. We theoretically prove that the DPKSVMEL algorithm satisfies differential privacy. The extensive experiments show the effectiveness of the DPKSVMEL algorithm for kernel SVMs on real datasets; meanwhile, it achieves higher classification accuracy than existing private SVM algorithms.


---

## Body

## 1. Introduction

In recent years, with the rapid development of computing devices in the collecting, storing, and processing capabilities, data sharing and analyzing are becoming easier and more practical [1]. Data mining and machine learning techniques have been gaining a great deal of attention for analyzing useful information. The classification algorithm, as one of the important data mining tasks, trains a classification model from labeled training datasets to classify unknown data in the future [2]. The support vector machine (SVM) [3, 4] is one of the most widely used machine learning algorithms for classification in practice [5]. SVMs train a classification model by finding a solution to the convex optimization problem. Like most other classification algorithms, SVMs also have privacy issues when the training datasets contain sensitive information such as user behavior records or electronic health records. In SVMs, support vectors (SVs) are an important component of the classification model and they are intact instances taken from the training datasets. Directly releasing the classification model of SVMs will carry significant risk to the privacy of individuals, especially for kernel SVMs [2].More and more researchers have made great efforts on the privacy leakage problem. Differential privacy (DP) [6–8] is one of the state-of-the-art models and has become an accepted standard for privacy protection in sensitive data analysis since it was proposed by a series of works by Dwork et al. in 2006. In recent decades, two main research directions of DP have been developed: differentially private data publishing and differentially private data analysis [9]. Differentially private data publishing aims to output aggregate information to the public without disclosing any individual record, including transaction data publishing [10], histogram publishing [11], stream data publishing [12], graph data publishing [13], batch query publishing [14], and synthetic datasets publishing [15]. The essential task of differentially private data analysis is extending the current non-private algorithms to differentially private algorithms, including supervised learning [16], unsupervised learning [17], and frequent pattern mining [18].In this paper, we studied the problem of how to release the classification model of kernel SVMs while satisfying the requirement of privacy protection. To overcome the shortcomings in the existing private SVM algorithms, such as the requirements on the differentiability of the objective function and the low classification accuracy, we proposed a new differentially private algorithm for the kernel SVMs. The main contributions in this paper concluded as follows:(i)
We propose the exponential and Laplace hybrid mechanism to prevent privacy leakage of the SVs. The hybrid mechanism takes advantage of both the exponential mechanism and the Laplace mechanism to improve the classification accuracy.(ii)
We define a similarity parameter to denote the correlation or distance between the non-SVs and every SV. This can be easily achieved from the symmetric kernel matrix produced during the training process. And then, every non-SV is divided into a group with one of the SVs according to the maximal value of the similarity.(iii)
Learning from the idea of top-k frequent pattern mining [1, 19, 20], we use different methods to protect the privacy of the SVs under some certain similarity parameter values. When the number of the non-SVs is greater than k within the group, we replace every SV with a mean value of the top-k randomly selected most similar non-SVs by the exponential mechanism. Otherwise, we add random noise to the SVs by the Laplace mechanism.(iv)
We theoretically prove that the DPKSVMEL algorithm satisfies DP. The extensive experiments show the effectiveness of the DPKSVMEL algorithm for kernel SVMs on real datasets; meanwhile, it achieves higher classification accuracy than existing private SVMs algorithms.The rest of the paper is organized as follows: In Section2, we discuss the work related to private SVMs. In Section 3, we give a brief overview of the basic knowledge of SVMs, DP, and top-k frequent pattern mining. Section 4 proposes the DPKSVMEL algorithm, and Section 5 gives the experimental performance evaluation of the DPKSVMEL algorithm. Section 6 concludes the research work.


## 2. Related Work

In this section, we briefly review some work of private SVMs and then focus on the work related to differentially private SVMs.There are some works related to private SVMs. Mangasarian et al. [21] proposed a highly efficient privacy-preserving SVM PPSVM via random kernels for vertically partitioned data. Lin et al. [2] pointed out the private violation problem of SVs in the classification model of the SVM and proposed a privacy-preserving SVM classifier PPSVC to replace the Gaussian kernel with a precisely approximate decision function. These two methods achieve similar classification accuracy to the original non-private SVM classifier. Nevertheless, the degree of privacy protection cannot be proved as the private SVMs based on DP.DP is a rigorous privacy definition and has become an accepted standard for privacy protection in sensitive data analysis. The degree of privacy protection can be measured with privacy budget parameterɛ. The classification model of the SVMs should be released under a DP guarantee. Chaudhuri et al. [22, 23] proposed two popular perturbation-based techniques, output perturbation and objective perturbation, for privacy-preserving machine learning algorithm design. Output perturbation introduces randomness into the weight vector w after the optimization process, and the randomness scale is determined by the sensitivity of w. Objective perturbation introduces randomness into the objective function before the optimization process, and the randomness scale is independent of the sensitivity of w. These two perturbation-based techniques have been applied to logistic regression and linear SVM algorithms. However, their sensitivity is difficult to analyze, and the loss function needs to satisfy certain convexity and differentiability criteria for objective perturbation. For nonlinear kernel SVMs, Chaudhuri et al. used the random projections method to approximate the kernel function by transforming it to linear classification and avoided publishing privacy values in the training datasets directly. The disadvantage of this method is that it needs to provide the projection matrix except for the privacy classification model in the prediction process, which increases the risk of privacy leakage. Furthermore, the appropriate projection dimension is also an issue to be considered. Rubinstein et al. [24] proposed two mechanisms for differentially private SVM learning, one with finite-dimensional feature mappings and one with potentially infinite-dimensional feature mappings. Both mechanisms are achieved by adding noise to the output classifier and are effective for all convex loss functions including the most frequent hinge loss function. They also came up with a utility metric by comparing the similarity of the classifiers released by private and non-private SVM. Their mechanisms are valid only for the translation-invariant kernels. Li et al. [25] developed a hybrid private SVM model by using public data and private data together. They leveraged a small portion of open-consented data to calculate the Fourier transformation to alleviate too much noise in the final outputs. However, public data are hard to obtain in the private world. Liu et al. [26] proposed a private classification algorithm LabSam with high classification accuracy under DP when the labeled data were limited and the privacy budget was small. Their algorithm implements random sampling under the exponential mechanism differing from the perturbation-based methods. Zhang et al. [27] constructed a novel private SVM classifier DPSVMDVP on dual variable perturbation, which added Laplace noise to the corresponding dual variables according to the ratio of errors.


## 3. Preliminaries

In this section, we give a brief overview of the basic knowledge of SVMs, DP, and top-k frequent pattern mining.


### 3.1. Support Vector Machines

The SVM is an efficient learning method for classification based on structural risk minimization [3]. It aims to find an optimal separating hyperplane with a maximal margin to separate two classes of the given instances. The maximal margin corresponds to the shortest distance between the closest data points and any point on the hyperplane. Xue et al. [28] described the complete calculation process of the decision function in detail. The main task for training a SVM is to solve the optimization problem of quadratic programming as follows [29, 30]:(1)minfα=12αTQα−eTα,subject to0≤αi≤C,i=1,…,landyTα=0.In equation (1), Q denotes a symmetric kernel matrix with Qij = yiyjK (xi, xj) and K is the kernel function. α is a dual vector, and xi and yi denote the training instance and label, respectively. The optimization problem of equation (1) can be solved by the sequential minimal optimization algorithm efficiently [30]. After the optimization process, we obtain the decision function as follows:(2)fx=∑i=1nαi∗yixi,x+b∗.From equation (2), we can conclude that the classification model of the SVMs is composed of dual variables α and SVs. It is a very serious private issue that directly releases a classification model with the original instances of the training datasets.


### 3.2. Differential Privacy

With the advent of the digital age, more and more personal information has been collected and shared by mobile devices and web services to improve the quality of these services. At the same time, it also raises privacy concerns of data contributors. DP [6–8, 31] provides a mathematically rigorous definition of privacy for private data analysis. It guarantees that any possible outcome of the data analysis is hardly any different from each other whether or not the individual participates in the database. The maximal difference of the outcome is controlled by a small privacy budget parameter ɛ. Formally, the definitions related to DP are given in the following.Definition 1.
(ε-DP [6]). A randomized algorithm K satisfies ε-DP if datasets D and D′ differ on at most one instance, and for all subsets of possible outcomes of the algorithm S ⊆ Range (K),(3)PrKD∈S≤expε×PrKD′∈S.Definition 2.
(sensitivity [6]). For a given query function f:D⟶Rd and neighboring datasets D and D′, the sensitivity of f is defined as(4)Δf=maxD,D′fD−fD′1.
Currently, there are two principal mechanisms used for realizing DP: the Laplace mechanism for numerical data and the exponential mechanism for nonnumerical queries.Definition 3.
(Laplace mechanism [8]). For a numeric function f:D⟶Rd, the algorithm K that answers f in equation (5) provides ɛ-DP.(5)KD=fD+LapΔfεd,where Lap (∆f/ε) is a random variable sampled from the Laplace distribution with mean 0 and standard deviation 2Δf/ε.
The Laplace mechanism retrieves the true results from the numerical query and then perturbs it by adding independent random noise according to the sensitivity.Definition 4.
(exponential mechanism [7]). Let qD,r be a scoring function on a dataset D that measures the quality of output r∈R, and Δq represents the sensitivity. The algorithm K satisfies ɛ-DP if(6)KD=returnr∝expεqD,r2Δq.
The exponential mechanism is useful to select a discrete output in a differentially private manner, which employs a scoring functionq to evaluate the quality of an output r with a nonzero probability.Definition 5.
(composition properties [31, 32]). Let K1 and K2 be ε1 and ε2-DP algorithms, respectively. Then, we have the following:Sequential composition: releasing the output ofK1 (D) and K2 (D) satisfies (ε1 + ε2)-DPParallel composition: forD1∩D2=∅, releasing K1 (D1) and K2 (D2) satisfies max(ε1, ε2)-DP


### 3.3. Top-k Frequent Pattern Mining

Frequent pattern mining aims to discover items that frequently appear together in a transaction dataset. Directly releasing the discovered frequent patterns with support counts will violate individual privacy. Therefore, the top-k most frequent pattern should be released under DP guarantee. Zhang et al. [1] proposed an algorithm DFP-Growth, which accurately found the top-k frequent patterns with noisy support counts while satisfying DP. The DFP-Growth algorithm is performed by two key steps: firstly, selecting the top-k frequent patterns by the exponential mechanism; secondly, perturbing the true support count of each top-k pattern by the Laplace mechanism.


## 3.1. Support Vector Machines

The SVM is an efficient learning method for classification based on structural risk minimization [3]. It aims to find an optimal separating hyperplane with a maximal margin to separate two classes of the given instances. The maximal margin corresponds to the shortest distance between the closest data points and any point on the hyperplane. Xue et al. [28] described the complete calculation process of the decision function in detail. The main task for training a SVM is to solve the optimization problem of quadratic programming as follows [29, 30]:(1)minfα=12αTQα−eTα,subject to0≤αi≤C,i=1,…,landyTα=0.In equation (1), Q denotes a symmetric kernel matrix with Qij = yiyjK (xi, xj) and K is the kernel function. α is a dual vector, and xi and yi denote the training instance and label, respectively. The optimization problem of equation (1) can be solved by the sequential minimal optimization algorithm efficiently [30]. After the optimization process, we obtain the decision function as follows:(2)fx=∑i=1nαi∗yixi,x+b∗.From equation (2), we can conclude that the classification model of the SVMs is composed of dual variables α and SVs. It is a very serious private issue that directly releases a classification model with the original instances of the training datasets.


## 3.2. Differential Privacy

With the advent of the digital age, more and more personal information has been collected and shared by mobile devices and web services to improve the quality of these services. At the same time, it also raises privacy concerns of data contributors. DP [6–8, 31] provides a mathematically rigorous definition of privacy for private data analysis. It guarantees that any possible outcome of the data analysis is hardly any different from each other whether or not the individual participates in the database. The maximal difference of the outcome is controlled by a small privacy budget parameter ɛ. Formally, the definitions related to DP are given in the following.Definition 1.
(ε-DP [6]). A randomized algorithm K satisfies ε-DP if datasets D and D′ differ on at most one instance, and for all subsets of possible outcomes of the algorithm S ⊆ Range (K),(3)PrKD∈S≤expε×PrKD′∈S.Definition 2.
(sensitivity [6]). For a given query function f:D⟶Rd and neighboring datasets D and D′, the sensitivity of f is defined as(4)Δf=maxD,D′fD−fD′1.
Currently, there are two principal mechanisms used for realizing DP: the Laplace mechanism for numerical data and the exponential mechanism for nonnumerical queries.Definition 3.
(Laplace mechanism [8]). For a numeric function f:D⟶Rd, the algorithm K that answers f in equation (5) provides ɛ-DP.(5)KD=fD+LapΔfεd,where Lap (∆f/ε) is a random variable sampled from the Laplace distribution with mean 0 and standard deviation 2Δf/ε.
The Laplace mechanism retrieves the true results from the numerical query and then perturbs it by adding independent random noise according to the sensitivity.Definition 4.
(exponential mechanism [7]). Let qD,r be a scoring function on a dataset D that measures the quality of output r∈R, and Δq represents the sensitivity. The algorithm K satisfies ɛ-DP if(6)KD=returnr∝expεqD,r2Δq.
The exponential mechanism is useful to select a discrete output in a differentially private manner, which employs a scoring functionq to evaluate the quality of an output r with a nonzero probability.Definition 5.
(composition properties [31, 32]). Let K1 and K2 be ε1 and ε2-DP algorithms, respectively. Then, we have the following:Sequential composition: releasing the output ofK1 (D) and K2 (D) satisfies (ε1 + ε2)-DPParallel composition: forD1∩D2=∅, releasing K1 (D1) and K2 (D2) satisfies max(ε1, ε2)-DP


## 3.3. Top-k Frequent Pattern Mining

Frequent pattern mining aims to discover items that frequently appear together in a transaction dataset. Directly releasing the discovered frequent patterns with support counts will violate individual privacy. Therefore, the top-k most frequent pattern should be released under DP guarantee. Zhang et al. [1] proposed an algorithm DFP-Growth, which accurately found the top-k frequent patterns with noisy support counts while satisfying DP. The DFP-Growth algorithm is performed by two key steps: firstly, selecting the top-k frequent patterns by the exponential mechanism; secondly, perturbing the true support count of each top-k pattern by the Laplace mechanism.


## 4. Materials and Methods

To solve the privacy leakage problem of the SVs in the classification model of kernel SVMs, we proposed the DPKSVMEL algorithm based on the exponential and Laplace hybrid mechanism. The privacy of SVs is protected by postprocessing the non-private classification model with DP, while the training process of the original SVMs is not changed. Firstly, we train a non-private kernel SVM to obtain a classification model including dual vectorα and the SVs. Secondly, we define a similarity parameter to denote the correlation or distance between the non-SVs and every SV and then every non-SV is divided into a group with one of the SVs according to the maximal value of the similarity. Thirdly, we use either the exponential mechanism or the Laplace mechanism to generate a new SV and then replace the original SV within the group under some certain similarity parameter values. The mechanism to use depends on whether the number of non-SVs is greater than k. Lastly, we output the classification model with the private SVs. Figure 1 gives an example of the DPKSVMEL algorithm implementation process.Figure 1
An example of the DPKSVMEL algorithm implementation process.In Figure1, there are three SVs and eight non-SVs. The square represents the SV, the small circle represents the non-SV, the triangle represents the private SV, and the big circle represents a group. Every group is represented by different colors and viewed as a hypersphere with the SV as the center and the similarity as the radius. And, every non-SV is divided into one group according to the maximal value of its similarity with every SV. In particular, some non-SVs that are located at the intersection of multiple groups also belong to one group to satisfy the parallel composition property of DP. We set the parameter k to 2 in this example. In the groups with red and yellow colors, the number of the non-SVs is greater than k. We use the exponential mechanism to randomly select the most similar two non-SVs and then generate a new private SV with the mean value of them. However, there is only one non-SV in the blue group. We use the Laplace mechanism to generate a new private SV with noise. Therefore, the SVs in the final classification model are all private ones to prevent privacy leakage.


### 4.1. Similarity Parameter and Sensitivity

In the DPKSVMEL algorithm, the similarity is a vital parameter. We view the symmetric kernel matrixQ in equation (1) as the probability of similarity between every two instances in the datasets, especially for the radial basis kernel.Definition 6.
(similarity). For a non-SVxi and a SV xj, the similarity between them is defined as(7)Similarityij=Qij=yi∗yj∗Kxi,xj=yi∗yj∗exp−gamma∗xi−xj2.
In equation (7), Similarity is a subset of Q. It is obtained easily from the classification model and requires no extra complicated computation. The smaller the distance between a non-SV and a SV, the greater the value of the Similarity when they have the same labels. If they have different labels, the value of the Similarity is less than zero and the corresponding non-SV will be discarded from participating in the calculation within the group.
TheSimilarity is viewed as the probability of the correlation between a non-SV and a SV. In the DPKSVMEL algorithm, we set a lower limit for the Similarity named LLs to denote the minimum value of the correlation or the maximum value of the distance between them. If the value of the Similarity is less than LLs, it means that the correlation is too small or the distance is too large between the non-SV and the SV; then, the non-SV is also discarded from the group. After all the non-SVs are divided into groups, we use the exponential and Laplace hybrid mechanism to generate a new SV in every group. When LLs are fixed, the radius of the hypersphere corresponding to each group is determined. Then, the sensitivity of the exponential mechanism and Laplace mechanism is calculated by LLs easily. They are denoted by Sensitivityem and Sensitivitylm, respectively.(8)Sensitivityem=1−LLs,(9)Sensitivitylm=sqrt−logLLs.
In the exponential mechanism, we useSimilarity as the scoring function. Under the fixed LLs, the maximum value of the similarity is 1 when the non-SV coincided with the SV and the minimum value is LLs within the group. Therefore, the sensitivity of the exponential mechanism is obvious as shown in equation (8). In the Laplace mechanism, we define the radius of the hypersphere R to denote the maximal distance between the non-SVs and the SV within a group that corresponds to the lower limit of the Similarity LLs. The relationship between LLs and R is drawn from equation (7) in that(10)LLs=exp−gamma∗R2,where gamma is a scale parameter with a default value of 1/n for a dataset with n attributes. Then,(11)R=sqrt−n∗logLLs,where R denotes the maximal distance between every non-SV and the SV within the group. As all the attributes in a dataset are independent, we conclude that the biggest change of any attribute within a group is at most sqrt (−log (LLs)) based on the formula for the distance between two points. Therefore, the sensitivity of the Laplace mechanism is as shown in equation (9).


### 4.2. Privacy Budget Allocation

In DP algorithm, the privacy budgetε is another vital parameter. It determines the level of privacy protection for a randomized algorithm. The smaller the privacy budget, the higher the level of privacy protection. When the allocated privacy budget runs out, the randomized algorithm K will lose privacy protection. In the DPKSVMEL algorithm, every non-SV is divided into a group with one of the SV and there are no common instances between groups. Therefore, the DPKSVMEL algorithm satisfies the parallel composition property of DP. There is no need to split the privacy budget for the exponential mechanism and the Laplace mechanism.


### 4.3. Description of the DPKSVMEL Algorithm

In the DPKSVMEL algorithm, DP is achieved by the exponential and Laplace hybrid mechanism. The description of the DPKSVMEL algorithm is shown in Algorithm1.Algorithm 1: DPKSVMEL
Input:Q: symmetric kernel matrix; ɛ: privacy budget; LLs: lower limit of the Similarity; Nns: the number of non-SVs in a group; k: the number of non-SVs selected in the exponential mechanism;Output: SVp: private SV;Begin(1)
obtain a non-private classification model including dual vectorα and the SVs by training a kernel SVM;(2)
get theSimilarity matrix from the subset of Q in which the Similarity value was no less than LLs;(3)
divide every non-SV into one group according to the maximal value of its similarity with every SV;(4)
fori in every group(5)
ifNns > k then(6)
compute the probabilityPrns for every non-SVs with its Similarity value;(7)
randomly select the most similark non-SVs with probability Prns by the exponential mechanism;(8)
SVpi = the mean value of the selected k non-SVs;(9)
else(10)
for every attribute of the SV(11)
SVpij = SVij + Laplace (Sensitivelm/ɛ);(12)
end for(13)
end if(14)
end for(15)
output the private classification model with SVp;EndThe DPKSVMEL algorithm protects the privacy of SVs by postprocessing the non-private classification model. It builds a single group for every SV and divides every non-SV into one of the groups according to its similarity. The private SVs are constructed by the exponential mechanism when the number of the non-SVs is greater thank within the group; otherwise, they are constructed by the Laplace mechanism. Finally, the DPKSVMEL algorithm outputs the private classification model. Because the running time of the algorithm only depends on the number of SVs, its time complexity is much less than O (n), where n denotes the number of instances.


### 4.4. Privacy Analysis

In the DPKSVMEL algorithm, randomness is introduced by the exponential and Laplace hybrid mechanism. According to the definition of DP, we prove that the DPKSVMEL algorithm satisfies DP by Theorem1.Theorem 1.
DPKSVMEL algorithm satisfies DP.Proof.
In the DPKSVMEL algorithm, DP is achieved by postprocessing the non-private classification model. Every SV is viewed as the center of a group, and there is no intersection between groups. We consider the impact of adding an instance in the dataset on the classification model in the following three cases. The first one is that the new instance becomes a SV; then, one new group needs to deal with the Laplace mechanism. The second one is that the new instance is a non-SV and is divided into a group, which only adds one non-SV to be randomly selected by the exponential mechanism. The third one is that the new instance is a non-SV and does not belong to any group, and the classification model shows no change. Based on the sensitivity computation in equations (8) and (9), either the exponential mechanism or the Laplace mechanism for dealing with one group satisfies DP. According to the parallel composition property of DP, the DPKSVMEL algorithm satisfies DP.


## 4.1. Similarity Parameter and Sensitivity

In the DPKSVMEL algorithm, the similarity is a vital parameter. We view the symmetric kernel matrixQ in equation (1) as the probability of similarity between every two instances in the datasets, especially for the radial basis kernel.Definition 6.
(similarity). For a non-SVxi and a SV xj, the similarity between them is defined as(7)Similarityij=Qij=yi∗yj∗Kxi,xj=yi∗yj∗exp−gamma∗xi−xj2.
In equation (7), Similarity is a subset of Q. It is obtained easily from the classification model and requires no extra complicated computation. The smaller the distance between a non-SV and a SV, the greater the value of the Similarity when they have the same labels. If they have different labels, the value of the Similarity is less than zero and the corresponding non-SV will be discarded from participating in the calculation within the group.
TheSimilarity is viewed as the probability of the correlation between a non-SV and a SV. In the DPKSVMEL algorithm, we set a lower limit for the Similarity named LLs to denote the minimum value of the correlation or the maximum value of the distance between them. If the value of the Similarity is less than LLs, it means that the correlation is too small or the distance is too large between the non-SV and the SV; then, the non-SV is also discarded from the group. After all the non-SVs are divided into groups, we use the exponential and Laplace hybrid mechanism to generate a new SV in every group. When LLs are fixed, the radius of the hypersphere corresponding to each group is determined. Then, the sensitivity of the exponential mechanism and Laplace mechanism is calculated by LLs easily. They are denoted by Sensitivityem and Sensitivitylm, respectively.(8)Sensitivityem=1−LLs,(9)Sensitivitylm=sqrt−logLLs.
In the exponential mechanism, we useSimilarity as the scoring function. Under the fixed LLs, the maximum value of the similarity is 1 when the non-SV coincided with the SV and the minimum value is LLs within the group. Therefore, the sensitivity of the exponential mechanism is obvious as shown in equation (8). In the Laplace mechanism, we define the radius of the hypersphere R to denote the maximal distance between the non-SVs and the SV within a group that corresponds to the lower limit of the Similarity LLs. The relationship between LLs and R is drawn from equation (7) in that(10)LLs=exp−gamma∗R2,where gamma is a scale parameter with a default value of 1/n for a dataset with n attributes. Then,(11)R=sqrt−n∗logLLs,where R denotes the maximal distance between every non-SV and the SV within the group. As all the attributes in a dataset are independent, we conclude that the biggest change of any attribute within a group is at most sqrt (−log (LLs)) based on the formula for the distance between two points. Therefore, the sensitivity of the Laplace mechanism is as shown in equation (9).


## 4.2. Privacy Budget Allocation

In DP algorithm, the privacy budgetε is another vital parameter. It determines the level of privacy protection for a randomized algorithm. The smaller the privacy budget, the higher the level of privacy protection. When the allocated privacy budget runs out, the randomized algorithm K will lose privacy protection. In the DPKSVMEL algorithm, every non-SV is divided into a group with one of the SV and there are no common instances between groups. Therefore, the DPKSVMEL algorithm satisfies the parallel composition property of DP. There is no need to split the privacy budget for the exponential mechanism and the Laplace mechanism.


## 4.3. Description of the DPKSVMEL Algorithm

In the DPKSVMEL algorithm, DP is achieved by the exponential and Laplace hybrid mechanism. The description of the DPKSVMEL algorithm is shown in Algorithm1.Algorithm 1: DPKSVMEL
Input:Q: symmetric kernel matrix; ɛ: privacy budget; LLs: lower limit of the Similarity; Nns: the number of non-SVs in a group; k: the number of non-SVs selected in the exponential mechanism;Output: SVp: private SV;Begin(1)
obtain a non-private classification model including dual vectorα and the SVs by training a kernel SVM;(2)
get theSimilarity matrix from the subset of Q in which the Similarity value was no less than LLs;(3)
divide every non-SV into one group according to the maximal value of its similarity with every SV;(4)
fori in every group(5)
ifNns > k then(6)
compute the probabilityPrns for every non-SVs with its Similarity value;(7)
randomly select the most similark non-SVs with probability Prns by the exponential mechanism;(8)
SVpi = the mean value of the selected k non-SVs;(9)
else(10)
for every attribute of the SV(11)
SVpij = SVij + Laplace (Sensitivelm/ɛ);(12)
end for(13)
end if(14)
end for(15)
output the private classification model with SVp;EndThe DPKSVMEL algorithm protects the privacy of SVs by postprocessing the non-private classification model. It builds a single group for every SV and divides every non-SV into one of the groups according to its similarity. The private SVs are constructed by the exponential mechanism when the number of the non-SVs is greater thank within the group; otherwise, they are constructed by the Laplace mechanism. Finally, the DPKSVMEL algorithm outputs the private classification model. Because the running time of the algorithm only depends on the number of SVs, its time complexity is much less than O (n), where n denotes the number of instances.


## 4.4. Privacy Analysis

In the DPKSVMEL algorithm, randomness is introduced by the exponential and Laplace hybrid mechanism. According to the definition of DP, we prove that the DPKSVMEL algorithm satisfies DP by Theorem1.Theorem 1.
DPKSVMEL algorithm satisfies DP.Proof.
In the DPKSVMEL algorithm, DP is achieved by postprocessing the non-private classification model. Every SV is viewed as the center of a group, and there is no intersection between groups. We consider the impact of adding an instance in the dataset on the classification model in the following three cases. The first one is that the new instance becomes a SV; then, one new group needs to deal with the Laplace mechanism. The second one is that the new instance is a non-SV and is divided into a group, which only adds one non-SV to be randomly selected by the exponential mechanism. The third one is that the new instance is a non-SV and does not belong to any group, and the classification model shows no change. Based on the sensitivity computation in equations (8) and (9), either the exponential mechanism or the Laplace mechanism for dealing with one group satisfies DP. According to the parallel composition property of DP, the DPKSVMEL algorithm satisfies DP.


## 5. Results

In this section, we compared the performance of the DPKSVMEL algorithm with the newest private SVM algorithms LabSam [26] and DPSVMDVP [27]. While PrivateSVM [24] does not provide practical and comparable experimental results, the experimental datasets in hybrid SVM [25] cannot be obtained now.


### 5.1. Datasets

The datasets in our experiments are commonly used for testing SVM algorithms’ performance and are available athttps://www.csie.ntu.edu.tw/∼cjlin/libsvmtools/. Table 1 shows the basic information of the eight datasets and classification accuracy of the non-private SVM with the default parameters based on LIBSVM (version 3.24) [33]. We use the radial basis function as the kernel function in the experiments.Table 1
The basic information of the datasets.
IndexDatasets#data#features#SVAccuracyAUC1Australian6901424485.80.94642Breast683106697.360.99523Heart2701313286.670.93144Ionosphere3513413794.590.98345Sonar2086015986.540.93536German10002459981.20.86037Diabetes768844778.130.84838Splice10006060794.30.9864


### 5.2. Algorithm Performance Experiments

In this section, we evaluated the performance of the DPKSVMEL algorithm by theAccuracy and AUC (the area under a ROC curve). The higher their values, the better the usability of the algorithm. To evaluate the algorithm performance under different parameters setting, we set k at 2 and 3, set privacy budget ɛ at 0.1, 0.5, and 1, and set the lower limit for the Similarity from 0.5 to 0.9. To avoid the influence of randomness on algorithm performance, we execute the algorithm DPKSVMEL 10 times under every set of parameters. Tables 2–9 show the mean value, standard deviation, maximum value, and minimum value of the Accuracy and AUC on the eight datasets. The values in bold represent the best case of the mean value of Accuracy and AUC under the same privacy budget. And, the running time of the DPKSVMEL algorithm is shown in Table 10.Table 2
The performance of the DPKSVMEL algorithm on dataset Australian.
kɛSimilarityAccuracyAUCMeanStdMaxMinMeanStdMaxMin20.10.583.432.5485.9478.260.89630.02370.91880.83520.683.361.8486.0981.300.89880.00960.91480.88840.785.591.1587.6883.770.90770.02110.92680.85050.884.412.8887.2577.680.91620.01020.92770.89920.986.070.6387.3985.220.91350.01000.92460.894020.50.584.172.4787.1080.580.90410.01730.92660.87870.685.321.3587.2583.040.90960.01640.92970.87290.784.713.5987.8375.650.91630.01010.92810.89860.885.671.7487.9782.610.92200.00520.92970.91160.985.881.0287.1083.480.91880.01270.93240.8915210.585.301.8386.8180.870.91710.00710.92610.90380.686.591.0088.1285.070.92580.00750.93700.91220.786.230.7887.6884.780.92260.00970.93170.89850.886.590.7987.5485.510.92950.00260.93380.92460.986.520.5687.3985.800.92870.00620.93720.918130.10.580.715.9286.6768.260.87760.04100.91870.79750.683.552.7286.9678.260.90230.01180.91740.88490.782.652.9186.2378.410.90870.01550.92400.86930.885.431.4887.1082.610.91300.01350.92710.89440.986.030.8887.3984.490.90780.01390.92230.876430.50.581.045.4986.5268.840.89870.01970.92280.86060.683.262.8786.5278.840.89940.01630.91750.87110.782.206.7387.8367.250.90720.01650.92770.87250.885.642.1487.5480.290.91530.01320.93180.88480.985.871.5087.1081.880.92240.00720.93240.9096310.584.872.2887.2579.570.92290.00580.92970.91480.685.361.4286.9682.460.91580.00990.93160.89550.786.141.8287.5481.590.92300.00810.93610.91050.886.200.6187.1085.220.92620.00840.93680.91420.986.410.5787.2585.650.92830.00400.93380.9225Table 3
The performance of the DPKSVMEL algorithm on dataset Breast.
kɛSimilarityAccuracyAUCMeanStdMaxMinMeanStdMaxMin20.10.596.710.5997.2295.460.99430.00070.99550.99300.696.650.5197.2295.310.99460.00030.99520.99430.796.880.3097.2296.340.99440.00070.99530.99260.897.040.3197.5196.490.99390.00110.99500.99100.997.260.2097.5196.780.99350.00090.99480.992320.50.596.790.2897.3696.340.99480.00030.99520.99430.696.490.4597.0795.750.99450.00040.99520.99390.797.100.2897.5196.630.99440.00030.99480.99380.897.230.2197.3696.780.99360.00070.99480.99260.997.310.1997.5196.930.99370.00080.99510.9923210.596.540.5097.3695.900.99510.00030.99540.99460.696.530.4997.2295.900.99500.00040.99540.99440.797.120.2597.3696.630.99470.00040.99500.99390.897.420.1797.6697.220.99400.00070.99480.99260.997.390.1897.6697.070.99310.00080.99410.991630.10.596.090.6896.7895.020.99420.00070.99520.99290.696.540.4497.0795.750.99450.00040.99490.99370.796.730.7297.6695.020.99400.00070.99510.99270.896.840.4097.3696.190.99400.00060.99500.99310.997.130.1797.3696.780.99450.00080.99580.993030.50.596.110.5197.0795.170.99470.00080.99530.99270.696.400.6597.5195.610.99480.00050.99580.99360.797.040.3897.3696.340.99480.00040.99520.99430.897.260.3297.8096.930.99410.00080.99550.99240.997.280.1797.5197.070.99380.00100.99490.9919310.596.560.3597.0795.900.99520.00040.99570.99440.696.780.1497.0796.630.99520.00030.99550.99470.797.310.2597.6696.780.99440.00060.99530.99320.897.390.2297.9597.220.99400.00110.99500.99190.997.440.1097.6697.360.99410.00070.99510.9930Table 4
The performance of the DPKSVMEL algorithm on dataset Heart.
kɛSimilarityAccuracyAUCMeanStdMaxMinMeanStdMaxMin20.10.580.002.5584.8177.040.88630.01840.90620.85000.679.852.5784.0776.670.89270.01630.90820.85370.781.931.4685.1980.000.89320.01680.92090.86140.884.331.1585.9381.850.91040.00820.92360.90170.985.521.0586.6783.700.92140.01120.93470.902620.50.582.812.0185.1978.520.90190.01540.92320.87530.684.191.0586.3082.960.90730.00730.91590.89570.784.261.0185.9382.590.91330.00700.92230.90170.884.632.1387.0479.630.91760.00700.92860.90380.986.190.7687.0484.810.92780.00200.93150.9247210.585.371.0987.0483.700.91440.00590.92230.90540.685.001.0587.0483.330.92030.00510.92920.91350.785.440.7686.6784.440.92270.00540.93170.91520.886.000.8387.0484.810.92540.00350.93270.92130.986.370.7287.4184.810.92930.00540.93860.919830.10.577.564.9284.0770.370.88940.00960.91080.87730.679.562.6283.7076.300.88750.01820.90890.85160.782.191.6684.4478.520.90000.01230.91590.87370.882.743.6986.6774.810.91180.00570.91900.89870.984.631.5586.3081.480.91920.00940.93480.904730.50.581.633.7986.3074.440.89050.03900.92030.78870.683.441.8685.5679.630.90800.00540.91630.89910.784.301.5986.6781.850.91440.00730.92520.90080.885.111.5187.7881.850.91980.00390.92940.91600.985.701.5488.1582.220.92230.00610.93100.9093310.584.371.5185.5681.110.91870.00480.92430.90800.685.151.7787.0481.110.92120.00460.92540.90910.785.671.5788.5282.960.92280.00780.93120.90940.886.001.0387.7884.440.92730.00570.93530.91870.986.150.8087.0484.810.92790.00360.93540.9229Table 5
The performance of the DPKSVMEL algorithm on dataset Ionosphere.
kɛSimilarityAccuracyAUCMeanStdMaxMinMeanStdMaxMin20.10.573.9312.4392.5951.000.94400.01310.96860.92460.676.5513.8391.1748.720.93520.02160.97830.90850.768.0113.2387.4644.440.94700.01360.96430.92500.874.426.2887.1865.810.94380.01470.96730.92260.983.964.1190.6077.780.96430.00960.97520.944720.50.585.505.9492.8872.360.94410.01590.97010.91950.677.819.8892.5960.970.94980.01460.96690.92070.782.513.7089.4677.210.94630.01290.97100.92630.886.184.9393.1677.490.96100.00610.97170.95140.990.512.7792.5984.330.96840.00530.97600.9573210.589.603.0992.5983.190.96070.01230.97900.94000.684.767.8393.4565.810.95980.01010.97530.94660.788.806.5293.7373.220.96780.00930.98080.94690.893.111.0094.3090.880.97040.00630.97970.95860.992.711.7394.3088.600.97510.00360.97990.969830.10.579.3211.1790.6055.840.94110.01420.95820.91710.674.7611.1793.1654.130.93790.01770.96350.90480.773.5611.7291.7455.270.94440.01400.96420.91570.877.355.0886.0470.940.95310.01710.97660.91660.979.096.1985.4766.670.95750.01230.97250.940830.50.582.517.1892.5970.090.94570.02340.97590.89370.677.619.3788.3261.540.95670.01620.98010.93280.776.8912.8590.3153.850.95800.01100.97170.94100.884.766.4392.8876.070.95970.00960.97180.94520.989.603.1193.1683.480.97070.00500.98070.9649310.585.646.9093.4574.930.95390.01350.96870.92990.683.4510.6994.0263.250.96510.01020.97490.93820.789.263.5592.5982.910.97270.00740.98450.95920.891.171.5793.1688.600.97230.00590.98040.96160.992.191.8094.3088.600.97570.00500.98170.9648Table 6
The performance of the DPKSVMEL algorithm on dataset Sonar.
kɛSimilarityAccuracyAUCMeanStdMaxMinMeanStdMaxMin20.10.569.426.0876.4458.170.82600.03430.88940.77510.670.727.1278.3759.130.84530.02540.88200.79620.776.255.0083.6567.310.87660.02720.91450.82460.880.053.3184.1373.560.89790.01750.91970.86080.981.733.7985.1074.520.91950.00780.92970.906220.50.573.563.2377.8866.830.85500.02800.90850.81560.672.364.7779.8165.380.85540.03380.90080.81270.777.884.2884.6270.670.88890.01600.91060.86130.880.384.4184.1371.630.90410.01220.91550.88080.983.943.7587.9877.400.92580.01140.93700.8962210.580.143.3685.5875.960.89850.01750.93110.87490.679.424.7384.6270.670.90250.01770.92870.87510.782.552.2986.0679.330.91420.01200.93190.89780.883.612.6685.5876.920.91940.00480.92700.91260.985.341.7187.5081.730.93030.00750.94070.916230.10.570.586.1780.2958.170.81840.05500.87310.69900.673.806.4181.7359.130.83210.04720.86640.73790.773.034.9177.8861.540.85090.02120.87130.80760.875.386.7882.2160.100.89110.02080.92820.86010.982.503.1087.9876.440.91470.01230.93620.895130.50.574.336.4382.6959.130.85380.03520.88980.76270.677.842.8283.1772.120.88440.02240.91990.84990.780.193.9785.1073.080.88700.02370.91330.83910.881.921.3383.6579.810.90190.01220.91590.88080.982.453.6086.0676.440.92330.00590.93100.9143310.580.343.2685.1075.960.90000.01390.92110.87900.681.352.6785.1076.920.90740.02120.93720.87050.783.511.7986.0681.250.91080.01190.92630.88980.884.281.8186.5479.810.92330.01020.93810.90490.985.771.1187.9884.130.93070.00390.93610.9229Table 7
The performance of the DPKSVMEL algorithm on dataset German.
kɛSimilarityAccuracyAUCMeanStdMaxMinMeanStdMaxMin20.10.572.191.7074.8070.000.72670.02960.76260.66900.673.081.5574.3069.600.76830.01120.78340.75140.773.423.7577.1064.300.76830.02180.79730.73520.873.302.6077.9070.000.78800.01230.80330.76160.977.161.2779.3075.600.80560.00790.81390.791020.50.572.913.2075.9064.500.76130.01920.78190.72370.671.913.2575.9064.400.78640.01400.80430.76940.771.567.1077.9055.300.80020.01030.81830.78310.874.564.1278.5067.000.80300.01310.82130.78140.975.523.6079.5068.100.82410.01280.83680.7936210.574.703.5478.4066.100.80180.01050.81600.78640.673.172.6377.1069.100.81180.00560.82180.80510.772.844.2478.1065.800.82050.00640.82680.80880.877.412.3379.7073.000.82490.00540.83250.81530.980.270.4380.8079.600.83810.00400.84250.832230.10.571.132.3974.0067.500.73070.02350.77570.70250.673.491.7375.8071.300.75220.02400.78060.69900.774.171.0375.8072.700.77430.01590.79860.74960.871.696.7978.0054.500.76820.03100.80470.72490.976.203.0379.0069.500.80090.01540.82240.773730.50.573.671.4075.2071.300.75680.02080.77660.72040.672.943.6277.3065.500.78080.01710.80830.75240.773.902.8976.9069.000.78680.02350.80800.72470.871.876.7078.4056.000.80780.00970.82200.79290.977.811.9179.8073.500.82140.01120.83960.7980310.576.161.8078.7073.200.80150.01380.81160.76800.674.941.8377.4072.200.80870.00720.82120.79830.776.631.9578.7072.900.81480.00730.82500.80400.878.521.1380.1076.100.82620.00510.83410.81420.980.171.0581.8077.900.84200.00520.85020.8331Table 8
The performance of the DPKSVMEL algorithm on dataset Diabetes.
kɛSimilarityAccuracyAUCMeanStdMaxMinMeanStdMaxMin20.10.565.960.7167.0664.970.76610.04560.81300.65390.667.622.7572.1465.230.70610.11230.80450.51420.770.554.0377.3464.970.78250.03590.83850.72190.871.483.6776.0466.150.79190.03210.82870.73850.974.402.5977.0870.310.80950.01780.83290.786420.50.568.593.6073.7060.550.72460.11120.79580.44760.670.923.1075.3966.540.78550.02250.81340.74080.769.575.0574.7457.420.76610.05510.82990.62550.872.722.0877.2169.790.78890.03350.82950.73160.974.432.2777.3470.180.81520.02050.84160.7851210.571.397.6377.3450.520.79390.02190.83150.75270.669.996.1175.1353.520.79050.02990.82610.73880.772.662.4775.2666.150.81050.01730.83380.77710.875.052.3377.0870.180.81410.01840.83740.77250.975.641.8278.2671.880.83090.00930.84130.813830.10.565.731.1067.1963.410.70660.06850.78940.60580.666.291.3968.4964.580.70130.07320.80340.54000.767.982.5472.7964.970.73690.07040.80070.57270.869.822.4575.2666.670.74720.04420.80900.67980.969.755.4477.3459.240.75200.06190.82830.644630.50.565.664.8569.7952.470.69080.09910.79480.53550.667.364.7774.3556.250.76870.04390.82240.67340.770.554.6576.0463.670.75520.09360.81960.50620.874.151.5977.4772.010.79780.01750.82410.77040.973.751.4475.5271.880.78920.02290.81420.7395310.568.183.8876.6961.460.75960.04480.82240.67450.667.7710.0876.8244.530.77410.04890.82860.65670.772.882.7277.2168.360.79680.03140.83210.73710.873.662.4878.1368.230.81600.01190.83050.79810.975.391.7177.4773.050.83090.01010.84460.8125Table 9
The performance of the DPKSVMEL algorithm on dataset Splice.
kɛSimilarityAccuracyAUCMeanStdMaxMinMeanStdMaxMin20.10.566.735.1774.0058.300.85320.03380.88860.77960.670.324.8177.1063.500.84990.00970.86540.83680.776.364.1582.5067.200.87890.01770.90630.85120.879.566.4685.0068.300.92120.00960.93580.90640.985.573.6590.0077.800.95620.00430.96160.950720.50.575.024.1083.0069.900.90310.01050.91880.88810.677.144.9684.1070.400.89900.01470.91720.87380.782.962.5785.7077.400.93010.00800.93780.91270.884.236.3189.4068.000.95290.00410.96080.94640.989.171.4390.4086.300.97030.00320.97560.9643210.585.981.3389.3084.400.94250.00730.95540.93120.685.353.3088.8080.100.95530.00560.96620.94820.788.092.3190.6084.000.96320.00460.96980.95570.890.501.2892.0087.800.97290.00360.97760.96440.992.170.6192.8091.100.97880.00190.98130.975830.10.561.685.2367.9052.800.81500.02390.84670.77500.668.395.2075.6057.900.83390.02970.88200.79500.774.175.7282.4065.000.87820.01710.90900.85920.878.963.3684.7074.000.91510.01070.93430.90090.986.623.0590.3082.000.95700.00470.96210.947030.50.574.065.7080.0060.800.89240.01880.91270.84880.676.096.4581.3060.400.89540.02380.91660.84570.779.576.4984.8065.200.92500.00970.93900.91240.886.571.8688.8082.800.95050.00500.95810.94430.988.844.3491.4076.700.97060.00240.97370.9652310.583.482.4686.5078.100.93950.00600.94870.93040.683.555.8188.7073.700.95420.00470.96000.94490.789.001.7090.8085.100.96260.00320.96700.95770.891.161.0793.0089.800.97410.00230.97930.97170.992.540.8593.5090.900.97930.00130.98150.9769Table 10
The running time of the DPKSVMEL algorithm (second).
DatasetsMeanStdMaxMinAustralian0.05790.00440.06830.0480Breast0.02390.00530.03300.0136Heart0.02250.00300.03090.0154Ionosphere0.03210.00290.03910.0270Sonar0.02570.00150.03230.0226German0.14820.01280.16460.1227Diabetes0.07020.00120.07460.0677Splice0.21590.01200.25240.2011Based on the above experimental results, aN-way ANOVA (analysis of variance) was conducted to compare the effect of the three parameters and the interaction model of every two parameters on Accuracy and AUC. Due to space constrains, we present the p value in the results of ANOVA only as shown in Tables 11 and 12. We can conclude that the results for parameters ɛ and Similarity are significantly different at the p<0.05 level. However, the results for parameter k are not significantly different for most of the datasets, similarly as every two parameter interaction.Table 11
Thep value in ANOVA of the Accuracy.
DatasetskɛSimilarityk ∗ ɛk ∗ Similarityɛ ∗ SimilarityAustralian0.00910.00120.00160.33320.11180.3509Breast0.02600.00180.00000.01750.03100.1785Heart0.00680.00000.00000.10480.04590.0005Ionosphere0.44830.00000.00190.29610.94280.2353Sonar0.26110.00000.00000.27940.20780.2477German0.07640.00010.00010.06230.07580.0534Diabetes0.01770.00200.00020.65240.62960.8198Splice0.04350.00000.00000.42390.09960.0013Table 12
Thep value in ANOVA of the AUC.
DatasetskɛSimilarityk ∗ ɛk ∗ Similarityɛ ∗ SimilarityAustralian0.09070.00010.00240.70500.91490.4190Breast0.13730.09480.00060.80170.21280.2116Heart0.87240.00000.00000.41910.55770.0149Ionosphere0.20560.00000.00010.41570.29210.1523Sonar0.42270.00000.00000.05060.32280.0029German0.14550.00000.00000.64360.81940.1119Diabetes0.00040.00000.00000.03040.18730.0096Splice0.02540.00000.00000.12770.14230.0001To observe the experimental performance of the algorithm more intuitively, Figures2–5 show Accuracy and AUC with the variation of Similarity under different k and ɛ values in the form of the bar graphs on datasets Australian and Breast. The effect of the experimental performance by the three parameters is consistent with the result of ANOVA. The larger the privacy budget ɛ, the higher the classification accuracy of the algorithm. The experimental performance for parameter Similarity is mainly affected by the privacy protection mechanism adopted. When its value is small, there are more non-SVs within the group and the exponential mechanism plays a greater role. Otherwise, the Laplace mechanism plays a greater role. The DPKSVMEL algorithm is more stable on dataset Breast.Figure 2
Accuracy under different k and ɛ on dataset Australian.Figure 3
AUC under different k and ɛ on dataset Australian.Figure 4
Accuracy under different k and ɛ on dataset Breast.Figure 5
AUC under different k and ɛ on dataset Breast.We compared the performance of the DPKSVMEL algorithm and the non-private SVM under different privacy budgets on datasets Australian and Breast from Figures6–9. With the increase of the privacy budget, the performance of the DPKSVMEL algorithm gradually reaches or even exceeds that of non-private SVM.Figure 6
Comparison of algorithmAccuracy under different ɛ on dataset Australian.Figure 7
Comparison of algorithmAUC under different ɛ on dataset Australian.Figure 8
Comparison of algorithmAccuracy under different ɛ on dataset Breast.Figure 9
Comparison of algorithmAUC under different ɛ on dataset Breast.Then, we compared theAccuracy of the DPKSVMEL algorithm and the LabSam algorithm under different privacy budgets on datasets Heart, Ionosphere, Sonar, German, and Diabetes in Figures 10–14. Finally, we compared the Accuracy of the DPKSVMEL algorithm and the DPSVMDVP algorithm under different privacy budgets on dataset Splice in Figure 15. Compared to the LabSam algorithm and the DPSVMDVP algorithm, our DPKSVMEL algorithm has higher classification accuracy and is closer to the non-private SVM under the same privacy budget.Figure 10
Comparison of algorithmAccuracy under different ɛ on dataset Heart.Figure 11
Comparison of algorithmAccuracy under different ɛ on dataset Ionosphere.Figure 12
Comparison of algorithmAccuracy under different ɛ on dataset Sonar.Figure 13
Comparison of algorithmAccuracy under different ɛ on dataset German.Figure 14
Comparison of algorithmAccuracy under different ɛ on dataset Diabetes.Figure 15
Comparison of algorithmAccuracy under different ɛ on dataset Splice.In addition, as the DPKSVMEL algorithm does not change the training process of the classical non-private SVMs, a number of new optimization methods can be easily combined with our proposed algorithm to improve the classification accuracy, for example, CRP algorithm [34] for bilinear analysis and NI-SVM [35] in event analysis tasks.


## 5.1. Datasets

The datasets in our experiments are commonly used for testing SVM algorithms’ performance and are available athttps://www.csie.ntu.edu.tw/∼cjlin/libsvmtools/. Table 1 shows the basic information of the eight datasets and classification accuracy of the non-private SVM with the default parameters based on LIBSVM (version 3.24) [33]. We use the radial basis function as the kernel function in the experiments.Table 1
The basic information of the datasets.
IndexDatasets#data#features#SVAccuracyAUC1Australian6901424485.80.94642Breast683106697.360.99523Heart2701313286.670.93144Ionosphere3513413794.590.98345Sonar2086015986.540.93536German10002459981.20.86037Diabetes768844778.130.84838Splice10006060794.30.9864


## 5.2. Algorithm Performance Experiments

In this section, we evaluated the performance of the DPKSVMEL algorithm by theAccuracy and AUC (the area under a ROC curve). The higher their values, the better the usability of the algorithm. To evaluate the algorithm performance under different parameters setting, we set k at 2 and 3, set privacy budget ɛ at 0.1, 0.5, and 1, and set the lower limit for the Similarity from 0.5 to 0.9. To avoid the influence of randomness on algorithm performance, we execute the algorithm DPKSVMEL 10 times under every set of parameters. Tables 2–9 show the mean value, standard deviation, maximum value, and minimum value of the Accuracy and AUC on the eight datasets. The values in bold represent the best case of the mean value of Accuracy and AUC under the same privacy budget. And, the running time of the DPKSVMEL algorithm is shown in Table 10.Table 2
The performance of the DPKSVMEL algorithm on dataset Australian.
kɛSimilarityAccuracyAUCMeanStdMaxMinMeanStdMaxMin20.10.583.432.5485.9478.260.89630.02370.91880.83520.683.361.8486.0981.300.89880.00960.91480.88840.785.591.1587.6883.770.90770.02110.92680.85050.884.412.8887.2577.680.91620.01020.92770.89920.986.070.6387.3985.220.91350.01000.92460.894020.50.584.172.4787.1080.580.90410.01730.92660.87870.685.321.3587.2583.040.90960.01640.92970.87290.784.713.5987.8375.650.91630.01010.92810.89860.885.671.7487.9782.610.92200.00520.92970.91160.985.881.0287.1083.480.91880.01270.93240.8915210.585.301.8386.8180.870.91710.00710.92610.90380.686.591.0088.1285.070.92580.00750.93700.91220.786.230.7887.6884.780.92260.00970.93170.89850.886.590.7987.5485.510.92950.00260.93380.92460.986.520.5687.3985.800.92870.00620.93720.918130.10.580.715.9286.6768.260.87760.04100.91870.79750.683.552.7286.9678.260.90230.01180.91740.88490.782.652.9186.2378.410.90870.01550.92400.86930.885.431.4887.1082.610.91300.01350.92710.89440.986.030.8887.3984.490.90780.01390.92230.876430.50.581.045.4986.5268.840.89870.01970.92280.86060.683.262.8786.5278.840.89940.01630.91750.87110.782.206.7387.8367.250.90720.01650.92770.87250.885.642.1487.5480.290.91530.01320.93180.88480.985.871.5087.1081.880.92240.00720.93240.9096310.584.872.2887.2579.570.92290.00580.92970.91480.685.361.4286.9682.460.91580.00990.93160.89550.786.141.8287.5481.590.92300.00810.93610.91050.886.200.6187.1085.220.92620.00840.93680.91420.986.410.5787.2585.650.92830.00400.93380.9225Table 3
The performance of the DPKSVMEL algorithm on dataset Breast.
kɛSimilarityAccuracyAUCMeanStdMaxMinMeanStdMaxMin20.10.596.710.5997.2295.460.99430.00070.99550.99300.696.650.5197.2295.310.99460.00030.99520.99430.796.880.3097.2296.340.99440.00070.99530.99260.897.040.3197.5196.490.99390.00110.99500.99100.997.260.2097.5196.780.99350.00090.99480.992320.50.596.790.2897.3696.340.99480.00030.99520.99430.696.490.4597.0795.750.99450.00040.99520.99390.797.100.2897.5196.630.99440.00030.99480.99380.897.230.2197.3696.780.99360.00070.99480.99260.997.310.1997.5196.930.99370.00080.99510.9923210.596.540.5097.3695.900.99510.00030.99540.99460.696.530.4997.2295.900.99500.00040.99540.99440.797.120.2597.3696.630.99470.00040.99500.99390.897.420.1797.6697.220.99400.00070.99480.99260.997.390.1897.6697.070.99310.00080.99410.991630.10.596.090.6896.7895.020.99420.00070.99520.99290.696.540.4497.0795.750.99450.00040.99490.99370.796.730.7297.6695.020.99400.00070.99510.99270.896.840.4097.3696.190.99400.00060.99500.99310.997.130.1797.3696.780.99450.00080.99580.993030.50.596.110.5197.0795.170.99470.00080.99530.99270.696.400.6597.5195.610.99480.00050.99580.99360.797.040.3897.3696.340.99480.00040.99520.99430.897.260.3297.8096.930.99410.00080.99550.99240.997.280.1797.5197.070.99380.00100.99490.9919310.596.560.3597.0795.900.99520.00040.99570.99440.696.780.1497.0796.630.99520.00030.99550.99470.797.310.2597.6696.780.99440.00060.99530.99320.897.390.2297.9597.220.99400.00110.99500.99190.997.440.1097.6697.360.99410.00070.99510.9930Table 4
The performance of the DPKSVMEL algorithm on dataset Heart.
kɛSimilarityAccuracyAUCMeanStdMaxMinMeanStdMaxMin20.10.580.002.5584.8177.040.88630.01840.90620.85000.679.852.5784.0776.670.89270.01630.90820.85370.781.931.4685.1980.000.89320.01680.92090.86140.884.331.1585.9381.850.91040.00820.92360.90170.985.521.0586.6783.700.92140.01120.93470.902620.50.582.812.0185.1978.520.90190.01540.92320.87530.684.191.0586.3082.960.90730.00730.91590.89570.784.261.0185.9382.590.91330.00700.92230.90170.884.632.1387.0479.630.91760.00700.92860.90380.986.190.7687.0484.810.92780.00200.93150.9247210.585.371.0987.0483.700.91440.00590.92230.90540.685.001.0587.0483.330.92030.00510.92920.91350.785.440.7686.6784.440.92270.00540.93170.91520.886.000.8387.0484.810.92540.00350.93270.92130.986.370.7287.4184.810.92930.00540.93860.919830.10.577.564.9284.0770.370.88940.00960.91080.87730.679.562.6283.7076.300.88750.01820.90890.85160.782.191.6684.4478.520.90000.01230.91590.87370.882.743.6986.6774.810.91180.00570.91900.89870.984.631.5586.3081.480.91920.00940.93480.904730.50.581.633.7986.3074.440.89050.03900.92030.78870.683.441.8685.5679.630.90800.00540.91630.89910.784.301.5986.6781.850.91440.00730.92520.90080.885.111.5187.7881.850.91980.00390.92940.91600.985.701.5488.1582.220.92230.00610.93100.9093310.584.371.5185.5681.110.91870.00480.92430.90800.685.151.7787.0481.110.92120.00460.92540.90910.785.671.5788.5282.960.92280.00780.93120.90940.886.001.0387.7884.440.92730.00570.93530.91870.986.150.8087.0484.810.92790.00360.93540.9229Table 5
The performance of the DPKSVMEL algorithm on dataset Ionosphere.
kɛSimilarityAccuracyAUCMeanStdMaxMinMeanStdMaxMin20.10.573.9312.4392.5951.000.94400.01310.96860.92460.676.5513.8391.1748.720.93520.02160.97830.90850.768.0113.2387.4644.440.94700.01360.96430.92500.874.426.2887.1865.810.94380.01470.96730.92260.983.964.1190.6077.780.96430.00960.97520.944720.50.585.505.9492.8872.360.94410.01590.97010.91950.677.819.8892.5960.970.94980.01460.96690.92070.782.513.7089.4677.210.94630.01290.97100.92630.886.184.9393.1677.490.96100.00610.97170.95140.990.512.7792.5984.330.96840.00530.97600.9573210.589.603.0992.5983.190.96070.01230.97900.94000.684.767.8393.4565.810.95980.01010.97530.94660.788.806.5293.7373.220.96780.00930.98080.94690.893.111.0094.3090.880.97040.00630.97970.95860.992.711.7394.3088.600.97510.00360.97990.969830.10.579.3211.1790.6055.840.94110.01420.95820.91710.674.7611.1793.1654.130.93790.01770.96350.90480.773.5611.7291.7455.270.94440.01400.96420.91570.877.355.0886.0470.940.95310.01710.97660.91660.979.096.1985.4766.670.95750.01230.97250.940830.50.582.517.1892.5970.090.94570.02340.97590.89370.677.619.3788.3261.540.95670.01620.98010.93280.776.8912.8590.3153.850.95800.01100.97170.94100.884.766.4392.8876.070.95970.00960.97180.94520.989.603.1193.1683.480.97070.00500.98070.9649310.585.646.9093.4574.930.95390.01350.96870.92990.683.4510.6994.0263.250.96510.01020.97490.93820.789.263.5592.5982.910.97270.00740.98450.95920.891.171.5793.1688.600.97230.00590.98040.96160.992.191.8094.3088.600.97570.00500.98170.9648Table 6
The performance of the DPKSVMEL algorithm on dataset Sonar.
kɛSimilarityAccuracyAUCMeanStdMaxMinMeanStdMaxMin20.10.569.426.0876.4458.170.82600.03430.88940.77510.670.727.1278.3759.130.84530.02540.88200.79620.776.255.0083.6567.310.87660.02720.91450.82460.880.053.3184.1373.560.89790.01750.91970.86080.981.733.7985.1074.520.91950.00780.92970.906220.50.573.563.2377.8866.830.85500.02800.90850.81560.672.364.7779.8165.380.85540.03380.90080.81270.777.884.2884.6270.670.88890.01600.91060.86130.880.384.4184.1371.630.90410.01220.91550.88080.983.943.7587.9877.400.92580.01140.93700.8962210.580.143.3685.5875.960.89850.01750.93110.87490.679.424.7384.6270.670.90250.01770.92870.87510.782.552.2986.0679.330.91420.01200.93190.89780.883.612.6685.5876.920.91940.00480.92700.91260.985.341.7187.5081.730.93030.00750.94070.916230.10.570.586.1780.2958.170.81840.05500.87310.69900.673.806.4181.7359.130.83210.04720.86640.73790.773.034.9177.8861.540.85090.02120.87130.80760.875.386.7882.2160.100.89110.02080.92820.86010.982.503.1087.9876.440.91470.01230.93620.895130.50.574.336.4382.6959.130.85380.03520.88980.76270.677.842.8283.1772.120.88440.02240.91990.84990.780.193.9785.1073.080.88700.02370.91330.83910.881.921.3383.6579.810.90190.01220.91590.88080.982.453.6086.0676.440.92330.00590.93100.9143310.580.343.2685.1075.960.90000.01390.92110.87900.681.352.6785.1076.920.90740.02120.93720.87050.783.511.7986.0681.250.91080.01190.92630.88980.884.281.8186.5479.810.92330.01020.93810.90490.985.771.1187.9884.130.93070.00390.93610.9229Table 7
The performance of the DPKSVMEL algorithm on dataset German.
kɛSimilarityAccuracyAUCMeanStdMaxMinMeanStdMaxMin20.10.572.191.7074.8070.000.72670.02960.76260.66900.673.081.5574.3069.600.76830.01120.78340.75140.773.423.7577.1064.300.76830.02180.79730.73520.873.302.6077.9070.000.78800.01230.80330.76160.977.161.2779.3075.600.80560.00790.81390.791020.50.572.913.2075.9064.500.76130.01920.78190.72370.671.913.2575.9064.400.78640.01400.80430.76940.771.567.1077.9055.300.80020.01030.81830.78310.874.564.1278.5067.000.80300.01310.82130.78140.975.523.6079.5068.100.82410.01280.83680.7936210.574.703.5478.4066.100.80180.01050.81600.78640.673.172.6377.1069.100.81180.00560.82180.80510.772.844.2478.1065.800.82050.00640.82680.80880.877.412.3379.7073.000.82490.00540.83250.81530.980.270.4380.8079.600.83810.00400.84250.832230.10.571.132.3974.0067.500.73070.02350.77570.70250.673.491.7375.8071.300.75220.02400.78060.69900.774.171.0375.8072.700.77430.01590.79860.74960.871.696.7978.0054.500.76820.03100.80470.72490.976.203.0379.0069.500.80090.01540.82240.773730.50.573.671.4075.2071.300.75680.02080.77660.72040.672.943.6277.3065.500.78080.01710.80830.75240.773.902.8976.9069.000.78680.02350.80800.72470.871.876.7078.4056.000.80780.00970.82200.79290.977.811.9179.8073.500.82140.01120.83960.7980310.576.161.8078.7073.200.80150.01380.81160.76800.674.941.8377.4072.200.80870.00720.82120.79830.776.631.9578.7072.900.81480.00730.82500.80400.878.521.1380.1076.100.82620.00510.83410.81420.980.171.0581.8077.900.84200.00520.85020.8331Table 8
The performance of the DPKSVMEL algorithm on dataset Diabetes.
kɛSimilarityAccuracyAUCMeanStdMaxMinMeanStdMaxMin20.10.565.960.7167.0664.970.76610.04560.81300.65390.667.622.7572.1465.230.70610.11230.80450.51420.770.554.0377.3464.970.78250.03590.83850.72190.871.483.6776.0466.150.79190.03210.82870.73850.974.402.5977.0870.310.80950.01780.83290.786420.50.568.593.6073.7060.550.72460.11120.79580.44760.670.923.1075.3966.540.78550.02250.81340.74080.769.575.0574.7457.420.76610.05510.82990.62550.872.722.0877.2169.790.78890.03350.82950.73160.974.432.2777.3470.180.81520.02050.84160.7851210.571.397.6377.3450.520.79390.02190.83150.75270.669.996.1175.1353.520.79050.02990.82610.73880.772.662.4775.2666.150.81050.01730.83380.77710.875.052.3377.0870.180.81410.01840.83740.77250.975.641.8278.2671.880.83090.00930.84130.813830.10.565.731.1067.1963.410.70660.06850.78940.60580.666.291.3968.4964.580.70130.07320.80340.54000.767.982.5472.7964.970.73690.07040.80070.57270.869.822.4575.2666.670.74720.04420.80900.67980.969.755.4477.3459.240.75200.06190.82830.644630.50.565.664.8569.7952.470.69080.09910.79480.53550.667.364.7774.3556.250.76870.04390.82240.67340.770.554.6576.0463.670.75520.09360.81960.50620.874.151.5977.4772.010.79780.01750.82410.77040.973.751.4475.5271.880.78920.02290.81420.7395310.568.183.8876.6961.460.75960.04480.82240.67450.667.7710.0876.8244.530.77410.04890.82860.65670.772.882.7277.2168.360.79680.03140.83210.73710.873.662.4878.1368.230.81600.01190.83050.79810.975.391.7177.4773.050.83090.01010.84460.8125Table 9
The performance of the DPKSVMEL algorithm on dataset Splice.
kɛSimilarityAccuracyAUCMeanStdMaxMinMeanStdMaxMin20.10.566.735.1774.0058.300.85320.03380.88860.77960.670.324.8177.1063.500.84990.00970.86540.83680.776.364.1582.5067.200.87890.01770.90630.85120.879.566.4685.0068.300.92120.00960.93580.90640.985.573.6590.0077.800.95620.00430.96160.950720.50.575.024.1083.0069.900.90310.01050.91880.88810.677.144.9684.1070.400.89900.01470.91720.87380.782.962.5785.7077.400.93010.00800.93780.91270.884.236.3189.4068.000.95290.00410.96080.94640.989.171.4390.4086.300.97030.00320.97560.9643210.585.981.3389.3084.400.94250.00730.95540.93120.685.353.3088.8080.100.95530.00560.96620.94820.788.092.3190.6084.000.96320.00460.96980.95570.890.501.2892.0087.800.97290.00360.97760.96440.992.170.6192.8091.100.97880.00190.98130.975830.10.561.685.2367.9052.800.81500.02390.84670.77500.668.395.2075.6057.900.83390.02970.88200.79500.774.175.7282.4065.000.87820.01710.90900.85920.878.963.3684.7074.000.91510.01070.93430.90090.986.623.0590.3082.000.95700.00470.96210.947030.50.574.065.7080.0060.800.89240.01880.91270.84880.676.096.4581.3060.400.89540.02380.91660.84570.779.576.4984.8065.200.92500.00970.93900.91240.886.571.8688.8082.800.95050.00500.95810.94430.988.844.3491.4076.700.97060.00240.97370.9652310.583.482.4686.5078.100.93950.00600.94870.93040.683.555.8188.7073.700.95420.00470.96000.94490.789.001.7090.8085.100.96260.00320.96700.95770.891.161.0793.0089.800.97410.00230.97930.97170.992.540.8593.5090.900.97930.00130.98150.9769Table 10
The running time of the DPKSVMEL algorithm (second).
DatasetsMeanStdMaxMinAustralian0.05790.00440.06830.0480Breast0.02390.00530.03300.0136Heart0.02250.00300.03090.0154Ionosphere0.03210.00290.03910.0270Sonar0.02570.00150.03230.0226German0.14820.01280.16460.1227Diabetes0.07020.00120.07460.0677Splice0.21590.01200.25240.2011Based on the above experimental results, aN-way ANOVA (analysis of variance) was conducted to compare the effect of the three parameters and the interaction model of every two parameters on Accuracy and AUC. Due to space constrains, we present the p value in the results of ANOVA only as shown in Tables 11 and 12. We can conclude that the results for parameters ɛ and Similarity are significantly different at the p<0.05 level. However, the results for parameter k are not significantly different for most of the datasets, similarly as every two parameter interaction.Table 11
Thep value in ANOVA of the Accuracy.
DatasetskɛSimilarityk ∗ ɛk ∗ Similarityɛ ∗ SimilarityAustralian0.00910.00120.00160.33320.11180.3509Breast0.02600.00180.00000.01750.03100.1785Heart0.00680.00000.00000.10480.04590.0005Ionosphere0.44830.00000.00190.29610.94280.2353Sonar0.26110.00000.00000.27940.20780.2477German0.07640.00010.00010.06230.07580.0534Diabetes0.01770.00200.00020.65240.62960.8198Splice0.04350.00000.00000.42390.09960.0013Table 12
Thep value in ANOVA of the AUC.
DatasetskɛSimilarityk ∗ ɛk ∗ Similarityɛ ∗ SimilarityAustralian0.09070.00010.00240.70500.91490.4190Breast0.13730.09480.00060.80170.21280.2116Heart0.87240.00000.00000.41910.55770.0149Ionosphere0.20560.00000.00010.41570.29210.1523Sonar0.42270.00000.00000.05060.32280.0029German0.14550.00000.00000.64360.81940.1119Diabetes0.00040.00000.00000.03040.18730.0096Splice0.02540.00000.00000.12770.14230.0001To observe the experimental performance of the algorithm more intuitively, Figures2–5 show Accuracy and AUC with the variation of Similarity under different k and ɛ values in the form of the bar graphs on datasets Australian and Breast. The effect of the experimental performance by the three parameters is consistent with the result of ANOVA. The larger the privacy budget ɛ, the higher the classification accuracy of the algorithm. The experimental performance for parameter Similarity is mainly affected by the privacy protection mechanism adopted. When its value is small, there are more non-SVs within the group and the exponential mechanism plays a greater role. Otherwise, the Laplace mechanism plays a greater role. The DPKSVMEL algorithm is more stable on dataset Breast.Figure 2
Accuracy under different k and ɛ on dataset Australian.Figure 3
AUC under different k and ɛ on dataset Australian.Figure 4
Accuracy under different k and ɛ on dataset Breast.Figure 5
AUC under different k and ɛ on dataset Breast.We compared the performance of the DPKSVMEL algorithm and the non-private SVM under different privacy budgets on datasets Australian and Breast from Figures6–9. With the increase of the privacy budget, the performance of the DPKSVMEL algorithm gradually reaches or even exceeds that of non-private SVM.Figure 6
Comparison of algorithmAccuracy under different ɛ on dataset Australian.Figure 7
Comparison of algorithmAUC under different ɛ on dataset Australian.Figure 8
Comparison of algorithmAccuracy under different ɛ on dataset Breast.Figure 9
Comparison of algorithmAUC under different ɛ on dataset Breast.Then, we compared theAccuracy of the DPKSVMEL algorithm and the LabSam algorithm under different privacy budgets on datasets Heart, Ionosphere, Sonar, German, and Diabetes in Figures 10–14. Finally, we compared the Accuracy of the DPKSVMEL algorithm and the DPSVMDVP algorithm under different privacy budgets on dataset Splice in Figure 15. Compared to the LabSam algorithm and the DPSVMDVP algorithm, our DPKSVMEL algorithm has higher classification accuracy and is closer to the non-private SVM under the same privacy budget.Figure 10
Comparison of algorithmAccuracy under different ɛ on dataset Heart.Figure 11
Comparison of algorithmAccuracy under different ɛ on dataset Ionosphere.Figure 12
Comparison of algorithmAccuracy under different ɛ on dataset Sonar.Figure 13
Comparison of algorithmAccuracy under different ɛ on dataset German.Figure 14
Comparison of algorithmAccuracy under different ɛ on dataset Diabetes.Figure 15
Comparison of algorithmAccuracy under different ɛ on dataset Splice.In addition, as the DPKSVMEL algorithm does not change the training process of the classical non-private SVMs, a number of new optimization methods can be easily combined with our proposed algorithm to improve the classification accuracy, for example, CRP algorithm [34] for bilinear analysis and NI-SVM [35] in event analysis tasks.


## 6. Conclusions

In this paper, we study the privacy problem of the classification model of kernel SVMs. We proposed the DPKSVMEL algorithm based on the exponential and Laplace hybrid mechanism. The privacy of SVs is protected by postprocessing the non-private classification model with DP to prevent privacy leakage of the SVs. The DPKSVMEL algorithm is proved to satisfy DP theoretically and overcomes some shortcomings in the existing private SVM algorithm. Firstly, the postprocessing in the DPKSVMEL algorithm does not change the training process of the non-private kernel SVMs. Therefore, no complex sensitivity analysis is required like output perturbation and objective perturbation. Secondly, the DPKSVMEL algorithm avoids the additional risk of privacy disclosure and the consideration of projection dimension caused by the transformation from nonlinear SVMs to linear SVMs using random projection as PrivateSVM and hybrid SVM. Meanwhile, the DPKSVMEL algorithm has higher classification accuracy than the newest private SVM algorithms LabSam and DPSVMDVP under the same privacy budget. However, the DPKSVMEL algorithm views the value of kernel function as the probability of similarity between a non-SV and a SV that is valid only for some kernel functions with values in the range 0 to 1. Furthermore, the DPKSVMEL algorithm has poor performance for the datasets with a high proportion of SVs, especially when the similarity lower limit is small. In the future, we will work in two aspects. One is to extend the DPKSVMEL algorithm into more kernel functions. The other is to consider setting different similarity lower limits for different groups.



---

*Source: 9506907-2021-12-10.xml*