A Differentially Private Text Perturbation Method Using Regularized Mahalanobis Metric (2020)

Abstract: Balancing the privacy-utility tradeoff is a crucial requirement of many practical machine learning systems that deal with sensitive customer data. A popular approach for privacy- preserving text analysis is noise injection, in which text data is first mapped into a continuous embedding space, perturbed by sampling a spherical noise from an appropriate distribution, and then projected back to the discrete vocabulary space. While this allows the perturbation to admit the required metric differential privacy, often the utility of downstream tasks modeled on this perturbed data is low because the spherical noise does not account for the variability in the density around different words in the embedding space. In particular, words in a sparse region are likely unchanged even when the noise scale is large. In this paper, we propose a text perturbation mechanism based on a carefully designed regularized variant of the Mahalanobis metric to overcome this problem. For any given noise scale, this metric adds an elliptical noise to account for the covariance structure in the embedding space. This heterogeneity in the noise scale along different directions helps ensure that the words in the sparse region have sufficient likelihood of replacement without sacrificing the overall utility. We provide a text-perturbation algorithm based on this metric and formally prove its privacy guarantees. Additionally, we empirically show that our mechanism improves the privacy statistics to achieve the same level of utility as compared to the state-of-the-art Laplace mechanism.

## introduction machine learning has been successfully utilized in a wide variety of real world applications including information retrieval, computer graphics, speech recognition, and text mining. technology companies like amazon, google, and microsoft already provide mlaas (machine learning as a service), where customers can input their datasets for model training and receive black-box prediction results as output. however, those datasets may contain personal and potentially sensitive information, which can be exploited to identify the individuals in the datasets, even if it has been anonymized @xcite . removing personally identifiable information is often inadequate, since having access to the summary statistics on the dataset has been shown to be sufficient to infer individual's membership in the dataset with high probability @xcite @xcite . moreover, machine learning models themselves can reveal information on the training data. in particular, sophisticated deep neural networks for natural language processing tasks like next word prediction or neural machine translation, often tend to memorize their training data, which makes them vulnerable to leaking information about their training data @xcite . to provide a quantifiable privacy guarantee against such information leakage, differential privacy (dp) has been adopted as a standard framework for privacy-preserving analysis in statistical databases @xcite @xcite . intuitively, a randomized algorithm is differentially private if the output distributions from two neighboring databases are indistinguishable. however, a direct application of dp to text analysis can be too restrictive because it requires a lower bound on the probability of any word to be replaced by any other word in the vocabulary. metric differential privacy arises as a generalization of local differential privacy @xcite , which originated in protecting location privacy such that locations near the user's location are assigned with higher probability while those far away are given negligible probability @xcite . in the context of privacy-preserving text analysis, metric differential privacy implies that the indistinguishability of the output distributions of any two words in the vocabulary is scaled by their distance, where the distance metrics used in the literature include hamming distance (reduced to dp), manhattan distance @xcite , euclidean distance @xcite @xcite , chebyshev distance @xcite , hyperbolic distance @xcite . in this paper, we propose a novel privacypreserving text perturbation method by adding an elliptical noise to word embeddings in the euclidean space, where the scale of the noise is calibrated by the regularized mahalanobis norm (formally defined in section 3). we compare our method to the existing multivariate laplace mechanism for privacy-preserving text analysis in the euclidean space @xcite . in both papers, text perturbation is implemented by adding a spherical noise sampled from multivariate laplace distribution to the original word embedding. however, the spherical noise does not account for the structure in the embedding space. in particular, words in a sparse region are likely unchanged even when the scale of noise is large. this can potentially result in severe privacy breach when sensitive words do not get perturbed. to increase the substitution probability of words in sparse regions, the scale of noise has to be large in the multivariate laplace mechanism, which will hurt the downstream machine learning utility. we address this problem by adding an elliptical noise to word embeddings according to the covariance structure in the embedding space. the intuition is that given a fixed scale of noise, we want to stretch the noise equidistant contour in the direction so that the substitution probability of words in the sparse region is increased on average. intuitively, this direction is the one that explains the largest variability in the word embedding vectors in the vocabulary. we prove the theoretical metric differential privacy guarantee of the proposed method. furthermore, we use empirical analysis to show that the proposed method significantly improves the privacy statistics while achieves the same level of utility as compared to the multivariate laplace mechanism. our main contributions are as follows: privacy-preserving text analysis is a well-studied problem in the literature @xcite . one of the common approaches is to identify sensitive terms (like personally identifiable information) in a document and replace them with some more general terms @xcite @xcite . another line of research achieves text redaction by injecting additional words into the original text without detecting sensitive entities @xcite @xcite . however, those methods are shown to be vulnerable to reidentification attacks @xcite . in order to provide a quantifiable theoretical privacy guarantee, the differential privacy framework @xcite has been used for privacypreserving text analysis. in the dptext model @xcite , an element-wise univariate laplace noise is added to the pre-trained autoencoders to provide privacy for text representations. another approach for privacy-preserving text perturbation is in the metric differential privacy framework @xcite , an extended notion of local differential privacy @xcite , which adds noise to the pre-trained word embeddings. metric differential privacy requires that the indistinguishability of the output distributions of any two words in the vocabulary be scaled by their distance, which reduces to differential privacy when hamming distance is used @xcite . a hyperbolic distance metric @xcite was proposed to provide privacy by perturbing vector representations of words, but it requires specialized training of word embeddings in the highdimensional hyperbolic space. for the word em-beddings in the euclidean space @xcite ), text perturbation is implemented by sampling independent spherical noise from multivariate laplace distributions. the former work @xcite subsequently used an earth mover's metric to derive a bag-of-words representation on the text, whereas the latter (feyisetan et al., 2020) directly worked on the word-level embeddings. since we work with word embeddings in the euclidean space, we compare our method to the multivariate laplace mechanism for text perturbation in those two papers @xcite . mahalanobis distance has been used as a sensitivity metric for differential privacy in functional data @xcite and differentially private outlier analysis @xcite . outside the realm of text analysis, mahalanobis distance is a common tool in cluster analysis, pattern recognition, and anomaly detection @xcite @xcite @xcite . ## methodology we begin by formally defining euclidean norm and the regularized mahalanobis norm. definition 1 (euclidean norm). for any vector @xmath0, its euclidean norm is: definition 2 (mahalanobis norm). for any vector @xmath1, and a positive definite matrix σ, its mahalanobis norm is: definition 3 (regularized mahalanobis norm). for any vector @xmath2, λ ∈ [0, 1], and a positive definite matrix σ, its regularized mahalanobis norm is: from the definitions above, λ can be considered as a tuning parameter. when λ = 0, the regularized mahalanobis norm reduces to the euclidean norm; when λ = 1, the regularized norm reduces to the mahalanobis norm @xcite note that for any η > 0, the trajectory of {@xmath3: y -x 2 = η} is spherical, whereas the trajectory of {@xmath4: y -x @xmath5. we will exploit this key difference in the geometry of equidistant contour between the euclidean norm and the regularized mahalanobis norm to motivate our text perturbation method. the proposed regularized mahalanobis norm is a type of shrinkage estimator @xcite @xcite , which is commonly used to estimate the covariance matrix of high-dimensional vectors so as to ensure the stability of the estimator. the matrix σ in the regularized mahalanobis norm controls the direction to which the equidistant contour in the noise distribution is stretched, while the parameter λ controls the degree of the stretch. definition 4 (metric differential privacy.). for @xmath6, a randomized algorithm m : @xmath7, @xmath8, the following holds: metric differential privacy (d x -privacy) originated in privacy-preserving geolocation studies @xcite , where the metric d is euclidean distance. it has been extended to quantifying privacy guarantee in text analysis, which states that for any two words w, w in the vocabulary w, the likelihood ratio of observing any ŵ ∈ w is bounded by d(w, w ), where d(w, w ) = φ(w) -φ(w ) 2 for an embedding function φ : @xmath9. the multivariate laplace mechanism @xcite perturbs the word embedding φ(w) by adding a random spherical noise z sampled from density f z (z) ∝ e z 2 , and then find the nearest neighbor in the embedding space as the output of the mechanism. the left panel in figure 1 illustrates the text perturbation by spherical noise in the multivariate laplace mechanism. here a is in the sparse region in the two-dimensional embedding space. given the privacy budget , a has a small probability of being substituted by other words because its expected perturbation (dotted trajectory) still has itself as the nearest neighbor. the right panel in figure 1 shows text perturbation in the proposed mahalanobis mechanism, where the word embeddings are redacted by an elliptical noise at the same privacy budget . the matrix σ is taken to be the sample covariance matrix of the word embeddings scaled by the mean sample variance, so that the noise contour is stretched toward the direction that explains the largest variability in the embedding space. the purpose of the scaling step is to ensure that the scale of the elliptical noise is the same as the scale of the spherical noise. by transforming the spherical noise contour into an elliptical contour, we increase the substitution probability of a in the sparse region, thus improving the privacy guarantee. meanwhile, since the scale of noise does not change, the utility is preserved at the same level. this is an illustrative example demonstrating the intuition and motivation of the proposed mahalanobis mechanism. our proposed mahalanobis mechanism for text perturbation shares the same general structure as the multivariate laplace mechanism. the key difference is that the spherical noise f z (z) ∝ exp ( z 2 ) in the multivariate laplace mechanism is replaced by the elliptical noise sampled from density f z (z) ∝ exp(-z rm ), which can be efficiently performed via algorithm 1. an overview for the proposed mahalanobis mechanism is presented in algorithm 2. when λ = 0, the proposed mahalanobis mechanism reduces to the multivariate laplace mechanism. a heuristic method for choosing the tuning parameter λ is to find the value of λ that maximizes the improvement in the privacy guarantee while maintaining the same level of utility. this can be done through empirical privacy and utility experiments as described in section 5. the input σ in algorithm 2 is computed by scaling the sample covariance matrix of the word embeddings by the mean sample variance so as to guarantee that the trace of σ equals the trace of i m . since σ is a scaled counterpart of the sample covariance matrix, it will stretch the elliptical noise toward the direction with the largest variability in the word embedding space, which maximizes the overall expected probability of words being substituted. we remark that in order to maximize the substitution probability for each individual word, a personalized covariance matrix σ w can be computed in the neighborhood of each word. this is beyond the scope of this paper and we leave it as future work. ## theoretical properties lemma 1. the random variable z returned from algorithm 1 has a probability density function of the form f z (z) ∝ exp(-z rm ). proof. define @xmath10. note that conditional on y , u follows a uniform distribution on a sphere with radius y in the m-dimensional space, which implies f u |y (u|y) ∝ 1/y m-1 when m @xmath11. therefore, the result in the lemma follows by definition. theorem 1. for any @xmath12, 1], the mahalanobis mechanism from algorithm 2 satisfies d χ -privacy with respect to the regularized mahalanobis norm. where m : w @xmath13: @xmath14. we begin by showing that for any w, w , ŵ ∈ w, it holds that the probability pr{m (w) = ŵ} is at most e φ(w)-φ(w ) rm times the probability pr{m (w ) = ŵ}. we define c ŵ = {@xmath15: v -φ( ŵ) 2 < min @xmath16: sampling from f z (z) ∝ exp(-z rm ) algorithm 2: the mahalanobis mechanism 1 input: string @xmath17. . . w n , privacy @xmath18, scaled sample covariance matrix σ, tuning parameter λ ∈ [0, 1] 2 for @xmath19, . . . , n} do 3 sample z from f z (z) ∝ exp(-z rm ) using algorithm 1. ## experiments we empirically compare the proposed mahalanobis mechanism and the existing multivariate laplace mechanism in both privacy experiments and utility experiments on the following two datasets (more details in appendix a): ## conclusions we develop a differentially private mahalanobis mechanism for text perturbation. compared to the existing multivariate laplace mechanism, our mechanism exploits the geometric property of elliptical noise so as to improve the privacy statistics while maintaining a similar level of utility. our method can be readily extended to the privacypreserving analysis on other natural language processing tasks, where utility can be defined according to specific needs. we remark that the choice of σ as the global covariance matrix of the word embeddings can be generalized to the personalized covariance matrix within the neighborhood of each word. in this sense, local sensitivity can be used instead of global sensitivity to calibrate the privacy-utility tradeoff. this can be done by adding a preprocessing clustering step on the word embeddings in the vocabulary, and then perform the mahalanobis mechanism within each cluster using the cluster-specific covariance matrix. furthermore, the choice of the tuning parameter λ can also be formulated as an optimization problem with respect to pre-specified privacy and utility constraints. since λ is the only tuning parameter on a bounded interval of [0, 1], a grid search would suffice, which can be conducted by finding the λ value that maximizes the utility (privacy) objective given the fixed privacy (utility) constraints.