This talk presents a formal approach to carrying out privacy preserving text perturbation using a variant of Diferential Privacy ( DP) known as Metric DP (mDP). Our approach applies carefully calibrated noise to vector representation of words in a high dimension space as defined by word embedding models. We present a privacy proof that satisfies mDP where the privacy parameter ε provides guarantees with respect to a distance metric defined by the word embedding space. We demonstrate how ε can be selected by analyzing plausible deniability statistics backed up by large scale analysis on GloVe and fastText embeddings. We also conduct experiments on well-known datasets to demonstrate the tradeof between privacy and utility for varying values of ε on diferent task types. Our results provide insights into carrying out practical privatization on text-based applications for a broad range of tasks.
• Security and privacy → Privacy protections;
Over the last decade, Diferential Privacy ( DP) [
Since our application involves privatizing individual sentences submitted by each user, Local DP (LDP) would be the ideal privacy model to consider. However, LDP has a requirement that renders it impractical for our application: it requires that the secret sentence xs has a non-negligible probability of being transformed into any other sentence xˆs , no matter how unrelated xs and xˆs are. Unfortunately, this constraint makes it virtually impossible to enforce that the semantics of xs are approximately captured by the privatized sentence xˆs , since the space of sentences is exponentially large in the length |xs |, and the number of sentences semantically related to xs will have vanishingly small probability under LDP.
To address this limitation we adopt metric DP (mDP) [
Formally, mDP is defined for mechanisms whose inputs come from a set X equipped with a distance function d : X × X → R+ satisfying the axioms of a metric (i.e. identity of indiscernibles, symmetry and triangle inequality). The definition of mDP depends on the particular distance function d being used and it is parametrized by a privacy parameter ε > 0. We say that a randomized mechanism M : X → Y satisfies ε-mDP if for any x, x ′ ∈ X the distributions over outputs of M(x ) and M(x ′) satisfy the following bound: for all y ∈ Y we have
Pr[M(x ) = y] ≤ eεd(x,x′) . (1)
Pr[M(x ′) = y]
We note that mDP exhibits the same desirable properties of DP (e.g.
composition, post-processing, robustness against side knowledge,
etc.), but we shall not be using these properties explicitly in our
analysis; we refer the reader to [
The type of probabilistic guarantee described by (1) is characteristic of DP: it says that the log-likelihood ratio of observing any particular output y given two possible inputs x and x ′ is bounded by εd(x, x ′). The key diference between mDP and local DP is that the latter corresponds to a particular instance of the former when the distance function is given by d(x, x ′) = 1 for every x , x ′. Unfortunately, this Hamming metric does not provide a way to classify some pairs of points in X as being closer than others. This indicates that local DP implies a strong notion of indistinguishability of the input, thus providing very strong privacy by “remembering almost nothing” about the input. In contrast, metric DP is less restrictive and allows the indistinguishability of the output distributions to be scaled by the distance between the respective inputs. In particular, the further away a pair of inputs are, the more distinguishable the output distributions can be, thus allowing these distributions to remember more about their inputs than under the strictly stronger definition of local DP.
A point of consideration for mDP is that the meaning of the privacy parameter ε changes if one considers diferent metrics, and is in general incomparable with the ε parameter used in standard (local) DP. Thus, in order to understand the privacy consequences of a given ε in mDP one needs to understand the structure of the underlying metric d. 2
Our privacy mechanism is described over the metric space induced by word embeddings as follows: Algorithm 1: Privacy Preserving Mechanism
Input: string x = w1w2 · · · wℓ , privacy parameter ε > 0 for i ∈ {1, . . . , ℓ } do
Compute embedding ϕi = ϕ(wi ) Perturb embedding to obtain ϕˆi = ϕi + N with noise density pN (z) ∝ exp(−ε ∥z ∥) ˆ Obtain perturbed word wˆ i = ar дminu∈W ∥ϕ(u) − ϕi ∥
Insert wˆ i in ith position of xˆ release xˆ 3
We now present a methodology for calibrating the ε parameter of our mDP mechanism M based on the geometric structure of the word embedding ϕ used to define the metric d. Our strategy boils down to identifying a small number of statistics associated with the output distributions of M, and finding a range of parameters ε where these statistics behave as one would expect from a mechanism providing a prescribed level of plausible deniability. We recall that the main reason this is necessary, and why the usual rules of thumb for calibrating ε in traditional (i.e. non-metric) DP cannot be applied here, is because the meaning of ε in mDP depends on the particular metric being used and is not transferable across metrics. We start by making some qualitative observations about how ε afects the behavior of mechanism M. For the sake of simplicity we focus the discussion on the case where x is a single word x = w, but all our observations can be directly generalized to the case |x | > 1. We note these observations are essentially heuristic, although it is not hard to turn them into precise mathematical statements.
A key diference between LDP and mDP is that the former provides a stronger form of plausible deniability by insisting that almost every outcome is possible when a word is perturbed, while the later only requires that we give enough probability mass to words close to the original one to ensure that the output does not reveal what the original word was, although it still releases information about the neighborhood where the original word was.
More formally, the statistics we look at are the probability Nw = Pr[M(w) = w] of not modifying the input word w, and the (efective) support of the output distribution Sw (i.e. number of possible output words) for an input w. In particular, given a small probability parameter η > 0, we define Sw as the size of the smallest set of words that accumulates probability at least 1 − η on input w:
Sw = min |{S ⊆ X : Pr[M(w) < S] ≤ η}| .
Intuitively, a setting of ε providing plausible deniability should have Nw small and Sw large for (almost) all words in w ∈ W.
These statistics can also be related to the two extremes of the Rényi entropy [10], thus providing an additional information-theoretic justification for the settings of ε that provide plausible deniability in terms of large entropy. Recall that for a distribution p over W with pw = PrW ∼p [W = w], the Rényi entropy of order α ≥ 0 is given by
Hα (p) =
1 1 − α log Õ w ∈W α pw ! .
The Hartley entropy H0 is the special case of Rényi entropy with α = 0. It depends on vocabulary size |W | and is therefore a best-case scenario as it represents the perfect privacy scenario for a user as the number of words grow. It is given by H0 = log2 |W |. Min-entropy H∞ is the special case with α = ∞ which is a worstcase scenario because it depends on the adversary attaching the highest probability to a specific word p(w). It is given by H∞ = − log2 max (p(w)).
w ∈W
This implies that we can see the quantities Sw and Nw as proxies for the two extreme Rényi entropies through the approximate identities H0(M(w)) ≈ log Sw and H∞(M(w)) ≈ log 1/Nw , where the last approximation relies on the fact that (at least for small enough ε), w should be the most likely word under the distribution of M(w). 4
A word embedding ϕ : W → Rn maps each word in some vocabulary to a vector of real numbers.
The geometry of the resulting embedding model has a direct
impact on defining the output distribution of our redaction
mechanism. To get an intuition for the structure of these metric spaces –
i.e., how words cluster together and the distances between words
and their neighbors – we ran several analytical experiments on two
widely available word embedding models: GloVe [9] and fastText
[
GloVe word embeddings
GloVe embeddings at k = 10 101 102
K (log scale) fastText word embeddings 0.4 0.6 0.8 1.0
1.2 fastText embeddings at k = 10 5th percentile 20th percentile 50th percentile 80th percentile 95th percentile
103 5th percentile 20th percentile 50th percentile 80th percentile 95th percentile 103
Our experiments provide: (i) insights into the distance d(x, x ′) that controls the privacy guarantees of our mechanism for diferent embedding models; and (ii) empirical evaluation of the plausible deniability statistics Sw and Nw for the mechanisms obtained using diferent embeddings.
Our analysis gives a reasonable approach to selecting ε by means of the proxies provided by the plausible deniability statistics. In general, tuning privacy parameters in (metric) diferential privacy is still a topic under active research, especially with respect to what ε means for diferent applications. Task owners ultimately need to determine what is best for their users based on the available descriptive statistics.
10000 se 900 lvau 800 .vSgw 760000 ae 500 loV 400 G 3000
In Fig. 3, we present the average values of Sw and Nw statistics for GloVe and fastText. We observe that similar values over fastText cover a broader range of ε values when compared to GloVe. However, the average values are not suficient to make a conclusive comparison between embedding models. The shape of the distribution needs to be further considered when selecting ε for similar values of Nw or Sw . For example, the average value of Sw for GloVe at ε = 29 is about the same as that for fastText at ε = 33 (both have an average Sw value of ≈ 750). However, from Fig. 4, we discover that they both have slightly diferent distributions with GloVe being slightly flatter and fastText more skewed to the right. Similar results for matching average values of Nw for GloVe at ε = 29 and fastText at ε = 36 are also presented in Fig. 4.
105 GloVe at ε = 29; avg. Sw ≈ 750
105 fastText at ε = 33; a g. Sw ≈ 750 200 400 600 800
Num. of di tinct word (of 1000) 105 GloVe at ε = 29; avg. Nw ≈ 136 1000
200 400 600 800
Num. of distinct words (of 1000) 105 fastText at ε = 36; avg. Nw ≈ 136 1000 104 t103 n ouC102 101 1000 104 t103 n ouC102 101 1000 104 t103 n ouC102 101 1000 104 t103 n ouC102 101 1000
In this section, we highlight the results of empirical Sw and Nw plausible deniability statistics for 300 dimension fastText and 50 dimension GloVe embeddings. The results were designed to yield comparable numbers to those presented for 300 dimension GloVe embeddings.
Dr. Oluwaseyi Feyisetan is an Applied Scientist at Amazon Alexa where he works on Diferential Privacy and Privacy Auditing mechanisms within the context of Natural Language Processing. He holds 2 pending patents with Amazon on preserving privacy in NLP systems. He completed his PhD at the University of Southampton in the UK and has published in top tier conferences and journals on crowdsourcing, homomorphic encryption, and privacy in the context of Active Learning and NLP. He has served as a reviewer at top NLP conferences including ACL and EMNLP. He is the lead organizer of the Workshop on Privacy and Natural Language Processing (PrivateNLP) at WSDM with an upcoming event scheduled for EMNLP. Prior to working at Amazon in the US, he spent 7 years in the UK where he worked at diferent startups and institutions focusing on regulatory compliance, machine learning and NLP within the finance sector, most recently, at the Bank of America.
200 400 600 800 1000 Count of M(w) = w (of 1000) 0 Nw results at ε = 5
Nw results at ε = 7
Nw results at ε = 9
Nw results at ε = 11 0 200 400 600 800 1000 Num. of distinct words (of 1000) 0 200 400 600 800 1000 Num. of distinct words (of 1000)
200 400 600 800 1000 Count of M(w) = w (of 1000) 0 0 0 0 ouC102 100 104 ouC102 100 104 ouC102 100 104 ouC102 100 104 102 100 104 102 100 104 102 100 104 102 100 Sw results at ε = 18 104 102 100 104 102 100 104 102 100 104 102 100 104 102 100 104 102 100 104 102 100 104 102 100 104 102 100 104 102 100 ing noise to sensitivity in private data analysis. In TCC. Springer, 265–284. and Utility-Preserving Textual Analysis via Calibrated Multivariate Perturbations.