A Collocation-based Method for Addressing Challenges in Word-level Metric Differential Privacy (2024)

Abstract: Applications of Differential Privacy (DP) in NLP must distinguish between the syntactic level on which a proposed mechanism operates, often taking the form of *word-level* or *document-level* privatization. Recently, several word-level *Metric* Differential Privacy approaches have been proposed, which rely on this generalized DP notion for operating in word embedding spaces. These approaches, however, often fail to produce semantically coherent textual outputs, and their application at the sentence- or document-level is only possible by a basic composition of word perturbations. In this work, we strive to address these challenges by operating *between* the word and sentence levels, namely with *collocations*. By perturbing n-grams rather than single words, we devise a method where composed privatized outputs have higher semantic coherence and variable length. This is accomplished by constructing an embedding model based on frequently occurring word groups, in which unigram words co-exist with bi- and trigram collocations. We evaluate our method in utility and privacy tests, which make a clear case for tokenization strategies beyond the word level.

## introduction the study of differential privacy (dp) in natural language processing has brought about a number of innovative approaches, ranging from text rewriting to private fine-tuning of language models @xcite . at the core of these approaches is the goal of providing a level of quantifiable privacy protection when text is shared or used for some downstream purpose. among other advantages, leveraging dp allows for flexibility in choice of privacy level, governed by the privacy budget, or ε. an early form of dp in nlp comes with the notion of word-level metric differential privacy (mldp), the goal of which is to allow for privacypreserving analysis on text documents by per-forming word-level perturbations @xcite . in essence, a word is obfuscated by adding random noise to its embedding, perturbing to a (possibly different) word, and then releasing this "privatized" word @xcite . metric dp is ensured via the implementation of mechanisms which add calibrated noise to text representations. while other recent advances in dp nlp have shifted towards more complex language models, the simplicity and atomicity of word-level mldp methods make a case for its further study. although these works show promising results in balancing privacy and utility in the mldp setting, a number of challenges have also been highlighted @xcite . firstly, the design of mechanisms raises challenges when the underlying spaces, e.g., word embeddings, are both vast (large vocabularies) and complex (high dimensional) @xcite . moreover, applying dp at the word level and composing these results for private text generation often results in texts with grammatical errors @xcite . beyond this, composed word-level mldp will always lead to privatized documents with the same length as the input documents, diminishing privacy protections. in this work, we aim to address these challenges by building upon the promise of mldp mechanisms, but rather than rely on word-level perturbations, we extend these mechanisms to operate on the collocation-level, or more generally, the n-gram level. by specifically focusing on collocations, we hope to improve output text coherence, introduce generated length variability, and boost utility while also performing fewer overall perturbations, thus saving privacy budget. in particular, we are guided by the following research question: ## a collocation-based mldp method in this section, we describe our proposed method, which differs from word-level mldp methods in that it sets the underlying metric space to that of a jointly trained model of unigrams, bigram collocations, and trigram collocations. we outline a method to extract collocations, the training of the abovementioned embedding model, and the augmentation of existing mldp mechanisms. ## experimental setup and results in our experiments to test our collocation-based method, we focus on evaluating the effect that can be observed by using collocations rather than pure words. in particular, we perform a two-part evaluation: utility experiments and privacy experiments. ## conclusion in this work, we present an alternative to wordlevel metric differential privacy, which differs in the way that we tokenize and privatize sensitive input texts on the collocation level. we provide two collocation extraction algorithms and their corresponding trained embedding models, showing how word-level mldp mechanisms can be simply augmented to operate on this higher syntactic level. in our evaluation, we demonstrate the merits of such augmentation, achieving a balance between improved utility, higher semantic coherence, and comparable privacy preservation. the results provide researchers with two overarching insights. using collocations, given the same overall budget for a document, we can achieve higher utility while still preserving privacy. at the same time, given the same per-token budget, perturbing collocations often outperforms word-byword privatization. thus, we make the case that further studies in the field of dp nlp should consider investigating linguistic units outside of the standard word-or sentence-/document-level. the main limitations of our study come with our reliance on one particular measure for collocation extraction, namely pmi. in addition, we focus on validating our method for the madlib mechanism, but do not perform extensive testing on more recent methods. finally, we base our results on the selected datasets for utility and privacy, whereas this would be well-served to be more extensively tested. as such, we propose the following paths for future work: (1) a focus on collocations and their reliable extraction for dp applications, (2) further work on validating the merits of privatization between the word and sentence level, and (3) deeper investigations into the rigorous evaluation of dp text privatization, with an emphasis on metrics.