# Differentially Private Singular Value Decomposition for Training Support Vector Machines

Authors: Zhenlong Sun; Jing Yang; Xiaoye Li
Journal: Computational Intelligence and Neuroscience
 (2022)

---

## Abstract

Support vector machine (SVM) is an efficient classification method in machine learning. The traditional classification model of SVMs may pose a great threat to personal privacy, when sensitive information is included in the training datasets. Principal component analysis (PCA) can project instances into a low-dimensional subspace while capturing the variance of the matrixA as much as possible. There are two common algorithms that PCA uses to perform the principal component analysis, eigenvalue decomposition (EVD) and singular value decomposition (SVD). The main advantage of SVD compared with EVD is that it does not need to compute the matrix of covariance. This study presents a new differentially private SVD algorithm (DPSVD) to prevent the privacy leak of SVM classifiers. The DPSVD generates a set of private singular vectors that the projected instances in the singular subspace can be directly used to train SVM while not disclosing privacy of the original instances. After proving that the DPSVD satisfies differential privacy in theory, several experiments were carried out. The experimental results confirm that our method achieved higher accuracy and better stability on different real datasets, compared with other existing private PCA algorithms used to train SVM.


---

## Body

## 1. Introduction

In the past decade, more and more personal information has been stored in electronic databases for machine learning and personalized recommendation. The data sharing and analysis bring lots of convenience to people's lives, but pose a great threat to personal privacy. Support vector machine (SVM) [1] is a popular classification method that searches for the best hyperplane that separates two class instances by solving a quadratic optimization problem. It has been applied in pattern recognition such as image recognition and text classification. In the classification model of SVM, the most serious privacy issue is that the support vectors (SVs) are directly obtained from the training datasets [2]. Therefore, the classification model should be privately published to avoid disclosing personal sensitive information.Differential privacy (DP) [3–6] has a strict mathematical definition and the level of privacy protection can be quantified by a small parameter ɛ named privacy budget. DP has been becoming an accept standard. It guarantees that the result of an analysis is virtually independent of the addition or removal of one record. DP has attracted a growing research attention [7]. The common mechanisms for implementing DP include Laplace mechanism [8], Gaussian mechanism [9], and exponential mechanism [10].Principal component analysis (PCA) [9] solves a low-rank subspace, which completely captures the variance of matrix A. The main advantages of working with the low-rank approximation of A include higher time and space efficiency, less noise, and removal of correlation between features. Through PCA, the original instances are projected into a low-dimensional subspace and the features become linearly independent. Eigenvalue decomposition (EVD) and singular value decomposition (SVD) are two common algorithms to perform PCA. They are related to the familiar theory of matrix diagonalization. The EVD is used for a symmetric matrix and SVD for an arbitrary matrix. Furthermore, SVD does not need to compute the matrix of covariance compared with EVD [11].This study researches the privacy leakage problem of SVM classifier. To overcome some shortcomings in the existing private SVMs, a differentially private singular value decomposition (DPSVD) algorithm is proposed to keep SVs private in the classification model of SVM. This study makes the following innovations:(i)
The authors proposed an idea that projecting the training instances into the low-dimensional singular subspace and the SVM can train the classification model on it while not violating the privacy requirements for the training data.(ii)
The projection process of the DPSVD satisfies DP, and the generated singular vectors are also private which can be provided directly to users for classification testing.(iii)
In the DPSVD, the projection process is implemented by SVD. The main advantage is that SVD does not need to calculate the matrix of covariance compared with EVD. It takes up a lot of memory space for high-dimensional data.(iv)
Our method protects privacy of the training instances before training the classification model; many optimization methods of SVMs can be applied directly to the training progress.(v)
After proving that the DPSVD satisfies differential privacy in theory, several experiments were carried out. The experimental results confirm that our method achieved higher accuracy and better stability on different real datasets, compared with other existing private PCA algorithms used to train SVM.


## 2. Related Work

From a privacy perspective, SVMs have serious privacy issues, because SVs tend to be directly obtained from the training datasets. There is a lot of work to solve this privacy problem based on DP. Chaudhuri et al. [12, 13] proposed two perturbation-based methods for problems like linear SVM classification. For nonlinear kernel SVM, they derived the kernel function through random projection and linearized the function. However, it is hard to analyze the sensitivity of the output perturbation, and the differentiability criteria are required in the loss function of objective perturbation. To learn SVM privately, Rubinstein et al. [14] developed two feature mapping methods by adding noise to the output classifier. But their methods only apply to the kernels that do not change with translation. Li et al. [15] designed a mixed SVM, which alleviate much of the noise through Fourier transform based on a few open-consented information. Zhang et al. [16] proposed DPSVMDVP by adding Laplace noise to the dual variables based on the error rate. Liu et al. [17] presented an innovative private classifier called LabSam by random sampling under the exponential mechanism. Sun et al. [18] proposed the DPWSS, which introduces randomness into SVM training; they also proposed another private SVM algorithm DPKSVMEL based on exponential and Laplace hybrid mechanism [19] for the kernel SVM to prevent privacy leakage of the SVs.PCA constructs a set of new features to describe the instances in a low-dimensional subspace. When the generated projection vectors are private, the new instances in the low-dimensional subspace are private as well, and they can be used directly to train SVMs without compromising the privacy of the instances. There are several researches on private PCA. Blum et al. [20] developed SuLQ by disturbing the matrix of covariance with Gaussian noise. However, the greatest eigenvalue might be not real, due to the asymmetry of the noise matrix. Chaudhuri et al. [21] modified SuLQ framework with a symmetric noise matrix and used it for data publishing. Dwork et al. [9] disturbed the matrix of covariance with Gaussian noise. Imtiaz and Sarwate [22, 23] and Jiang et al. [24] disturbed the matrix of covariance with Wishart noise and it guarantees that the perturbed matrix of covariance is positive semidefinite. Xu et al. [25] and Huang et al. [26] added symmetric Laplace noise to the matrix of covariance. Those methods above all generate the perturbed matrix of covariance by adding a noise matrix and then perform EVD to implement PCA. And only [26] measured the availability of the private PCA by SVM, but not to research private PCA from the privacy perspective of SVM. Recently, SVD has been widely used in collaborative filtering [27], deep learning [28], data compression [29, 30], and images watermarking [31]. There are few researches on privacy-preserving data mining based on SVD. Keyvanpour et al. [32] defined a method that combined SVD and feature selection to benefit from the advantages of both domains. Li et al. [33] gave a new algorithm for protecting privacy based on nonnegative matrix factorization and SVD. Kousika et al. [34] proposed a methodology based on SVD and 3D rotation data perturbation for preserving privacy of data.


## 3. Background

Table1 summarizes the symbols used in this study.Table 1
Symbols.
SymbolDescriptionD, D′The adjacent matrix of datasetsA, A˜Matrix of covariancexi∈Rd.Train instanceyi∈1,−1.LabelΑDual vectorQSymmetric matrix for kernel functionKKernel functionEVector composed entirely of onesCUpper limit ofαλiEigenvaluevi.EigenvectorΓThe accumulative contribution rate of principal componentsU, VThe singular vectors or eigenvectors matrix∑, SThe singular values or eigenvalues diagonal matrixσiSingular valueIUnit diagonal matrixMA randomized mechanismOAll subsets of possible outcomes of mechanismMɛPrivacy budgetβ, δPrivacy parameterS1, S2Theℓ1 and ℓ2 sensitivity of functionLaplace(b)Laplace noise (mean: 0; scale:b)N(0, τ2)Gaussian noise with (mean: 0; deviation:τ)


### 3.1. Support Vector Machines

Given training instancesxi∈Rd and labels yi∈1,−1 the classification model of SVM can be obtained by solving the following optimization problem [35]:(1)minαfα=12αTQα−eTα.(2)Subject to0≤αi≤C,i=1,...,lyTα=0,where α is a dual vector; Q is a symmetric matrix, Qij = yiyjK(xi, xj), and K is the kernel function.Letx be a new instance. The label of x can be predicted by the decision function as follows:(3)fx=∑i=1nαiyiKxi,x+b.In the classification model, only the SVs determine the maximal margin and correspond to the nonzeroαis, and others equal zero. From a privacy perspective, the classification model has serious privacy issues as the SVs are intact instances.


### 3.2. Principal Component Analysis

PCA computes a low-rank subspace and achieves the dimensionality reduction for high-dimensional data, shedding light on the use of private SVM in high-dimensional data classification. For a given data matrixD∈Rn×d with d features of n instances, the i-th row of D is denoted by xi and assumes that its ℓ2 norm satisfies ||xi||2 ≤ 1. After the matrix is centralized by column, the matrix of covariance can be obtained as(4)A=1nDTD=1n∑i=1nxiTxi.The matrix of covariance is a real symmetric matrix; therefore its eigenvalues and corresponding eigenvectors can be obtained by EVD:(5)Avi=λivi,where λi is one of the eigenvalues and vi is its corresponding eigenvector. The λi could be treated as variance of the i-th principal component to denote its importance and is sorted in descending order. Generally, the threshold of the accumulative contribution rate of principal components γ (0≤γ≤1) is set to decide the target dimension k by(6)∑i=1kλi∑i=1dλi≥γ.According to the diagonalization theory of matrix and (5), it obtains another representation of EVD as follows:(7)A=V∑VT,where V is an orthogonal matrix consisting of eigenvectors in columns and ∑ is a diagonal matrix taking eigenvalues as diagonal entries. Compared with EVD, SVD can be applied to an arbitrary real matrix and it does not need to calculate matrix of covariance. The representation of SVD is shown as follows:(8)D=USVT,where U and V are the left and right singular matrices, which consist of left and right singular vectors, respectively; S is a diagonal matrix taking singular values as diagonal entries. The singular value σi is also sorted in descending order. The relationship between EVD and SVD is as follows:(9)A=1nDTD=1nUSVTTUSVT=1nVSUTUSVT=1nVSSVT=1nVS2VT,(10)A˜=1nDDT=1nUSVTUSVTT=1nUSVTVSUT=1nUSSUT=1nUS2UT,where UTU=I and VTV=I, because U and V are both made up of unit orthogonal vectors; they also are called orthonormal basis matrices. The coefficient 1/n has nothing to do with the eigenvectors and the proportionality of eigenvalues. We generally use DTD to approximate the matrix of covariance. From (9) and (10), we can conclude that the SVD of an arbitrary real matrix yields a similar result to the EVD of its matrix of covariance. In the SVD of D, the right singular vectors serve as the eigenvectors of DTD, and the left ones serve as those of DDT. The singular values equal the square roots of the nonzero eigenvalues of DTD and DDT.


### 3.3. Differential Privacy

Definition 1.
(differential privacy (see [3])). A stochastic mechanism M satisfies (ε, δ)-differential privacy, provided that, for every two adjacent matrices D and D′ differing in exactly one row, and for all subsets of probable outcomes O⊆ Range(M),(11)PrMD∈O≤expε×PrMD′∈O+δ.
Whenδ equals zero, M satisfies ε-differential privacy.Definition 2.
(sensitivity (see [3])). For a given function q:D⟶Rd, and adjacent matrices D and D′, the sensitivities S1 and S2 of function q can be, respectively, expressed as(12)S1=maxD,D′qD−qD′1andS2=maxD,D′qD−qD′2.
S1 corresponding to ℓ1 norm is usually used in Laplace mechanism, while S2 corresponding to ℓ2 norm is used in Gaussian mechanism.Definition 3.
(Laplace mechanism (see [8])). For a numeric function q:D⟶Rd, with scale factor b = S1/ɛ. The Laplace mechanism, which adds independent random noise distributed as Laplace(b) to each output of q(D), ensures ε-differential privacy.Definition 4.
(Gaussian mechanism (see [9])). For a numeric function q:D⟶Rd, let β=S22ln1.25/δ/ε. The Gaussian mechanism, which adds independent random noise distributed as N(0, β2) to each output of q(D), ensures (ε, δ)-differential privacy.


## 3.1. Support Vector Machines

Given training instancesxi∈Rd and labels yi∈1,−1 the classification model of SVM can be obtained by solving the following optimization problem [35]:(1)minαfα=12αTQα−eTα.(2)Subject to0≤αi≤C,i=1,...,lyTα=0,where α is a dual vector; Q is a symmetric matrix, Qij = yiyjK(xi, xj), and K is the kernel function.Letx be a new instance. The label of x can be predicted by the decision function as follows:(3)fx=∑i=1nαiyiKxi,x+b.In the classification model, only the SVs determine the maximal margin and correspond to the nonzeroαis, and others equal zero. From a privacy perspective, the classification model has serious privacy issues as the SVs are intact instances.


## 3.2. Principal Component Analysis

PCA computes a low-rank subspace and achieves the dimensionality reduction for high-dimensional data, shedding light on the use of private SVM in high-dimensional data classification. For a given data matrixD∈Rn×d with d features of n instances, the i-th row of D is denoted by xi and assumes that its ℓ2 norm satisfies ||xi||2 ≤ 1. After the matrix is centralized by column, the matrix of covariance can be obtained as(4)A=1nDTD=1n∑i=1nxiTxi.The matrix of covariance is a real symmetric matrix; therefore its eigenvalues and corresponding eigenvectors can be obtained by EVD:(5)Avi=λivi,where λi is one of the eigenvalues and vi is its corresponding eigenvector. The λi could be treated as variance of the i-th principal component to denote its importance and is sorted in descending order. Generally, the threshold of the accumulative contribution rate of principal components γ (0≤γ≤1) is set to decide the target dimension k by(6)∑i=1kλi∑i=1dλi≥γ.According to the diagonalization theory of matrix and (5), it obtains another representation of EVD as follows:(7)A=V∑VT,where V is an orthogonal matrix consisting of eigenvectors in columns and ∑ is a diagonal matrix taking eigenvalues as diagonal entries. Compared with EVD, SVD can be applied to an arbitrary real matrix and it does not need to calculate matrix of covariance. The representation of SVD is shown as follows:(8)D=USVT,where U and V are the left and right singular matrices, which consist of left and right singular vectors, respectively; S is a diagonal matrix taking singular values as diagonal entries. The singular value σi is also sorted in descending order. The relationship between EVD and SVD is as follows:(9)A=1nDTD=1nUSVTTUSVT=1nVSUTUSVT=1nVSSVT=1nVS2VT,(10)A˜=1nDDT=1nUSVTUSVTT=1nUSVTVSUT=1nUSSUT=1nUS2UT,where UTU=I and VTV=I, because U and V are both made up of unit orthogonal vectors; they also are called orthonormal basis matrices. The coefficient 1/n has nothing to do with the eigenvectors and the proportionality of eigenvalues. We generally use DTD to approximate the matrix of covariance. From (9) and (10), we can conclude that the SVD of an arbitrary real matrix yields a similar result to the EVD of its matrix of covariance. In the SVD of D, the right singular vectors serve as the eigenvectors of DTD, and the left ones serve as those of DDT. The singular values equal the square roots of the nonzero eigenvalues of DTD and DDT.


## 3.3. Differential Privacy

Definition 1.
(differential privacy (see [3])). A stochastic mechanism M satisfies (ε, δ)-differential privacy, provided that, for every two adjacent matrices D and D′ differing in exactly one row, and for all subsets of probable outcomes O⊆ Range(M),(11)PrMD∈O≤expε×PrMD′∈O+δ.
Whenδ equals zero, M satisfies ε-differential privacy.Definition 2.
(sensitivity (see [3])). For a given function q:D⟶Rd, and adjacent matrices D and D′, the sensitivities S1 and S2 of function q can be, respectively, expressed as(12)S1=maxD,D′qD−qD′1andS2=maxD,D′qD−qD′2.
S1 corresponding to ℓ1 norm is usually used in Laplace mechanism, while S2 corresponding to ℓ2 norm is used in Gaussian mechanism.Definition 3.
(Laplace mechanism (see [8])). For a numeric function q:D⟶Rd, with scale factor b = S1/ɛ. The Laplace mechanism, which adds independent random noise distributed as Laplace(b) to each output of q(D), ensures ε-differential privacy.Definition 4.
(Gaussian mechanism (see [9])). For a numeric function q:D⟶Rd, let β=S22ln1.25/δ/ε. The Gaussian mechanism, which adds independent random noise distributed as N(0, β2) to each output of q(D), ensures (ε, δ)-differential privacy.


## 4. Materials and Methods

To overcome the shortcomings in the existing private SVMs, we proposed the DPSVD. The DPSVD privately projects the original instances to a low-dimension singular subspace and trains a SVM classification model in it to protect the privacy of training instances.


### 4.1. Algorithm Description: Algorithm 1 Is the Pseudocode of the DPSVD

The algorithm 1 describes the implementation process of the DPSVD for training a private classification model of SVM. Firstly, it generates a noise matrix sampled from Gaussian distribution, and this step does not need to symmetrize the noise matrix as the existing private PCA algorithms. Secondly, it adds the noise matrix to the raw data matrix rather than the matrix of covariance of the raw data. When features far outnumber instances, the matrix of covariance will take up a lot of memory space, especially for high-dimensional data. Meanwhile, the matrix of covariance will magnify errors in the raw data to some extent. Thirdly, the DPVSD algorithm computes the singular values and singular matrices by SVD, while the existing private PCA algorithms use EVD. Generally, SVD can be considered a black box and has higher execution efficiency compared with EVD, although the two decomposition methods generate the same projection subspace by singular vectors or eigenvectors under the nonprivate situation. There are similar computing processes with the EVD in the next three steps. Lastly, the DPSVD distributes the private classification model to predict the new instances, prior to idea that it projects them to the same singular subspace by the private singular vectors. In brief, the DPSVD trains a private SVM classifier for predicting the new instances in future.Algorithm 1: DPSVD.
Input: Raw data matrix D∈Rn×d, instances n, features d, privacy parameters ε, δ and β, accumulative contribution rate of principal components γ;Output: Classification model fx=∑i=1nαiyiKxi,x+b, private singular vectors Vk;BeginGenerate a noise matrixE∈Rn×d, every entry is i.i.d. and sampled from N(0, β2);Add the noise matrix to the raw data matrixD’ = D + E;Compute the singular valuesσ and singular matrices U, V of D′ by SVD, D′=USVT;Select the target dimensionk according to ∑i=1kσi2/∑i=1dσi2≥γ;Select firstk singular vectors Vk to project the original training instances to the low-dimensional singular subspace Y = DVk;Compute the classification modelf(x) in the singular subspace;Usef(x) and Vk to predict the new instances.End


### 4.2. Privacy Analysis

Firstly, the sensitivity of the functionq(D) is analyzed, and then the DPSVD is demonstrated to satisfy (ε, δ)-differential privacy. In the DPSVD algorithm, the noise matrix is added to the data matrix D; therefore q(D) = D. Given that two adjacent data matrices D and D′ differ by exactly one row corresponding to an instance, we set D′ obtained from D by deleting the last row, D=x1,...,xnT∈Rn×d and D′=x1,...,xn−1T∈Rn−1×d, and assume each row has unit ℓ2 norm ||xi||2≤1 at the most.Lemma 1.
The sensitivity of the functionq(D) S2 equals one.Proof.
According to Definition2, it obtains S2 by the following inequation:(13)S2=maxD,D′qD−qD′2=maxD,D′D−D′2=maxD,D′xn2≤1
Therefore, the sensitivity of the functionq(D) equals one.Theorem 1.
The DPSVD satisfies (ε, δ)-differential privacy.Proof.
To demonstrate that the DPSVD satisfies (ε, δ)-differential privacy, it is necessary to demonstrate every step in the algorithm satisfies it. According to Lemma 1, it obtains that S2 equals one. Let β=S22ln1.25/δ/ε=2ln1.25/δ/ε; then Step (1) and Step (2) satisfy DP according to Definition 4. Step (3) and Step (4) postprocess the private data matrix D′; they also satisfy DP. Step (5) generates the private singular vectors Vk; the projected instances Y in the low-dimensional singular subspace are private as well. Meanwhile, Y does not need to be distributed to users. Step (6) and Step (7) compute the classification model based on private projection instances and distribute it together with private singular vector to predict the new instances. The last three steps do not violate the privacy requirement of DP. Therefore, the DPSVD satisfies (ε, δ)-differential privacy.


### 4.3. Algorithm Comparison

The three algorithms were compared theoretically between DPSVD, AG [9], and DPPCA-SVM [26] summarized in Table 2. Other ones have been compared by the DPPCA-SVM algorithm. Our algorithm uses SVD to perform PCA; it does not need to compute matrix of covariance and symmetrize the noise matrix as the description above. It obtains the same noise scale as AG algorithm, because they use identical mechanism of DP to generate the noise matrix.Table 2
The comparison between the three algorithms.
AlgorithmPCAAdding modeNoise formNoise scaleMechanismPrivacy levelDPSVDSVDDAsymmetricOd/nεGaussian(ε, δ)AGEVDDTD/nSymmetricOd/nεGaussian(ε, δ)DPPCA-SVMEVDDTD/nSymmetricOd/nεLaplace(ε, 0)Therefore, the classification model and the singular vectors for projection are both private; they can be used to predict the new instances in the same singular subspace. The main advantage of the DPSVD compared with other private SVMs is that our algorithm trains the classification model in the private low-dimensional singular subspace generated by SVD. In this way, the features of the instances in the singular subspace become linearly independent and low-dimensional and therefore have higher time and space efficiency for training the classification model. The difference between our algorithm with other private PCA algorithms is that it does not need to calculate the matrix of covariance or symmetrize the noise matrix. Meanwhile, the DPSVD protects privacy of the training instances before training the classification model; many optimization methods of SVMs can be applied directly to the training progress.


## 4.1. Algorithm Description: Algorithm 1 Is the Pseudocode of the DPSVD

The algorithm 1 describes the implementation process of the DPSVD for training a private classification model of SVM. Firstly, it generates a noise matrix sampled from Gaussian distribution, and this step does not need to symmetrize the noise matrix as the existing private PCA algorithms. Secondly, it adds the noise matrix to the raw data matrix rather than the matrix of covariance of the raw data. When features far outnumber instances, the matrix of covariance will take up a lot of memory space, especially for high-dimensional data. Meanwhile, the matrix of covariance will magnify errors in the raw data to some extent. Thirdly, the DPVSD algorithm computes the singular values and singular matrices by SVD, while the existing private PCA algorithms use EVD. Generally, SVD can be considered a black box and has higher execution efficiency compared with EVD, although the two decomposition methods generate the same projection subspace by singular vectors or eigenvectors under the nonprivate situation. There are similar computing processes with the EVD in the next three steps. Lastly, the DPSVD distributes the private classification model to predict the new instances, prior to idea that it projects them to the same singular subspace by the private singular vectors. In brief, the DPSVD trains a private SVM classifier for predicting the new instances in future.Algorithm 1: DPSVD.
Input: Raw data matrix D∈Rn×d, instances n, features d, privacy parameters ε, δ and β, accumulative contribution rate of principal components γ;Output: Classification model fx=∑i=1nαiyiKxi,x+b, private singular vectors Vk;BeginGenerate a noise matrixE∈Rn×d, every entry is i.i.d. and sampled from N(0, β2);Add the noise matrix to the raw data matrixD’ = D + E;Compute the singular valuesσ and singular matrices U, V of D′ by SVD, D′=USVT;Select the target dimensionk according to ∑i=1kσi2/∑i=1dσi2≥γ;Select firstk singular vectors Vk to project the original training instances to the low-dimensional singular subspace Y = DVk;Compute the classification modelf(x) in the singular subspace;Usef(x) and Vk to predict the new instances.End


## 4.2. Privacy Analysis

Firstly, the sensitivity of the functionq(D) is analyzed, and then the DPSVD is demonstrated to satisfy (ε, δ)-differential privacy. In the DPSVD algorithm, the noise matrix is added to the data matrix D; therefore q(D) = D. Given that two adjacent data matrices D and D′ differ by exactly one row corresponding to an instance, we set D′ obtained from D by deleting the last row, D=x1,...,xnT∈Rn×d and D′=x1,...,xn−1T∈Rn−1×d, and assume each row has unit ℓ2 norm ||xi||2≤1 at the most.Lemma 1.
The sensitivity of the functionq(D) S2 equals one.Proof.
According to Definition2, it obtains S2 by the following inequation:(13)S2=maxD,D′qD−qD′2=maxD,D′D−D′2=maxD,D′xn2≤1
Therefore, the sensitivity of the functionq(D) equals one.Theorem 1.
The DPSVD satisfies (ε, δ)-differential privacy.Proof.
To demonstrate that the DPSVD satisfies (ε, δ)-differential privacy, it is necessary to demonstrate every step in the algorithm satisfies it. According to Lemma 1, it obtains that S2 equals one. Let β=S22ln1.25/δ/ε=2ln1.25/δ/ε; then Step (1) and Step (2) satisfy DP according to Definition 4. Step (3) and Step (4) postprocess the private data matrix D′; they also satisfy DP. Step (5) generates the private singular vectors Vk; the projected instances Y in the low-dimensional singular subspace are private as well. Meanwhile, Y does not need to be distributed to users. Step (6) and Step (7) compute the classification model based on private projection instances and distribute it together with private singular vector to predict the new instances. The last three steps do not violate the privacy requirement of DP. Therefore, the DPSVD satisfies (ε, δ)-differential privacy.


## 4.3. Algorithm Comparison

The three algorithms were compared theoretically between DPSVD, AG [9], and DPPCA-SVM [26] summarized in Table 2. Other ones have been compared by the DPPCA-SVM algorithm. Our algorithm uses SVD to perform PCA; it does not need to compute matrix of covariance and symmetrize the noise matrix as the description above. It obtains the same noise scale as AG algorithm, because they use identical mechanism of DP to generate the noise matrix.Table 2
The comparison between the three algorithms.
AlgorithmPCAAdding modeNoise formNoise scaleMechanismPrivacy levelDPSVDSVDDAsymmetricOd/nεGaussian(ε, δ)AGEVDDTD/nSymmetricOd/nεGaussian(ε, δ)DPPCA-SVMEVDDTD/nSymmetricOd/nεLaplace(ε, 0)Therefore, the classification model and the singular vectors for projection are both private; they can be used to predict the new instances in the same singular subspace. The main advantage of the DPSVD compared with other private SVMs is that our algorithm trains the classification model in the private low-dimensional singular subspace generated by SVD. In this way, the features of the instances in the singular subspace become linearly independent and low-dimensional and therefore have higher time and space efficiency for training the classification model. The difference between our algorithm with other private PCA algorithms is that it does not need to calculate the matrix of covariance or symmetrize the noise matrix. Meanwhile, the DPSVD protects privacy of the training instances before training the classification model; many optimization methods of SVMs can be applied directly to the training progress.


## 5. Results

### 5.1. Datasets

Our experiments were carried out on four popular datasets for testing SVM performance. Table3 describes their basic information, including the number of the instances, the number of the features, and the ranges of values in the data. They are accessible at https://www.csie.ntu.edu.tw/∼cjlin/libsvmtools/datasets/ and http://archive.ics.uci.edu/ml/datasets.php. It trains the SVM to compare the performance of algorithms based on LIBSVM (version 3.25) [36] with the radial basis function as the kernel function and default parameters.Table 3
Test datasets.
IndicesDatasetsInstancesFeaturesRanges1A1a1605119[0, 1]2Mushrooms8124112[-1, 1]3Musk6598166[-1, 1]4Splice100060[-1, 1]


### 5.2. Algorithm Performance Experiments

The performance of the DPSVD was compared with AG, DPPCA-SVM, and the nonprivate SVM on the four real datasets. In the experiments, it designed two metrics of algorithm performanceAccuracy and SV. Accuracy denotes how accurate the classification is, and SV denotes how many SVs are contained in the classifier. The higher the Accuracy, the greater the usability of the classifier. The closer SV to that of nonprivate SVM, the better the stability of the algorithm. The privacy budget ɛ was set at 0.1, 0.5, and 1, δ at 1/n2, and the accumulative contribution rate of principal components γ at 90%. Three private algorithms were implemented five times under every privacy budget parameter. The mean values, standard deviation, and maximum and minimum values of the two metrics are given in Table 4.Table 4
Performance comparison of algorithms on different datasets.
DatasetsɛAlgorithmAccuracySVMeanStdMaxMinMeanStdMaxMinA1a--SVM83.49------754------0.1DPSVD83.350.1583.6183.247636771756AG83.080.2483.3082.687434747738DPPCA-SVM82.580.5883.3081.93771127837540.5DPSVD83.500.2283.8683.307559768743AG83.090.1683.1882.806863689682DPPCA-SVM83.070.5083.4982.24764147787471DPSVD83.590.1383.7483.437535759748AG83.450.2483.8083.186974702693DPPCA-SVM83.460.4184.1182.9975614778742Mushrooms--SVM99.90------617------0.1DPSVD99.890.0199.9099.8863939700607AG99.180.0299.2199.155183521514DPPCA-SVM99.490.4299.8999.02683677476040.5DPSVD99.900.0199.9099.8963325674607AG99.190.0599.2699.145245531517DPPCA-SVM99.590.3899.9099.06763508116871DPSVD99.900.0099.9099.9060226625559AG99.790.0499.8399.7344522469417DPPCA-SVM99.830.0899.9899.7865181779559Musk--SVM93.95------1351------0.1DPSVD94.080.1194.2393.9513511513691330AG88.960.0889.0988.8918651018761855DPPCA-SVM93.970.2094.2393.7413798139113690.5DPSVD94.140.1194.2794.0013591413791341AG88.940.0188.9588.921866618741858DPPCA-SVM94.100.1594.3593.97133615135513151DPSVD94.140.1094.2994.0413451013581333AG88.930.0288.9588.9118721018871860DPPCA-SVM94.190.1794.3593.9213184013841275Splice--SVM94.30------607------0.1DPSVD91.080.7592.4090.6063517662616AG90.560.8391.3089.3059116605568DPPCA-SVM87.140.3287.4086.70643166606190.5DPSVD92.000.8092.8090.7061010625600AG93.580.3894.0093.005885595582DPPCA-SVM87.220.7388.4086.60659347066151DPSVD92.360.5693.1091.8061819645594AG93.560.3193.9093.105943599591DPPCA-SVM87.360.9488.3086.0064121667614From the experiments results in Table4, the DPSVD was the most accurate in classification than the other two private classifiers under different privacy budget for most of the datasets. Sometimes, our algorithm even outperformed the nonprivate SVM. This is mainly because our algorithm removes the linear dependence between features and unimportant features by SVD. Meanwhile, our algorithm has the better stability of the algorithm as its SV is much closer to the nonprivate SVM. To compare algorithm performance more intuitively, the mean values of the two metrics for the four algorithms are shown in Figures 1–8.Figure 1
Accuracy at various ɛ on dataset A1a.Figure 2
Accuracy at various ɛ on dataset Mushrooms.Figure 3
Accuracy at various ɛ on dataset Musk.Figure 4
Accuracy at various ɛ on dataset Splice.Figure 5
SV at various ɛ on dataset A1a.Figure 6
SV at various ɛ on dataset Mushrooms.Figure 7
SV at various ɛ on dataset Musk.Figure 8
SV at various ɛ on dataset Splice.In Figure1 to Figure 3, the DPSVD achieved the highest classification accuracy in the three private algorithms and closer to the nonprivate SVM than the other two algorithms. In Figure 4, the AG achieved the higher classification accuracy than the DPSVD as the privacy budget increases. In Figure 5 to Figure 8, the DPSVD contained the closer number of SVs in the classifier to the nonprivate SVM than the other two algorithms. Therefore, the PDSVD achieved higher classification accuracy and better algorithm stability on most of the datasets and approximated the performance of the nonprivate SVM. The AG algorithm on dataset Musk in Figure 3 and the DPPCA-SVM algorithm on dataset Splice in Figure 4 have relatively lower classification accuracy. It also shows that the DPSVD has better algorithm stability.


## 5.1. Datasets

Our experiments were carried out on four popular datasets for testing SVM performance. Table3 describes their basic information, including the number of the instances, the number of the features, and the ranges of values in the data. They are accessible at https://www.csie.ntu.edu.tw/∼cjlin/libsvmtools/datasets/ and http://archive.ics.uci.edu/ml/datasets.php. It trains the SVM to compare the performance of algorithms based on LIBSVM (version 3.25) [36] with the radial basis function as the kernel function and default parameters.Table 3
Test datasets.
IndicesDatasetsInstancesFeaturesRanges1A1a1605119[0, 1]2Mushrooms8124112[-1, 1]3Musk6598166[-1, 1]4Splice100060[-1, 1]


## 5.2. Algorithm Performance Experiments

The performance of the DPSVD was compared with AG, DPPCA-SVM, and the nonprivate SVM on the four real datasets. In the experiments, it designed two metrics of algorithm performanceAccuracy and SV. Accuracy denotes how accurate the classification is, and SV denotes how many SVs are contained in the classifier. The higher the Accuracy, the greater the usability of the classifier. The closer SV to that of nonprivate SVM, the better the stability of the algorithm. The privacy budget ɛ was set at 0.1, 0.5, and 1, δ at 1/n2, and the accumulative contribution rate of principal components γ at 90%. Three private algorithms were implemented five times under every privacy budget parameter. The mean values, standard deviation, and maximum and minimum values of the two metrics are given in Table 4.Table 4
Performance comparison of algorithms on different datasets.
DatasetsɛAlgorithmAccuracySVMeanStdMaxMinMeanStdMaxMinA1a--SVM83.49------754------0.1DPSVD83.350.1583.6183.247636771756AG83.080.2483.3082.687434747738DPPCA-SVM82.580.5883.3081.93771127837540.5DPSVD83.500.2283.8683.307559768743AG83.090.1683.1882.806863689682DPPCA-SVM83.070.5083.4982.24764147787471DPSVD83.590.1383.7483.437535759748AG83.450.2483.8083.186974702693DPPCA-SVM83.460.4184.1182.9975614778742Mushrooms--SVM99.90------617------0.1DPSVD99.890.0199.9099.8863939700607AG99.180.0299.2199.155183521514DPPCA-SVM99.490.4299.8999.02683677476040.5DPSVD99.900.0199.9099.8963325674607AG99.190.0599.2699.145245531517DPPCA-SVM99.590.3899.9099.06763508116871DPSVD99.900.0099.9099.9060226625559AG99.790.0499.8399.7344522469417DPPCA-SVM99.830.0899.9899.7865181779559Musk--SVM93.95------1351------0.1DPSVD94.080.1194.2393.9513511513691330AG88.960.0889.0988.8918651018761855DPPCA-SVM93.970.2094.2393.7413798139113690.5DPSVD94.140.1194.2794.0013591413791341AG88.940.0188.9588.921866618741858DPPCA-SVM94.100.1594.3593.97133615135513151DPSVD94.140.1094.2994.0413451013581333AG88.930.0288.9588.9118721018871860DPPCA-SVM94.190.1794.3593.9213184013841275Splice--SVM94.30------607------0.1DPSVD91.080.7592.4090.6063517662616AG90.560.8391.3089.3059116605568DPPCA-SVM87.140.3287.4086.70643166606190.5DPSVD92.000.8092.8090.7061010625600AG93.580.3894.0093.005885595582DPPCA-SVM87.220.7388.4086.60659347066151DPSVD92.360.5693.1091.8061819645594AG93.560.3193.9093.105943599591DPPCA-SVM87.360.9488.3086.0064121667614From the experiments results in Table4, the DPSVD was the most accurate in classification than the other two private classifiers under different privacy budget for most of the datasets. Sometimes, our algorithm even outperformed the nonprivate SVM. This is mainly because our algorithm removes the linear dependence between features and unimportant features by SVD. Meanwhile, our algorithm has the better stability of the algorithm as its SV is much closer to the nonprivate SVM. To compare algorithm performance more intuitively, the mean values of the two metrics for the four algorithms are shown in Figures 1–8.Figure 1
Accuracy at various ɛ on dataset A1a.Figure 2
Accuracy at various ɛ on dataset Mushrooms.Figure 3
Accuracy at various ɛ on dataset Musk.Figure 4
Accuracy at various ɛ on dataset Splice.Figure 5
SV at various ɛ on dataset A1a.Figure 6
SV at various ɛ on dataset Mushrooms.Figure 7
SV at various ɛ on dataset Musk.Figure 8
SV at various ɛ on dataset Splice.In Figure1 to Figure 3, the DPSVD achieved the highest classification accuracy in the three private algorithms and closer to the nonprivate SVM than the other two algorithms. In Figure 4, the AG achieved the higher classification accuracy than the DPSVD as the privacy budget increases. In Figure 5 to Figure 8, the DPSVD contained the closer number of SVs in the classifier to the nonprivate SVM than the other two algorithms. Therefore, the PDSVD achieved higher classification accuracy and better algorithm stability on most of the datasets and approximated the performance of the nonprivate SVM. The AG algorithm on dataset Musk in Figure 3 and the DPPCA-SVM algorithm on dataset Splice in Figure 4 have relatively lower classification accuracy. It also shows that the DPSVD has better algorithm stability.


## 6. Conclusions

To solve the privacy leak of SVM classifiers, especially on high-dimensional data, the DPSVD algorithm was proposed to project the training instances into the low-dimensional singular subspace and train a private SVM classifier on it while not violating the privacy requirements for the training data. The DPSVD is proved to satisfy DP. The main advantages of the DPSVD include three aspects. Firstly, it trains the classification model in the private low-dimensional singular subspace; therefore it has higher time and space efficiency compared with other private SVMs. Secondly, it does not need to calculate the matrix of covariance or symmetrize the noise matrix and has higher classification accuracy and better stability of the algorithm than other existing private PCA algorithms through the comparison experiments. Thirdly, it protects privacy of the training instances before training the classification model, and many optimization methods of SVMs can be applied directly to the training progress. Meanwhile, its algorithmic ideas can be applied to other machine learning areas to solve data privacy problems. However, the DPSVD can only solve the linear dependence between the data features. In future work, we will consider the nonlinear dependence to train a private classification model. In addition, the problem of data instances compression through SVD is another research direction.



---

*Source: 2935975-2022-03-26.xml*