On Privacy Protection of Latent Dirichlet Allocation Model Training

1 Introduction

Massive text data have arisen in the sustained and rapid development of Internet. Mining and analyzing of text data can help us gain a vast amount of knowledge, thus benefiting the whole society. As a fundamental model for text mining, Latent Dirichlet Allocation(LDA) [Blei et al., 2003] can be used for discovering the main features of the sparse text datasets by identifying their hidden semantic architecture. Particularly, LDA can map the high-dimensional text data to a lowdimensional topic space while retaining the implicit semantics, which has been an effective machine learning technique for clustering or classification. Many enterprises such as Yahoo [Smola and Narayanamurthy, 2010], Tencent [Wang et al., 2014][Yut et al., 2017], and Microsoft [Yuan et al., 2015] have all built LDA platforms for supporting big data analysis and training machine learning models on various text data.

Similar to other machine learning models, LDA may be trained on the datasets that contain some sensitive information of individuals and will inevitably memorize some knowledge about the datasets. Unfortunately, aiming at this characteristic, some attacks have been proposed to extract the private information of the training data from machine learning models. For example, membership inference attacks (MIA)[Shokri et al., 2017] can be launched to infer the membership information of an individual. Model inversion attacks [Fredrikson et al., 2014] have been proved to be able to extract training data from observed model predictions. Therefore, despite the popularity and effectiveness, the naive LDA model may also suffer from these attacks and lead to great privacy risks.

Differential privacy proposed by Dwork [Dwork et al., 2006] has been the de-facto standard of privacy protection with a rigorous mathematical proof. Due to its strong privacy guarantee, DP has also been exploited in many fields such as data publication [Ren et al., 2018][Li et al., 2019]and machine learning [Chaudhuri et al., 2011][Abadi et al., 2016]as well as LDA training [Park et al., 2016][Zhu et al., 2016]. For example, Park et al. [Park et al., 2016] proposed to obtain privacy guarantee for LDA models by perturbing the expected sufficient statistics in each iteration of the variational Bayesian method, which is a parameter estimation algorithm for LDA. Zhu et. al. [Zhu et al., 2016] presented a differentially private LDA algorithm by perturbing the sampling distribution in the collapsed Gibbs sampling(CGS) process, which is a typical training algorithm for LDA.

Both the above algorithms achieve DP by injecting extra noise to the training process of LDA regarding to centralized training datasets. However, as a typical sampling algorithm with inherent randomness, CGS possesses uncertainty in its execution and naturally provides some level of privacy guarantee, which has been indicated in [Wang et al., 2015][Foulds et al., 2016]. In particular, Wang et al. [Wang et al., 2015] proved that posterior sampling and the stochastic gradient Markov chain Monte Carlo techniques possess some inherent privacy guarantee. Foulds et al. [Foulds et al., 2016] further extended this conclusion to the general MCMC methods. Besides the inherent privacy, both existing algorithms consider the LDA model training on centralized datasets owned by a trustworthy data curator. Nevertheless, due to privacy concerns, individual data contributors may be reluctant to directly share their sensitive data but prefer to send the locally sanitized data to the model trainer.

Therefore, aiming to provide strong privacy guarantee for LDAmodel training, this paper not only investigates to utilize the inherent privacy of CGS in LDA training on centralized datasets, but also proposes a locally private version of LDA that can be trained on crowd-sourced datasets with local sanitations. The contributions are summarized as follows:

• We develop a privacy monitoring algorithm to measure the inherent privacy guarantee of CGS algorithm in LDA. In particular, we first define two different levels of privacy: document level and word level, and present the corresponding lower bound of privacy guarantee after a given number of iterations.
• We propose LP-LDA, a novel mechanism that supports training a LDA model on crowd-sourced datasets with local sanitation, which can provide the guarantee of local privacy for individual data contributors.
• We conduct experiments on several real-world datasets to demonstrate the effectiveness of our proposed algorithms. Particularly, experimental results show that our LP-LDA can achieve a high model training accuracy while providing sufficient local privacy guarantee.

The rest of paper is organized as follows. Section 2 reviews the preliminaries. Section 3 describes our algorithms in detail. The experiments are presented in Section 4. Finally, we conclude the paper in Section 5.

2 Preliminaries

2.1 LDA and Collapsed Gibbs Sampling

LDA model was first proposed by David Blei in 2003 for analyzing the implicit semantic architecture of a corpus. In LDA model, any document m in a corpus D can be described by different distributions on K latent topics, where each topic k can be represented by a distribution on all words. LDA assumes the generative process of the documents in the corpus D as follows:

1. for each topic k, draw a "topic-word" distribution φk on all words t from Dirichlet(β⃗1), where β is the hyperparameter for the Dirichlet priors and can be interpreted as the prior observation for the "topic-word" count.
2. for each document m, draw a "document-topic" distribution θm from Dirichlet(α⃗1), where α is a hyperparameter similar to β and represents the prior observation for the "document-topic" count.
3. for each word w in a document m, first draw a topic k from θm, and then draw a word t from φk.

The essence of training a LDA model is to estimate the parameters φk for a given corpus D.The collapsed Gibbs sampling is such an effective parameter estimation algorithm. It iterates over each word wi and samples new topic zi for wi based on this full conditional distribution

where ¬i denotes the whole words except word wi, ntk denotes the count of topic k assigned to word t and nkm denotes the count of topic k appeared in document m which are maintained in matrices N tk and N km respectively.

After multiple rounds of sampling over the whole corpus, the topic sample of each word can be obtained. And the parameter φk can be estimated by its posterior expectation.

The detailed procedures of CGS can be referred to [Heinrich, 2005].

2.2 Differential Privacy

Differential privacy proposed by Dwork [Dwork et al., 2006] has been the de-facto standard of privacy protection with a rigorous mathematical proof. The rationale of DP guarantee is that negligible information can be gained by manipulating the output of a query on neighboring datasets.

Definition 1. [Dwork et al., 2006] (Differential Privacy) A randomized mechanism M : D → Y is ε-differential private if for any neighboring datasets D,D′ that satisfying |D∆D′ | = 1 and any output S ⊆ Y :

2.3 Local Privacy

Differential privacy implicitly assumes a centralized dataset owned by a trustworthy curator and does not ensure the privacy guarantee for individual data contributors. Recently, local (differential) privacy has been proposed to provide data sanitization at the individual users' side instead of the central server side.

Definition 2. [Dwork et al., 2014](Local Privacy) A randomized function f satisfies ε-local privacy if and only if for any two input tuples t and t′ in the domain of f, and for any output t∗ of f, there is:

3 Our Approach

In this section, we first investigate the inherent privacy of CGS process in LDA for a non-sanitized dataset owned by a trustworthy curator. Then, as a complement to the privacy guarantee of the data acquisition period, a locally private mechanism LP-LDA is presented to realize LDA model training on a sanitized dataset by local users.

3.1 PrivacyMonitoring Algorithm

Inherent Privacy of CGS

Generally, DP is achieved on most machine learning algorithms by introducing extra noise or randomness, which will inevitably cause a utility loss of the trained model. However, it has been shown in [Foulds et al., 2016] that some degree of inherent DP can be obtained on Gibbs sampling algorithm for free. This is because each sampling process in Gibbs sampling works in a way the same as an exponential mechanism, which is a classic method to achieve DP. Obviously, as one version of Gibbs sampling, Collapsed Gibbs Sampling naturally inherits this property. Furthermore, such a property can also provide privacy for free in the CGS-based LDA training process. Therefore, aiming to utilize the inherent privacy, we develop a privacy monitoring algorithm to quantify the privacy guarantee of CGS in the LDA training process. In particular, the rationale behind the privacy monitoring algorithm is to find an adequate exponential mechanism for each sampling process in CGS and then accumulate the total privacy guarantee of all exponential mechanisms according to the composition theorem of DP.

Document-level Privacy and Word-level Privacy

This paper considers to provide DP for the individual words and documents in the training corpus for LDA, respectively.

Word-level privacy: Let D = {w1,w2, ...wW} denote a corpus with |D| = W words wi (i = 1, 2, ...,W). Then, its neighboring dataset D′ satisfying |D∆D′ | = 1 differs from D by a single word w. Word-level privacy prevents membership inference of individual words of the training corpus from the trained LDA model.

Document-level privacy: Let D = {m1,m2, ...mM} denote a corpus with |D| = M documents mi (i = 1, 2, ..., M). Then, its neighboring dataset D′ satisfying |D∆D′ | = 1 differs from D by a single document m. In order to bound the sensitivity, we assume that a single document includes at most Nmax words. Document-level privacy prevents reidentification of individual documents in the training dataset of LDA, which may be contributed by and associated with individual users.

Inherent Privacy in Each Sampling

To begin with, we show the essence of the intrinsic privacy guarantee in each sampling of CGS in terms of exponential mechanism. Consider the sampling process for word wi in the nth iteration. Suppose its sampling distribution on K topics is given by P = (p1, p2, ..., pK)⊤, where pk denotes the probability that topic k is assigned to wi in this sampling. Then we can rewrite pk as

which could be understood as an output probability of an exponential mechanism ME(wi, u,K) that selects the topic k ∈ K with probability of pk. The utility function of ME(wi, u,K) is u(wi, k) = lnpk and its sensitivity is ∆lnpk. Obviously, ε = 2∆lnpk is the intrinsic privacy guarantee of the exponential mechanism ME(wi, u, K).

Privacy Monitoring for Each Sampling

Unfortunately, it's intractable to specify an exact value of 2∆lnpk in the execution process of CGS algorithm in LDA due to the complicated architecture of training corpus, hence we attempt to find an upper bound of 2∆ ln pk to quantify the privacy guarantee ε.

According to Equation (1), the sampling distribution P for word wi = t in D in the n-th iteration could be computed by

Suppose that P′ = (p′1 , p′2 , ..., p′K )⊤ is the corresponding distribution on D′ , which is the neighboring dataset of D, then

where Nk denotes the count of topic k assigned in the D-D′ where k ∈ {1, 2, ...,K}. We refer to {N1,N2, ...,Nk} as a topic partition on D - D′ and ∑ Nk = |D - D′ |.

Given a topic partition γ = {N1,N2, ...,Nk}, the privacy guarantee in this sampling process could be measured by

where ξk denotes the sensitivity of lnpk. However, there are (N+K-1 K-1 ) partitions in total. So, it is computational prohibitive to find the maximal εγ among all partitions. In the following, we consider how to reduce the searching space of partitions.

For simplicity, we first consider a special case, in which there exists some topic i with Ni = 0 in a given partition.

Theorem 1. Suppose that there exists some Nk = 0 in a given partition γ = {N1, N2, ..., NK}, then the privacy guarantee

if and only if for any j ̸= k

Proof. Appendix A of full version [Zhao et al., 2019].

Corollary 1. Suppose that there exists a topic set T = {k, ..., j} with {Nj ̸= 0, ∀j ∈ T } in a given partition γ, and it holds that

for some k ∈ T , then the privacy guarantee

Proof. This proof follows from the result of Theorem 1.

Theorem 1 and corollary 1 illustrate a special case to find the privacy εγ. The following lemma and theorem further demonstrate that among all the partitions, the one with the largest privacy guarantee belongs to a partitions set P = {γ|∃k, s.t. Nk = N, Nj = 0, ∀j ̸= k}.

Lemma 1. There exists a partition γ ∗ in P such that

where Γ denotes the set consisting of all the partitions.

Proof. Appendix B of full version [Zhao et al., 2019].

Algorithm 1 Privacy Monitoring for Each Sampling

Input: word count matrices N tk and N km, N = |D - D′ | (D = 1 for word-level privacy or D = Nmax for documentlevel privacy)

Parameter: hyper parameters α, β

Output: privacy guarantee ε

• 1: compute the sampling distribution P with pk ∝ rk = ntk+β ∑Vt=1 (ntk+β) · nkm+α ∑Kk=1 (nkm+α)
• 2: compute pseudo sampling distribution q with qk = ntk+β ∑Vt=1 (ntk+β)-N · nkm+α ∑Kk=1 (nkm+α)
• 3: for each component qk of q do
• 4: compute ξk = ln( ∑k r′k ∑k rk · rk qk )
• 5: end for
• 6: find index k such that |rk - qk| = ‖r - q‖∞
• 7: compute ξ = ln( ∑j̸=k rj+qk ∑j rj ) with qk
• 8: return ε = 2max{ξ1, ξ2, ..., ξK, ξ}

Definition 3. (Pseudo sampling distribution) Suppose that given a vector q with length K, each component

Then q is the pseudo sampling distribution in this sampling.

Theorem 2. Among all the partitions, there must exist a partition γ ′ inP = {γ|∃k, s.tNk = N, Nj = 0, ∀j ̸= k}

such that

if condition (4) holds. k is the topic index such that |rk - qk| = ‖r - q‖∞, q is the pseudo sampling distribution.

Proof. Appendix C of full version [Zhao et al., 2019].

Theorem 2 indicates that only the partitions in P need to be considered for computing the privacy ε in the each sampling processing, which greatly reduce the searching scope. In particular, if condition (4) holds for all partitions in P, the privacy guarantee could be computed directly by Equation (8), which is the first case to consider. If not, for any partition γ in P not satisfying condition (4), the privacy guarantee could be computed by Equation (5). Due to the arbitrariness of γ, we have another K cases to consider since there are K partitions in P. Furthermore, since whether condition (4) holds is unknown, we have to enumerate all these K+1 cases to find the privacy guarantee bound. Algorithm 1 presents the searchingbased algorithm for monitoring the privacy guarantee of each sampling for each word.

Privacy Monitoring for LDA

So far, the privacy guarantee εiw of the sampling process for word w in the ith iteration can be measured by Algorithm 1.

Algorithm 2 Privacy Monitoring for CGS in LDA

Input: document corpus D

Parameter: iteration number n

Output:privacy guarantee ε

• 1: while not finished do
• 2: for each document m in D do
• 3: for each word w in m do
• 4: compute the sampling distribution p
• 5: call algorithm 1 to compute εiw
• 6: sample a topic and update matrices Ntk and Nkm
• 7: end for
• 8: end for
• 9: end while
• 10: return maxw{∑ni=1 εiw }

Since the sampling process of the whole CGS algorithm is iteratively performed for each word but alternatively among all the words in the corpus, the total privacy guarantee of the whole CGS process in LDA training could be computed according to the composition theorems of DP.

Theorem 3. Given a corpus D, suppose the CGS algorithm performed on word w at the i-th iteration satisfies εiw -DP, then after n iterations, the whole CGS algorithm performed on D satisfies maxw{∑ni=1 εiw }-DP.

Proof. For any word w, after n iterations of sampling, it will be accessed to by the whole CGS process n times, according to the sequential composition theorem [Li et al., 2016], the total privacy guarantee for word w in the CGS algorithm is εw = ∑ni=1 εiw . While, according to the Equation (1), each iteration of CGS in LDA only accesses to each word once to perform the sampling, then according to the parallel composition theorem [Li et al., 2016], the total privacy guarantee for the copus(all words) should be the maximum privacy guarantee of CGS among all words, that is maxw{∑ni=1 εiw }.

Based on this observation, Algorithm 2 shows the privacy monitoring algorithm for the whole CGS process in LDA.

3.2 LP-LDA

As analyzed above, CGS algorithm can intrinsically guarantee the privacy of individual documents for the LDA model trained on a plain-text dataset, which is owned by a trustworthy curator. However, in many distributed applications, data servers are not always privacy-reliable and data owners may not be willing to directly contribute their sensitive data. In this case, we further propose a hidden-data based LDA mechanism LP-LDA that can perform the training process on a sanitized dataset. In particular, the LP-LDA mechanism mainly consists of two components: local perturbation at the user side and training on reconstructed dataset at the server side.

Local Perturbation

The local perturbation at the user side includes the following steps:

• Step 1. Each document m is encoded as a binary vector Vm, in which each bit Vm[j] represents the presence of the j-th word in the word bag of the corpus.

• Step 2. Each bit Vm[j] of the binary vector Vm is then randomly flipped according to the following randomized response rule:

where f ∈ [0, 1] is a parameter that specifies the randomness of flipping and adjusts the local privacy level.

• Step 3. Then the noisy binary vector ˆVm[j] is sent to the central server by each user. Obviously, ˆVm[j] is locally sanitized without concerning user's privacy.

Training on Reconstructed Dataset

After receiving the flipped binary vectors from a large number of data contributors, the central server can aggregate the vectors, reconstruct the dataset and then perform training on the reconstructed dataset. The rationale behind this is that the training result of topic-word distribution is insensitive to the document partitions and only depends on the total word counts in the corpus.

• Step 1. For each bit in the noisy binary vectors, the server counts the number of 1′ s as nt = ∑Mi=1 ˆVm[t].
• Step 2. The server then estimates the true count Nt of each bit in the original binary vectors Vm as ˆNt = (2nt - fM)/2(1 - f ).
• Step 3. For each bit, the server first computes the difference δt = ˆNt -nt.
• Step 4. For each bit t, if δt > 0, the server randomly samples δt binary vectors with the t-th bit as 0 and sets the t-th bit as 1; if δt < 0, then the server randomly samples |δt| binary vectors with the t-th bit as 1 and sets the t-th bit as 0; otherwise, keeps the noisy bit vectors as received.
• Step 5. Based on the noisy bit vectors, the server reconstructs a dataset and performs the CGS process on it.

Privacy Analysis of LP-LDA

Theorem 4. The LP-LDA satisfies ε-differential privacy for each document contributor where ε = ln 1-f/2 f/2 .

Proof. Suppose a word t appears in a noisy bit vector, then the probability of it being kept from the original bit vector is Pr( ˆVm[t] = 1|Vm[t] = 1) = 1 - f/2 and the probability of it being flipped from the original bit vector is Pr( ˆVm[t] = 1|Vm[t] = 0) = f/2. Then, according to the definition of DP, it guarantees the privacy of

The analysis also holds for any bit t that ˆVm[t] = 0.

Since the reconstruction and training process are essentially post-processes on the noisy bit vectors, the local privacy remains unchanged for all the documents.

Utility Analysis of LP-LDA

Theorem 5. Let Nt and nt denote the counts of word t in the original and perturbed datasets, respectively, then

is an unbiased estimator of Nt with the variance of

Proof. See proof in full version [Zhao et al., 2019].

4 Experiment

In this section, we evaluate the effectiveness of our proposed privacy monitoring algorithm and locally private LDA algorithm LP-LDA on real-world datasets.

The datasets used in our experiment are: KOS 1 : contains 3430 blog entries from dailykos website. NIPS 2 : contains 1740 research papers from NIPS conference. Enron 3 : contains 0.5 million email messages from about 150 users.

We extracted part of these datasets as our training datasets and the rest as the testsets. For simplicity, we setup a preprocessing phase on these dataset before running our experiments. For example, all stop words were removed and 1000 most frequent words in each dataset were chosen as the corresponding vocabulary list. Details about these datasets after pre-processing can be found in Table 1.

In our experiments, for all datasets, the topic number is set as 50, the maximum iteration number of CGS process in LDAmodel training is set as 300, which is sufficient for convergence on all three datasets. The hyper parameters α and β are set as 0.1, 0.01, respectively.

4.1 Inherent Privacy of CGS in LDA

• (a) Document-level privacy

Figure 1: privacy guarantee vs. iteration number of CGS in LDA

1 http://archive.ics.uci.edu/ml/

2 http://nips.djvuzone.org/txt.html

3 www.cs.cmu.edu/ enron

Figure 1 illustrates the inherent privacy guarantee of CGS algorithm in LDA measured by our proposed privacy monitoring algorithm on three datasets for both document-level and word-level privacy. It should be noted that a larger privacy parameter ε in the figures means less privacy guarantee.

As we can see in both subfigures, both word-level and document-level privacy parameter ε of CGS in LDA increase approximately linearly with the number of sampling iterations. This is because the privacy bound in each iteration of sampling is very close, and the total privacy parameter will accumulate with the number of iterations according to the sequential composition theorem.

Although CGS on all datasets can obtain privacy guarantee for free, the inherent privacy varies on different datasets. For document level, the privacy guarantee achieved on NIPS is the weakest while that on Enron is the strongest. That is because the documents in NIPS averagely contain the most words, which also means it is the most difficult to be effectively hidden. For word-level privacy, the LDAmodel trained on NIPS has the strongest privacy guarantee because it contains largest number of words and the sampling probability for each unique word will be the lowest. On the contrary, with the fixed length of vocabulary list, KOS contains the fewest words in total and results the weakest word-level privacy after same number of iteration.

4.2 Local Mechanism

Figure 2 depicts the simulation performance of our proposed LP-LDA mechanism in terms of different level of privacy. The flipping probability f in LP-LDA varies from 0.5 to 0.001, and the corresponding privacy level varies from 1.089 to 7.6004. The utility of LDA model training is measured by the perplexity on test sets. Perplexity is an informationtheoretical measure commonly used to evaluate the prediction performance of LDA model and generally smaller perplexity on a test set means better prediction accuracy. In particular, we compared LP-LDA with a baseline privacy-preserving LDA mechanism based on Laplace mechanism, in which the sufficient statistics of the likelihood, i.e., word count matrices N tk and N km are privatized at the beginning of the CGS algorithm with the sensitivity of 1 and privacy of ε [Foulds et al., 2016].

As shown, both the perplexity of LP-LDA and baseline algorithm decrease with the increase of ε, which shows the trade-off between the privacy and utility. For stronger privacy regime with smaller ε, the perplexity of LP-LDA is larger than that of the baseline algorithm. That is because the Laplace mechanism baseline algorithm incurs less noise than randomized response in LP-LDA for the statistics of word count Nt. While for weaker privacy regime with larger ε, the perplexity of LP-LDA is far less than that of the baseline algorithm and shows greater LDA model training utility. These utility comparison results can be also explained by the variance difference of the word count Nt in two mechanisms. In baseline mechanism based on Laplace noise, the noise variance is D(N ′ t ) = 2K2 /ε2 , while the variance D( ˆNt) in our proposed LP-LDA is shown in Equation (10). In particular, for larger ε on all three datasets, the baseline method always has a higher noise variance than LP-LDA.

5 Conclusion and FutureWork

In this work, we investigate the privacy protection of LDA model training. We first present that the CGS algorithm in LDA can possess some inherent privacy in each sampling process and then propose a efficient searching-based privacy monitoring algorithm to identify the privacy guarantee bound in the iterative CGS process of LDA. In addition, besides training on a trustworthy data server, we also propose a locally private solution of LP-LDA to achieve LDA training on a sanitized dataset by individual local users, which is applicable to many scenarios. The experiments on real-world datasets validate our proposed approaches. Future work will center on finding tighter bound of the inherent privacy guarantee in LDAmodel training.

Acknowledgments

This work is supported by National Natural Science Foundation of China under Grant 61572398, Grant 61772410, Grant 61802298, Grant 11690011 and Grant U1811461, in part by the Fundamental Research Funds for the Central Universities under Grant xjj2018237, in part by the China Postdoctoral Science Foundation under Grant 2017M623177, and in part by the National Key Research and Development Program of China under Grant 2017YFB1010004.