Guiding Text-to-Text Privatization by Syntax (2023)

Abstract: Metric Differential Privacy is a generalization of differential privacy tailored to address the unique challenges of text-to-text privatization. By adding noise to the representation of words in the geometric space of embeddings, words are replaced with words located in the proximity of the noisy representation. Since embeddings are trained based on word co-occurrences, this mechanism ensures that substitutions stem from a common semantic context. Without considering the grammatical category of words, however, this mechanism cannot guarantee that substitutions play similar syntactic roles. We analyze the capability of text-to-text privatization to preserve the grammatical category of words after substitution and find that surrogate texts consist almost exclusively of nouns. Lacking the capability to produce surrogate texts that correlate with the structure of the sensitive texts, we encompass our analysis by transforming the privatization step into a candidate selection problem in which substitutions are directed to words with matching grammatical properties. We demonstrate a substantial improvement in the performance of downstream tasks by up to 4.66% while retaining comparative privacy guarantees.

## introduction from compliance with stringent data protection regulations to building trust, privacy emerged as a formidable challenge to applications that build on user-generated data, and consensus exists regarding the need to safeguard user privacy. in the context of text analysis, privacy is typically protected by sanitizing personally identifiable information from the text via ad-hoc filtering or anonymization. the literature is replete with naïve approaches that either redact words from the text or insert distractive words into the text. using generalization and suppression on quasi-identifiers, an intuitive way of expressing privacy is presented by k-anonymity @xcite and its notable adaptations for text data @xcite . however, these approaches are fundamentally flawed. incapable of anticipating an adversary's side knowledge, most anonymization schemes are vulnerable to re-identification and thus provably non-private. as text conveys seemingly innocuous information, researchers demonstrated that this information can be leveraged to identify authorship @xcite or disclose identifiable information @xcite @xcite . @xcite , for instance, recovered verbatim text from the training corpus using black-box querying to a language model. building upon noise calibration, differential privacy (dp) @xcite attracted considerable attention for their robust notion of privacy. for text analysis, dp is applied to the vector-valued representation of text data @xcite @xcite . we focus on metric differential privacy @xcite , in which data is processed independently, similar to the setting of randomized response @xcite . to avoid the curse of dimensionality of randomized response, noise is scaled by a general distance metric. for text-to-text privatization, @xcite adopted a distance metric so that words that are close (i.e. more similar) to a word are assigned with a higher substitution probability than those that are more distant (i.e. less similar). this requires that the text is mapped onto a continuous embedding space @xcite @xcite . proceeding from the embedding, each word in the text is privatized by a three-step protocol: (1) retrieving the vector representation of the word, (2) perturbing the vector representation of the word with noise sampled from a multivariate distribution, and (3) projecting the noisy representation of the word back to the discrete vocabulary space. as the noisy representations are unlikely to exactly represent words in the embedding space, a nearest neighbor approximation is returned. since text-to-text privatization operates directly on embeddings and words in the embedding space are mapped based on co-occurrences, words tend to be substituted by words that stem from a common semantic context. however, there is no guarantee that words are substituted by words that serve similar roles within the grammatical structure of a text. motivated by the example of sentiment analysis, in which sentiment is typically expressed by adjectives and forms of adjectives @xcite , we hypothesize that substitutions strictly based on co-occurrences may degrade downstream performance. this hypothesis is in line with linguists finding repeated evidence for the relevance of grammatical properties for language understanding @xcite . we summarize our contributions as follows: ## methodology since text-to-text privatization operates directly on geometric space of embeddings, it is necessary to understand the structure of the embedding space. to get an understanding of the embedding space, we selected a subset of 1, 000 most frequent words from the 100-dimensional glove embedding and manifolded them onto a two-dimensional representation. enriched by grammatical properties derived from the universal part-of-speech tagset @xcite , we chart a t-distributed stochastic neighbor embedding (van der @xcite in figure 1 . we note that we derived each word's grammatical category without context, which may explain the general tendency towards nouns (presumably misclassified verbs). regardless of potentially misclassified grammatical categories, we can draw the following conclusions: while nouns, verbs, and adjectives are distributed throughout the embedding space, we find distinct subspaces for numerals and punctuation. this is because word embeddings are trained towards an objective that ensures that words occurring in a common context have similar embeddings, disregarding their syntactic roles within the structure of a text. considering that text-to-text privatization typically selects the nearest approximate neighbor after the randomized mechanism is queried as substitution, we expect this mechanism to fall short in producing syntactically coherent texts. we adopt the multivariate laplace mechanisms of madlib @xcite . aimed at preserving the grammatical category of a word after its substitution, we incorporate a constraint into the candidate selection that directs the randomized mechanism towards words with a matching grammatical category. this constraint is incorporated as follows: we create a dictionary that serves as a lookup table for the grammatical category of each word in the vocabulary and generalize the randomized mechanism to return a flexible k ≫ 1 (instead of @xmath0. if available, a word is replaced by the nearest word (measured from the noisy representation) that matches its grammatical category. otherwise, the protocol reduces to canonical madlib. the computational overhead of the candidate selection is o(log k). this modification introduces the size of the candidate pool k as an additional hyperparameter. intuitively, k should be chosen based on the geometric properties of the embedding, i.e., k should be large enough to contain at least one other word with a matching grammatical category. we investigate our modification tomadlib in terms of its capability to preserve grammatical properties and its implications. for reasons of reproducibility, we base all experiments on the 100dimensional glove embedding. once we determined our sub-vocabulary, we calculated the necessary size of the candidate pool k. we counted the number of steps required from each word in our subset until a neighbor with a matching category was found. averaging this count revealed that each word is linked to another word with a matching category within a neighborhood of 20. we thus parameterized the candidate pool to a fixed @xmath1. ## experiments we conduct a series of experiments at a strategically chosen set of privacy budgets ε = {5, 10, 25} to demonstrate the relevance of directing substitution to words that share similar syntactic roles rather than restricting substitution only to words that appear in a similar semantic context. these privacy budgets represent three privacy regimes: ε = 5 for high privacy, ε = 10 for moderate privacy, and ε = 25 for low privacy. ## conclusion privatizing written text is typically achieved through text-to-text privatization over the embed-ding space. since text-to-text privatization scales the notion of indistinguishably of differential privacy by a distance in the geometric space of embeddings, prior studies focused on geometric properties @xcite @xcite . unlike prior studies on amplifying text-to-text privatization by accounting for the geometric position of words within the embedding space, we initialized a set of strategies for amplification from the perspective of grammatical properties, such as category, number, or tense. by incorporating grammatical properties in the form of part-of-speech tags into text-to-text privatization, we direct the privatization step towards preserving the syntactic role of a word in a text. we experimentally demonstrated that that surrogate texts that conform to the structure of the sensitive text outperform surrogate texts that strictly rely on co-occurrences of words in the embedding space. limitations. we note that directing the substitution to candidates with matching grammatical categories incurs additional information leakage that is not accounted for by our modification. too remedy the unaccounted information leakage, one could recast the candidate selection through the exponential mechanism @xcite .