Privacy-aware Synthesizing for Crowdsourced Data

1 Introduction

In recent years, crowdsourcing has emerged as a popular and fast paradigm to solve many challenging data analysis tasks. Through the power of the crowd, the data collectors (e.g., hospitals, foundations and government agencies) can easily obtain large amounts of useful information. At the same time, the proliferation of new information techniques enables these data collectors to easily share their data that are collected from a crowd of users (e.g., patients, customers) with researchers or data analyzers. From such a wealth of shared data, researchers or data analyzers can discover useful knowledge or patterns to improve the quality of products, the management of public health, and so on. For example, in healthcare applications, the adverse events about a new drug can be easily collected by the hospitals from different patients. If the hospitals are willing to share these medical data, it would be very useful for the drug makers or medical research institutions to understand the efficacy of the drug.

Although the sharing of crowdsourced data brings many benefits, it may introduce privacy issues [Miao et al., 2015;

Shi and Wu, 2017; Miao et al., 2017; Feng et al., 2017]. Considering the above example, the hospital aims to collect the adverse events about a new drug from different patients. The patients usually trust the hospital and are willing to provide all the requested information. But if the hospital directly releases the patients' medical data to the drug makers, the private information of patients would be disclosed. Without effective privacy-preserving mechanisms, the patients may not allow their data to be released. Thus, it is essential to address how to enable the data collectors to release the crowdsourced data without disclosing users' private information.

Among existing privacy-preserving techniques, differential privacy (DP) has drawn significant attention as it can provide very rigorous privacy and utility guarantee [Dwork et al., 2006]. However, this technique has several practical limitations when it is applied in the setting of releasing crowdsourced data. First of all, since the crowdsourced data on an object (e.g., the new drug) are usually collected from multiple users or sources, there inevitably exist conflicts among these data. The reasons include incomplete views of observations, environment noise, different knowledge bases and even the intent to deceive, etc. Directly applying DP on these data can not eliminate the conflicts, and this will certainly degrade the accuracy of the data analysis results. Additionally, DP is usually achieved by adding noise following the Laplace or exponential mechanisms [Dwork et al., 2006]. The noise scale introduced by the Laplace mechanism is proportional to the number of data records, and such noise may make the data useless considering that crowdsourced dataset usually contains large amounts of data records. Although the noise introduced by the exponential mechanism does not depend on the number of data records, it depends on the domains of the input data [Dwork et al., 2014], which may also make the crowdsourced data useless because these data usually have large domains.

To address the above challenges, in this paper, we propose a novel sampling-based privacy-aware synthesizing method for crowdsourced data (PrisCrowd). In this method, the data collector first learns the underlying patterns (i.e., densities) of the data for the objects through assigning each user a fine grained weight (or reliability degree) on each object. Then, for each object, the data collector samples a set of candidate synthetic data from the learned density. Finally, these synthetic data are subjected to our proposed privacy test, and the data collector only releases the synthetics that can pass the privacy test. The proposed method can not only extract high quality crowdsourced data via differentiating each user's fine grained reliability degrees on different objects but also achieve DP without injecting noise to the data. Both theoretical analysis and extensive experiments on real-world datasets are provided to verify the desirable performance of the proposed method.

2 Problem Setting

This paper considers a data releasing scenario, where a crowd of users and a data collector are involved. The users (or data sources) are the individuals (e.g., patients, customers) who can observe some objects (e.g., drugs, commodities) and provide claims for them. The data collector is an individual or institution (e.g., a hospital, an online store) who can collect the claims for these objects from a crowd of users and then release these claims to the public either voluntarily or for financial incentives. Here, we assume that the collector is trusted and the security threats mainly come from the public.

Problem formulation. Suppose there are N objects O = ^oi'Ni=1 which are observed by M users U = ^1; 2; :::;M'. For each object oi, the claims of users are denoted as Xi = ^xi;s's¸Ui , where xi;s represents the claim provided by user s for object oi and Ui represents the set of users who provide claims for this object. The claims collected by the data collector from all users are denoted as X = ^Xi'Ni=1 , which need to be released to the public. Our goal in this paper is to design a mechanism based on which the data collector can release users' claims with strong privacy protection for their private information, while at the same time, the data analyzer can achieve good utility from the released data.

3 Preliminary

Definition 1 (Differential Privacy [Dwork et al., 2006]). A randomized algorithm A is .�; �/-differentially private if for all neighboring datasets D;D¤ ¸ X n and for all events S in the output space of A, the following holds: Pr.A.D/ ¸ S/ f e� Pr.A.D¤ / ¸ S/ + �.

The kernel density estimation (KDE) is a statistically-sound method to estimate a continuous distribution. Suppose there are n independent observations X = ^x1; :::; xn' ¸ Rd following an unknown true density f < .x/. The standard KDE � f.x/ for the estimation of f < .x/ at those points is defined as � f.x/ = 1n ‡ni=1 KH.x; xi/. The following assumption will be used throughout the paper.

Assumption 1. For a vector xi ¸ Rd , we assume that the ker-

nel function satisfies KH.x; xi/ = KH.x * xi/. Furthermore, KH.x*xi/ is essentially a bump centered at xi. More specifically, we take KH.x/ = �H�* 1 2K.H* 12 z/, where the kernel K itself is a probability density with zero mean and identity

covariance and satisfying limæxæ�� æxæd K.x/ = 0.

Common choices for K that satisfy the above assumption include Gaussian and Epanechinikov kernels. As an example, Fig. 1 visualizes the construction of the standard KDE of 5 data points (black circles) using the well-known Gaussian kernel that is defined as KH.x * xi/ = . 1 ø2�h /d exp.* æx*xiæ2 2h2 /, where h is the bandwidth. The red curves are the component densities, and each red curve is a scaled version of the normal density curve centered at a datum. The standard KDE is obtained by summing these five scaled components.

4 Methodology

4.1 Overview

To achieve the goal described in Section 2, we propose a novel privacy-aware synthesizing method for crowdsourced data (i.e., PrisCrowd), which contains two phases. In the first phase, we propose to use the weighted KDE as an intermediate representation of the raw data. This intermediate representation can well capture the statistical properties of the raw data. In the second phase, we first sample a set of candidate synthetic claims from the learned densities in the first phase, then each of these candidate claims is subjected to the proposed privacy test. If the claim passes the privacy test, it will be released, otherwise it will be discarded. The flowchart of the proposed two-phase method is shown in Fig. 2.

4.2 Weighted KDE-based Data Representation

In order to share "wealth" data with the data analyzer, the data collector first needs to learn the characteristics or the underlying patterns of original data, i.e., the informative density distributions of objects. To estimate the density for each object, the standard kernel density estimation (KDE) can be adopted. Additionally, since different users may provide different claims for the same object, the reliability degrees (or weights) of these users should be taken into account when estimating the densities [Li et al., 2014b; Li et al., 2014a; Li et al., 2016; Miao et al., 2019]. However, the standard KDE cannot differentiate the importance of users (i.e., user reliability degrees). In order to learn users' reliability and compute the densities of objects simultaneously, we propose a novel method which can estimate users' global and local weights, and then combine them to learn objects' informative density distributions. A user's global weight reflects his capability to provide truthful information for all the objects, and the local weights represent that this user may have different confidence when providing claims for different objects. The advantage of the proposed method is that it can estimate reasonable reliability for each user, and in turn, learn the accurate informative density distributions for objects.

Global Weight Estimation

To evaluate the overall importance of users, the data collector assigns a global weight gs ¸ R to each user s. Meanwhile, we can obtain a global density f g i for each object oi, which should be close to the distribution of claims from reliable users. The distribution of the input claims Xi can be obtained by KHi .x; Xi/ (x ¸ R is a variable), i.e., the kernel function associated with a reproducing kernel Hilbert space Hi. To minimize the weighted deviation from the estimated density Q = ^f g i .x/'Ni=1 to the multi-user input X = ^Xi'Ni=1 , we propose the following optimization framework

where Es denotes the set of objects observed by user s, G = ^gs's¸U and the normalized squared loss dHi .KHi .�; �/; f g i .x// is defined as dHi .KHi .x; xi;s/; f g i .x// = æKHi .x; xi;s/ * f g i .x/æ2Hi . The global loss function (i.e., Eq. (1)) extends the framework in [Li et al., 2014b] from real space to Hilbert space. We can use an iterative procedure to solve it. Specifically, in the k-th iteration, gs is updated as

where f g.k/ i .x/ = ‡t¸Ui g.k/ t KHi .x; xi;t/_.‡t¸Ui g.k/ t /. Eq. (2) shows that a user's global weight is inversely proportional to the distance between its claims and the estimated global densities at the log scale. Users whose claims are close to the derived global densities will have higher global weights.

Local Weight Estimation

As described above, each user may have different confidence when providing claims for different objects. Thus, we need to model the local weight of each user on every object, which will in turn help to infer the accurate density estimations. A potential way to achieve this is to establish a square loss function. However, it leads to a problem that each user would receive the same local weight, and the trustworthiness of the claims provided by different users would be equal. In order to address this problem, we use Hampel loss function [Hampel et al., 2011]:

where q1 < q2 < q3 are predefined nonnegative parameters. These parameters allow us to decrease the trustworthiness of

"bad" claims and increase that of "good" ones for each object, so the importance of users can be well distinguished.

Since we incorporate users' reliability into estimating the local densities, the local kernel density of object oi can be defined as f l i .x/ = ‡s¸Ui li;sKHi .x; xi;s/, where li;s is the local weight of the user s on object oi. Thus, the objective function for estimating li = ^li;s's¸Ui is

where æ�æ denotes the difference between users' claims and the estimated local density f l i .x/. This objective function is not convex, i.e., Eq. (3) does not have a closed form solution. Fortunately, it is possible to approximate li = ^li;s's¸Ui with a standard iteratively re-weighted least squares (IRWLS) algorithm. The iterative procedure for computing ^li;s's¸Ui is

where k denotes the number of iterations. This equation shows that users would receive lower weights when they provide "bad" claims which deviate largely from the center f l i .x/ = ‡t¸Ui li;tKHi .x; xi;t/.

Combined Weight Estimation

For each user s, to measure the consistency degree of the global and local weights (i.e., gs and li;s), we define a mixture weight, named combined weight ci;s. To learn the combined weight, the relative entropy is employed, which minimizes the information loss between user's global weight and local weight. The smaller the relative entropy value of those weights, the higher the degree of their consistency. The objective of the combined model is

By solving Eq. (4), we can obtain the combined weight ci;s of user s on the object oi as ci;s = øli;sgs_.‡t¸Ui øli;tgt/. Based on the learned combined weights, we can obtain the density of object oi which is the weighted sum of claims in Hilbert space and is given as

4.3 Privacy Test-based Synthetics Release

To provide strong privacy protection for users' private information, in this section, we propose a privacy test-based synthetics release method, which contains two steps: Candidate synthetics generation and Privacy test for candidate synthetics. In the first step, we sample a set of synthetic claims from the learned density in Eq. (5) as the candidate data to release. Then, in the second step, these sampled synthetics are subjected to a privacy test. If a synthetic claim passes the test, it will be released, otherwise it will be discarded.

Candidate Synthetics Generation

We first discuss how to generate the synthetic claims �Xi for each object oi. Specifically, we generate each element in �Xi as follows:

1. Select a random integer s ¸ Ui with probability ci;s;
2. Generate a synthetic claim �xi;s through sampling from the probability distribution KHi .x; xi;s/.

Here ci;s can be treated as the sampling probability that determineswhether xi;s is selected or not. In this step, we aimto select some seed data (e.g., xi;s) and then probabilistically transform them into the synthetic data. The sampling mechanism used here can increase the uncertainty of the adversary about whether a user's data is in the released dataset or not, and thus it can help to protect users' privacy to some extent. However, it is not enough to only use the sampling mechanism, directly releasing the sampled data can still violate users' privacy [Gehrke et al., 2012]. To tackle this problem, we design the following privacy test mechanism to further prevent users' private information from being disclosed.

Privacy Test for Candidate Synthetics

To prevent an adversary from deducing that a particular claim in Xi is more responsible for generating the released synthetic data than other claims, the following randomized privacy test mechanism is proposed. Each candidate synthetic data in �Xi is subjected to the randomized privacy test, and it is released only when it passes this test.

Suppose k g 1 and � > 1 are the privacy parameters, and �0 is the randomness parameter. Let M.�/ denote the above synthetic data generation procedure, which samples a candidate synthetic based on a seed data. Given xi;s ¸ Xi, we use Pr^ �xi;s = M.xi;s/' to denote the probability that a synthetic data �xi;s is generated based on M.�/. Then the privacy test procedure for �xi;s is described as follows:

1. Randomize k by adding a noise: �k = k + z, where z � Lap.1_�0/ is sampled from the Laplace Distribution.
2. Let a g 0 be the integer that satisfies the inequalities � *a*1 < Pr^ �xi;s = M.xi;s/' f � *a .
3. Let k¤ be the number of records xi;s¤ ¸ Xi that satisfies � *a*1 < Pr^ �xi;s = M.xi;s¤ ' f � *a .
4. If k¤ g �k, �xi;s passes the test, otherwise it fails.

Note that k¤ denotes the number of possible data seeds that can generate �xi;s with a probability value falling into a very stringent interval [� *a*1 ; � *a ]. The threshold parameter �k prevents releasing sensitive synthetic data. Under this randomized privacy test, a candidate synthetic data is released only when there are at least �k possible data seeds that can generate �xi;s. Intuitively, the larger the value of k, the larger the number of the possible seed data that are indistinguishable from xi;s. Also, the less the value of �, the more difficult to distinguish xi;s from other possible seed data. Algorithm 1 summarizes the proposed privacy test-based synthetics release procedure, in which m denotes the number of synthetic claims that need to be released for object oi.

Algorithm 1 Private test-based synthetics release for oi

Input: ^ci;s's¸Ui , Xi = ^xi;s's¸Ui , k, �, �0, and m.

Output: The dataset �Xi that can be released.

• 1: �Xi = �
• 2: while � �Xi� < m do
• 3: Select a random integer s ¸ Ui with probability ci;s;
• 4: Generate a synthetic claim �xi;s based on the probability distribution KHi .x; xi;s/;
• 5: Conduct randomized privacy test for �xi;s;
• 6: if �xi;s passes the privacy test then
• 7: �Xi = �Xi ·^ �xi;s';
• 8: end if
• 9: end while
• 10: return �Xi;

4.4 Theoretical Analysis

Consistency Analysis

In Section 4.3, we generate the synthetic claims for object oi by sampling from the mixture distribution fi.x/, i.e., �xi;s � fi.x/. After obtaining the dataset �Xi = ^�xi;s'ms=1 , a basic question here is that how well the generated dataset can reflect the original density function fi.x/. Since each �xi;s is sampled from fi.x/ independently, the density function over ^ �xi;s'ms=1 can be denoted as � fi.x/ = 1m ‡ms=1 KHi .x; �xi;s/. In Theorem 1, we provide the expected squared L2-norm distance between fi.x/ and � fi.x/.

Theorem 1. Under Assumption 1 for KHi with the diagonal bandwidth matrix Hi = �h2 Id, we further assume that the support of K.z/ satisfies æzæ f 1. Then, the expected squared L2-norm distance between fi.x/ and � fi.x/, i.e., J = E[� .fi.x/ * � fi.x//2dx], satisfies

where A = supx¸Rd æ(fi.x/æ, B = � .K.z//2dz and V is the volume of the support of fi.x/. The expectation is respected to ^�xi;s'ms=1 � fi.x/. This theorem is a general result for d dimensional case, in this paper, the value of d is 1.

Privacy Analysis

Next, we conduct privacy analysis for Algorithm 1. Based on Theorem 2, we know that the proposed algorithm is differentially private.

Theorem 2. Note that the input parameters of Algorithm 1 include ^ci;s's¸Ui , k g 1, � > 0, and �0. For any neighboring datasets Xi and X ¤ i such that �Xi�; �X ¤ i� g k and any integer 1 f t < k, we have that Algorithm 1 is .�; �/- differentially private, where � = �0+log.1+ �t maxs¸Ui ci;s mins¸Ui ci;s /; � =

Remark 1. Note that the proposed Algorithm 1 is different from the mechanism in [Bindschaedler et al., 2017]. The probability of choosing the seed xi;s is non-uniform in Algorithm 1 while that is uniform in [Bindschaedler et al., 2017].

The non-uniform property may generate different parameters of differential privacy. When maxs¸Ui ci;s = mins¸Ui ci;s = 1_�Ui� (i.e., we uniformly sample the seed xi;s), the above Theorem 2 is actually Theorem 1 in [Bindschaedler et al., 2017]. Thus, Theorem 2 in our paper is a generalization of Theorem 1 in [Bindschaedler et al., 2017]. Although the main idea of the proof for Theorem 2 is similar to that in [Bindschaedler et al., 2017], the details are quite different: in [Bindschaedler et al., 2017] the proof consider X ¤ i = Xi ·^xi;s¤ ' as the neighborhood dataset while ours consider X ¤ i = ^Xi * ^xi;s'' ·^xi;s¤' as the neighborhood dataset. That is because if we add one data record, the probability of sampling seeds, i.e., ^ci;s', will be totally changed. So the proof in [Bindschaedler et al., 2017] cannot satisfy our case.

5 Experiments

Performance measure. To evaluate the performance of our method, we adopt two measure metrics: the integrated squared error (ISE) and the squared integrated squared error (SISE). ISE is defined as: ‡Ni=1 � +� *� .fi * � fi/2dx, where fi and � fi are respectively the original density and the density derived from the synthetic data for object oi. SISE is defined as: ‡Ni=1 .� +� *� .fi* � fi/2dx/2 . Compared with ISE, SISE tends to penalize more on the large distance and less on the small distance. Since the goal of the collector is to release the data whose pattern is similar to the true underlying pattern for the objects, the lower the ISE or SISE, the better the method.

Datasets. We adopt the following real-world datasets for our experiments: Population Dataset [Pasternack and Roth, 2010; Wan et al., 2016], Stock Dataset [Li et al., 2012], and Indoor Floorplan Dataset [Li et al., 2014a]. The statistics of these datasets are provided in Table 1.

Baselines. Here, we adopt twobaselines, i.e. Basic andUniform. In the Basic method, the data collector adds three level noise to the original data: � = 0:1 (Strong), � = 1 (normal) and � = 10 (Weak). In the Uniform method, the collector treats all users equally and the entities' densities are learned with the uniformly weighted kernel density estimation. Here, the synthetic data generation and the privacy tests procedures are the same with those in our proposed method.

Case study. In order to investigate the advantages of the users' combined weights, we conduct case studies on the three real-world datasets. For each dataset, we randomly select two objects as the cases, and then estimate their densities. The estimated densities are shown in Fig. 3. The red line in each subfigure represents the density estimated based on users' combined weights. The black line represents the result estimated only based on the global weight of each user. We also conduct estimations without considering user quality, i.e., treating all users equally, and the estimated density for each object is represented with the green line. The results in Fig.3 show that the densities estimated based on users' combined weights are the closest to the true densities which are represented with the blue lines. Additionally, we show the claims of each object in this figure with magenta circles and crosses. We can see that some claims (i.e., the magenta crosses) are far away from others (i.e., the magenta circles). These claims are usually provided by the users with low weights, and they can be treated as outliers when estimating each object's density. The results show that the method based on the combined weight is more robust to outliers than the methods which only adopt users' global weights or treat all users equally. In other words, the estimated density for each object based PrisCrowd can well reflect the underlying true density of this object.

Accuracy comparison. In this experiment, we evaluate the accuracy (or quality) of the published synthetic data and explore whether these data can well reflect the underlying true densities of the objects. Here we assume that the data collector releases 30 synthetic claims for each object to the public. The parameters � and k are set as 4 and 5 respectively. In order to evaluate the accuracy of the synthetic claims, we first derive the density (i.e., � fi) of each object from the synthetic data, and then calculate ISE and SISE for each dataset. The results are shown in Table 2, from which we can see the proposed approach performs much better than the baseline methods on all real-world datasets. That is to say, the synthetic data generated based on our proposed method could well preserve the characteristics of the underlying pattern for the objects. Additionally, the results also show that the advantages of our proposed approach on the Stock dataset is larger than that on the Population and Indoor Floorplan datasets. The reason is that there are more outlying data points in the Stock dataset, and our proposed approach is robust to these outliers while the baseline methods are very sensitive to them.

The effect of the number of sampled claims. In this experiment, we evaluate the effect of the number of sampled claims for each object on the performance of the proposed method. Here we vary the number of the sampled claims for each object from 1 to 30 and then calculate the ISE and SISE on the three real-world datasets. The results are shown in Fig. 4, from which we can see the ISE and SISE gradually get flattened with the increase of the number of the sampled claims for each object. Take the population dataset as an example, when the number of sampled claims is lager than 10, the values of ISE and SISE are almost the same. That is to say, the released data generated based on our proposed method could well reflect the underlying patterns of the objects even only a few claims are sampled for each object.

Computational cost. Next we evaluate the computational cost of the synthetic claims generation procedure, i.e., the second phase in our proposed method. In this experiment, we only generate synthetic claims for the objects whose ground truths can be achieved from the original datasets, and consider two scenarios, i.e., with privacy tests and without privacy tests. Then we vary the number of the sampled claims for each object from 1 to 30. The running time of the synthetic claims generation procedure for the Population and Indoor Floorplan datasets is shown in Fig. 5, from which we can see the running time in the two scenarios is approximately linear with respect to the number of sampled claims for each object. Additionally, the results also show that the privacy test step introduce extra computational cost during the released data generation procedure. This is because each candidate synthetic data record needs to be tested in the privacy test step. Since good utility can be achieved based on our proposed method even only a few synthetic claims are generated for each object, the computational cost is tolerable in practice.

6 RelatedWork

Recently, various differential private data release approaches have been proposed. Those methods can be roughly partitioned into two categories: the interactive ones and the noninteractive ones. In an interactive method [Li et al., 2010; Hardt and Rothblum, 2010; Roth and Roughgarden, 2010], a data analyzer can pose queries via a private mechanism, and a dataset owner answers these queries in response. In the noninteractive framework [Nissim et al., 2007; Bindschaedler and Shokri, 2016; Blum et al., 2013; Wang et al., 2018; Wang et al., 2019], a data owner releases the private version of the original data. Once data are published, the owner has no further control over the published data.

The method in our paper is non-interactive. The typical approach to protect data privacy in the non-interactive context is to directly add noise, which is taken by [Bindschaedler and Shokri, 2016; Blum et al., 2013]. These works are either computationally infeasible on high-dimensional data, or practically ineffective because of their large utility costs. There are also some other works [Bindschaedler and Shokri, 2016] which release private data without adding noise, but they are unsuitable to be used in the newly appearing crowdsourcing setting considered in this paper where multi-sources provide multi-observations for multi-objects.

7 Conclusions

In this paper, we propose a novel privacy-aware synthesizing method for crowdsourced data. Based on this method, the data collector can release the crowdsourced data with strong privacy protection for users' private information, while at the same time, the data analyzer can achieve good utility from the released data. Both theoretical analysis and extensive experiments on real-world datasets verify the effectiveness of the proposed method.

Acknowledgements

This work was supported in part by the US National Science Foundation (NSF) under grants IIS-1514204 and CCF1716400. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the NSF.