On a Utilitarian Approach to Privacy Preserving Text Generation (2021)

Abstract: Differentially-private mechanisms for text generation typically add carefully calibrated noise to input words and use the nearest neighbor to the noised input as the output word. When the noise is small in magnitude, these mechanisms are susceptible to reconstruction of the original sensitive text. This is because the nearest neighbor to the noised input is likely to be the original input. To mitigate this empirical privacy risk, we propose a novel class of differentially private mechanisms that parameterizes the nearest neighbor selection criterion in traditional mechanisms. Motivated by Vickrey auction, where only the second highest price is revealed and the highest price is kept private, we balance the choice between the first and the second nearest neighbors in the proposed class of mechanisms using a tuning parameter. This parameter is selected by empirically solving a constrained optimization problem for maximizing utility, while maintaining the desired privacy guarantees. We argue that this empirical measurement framework can be used to align different mechanisms along a common benchmark for their privacy-utility tradeoff, particularly when different distance metrics are used to calibrate the amount of noise added. Our experiments on real text classification datasets show up to 50% improvement in utility compared to the existing state-of-the-art with the same empirical privacy guarantee.

## introduction over the past decade, privacy-preserving machine learning has emerged as a hot topic in a variety of real world speech and language applications. in natural language processing (nlp), ensuring data privacy in machine learning tasks is especially challenging because text data tends to be rich in sensitive and potentially identifiable information about the users that contributed to these datasets. the literature is replete with approaches proposed for privacy-preserving text analysis, such as replacing sensitive information with general terms @xcite @xcite , injecting additional words into original texts @xcite @xcite , as well as k-anonymity and its variants @xcite @xcite . however, these methods are provably non-private and have been shown to be vulnerable to re-identification attacks @xcite . to ensure a quantifiable privacy guarantee, differential privacy (dp) has become the de facto standard for privacy-preserving statistical analysis @xcite @xcite , with applications to text analysis. at a high level, a randomized algorithm is differentially private if the output distributions from any two neighboring databases are (near) indistinguishable. this indistinguishability is controlled by a privacy parameter, which, in the case of text analysis, is often scaled by the distance between neighboring datasets to capture the semantic similarity between different words @xcite @xcite . this calibration enables the mechanisms to enjoy metric-dp @xcite , which was first introduced as a generalization of local dp @xcite for protecting location privacy. observe that a direct application of local dp mechanisms will be too restrictive because it requires that the probability ratio between the output distributions of any two words in the vocabulary be bounded by some fixed constant. due to the high dimensional nature of textual tasks and very large vocabulary sizes (e.g. 2.2m words for glove common crawl @xcite ), this can lead to adding a lot of noise for achieving the desired privacy guarantees, severely impacting the utility of the nlp task. comparing metric-dp mechanisms. in the context of text analysis, we are given a vocabulary set w and an embedding function φ : @xmath0, where p is the dimensionality of the embedding model. for @xmath1, a mechanism m : @xmath2: r p × r @xmath3, ∞) if for any w, w , ŵ ∈ w, the following holds: the probabilistic guarantee in (1) ensures that the log probability ratio of observing any output ŵ given two inputs w and w is bounded by d{φ(w), φ(w )}. this makes metric-dp less restrictive in that the indistinguishability of the output distributions is scaled by the distance between the inputs. if d{φ(w), φ(w )} = 1(@xmath4, then metric-dp reduces to standard dp. note that while metric-dp allows for a flexible privacy budget calibrated by not only but also the distance metric, this flexibility makes it harder to interpret the privacy parameter . for example, in standard dp, = 30 essentially means negligible privacy guarantee since e 30 is an astronomically large probability ratio; however, = 30 is common in the metric-dp literature @xcite @xcite and still provides meaningful privacy guarantees. this is because the pairwise distance in the word embedding space can be small floating numbers, which brings exp (30d{φ(w), φ(w )}) to a reasonable scale. thus, alone cannot fully characterize the privacy guarantee without the knowledge of the underlying metric space. more importantly, this indicates that the privacy guarantees from dp mechanisms with respect to different metrics are not directly comparable using only their values. ## the class of vickrey mechanisms to motivate our construction of the vickrey mechanisms, we begin by discussing the limitations of a general approach in the existing metric dp text generation mechanisms. we denote by @xmath5, . . . , w n } the vocabulary set containing n distinct words, and by φ : @xmath6. a common first step is to sample an additive noise z from a density function p(z) ∝ exp{-d(z, 0)}, where d is the distance metric used in the mechanism foot_1 . for example, the laplace mechanism uses d(x, y) = x -y 2 (also known as euclidean or l 2 distance), and the mahalanobis mechanism uses d(x, y) = (x -y)σ -1 (x -y) (also known as mahalanobis distance), where σ is the sample covariance of the word embeddings. once the noise is sampled, it is then added to the input word embedding and the word with an embedding that is nearest to this noised embedding is chosen as the output: a limitation of this noisy nearest neighbor selection is that when |z| is small (in particular, smaller than half the distance from the input word to its nearest neighbor), the first nearest neighbor to the noised embedding is the same as the original input word. the problem is exaggerated for rare words, which exist in the sparse regions of the embedding space and hence, do not get perturbed even for larger noise scales. this makes it easier for an adversary to reconstruct the original word, which may contain sensitive information (e.g. street names). the proposed vickrey mechanisms generalize the noisy nearest neighbor selection step by distributing the selection probability between the first and second nearest neighbor foot_2 using a tuning parameter @xmath7, 1] (see algorithm 1). intuitively, this generalization makes the reconstruction of the original input word harder (see figures 1 and 2 ). we capture our intuition for the claim above in figure 1 . for simplicity, the horizontal axis in both plots represents the one-dimensional embedding on a vocabulary containing only 5 words: (a, b, c, d, e). the vertical axis represents the output probability of each word through the mechanism. the plots represent the output probability in the mechanism for each of the 5 words, corresponding to the potential noised embedding values on the horizontal axis. the top plot represents the laplace mechanism when only the first nearest neighbor algorithm 1: the vickrey mechanism to the noised embedding is feasible for selection (@xmath8. in this case, all 5 curves are step functions since only the nearest neighbors are returned. the bottom plot shows the output probability for the vickrey mechanisms, which always impart plausible deniability with another word when the noised embedding falls in any open interval. overview of algorithm 1. we outline the main steps for the class of vickrey mechanisms in algorithm 1. for each word in the input, an additive noise z is sampled according to the density function p(z) ∝ exp{-d(z, 0)}. then the vickrey mechanism will select both the first and second nearest neighbor of the noised embedding as candidates, and randomly output one of them according to probabilities calibrated by their distances to the noised embedding using a tuning parameter t. the closer t is to 1, the more the vickrey mechanism favors the second nearest neighbor. privacy analysis. we formally prove that the vickrey mechanism m t at privacy @xmath9, 1]. theorem 1. for any @xmath10, 1], > 0, metric d and w, w , ŵ ∈ w, the vickrey mechanism m t from algorithm 1 satisfies metric-dp: to be the set that has w i and w j as the first and second nearest neighbors. let p w (z) be the density function for the perturbed embedding conditional on the input w: p w (z) ∝ exp (-d{z -φ(w), 0}) since metric d satisfies the triangle inequality, d{z-φ(w ), 0}-d{z-φ(w), 0} ≤ d{φ(w), φ(w )}, we obtain: and ρ(w, ŵ) = pr{m t (w) = ŵ}. since ρ(w, ŵ) is a sum of partial probabilities in the areas where ŵ is either the first or the second nearest neighbor to the noised embedding, we have: for our experiments, we use the euclidean distance for d so that the vickrey mechanism reduces to the laplace mechanism when @xmath11. in general, any distance function d that satisfies the triangle inequality can be used to ensure the desired metric-dp guarantee (quantified by the parameter ). ## tuning parameter selection we now discuss how to select the tuning parameter in algorithm 1. we do this by optimizing an empirical formulation of the privacy-utility tradeoff. we discuss the details of this formulation next. ## experimental results setup. we evaluate the performance of the proposed vickrey mechanisms in terms of the empirical privacy-utility tradeoff on three datasets: for all three datasets, we consider both 300dimensional glove embeddings @xcite and 300-d fasttext embeddings @xcite . the empirical privacy measurement uses the adversary's expected inference error rate, i.e. d e ( ŵ, w) = 1( ŵ = w). the utility-specific metric d l is chosen to be the misclassification error rate. the prior word distribution is chosen to be the empirical word distribution in the dataset, because we want to assume an informative adversary so as not to underestimate the privacy risk. in the vickrey mechanism, the distance function is the euclidean distance, so that @xmath12. we also compare our results with the mahalanobis mechanism @xcite . ## generalizing vickrey mechanism beyond the second nearest neighbor by a random selection of both the first and the second nearest neighbor to the noised embedding, we have shown that the vickrey mechanism can empirically improve the privacy-utility tradeoff upon the existing laplace and mahalanobis mechanisms. a natural generalization is to extend the selection to @xmath13. algorithm 3 presents the outline of the generalized vickrey mechanism that randomly chooses among the noisy k nearest neighbors as output, where the selection probability is inversely associated with their distance to the noised embedding. similar to algorithm 2, the tuning parameters are selected as to optimize for the empirical privacyutility tradeoff, but the selection process will be more challenging because the optimization space is unbounded. we defer the details of this optimization to future work. however, we formally state in theorem 2 the metric-dp guarantee from the generalized vickrey mechanism in algorithm 2. due to space constraints, we defer the details of algorithm 3: generalized vickrey mechanism 1 input: string @xmath14. . . wn, metric d, privacy parameter , tuning parameters t1, . . . , t @xmath15, 0)} 4 obtain φi ← φ(wi) + z 5 let wi1 ← arg min @xmath16. . . wik ← arg min @xmath17, wi1 ,..., wik } φi -φ(w) 2. 6 set ŵi ← wir with prob. pr(t 1,...,k , φi), where pr(t 1,...,k , φi) = exp{-tr φ( wir -φi 2 } j exp{-t j φ( wij -φi 2 } for all @xmath18. 7 return @xmath19. . . ŵn. theorem 2. for any @xmath20, . . . , t k ] ∈ [0, ∞) k , @xmath21, > 0 and w, w , ŵ ∈ w, the generalized vickrey mechanism m t from algorithm 3 satisfies metric-dp for any metric d. in figure 3 , we compare 5 generalizations of the vickrey mechanism that deterministically select the noisy 1 st , . . . , 5 th neighbors as the output on the product reviews data using both 300-d glove and 300-d fasttext. we can see that the improvement is most significant between the 1 st and 2 nd nearest neighbor. it also shows that there is benefit in introducing the 3 rd nearest neighbor into the selection pool, while no big difference is found beyond the 3 rd neighbor. ## discussion and conclusion in this paper, we present a measurement framework to quantify the empirical privacy-utility tradeoff for metric-dp text generation mechanisms, where the empirical privacy metric is the reconstruction risk of the original text based on the redacted text. we adopt a constrained optimization setup, where within the class of metric-dp mechanisms, we maximize the empirical privacy guarantee while keeping the machine learning utility loss under a prespecified tolerance. a novel class of vickrey mechanism is proposed, which not only enjoys metric-dp but also optimizes the privacy-utility tradeoff within the constraint. we apply our methodology to the three text classification datasets and demonstrate how to empirically compare the privacyutility tradeoff as well as how to choose the optimal parameter setting according to the constrained optimization. our results show superior performance when compared to existing mechanisms. our analysis in this paper leaves ample room for further investigation. an ongoing work we are exploring is the inclusion of contextual information into the probability calibration between the two nearest neighbors. we leave it as an interesting open problem to explore how the choice of k th neighbor impacts the tradeoff in this scenario, since contextual signals will likely restrict the set of candidate words we can choose from.