[1]Matthias Engelbach These authors contributed equally to this work.

These authors contributed equally to this work.

[1]Institute for Industrial Engineering IAO, Fraunhofer, Nobelstrasse 12,
Stuttgart, 70569, Germany

2]Institute of Human Factors and Technology Management IAT, University of
Stuttgart, Nobelstrasse 12, Stuttgart, 70569, Germany

3]Contractor Consulting GmbH, Adams-Lehmann-Str. 56, Munich, 80797, Germany

# Combining Embeddings and Domain Knowledge for Job Posting Duplicate
Detection

<EMAIL_ADDRESS>Dennis Klau<EMAIL_ADDRESS>stuttgart.de Maximilien Kintz<EMAIL_ADDRESS>Alexander
Ulrich<EMAIL_ADDRESS>*  [  [

###### Abstract

Job descriptions are posted on many online channels, including company
websites, job boards or social media platforms. These descriptions are usually
published with varying text for the same job, due to the requirements of each
platform or to target different audiences. However, for the purpose of
automated recruitment and assistance of people working with these texts, it is
helpful to aggregate job postings across platforms and thus detect duplicate
descriptions that refer to the same job. In this work, we propose an approach
for detecting duplicates in job descriptions. We show that combining overlap-
based character similarity with text embedding and keyword matching methods
lead to convincing results. In particular, we show that although no approach
individually achieves satisfying performance, a combination of string
comparison, deep textual embeddings, and the use of curated weighted lookup
lists for specific skills leads to a significant boost in overall performance.
A tool based on our approach is being used in production and feedback from
real-life use confirms our evaluation.

###### keywords:

Job Posting Analysis, Similarity Embeddings, Domain Knowledge, Duplicate
Detection, Deployed Application

##  1 Introduction

With increasing digitization of business processes, the possibility to assist
people working in the area of human resources by leveraging means of automated
recruiting has become an important topic [1, 2]. Technologies like artificial
intelligence (AI) and robot process automation (RPA) can be applied to a wide
range of tasks in a typical recruiting process, such as automated screening of
job portals (e.g. LinkedIn) for retrieving job offerings published by hiring
companies or personal job profiles and CVs [3].

However, even with advanced methods and tools for collecting such data,
further processing can be challenging. Especially when merging data stemming
from multiple sources, curating and cleaning the vast amount of records
captured regularly is crucial [4, p. 6]. For instance, a database might
contain current job postings targeting recruitment of freelancers for IT
projects that have been published on several job platforms in parallel and
which in fact relate to one single job reference. As of now, while many other
steps in the recruitment process can already be automated quite successfully,
the detection of such duplicates within unstructured textual data is not an
easy task to solve [5]. This is partially due to the fact that platform and
company specific constraints often result in similar, but not identical
postings for both: different job advertisements being part of the same
project, as well as job postings coming from the same company, but relating to
different projects [6].

For those reasons simple automated duplicate checks usually lead to a high
rate of false positives, which is why this task is often still solved in the
form of time consuming manual work. To address this problem and to provide a
useful programmatic solution, we investigated different methods of similarity
detection tailored to the specific goal of finding duplicates among the
textual contents of job postings.

Our key findings are that several approaches deliver good results, but only a
combination of text similarity matching with domain knowledge in the form of a
weighted skills averages and text embedding gives a very high score with few
false positives.

An application based on our duplicate detection approach was developed in a
economically viable way and has been successfully deployed as a live system
for the past months.

##  2 Industrial Use Case and Requirements

Recruiters deal with the matching of candidates with job positions, for
example finding a suitable IT freelancers for specific software development
projects. One task the recruiters need to perform consists in the curation of
a job listings database. Companies looking for IT freelancers often publish
open positions on many different web sites, in slightly different variations.
These open positions need to be aggregated and duplicates need to be
identified. This time-consuming process occurs mostly manually or with some
degree of automation that however is error prone and requires manual
oversight.

To give an idea of the difficulty of the task, some example borderline cases
can be named:

  * •

the same job posting may be published on two different sites with slightly
different wording in the title and text description,

  * •

the same company may be looking for two people for the same Java development
project, one for front-end and one for back-end, resulting in very similar
postings for different jobs or

  * •

the same employer may be looking for two Java developers in a project, one
working on site in the company offices, one being a remote working position.

These examples show that detecting duplicate job listings is hard to achieve
in a reliable way by simply matching basic data such as job title description
and company name, or only analyzing the required skills. A sophisticated
combination of several different criteria, however, can greatly increase the
detection performance.

As the project was conducted for a real-world use-case in cooperation with
Contractor Consulting GmbH111https://www.contractor.de, the goal was to have a
tool ready for production use. Because of this, some specific requirements
applied that may would not have been relevant in the setting of a larger
research project:

  * •

Both, the development and operation costs had to be limited in order to get a
viable business case. The development and usage of the resulting tool must be
cheaper than the labor cost of manually detecting duplicates, and the
additional costs generated by false detection (false positives/negatives). The
tool will be used in a semi-automated fashion, where listings marked as
duplicate, i.e. true and false positives, are reviewed by the recruiting
experts; while non-duplicates are processed automatically and no further
review or action is triggered. Therefore, in the context of
misclassifications, false positives pose less of an issue to the users than
false negatives due to the human review and feedback loop. The potential
savings generated by the new tool do not justify the development and usage of
large-scale solutions. Development effort was limited to about 15 to 20 person
days.

  * •

Additionally, the software shall have no licensing and hardware renting costs.
This means that using large cloud AI platforms or hardware-intensive large
language models was not an option.

  * •

Whenever possible, easy to understand and easy to maintain solutions should be
preferred, so as to ensure that the tool can be maintained by the end users.

These requirements constrained the scope of considered approaches and tools
used during the project, also excluding the fine-tuning of big language models
with curated data sets.

##  3 Related Work

Usage of AI solutions in recruitment processes is common and well documented,
though typically the task addressed is the analysis and review of applications
and resumes [7].

Some research has already addressed job descriptions. In [8], the authors show
how removing stop words and extracting relevant features from online job
description postings help in the detection of fake postings.

Works like [6] address the specific task of duplicate detection for online
recruitment using standard de-duplication techniques like Jaccard Similarity
and n-grams with limited success. Furthermore, [9] investigated different 24
methods for job duplicate detection, including usage of different tokenizers.
Another common use case from a different, yet still technical domain is the
detection of duplicates among free text bug reports, where in some cases
similar techniques have been applied [10] [11] However, extensive usage of
domain knowledge is not applied there.

Text comparison is a common task for which many approaches exist. However,
classic algorithms such as Levenshtein distance [12], TF-IDF [13] or longest
common subsequence (LCS) [14] are not suitable for our approach, as the job
listings contain many similar-looking text blocks on a word and character
basis, but are often very different in terms of meaning.

Gao et al. [15] use Word2Vec [16] embeddings to detect short text duplicates.
The usage of embeddings is clearly relevant to our work, job descriptions tend
to be long documents and thus require a different approach than the one
proposed by the authors.

Foltýnek et al. [17] provide a review of plagiarism detection methods, an area
related but not identical to our problem domain. The findings confirm that
using new machine learning techniques and a combination of approaches is most
promising.

Wang and Dong [18] give an overview of text similarity measurement techniques.
One main finding of the study that is relevant to the present work is the
confirmation that text matching is application and domain-specific, i.e.
dependent on the type of texts and on the task to be accomplished after the
similarity has been computed. In order to create performant solutions,
different algorithms need to be considered.

Overall, our overview of related work shows that though many approaches exist
for computing text document similarity, a selection of the most appropriate
one is always task and domain specific and thus needs to be reviewed for each
new project. The particularities of job descriptions texts and the project
requirements mentioned in the previous section lead us to conduct the
experiments described in the following chapters.

##  4 Data Resources

During the project phase we had access to a database with about 45.000
collected project tenders and according textual descriptions. The typical
content of a job description is well established and has already been studied.
[19] mention the main elements of such a text: a job title, required skills,
preferred skills and responsibilities. In our specific case and dataset, we
identified the following features as most relevant:

  * •

Title: The headline on top of the project proposition

  * •

Description: The text body describing the project and job requirements

Additionally, each project in the data set is identified by a unique project
ID. The description is the textual main body of the job posting and typically
consists of the following elements:

  * •

a short introduction text usually describing the company that is looking for a
freelancer,

  * •

the tasks to be accomplished – often in form of a bullet-point list,

  * •

requirements to be met by the potential candidate, for example years of
experience in a specific area, required hard and soft skills, etc.

  * •

general working information such as start and end date of the project, remote
or on-site position, or amount of hours of work expected

  * •

a short ending text describing the application process.

The exact elements and their order may vary from document to document.
Additionally, many postings contain additional ”glue” or ”boilerplate” text
added by the company or recruiting agency, which does not carry information
for our task, but can lead to false positive detections.

Besides the textual information that we get for each job offer, the data set
also contains some meta information for each sample like date of publishing,
which we use to limit matching candidates to a realistic time range in which
we expect duplicates of the same job to appear (e.g., a few weeks). Other
features like working place, duration (for freelancers that work on specific
projects this is usually already fixed in the job posting) and starting date
are also stored for every job posting. Although these structured features
could also be indicators for duplicates, during our pretesting we found them
to be misleading for many cases as well, since different projects and jobs
might share the same place or dates and some features are missing for some
candidates in the database. Even though such information might be useful for
the validation of detected duplicates, in our work we focus on comparing the
larger textual features mentioned before such as job description and title.

In addition to the job posting data, we had access to an (automatically
created) key word list containing the $25.000$ most frequent skills (occurring
at least seven times in resumes). Accompanied by the skill list we also
introduced a skill black list during the project phase with the aim to exclude
misleading or wrong entries in the skill list.

A small test set was manually annotated with $50$ duplicate-pairs identified
by Contractor. This test set exhibits the a high quality and was used only
used for final testing of the deployed pipeline. After the implementation of
the first version of the detection pipeline, we created a validation set by
annotating a set of $176$ job posting-pairs with corresponding predictions by
the pipeline. After curation, we ended up with $74$ duplicates and $73$ non-
duplicates. We refer to those $73$ non-duplicates also as fake-duplicates,
since they were labeled as duplicates by our algorithm and therefore exhibit
at least some degree of similarity to the matching source. $29$ of the
predictions could not be assigned confidently to one of the classes
(duplicate, non-duplicate) even after review from the domain experts and were
removed from the curated dataset. This validation set was used to fine-tune
the parameters and thresholds during development of the matching algorithms.

Figure 1: Example of job offering comparison for two different positions that
are part of the the same project. While the original description text has
greater parts of overlap in boiler plate text sections, the extracted pure
skill texts differ significantly. Yellow markings indicate overlapping text
parts between source and target texts. The censored parts mark confidential
information.

##  5 Method and Experimental Setting

###  5.1 Data Preprocessing

Before comparing job offerings with each other, the whole dataset (and
especially the textual contents) are preprocessed and cleaned: we remove
special characters such as line breaks or enumeration characters to receive a
normalized version of all texts – mainly containing letters, white spaces and
numbers. We make an exception for special characters like ’+’ or slashes that
can appear in technical skills (e.g. C++, S/4 Hana), which we keep in the text
corpus. Besides, similar to the approach proposed by Gunawan et al. [20], we
extract and lowercase all skill terms from the original description texts
based on the skill list and skill black list mentioned in the previous section
together with their weights (see Section ”Weighted Keyword Matching”). This
preprocessing is done for all further matching methods and score computations.

###  5.2 Evaluation Metrics

For measuring the quality of our matching algorithms, we resort to standard
metrics like Precision, Recall and F1-Score, which have proven to be reliable
indicators for duplicate detection tasks [21]. We compute them over all
matched pairs of project publication records in our data sets. In detail, we
handle a comparison result as true positive (TP) if an actual duplicate has
been detected successfully, and as false negative (FN) if this is not the
case. Similarly, non-duplicate pairs that have been assigned with a duplicate
label are treated as false positives (FP), while true negatives (TN) are all
pairs of correctly labeled non-duplicates. As proposed by previous works [22],
we use score dependent threshold values (TH) for the decision of label
assignment. Thus, if a matching pair sample gets assigned a score above the
threshold by an algorithm, it is labeled as a predicted duplicate, otherwise
it is assigned the non-duplicate prediction label. We use the validation set
containing both duplicates and fake-duplicate job pairs introduced in the
previous section as a development set for score and threshold optimization and
evaluate our final pipeline on the test set containing only known duplicate
pairs to ensure that our approach is valid for unseen data.

###  5.3 Overlap-based Similarity Matching

We use a simple Text Overlap Score computation, that computes the degree of
matching text blocks between two job publications and serves as a baseline for
all further experiments. In detail, the Python package _levenshtein_
222https://maxbachmann.github.io/Levenshtein/levenshtein.html is used to get
all larger text blocks (with minimum length of 15 characters) within the
source text that also appear in the target candidate of the current matching
pair.

We define $S$ as the source text and $T$ to be the target matching text. For
each overlapping block $i$, we define $b_{i}$ as its length. If there are a
total of $n$ overlapping blocks, the total length of overlapping text is:

$B=\sum_{i=1}^{n}b_{i}$

Then, the $TOS$ is calculated as follows:

$TOS=\frac{B}{\text{len}(S)}$

This means, we sum up the length of the overlapping string blocks (number of
overlapping characters) and normalize the result by dividing through the total
length of the source text to get a percentage value that indicates the degree
of overlap.

During our first pretest experiments using the overlap score, we found that
many of the job offering texts consist of larger blocks of boiler plate text
(such as introduction of the company or common contact information) that are
shared among different job offerings published by the same company or agency.
This results in high $TOS$ values for different job postings. On the other
hand, we identified other passages of the description text as most relevant
for distinguishing between job offers, specifically all sections containing
project-related skill requirements.

In Figure 1 we illustrate this finding with an example: The start and end of
the matching source text overlap in most parts with the target, while the
skill list indicates that in this case indeed different job offerings are
compared.

For this reason, besides computing a simple overlap score over the whole job
description text, we additionally compute a Skill Overlap Score ($SOS$) that
only considers matching blocks appearing in the concatenation of all listed
skill words and terms detected in the whole description text (see bottom of
Figure 1). These pure skill texts, representing the most specific parts of a
job offering, are extracted during the preprocessing phase by using the skill
list.

Note, that for each pair matched with the overlap scores we compute a forward
and a backward score, since the choice of source and target texts influences
the length of the resulting matching blocks. Therefore, the final $TOS$ is
calculated by taking the mean of the forward and backward pass:

$TOS_{\text{final}}=\frac{TOS_{\text{forward}}+TOS_{\text{backward}}}{2}$

The final Skill Overlap Score $SOS$ is computed analogously.

Figure 2: Overview of the different scoring approaches in their respective
matching classes and the final selected component of each class for the total
score. The components were selected by their performance on the validation
set.

###  5.4 Embedding-based Similarity Matching

In addition to the string overlap scores, we also test similarity matching
based on text embeddings in order to capture semantic similarities (e.g.
different wordings and phrases) not detected by the strict string matching
approach. In detail, since our data contained both German and English job
descriptions, we used a multilingual text encoding method as proposed by Yang
et al. [23] and provided by the pretrained model _distiluse-base-multilingual-
cased-v1_ 333https://www.sbert.net/docs/pretrained_models.html from the Python
library _sentence-transformers_ [24].

Embeddings for all data samples are computed during preprocessing and cached
for all further comparison actions. During pairwise matching of job
descriptions, we compute the Embedding Score ($ES$) with the commonly used
cosine similarity [25] between embedding vectors $S_{e}$ of source $S$ and
$T_{e}$ of target candidate $T$ as follows:

$ES=\text{cosine similarity}(S_{e},T_{e})=\frac{S_{e}\cdot
T_{e}}{\|S_{e}\|\|T_{e}\|}$

We then normalize the results by mapping (eventually appearing) negative
values to 0 (indicating no significant similarity between $S$ and $T$) for
ensuring comparability of scores.

Similar to the computation of the overlap scores, we calculate embedding
scores for different parts of the original job description:

  * •

Text Embedding Score ($TES$): Embedding over the whole job description text

  * •

Skill Embedding Score ($SES$): Embedding over the pure skill text
(concatenation of all found skill terms)

  * •

Title Embedding Score ($TTES$): Embedding over the headline of the job
description (retrieved from a separate feature in the data set)

  * •

All Text Embedding Score ($AES$): Embedding over concatenation of all texts
(title, description and skill text)

###  5.5 Weighted Keyword Matching

During the pretesting phase of the project, we found that skill terms
mentioned in job descriptions are key features regarding the task of duplicate
detection. On the other hand, since the list of relevant skills was created in
an automated manner, it also contains wrong or misleading keywords (examples
for that are ”English”, ”experience” or ”team work”) that are not indicating
real technical skill requirements for the job. Furthermore, very common terms
like ”Java”, that are occurring in a lot of job descriptions, are considered
as not helpful for finding duplicates. Although a skill black list as
introduced in the Data Resources section was used, manual capturing of all
misleading terms was not feasible within the scope of the project.

For those reasons and as proposed by other work like [20], we introduce
another matching approach: a Weighted Skill Score ($WSS$). In contrast to the
previous, presented scores which use the skill list to different degrees, the
$WSS$ focuses on the significance of individual skill keywords by taking into
account their relevance among the whole corpus of the data set. For that, we
calculate weights for every skill term in the skill list during preprocessing
by counting their occurrences in all project descriptions of the data set to
approximate a value of their significance. The weights are re-computed on a
regular basis, witch could also be done in an online manner while the system
is active and new project descriptions are added to the data base. This way
the system can continuously learn during its operation time. For a skill term
$s_{i}$ from the skill list, we define $f(s_{i})$ as its frequency in the
entire project database. Then, the weight of the skill term is:

$w(s_{i})=\frac{1}{f(s_{i})}$

During calculation of the weighted score for a matching pair, we take the
inverse of every precomputed skill term’s frequency because we assign more
frequent skill words less relevancy for duplicate detection than specific
skills that appear very seldom.

For a source text $S$ and a target candidate $T$, the Weighted Skill Score
$WSS$ is then calculated as follows:

$WSS=\frac{\sum_{s_{i}\in(S\cap T)}w(s_{i})}{\sum_{s_{i}\in S}w(s_{i})}$

The $WSS$ consists of the sum of weights of all skill terms found in both job
descriptions $S$ and $T$ divided by the sum of weights of all skills within
the source text of the matching pair.

Again, we perform a forward and backward pass by swapping $S$ and $T$ and use
the mean of both for the final weighted skill scores $WSS_{\text{final}}$:

$WSS_{\text{final}}=\frac{WSS_{\text{forward}}+WSS_{\text{backward}}}{2}$

###  5.6 Combined Matching

As a result of the experiments during a first pretesting phase, we deducted a
final combined Total Score ($TS$) that is calculated by averaging over the
three (best performing) individual scores – each coming from one of three
categories mentioned before. Figure 2 visualizes the score influences
contributing to our total score: we found that the skill related metrics
perform best during our tests, thus the $TS$ consists of the average of Skill
Overlap Score $SOS$, Skill Embedding Score $SES$ and Weighted Skill Score
$WSS$. In principal, all employed scoring methods are language and location
independent and have been applied to German and English job postings. For
better performance of the embedding methods, it is advised to use an
appropriate embedding model for the target language or a multilingual one.

##  6 Results and Discussion

###  6.1 Threshold Finding

To identify suitable thresholds for each score, we start visualizing the
prediction results for the different methods on the validation set with
duplicates and (similar looking) non-duplicates. Figure 3 shows those
predictions for every scoring method introduced in the previous section. Note
that, due to the constrained scope of the project, we set the threshold values
manually by human supervision to achieve a good prediction performance for
each scoring method. However, we use the same values for every method group to
preserve comparability. The thresholds are listed in Table 1 together with the
according score performance when applying these threshold values for
prediction on the validation set.

###  6.2 Experimental Results

Table 1: Experimental results for different matching score computations listed as Precision (P), Recall (R) and F1-Score (F1) of correctly recognized project duplicates on the validation set. TH indicates the threshold chosen for the specific score, and * the scores used to compute the Total Score ($TS$). Matching Score | TH | P | R | F1
---|---|---|---|---
Text Overlap ($TOS$) | 0.40 | 0.48 | 0.66 | 0.55
Skill Overlap ($SOS$) * | 0.40 | 0.89 | 0.66 | 0.76
Text Embedding ($TES$) | 0.50 | 0.52 | 0.81 | 0.63
Skill Embedding ($SES$) * | 0.50 | 0.66 | 0.97 | 0.79
Title Embedding ($TTES$) | 0.50 | 0.49 | 0.74 | 0.59
All Text Embedding ($AES$) | 0.50 | 0.57 | 0.95 | 0.71
Weighted Skill ($WSS$) * | 0.20 | 0.84 | 0.97 | 0.90
Total Score ($TS$) | 0.35 | 0.89 | 0.99 | 0.94

Comparing the performance of individual scores, Table 1 and Figure 3 indicate
that using the text overlap ($TOS$) and embedding score ($TES$) over the whole
description texts is not sufficient for discriminating between real and fake
duplicates. This is also due to the already mentioned existence of overlapping
boilerplate text: some texts originate from the same company or even project,
but indeed advertise different jobs. When concentrating on the skill text
containing only relevant technical terms specific for a given job offer by
using the $SOS$ and $SES$ metrics, performance increases significantly.

In contrast, relying on the individual result of the title score $TTES$ is not
helpful. Although in the beginning we expected the headline of a job offering
to be a meaningful indicator for duplicate references, we realized that these
texts without any further context are also highly misleading, since a lot of
independent companies and projects use the same wording and technical terms
(e.g. ”SAP developer wanted”) when publishing job postings. Even combining the
title and skill text with the original job description text in the all text
embedding approach ($AES$) cannot deliver good performance. Overall, one of
our key findings was that – although they achieve the highest prediction
scores for real duplicate pairs – all of our embedding approaches in general
seem not to be capable of separating fake duplicates from real ones, as the
corresponding plots in Figure 3 underline.

On the other hand, only using the weighted skill score ($WSS$) without
combining with any other measure already performs well. The fact that we
attribute weights to significant skill features allows reliable detection of
fake duplicates, since in contrast to the other metrics the influence of
overlapping (but maybe misleading) boilerplate text on the prediction is
reduced. Note that a requirement for the productive usage of this score
computation is the continuous update of the underlying skill weights to
capture the relevance of new terms and wordings that might arise over time.

With combining the most promising individual scores of each group (namely the
skill based scores) to form the total score $TS$, we can improve the
performance on the validation set to an F1 score of $0.94$, meaning that most
of the comparison pairs could be classified correctly into duplicates and non-
duplicates. We believe that assembling our scoring method in this way allows
us to compensate weaknesses of individual scores and to create more reliable
and stable prediction results, as shown before [26].

During the final phase of the project, we applied this optimized setting to
the test set consisting of $50$ samples which are exclusively real duplicate
pairs. Since there are no non-duplicates in this dataset, the final test
before productive deployment ensures that the constructed total score can
identify the actual duplicates well by assigning them a relatively high score.
Although there was a clearly visible scatter among predictions with a $TS$
ranging from $0.24$ to $0.93$, we could identify some indicators of similarity
for every test sample, indicating the potential for further fine-tuning of the
$TS$. For a threshold of $0.2$, all of the real duplicates would have been
detected. After feedback from the project partner, however, thresholds were
not set to the optimal operating point for the (rather small) test set, but to
a more robust value (see next section) for the final productive deployment.
This threshold choice implies more importance to specificity (i.e. low false
alarm rate) at the cost of sensitivity.

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

Figure 3: Score predictions for the different methods on the test set with 74
duplicates and 73 non-duplicates. The thresholds are set manually for each
score to gain a good distinction between positive and negative duplicate
predictions.

##  7 Productive Deployment

After the experimental evaluation, the duplicate detection framework in
deployed in production with periodic checks for recently published and
collected job descriptions. In terms of scalability, once the initial vector
database for the document embeddings is generated, the computational cost and
time scales linearly in the number of processed documents. Since only a fixed
time frame is compared to a new job posting, the number of comparisons can in
fact vary but does not scale with the size of the dataset.

For the deployed system, the thresholds for the score computations were
adapted and an additional criteria introduced: the $TS$ threshold is set to
$0.6$ and each individual scoring method must achieve a minimum value of $0.1$
in order to classify a pair as duplicates. With this setting, $58.860$
published job descriptions were analyzed and matched during a first productive
phase of six months, of which $33.865$ were found to be no duplicates and
$24.995$ to be duplicates of other projects. In detail, for every sample
predicted as a duplicate we identified about $2.5$ duplicate job offerings on
average. This implies that the $24.995$ duplicate predictions contain about
$10.000$ unique job postings, leading to a total sum of $43.705$ postings
identified as unique within this period of time. Overall, the positive
feedback given by the end users of the tool after several months of productive
usage confirm that our solution is working as intended and validates our
approach.

##  8 Limitations

As stated by Draisbach and Naumann [27], choosing thresholds on a small test
set of samples might not scale appropriately when the data set gets larger.
Therefore, future experiments on larger (labeled) test sets are necessary for
a more generalizable threshold estimation. This was however not possible in
the scope of this work, due to the nature of requiring high-quality labeled
data, which had to be collected manually by recruiting experts during the data
collection phase of the project.

An additional source of improvement is a more sophisticated determination of
the weights assigned to the individual metrics that form the Total Score
($TS$). The assumption, that individual scoring approaches carry more
information than others to solve a task in a specific domain, is reasonable
and was also shown in [26].

##  9 Conclusion and Future Work

Our work showed that for duplicate detection in real world scenarios, like
detecting clones of job descriptions, the integration of domain specific
expert knowledge is crucial. While applying standard matching algorithms like
string similarity and embedding comparison only leads to limited performance,
we pointed out that combining these approaches with context specific additions
– in our case the emphasis of significant skill terms – achieves satisfactory
results (F1-score of 0.94) regarding capabilities for productive deployment.
For future work, we plan to do a larger evaluation on bigger (human-curated)
test sets to identify possible weak points of our approach that could not be
addressed within the limited scope of this first project.
Furthermore, as large language models (LLMs) become more advanced even in not
explicitly shown domains, they can be used as a baseline classifier in zero-
or many-shot evaluations. This allows for a more comprehensive evaluation,
with the LLM serving as a proxy for a human evaluator. Additionally, available
LLMs can be fine-tuned on the recruiting domain and used as an additional
scoring method, either in parallel or incorporated as on component in the
Total Score ($TS$). However, this raises the challenge of keeping the tool
computationally efficient, as SOTA LLMs are quite expensive to operate. [28]
Incorporating feedback mechanisms for users is currently done in an offline
fashion by utilizing their feedback on classification performance to re-
calibrate the thresholds over time. This could also be done automatically at
predefined intervals or by using distribution shift [29] or performance
monitoring approaches [30].

Disclosure of Interests The authors have no competing interests to declare
that are relevant to the content of this article.

## References

  *   * Donovan [2017] Donovan, K.: Automated recruiting and the human factor. ManpowerGroup Solutions (2017)
  * Leong [2018] Leong, C.: Technology & recruiting 101: how it works and where it’s going. Strategic HR Review 17(1), 50–52 (2018)
  * Kong et al. [2021] Kong, Y., Xie, C., Wang, J., Jones, H., Ding, H.: Ai-assisted recruiting technologies: Tools, challenges, and opportunities. In: Proceedings of the 39th ACM International Conference on Design of Communication, pp. 359–361 (2021)
  * Draisbach [2022] Draisbach, U.: Efficient duplicate detection and the impact of transitivity. PhD thesis, Universität Potsdam (2022)
  * Ramya et al. [2016] Ramya, R., Venugopal, K., Iyengar, S., Patnaik, L.: Feature extraction and duplicate detection for text mining: A survey. Global Journal of Computer Science and Technology: C Software & Data Engineering 16(05) (2016)
  * Burk et al. [2017] Burk, H., Javed, F., Balaji, J.: Apollo: Near-duplicate detection for job ads in the online recruitment domain. In: 2017 IEEE International Conference on Data Mining Workshops (ICDMW), pp. 177–182 (2017). IEEE
  * Chan et al. [2022] Chan, L., Hogaboam, L., Cao, R.: Artificial Intelligence in Human Resources, pp. 139–155. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-05740-3_9
  * Vo et al. [2021] Vo, M.T., Vo, A.H., Nguyen, T., Sharma, R., Le, T.: Dealing with the class imbalance problem in the detection of fake job descriptions. Computers, Materials & Continua 68(1), 521–535 (2021)
  * Zhao et al. [2022] Zhao, Y., Chen, H., Mason, C.M.: A framework for duplicate detection from online job postings. In: IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology. WI-IAT ’21, pp. 249–256. Association for Computing Machinery, New York, NY, USA (2022). https://doi.org/10.1145/3486622.3493928
  * Sureka and Jalote [2010] Sureka, A., Jalote, P.: Detecting duplicate bug report using character n-gram-based features. In: 2010 Asia Pacific Software Engineering Conference, pp. 366–374 (2010). https://doi.org/10.1109/APSEC.2010.49
  * Tian et al. [2012] Tian, Y., Sun, C., Lo, D.: Improved duplicate bug report identification. In: 2012 16th European Conference on Software Maintenance and Reengineering, pp. 385–390 (2012). https://doi.org/10.1109/CSMR.2012.48
  * Levenshtein [1966] Levenshtein, V.I.: Binary codes capable of correcting deletions, insertions, and reversals. In: Soviet Physics Doklady, Vol. 10, No. 8, pp. 707–710 (1966)
  * Sparck Jones [1972] Sparck Jones, K.: A statistical interpretation of term specificity and its application in retrieval. In: Journal of Documentation, vol. 28, pp. 11–21 (1972)
  * Maier [1978] Maier, D.: The complexity of some problems on subsequences and supersequences. J. ACM 25(2), 322–336 (1978) https://doi.org/10.1145/322063.322075
  * Gao et al. [2017] Gao, J., He, Y., Zhang, X., Xia, Y.: Duplicate short text detection based on word2vec. In: 2017 8th IEEE International Conference on Software Engineering and Service Science (ICSESS), pp. 33–37 (2017). https://doi.org/10.1109/ICSESS.2017.8342858
  * Mikolov et al. [2013] Mikolov, T., Chen, K., Corrado, G., Dean, J.: Efficient estimation of word representations in vector space. In: 1st International Conference on Learning Representations, ICLR 2013, Scottsdale, Arizona, USA, May 2-4, 2013, Workshop Track Proceedings (2013). http://arxiv.org/abs/1301.3781
  * Foltýnek et al. [2019] Foltýnek, T., Meuschke, N., Gipp, B.: Academic plagiarism detection: A systematic literature review. ACM Comput. Surv. 52(6) (2019) https://doi.org/10.1145/3345317
  * Wang and Dong [2020] Wang, J., Dong, Y.: Measurement of text similarity: A survey. Information 11(9) (2020) https://doi.org/10.3390/info11090421
  * Park et al. [2009] Park, J.-r., Lu, C., Marion, L.: Cataloging professionals in the digital environment: A content analysis of job descriptions. Journal of the American Society for Information Science and Technology 60(4), 844–857 (2009) https://doi.org/10.1002/asi.21007 https://asistdl.onlinelibrary.wiley.com/doi/pdf/10.1002/asi.21007
  * Gunawan et al. [2018] Gunawan, D., Sembiring, C., Budiman, M.A.: The implementation of cosine similarity to calculate text relevance between two documents. In: Journal of Physics: Conference Series, vol. 978, p. 012120 (2018). IOP Publishing
  * Bilenko and Mooney [2003] Bilenko, M., Mooney, R.J.: On evaluation and training-set construction for duplicate detection. In: Proceedings of the KDD-2003 Workshop on Data Cleaning, Record Linkage, and Object Consolidation, pp. 7–12 (2003). Citeseer
  * Ektefa et al. [2011] Ektefa, M., Jabar, M.A., Sidi, F., Memar, S., Ibrahim, H., Ramli, A.: A threshold-based similarity measure for duplicate detection. In: 2011 IEEE Conference on Open Systems, pp. 37–41 (2011). https://doi.org/10.1109/ICOS.2011.6079233
  * Yang et al. [2019] Yang, Y., Cer, D., Ahmad, A., Guo, M., Law, J., Constant, N., Abrego, G.H., Yuan, S., Tar, C., Sung, Y.-H., et al.: Multilingual universal sentence encoder for semantic retrieval. arXiv preprint arXiv:1907.04307 (2019)
  * Reimers and Gurevych [2020] Reimers, N., Gurevych, I.: Making monolingual sentence embeddings multilingual using knowledge distillation. CoRR abs/2004.09813 (2020) 2004.09813
  * Singhal et al. [2001] Singhal, A., et al.: Modern information retrieval: A brief overview. IEEE Data Eng. Bull. 24(4), 35–43 (2001)
  * Engelbach et al. [2023] Engelbach, M., Klau, D., Scheerer, F., Drawehn, J., Kintz, M.: Fine-tuning and aligning question answering models for complex information extraction tasks. In: Accepted for KDIR 2023 - 15th International Conference on Knowledge Discovery and Information Retrieval (2023)
  * Draisbach and Naumann [2013] Draisbach, U., Naumann, F.: On choosing thresholds for duplicate detection. In: Proceedings of the 18th International Conference on Information Quality, ICIQ 2013, Little Rock, AR, USA, November 7-9, 2013 (2013)
  * Samsi et al. [2023] Samsi, S., Zhao, D., McDonald, J., Li, B., Michaleas, A., Jones, M., Bergeron, W., Kepner, J., Tiwari, D., Gadepally, V.: From words to watts: Benchmarking the energy costs of large language model inference. In: 2023 IEEE High Performance Extreme Computing Conference (HPEC), pp. 1–9 (2023). https://doi.org/10.1109/HPEC58863.2023.10363447
  * Rabanser et al. [2019] Rabanser, S., Günnemann, S., Lipton, Z.: Failing loudly: An empirical study of methods for detecting dataset shift. In: Advances in Neural Information Processing Systems, vol. 32 (2019)
  * Ginart et al. [2022] Ginart, T., Jinye Zhang, M., Zou, J.: Mldemon: Deployment monitoring for machine learning systems. In: Camps-Valls, G., Ruiz, F.J.R., Valera, I. (eds.) Proceedings of The 25th International Conference on Artificial Intelligence and Statistics. Proceedings of Machine Learning Research, vol. 151, pp. 3962–3997 (2022). https://proceedings.mlr.press/v151/ginart22a.html


# Privacy Guarantees for De-identifying Text Transformations

###### Abstract

Machine Learning approaches to Natural Language Processing tasks benefit from
a comprehensive collection of real-life user data. At the same time, there is
a clear need for protecting the privacy of the users whose data is collected
and processed. For text collections, such as, e.g., transcripts of voice
interactions or patient records, replacing sensitive parts with benign
alternatives can provide de-identification. However, how much privacy is
actually guaranteed by such text transformations, and are the resulting texts
still useful for machine learning?

In this paper, we derive formal privacy guarantees for general text
transformation-based de-identification methods on the basis of _Differential
Privacy_.

We also measure the effect that different ways of masking private information
in dialog transcripts have on a subsequent machine learning task. To this end,
we formulate different masking strategies and compare their privacy-utility
trade-offs. In particular, we compare a simple redact approach with more
sophisticated word-by-word replacement using deep learning models on multiple
natural language understanding tasks like named entity recognition, intent
detection, and dialog act classification. We find that only word-by-word
replacement is robust against performance drops in various tasks.

Index Terms: Differential privacy, Spoken language understanding, Named entity
recognition, Intent detection.

##  1 Introduction

Machine learning approaches, in particular Deep Learning, dominate many areas
of Natural Language Processing (NLP). To reach peak performance, they require
large data sets to train models. It is thus common to continuously collect
user data after a model has been deployed in order to augment existing
training data. This practice raises a clear need for protecting the privacy of
the users whose data are collected. For instance, commercial providers of
voice assistants have been criticized for recording and transcribing
conversations of their
users111https://www.bloomberg.com/news/articles/2019-04-10/is-anyone-
listening-to-you-on-alexa-a-global-team-reviews-audio. But other domains are
affected as well, for instance, patients’ health records in medical
applications.

For text collections, one way to respect the users’ privacy is to sanitize
each document through a de-identification process before adding it to a data
collection. De-identification requires to either delete all sensitive
information in a text, or to replace it with benign surrogates. 11todo:
1Insert citations. Arguably, strict deletion is the less desirable option
because without an indication of where the edit was made, texts can become
impossible to understand or, perhaps worse, change their meaning. To
illustrate, consider the following example from the medical domain, where the
names of specific medications are considered sensitive information:

  1. (1)

Besides warfarin, the patient is not taking any medication.

  2. (2)

Besides, the patient is not taking any medication .

A more commonly used alternative to deletion is redaction, where relevant text
portions are blackened rather than deleted, but this can still impact
readability. For instance, when dates, times, and locations are considered
sensitive with respect to a person’s whereabouts, a sentence such as (3) would
be rather useless in a text corpus in its redacted form (4):

  1. (3)

How about Rick’s Café around noon on the 15th ?

  2. (4)

How about Rick’s Café around noon on the 15th ?

This example illustrates that de-identification can imply a trade-off between
_privacy_ and _utility_. In order to gauge the latter, Tang et al. measure the
impact of three alternative methods for masking sensitive words on a
subsequent machine learning task [1]. The methods consist of two different
ways of replacing words with other, randomly selected words from the same
category, and of a method for replacing words with a specific category marker.
Applying these strategies to the previous example could lead e.g. to the
sentences in (5) and (6) respectively:

  1. (5)

How about London around 4 o’clock on the 3rd of May ?

  2. (6)

How about $<$LOCATION$>$ around $<$TIME$>$ on $<$DATE$>$?

However, Tang et al. [1] do not give any formal privacy guarantees for their
methods, making it difficult to judge the privacy-utility trade-off.

In this paper, we fill this gap by deriving formal privacy guarantees for
general text transformation-based de-identification methods on the basis of
_Differential Privacy_ , a well-established framework for quantifying privacy
leakage [2]. In addition, we show the impact of five different text
transformation strategies on three common NLP tasks, when the transformed
texts are used as training data for machine learning approaches. Unlike Tang
et al., we perform our experiments on six different corpora to gain more
balanced evidence.

##  2 Related Work

Text de-identification, also known as sanitization, is well established in
highly sensitive domains, such as e.g., for patient health records [3]. A
large number of de-identification methods have been suggested in that area in
the past e.g. [4, 5, 6]. While such methods are important for a number of
domains, we focus here on the privacy issues associated with cloud-based
dialog systems, such as e.g. [7], which are generally acknowledged (e.g. [8])
but have not yet received wide-spread attention.

In contrast, the necessity for protecting private information has long been
realized in the data mining community [8]. Our task is, however, quite
different from data mining. For instance, data mining transformations
oftentimes pay special attention to the preservation of certain statistical
properties of the underlying data, which is not a primary concern in our work,
thus allowing us to explore simpler approaches.

Probably the closest work to ours is [1] where the impact of data sanitization
has been investigated on Automatic Speech Recognition (ASR) and call
classification tasks. It has been shown there that the spoken dialog system
trained on sanitized data achieves a comparable accuracy. In contrast, we
apply text replacement to Natural Language Understanding (NLU) tasks and show
that some replacement strategies can have a large destructive effect on the
performance of the model. We verify this by applying a state-of-the-art deep
learning model to train the NLU tasks by fine-tuning BERT [9] embeddings on
three tasks that include named entity recognition, intent detection and dialog
act classification.

Recently, Carrell et al. [10] proposed an attack to leak sensitive information
in a transformed text, however, this attack only works on a small dataset. The
attack does not scale to large datasets because it requires the attacker to
perform annotation of private tokens, which is costly and tedious.

##  3 Privacy

A general framework for protecting privacy is Differential Privacy (DP)
introduced in [11]. DP quantifies to what extent privacy in statistical
queries is preserved while extracting useful information from a dataset and
has received increasing attention recently as a rigorous privacy methodology.
In this section, we clarify the connection between DP and text replacement
methods but first provide some technical background on general DP.

Let $\mathcal{D}$ be the set of all possible datasets for a given domain of
data points. A key concept in DP is neighboring datasets. We call two datasets
$D_{1},D_{2}\in\mathcal{D}$ neighboring if they are the same except for one
data point. For example, $D_{1}$ and $D_{2}$ could be two text corpora which
differ only in one single word. The intuition behind differential privacy, as
defined below, is a guarantee that a randomized algorithm behaves similarly on
similar input datasets to a point where the output of the algorithm does not
allow to infer which dataset was used with any relevant degree of certainty.
Therefore, an attacker cannot tell whether the aforementioned data point is
contained in the algorithm’s dataset or not.

######  Definition.

(Differential Privacy). A randomized algorithm $\mathcal{M}$ is
$(\varepsilon,\delta)$ private with domain $\mathcal{D}$ if for all measurable
sets $S\in\text{Range}(\mathcal{M})$ and for all neighboring datasets $D_{1}$
and $D_{2}$ differing in at most one data point, we have

$\Pr[\mathcal{M}(D_{1})\in S]\leq\exp{(\varepsilon)}\Pr[\mathcal{M}(D_{2})\in
S]+\delta\vspace{-1mm}$ (1)

Intuitively, a $(\varepsilon,\delta)$ differential private mechanism
guarantees that the absolute value of privacy leakage will be bounded by
$\varepsilon$ with probability at least $1-\delta$ for adjacent datasets. The
higher the value of $\varepsilon$, the higher the chance of data re-
identification.

Input: dataset $\mathcal{D}$, token replacement policy $\pi$, probability
parameter $p$.

for  _$t^{\prime}$ in sensitive data_ do

$r\sim U(0,1)$ if  _$r\leq p$_ then

replace $t^{\prime}$ with $t\sim\pi(t|t^{\prime})$

end if

end for

Algorithm 1 Probabilistic Text De-identification

To define a general algorithm for de-identification, let $\mathcal{T}$ denote
the vocabulary of private tokens and consider a token replacement policy
$\pi:\mathcal{T}\longrightarrow\mathcal{T}$, where $\pi(t|t^{\prime})$ is the
probability of replacing $t^{\prime}$ in the original text with $t$. We
introduce a parameter $p$ to model the probability that a token gets replaced:

######  Lemma.

If token replacement policy $\pi$ in the algorithm is independent of the token
to replace, i.e. $\pi(t|t^{\prime})=\pi(t)$, the algorithm is
$(\varepsilon,0)$ differentially private with:

$\varepsilon=\max_{t}\log\frac{1-p+p\,\pi(t)}{p\,\pi(t)}.\vspace{-1mm}$ (2)

To prove it, we consider two neighboring datasets $D_{1}$ and $D_{2}$, which
are the same except in one token. In other words, $D_{2}$ can be obtained from
$D_{1}$ by replacing a token $t_{1}$ in $D_{1}$ with $t_{2}$. Using this
notation, we may compute the privacy loss as follows. Let

$\varepsilon=\log\frac{\Pr[t\in\mathcal{M}(D_{1})]}{\Pr[t\in\mathcal{M}(D_{2})]}$
(3)

where $\mathcal{M}(D)$ is the dataset obtained by applying the de-
identification algorithm to the original dataset $D$, and $t$ is the observed
token in the resulting text. If $t_{1}$ and $t_{2}$ are not equal to $t$
(i.e., $t_{1}$ and $t_{2}$ are replaced by $t$), we have :

$\frac{\Pr[t\in\mathcal{M}(D_{1})]}{\Pr[t\in\mathcal{M}(D_{2})]}=\frac{p\,\pi(t|t_{1})}{p\,\pi(t|t_{2})}=1$
(4)

where we have used this fact that replacement policies are independent of the
original tokens. On the other hand, if $t$ is equal to $t_{1}$, we arrive at
the following expression for the privacy loss:

$\frac{\Pr[t\in\mathcal{M}(D_{1})]}{\Pr[t\in\mathcal{M}(D_{2})]}=\frac{1-p+p\,\pi(t)}{p\,\pi(t)}.$
(5)

We get the inverse of this expression in the opposite case $t=t_{2}$. The
overall privacy bound is given by the maximum of (4) and (5) over the private
tokens as stated in (2). ∎

The algorithm is a variant of randomized response [12] whose connection to
differential privacy has been studied before (e.g. [2, 12, 13]), although not
in the context of text de-identification. The probability parameter $p$ gives
data curators fine-grained control over the privacy-utility trade-off: an
ideal text replacement, corresponding to $p=1$, has zero privacy loss
($\epsilon=0$) but in cases where the replacement noise harms the performance
of models trained on the resulting data too much, the curator might choose to
use a lower probability $p$ if reduced privacy is deemed acceptable. Our lemma
allows to quantify this effect and compare different de-identification
options.

In practice, $p=1$ cannot be achieved very easily if the sensitive tokens are
identified automatically as in e.g. [1]’s and our own experiments below.
Instead, the recall value of the employed identification method defines an
upper bound for $p$, e.g., a recall value of $0.8$ implies that an expected
$20\%$ of the sensitive tokens will not be replaced. As $p$ approaches $0$,
the $\epsilon$ value approaches infinity, meaning that no privacy is provided.

In order to interpret our result, we consider the case where an attacker gets
hold of the fully transformed data set. The level of privacy expressed by the
lemma refer to the possibility of reversing the replacement in order to
reconstruct the source from a transformed sentence, which is difficult when
the privacy loss is small. Context information might be helpful, but in
general, original tokens can only be guessed according to their prior
probabilities which we assume to be uniform in this paper. However, the
algorithm allows for certain sentences to appear in the output untransformed,
either because of the value of the randomized response value $r$, or when the
randomly chosen replacement token happens to be identical to the source token.
The privacy guarantee given by our lemma arises from the fact that transformed
and untransformed sentences are not obviously distinguishable. In fact, the DP
parameter, $\epsilon$ can be seen as a measure of the certainty with which an
attacker can judge whether a sentence from the output was actually part of the
source text.

Referring to a specific instance of the above algorithm, i.e. a fixed choice
for $p$ and $\pi$ (called a text replacement _strategy_), with tokens being
either single words or multi-word expressions, we examine some straight-
forward replacement strategies and the level of privacy they present in the
light of our results.

Redact

Here, the private tokens are replaced with a non-word placeholder that is
typically not part of the vocabulary of the source text e.g.IIIII. Hence, we
only fall into case (4) above, implying $\epsilon=0$ under the interpretation
outlined above: an attacker can decide with certainty which of the tokens were
part of the original text but cannot infer the replaced tokens.

Typed placeholder (aka value-class membership [1])

This is akin to using private category markers like LOCATION as the
replacement token. This is a strategy similar to redaction, providing the same
level of privacy. However, it provides additional information about a replaced
token’s category and might thus be more useful than redaction for certain NLP
tasks.

Named placeholder

A fixed category exemplar is used to replace all private tokens of that
category [14], e.g, all locations are replaced by “London”. This strategy
makes it slightly more difficult to judge which sentence was transformed and
which was not, i.e. $\epsilon>0$. But for all instances that differ from the
exemplar, it is clear that they must have been part of the source.

Word-by-word replacement

We can distinguish between value distortion [1] if the replacement tokens are
from an external source, and value dissociation [1] when the surrogate tokens
are from the same corpus. The latter keeps the distribution of tokens in the
resulting document unchanged, which might be relevant for some tasks. Both
variants make it hard to identify untransformed sentences, which is reflected
in lower $\epsilon$ values.

Full entity replacement

Text coherence could be improved if source tokens were consistently replaced
by the same surrogates. However, this case is not supported by our lemma where
we require $\pi(t|t^{\prime})=\pi(t)$. Another downside of the word-by-word
strategy is that multi-word expressions could lead to nonsensical
replacements, e.g. “Frankfurt Airport” could be transformed to “New
Francisco”. A variant is thus to replace full entities instead of single
words. In terms of what can be captured by our lemma, this does not lead to
more privacy, but the expected gain in coherence might benefit downstream
tasks.

Table 1: Examples of the replacement strategies, using color codes for PER,
LOC, ORG, and TIME.

Replacement strategy |  Transformed text
---|---
No Replacement |  Hi Mister Miller, the Lufthansa flight from Frankfurt Airport to Rome is leaving by six pm
Redact |  Hi Mister IIIII, the IIIII flight from IIIII to IIIII is leaving by IIIII
Typed-Placeholder |  Hi Mister PER , the ORG flight from LOC to LOC is leaving by TIME
Named-Placeholder |  Hi Mister Smith, the SAP flight from London to London is leaving by afternoon
Word by word |  Hi Mister John, the BOSCH flight from New Boston to Berlin is leaving by eleven morning
Full entity |  Hi Mister John, the BOSCH flight from New York to Berlin is leaving by twelve pm

Table 2: Evaluation of the different token replacement strategies on the 6
datasets comprising of 3 tasks: NER, ID, DAC. Average performance computed
from ten runs. The best Accuracy/F1-score in each class/task are in bold and
the best text transformation result have asterisk (*). The replacement
strategies use ground-truth annotations for the identification of sensitive
tokens, i.e. $p=1,\varepsilon=0$.

Replacement strategy | VerbMobil NER F1-score | ATIS ID Accuracy | SNIPS ID Accuracy | en-TOD ID Accuracy | Restaurant DAC Accuracy | Taxi DAC Accuracy
---|---|---|---|---|---|---
No replacement | $\mathbf{88.3\pm 0.2}$ | $\mathbf{98.4\pm 0.2}$ | $\mathbf{98.0\pm 0.2}$ | $\mathbf{99.4\pm 0.0}$ | $\mathbf{78.9\pm 0.1}$ | $\mathbf{90.0\pm 0.1}$
Redact | $0.2\pm 0.2$ | $94.8\pm 0.2$ | $89.7\pm 0.8$ | $97.4\pm 0.6$ | $75.9\pm 0.3$ | $88.1\pm 0.2$
Typed-Placeholder | $0.0\pm 0.0$ | $95.7\pm 0.3$ | $54.1\pm 3.8$ | $97.2\pm 0.7$ | $76.5\pm 0.2$ | $87.9\pm 0.5$
Named Placeholder | $13.5\pm 1.4$ | $95.9\pm 0.3$ | $76.2\pm 2.9$ | $98.2\pm 0.1$ | $77.3\pm 0.2$ | $89.3\pm 0.1$
Word-by-Word | $72.6\pm 0.3$ | $\mathbf{98.6\pm 0.2}^{*}$ | ${97.5\pm 0.3}^{*}$ | ${99.2\pm 0.1}^{*}$ | $78.4\pm 0.2$ | ${89.9\pm 0.2}^{*}$
Full Entity | ${85.9\pm 0.3}^{*}$ | $\mathbf{98.5\pm 0.2}^{*}$ | ${97.4\pm 0.3}^{*}$ | ${99.2\pm 0.1}^{*}$ | ${78.5\pm 0.1}^{*}$ | ${89.9\pm 0.1}^{*}$

An example for each of these replacement strategies is given in Table 1.
Besides discussing privacy aspects, we have speculated on the differences of
the strategies on subsequent applications. In order to verify these
considerations, we now measure the impact of the different replacement
strategies empirically.

##  4 Utility

We experiment with three common NLP tasks, Named Entity Recognition (NER),
Intent Detection (ID), and Dialog Act Classification (DAC), across six
different datasets (see Table 3). The variety in datasets is important since
what is considered sensitive information is typically domain-dependent. Here,
we consider as private: (1) the identity of one or both speakers, (2)
organizations, such as e.g., company names, etc. (3) The locations or
addresses (4) The dates and times. This private information coincides with
typical named entities (NEs) and slot classes in dialog datasets such as PER
(personal names), ORG (organization), LOC (location), DATE and TIME.

###  4.1 Datasets

Table 3: Dataset summary for three different tasks: Named Entity Recognition (NER), Intent Detection (ID), and Dialog Act Classification (DAC) Dataset | Task | Private | Classes | Train | / | Val. | / | Test
---|---|---|---|---|---|---|---|---
|  | Tokens |  | Sentences
VerbMobil | NER | 5 NEs | 6 | 19K | / | 2848 | / | 5230
ATIS | ID | 21 slots | 21 | 4478 | / | 500 | / | 893
SNIPS | ID | 39 slots | 7 | 13K | / | 700 | / | 700
FB en-TOD | ID | 15 slots | 12 | 30K | / | 4181 | / | 8621
MS Restaurant | DAC | 21 slots | 24 | 20K | / | 2936 | / | 5859
MS Taxi | DAC | 10 slots | 18 | 16K | / | 2273 | / | 4597

The Verbmobil corpus is a large collection of spontaneous telephone
conversations [15]. In each conversation, two speakers negotiate the details
of a business meeting. The corpus contains English, German, and Japanese
conversations, however, we only use English portion of the corpus for our
experiments. The Verbmobil corpus does not come pre-annotated with NE classes.
About 20% of the Verbmobil corpus was thus annotated via crowd sourcing. The
remaining 80% of the corpus was annotated automatically using spaCy
222https://spacy.io and post-corrected manually.

The ATIS [16] corpus is a popular dataset for slot filling and intent
detection tasks in the Air Travel Information Services domain. For the text
transformation experiments, we map the provided slot labels to the
aforementioned named entity categories.

SNIPS is another popular benchmark dataset for slot filling and intent
detection task by SNIPS.AI [17]. The dataset consists of seven intents from
different domains such as “AddToPlaylist”, “BookRestaurant”, “GetWeather”,
“RateBook”.

FB en-TOD is a multilingual slot and intent classification dataset recently
released by Facebook [18]. It consists of utterances from three languages
(English, Spanish, and Thai) and three domains (Alarm, Reminder, and Weather).
In this paper, we only use the English dataset.

MS Taxi and MS Restaurant are two out of three dialog challenge datasets
released by Microsoft at the SLT 2018 workshop [19] for taxi bookings and
restaurant reservations with 19 and 29 slot types respectively and 11 dialog
acts. The number of classes for the Taxi and Restaurant datasets are 18 and 24
respectively after removing classes with less than 40 utterances.

###  4.2 Experiments

For all comparison experiments, we first run a baseline experiment using the
original datasets. Then, we apply the respective privacy strategies to the
training data before fine-tuning a BERT model for token/sentence
classification. We then compare the performance of the resulting models with
the baseline with respect to the (untransformed) test set. The BERT
classification model involves fine-tuning the pre-trained BERT embeddings on
the training data with an additional linear layer whose weights are randomly
initialized. We trained all the parameters of the model end-to-end, including
the linear layer.

For the implementation, we fine-tuned BERT on the various tasks using the
simpletransformers333https://github.com/ThilinaRajapakse/simpletransformers
based on the transformers library of HuggingFace [20]. The hyper-parameters of
the model are 768-dimensional embedding layer (for bert-base-cased model),
batch size of 8 for NER and 16 for other tasks, maximum learning rate of
$0.00005$, maximum sequence length is 128 for NER and 64 for other tasks. The
maximum number of epochs for all experiments is 3.

Figure 1: Connection between DP (privacy), Replacement probability $p$, and
F1-score (performance) on Verbmobil.

###  4.3 Results

We show that the performance of the redact and word-by-word replacement
strategies can be improved by tuning the parameter $p$ described in Section 3.
For example, by setting $p=0.9$ (i.e. $\epsilon=6.75$), we can improve the
F1-score by around $4\%$ for word-by-word and $60\%$ for redact as shown in
Figure 1, demonstrating the ability to control the privacy-utility trade-off.
In the word-by-word replacement experiments, we replace a NE word $t^{\prime}$
by another word $t$ of the same entity class based on their relative frequency
distribution $\pi(t)$ in the corpus.

The baseline to which we compare all other experiments is simply trained on
the original training set, i.e., without removing any private information. On
the test set, the resulting model yields a prediction F1-score/Accuracy of
$88.3\%$ (NER), $98.4\%$ (ATIS intent) and $98.0\%$ (SNIPS intent), $99.4\%$
(en-TOD intent), $78.9\%$ (Restaurant DAC) and $90.0\%$ (Taxi DAC).

Table 2 shows the result for the different text transformation strategies.
Replacing private tokens using redact, typed placeholder and named placeholder
strategies generally gave a worse result than the word-by-word replacement.
For NER, we observe a substantial drop in performance for redact and
placeholder approaches because the model overfits on the replacement tokens
which are expected to be absent in the test set. On the other hand, the drop
is minimal for intent and dialog act classification tasks around ($2-4\%$)
similar to the observation in [1], except for the SNIPS dataset with much
larger reduction in performance of $8-44\%$ depending on the placeholder
strategy. This shows that these transformation strategies are generally not
suitable for training NLU systems.

For the word-by-word replacement, we observe a drop of 15% in F1-score when we
replace all words labeled as named entities with tokens of the same-type. For
NER, we find that “TIME”, “ORG” and “DATE” are most affected by the word-by-
word replacement in terms of drop in F1-score because many of them are multi-
word expressions. Thus, the three named entities gain the most by full-entity
replacement. On the other-hand, the drop is very small ($<1\%$) for other
intent and dialog act classification.

Table 1 illustrates an example of the full-entity replacement (e.g “Frankfurt
Airport” is replaced by “New York”). This approach gives the best performance
out of all the transformation strategies with only $2.4\%$ drop for NER.
Interestingly, there is no significant difference between its performance and
the baseline on the intent and dialog act classification tasks across the
datasets. In summary, the text obtained using the word-by-word or full-entity
text transformation are more suitable for training NLU systems while
protecting the privacy of users.

##  5 Conclusion

Replacing sensitive tokens with benign alternatives is a common method for de-
identifying text documents. We prove that privacy guarantees for a formalized
version of this process can be expressed in terms of Differential Privacy. Our
approach includes two parameters, $p$ and $\pi$ that allow different
replacement strategies to be expressed as instances of the same algorithm. The
respective DP-$\epsilon$ value follows from the choices for $p$ and $\pi$,
permitting a comparison of different replacement strategies with respect to
their privacy implications.

User privacy is juxtaposed by the performance impact that a text
transformation has on subsequent machine learning tasks. We experiment with
three different NLP tasks across six different datasets and find that both
word-by-word and full entity replacement strategies are robust against
performance drops across all examined tasks.

22todo: 2future work

##  6 Acknowledgments

This research has received funding by the European Union’s Horizon 2020
research and innovation programme under grant agreement No. 3081705 – COMPRISE
(http://www.compriseh2020.eu/). We thank Xiaoyu Shen, Volha Petukhova, and the
anonymous reviewers for their insightful comments that helped us to improve
this paper.

## References

  * [1] M. J. Tang, D. Z. Hakkani-Tür, and A. GokhanTur, “Preserving privacy in spoken language databases,” in _. In Proc. of the International Workshop on Privacy and Security Issues in Data Mining, ECML/PKDD_ , 2004.
  * [2] C. Dwork and A. Roth, _The Algorithmic Foundations of Differential Privacy_ , ser. Foundations and Trends in Theoretical Computer Science. Now Publishers Inc., August 11, 2014.
  * [3] Özlem Uzuner, Y. Luo, and P. Szolovits, “Evaluating the state-of-the-art in automatic de-identification,” _Journal of the American Medical Informatics Association_ , vol. 14, no. 5, pp. 550–563, September 2007.
  * [4] S. M. Meystre, F. J. Friedlin, B. R. South, S. Shen, and M. H. Samore, “Automatic de-identification of textual documents in the electronic health record: a review of recent research,” _BMC Medical Research Methodology_ , vol. 10, no. 70, 2010, https://doi.org/10.1186/1471-2288-10-70.
  * [5] F. Dernoncourt, J. Y. Lee, O. Uzuner, and P. Szolovits, “De-identification of patient notes with recurrent neural networks,” _Journal of the American Medical Informatics Association_ , vol. 24, no. 3, pp. 596–606, June 2017.
  * [6] K. Khin, P. Burckhardt, and R. Padman, “A deep learning architecture for de-identification of patient notes: Implementation and evaluation,” in _Proceedings of the Workshop on Information Technologies and Systems (WITS)_ , San Jose, CA, USA, December 16-18 2018.
  * [7] H. Chen, X. Liu, D. Yin, and T. Michigan, “A survey on dialogue systems: Recent advances and new frontiers,” _ACM SIGKDD Explorations Newsletter_ , vol. Volume 19, no. 2, pp. 25–35, December 2017.
  * [8] C. C. Aggarwal and P. S. Yu, Eds., _Privacy-preserving Data Mining: Models and Algorithms_. Springer, 2008.
  * [9] J. Devlin, M. Chang, K. Lee, and K. Toutanova, “BERT: pre-training of deep bidirectional transformers for language understanding,” _CoRR_ , vol. abs/1810.04805, 2018. [Online]. Available: http://arxiv.org/abs/1810.04805
  * [10] D. S. Carrell, D. J. Cronkite, M. R. Li, S. Nyemba, B. A. Malin, J. S. Aberdeen, and L. Hirschman, “The machine giveth and the machine taketh away: a parrot attack on clinical text deidentified with hiding in plain sight,” _Journal of the American Medical Informatics Association_ , vol. 26, no. 12, pp. 1536–1544, 08 2019. [Online]. Available: https://doi.org/10.1093/jamia/ocz114
  * [11] C. Dwork, F. McSherry, K. Nissim, and A. Smith, “Calibrating noise to sensitivity in private data analysis,” in _Theory of Cryptography_ , S. Halevi and T. Rabin, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2006, pp. 265–284.
  * [12] S. L. Warner, “Randomized response: A survey technique for eliminating evasive answer bias,” _Journal of the American Statistical Association_ , vol. 60, no. 309, pp. 63–69, 1965, pMID: 12261830. [Online]. Available: https://www.tandfonline.com/doi/abs/10.1080/01621459.1965.10480775
  * [13] Y. Wang, X. Wu, and D. Hu, “Using randomized response for differential privacy preserving data collection,” in _Proceeding of the workshop Privacy and Anonymity in the Information Society (PAIS) of the EDBT/ICDT 2016 Joint Conference_ , T. Palpanas and K. Stefanidis, Eds., Bordeaux, France, March 15 2016\.
  * [14] J. P. Pestian, C. Brew, P. Matykiewicz, D. Hovermale, N. Johnson, K. B. Cohen, and W. Duch, “A shared task involving multi-label classification of clinical free text,” in _Biological, translational, and clinical language processing_. Prague, Czech Republic: Association for Computational Linguistics, Jun. 2007, pp. 97–104. [Online]. Available: https://www.aclweb.org/anthology/W07-1013
  * [15] K. Weilhammer, U. Reichel, and F. Schiel, “Multi-Tier Annotations in the Verbmobil Corpus,” in _Proceedings of the Third International Conference on Language Resources and Evaluation (LREC 2002)_ , Las Palmas, Canary Islands, Spain, May, 29–31, 2002.
  * [16] C. T. Hemphill, J. J. Godfrey, and G. R. Doddington, “The ATIS spoken language systems pilot corpus,” in _Speech and Natural Language: Proceedings of a Workshop Held at Hidden Valley, Pennsylvania, June 24-27,1990_ , 1990. [Online]. Available: https://www.aclweb.org/anthology/H90-1021
  * [17] A. Coucke, A. Saade, A. Ball, T. Bluche, A. Caulier, D. Leroy, C. Doumouro, T. Gisselbrecht, F. Caltagirone, T. Lavril, M. Primet, and J. Dureau, “Snips voice platform: an embedded spoken language understanding system for private-by-design voice interfaces,” _ArXiv_ , vol. abs/1805.10190, 2018\.
  * [18] S. Schuster, S. Gupta, R. Shah, and M. Lewis, “Cross-lingual transfer learning for multilingual task oriented dialog,” in _NAACL-HLT_ , 2019.
  * [19] X. Li, S. Panda, J. Liu, and J. Gao, “Microsoft dialogue challenge: Building end-to-end task-completion dialogue systems,” _arXiv preprint arXiv:1807.11125_ , 2018.
  * [20] T. Wolf, L. Debut, V. Sanh, J. Chaumond, C. Delangue, A. Moi, P. Cistac, T. Rault, R. Louf, M. Funtowicz, and J. Brew, “Huggingface’s transformers: State-of-the-art natural language processing,” _ArXiv_ , vol. abs/1910.03771, 2019.