Unsupervised Text Deidentification (2022)

Abstract: Deidentification seeks to anonymize textual data prior to distribution. Automatic deidentification primarily uses supervised named entity recognition from human-labeled data points. We propose an unsupervised deidentification method that masks words that leak personally-identifying information. The approach utilizes a specially trained reidentification model to identify individuals from redacted personal documents. Motivated by K-anonymity based privacy, we generate redactions that ensure a minimum reidentification rank for the correct profile of the document. To evaluate this approach, we consider the task of deidentifying Wikipedia Biographies, and evaluate using an adversarial reidentification metric. Compared to a set of unsupervised baselines, our approach deidentifies documents more completely while removing fewer words. Qualitatively, we see that the approach eliminates many identifying aspects that would fall outside of the common named entity based approach.

## introduction in domains such as law, medicine, and government, it can be difficult to release textual data because it contains sensitive personal information @xcite @xcite . privacy laws and regulations vary by domain and impact the requirements for deidentification. most prior work on automatic deidentification @xcite @xcite @xcite deidentifies data to the requirements of the hipaa safe harbor method (centers for @xcite . annotations for these systems are based on a list of 18 identifiers like age, phone number, and zip code. these systems treat deidentification as a named entity recognition problem within this space. upon the removal of these pre-defined entities, text is no longer considered sensitive. however, one of the 18 categories defined by hipaa safe harbor includes "any unique identifying number, characteristic, or code [that could be used to reidentify an individual]". prior work ignores this nebulous 18th category. one reason the category is ill-defined is due to the existence of quasi-identifiers, pieces of personally identifiable information (pii) that do not fall under any single category and therefore are difficult to identify and label in the general case @xcite . even data that has all of the categories from safe harbor removed may still be reidentified through quasi-identifiers @xcite . supervised approaches cannot naturally detect quasiidentifiers, since these words are not inherently labeled as pii @xcite . in this work, we propose an unsupervised deidentification method that targets the more general definition of pii. instead of relying on specific rule lists of named entities, we directly remove words that could lead to reidentification. motivated by the goal of k-anonymity @xcite , our approach utilizes a learned probabilistic reidentification model to predict the true identity of a given text. we perform combinatorial inference in this model to find a set of words that, when masked, achieve k-anonymity. the system does not require any annotations of specific pii, but instead learns from a dataset of aligned descriptive text and profile information. using this information, we can train an identification process using a dense encoder model. experiments test the ability of the system to deidentify documents from a large-scale database. we use a dataset of wikipedia biographies aligned tommy jönsson 97% tommy jönsson (born march 4, 1976) is a former swedish football player, who played as defender and retired in 2010. tommy (born march 4, 1976) is a former swedish football player, who played as defender and retired in 2010. <@xmath0, 1976) is a former swedish football player, who played as defender and retired in 2010. <@xmath1, 1976) is a @xmath2, who played as defender and retired in 2010. <@xmath3, 1976) is a @xmath4, who played as defender and retired @xmath5. <@xmath6, <@xmath7, who played as defender and retired @xmath8. tommy jönsson 90% tommy jönsson 41% tommy jönsson 38% vincent cobos 34% pmlm -tapas neural reidentification model tommy jönsson 100% with info-boxes @xcite . the system is fit on a subset of the data and then asked to deidentify unseen individuals. results show that even when all words from the profile are masked, the system is able to reidentify 32% of individuals. when we use our system to deidentify documents, it is able to fully anonymize them while retaining over 50% of words. when we compare our deidentification method to a set of unsupervised baselines, our method deidentifies documents more completely while removing fewer words. we qualitatively and quantitatively analyze the redactions produced by our system, including examples of successfully redacted quasi-identifiers. ## related work automated deidentification. there is much prior work on deidentifying text datasets, both with rule-based systems @xcite @xcite @xcite and deep learning methods @xcite @xcite . each of these methods is supervised, relies on datasets with human-labeled pii, and focuses on removing some subset of the 18 identifying categories from hipaa safe harbor. other approaches include generating entire new fake datasets using generative adversarial networks (gans) @xcite . @xcite train an lstm on an emr-based nlp task using adversarial loss to prevent the model from learning to reconstruct the input. finally, differential privacy is a technique for ensuring provably private distributions @xcite . it has mostly been used for training anonymized models on data containing pii, but requires access to the un-anonymized datasets for training @xcite . our deidentification approach does not provide the formal guarantees of differential privacy, but aims to provide a practical solution for anonymizing datasets in real-world scenarios. ## motivating experiment: quasi-identifiers in order to study the problem of deidentifying personal information from documents, we set up a model dataset utilizing personal profiles from wikipedia. we use the wikibio dataset @xcite . each entry in the dataset contains a document, the introductory text of the wikipedia article, and a profile, the infobox of key-value pairs containing personal information. we train on the training dataset of 582, 659 documents and profiles. during test time, we evaluate only test documents, but consider all 728, 321 profiles from the concatenation of the train, validation, and test sets. this dataset represents a natural baseline by providing a range of factual profile information for a large collection of individuals, making it challenging to deidentify. in addition, it provides an openly available collection for comparing models. is it difficult to deidentify individuals in this dataset? wikipedia presents no domain challenges, and so finding entities is trivial. in addition many of the terms in the documents overlap directly with the terms in the profile table. simple techniques should provide robust deidentification. we test this with two deidentification techniques: (1) named entity removes all words in documents that are tagged as named entities. (2) lexical removes all words in the document that also overlap with the profile. to reidentify, we use an information retrieval model (bm25) and a dense neural network approach (described in section 5). this experiment indicates that even in the wik-ibio domain, there are a significant number of pseudo-identifiers that allow the system to identify documents even when almost all known matching information is removed. in this work we study methods for discovering and quantifying these identifiers. ## deidentification by inference an overview of our data and system is shown in figure 1 . given a document x 1 . . . x n , we consider the problem of uniquely identifying the corresponding person y from a set of possible options y. the system works in the presence of redactions defined by a latent binary mask z 1 . . . z n on each position, where setting z @xmath9. we define a reidentification model as a model of p(y | x, z) that gives a probability to each profile in algorithm 1 greedy deidentification x, ŷ ← input document and person z j ← 0 for all j for @xmath10, z -j , z @xmath11, z) then return z y for a masked document. during deidentification, we assume that we have access to the true identity ŷ of the document that we would like to hide. our objective is to find the minimally sized mask that ensures that ŷ is not in the top-k predictions of the identification model: this objective is motivated by the concept of k-anonymity @xcite . a dataset has k-anonymity if each person ŷ in the dataset is indistinguishable from at least k other people in y. the k-anonymity objective is combinatorial, and is intractable to solve with a non-trivial reidentification model. we instead approximate it with search. specifically we use a simple greedy deidentification technique shown in algorithm 1. ## reidentification model the core of this redaction system is a model of reidentification, p(y | x, z). defining this model faces two challenges: a) to facilitate informed search in the presence of masks and b) to correctly identify a person from 100,000s of choices. as we do not have access to supervised masks, we define the probability of unmasked identification as marginalizing over all possible masks: to assign a prior over masks p(z | x), we opt for a simple setting that avoids building in additional information and fits well with deidentification search. one possibility would be to follow bert-style masking and mask words at a fixed ratio of 15% @xcite . however, liao et al. (2020) argue that while successful for classification, fixed-ratio masking works poorly for generation-style objectives. following this advice, we use the following algorithm to construct masks of varying size: for the reidentification model, p(y|x, z; θ), we follow the dense retrieval literature and use an embedding-based model @xcite . specifically we use an (asymmetric) bi-encoder model on documents and profiles. the document encoder f computes an embedding of the masked document, and the profile encoder g(y) produces an embedding of the profile table corresponding to person y. we score the match by computing the joint encoding f (x, z) ⊤ g(y) using the dot product between the vectors outputted by two neural networks. define the matrix of profile embeddings as @xmath12; ...; g(y |y| )]. the reidentification probability is defined as during training we utilize label smoothing on the distribution, which has also been shown to be useful when training for inference in an argmax setting @xcite . to train the model we optimize a lower bound on the identification log-likelihood: specifically we sample a word dropout mask z for each element x from the prior, and then mask words during reidentification training. note that for training we compute the full distribution and do not use a contrastive approximation. in order to learn the parameters of g we utilize coordinate ascent. specifically we fix g and optimize the parameters of f . we then switch and optimize the profile encoder g on odd-numbered epochs to predict documents in x (with no masking), and then recompute g. ## experimental setup models we call our main deidentification model nn deid. we consider several different parameterization variants of the dual encoder. document encoder (f (x, z)), we consider two different pretrained language models: roberta-base version @xcite (125m parameters) and pmlm @xcite ) (125m parameters), a pretrained encoder specifically designed to support masking-style inference. for the table encoder (g(z)), we consider: roberta-base @xcite (125m parameters) with a simple linearized version of the profile, and tapas base @xcite (111 million parameters), a model designed to handle table input. we randomly compute masks online during training, so documents take a new randomly-redacted form on each epoch. all models are implemented in hugging face transformers library @xcite . each model is trained for sixty epochs, about two days on a single nvidia rtx a6000 gpu. more training details are available in a. we experiment with all combinations for reidentification models, specified by document-profile encoders, roberta-roberta (rr), roberta-tapas (rt), pmlm-roberta (pr), pmlm-tapas (pt). the pt model is the default for nn deid. baselines we consider several unsupervised redaction baselines based on lexical matches with the table and word frequencies. lexical removes all overlapping words that appear in the profile from the document. idf (table -aware) masks all overlapping words that appear in the profile from the document, then masks in order of descending inverse document frequency (idf) (rarest word first) until a fixed threshold. we compute idf based on the full corpus of documents and profiles from the train, validation, and test sets. named entity removes all named entities from the document. 2 metrics a major challenge is how to evaluate text privacy in the presence of a strong reidentification models. as shown in section 3, information retrieval metrics work well for lightly redacted documents, but fail under heavy masking. we ran preliminary experiments with human subjects, but found that even at seemingly low levels of masking, documents were nearly impossible for humans to reidentify. inspired by work on adversarial privacy such as the neurips hide-and-seek challenge (jordon 2 we identify named entities using the dslim/bert-base-ner-uncased model available from hugging face. named entities identified are personal names (per), organization names (or), location names (loc), and miscellaneous names (misc) @xcite . 0.0 0.2 0.4 0.6 0.8 % words masked 0.0 0.2 0.4 0.6 0.8 1.0 reidentification % (ensemble) nn deid idf idf (table-aware) document lexical named entity figure 2: pareto curves comparing deidentification approaches on privacy versus words masked. lexical and named entity baselines are fixed values. nn deid is computed with different k-anonymity values. idf (table-aware) and idf remove until a fixed idf cutoff threshold. we also include a word-matching based ir model in the ensemble, but find that it is not competitive at reidentification. explicitly, the ensemble consists of the three variant parameterizations (rr, pr, rt) as well as the ir matching model. as a metric of utility, we compute the average percentage of words masked, as well as the information loss percentage, computed as the ratio between the size of the original and redacted texts when compressed. for each method and baseline we sweep over mask sizes to compute a curve of reidentifiability and utility. inference we generate redactions from the reidentification models using greedy search to find the word to mask that causes the maximum decrease in the correct prediction. we use search implementations from the textattack library @xcite . search takes in a stopping parameter k which indicates the rank cutoff of ŷ to stop search, ŷ ̸ ∈ k arg max y p(y|x, z). we run with different values of k to sweep over levels of privacy, and generate redactions with different masking rates. we ignore stopwords to speed up the search since they will rarely be identifiers. figure 2 expands on these results by showing the pareto curves for privacy and utility across methods. curves are obtained by varying the k value used in nn deid and the threshold for idf based deidentification. curves show that in addition to achieving better utility at very low rates of identifiablity, the method also achieves better utility than lexical matching, and a steeper privacy curve even at lower levels of redaction. ## conclusion we propose an unsupervised method for text deidentification that focuses on deidentifying pseudoidentifiers. the method first learns to reidentify from text utilizing a prior masking models. we then utilize search to find a mask to ensure k-anonymity in this model. this approach outperforms masking based on named entities and matching with tabular data, both of which fail to fully anonynize the document. using an ensemble of reidentification models as a metric, we show that our approach can reach high levels of privacy with moderate levels of redaction. in future work we plan to utilize this approach in conjugation with downstream tasks in order to further demonstrate the utility of the redacted data. we also plan to compare and evaluate with domain-specific approaches for distribut-