Ratio Utility and Cost Analysis for Privacy Preserving Subspace Projection
Mert Al Shibiao Wan Sun-Yuan Kung


Magnon-photon coupling in antiferromagnets
    X. R. Wang
    December 30, 2023
==========================================



With a rapidly increasing number of devices connected to the internet, big data has been applied to various domains of human life. Nevertheless, it has also opened new venues for breaching users' privacy. Hence it is highly required to develop techniques that enable data owners to privatize their data while keeping it useful for intended applications. Existing methods, however, do not offer enough flexibility for controlling the utility-privacy trade-off and may incur unfavorable results when privacy requirements are high. To tackle these drawbacks, we propose a compressive-privacy based method, namely RUCA (Ratio Utility and Cost Analysis), which can not only maximize performance for a privacy-insensitive classification task but also minimize the ability of any classifier to infer private information from the data. Experimental results on Census and Human Activity Recognition data sets demonstrate that RUCA significantly outperforms existing privacy preserving data projection techniques for a wide range of privacy pricings.




Compressive privacy, Subspace methods, Projection matrix, Principal/Discriminant component analysis



0pt



§ INTRODUCTION


With our daily activities moving online, vast amounts of personal information are being collected, stored and shared across the internet, often without the data owner's knowledge. Even when the data owners trust data keepers such as Internet Service Providers and Statistics Bureaus to keep their personal information private, the data are often needed to be analyzed and released for Statistics, Commercial and Research purposes. This raises obvious concerns about the privacy of data contributors, as not only are the data vulnerable to inadvertent leakages, but also to malicious inference by other parties. Thus privacy-protection methods should be employed that allow data collectors and owners to control the types of information that can be inferred from their data.

Consider a scenario where mobile users upload their sensor readings to the cloud, which in turn trains a classifier that allows smartphones to identify their users from sensor readings in the background as in <cit.>. This approach takes advantage of the vast storage and computation resources of the cloud. However, without proper processing the same data can be used to infer sensitive information about users, such as location, context and activities performed <cit.>. This is especially alarming given the fact that private information about users may not only be inferred by the cloud but possibly by other users as well through classifiers, which may include training samples in them <cit.>.

A number of approaches based on data projection and/or noise addition have been proposed to preserve the statistics of the data for machine learning applications, while making privacy-sensitive information unavailable. Additive noise based randomization was proposed in <cit.>, but was shown to be susceptible to reconstruction attacks using spectral properties of random noise and data <cit.>. Liu et al. <cit.> proposed projection of the data to a lower dimensional space via a Random Projection Matrix. Later, a more suitable system was proposed in <cit.> for collaborative-learning, where the cloud trains a classifier with data from multiple users. Each user randomly generates a hidden Projection Matrix and adds variable levels of noise to projected samples before sending them to the cloud.

In <cit.>, Kung presented a supervised version of Principle Component Analysis (PCA) called Discriminant Component Analysis (DCA) in order to project the data into a lower dimensional space that maximizes the discriminant power as in Fisher Discriminant Analysis <cit.>. The recent work of Diamantaras and Kung <cit.> inspired by this approach introduced another criterion called Multiclass Discriminant Ratio (MDR), and projects the data based on a pair of desirable and undesirable classification tasks.  
 
Dimension reduction through data projection removes both application-relevant and privacy-sensitive information from the data. DCA and MDR attempt to remove as little application-relevant information as possible by optimizing the projection subspace for the intended classification task. Yet they do not offer any flexibility for finding a favorable trade-off between utility and privacy. 

To address these problems, we propose a methodology called RUCA (Ratio Utility and Cost Analysis), which forms a bridge between DCA (utility driven projection) and MDR (privacy emphasized projection) and allows data owners to select a compromise between them. RUCA can be considered as a generalization of DCA and MDR, and it can also be extended to multiple privacy-sensitive classifications. Experimental results on Census and Human Activity Recognition data sets show that our methodology can provide better classification accuracies for the desired task while outperforming state-of-the-art privacy preserving data projection methods in terms of accuracies obtained from privacy-sensitive classifications.

Our methodology for privacy preservation is described in Section <ref>, and it is formulated as the problem of maximizing separability of projected data for a desired classification task, while minimizing separability for undesirable classifications. We then present Generalized Eigenvalue Decomposition as a method for finding the optimal Projection Matrix that achieves this task. Our methods are tested on real data with possible utility and privacy classifications in Section <ref> and are compared with other projection based privacy protection methods. Finally, we conclude in Section <ref>.



§ METHODOLOGY





 §.§ Problem Statement

For simplicity, we shall assume that there is a single privacy-sensitive classification on the data, though it is straightforward to generalize this to the case where there are multiple privacy-sensitive classifications. We assume that the data of our concern is fully represented by a set of N M-dimensional vectors {_1,_2,⋯,_N}. For the desired classification, which we name utility classification, we have a set of labels y_i associated with the vectors _i. For an undesirable classification, which we name privacy classification, we have a set of labels s_i associated with the vectors _i. There are two or more classes for each classification task, i.e. y_i ∈ 1,⋯,L, s_i ∈ 1,⋯,P, where L and P are the numbers of utility and privacy classes, respectively.

Let  be an M × K projection matrix where K<M and _i=^T_i denote the projection of a vector _i to a K-dimensional subspace. Let  denote the M × N matrix whose columns correspond to the data entries _i and  denote the K × N matrix whose columns correspond to the projected entries _i. Given , our problem is to find a matrix  such that given the projected data matrix =^T: 

 
  * A classifier can achieve similar performance on the task of finding the labels {y_1,y_2,⋯,y_N}, compared to the case where the full data matrix  is given.
 
  * Conversely, any classifier achieves poor performance, ideally as poor as random guessing, on the task of finding the set of labels {s_1,s_2,⋯,s_N}.




 §.§ Projection Method




To achieve the task outlined above, we need to select a subspace such that separability between classes based on the utility labels y_i is maximized, while separability between classes based on privacy labels s_i is minimized. For utility driven dimension reduction, given the subspace dimension K, DCA <cit.> involves searching for the projection matrix _DCA∈^M × K:

    _DCA = :^T[+ρ]=arg max(^T )

where (·) is the trace operator and ρ is a small regularization term added for numerical stability.  is the center adjusted scatter matrix:

    = ^T=∑_i=1^N[_i-][_i-]^T

where  denotes the mean of the samples {_i}_i = 1^N.  is divided into two additive parts:

    = +

where  and  are utility between-class and within-class scatter matrices, respectively. These are defined as

    = ∑_c=1^L N^u_c[-^u_c][-^u_c]^T 
       = ∑_c=1^L ∑_y_i=c [_i-^u_c][_i-^u_c]^T

where ^u_c is the mean and  N^u_c is the number of samples in utility class c, respectively. Privacy between-class scatter matrix  can be defined similarly:

    = ∑_c=1^P N^p_c[-^p_c][-^p_c]^T

where ^p_c is the mean and  N^p_c is the number of samples in privacy class c, respectively. 

Optimal solution to the problem given in Equation <ref> remains the same when  is replaced with  due to the relationship given in Equation <ref>. Even though Equation <ref> applies more restrictive orthonormality constraints to the columns of the projection matrix , the subspace spanned by these columns constitutes an optimal solution for Multiclass Discriminant Analysis (MDA) criterion <cit.> (with an additional regularization term ρ):

    MDA=(^T )/(^T (+ρ) )

where (·) is the determinant operator.

In addition, an optimal solution to both of these problems can be derived from the first K principal generalized eigenvectors of  the matrix pencil (,+ρ) <cit.>.

Multiclass Discriminant Ratio (MDR) is a natural extension to MDA criterion for the case where there are two conflicting goals: To maximize separability for a utility classification problem and to minimize separability for a privacy classification problem <cit.>. It is defined as:

    MDR = (^T )/(^T (+ρ) )


Analogous to DCA and MDA, an optimal solution to MDR can be derived from the first K principal generalized eigenvectors of the matrix pencil (,+ ρ). Thus DCA and MDR, barring an orthonormality constraint on the columns of the projection matrix, are very similar and can both be solved via Generalized Eigenvalue Decomposition. 

We shall add additional parameters to DCA to obtain a compromise between DCA and MDR, which we will call Ratio Utility and Cost Analysis (RUCA):

    _RUCA = :^T[𝐒_RUCA+ρ]=arg max(^T )
 
where 𝐒_RUCA is a privacy-regularized scatter matrix:

    𝐒_RUCA=+ρ_p

where ρ_p is a privacy parameter different from ρ. 

Note that when ρ_p is 0, this projection method becomes DCA and when ρ_p is very large, it becomes MDR as the term ρ_p dominates. By varying ρ_p, it is possible to establish a more favorable trade-off between utility and privacy than MDR. Additionally, RUCA can be generalized to multiple privacy classifications by including multiple between-class scatter matrices in the regularization:

    𝐒_RUCA=+∑_i^ρ_p_i _i


Finally, an optimal solution to RUCA can be derived from the first K principal generalized eigenvectors of the matrix pencil (,𝐒_RUCA+ρ). In other words, columns of the projection matrix  correspond to K largest eigenvalues λ_i satisfying the following relationship:

    _i = λ_i (𝐒_RUCA+ρ)_i


In all the subspace optimization techniques described above, the left hand side of the characteristic equation remains the same as in Equation <ref>. Due to the fact that rank of  is at most L-1, there are at most L-1 non-zero eigenvalues associated with the generalized eigenvalue decompositions. In practice, another small regularization term ρ' may be added to  to make it full rank, which will allow users to rank the columns of  in cases where K ≥ L. As columns corresponding to eigenvalues ranking L or lower don't normally contribute to our criteria, they are expected to have little contribution to the effectiveness of utility classification.



§ EXPERIMENTAL RESULTS




 §.§ Data Sets




We have tested our approach with multiple applications on Census (Adult) and Human Activity Recognition (HAR) <cit.> data sets, both of which are available at UCI Machine Learning Repository <cit.>. For the Census data set we used Income as the utility classification where we try to classify an individual as with high- or low-income, parallel with the original purpose of the data set. Privacy classifications were chosen as Marital Status and Gender, both of which were given as categorical features in the original data. We grouped `Married-civ-spouse', `Married-spouse-absent' and `Married-AF-spouse' into a single category called `Married'. `Divorced', `Separated' and `Widowed' were grouped into a single category called `Used to be Married'. We left the `Never Married' category as is. 

We first removed the samples with missing features in the data set and randomly sampled the rest of the training and testing sets (separately) in order to create two sets in which all privacy classes have equal number of samples, i.e. numbers of males and females were equal in our training and testing sets, and so were the number of samples categorized as 'Married', 'Never Married' and 'Used to be Married'. All categorical features were turned to numerical ones via binary encoding, as we determined it to yield higher classification accuracies than one-hot encoding with this data. After these operations we had 10086 samples remaining in the training set and 4962 samples remaining in the testing set with 29 features.

In HAR data set, we had Activity and Identity as labels available to us, either of which can be utility or privacy based on the application. Therefore we tested for both cases. Activity had 6 types of labels: `Walking', `Walking Upstairs', `Walking Downstairs', `Sitting', `Standing' and `Laying'. Identity, on the other hand, had 21 types of labels based on the individuals who contributed to the data. 

Training and testing sets of the HAR data set consist of samples contributed by two disjoint sets of users. Therefore we extracted testing sets for Identity classification by randomly picking samples from the original training set. When Activity classification was chosen as utility, we tested Activity classification accuracy on the original testing set and Identity classification accuracy on the extracted testing set. The numbers of training, privacy testing and utility testing samples were 4011, 1890 and 2947, respectively, with 561 features. 

When Identity classification was chosen as utility, we tested both Identity and Activity classification accuracies on the same testing set, which was extracted from the original training set.  The numbers of training and testing samples were 4026 and 1890 respectively with 561 features. As with the Census data, we kept the number of samples in all privacy classes equal in all sets.



 §.§ Results




All our experiments were performed using RBF SVM on the original and projected data. Training and testing sets were separated as described in the last section before the experiments commenced. With the Census data set we performed 50 iterations at which we randomly picked 10% of the training samples. At each iteration and with each projection method, a 5-fold cross-validation grid search was performed to find the best parameters for training utility and privacy classifiers. 

With the HAR data set we performed 50 iterations at which we randomly picked 25% of the training samples. Once again, optimal parameters for SVM-RBF were determined via 5-fold cross-validation at each iteration. PCA and Random Projection were also included in our experiments for comprehensiveness. 

In order to compare RUCA's performance with other projection methods, we adopt a simple performance criterion:

    Performance = Acc_U+β(1-Acc_P)

where Acc_U and Acc_P denote the utility and privacy classification accuracies, respectively, and β denotes the Privacy Pricing. Higher β indicates that higher emphasis is placed on privacy, while β=0 indicates that all the emphasis is placed on utility.

Figure <ref> displays the utility-privacy trade-off curves obtained by progressively adding more components with each projection method. We stopped adding components as they started contributing predominantly to privacy classification. To obtain the results provided in Tables <ref>, <ref> and <ref>, we picked K=1, K=5 and K=20, respectively, because we had L=2, L=6 and L=21 for Income, Activity and Identity classification problems, respectively.

The curves in Figure <ref>(a) demonstrate a trade-off between utility and privacy as the privacy parameter ρ_p is increased. Even RUCA with a low privacy parameter achieves higher privacy levels than possible with DCA. RUCA with ρ_p=1 outperforms PCA and DCA when β≥ 0.067, whereas RUCA with ρ_p=4 outperforms MDR and all remaining methods for all privacy pricings. Based on the trade-off curves in Figures <ref>(b) and <ref>(c), RUCA outperforms both DCA and MDR on HAR data for all privacy pricings. Furthermore, RUCA outperforms all other methods in (b) for all privacy pricings and all other methods in (c) when ρ_p ≥ 0.226. PCA and Random Projection, on the other hand, are seen to under-perform in all plots when the privacy pricing is high. 

By comparing the curves in (b) and (c), it becomes apparent that Identity classification when Activity is private is much harder than Activity classification when Identity is private on HAR data. Steepness of the drops in (b) suggests that more utility performance can be obtained by sacrificing relatively little privacy, which is not the case in (c).

Results with K=1 for the Census data set are given in Table <ref>. Clearly, DCA alone reduces gender classification accuracy close to random guessing (50%) by sacrificing less than 1% (absolute) utility classification accuracy. Accordingly for this application, a nonzero privacy parameter ρ_p was only applied to the between-class scatter matrix of Marital Status classification and privacy parameter was kept at 0 for Gender classification. The table demonstrates a clear utility-privacy trade-off as ρ_p is increased, similar to Figure <ref>(a). RUCA outperforms DCA when β≥ 0.073 and all other methods for all privacy pricings. Results indicate that a small privacy parameter ρ_p provides significantly better privacy while sacrificing little utility classification performance, whereas with a large ρ_p it is possible to get better utility classification performance for the same privacy classification performance as other methods.

Tables <ref> and <ref> show similar results for HAR data set when Activity classification and Identity classification are chosen as utility, respectively. Utility performance doesn't immediately drop, though privacy classification accuracies decrease as ρ_p is increased. Here RUCA outperforms all other methods for all privacy pricings, except for Random Projection as seen in Table <ref>. Although Random Projection provides better privacy for HAR data set when Activity classification is chosen as utility, it only outperforms RUCA when β≥ 5.621, i.e. when much higher emphasis is placed on privacy.





§ CONCLUSION



We have presented a novel subspace projection method that allows data offered by users in a collaborative learning environment to be used for the intended purpose, with minimal loss of private information. We formulated a new criterion called Ratio Utility and Cost Analysis, which combines utility driven DCA  with privacy emphasized MDR. Our method allows users to define multiple undesirable classifications on their data and achieve better utility for a given level of privacy. Using publicly available Census (Adult) and Human Activity Recognition data sets, we have demonstrated that our approach can provide better classification performance for the intended task for an equally low privacy classification performance when compared with state-of-the-art methods. Future work will include the extension of RUCA to privacy preserving non-linear projections, as well as an optimization method for the privacy parameters.









IEEEbib


*

