# Using MOPSO for Optimizing Randomized Response Schemes in Privacy Computing

Authors: Zhiqiang Gao; Xiaolong Cui; Yanyu Duan; Zhang Jun; Zhensheng Peng
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

It is a challenging concern in data collecting, publishing, and mining when personal information is controlled by untrustworthy cloud services with unpredictable risks for privacy leakages. In this paper, we formulate an information-theoretic model for privacy protection and present a concrete solution to theoretical architecture in privacy computing from the perspectives of quantification and optimization. Thereinto, metrics of privacy and utility for randomized response (RR) which satisfy differential privacy are derived as average mutual information and average distortion rate under the information-theoretic model. Finally, a discrete multiobjective particle swarm optimization (MOPSO) is proposed to search optimal RR distorted matrices. To the best of our knowledge, our proposed approach is the first solution to optimize RR distorted matrices using discrete MOPSO. In detail, particles’ position and velocity are redefined in the problem-guided initialization and velocity updating mechanism. Two mutation strategies are introduced to escape from local optimum. The experimental results illustrate that our approach outperforms existing state-of-the-art works and can contribute optimal Pareto solutions of extensive RR schemes to future study.


---

## Body

## 1. Introduction

With the rapid development of artificial intelligence [1, 2] and mobile computing, big data has conceived booming series of services and has been regarded as a ubiquitously fundamental resource. New paradigms such as smart city [3], Takeout [4], and mobile pay [5] are growing at an amazing speed. Undoubtedly, these applications can provide users with accurate and personalized services with great convenience. However, large amounts of users’ personal information, including consuming habits, income status, and location, are collected beyond the control of their real owners. Especially, massive privacy concerns, including AOL search logs scandal (2006) [6, 7], de-anonymity and cancellation of Netflix prize (2009) [8, 9], complaint of privacy settings by Facebook (2009) [10], privacy breach of New York taxi trips (2016) [11], and massive breach of Equifax data (2017) [12] have tightened the whole society’s nerve over sensitive data collecting, releasing, and mining. It can be regarded as a profound privacy challenge and a motivating research field in privacy computing. On the whole, categories of privacy computing can be divided into three imperative aspects: privacy preserving data collecting (PPDC), privacy preserving data mining (PPDM), and privacy preserving data publishing (PPDP).Fruitful works of anonymity-based traditional privacy preserving methods [13–17], as well as randomization-based approaches [18–20], have been prominently studied and extensively applied in so many fields ranging from social networks [21], location-based services [22], and smart healthcare [23–25] to intelligent transportation [26]. However, most of traditional approaches are designed on specific application scenarios. Notably, newly arising challenges in privacy computing can be summarized into the following four urgent issues: (1) there still lack rigorous theoretical architecture and fundamental principles of privacy computing, which can systematically quantify privacy and describe relationship between protection level and utility loss; (2) large amounts of personal data are collected by untrustworthy collector, which enlarges the gap between owners and collectors in risk of privacy leakages; (3) new computing paradigms, such as MapReduce [27], Storm [28], and Spark [29], and deep learning, are in need of further security enhancement from the perspective of privacy computing; (4) optimization of the trade-off between individual privacy and data utility in privacy computing schemes should be further studied under the premise of satisfying users’ diversified requirements.In this paper, our work is concentrated on the most challenging issue of quantifying and optimizing the trade-off between data privacy and utility in privacy computing. Derived from the concept of privacy computing, randomized response [30, 31] is highly efficient in PPDC and capable of masking private data, while maintaining the reconstruction ability of aggregate information with tolerable errors. In RR schemes, individuals’ private data is transformed by RR distorted matrices (for ease of illustration, we use RR matrices for short.) to nonsensitive disguised data. Although RR schemes have been widely studied in sensitive survey, the primary problem of searching for optimal RR matrices is rarely explored. Additionally, the search space of RR matrix is astronomical and infeasible to exploit with brute-force method. We transform the comparison of RR schemes into the model of multiobjective optimization problem, for which multiobjective particle swarm optimization (MOPSO) [32] is extremely fit to provide a much more diversified set of optimal Pareto fronts than other solutions. Thus, different RR schemes can be compared in a quantified manner by two conflicting metrics of privacy and utility under the information-theoretic model. Moreover, differential privacy can provide a rigorous and fundamental guarantee for the optimization of RR schemes in privacy computing. Overall, MOPSO is utilized to search optimal RR matrices by the metrics of privacy and utility derived from the information-theoretic model. Our experimental results show a satisfying improvement over existing works and a wide range of optimal Pareto fronts are obtained for extensive schemes. The contributions of our work can be summarized as follows:(i)
We formulate the information-theoretic model for privacy quantification and present a solution to theoretical architecture in privacy computing.(ii)
We derive metrics of privacy and utility under the information-theoretic model for RR matrices which satisfy differential privacy.(iii)
We proposed a specified discrete MOPSO to find the optimal set of RR matrices under two conflicting goals: privacy and utility.The remainder of our paper is structured as follows. Section2 makes a systematic review on related works in privacy computing from the perspectives of quantification and optimization in PPDC, PPDP, and PPDM. In Section 3, the information entropy model in privacy computing is illustrated and the multiobjective optimization problem for quantifying privacy and data utility of RR schemes under ε-differential privacy is modeled. Section 4 presents a solution to searching optimal set of RR matrices by discrete MOPSO and Section 5 discusses the experimental results. Conclusion and future work are provided in Section 6.


## 2. Related Work

Roughly speaking, there can be three typical scenarios in privacy computing, namely, data collecting, data publishing, and data mining according to the convoluted life-cycle of private data. In fact, privacy computing (will be detailed in Section3) emphasizes the quantification and optimization.Privacy preserving data collection (PPDC), regarded as local privacy, is a strategy that perturbs the data locally before they reach the untrustworthy data-collector. The goal of PPDC is to satisfy accurate estimation of population statistics as well as guarantee the privacy of individual simultaneously. Wang et al. [33] compared randomized response with Laplace mechanism using differential privacy in PPDC and recommended a RR-based scheme with less utility loss. RAPPOR in [31] is also a RR-based application of differential privacy in Chrome, which allows crowd-sourcing statistics from client-end browsers with rigorous ε-differential privacy guarantee. PPDC can achieve meaningful aggregate information inferences while preserving the privacy of client-side users. Works in [30, 34–37] can be categorized into the scenario where data-collector wishes to grasp the distribution of original data while each client is just required to submit a perturbed version. Intuitively, these methods are in similarity with reconstruction on noised data. Notably, randomized response and local differential privacy [38] can be two powerful tools in PPDC. Coincidentally, randomized response can satisfy ε-differential privacy by specified parameter settings. However, FRAPP in [39] just generalized each element in distorted matrix by a single metric of accuracy. While, Agrawal and Srikant [36] just measured data reconstruction under differential privacy in terms of data utility by mean square error in the process of data mining. Huang and Du proposed a scheme of OptRR [34] which combines SPEA2 to find optimal distorted matrices in a heuristic way. Unfortunately, they mistake the dominance relationship of Pareto solutions. Additionally, the upper bound of privacy that derived from maximum a posteriori (MAP) estimate is not rigorous compared with differential privacy budget. In our work, two metrics of individuals’ privacy and data utility are optimized simultaneously under a unified model of multiobjective optimization problem, which can present a much more thorough illustration of RR matrices than FRAPP. Additionally, discrete MOPSO is proposed to provide more diversified optimal solutions than SPEA2. Particles’ position and velocity are both redefined and a novel velocity updating mechanism is adopted with two mutation strategies. The experiments show that our approach outperforms SPEA2 and FRAPP.Intuitively, there is no prominent discrimination between privacy preserving data publishing (PPDP) and privacy preserving data mining (PPDM) for the reason that the two models are built on the same assumption of trusted data-curator. Also, privacy preserving data collection can be covered by PPDM when collected data is directly served for data mining. According to the life-cycle of data and typical appliances, PPDC can be studied independently. On the one hand, there are two settings, namely, interactive and noninteractive in PPDP. Thereinto,k-anonymity [13] and its variants [14–17] are extensively studied on the assumption that data can be divided into sensitive attributes and quasi-identifiers in tabular forms. However, linkage attack, differential attack, and background knowledge attack are proposed in sequence to destroy the above privacy preserving models. To this end, anonymity-based approaches fail to provide strong privacy guarantees compared with the rigorous definition of differential privacy. Li et al. [40] preceded with randomized sampling before k-anonymity to achieve (ε, δ)-differential privacy, which shed lights on the broken gap between semantic security and syntactic security in PPDP. On the other hand, privacy preserving data mining was first proposed by Agrawal and Srikant in 2000 [36]. Later, Agrawal and Aggarwal [35] utilized EM algorithm to preserve individual privacy in the reconstruction of data distribution. In [30], Du and Zhan proposed a RR-based scheme to build decision trees on perturbed data and Agrawal and Haritsa presented a solution of privacy preserving computation for perturbed data with multiple attributes from multiple clients in [39].Although several lines of privacy computing fall into the scope of PPDC, PPDP, and PPDM, there still lacks a systematical architecture of privacy computing with fundamental supports in rigorous and provable theory. Our work systematically illustrates the domain of privacy computing and builds a new paradigm of multiobjective optimization problem, which is aimed at quantifying individuals’ privacy and data utility in PPDC. Guaranteed by differential privacy in randomized response, discrete MOPSO presents an excellent solution to the trade-off between privacy and data utility in optimal RR matrices and performs better than the state-of-the-art schemes.


## 3. Privacy Computing

### 3.1. Information-Theoretic Model

Privacy computing [41] can be defined as an open theoretic system, which is comprised of computing models, application scenarios, quantitative definitions, and powerful privacy preserving techniques. We quantify the concept of privacy under the general definition of information theory rather than terms that are restricted to sensitive or personal data from laws and regulations.Inspired by the process of information transferring in communication system, intrinsic similarity can be applied in privacy computing. Information will be affected by a noisy channel which can be regarded as a beneficial protection when they are transferred to the receiver-side. Here, we review information theory basics before demonstrating how to quantify privacy and utility in privacy computing.Information theory [42] is a mathematical framework for quantifying information transmission in communication systems. Figure 1 illustrates the scenario of a general channel model between source and receiver, which is illustrated in Scenario 1.Figure 1
General channel model of information theory.Scenario 1.
The probability space is comprised of discrete memoryless information sourceX, receiver Y, and channel P(Y∣X) as follows:(1)XPX=a1a2⋯asPa1Pa2⋯Pas,YPY=b1b2⋯brPb1Pb2⋯Pbr,PY∣X=pb1∣a1pb2∣a1⋯pbr∣a1pb1∣a2pb2∣a2⋯pbr∣a2⋮⋮⋮pb1∣aspb2∣as⋯pbr∣as,subjectto∑i=1sPai=1,0≤Pai≤1∑i=1rPbi=1,0≤Pbi≤1∑j=1rPbj∣ai=1,0≤Pbj∣ai≤1,i∈1,2,…,s.
SourceX∈a1,a2,…,as and receiver Y∈b1,b2,…,bs (sometimes r≠s) are discretized into mutually exclusive and exhaustive categories with corresponding probability as shown in Abbreviations. From the perspective of receiver’s observations, information source is an abstract mathematical representation for a physical entity that produces a succession of discrete symbols in a randomized manner. P(Y∣X) is the feature of channel with distortion noise. Overall, the transmission flow can be formulated as(2)PTY=PY∣XPTX.
Information theory quantifies how much information a receiverY carries about the source X, which is applicable in the scenario of measuring how much original information can be estimated from distorted data. Applying Shannon’s mathematical theory in information theory to privacy computing, we can derive several quantitative representations of information.Pertinent to information source in probability space, self-informationΙai denotes the uncertainty of event ai before the following occurs:(3)Iai=log⁡1Pai.Prior entropy of HX denotes the average uncertainty about X before received and the probability of secret leakage. The Shannon entropy of X is defined as(4)HX=∑i=1rPailog⁡1Pai.Posterior entropy HX∣Y denotes the average uncertainty about X after being received and the chance of attackers detecting secrets over the output(5)HX∣Y=EHX∣bj=∑j=1sPbjHX∣bj=∑i=1r∑j=1sPaibjlog⁡1Pai∣bj=∑X,YPxylog⁡1Px∣y.Mutual information IX;Y denotes how much X can be preserved from Y and gains by observing information leakage(6)IX;Y=HX-HX∣Y.Average mutual information can be calculated as (7)IX;Y=EX,YIx;y=∑X,YPxyIx;y=∑X,YPxylog⁡Px∣yPx.On the other hand, the decoding functionF can be used as the inverse process of channel when bj received from source ai(8)Fbj=ai.When signalbj is received, conditional error rate PE can be measured as follows:(9)Pe∣bj=1-Pai∣bj=1-PFbj∣bj.PE=∑YPbjPe∣bj=∑YPbj1-PFbj∣bj=1-∑YPFbjbj=∑X,YPaibj-∑YPFbjbj=∑X,YPaibj-∑YPa∗bj=∑Y,X-a∗Paibj.It is worth noting that privacy has many similarities with information theory and anonymity from a mathematical point of view. Thus, privacy can be generalized and formulated as follows.Definition 1 (privacy).
Given i.i.d vectorX=x1,x2,…,xn and the probability Pxi, privacy of X can be defined by information entropy in probability space(10)privacyX=-∑npxilog⁡pxi.
When variables ofXi and Xj are not independent, mutual information can be adopted to measure the information contained in one process about another through a noisy channel environment(11)privacyXi,Xj=∑pxi,xjlog⁡pxi∣xjpxi.
In practice, privacy can be estimated from distorted data by certain priori knowledge. Data utility can be measured by mean square error (MSE) of estimatorPX^ and PX [34](12)MSEX=EPX^-PX2.Equipped with the information-theoretic model of privacy above, we establish an open architecture of privacy computing with 7 key components, named tuple (X, P, M, Ф, Ω, T, Δ) as shown in Abbreviations.In detail, the distribution ofX plays a significant role in reconstruction and estimate of original attributes for private data. P denotes the set of participants, including owners of private information, analysts, attackers with arbitrary background knowledge, and curators and collectors of private information. M represents the metrics of quantifying privacy, for example, privacy and utility. Ф involves constraints on time and scenarios, such as data collection, data releasing, and data mining. Ω can be extended to the operations covering the whole life-cycle of privacy, including PPDC, PPDP, and PPDM. T represents mature privacy computing paradigms, such as randomized response, differential privacy, and k-anonymity. Additionally, Δ is the supplementary set of privacy computing. Theoretically, we can formulate the relationship of privacy and utility in the system of privacy computing(13)privacy=fX,P,M,Ф,Ω,utility=gX,P,M,Ф,Ω.In summary, privacy and utility are quantified by metric functions off and g with tuple of input parameter X, P, M, Ф, and Ω (the detailed description of f and g will be presented in Section 3.3). Specifically, in the concrete setting of our work, X denotes the collected categorical data from distributed clients. P represents the client-side user and the server-side untrustworthy collector. M is the evaluation metric of privacy and utility. Ф depicts the scenario setting where data collection occurs. Ω is the operation of randomized response in PPDC. Notably, T denotes the paradigm of randomized response guaranteed by differential privacy (the concrete usage of Ф and T will be described in Section 4).Intuitively, the scope of privacy computing involved in the life-cycle of privacy can be illustrated in Figure2. When privacy is collected, published, mined, or stored without protection, it is no better than destroying them directly.Figure 2
Life-cycle of privacy.


### 3.2. Randomized Response under Differential Privacy

Randomized response aims at eliciting information on sensitive survey and can be used to derive unbiased estimate from untruthful responses. Typically, aggregate information and relatively accurate reconstruction from distorted responses can be estimated and built while protecting local individual privacy by RR under differential privacy.Treated as the most rigorous privacy preserving tool, differential privacy (DP) [43, 44] is widely studied in privacy computing. DP can provide effective protection over the outcome no matter how one opts in or opts out of the database.Definition 2 (ε-differential privacy [18]).
Given two statistical databasesD and D′ which satisfy D-D′=1 (Hamming distance), randomized function A achieves ε-differential privacy on condition that(14)e-ε≤PrAD∈RPrAD′∈R≤eε,where A(D) denotes the output within the domain of R. ε is privacy budget which can balance privacy preserving level and utility of outputs.It is well accepted that Laplace mechanism can calibrate i.i.d noise from Laplace distribution which satisfies differential privacy. However, compared with randomized response, MSE of Laplace mechanism is ill-performed under the single metric of data utility [33]. Thus, our work emphasizes randomized response which conducts sensitive categorical data collection in privacy computing as shown in Scenario 2 and Figure 3.Figure 3
Randomized response scheme.Scenario 2.
Given thatn individual Ui∈U, U=U1,U2,…,Un, with categorical private data xi∈X, X=x1,x2,…,xn, to protect data privacy, each individual Ui submits another distorted version yi∈X within the same category domain to the untrustworthy data-collector by designed distorted matrices in randomized response.
Given thatP(xi) denotes the proportion of category xi in the original sensitive data and P∗(xi) denotes the proportion of xi in the distorted data and given that P⃑y∗=P∗(x1),P∗(x2),…,P∗(xn)T and P⃑x=P(x1),P(x2),…,P(xn)T, our designed distorted matrix M is as follows:(15)M=px1x1⋯px1xn⋮⋱⋮pxnx1⋯pxnxn,where pyx=pyi=y∣xi=x denotes the probability that when original data input is x and disguised output is y, we can get the following equation:(16)P⃑y∗=MP⃑x.Compared with Scenario1, we can bridge the gap between information theory and RR scheme in Scenario 2 of privacy computing. From the perspective of data-collector which is equal to the role of receiver in information-theoretic model, the number of categories xi in distorted data Ni (i=1,…,n) and the total number of records N can be used to derive the maximum likelihood estimation (MLE) of P⃑^∗y(17)P⃑^∗y=N1N,…,NnNT.In [37], Agrawal et al. proposed an iterative approach to estimate P⃑^x, resulting however in high running time consumption. Thus, we derive P⃑^x by matrix transformation based on (16). In other words, MLE of P⃑x can be obtained when M is invertible. We regard it as a constraint of M in the case that determinant of M is nonzero. It can be concluded that M is the key factor that determines the accuracy of estimating P⃑x. Undoubtedly, as the amount of data grows, the distribution reconstruction of P⃑x will be relatively close to the true distribution of original data(18)P⃑^x=M-1P⃑^y∗.However, how to design distorted matrices and compare which matrix is optimal remain to be fundamentally unsolved. In [33], designed distorted matrix with larger diagonal elements is deemed to achieve better data utility while thoroughly ignoring the metric of privacy and failing to provide a diversified set of optimal distorted matrices. Then we take a concrete example of binary data collection for better understanding [45].Example 1.
GivenX={x1,x2} and 2 × 2 distorted matrix M, the unbiased estimator and variance of the binary attribute x1 are as follows:(19)M=px1x1px1x2px2x1px2x2,π^=px1x1-12px1x1-1+N12px1x1-1N,Varπ^=1/4-π^-1/22N+1/16px1x1-1/22-1/4N.Derived from differential privacy in Definition2, we can reach the conclusion that while max⁡px1x1/px1x2,px2x2/px2x1≤eε is satisfied, ε-differential privacy can be achieved. When px1x1=eε/(eε+1) and px1x2=1/(eε+1), the designed distorted matrix can achieve the optimal utility [33]. Additionally, when a participant responses with a deniable probability of 1/4 in RR survey, we can get ε=ln⁡(0.75/(1-0.75))=ln⁡(3). That is, ln⁡(3)-differential privacy can guarantee the process of the sensitive information survey [31].However, while obtaining the highest data utility, privacy is not perfectly protected. Meanwhile, although guaranteed by differential privacy, different designed distorted matrices, such as Warner’s scheme in [45], Uniform Perturbation in [37], and FRAPP in [39], are difficult to determine which is optimal. Notably, the relationship of the two conflicting objectives can be defined as follows. Let f(M) and g(M) denote privacy and utility of RR matrices, respectively.Definition 3 (Pareto dominance).
M ∗ is in Pareto dominance i.f.f(20)∀Fp∈fM,gM:FpM∗≤FpM∧∃Fk∈fM,gM:FkM∗<FkM.Definition 4 (optimal RR matrix set).
The set of allM∗ in Pareto dominance from feasible domain Xp are(21)Archive=M∗∣¬∃M∈Xp:M≻M∗.Definition 5 (optimal RR matrix front).
The set of objective functions obtained by Pareto optimal set are(22)Pf=fM∗,gM∗∣M∗∈Archive.
Obviously, optimal RR matrices are not unique and, actually, we can find a set of optimal RR matrices for further selection in search space. In the next subsection, we are focused on the quantification scheme for metrics of privacy and utility pertinent tof(M) and g(M).


### 3.3. Scheme for Quantification

Measuring privacy and utility in RR schemes is crucial for many reasons [46, 47]. (1) It is difficult to justify RR matrices just by investigator’s intuition and experience. (2) The two criteria are conflicting in nature: when data utility increases, privacy will undoubtedly decrease to a certain degree and vice versa. However, combination of the two metrics can give thoroughly reasonable quantification schemes than a single one.Meanwhile, information theory can quantify how much information a receiverY carries about the source X. Noisy channel can link source coding and receiver decoding by quantitative notions of average mutual information and distortion rate. In OptRR [34], privacy is measured by the amount of individual privacy estimated from the distorted data, and utility is measured by MSE of original data and the estimator. Differently and more convincingly, we derive metrics of privacy and utility for distorted matrices by average mutual information and average distortion rate in information-theoretic model with much more rigorous mathematical foundation.


#### 3.3.1. Quantification for Privacy

Mutual information can be interpreted as the information preserved in the process of receiver from information source. Similarly, privacy can be defined as average mutual information in terms of discrete random probability space as in Scenario2. Similar to noisy channel between symmetric discrete source and receiver, client-side and server-side can communicate by distorted matrices as shown in Table 1.Table 1
Comparison of the two models.
Counterpart Comparison Source versus client-side Discrete memoryless information sourceX IndividualUi∈U with categorical data xi∈X Receiver versus server-side Discrete information receiverY Distorted versionyi∈Y Channel versus distorted matrices Noisy channel M = p x 1 x 1 ⋯ p x 1 x n ⋮ ⋱ ⋮ p x n x 1 ⋯ p x n x n, sum of each row is 1Our goal is to optimize distorted matrices by designed metrics inspired from noisy channel. In detail, privacy can be defined as average mutual informationIX;Y that the server-side obtained from client-side, namely, priori entropy HX minus posterior entropy HX∣Y. The value of privacy is equal to average uncertainty about X that remained in Y(23)
I
X
;
Y
=
H
X
-
H
X
∣
Y
=
∑
X
P
x
log
⁡
1
P
x
-
∑
X
,
Y
P
x
y
log
⁡
1
P
x
∣
y
=
∑
X
,
Y
P
x
y
log
⁡
1
P
x
-
∑
X
,
Y
P
x
y
log
⁡
1
P
x
∣
y
=
∑
X
,
Y
P
x
y
log
⁡
P
x
∣
y
P
x
=
∑
X
,
Y
P
x
y
log
⁡
P
x
y
P
x
P
y
=
∑
X
,
Y
P
x
y
log
⁡
P
y
∣
x
P
y
.Undoubtedly, the upper bound ofIX;Y can be restricted with obvious proof by(24)IX;Y≤min⁡HX,HY.From the perspective of adversary, the smaller the value ofI(X;Y) is, the better the privacy is protected. According to Jensen’s inequality and (23), average mutual information is bounded by 0≤IX;Y≤minHX,HY which is suitable for the bound of privacy. Metric functions of f in privacy computing can be represented by(25)privacy=∑X,YPxylog⁡Py∣xPy.


#### 3.3.2. Quantification for Utility

In information-theoretic model of privacy computing, data utility can be quantified by average distortion rate which is the measure of how muchX and Y are distorted. Distortion function and distortion matrix are represented by (26)dX,Y≥0,(27)dxi,yj=0,i=j1,i≠j,(28)D=da1,b1da1,b2⋯da1,brda2,b1da2,b2⋯da2,br⋮⋮⋮dar,b1dar,b2⋯dar,br.Distortion function defined in (26) and (27) is nonnegative. The distortion matrix can be computed in (28). Finally, average distortion rate can be computed as(29)D-=Edx,y=∑X,YPxydx,y=∑i=1∑j=1PyiPxj∣yidxi,yj.Thus, utility is defined by average distortion rate; the smaller its value, the higher its utility. Metric functions ofg in privacy computing can be represented by(30)utility=∑i=1∑j=1PyiPxj∣yidxi,yj.Finally, our work is focused on minimizing the two objectives of privacy and utility simultaneously under specified constraints. In next section, we will illustrate our solution to the problem illustrated in (31) by our proposed discrete MOPSO(31)V-minFM=fM,gMTs.t.discreteprobabiltyspaceε-differential  privacydetM≠0.Notably, constraint that is determinant ofM, det(M), is nonzero which guarantees that M is invertible.


## 3.1. Information-Theoretic Model

Privacy computing [41] can be defined as an open theoretic system, which is comprised of computing models, application scenarios, quantitative definitions, and powerful privacy preserving techniques. We quantify the concept of privacy under the general definition of information theory rather than terms that are restricted to sensitive or personal data from laws and regulations.Inspired by the process of information transferring in communication system, intrinsic similarity can be applied in privacy computing. Information will be affected by a noisy channel which can be regarded as a beneficial protection when they are transferred to the receiver-side. Here, we review information theory basics before demonstrating how to quantify privacy and utility in privacy computing.Information theory [42] is a mathematical framework for quantifying information transmission in communication systems. Figure 1 illustrates the scenario of a general channel model between source and receiver, which is illustrated in Scenario 1.Figure 1
General channel model of information theory.Scenario 1.
The probability space is comprised of discrete memoryless information sourceX, receiver Y, and channel P(Y∣X) as follows:(1)XPX=a1a2⋯asPa1Pa2⋯Pas,YPY=b1b2⋯brPb1Pb2⋯Pbr,PY∣X=pb1∣a1pb2∣a1⋯pbr∣a1pb1∣a2pb2∣a2⋯pbr∣a2⋮⋮⋮pb1∣aspb2∣as⋯pbr∣as,subjectto∑i=1sPai=1,0≤Pai≤1∑i=1rPbi=1,0≤Pbi≤1∑j=1rPbj∣ai=1,0≤Pbj∣ai≤1,i∈1,2,…,s.
SourceX∈a1,a2,…,as and receiver Y∈b1,b2,…,bs (sometimes r≠s) are discretized into mutually exclusive and exhaustive categories with corresponding probability as shown in Abbreviations. From the perspective of receiver’s observations, information source is an abstract mathematical representation for a physical entity that produces a succession of discrete symbols in a randomized manner. P(Y∣X) is the feature of channel with distortion noise. Overall, the transmission flow can be formulated as(2)PTY=PY∣XPTX.
Information theory quantifies how much information a receiverY carries about the source X, which is applicable in the scenario of measuring how much original information can be estimated from distorted data. Applying Shannon’s mathematical theory in information theory to privacy computing, we can derive several quantitative representations of information.Pertinent to information source in probability space, self-informationΙai denotes the uncertainty of event ai before the following occurs:(3)Iai=log⁡1Pai.Prior entropy of HX denotes the average uncertainty about X before received and the probability of secret leakage. The Shannon entropy of X is defined as(4)HX=∑i=1rPailog⁡1Pai.Posterior entropy HX∣Y denotes the average uncertainty about X after being received and the chance of attackers detecting secrets over the output(5)HX∣Y=EHX∣bj=∑j=1sPbjHX∣bj=∑i=1r∑j=1sPaibjlog⁡1Pai∣bj=∑X,YPxylog⁡1Px∣y.Mutual information IX;Y denotes how much X can be preserved from Y and gains by observing information leakage(6)IX;Y=HX-HX∣Y.Average mutual information can be calculated as (7)IX;Y=EX,YIx;y=∑X,YPxyIx;y=∑X,YPxylog⁡Px∣yPx.On the other hand, the decoding functionF can be used as the inverse process of channel when bj received from source ai(8)Fbj=ai.When signalbj is received, conditional error rate PE can be measured as follows:(9)Pe∣bj=1-Pai∣bj=1-PFbj∣bj.PE=∑YPbjPe∣bj=∑YPbj1-PFbj∣bj=1-∑YPFbjbj=∑X,YPaibj-∑YPFbjbj=∑X,YPaibj-∑YPa∗bj=∑Y,X-a∗Paibj.It is worth noting that privacy has many similarities with information theory and anonymity from a mathematical point of view. Thus, privacy can be generalized and formulated as follows.Definition 1 (privacy).
Given i.i.d vectorX=x1,x2,…,xn and the probability Pxi, privacy of X can be defined by information entropy in probability space(10)privacyX=-∑npxilog⁡pxi.
When variables ofXi and Xj are not independent, mutual information can be adopted to measure the information contained in one process about another through a noisy channel environment(11)privacyXi,Xj=∑pxi,xjlog⁡pxi∣xjpxi.
In practice, privacy can be estimated from distorted data by certain priori knowledge. Data utility can be measured by mean square error (MSE) of estimatorPX^ and PX [34](12)MSEX=EPX^-PX2.Equipped with the information-theoretic model of privacy above, we establish an open architecture of privacy computing with 7 key components, named tuple (X, P, M, Ф, Ω, T, Δ) as shown in Abbreviations.In detail, the distribution ofX plays a significant role in reconstruction and estimate of original attributes for private data. P denotes the set of participants, including owners of private information, analysts, attackers with arbitrary background knowledge, and curators and collectors of private information. M represents the metrics of quantifying privacy, for example, privacy and utility. Ф involves constraints on time and scenarios, such as data collection, data releasing, and data mining. Ω can be extended to the operations covering the whole life-cycle of privacy, including PPDC, PPDP, and PPDM. T represents mature privacy computing paradigms, such as randomized response, differential privacy, and k-anonymity. Additionally, Δ is the supplementary set of privacy computing. Theoretically, we can formulate the relationship of privacy and utility in the system of privacy computing(13)privacy=fX,P,M,Ф,Ω,utility=gX,P,M,Ф,Ω.In summary, privacy and utility are quantified by metric functions off and g with tuple of input parameter X, P, M, Ф, and Ω (the detailed description of f and g will be presented in Section 3.3). Specifically, in the concrete setting of our work, X denotes the collected categorical data from distributed clients. P represents the client-side user and the server-side untrustworthy collector. M is the evaluation metric of privacy and utility. Ф depicts the scenario setting where data collection occurs. Ω is the operation of randomized response in PPDC. Notably, T denotes the paradigm of randomized response guaranteed by differential privacy (the concrete usage of Ф and T will be described in Section 4).Intuitively, the scope of privacy computing involved in the life-cycle of privacy can be illustrated in Figure2. When privacy is collected, published, mined, or stored without protection, it is no better than destroying them directly.Figure 2
Life-cycle of privacy.


## 3.2. Randomized Response under Differential Privacy

Randomized response aims at eliciting information on sensitive survey and can be used to derive unbiased estimate from untruthful responses. Typically, aggregate information and relatively accurate reconstruction from distorted responses can be estimated and built while protecting local individual privacy by RR under differential privacy.Treated as the most rigorous privacy preserving tool, differential privacy (DP) [43, 44] is widely studied in privacy computing. DP can provide effective protection over the outcome no matter how one opts in or opts out of the database.Definition 2 (ε-differential privacy [18]).
Given two statistical databasesD and D′ which satisfy D-D′=1 (Hamming distance), randomized function A achieves ε-differential privacy on condition that(14)e-ε≤PrAD∈RPrAD′∈R≤eε,where A(D) denotes the output within the domain of R. ε is privacy budget which can balance privacy preserving level and utility of outputs.It is well accepted that Laplace mechanism can calibrate i.i.d noise from Laplace distribution which satisfies differential privacy. However, compared with randomized response, MSE of Laplace mechanism is ill-performed under the single metric of data utility [33]. Thus, our work emphasizes randomized response which conducts sensitive categorical data collection in privacy computing as shown in Scenario 2 and Figure 3.Figure 3
Randomized response scheme.Scenario 2.
Given thatn individual Ui∈U, U=U1,U2,…,Un, with categorical private data xi∈X, X=x1,x2,…,xn, to protect data privacy, each individual Ui submits another distorted version yi∈X within the same category domain to the untrustworthy data-collector by designed distorted matrices in randomized response.
Given thatP(xi) denotes the proportion of category xi in the original sensitive data and P∗(xi) denotes the proportion of xi in the distorted data and given that P⃑y∗=P∗(x1),P∗(x2),…,P∗(xn)T and P⃑x=P(x1),P(x2),…,P(xn)T, our designed distorted matrix M is as follows:(15)M=px1x1⋯px1xn⋮⋱⋮pxnx1⋯pxnxn,where pyx=pyi=y∣xi=x denotes the probability that when original data input is x and disguised output is y, we can get the following equation:(16)P⃑y∗=MP⃑x.Compared with Scenario1, we can bridge the gap between information theory and RR scheme in Scenario 2 of privacy computing. From the perspective of data-collector which is equal to the role of receiver in information-theoretic model, the number of categories xi in distorted data Ni (i=1,…,n) and the total number of records N can be used to derive the maximum likelihood estimation (MLE) of P⃑^∗y(17)P⃑^∗y=N1N,…,NnNT.In [37], Agrawal et al. proposed an iterative approach to estimate P⃑^x, resulting however in high running time consumption. Thus, we derive P⃑^x by matrix transformation based on (16). In other words, MLE of P⃑x can be obtained when M is invertible. We regard it as a constraint of M in the case that determinant of M is nonzero. It can be concluded that M is the key factor that determines the accuracy of estimating P⃑x. Undoubtedly, as the amount of data grows, the distribution reconstruction of P⃑x will be relatively close to the true distribution of original data(18)P⃑^x=M-1P⃑^y∗.However, how to design distorted matrices and compare which matrix is optimal remain to be fundamentally unsolved. In [33], designed distorted matrix with larger diagonal elements is deemed to achieve better data utility while thoroughly ignoring the metric of privacy and failing to provide a diversified set of optimal distorted matrices. Then we take a concrete example of binary data collection for better understanding [45].Example 1.
GivenX={x1,x2} and 2 × 2 distorted matrix M, the unbiased estimator and variance of the binary attribute x1 are as follows:(19)M=px1x1px1x2px2x1px2x2,π^=px1x1-12px1x1-1+N12px1x1-1N,Varπ^=1/4-π^-1/22N+1/16px1x1-1/22-1/4N.Derived from differential privacy in Definition2, we can reach the conclusion that while max⁡px1x1/px1x2,px2x2/px2x1≤eε is satisfied, ε-differential privacy can be achieved. When px1x1=eε/(eε+1) and px1x2=1/(eε+1), the designed distorted matrix can achieve the optimal utility [33]. Additionally, when a participant responses with a deniable probability of 1/4 in RR survey, we can get ε=ln⁡(0.75/(1-0.75))=ln⁡(3). That is, ln⁡(3)-differential privacy can guarantee the process of the sensitive information survey [31].However, while obtaining the highest data utility, privacy is not perfectly protected. Meanwhile, although guaranteed by differential privacy, different designed distorted matrices, such as Warner’s scheme in [45], Uniform Perturbation in [37], and FRAPP in [39], are difficult to determine which is optimal. Notably, the relationship of the two conflicting objectives can be defined as follows. Let f(M) and g(M) denote privacy and utility of RR matrices, respectively.Definition 3 (Pareto dominance).
M ∗ is in Pareto dominance i.f.f(20)∀Fp∈fM,gM:FpM∗≤FpM∧∃Fk∈fM,gM:FkM∗<FkM.Definition 4 (optimal RR matrix set).
The set of allM∗ in Pareto dominance from feasible domain Xp are(21)Archive=M∗∣¬∃M∈Xp:M≻M∗.Definition 5 (optimal RR matrix front).
The set of objective functions obtained by Pareto optimal set are(22)Pf=fM∗,gM∗∣M∗∈Archive.
Obviously, optimal RR matrices are not unique and, actually, we can find a set of optimal RR matrices for further selection in search space. In the next subsection, we are focused on the quantification scheme for metrics of privacy and utility pertinent tof(M) and g(M).


## 3.3. Scheme for Quantification

Measuring privacy and utility in RR schemes is crucial for many reasons [46, 47]. (1) It is difficult to justify RR matrices just by investigator’s intuition and experience. (2) The two criteria are conflicting in nature: when data utility increases, privacy will undoubtedly decrease to a certain degree and vice versa. However, combination of the two metrics can give thoroughly reasonable quantification schemes than a single one.Meanwhile, information theory can quantify how much information a receiverY carries about the source X. Noisy channel can link source coding and receiver decoding by quantitative notions of average mutual information and distortion rate. In OptRR [34], privacy is measured by the amount of individual privacy estimated from the distorted data, and utility is measured by MSE of original data and the estimator. Differently and more convincingly, we derive metrics of privacy and utility for distorted matrices by average mutual information and average distortion rate in information-theoretic model with much more rigorous mathematical foundation.


### 3.3.1. Quantification for Privacy

Mutual information can be interpreted as the information preserved in the process of receiver from information source. Similarly, privacy can be defined as average mutual information in terms of discrete random probability space as in Scenario2. Similar to noisy channel between symmetric discrete source and receiver, client-side and server-side can communicate by distorted matrices as shown in Table 1.Table 1
Comparison of the two models.
Counterpart Comparison Source versus client-side Discrete memoryless information sourceX IndividualUi∈U with categorical data xi∈X Receiver versus server-side Discrete information receiverY Distorted versionyi∈Y Channel versus distorted matrices Noisy channel M = p x 1 x 1 ⋯ p x 1 x n ⋮ ⋱ ⋮ p x n x 1 ⋯ p x n x n, sum of each row is 1Our goal is to optimize distorted matrices by designed metrics inspired from noisy channel. In detail, privacy can be defined as average mutual informationIX;Y that the server-side obtained from client-side, namely, priori entropy HX minus posterior entropy HX∣Y. The value of privacy is equal to average uncertainty about X that remained in Y(23)
I
X
;
Y
=
H
X
-
H
X
∣
Y
=
∑
X
P
x
log
⁡
1
P
x
-
∑
X
,
Y
P
x
y
log
⁡
1
P
x
∣
y
=
∑
X
,
Y
P
x
y
log
⁡
1
P
x
-
∑
X
,
Y
P
x
y
log
⁡
1
P
x
∣
y
=
∑
X
,
Y
P
x
y
log
⁡
P
x
∣
y
P
x
=
∑
X
,
Y
P
x
y
log
⁡
P
x
y
P
x
P
y
=
∑
X
,
Y
P
x
y
log
⁡
P
y
∣
x
P
y
.Undoubtedly, the upper bound ofIX;Y can be restricted with obvious proof by(24)IX;Y≤min⁡HX,HY.From the perspective of adversary, the smaller the value ofI(X;Y) is, the better the privacy is protected. According to Jensen’s inequality and (23), average mutual information is bounded by 0≤IX;Y≤minHX,HY which is suitable for the bound of privacy. Metric functions of f in privacy computing can be represented by(25)privacy=∑X,YPxylog⁡Py∣xPy.


### 3.3.2. Quantification for Utility

In information-theoretic model of privacy computing, data utility can be quantified by average distortion rate which is the measure of how muchX and Y are distorted. Distortion function and distortion matrix are represented by (26)dX,Y≥0,(27)dxi,yj=0,i=j1,i≠j,(28)D=da1,b1da1,b2⋯da1,brda2,b1da2,b2⋯da2,br⋮⋮⋮dar,b1dar,b2⋯dar,br.Distortion function defined in (26) and (27) is nonnegative. The distortion matrix can be computed in (28). Finally, average distortion rate can be computed as(29)D-=Edx,y=∑X,YPxydx,y=∑i=1∑j=1PyiPxj∣yidxi,yj.Thus, utility is defined by average distortion rate; the smaller its value, the higher its utility. Metric functions ofg in privacy computing can be represented by(30)utility=∑i=1∑j=1PyiPxj∣yidxi,yj.Finally, our work is focused on minimizing the two objectives of privacy and utility simultaneously under specified constraints. In next section, we will illustrate our solution to the problem illustrated in (31) by our proposed discrete MOPSO(31)V-minFM=fM,gMTs.t.discreteprobabiltyspaceε-differential  privacydetM≠0.Notably, constraint that is determinant ofM, det(M), is nonzero which guarantees that M is invertible.


## 3.3.1. Quantification for Privacy

Mutual information can be interpreted as the information preserved in the process of receiver from information source. Similarly, privacy can be defined as average mutual information in terms of discrete random probability space as in Scenario2. Similar to noisy channel between symmetric discrete source and receiver, client-side and server-side can communicate by distorted matrices as shown in Table 1.Table 1
Comparison of the two models.
Counterpart Comparison Source versus client-side Discrete memoryless information sourceX IndividualUi∈U with categorical data xi∈X Receiver versus server-side Discrete information receiverY Distorted versionyi∈Y Channel versus distorted matrices Noisy channel M = p x 1 x 1 ⋯ p x 1 x n ⋮ ⋱ ⋮ p x n x 1 ⋯ p x n x n, sum of each row is 1Our goal is to optimize distorted matrices by designed metrics inspired from noisy channel. In detail, privacy can be defined as average mutual informationIX;Y that the server-side obtained from client-side, namely, priori entropy HX minus posterior entropy HX∣Y. The value of privacy is equal to average uncertainty about X that remained in Y(23)
I
X
;
Y
=
H
X
-
H
X
∣
Y
=
∑
X
P
x
log
⁡
1
P
x
-
∑
X
,
Y
P
x
y
log
⁡
1
P
x
∣
y
=
∑
X
,
Y
P
x
y
log
⁡
1
P
x
-
∑
X
,
Y
P
x
y
log
⁡
1
P
x
∣
y
=
∑
X
,
Y
P
x
y
log
⁡
P
x
∣
y
P
x
=
∑
X
,
Y
P
x
y
log
⁡
P
x
y
P
x
P
y
=
∑
X
,
Y
P
x
y
log
⁡
P
y
∣
x
P
y
.Undoubtedly, the upper bound ofIX;Y can be restricted with obvious proof by(24)IX;Y≤min⁡HX,HY.From the perspective of adversary, the smaller the value ofI(X;Y) is, the better the privacy is protected. According to Jensen’s inequality and (23), average mutual information is bounded by 0≤IX;Y≤minHX,HY which is suitable for the bound of privacy. Metric functions of f in privacy computing can be represented by(25)privacy=∑X,YPxylog⁡Py∣xPy.


## 3.3.2. Quantification for Utility

In information-theoretic model of privacy computing, data utility can be quantified by average distortion rate which is the measure of how muchX and Y are distorted. Distortion function and distortion matrix are represented by (26)dX,Y≥0,(27)dxi,yj=0,i=j1,i≠j,(28)D=da1,b1da1,b2⋯da1,brda2,b1da2,b2⋯da2,br⋮⋮⋮dar,b1dar,b2⋯dar,br.Distortion function defined in (26) and (27) is nonnegative. The distortion matrix can be computed in (28). Finally, average distortion rate can be computed as(29)D-=Edx,y=∑X,YPxydx,y=∑i=1∑j=1PyiPxj∣yidxi,yj.Thus, utility is defined by average distortion rate; the smaller its value, the higher its utility. Metric functions ofg in privacy computing can be represented by(30)utility=∑i=1∑j=1PyiPxj∣yidxi,yj.Finally, our work is focused on minimizing the two objectives of privacy and utility simultaneously under specified constraints. In next section, we will illustrate our solution to the problem illustrated in (31) by our proposed discrete MOPSO(31)V-minFM=fM,gMTs.t.discreteprobabiltyspaceε-differential  privacydetM≠0.Notably, constraint that is determinant ofM, det(M), is nonzero which guarantees that M is invertible.


## 4. MOPSO in Privacy Computing

In a simplified condition that RR matrices are generated from the range of{0,1/d,2/d,…,1} (d is integer), the NP-hard problem of searching optimal RR matrices reaches an astronomical number of d+n-1dn, while the real search boundary of our scheme is the whole probability space which is much more complex than the condition above. Therefore, we provide discrete MOPSO to optimize conflicting goals of privacy and utility simultaneously and evaluate different RR schemes with fewer tunable variables as well as fast convergent rate.


### 4.1. Outline of Algorithm

The two objectives of privacy and utility are derived from RR matrices which can reflect the nature of privacy information in RR schemes. In detail, average mutual information and average distortion rate are constrained byε-differential privacy and probability boundary. Our proposed discrete MOPSO is comprised of the following stages as shown in Algorithm 1.  (1) Particles are initialized in a structure of discrete position, velocity, personal-best, global-best, repository, and mutation archive with dynamic hypervolume; (2) velocity updating is redefined by activation function of ReLU which can retain best genes from global-best for new discrete position; (3) repository updating is guaranteed by hypercube quality and diversity by hypervolume in combination with roulette wheel selection and crowding distances dynamically and adaptively; (4) performance of mutation archive is determined by two strategies of mutation percentage and guided-random mechanism to maintain diversity of computation; (5) constraints judgment: ε-differential privacy guarantees the rigorous protection bounds against arbitrary background knowledge. In each column of RR matrix, the ratio of maximum and minimum is bounded by privacy budget. The sum of each column is 1 and determinant of each matrix is nonzero; (6) termination judgment. Notably, the combination of repository and mutation archive are the final output of optimal RR matrices after Pareto dominance check. The process of our algorithm is illustrated in the following and parameters are listed in Abbreviations.Algorithm 1:Discrete MOPSO for optimizing for RR matrices.
Input: Parameters of Np, Nr, Nm, maxgen, dim Output: Final optimal set repository. Step  1. Initialization: Do Step  1.1. Initialization in particles of position POS, Velocity VEL, PBEST, GBEST; Step  1.2. Initialization in repository REP; Step  1.3. Initialization in mutation archive ARC; Step  1.4. Check constraints: (1) Each column in POS is bounded by maxx=1,…,tmaxx=1,…,t⁡pxy/minx=1,…,t⁡pxy≤eε; (2) Sum of each column in POS is 1; (3) Determinant of POS cannot be 0. While constraints cannot be satisfied simultaneously, return to Step  1.1. Step  2. Repeat: Step  2.1. Updating VEL and POS for each particle according to velocity updating mechanism and check constraints for newPOS as Step  1.1; Step  2.2. Calculate fitness under evaluation function for each particle and update PBEST and GBEST; Step  2.3. Update REP by Pareto dominance and hyper-volume respectively; Step  2.4. Mutation is operated on ARC while Nm>0. Two strategies of mutation percentage is set to 1/3 and guided-random mechanism is a partial imitation of GBEST in REP under boundary constraints; Step  3. Termination: If stopping criterion is achieved, halt and check the combination of REP and ARC by Pareto dominance. Output the final optimal RR matricesfrom REP and ARC; Otherwise, loop to Step  2.


### 4.2. Initialization

RR matrix is coded as position of particle,POS, in which sum of each column is normalized to 1 and determinant of which is nonzero under constraint of ε-differential privacy.POS_fit is a vector of privacy and utility for each particle evaluated by two objective functions from (25) and (30). Initialization of velocityVEL is a randomized matrix with the same size asPOS. Personal-bestPBEST is initialized byPOS andPOS_fit.GBEST is selected fromPBEST of each particle at random. RepositoryREP and mutation archiveARC are initialized as empty sets at first.


### 4.3. Velocity Updating

According to continual velocity updating rule in (32), we redefine the operation of velocity in a discrete form. Inspired by activation function of rectified linear unit (ReLU), velocity is discretized into a copy of certain features fromGBEST by our scheme of ReLU in (32) and (33) as shown in Figure 4. Each element inVEL is a representation of certain excellent episodes fromGBEST. In this paper, cognitive and social components of c1, c1 are fixed to value 2. Inertia weight ofωis set to 0.4. r1 and r2 are random factors generated from the interval of 0 and 1(32)VEL=ReLUω∗VEL+c1∗r1∗PBEST-POS+c2∗r2∗GBEST-POS(33)ReLU=max⁡0,x=0,ifx≤0x,ifx>0.Figure 4
Activation function of ReLU.In detail,VEL is transformed by ReLU by the threshold of 0. Utilizing the operator of AND withGBEST in (34), outstanding episode truncated fromGBEST is preserved directly. Then corresponding position inPOS is substituted by the outstanding episode maintained inVEL with replacing operator of ⊕. After normalization ofPOS, a new position is updated in (35)(34)VEL=VELANDGBSET(35)POS=normalizeVEL⊕POS.Overall, an illustrative example of velocity updating for each particle can be depicted in Figure5.Figure 5
Example of velocity updating.


### 4.4. Repository Updating

RepositoryREP is the archive of good RR matrices in the representative form ofPOS. In order to maintain diversity and optimize distribution, our updating mechanism is based on hypervolume and crowd distance. Hypervolume is divided by hyperlimits and hypercube dynamically and adaptively according to the boundaries of each Pareto solution inREP. Each hypercube bounded by hyperlimits is assigned with hyperquality based on the number of particles inside.GBEST is selected by roulette wheel in the hypercube with higher hyperquality. When particles exceed the capacity of repository, extra particles with the smallest crowding distances, which are measured by (36), are removed and transferred to the mutation archiveARCfor the use of mutation(36)dXi=1n-1∑Y∈REP-XidimXi-Y2,where dim is the dimension of Xi and n denotes the number of particles inREP. In other words, crowding distance is a measure of average distance with all the other particles inREP.


### 4.5. Strategies for Mutation

To maintain diversity and enhance ability to escape from local optimum, two strategies for mutation are designed: fixed mutation percentage and guided-randomization as shown in Algorithm2.Algorithm 2:Mutation for discrete MOPSO.
Input: ARC and mutation percentage P Output: New particles. Step  1. Randomized mutation Select particles from ARC according to percentage P; Each selected particle is re-randomized; P ∗ d i m columns in each particle are replaced by newly generated columns which still satisfy constraints as in Algorithm1; Calculate fitness for each newly generated particle. Step  2. Guided mutation Select the remaining particles from ARC; Each particle is mutated by the guidance of GBEST; ( 1 - P ) ∗ d i m columns in each particle are replaced by corresponding columns in GBEST which still satisfy constraints as in Algorithm 1; Calculate fitness for each newly generated particle.


### 4.6. Boundaries Checking

Position of all particles are bounded byε-differential privacy when maxx=1,…,t⁡(maxx=1,…,tpxy/minx=1,…,tpxy)≤eε, which means that the maximum in each column is no more than eε times of the minimum. The tunable parameter of privacy budget ε is regulated to satisfy different users’ privacy-preserved requirements. In addition, mutation is performed in the phase of particle updating when certain position is out of the bound.


### 4.7. Termination Checking

Termination criterion for MOPSO can be set as follows:(1) limiting the maximum iteration number; (2) among certain number of consecutive generations, quality of repositoryREP does not improve. When termination criterion is met, the combination set of optimal RR matrices in Pareto dominance fromREP andARC is output as the final solution. In our work for termination, we combine both methods for the reason that either criterion can guarantee a diversified optimal solution set for different requirements and can benefit from the fast convergent feature of MOPSO.


### 4.8. Complexity Analysis

#### 4.8.1. Space Complexity

In our scheme of discrete MOPSO, two RR matrices set, namely,REP andARC, are needed, both of which occupy complexity of O((Nr+Nm)∗dim2). Nr and Nm are the size ofREP andARC with particles’ dimension of dim. All particles need a complexity of O(Np∗dim2), where Np is the size of population. Thus, the total space complexity of discrete MOPSO for RR matrices is O((Np+Nm+Nr)∗dim2).


#### 4.8.2. Time Complexity

The main time complexity is occupied by Pareto dominance check and repository updating in Algorithm1. For ease of representation, let n be the number of solution. The evaluation number is 2Cn2, namely, O(n2). Initialization inStep  1 needs O(Np∗n2) operations of Pareto dominance check. Repository updating inStep  2 occupies complexity of O(n2). Thus, the worst running time complexity of our scheme is O(max(Np,maxgen)∗n2), where maxgen is the iteration number.


## 4.1. Outline of Algorithm

The two objectives of privacy and utility are derived from RR matrices which can reflect the nature of privacy information in RR schemes. In detail, average mutual information and average distortion rate are constrained byε-differential privacy and probability boundary. Our proposed discrete MOPSO is comprised of the following stages as shown in Algorithm 1.  (1) Particles are initialized in a structure of discrete position, velocity, personal-best, global-best, repository, and mutation archive with dynamic hypervolume; (2) velocity updating is redefined by activation function of ReLU which can retain best genes from global-best for new discrete position; (3) repository updating is guaranteed by hypercube quality and diversity by hypervolume in combination with roulette wheel selection and crowding distances dynamically and adaptively; (4) performance of mutation archive is determined by two strategies of mutation percentage and guided-random mechanism to maintain diversity of computation; (5) constraints judgment: ε-differential privacy guarantees the rigorous protection bounds against arbitrary background knowledge. In each column of RR matrix, the ratio of maximum and minimum is bounded by privacy budget. The sum of each column is 1 and determinant of each matrix is nonzero; (6) termination judgment. Notably, the combination of repository and mutation archive are the final output of optimal RR matrices after Pareto dominance check. The process of our algorithm is illustrated in the following and parameters are listed in Abbreviations.Algorithm 1:Discrete MOPSO for optimizing for RR matrices.
Input: Parameters of Np, Nr, Nm, maxgen, dim Output: Final optimal set repository. Step  1. Initialization: Do Step  1.1. Initialization in particles of position POS, Velocity VEL, PBEST, GBEST; Step  1.2. Initialization in repository REP; Step  1.3. Initialization in mutation archive ARC; Step  1.4. Check constraints: (1) Each column in POS is bounded by maxx=1,…,tmaxx=1,…,t⁡pxy/minx=1,…,t⁡pxy≤eε; (2) Sum of each column in POS is 1; (3) Determinant of POS cannot be 0. While constraints cannot be satisfied simultaneously, return to Step  1.1. Step  2. Repeat: Step  2.1. Updating VEL and POS for each particle according to velocity updating mechanism and check constraints for newPOS as Step  1.1; Step  2.2. Calculate fitness under evaluation function for each particle and update PBEST and GBEST; Step  2.3. Update REP by Pareto dominance and hyper-volume respectively; Step  2.4. Mutation is operated on ARC while Nm>0. Two strategies of mutation percentage is set to 1/3 and guided-random mechanism is a partial imitation of GBEST in REP under boundary constraints; Step  3. Termination: If stopping criterion is achieved, halt and check the combination of REP and ARC by Pareto dominance. Output the final optimal RR matricesfrom REP and ARC; Otherwise, loop to Step  2.


## 4.2. Initialization

RR matrix is coded as position of particle,POS, in which sum of each column is normalized to 1 and determinant of which is nonzero under constraint of ε-differential privacy.POS_fit is a vector of privacy and utility for each particle evaluated by two objective functions from (25) and (30). Initialization of velocityVEL is a randomized matrix with the same size asPOS. Personal-bestPBEST is initialized byPOS andPOS_fit.GBEST is selected fromPBEST of each particle at random. RepositoryREP and mutation archiveARC are initialized as empty sets at first.


## 4.3. Velocity Updating

According to continual velocity updating rule in (32), we redefine the operation of velocity in a discrete form. Inspired by activation function of rectified linear unit (ReLU), velocity is discretized into a copy of certain features fromGBEST by our scheme of ReLU in (32) and (33) as shown in Figure 4. Each element inVEL is a representation of certain excellent episodes fromGBEST. In this paper, cognitive and social components of c1, c1 are fixed to value 2. Inertia weight ofωis set to 0.4. r1 and r2 are random factors generated from the interval of 0 and 1(32)VEL=ReLUω∗VEL+c1∗r1∗PBEST-POS+c2∗r2∗GBEST-POS(33)ReLU=max⁡0,x=0,ifx≤0x,ifx>0.Figure 4
Activation function of ReLU.In detail,VEL is transformed by ReLU by the threshold of 0. Utilizing the operator of AND withGBEST in (34), outstanding episode truncated fromGBEST is preserved directly. Then corresponding position inPOS is substituted by the outstanding episode maintained inVEL with replacing operator of ⊕. After normalization ofPOS, a new position is updated in (35)(34)VEL=VELANDGBSET(35)POS=normalizeVEL⊕POS.Overall, an illustrative example of velocity updating for each particle can be depicted in Figure5.Figure 5
Example of velocity updating.


## 4.4. Repository Updating

RepositoryREP is the archive of good RR matrices in the representative form ofPOS. In order to maintain diversity and optimize distribution, our updating mechanism is based on hypervolume and crowd distance. Hypervolume is divided by hyperlimits and hypercube dynamically and adaptively according to the boundaries of each Pareto solution inREP. Each hypercube bounded by hyperlimits is assigned with hyperquality based on the number of particles inside.GBEST is selected by roulette wheel in the hypercube with higher hyperquality. When particles exceed the capacity of repository, extra particles with the smallest crowding distances, which are measured by (36), are removed and transferred to the mutation archiveARCfor the use of mutation(36)dXi=1n-1∑Y∈REP-XidimXi-Y2,where dim is the dimension of Xi and n denotes the number of particles inREP. In other words, crowding distance is a measure of average distance with all the other particles inREP.


## 4.5. Strategies for Mutation

To maintain diversity and enhance ability to escape from local optimum, two strategies for mutation are designed: fixed mutation percentage and guided-randomization as shown in Algorithm2.Algorithm 2:Mutation for discrete MOPSO.
Input: ARC and mutation percentage P Output: New particles. Step  1. Randomized mutation Select particles from ARC according to percentage P; Each selected particle is re-randomized; P ∗ d i m columns in each particle are replaced by newly generated columns which still satisfy constraints as in Algorithm1; Calculate fitness for each newly generated particle. Step  2. Guided mutation Select the remaining particles from ARC; Each particle is mutated by the guidance of GBEST; ( 1 - P ) ∗ d i m columns in each particle are replaced by corresponding columns in GBEST which still satisfy constraints as in Algorithm 1; Calculate fitness for each newly generated particle.


## 4.6. Boundaries Checking

Position of all particles are bounded byε-differential privacy when maxx=1,…,t⁡(maxx=1,…,tpxy/minx=1,…,tpxy)≤eε, which means that the maximum in each column is no more than eε times of the minimum. The tunable parameter of privacy budget ε is regulated to satisfy different users’ privacy-preserved requirements. In addition, mutation is performed in the phase of particle updating when certain position is out of the bound.


## 4.7. Termination Checking

Termination criterion for MOPSO can be set as follows:(1) limiting the maximum iteration number; (2) among certain number of consecutive generations, quality of repositoryREP does not improve. When termination criterion is met, the combination set of optimal RR matrices in Pareto dominance fromREP andARC is output as the final solution. In our work for termination, we combine both methods for the reason that either criterion can guarantee a diversified optimal solution set for different requirements and can benefit from the fast convergent feature of MOPSO.


## 4.8. Complexity Analysis

### 4.8.1. Space Complexity

In our scheme of discrete MOPSO, two RR matrices set, namely,REP andARC, are needed, both of which occupy complexity of O((Nr+Nm)∗dim2). Nr and Nm are the size ofREP andARC with particles’ dimension of dim. All particles need a complexity of O(Np∗dim2), where Np is the size of population. Thus, the total space complexity of discrete MOPSO for RR matrices is O((Np+Nm+Nr)∗dim2).


### 4.8.2. Time Complexity

The main time complexity is occupied by Pareto dominance check and repository updating in Algorithm1. For ease of representation, let n be the number of solution. The evaluation number is 2Cn2, namely, O(n2). Initialization inStep  1 needs O(Np∗n2) operations of Pareto dominance check. Repository updating inStep  2 occupies complexity of O(n2). Thus, the worst running time complexity of our scheme is O(max(Np,maxgen)∗n2), where maxgen is the iteration number.


## 4.8.1. Space Complexity

In our scheme of discrete MOPSO, two RR matrices set, namely,REP andARC, are needed, both of which occupy complexity of O((Nr+Nm)∗dim2). Nr and Nm are the size ofREP andARC with particles’ dimension of dim. All particles need a complexity of O(Np∗dim2), where Np is the size of population. Thus, the total space complexity of discrete MOPSO for RR matrices is O((Np+Nm+Nr)∗dim2).


## 4.8.2. Time Complexity

The main time complexity is occupied by Pareto dominance check and repository updating in Algorithm1. For ease of representation, let n be the number of solution. The evaluation number is 2Cn2, namely, O(n2). Initialization inStep  1 needs O(Np∗n2) operations of Pareto dominance check. Repository updating inStep  2 occupies complexity of O(n2). Thus, the worst running time complexity of our scheme is O(max(Np,maxgen)∗n2), where maxgen is the iteration number.


## 5. Experiments and Discussion

We conduct our experiments on two kinds of datasets: synthesis datasets and real datasets from UCI. Performance of our proposed discrete MOPSO is compared with Wanner, FRAPP, UP, and SPEA2 in [34]. Parameters of discrete MOPSO are shown in Table 2.Table 2
Parameters of our algorithm.
Notation Value Population sizeNp 100 Repository sizeNr 200 Mutation archive sizeNm 200 Maximum number of iterationsMaxgen 200 Mutation percentagep 1/3 Initial weightw 0.4 Cognitive coefficientsc1, c2 2 Number of grids inREP  Ngrid 20 hypercube_limits inREPwill change dynamically as with boundaries of particles.


### 5.1. Pareto Front

RR matrices that are generated from Warner, UP, and FRAPP have been proved to obtain the same Pareto front distribution [34]. Thus, for ease of illustration, we take FRAPP as a comparison. Synthesis datasets are generated in the following way: diagonal element of p in RR matrices is generated from [0,1] with the stride of 0.001. 999 RR matrices can be obtained. Random numbers are chosen from different distribution in a single-dimension set of 10000 records with 8 different categories. Nondominated solutions that are beyond differential privacy are deleted in advance. For different distributions, we set privacy budget ε=2. In addition, when privacy budget ε varies, the results are featured with similar trends. Six kinds of Pareto fronts of different RR schemes are presented in Figure 6. Corresponding statistics from boxplot are shown in Figure 7.Figure 6
Pareto front of different distribution with privacy budgetε=2.
(a)
Uniform distribution by linear standard uniform transformation (b)
Student’st distribution with 3 degrees of freedom (c)
Chi-square distribution with 8 degrees of freedom (d)
Binomial distribution (N=10000, p=0.3) (e)
Beta distribution (α=1, β=2) (f)
Gamma distribution (α=1, β=2)Figure 7
Boxplot of different distribution with privacy budgetε=2.
(a)
Uniform distribution by linear standard uniform transformation (b)
Student’st distribution with 3 degrees of freedom (c)
Chi-square distribution with 8 degrees of freedom (d)
Binomial distribution (N=10000, p=0.3) (e)
Beta distribution (α=1, β=2) (f)
Gamma distribution (α=1, β=2)In Figure6, we can conclude that metric of utility obtained by our approach can reach a wider range than FRAPP. Our solutions are almost in dominance of all those in FRAPP, which shows the better global optimization capability by discrete MOPSO. In terms of privacy, we can find more Pareto solutions for RR matrices than FRAPP. FRAPP just consider RR matrices by a single metric of accuracy, while our method can optimize two metrics of privacy and utility simultaneously.We take Gamma distribution in Figure6(f) as an example. Only 389 out of 999 RR matrices in FRAPP satisfy differential privacy when ε=2, while our approach has the ability to maintain a wider range of privacy and utility by adoptingREP andARC. Mutation and velocity updating operation enhance the searching ability especially in a wider range of privacy. On the other hand, it can be calculated that H(X) is 2.6741 and H(Y)=2.9358. Maximum of privacy falls within the scope of minimum of H(X) and H(Y) which can prove the conclusion in Section 3.3.1.In Figure7, it obviously shows that RR matrices optimized by our method have a much wider range of privacy and utility than FRAPP, especially in the metric of privacy by average mutual information. It can be summarized that lower distortion rate responds to better utility and better performance of privacy is in accordance with less average mutual information.


### 5.2. Privacy Budget

Privacy budget is the most important index of balancing the trade-off between privacy and utility. Under the bound of differential privacy thatmaxu=1,…,t(maxv=1,…,tpuv/minv=1,…,tpuv)≤eε, effect of different privacy budgets (ε=0,0.1,0.5,1,1.5,2) on the number of RR matrices is shown in Figure 8.Figure 8
Effect on number of RR matrices with differentε.
(a)
Normal distribution (b)
Gama distributionIn Figure8, the case of ε=0 means that each element in RR matrix is equal, which is the special condition of maximum privacy with minimum utility according to information-theoretic model. Notably, when ε=0,0.1,0.5,1, the size ofREP andARC is set to 200 and when ε=1.5, 2, the size is set to 400 for evaluating the further exploitative ability of our method in Figure 8(a). In Figure 8(b), where ε=0,0.1,0.5, size ofREP andARC is set to 200. It can be concluded that our method has a better performance on finding more RR matrices. As ε grows larger, FRAPP can find more RR matrices. However, our method is focused on a more diversified distribution of Pareto solution with much higher quality on the trade-off between privacy and utility. As with decrease in ε, privacy is strongly preserved. There is a sharp drop in the number of RR matrices obtained by FRAPP, while our method keeps almost stable due to the adoption ofREP andARC.


### 5.3. Case Study

We adopt two datasets from UCI:(1) car evaluation data set, including 1728 instances of 4 classes of uncc. (70.023%), acc. (22.222%), good (3.993%), and v. good (3.762%) with 6 attributes; (2) the game of Connect-4 opening database containing all legal 8-ply positions from 67557 instances and 42 attributes in 3 classes of win (65.83%), loss (24.62%), and draw (9.55%).In Figure9, under a strong bound of privacy budget ε=0.5, we can conclude that our method can obtain a wider range of Pareto front in terms of privacy and utility than FRAPP for car evaluation, especially in the metric of privacy. For Connect-4, both methods have nearly the same range and statistics in boxplot figure. Meanwhile, our approach can still gain better statistics in Pareto dominance of FRAPP as shown in Figures 9(a) and 9(c). In addition, when ε=2, we can estimate the best utility of original data distribution by the two methods. Our method has a better performance than FRAPP as to the metric of utility as illustrated in Figure 10.Figure 9
Pareto front and boxplot withε=0.5.
(a)
Pareto front of car evaluation (b)
Boxplot of car evaluation (c)
Pareto front of Connect-4 (d)
Boxplot of Connect-4Figure 10
Estimation of datasets withε=2.
(a)
Estimation of car evaluation (b)
Estimation of Connect-4In addition, to fully test our method, we compared it with OptRR [34] in the aspect of running time for obtaining 200 RR matrices inREP. Dimension of RR matrices, D, is set from 5 to 150. OptRR is developed from evolutionary multiobjective optimization method, namely, SPEA2. The experiment is conducted by Intel core i5-4590CPU@3.30 GHz, 4 GB RAM, and coded in matlab on Windows 7-64 bit. Results of running time are shown in Table 3.Table 3
Running time results (seconds).
Approach Dimension of RR matrices D = 5 D = 10 D = 20 D = 50 D = 100 D = 150 Ours 6.57 6.87 7.08 10.88 27.12 53.28 OptRR 20.79 67.83 140.73 301.35 697.26 1762.43The running time results are obtained from the mean value of 20 independent experiments in Table3. Our approach has a faster convergence rate than OptRR in finding optimal RR matrices, especially when dimension of RR matrices grows. Larger dimensions of RR matrices challenge computing capability as well as the optimization strategies in MOPSO and OptRR. The simple operators in our methods like AND and Replacement are beneficial in reducing complexity and,also, the advantage of MOPSO in fast convergence plays a key role in speeding up the searching process.


## 5.1. Pareto Front

RR matrices that are generated from Warner, UP, and FRAPP have been proved to obtain the same Pareto front distribution [34]. Thus, for ease of illustration, we take FRAPP as a comparison. Synthesis datasets are generated in the following way: diagonal element of p in RR matrices is generated from [0,1] with the stride of 0.001. 999 RR matrices can be obtained. Random numbers are chosen from different distribution in a single-dimension set of 10000 records with 8 different categories. Nondominated solutions that are beyond differential privacy are deleted in advance. For different distributions, we set privacy budget ε=2. In addition, when privacy budget ε varies, the results are featured with similar trends. Six kinds of Pareto fronts of different RR schemes are presented in Figure 6. Corresponding statistics from boxplot are shown in Figure 7.Figure 6
Pareto front of different distribution with privacy budgetε=2.
(a)
Uniform distribution by linear standard uniform transformation (b)
Student’st distribution with 3 degrees of freedom (c)
Chi-square distribution with 8 degrees of freedom (d)
Binomial distribution (N=10000, p=0.3) (e)
Beta distribution (α=1, β=2) (f)
Gamma distribution (α=1, β=2)Figure 7
Boxplot of different distribution with privacy budgetε=2.
(a)
Uniform distribution by linear standard uniform transformation (b)
Student’st distribution with 3 degrees of freedom (c)
Chi-square distribution with 8 degrees of freedom (d)
Binomial distribution (N=10000, p=0.3) (e)
Beta distribution (α=1, β=2) (f)
Gamma distribution (α=1, β=2)In Figure6, we can conclude that metric of utility obtained by our approach can reach a wider range than FRAPP. Our solutions are almost in dominance of all those in FRAPP, which shows the better global optimization capability by discrete MOPSO. In terms of privacy, we can find more Pareto solutions for RR matrices than FRAPP. FRAPP just consider RR matrices by a single metric of accuracy, while our method can optimize two metrics of privacy and utility simultaneously.We take Gamma distribution in Figure6(f) as an example. Only 389 out of 999 RR matrices in FRAPP satisfy differential privacy when ε=2, while our approach has the ability to maintain a wider range of privacy and utility by adoptingREP andARC. Mutation and velocity updating operation enhance the searching ability especially in a wider range of privacy. On the other hand, it can be calculated that H(X) is 2.6741 and H(Y)=2.9358. Maximum of privacy falls within the scope of minimum of H(X) and H(Y) which can prove the conclusion in Section 3.3.1.In Figure7, it obviously shows that RR matrices optimized by our method have a much wider range of privacy and utility than FRAPP, especially in the metric of privacy by average mutual information. It can be summarized that lower distortion rate responds to better utility and better performance of privacy is in accordance with less average mutual information.


## 5.2. Privacy Budget

Privacy budget is the most important index of balancing the trade-off between privacy and utility. Under the bound of differential privacy thatmaxu=1,…,t(maxv=1,…,tpuv/minv=1,…,tpuv)≤eε, effect of different privacy budgets (ε=0,0.1,0.5,1,1.5,2) on the number of RR matrices is shown in Figure 8.Figure 8
Effect on number of RR matrices with differentε.
(a)
Normal distribution (b)
Gama distributionIn Figure8, the case of ε=0 means that each element in RR matrix is equal, which is the special condition of maximum privacy with minimum utility according to information-theoretic model. Notably, when ε=0,0.1,0.5,1, the size ofREP andARC is set to 200 and when ε=1.5, 2, the size is set to 400 for evaluating the further exploitative ability of our method in Figure 8(a). In Figure 8(b), where ε=0,0.1,0.5, size ofREP andARC is set to 200. It can be concluded that our method has a better performance on finding more RR matrices. As ε grows larger, FRAPP can find more RR matrices. However, our method is focused on a more diversified distribution of Pareto solution with much higher quality on the trade-off between privacy and utility. As with decrease in ε, privacy is strongly preserved. There is a sharp drop in the number of RR matrices obtained by FRAPP, while our method keeps almost stable due to the adoption ofREP andARC.


## 5.3. Case Study

We adopt two datasets from UCI:(1) car evaluation data set, including 1728 instances of 4 classes of uncc. (70.023%), acc. (22.222%), good (3.993%), and v. good (3.762%) with 6 attributes; (2) the game of Connect-4 opening database containing all legal 8-ply positions from 67557 instances and 42 attributes in 3 classes of win (65.83%), loss (24.62%), and draw (9.55%).In Figure9, under a strong bound of privacy budget ε=0.5, we can conclude that our method can obtain a wider range of Pareto front in terms of privacy and utility than FRAPP for car evaluation, especially in the metric of privacy. For Connect-4, both methods have nearly the same range and statistics in boxplot figure. Meanwhile, our approach can still gain better statistics in Pareto dominance of FRAPP as shown in Figures 9(a) and 9(c). In addition, when ε=2, we can estimate the best utility of original data distribution by the two methods. Our method has a better performance than FRAPP as to the metric of utility as illustrated in Figure 10.Figure 9
Pareto front and boxplot withε=0.5.
(a)
Pareto front of car evaluation (b)
Boxplot of car evaluation (c)
Pareto front of Connect-4 (d)
Boxplot of Connect-4Figure 10
Estimation of datasets withε=2.
(a)
Estimation of car evaluation (b)
Estimation of Connect-4In addition, to fully test our method, we compared it with OptRR [34] in the aspect of running time for obtaining 200 RR matrices inREP. Dimension of RR matrices, D, is set from 5 to 150. OptRR is developed from evolutionary multiobjective optimization method, namely, SPEA2. The experiment is conducted by Intel core i5-4590CPU@3.30 GHz, 4 GB RAM, and coded in matlab on Windows 7-64 bit. Results of running time are shown in Table 3.Table 3
Running time results (seconds).
Approach Dimension of RR matrices D = 5 D = 10 D = 20 D = 50 D = 100 D = 150 Ours 6.57 6.87 7.08 10.88 27.12 53.28 OptRR 20.79 67.83 140.73 301.35 697.26 1762.43The running time results are obtained from the mean value of 20 independent experiments in Table3. Our approach has a faster convergence rate than OptRR in finding optimal RR matrices, especially when dimension of RR matrices grows. Larger dimensions of RR matrices challenge computing capability as well as the optimization strategies in MOPSO and OptRR. The simple operators in our methods like AND and Replacement are beneficial in reducing complexity and,also, the advantage of MOPSO in fast convergence plays a key role in speeding up the searching process.


## 6. Conclusion

In this paper, we formulate the information-theoretic model as to quantification for privacy and establish an open framework of privacy computing. In terms of optimizing RR matrices in information collection by randomized response, we derived metrics for privacy and utility, namely, average mutual information and average distortion rate. Furthermore, our proposed approach is the first solution to optimized RR matrices using discrete MOPSO under information-theoretic model. Our discrete MOPSO is proposed to solve the double-objective optimization problem under differential privacy. Two mutation strategies in extra mutation archive and velocity updating mechanism are successful in helping MOPSO escape from local optimum. The experimental results on synthesis datasets and real datasets from UCI show that our approach outperforms existing state-of-the-art works in the aspects of Pareto front, privacy budget, and data distribution reconstruction, especially excellent in privacy protection. Moreover, we hope to contribute our optimal Pareto solutions of extensive RR schemes to the public for the future study. Some extensive work can be applied to other domains of privacy computing.



---

*Source: 7846547-2018-04-03.xml*