Sentence-level Privacy for Document Embeddings (2022)

Abstract: User language data can contain highly sensitive personal content. As such, it is imperative to offer users a strong and interpretable privacy guarantee when learning from their data. In this work we propose SentDP, pure local differential privacy at the sentence level for a single user document. We propose a novel technique, DeepCandidate, that combines concepts from robust statistics and language modeling to produce high (768) dimensional, general \epsilon -SentDP document embeddings. This guarantees that any single sentence in a document can be substituted with any other sentence while keeping the embedding \epsilon -indistinguishable. Our experiments indicate that these private document embeddings are useful for downstream tasks like sentiment analysis and topic classification and even outperform baseline methods with weaker guarantees like word-level Metric DP.

## introduction language models have now become ubiquitous in nlp @xcite @xcite , pushing the state of the art in a variety of tasks @xcite @xcite . while language models capture meaning and various linguistic properties of text @xcite , an individual's written text can include highly sensitive information. even if such details are not needed or used, sensitive information has been found to be vulnerable and detectable to attacks @xcite @xcite . reconstruction attacks @xcite have even successfully broken through private learning schemes that rely on encryption-type methods @xcite . as of now, there is no broad agreement on what constitutes good privacy for natural language @xcite . @xcite argue that different applications and models require different privacy definitions. several emerging works propose to apply metric differential privacy @xcite at the word level @xcite @xcite @xcite . they propose to add noise to word embeddings, such that they are indistinguishable from their nearest neighbours. at the document level, however, the above definition has two areas for improvement. first, it may not offer the level of privacy desired. having each word indistinguishable with similar words may not hide higher level concepts in the document, and may not be satisfactory for many users. second, it may not be very interpretable or easy to communicate to end-users, since the privacy definition relies fundamentally on the choice of embedding model to determine which words are indistinguishable with a given word. this may not be a clear and precise enough for end-users to grasp. in this work, we propose a new privacy definition for documents: sentence privacy. this guarantee is both strong and interpretable: any sentence in a document must be indistinguishable with any other sentence. a document embedding is sentenceprivate if we can replace any single sentence in the document and have a similar probability of producing the same embedding. as such, the embedding only stores limited information unique to any given sentence. this definition is easy to communicate and strictly stronger than word-level definitions, as modifying a sentence can be changing one word. although this definition is strong, we are able to produce unsupervised, general embeddings of documents that are useful for downstream tasks like sentiment analysis and topic classification. to achieve this we propose a novel privacy mechanism, deepcandidate, which privately samples a high-dimensional embedding from a preselected set of candidate embeddings derived from public, non-private data. deepcandidate works by first pretuning a sentence encoder on public data such that semantically different document embeddings are far apart from each other. then, we approximate each candidate's tukey depth within the private documents' sentence embeddings. deeper candidates are the most likely to be sampled to represent the private document. we evaluate deepcandidate on three illustrative datasets, and show that these unsupervised private embeddings are useful for both sentiment analysis and topic classification as compared to baselines. in summary, this work makes the following contributions to the language privacy literature: then, the space of all documents is @xmath0, s 2 , . . . , s k ) for any non-negative integer k of sentences. in this work, we focus on cohesive documents of sentences written together like reviews or emails, but our methods and guarantees apply to any sequence of sentences, such as a collection of messages written by an individual over some period of time. our task is to produce an embedding @xmath1. that is, if one were to replace any single sentence in the document s @xmath2, the probability of producing a given embedding z is similar. to achieve this, we propose a randomized embedding function (the embedding mechanism) m : @xmath3, that generates a private embedding @xmath4. ## sentence-level privacy we now introduce our simple, strong privacy definition, along with concepts we use to satisfy it. ## deepcandidate while useful and general, the document embedding g(x) does not satisfy sentdp. we now turn to describing our privacy-preserving technique, deepcandidate, which generates general, ϵ-sentdp document embeddings that preserve relevant information in g(x), and are useful for downstream tasks. to understand the nontrivial nature of this problem, we first analyze why the simplest, straightfoward approaches are insufficient. motivation. preserving privacy for high dimensional objects is known to be challenging @xcite @xcite . for instance, adding laplace noise directly to g(x), as done to satisfy some privacy definitions @xcite , does not guarantee sentdp for any ϵ. recall that the embedding space is all of r d . a change in one sentence can lead to an unbounded change in g(x), since we do not put any restrictions on the general encoder g. thus, no matter how much noise we add to g(x) we cannot satisfy sentdp. a straightforward workaround might be to simply truncate embeddings such that they all lie in a limited set such as a sphere or hypercube as done in prior work @xcite . in doing so, we bound how far apart embeddings can be for any two sentences, ∥g(s i ) -g(s ′ i )∥ 1 , thus allowing us to satisfy sentdp by adding finite variance noise. however, such schemes offer poor utility due to the high dimensional nature of useful document embeddings (we confirm this in our experiments). we must add noise with standard deviation proportional to the dimension of the embedding, thus requiring an untenable degree of noise for complex encoders like bert which embed into r 768 . our method has three pillars: (1) sampling from a candidate set of public, non-private document embeddings to represent the private document, (2) using the tukey median to approximate the document embedding, and (3) pre-training the sentence encoder, g, to produce relevant candidates with high tukey depth for private document x. ## conclusions and future work we introduce a strong and interpretable local privacy guarantee for documents, sentdp, along with deepcandidate, a technique that combines principles from nlp and robust statistics to generate general ϵ-sentdp embeddings. our experiments confirm that such methods can outperform existing approaches even with with more relaxed privacy guarantees. previous methods have argued that it is "virtually impossible" to satisfy pure local dp @xcite at the word level while capturing linguistic semantics. our work appears to refute this notion at least at the document level. to follow up, we plan to explore other ap-proaches (apart from k-means) of capturing the structure of the embedding distribution g(µ) to encourage better candidate selection. we also plan to experiment with decoding private embeddings back to documents by using novel candidates produced by a generative model trained on f .