11institutetext: Cinnamon AI
10th floor, Geleximco building, 36 Hoang Cau, Dong Da, Hanoi, Vietnam.
11email: {simon, nathan, ian, tadashi<EMAIL_ADDRESS>22institutetext: Deakin University, Australia.
22email<EMAIL_ADDRESS>
33institutetext: Hung Yen University of Technology and Education, Vietnam.
33email<EMAIL_ADDRESS>
Bao-Sinh Nguyen, Dung Tien Le, Hieu M. Vu, Tuan-Anh D. Nguyen, Minh-Tien
Nguyen, Hung Le

# Improving Document Image Understanding with Reinforcement Finetuning

Bao-Sinh Nguyen  11 Dung Tien Le  11 Hieu M. Vu  11 Tuan-Anh D. Nguyen  11
Minh-Tien Nguyen  1133 Hung Le  22

###### Abstract

Successful Artificial Intelligence systems often require numerous labeled data
to extract information from document images. In this paper, we investigate the
problem of improving the performance of Artificial Intelligence systems in
understanding document images, especially in cases where training data is
limited. We address the problem by proposing a novel finetuning method using
reinforcement learning. Our approach treats the Information Extraction model
as a policy network and uses policy gradient training to update the model to
maximize combined reward functions that complement the traditional cross-
entropy losses. Our experiments on four datasets using labels and expert
feedback demonstrate that our finetuning mechanism consistently improves the
performance of a state-of-the-art information extractor, especially in the
small training data regime.

###### Keywords:

Information Extraction Reinforcement Learning Human-In-The-Loop

##  1 Introduction

Digitizing business documents is crucial for companies and corporations to
improve their productivity and efficiency. Although the advent of Document
Intelligence brings forth many opportunities to capture the key information of
document images, extraction for visually-rich documents such as receipts,
invoices, and leaflets remains notoriously challenging due to the spareness of
textual information and the variety in layouts and formats. Thus, for an AI
system to fully understand and extract desired information, it is essential to
incorporate the textual, visual, and layout aspects into the model and have it
trained in an end-to-end manner.

To this end, several approaches have aimed to encode visual and layout
information in addition to contextual features to enhance document
representations. Earlier approaches focus on improving the performance of
document layout and information extraction separately, and combine them in a
multi-stage pipeline. However, these methods often lead to cascading error due
to the nature of pipeline processing. Recent attempts introduce end-to-end
training via Graph Neural Networks [1] and language modeling - LayoutLM [2, 3]
\- for jointly modeling text and layout information.

While the methods above are effective when dealing with benchmark datasets,
there exists challenges for practical cases. First, for the model to perform
well on a new dataset, a decent amount of labeled training data are required
to finetune the model. Benchmark datasets can include up to thousand samples
or even more. However, in reality, only a few labeled samples can be provided
for training because data annotation is time-consuming and labor-expensive.
Therefore, an open research question still remains: how do we make the most of
these valuable data to enable sample-efficient information extraction? The
second issue is the current training process relies solely on predefined
datasets for finetuning in a supervised manner. The supervised training often
uses the differentiable loss, such as cross-entropy, to predict the locations
of the extracted content, which may cause a mismatch between the training
objective and the performance metric. More importantly, this opts out the
opportunities for domain experts to provide feedback, design the learning
criteria, and guide the model to more accurate extraction.

In this paper, we introduce a new fine-tuning method that complements the
traditional cross-entropy training with different learning objectives that
match better the evaluation criteria. We formulate the information extraction
task as a reinforcement learning (RL) problem wherein the information
extractor, such as SpanIE-Recur [4], is the policy network, and its output
corresponds to actions. We design different reward functions to capture the
spatial, categorical, lexical and semantic similarity between the extracted
and the ground-truth answers. We then use the proximal policy gradient
algorithm (PPO) [5] to learn the optimal policy that maximizes the total
rewards. Our approach not only exploits all aspects of training signals from
the data but also allows the domain expert to design rewards or provide
feedback to improve the system. We evaluate our method on two public and two
private visually-rich document datasets and achieve consistent improvement
over only using supervised training in terms of F1 scores, especially when the
the training data is limited. We also conduct human-in-the-loop experiment
where a domain expert provide ranking feedback to finetune the model, showing
clear improvement over few number of interactions.

Our contributions are three-fold: (i) a novel approach to improve information
extraction in business documents using reinforcement learning, (ii) a set of
complimentary reward functions to aid the traditional supervised learning
(SL), and (iii) extensive experiments on both public (English) and private
real-world dataset (Japanese), confirming the benefit of our approach with
both limited ground-truth labels and expert’s feedback.

##  2 Related Work

####  2.0.1 Information extraction (IE)

is an increasingly popular task, where the goal is to automatically extract
structured information from a given unstructured document. Unlike plain text,
visually-rich documents (VRDs) usually contain sparser texts with well-defined
layouts and meaningful visual structures, which can previously be addressed
using computer vision and graph-based methods [6, 7]. With the success of BERT
[8] and its derivatives, e.g. LayoutLM [2, 3], IE methods for VRDs are seeing
a trend of shifting from traditional to NLP techniques, such as sequence
labeling and span extraction.

There have been many studies applying span extraction to IE. [9] presented a
span-based model for NER, which enables the model to handle the more common
sequence labeling approach such as overlapping entities and discontinued
entities. One disadvantage of span-based methods is that they usually only
extract one answer for one question at a time. To address this issue, [4] and
[10] share the same question-context interaction mechanism which enables
simultaneous extraction for multiple questions, but the former employs a
recursive linking technique while the latter proposes combining span
extraction with sequence labeling to facilitate multi-value extraction. In
this paper, we adapt SpanIE-Recur to our task. However, instead of directly
applying the technique, we empower SpanIE-Recur by putting it into an RL
framework, which allows SpanIE-Recur to take into account the advantage of
transfer learning and human feedback for training. Based on that, we can
improve the quality of our extraction model.

####  2.0.2 Reinforcement learning

has been applied to text summarization [11], dialogue generation [12] and
machine translation [13]. Most of these methods focus on building an RL agent
that generates texts in forms of summary, dialogue, and different language
based on the reward signal computed directly from the ground truth text and
prediction text. Recent attempts push the idea further by adding preference
learning into the reward model [14, 15, 16]. We extend RL as the technique to
our IE task for VRDs. More importantly, to the best of our knowledge, this
paper is the very first attempt to apply reinforcement learning for the
visually-rich document information extraction task.

##  3 Background

####  3.0.1 Information extraction backbone

We use SpanIE-Recur [4] as the backbone of our model. SpanIE-Recur addresses
the IE problem by the Extractive Question Answering (QA) formulation [8].
Concretely, it replaces the sequence labeling head of the original LayoutLM
[2] by a span prediction head to predict the starting and the ending positions
of the answers given an input field/tag (hereinafter referred as a question).

In particular, let $D=\\{w_{0},w_{1},...,w_{n}\\}$ denote the input document
context consisting of $n$ input tokens. The pretrained language model converts
them into a set of hidden representations $H=\\{h_{0},h_{1},...,h_{n}\\}$. The
$t$-th question $q_{t}$ is represented by an embedding vector $e_{q_{t}}$. The
query-context interaction module $g$, which is implemented by attention
layers, outputs the starting and the ending position of the corresponding
answer span: $start_{t},end_{t}=g(H,e_{q_{t}})$.

####  3.0.2 Proximal Policy Optimization

Proximal Policy Optimization (PPO) [5] is an on-policy RL algorithm that
utilizes the clipped loss function to avoid big changes in the policy update,
still guarantees improvements. Let $s_{t}$ and $a_{t}$ denote the state and
action at timestep $t$ respectively, $\pi_{\theta}$ denote the policy network.
The PPO training objective is:

$J^{PPO}(\theta)=\mathop{\mathbb{E}}[\min\\{ra(\theta)\hat{A}_{\theta_{old}}(s_{t},a_{t}),\\\
\mathrm{clip}(ra(\theta),1-\epsilon,1+\epsilon)\hat{A}_{\theta_{old}}(s_{t},a_{t})\\}]$
(1)

where $\theta$ is the current policy’s parameters,
$\hat{A}_{\theta_{old}}(s_{t},a_{t})$ is the advantage calculated at the old
policy parameters $\theta_{old}$ before each updated policy iteration, by
using any advantage estimation algorithm to transform the rewards [17], and
$ra(\theta)=\frac{\pi_{\theta}(a_{t}|s_{t})}{\pi_{\theta_{old}}(a_{t}|s_{t})}$
is the ratio between the new policy and the old policy. If the ratio $ra$
falls outside the range $1-\epsilon$ and $1+\epsilon$, the advantage function
will be clipped.

##  4 Method

###  4.1 Problem formulation for reinforcement finetuning

We adapt the original SpanIE-Recur [4] as the policy network $\pi_{\theta}()$
of the IE agent and finetune it using RL. The only difference is that we
replace the learnable question embedding $e_{q_{t}}$ by the embedding produced
from a pretrained multilingual text encoder [18] taking the question text as
the input, which can benefit transfer learning settings. We treat the
information extraction process as a sequential decision making process so that
we can employ RL, where each question to a document corresponds to one
timestep in an episode. At each timestep $t$, the document context $D$ and the
$t$-th question $q_{t}$ are fed to the model, that is to say, the agent is in
the state $s_{t}=(D,q_{t})$. The model predicts the starting position
$start_{t}$ and the ending position $end_{t}$ of the answer span, thus the
agent takes action $a_{t}=(start_{t},end_{t})$, which corresponds to
extracting the answer string $\hat{y}=D[start_{t}:end_{t}+1]$111Using Python
slicing notation. from the document context. It then receives a reward $r$
based on a reward function (described in Section 4.2) and goes to the next
timestep $t+1$ until all questions are traversed by the agent. The RL
formulation is shown in Figure 1.

Figure 1: Reinforcement Learning formulation using SpanIE-Recur backbone.

###  4.2 Reward functions

We improve the quality of SpanIE-Recur by defining new reward functions for
RL. We argue that the advantage of RL fine-tuning over SL is that RL fine-
tuning provides the flexibility in designing the reward that reflects human’s
preferences, which is not available in traditional SL. Moreover, this reward
can fully utilize different training signals from the data. Therefore, we
introduce an unified reward function, which considers the following criteria
of a good answer given an input question.

####  4.2.1 String matching reward

Our string matching reward bases on the Levenshtein distance between the
output answer string $\hat{y}$ and the ground truth answer string $y$.
Intuitively, we expect that a higher reward should be given to the output
answer that is more similar to the ground truth one and vice versa.

$r_{string}=1-\mathrm{Levenshtein\\_distance}(y,\hat{y})$ (2)

####  4.2.2 Location reward

The location reward encourages the location matching between the output answer
span and the corresponding ground truth span in the document context. Let
$a=(start$, $end)$ be the predicted starting and ending positions of the span
and $a\\_gt=(start\\_gt$, $end\\_gt)$ be the corresponding ground truth ones.
The exact formula for location reward is calculated by intersection over union
of two spans:

$r_{location}=\frac{interArea}{(end-start)+(end\\_gt-start\\_gt)-interArea}$
(3)

where $interArea$ is the length of the intersection between two spans.

####  4.2.3 Label reward

The label reward enforces the correctness of the label (field/tag) of the
extracted answer. Particularly, given a question $q_{t}$, if the IE model
extracts the answer $\hat{y}=D[start:end+1]$, we expect that the actual label
of the span $(start,end)$ in the document $D$ matches to $q_{t}$, i.e:

$r_{label}=\begin{cases}1&\text{if $label(\hat{y})=q_{t}$}\\\ 0&\text{if
$label(\hat{y})\neq q_{t}$ and $label(\hat{y})=other$}\\\ -1&\text{if
$label(\hat{y})\neq q_{t}$ and $label(\hat{y})\neq other$}\\\ \end{cases}$ (4)

where $label()$ returns the actual tag of the answer span $\hat{y}$, by
obtaining the majority of token’s ground truth tags in this span, $other$ is a
special tag we assign for tokens that do not belong to any targeted field.
Intuitively, this reward penalizes more severely if the model mis-recognizes
an entity as another targeted field rather than its ground truth field.

####  4.2.4 Semantic reward

The semantic reward incentivizes the semantic matching between the output
answer and the ground truth one. We utilize the pretrained multilingual
sentence encoder [18] to compute the sentence embeddings of the output and the
ground truth, and then measure their Cosine similarity in the latent embedding
space.

$r_{semantic}=cosine(enc(y),enc(\hat{y}))$ (5)

where $enc()$ returns the vector of an input by using the sentence encoder.

The final formula for the unified reward.

$r=\alpha_{1}\times r_{string}+\alpha_{2}\times r_{location}+\alpha_{3}\times
r_{label}+\alpha_{4}\times r_{semantic}$ (6)

where $\alpha_{i}$’s are the corresponding weights for each reward component.

Algorithm 1 Training protocol

1:Dataset $\mathbb{D}$, Pretrained SpanIE-Recur $\pi_{\theta}()$, Maximum
number of iterations for RL finetuning $n_{max}$.

2:Perform traditional supervised training of $\pi_{\theta}()$ on $\mathbb{D}$
until convergence. $i\leftarrow 0$

3:while $i\leq n_{max}$ do

4: Initialize set of trajectories $\mathbb{T}\leftarrow\\{\\}$. Sample set of
documents $\\{D_{k}\\}$ from $\mathbb{D}$.

5: for $D_{k}$ in $\\{D_{k}\\}$ do

6: Initialize trajectory $\tau\leftarrow\\{\\}$, $t\leftarrow 0$.

7: for $q_{t}$ in all questions do

8: The agent is in state $s_{t}\leftarrow(D_{k},q_{t})$.

9: The agent takes action $a_{t}\sim\pi_{\theta}(s_{t})$ as described in
Section 4.1.

10: The environment returns corresponding reward $r_{t}$ calculated by
Equation 6.

11: The environment returns the timestep for the next state $t\leftarrow t+1$.

12: $\tau\leftarrow\tau\cup\\{s_{t},a_{t},r_{t}\\}$. $i\leftarrow i+1$

13: end for

14: $\mathbb{T}\leftarrow\mathbb{T}\cup\tau$

15: end for

16: Given trajectories $\mathbb{T}$, calculate PPO loss function by Equation
1.

17: Backpropagate the gradients and update the parameters of $\pi_{\theta}$.

18:end while

19:return $\pi_{\theta}$

###  4.3 Transfer learning with ground-truth labels

In this section, we describe the RL fine-tuning procedure based on the
following protocol. Starting with a pretrained weight model (e.g. LayoutLM),
we finetune the pretrained model on the training set with normal supervised
training until convergence. In practice, this training set is divided into
smaller subsets with a given size (2%, 5%, 10% or 100% of the entire training
data). We finetune the model further with our reinforcement learning for up to
$n_{max}=100000$ iterations. During this process, we utilize the ground truth
labels provided with each dataset to compute the aforementioned reward
functions. These ground truth labels comprise of the actual texts and their
corresponding starting and ending positions in the context. The goal is to
observe whether our reinforcement finetuning helps to improve the performance
of the normal supervised training of the current state-of-the-art model.

###  4.4 Experts’ feedback as reward

In addition to using ground-truth answers to compute the rewards, we propose
to use expert’s feedback to train the model. In this setting, we mimic the
real environment where human can give feedback to the model via an interactive
interface. The interface for feedback is designed as follows. Given a document
and a question, the model outputs softmax distributions over starting and
ending positions of the possible answers. We then sample from the
distributions to get five pairs of start-end actions, representing top five
answer candidates, which are equivalent to five options/buttons on the screen.
To account for cases when the model cannot provide good candidates, we provide
a sixth option - a button named No good options available. Experts could
select one of the six options that is most appropriate for the question as
feedback to the model. The selected candidate is used as ground truth $y$ to
compute the reward using Equation 6 above. Figure 2 (a) shows the interface of
our system.

###  4.5 Training algorithm

We describe the detailed protocol to train the information extractor (SpanIE-
Recur) with our rewards in Algorithm 1. We sample a document and its set of
questions from the training data to form the RL trajectory. For each question,
we concatenate the document and question representations to build the current
state. Then, we sample one start-end action from the softmax layers of SpanIE-
Recur to extract the candidate answer for the question. The reward is computed
based on the candidate answer and the ground truth to construct the RL’s loss
function to optimize SpanIE-Recur.

##  5 Settings and Evaluation Metrics

####  5.0.1 Datasets

We use two public and two private datasets in our experiments. The two public
datasets are in English: SROIE [19] and CORD [20]. SROIE is a collection of
scanned receipt images, where each receipt has four fields to extract:
address, company, date, total. CORD contains receipts collected from
Indonesian shops and restaurants, where there are 30 semantic labels defined
under 4 categories, such as store information, payment information, menu,
total. Compared to SROIE, document images in CORD are captured in the wild,
thus the data is more noisy and has lower quality. For private datasets, we
collect two in-house datasets: the first one is a collection of Japanese
technical document images and the second one is a dataset of Japanese
invoices. The statistics of the four datasets are listed in Table 1.

Table 1: Statistic of datasets Dataset | # of fields | train | development | test
---|---|---|---|---
SROIE | 4 | 626 | 0 | 347
CORD | 30 | 800 | 100 | 100
Inhouse-1 | 12 | 481 | 0 | 149
Inhouse-2 | 12 | 1032 | 0 | 433

####  5.0.2 Evaluation metrics

The results are reported on the test split of the corresponding dataset by
evaluating the standard field-level Precision, Recall, and F1 scores (weighted
average) as in previous studies [2, 3].

####  5.0.3 Baselines

As far as we know, there is only one prior work [21] which targets the same
few-shot learning problem on business documents. However, they only target few
simple fields in their experiments and do not cover the broad range of
datasets. Thus, we consider the supervised learning (SL) result of SpanIE-
Recur [4] (with the LayoutLM backbone) as a competitive baseline, which is
also used in [21].

####  5.0.4 Implementation detail

Our model uses LayoutLM-base with 12 Transformer blocks, the hidden size is
768, the input sequence length is 512 and the total number of parameters is
113M. The question embedding size is also 768. All experiments are conducted
on a single Tesla T4 GPU. For all experiments, we use a learning rate of
$5e-5$ and the Adam optimizer in the supervised training stage, with the
standard cross-entropy loss. The hyper-parameters for PPO training are: the
learning rate of $1e-6$, discount factor of 0.95 and clipping rate of 0.2. We
set the weights of reward components $\alpha_{i}$’s to 0.25. These hyper-
parameters are manually tuned for the Inhouse-1 dataset and used across
experiments. To reduce the effort of tuning in future works, we may use
methods that automatically learn hyper-parameter scheduling [22].

##  6 Experimental Results

We confirm the efficiency of our approach in two settings: transfer learning
with limited data by using ground-truth labels and learning with humans’
feedback. While the former uses the ground-truth answer to construct different
rewards for training the model (Section 4.3), the latter uses human’s feedback
(see Section 4.4). We also conduct ablation studies to verify the contribution
of each reward type.

Table 2: Results of transfer learning on public datasets.

|  | Original SL | +RL
---|---|---|---
Dataset | Precision | Recall | F1 | Precision | Recall | F1 |  $\Delta$F1
CORD | 2% | 21.69 | 2.77 | 3.04 | 40.11 | 15.94 | 21.23 | 18.19
5% | 64.33 | 47.83 | 51.48 | 66.39 | 52.69 | 57.83 | 6.35
10% | 79.45 | 72.98 | 75.32 | 80.76 | 73.05 | 76.12 | 0.80
100% | 96.31 | 94.91 | 95.39 | 97.11 | 95.03 | 95.71 | 0.32
SROIE | 2% | 80.93 | 78.08 | 79.46 | 80.61 | 79.77 | 80.16 | 0.70
5% | 85.94 | 80.59 | 83.09 | 86.07 | 82.09 | 83.95 | 0.86
10% | 88.33 | 85.27 | 86.74 | 89.22 | 85.37 | 87.20 | 0.46
100% | 91.83 | 91.45 | 91.61 | 91.89 | 91.54 | 91.68 | 0.07

Table 3: Results of transfer learning on our in-house datasets. Pretrained
means the in-house pretrained weight we use to initialize the model before
performing transfer learning.

|  | Original SL | +RL
---|---|---|---
Dataset | Precision | Recall | F1 | Precision | Recall | F1 |  $\Delta$F1
Inhouse-1 | Pretrained | 38.24 | 14.62 | 18.02 | - | - | - | -
2% | 74.44 | 56.63 | 62.08 | 69.39 | 65.17 | 66.35 | 4.27
5% | 86.45 | 76.64 | 80.35 | 84.15 | 75.60 | 79.63 | -0.72
10% | 89.91 | 80.29 | 83.13 | 89.11 | 82.92 | 85.75 | 2.62
100% | 94.34 | 94.02 | 94.03 | 94.36 | 94.98 | 94.37 | 0.34
Inhouse-2 | Pretrained | 73.83 | 40.53 | 48.06 | - | - | - | -
2% | 82.18 | 68.74 | 73.71 | 81.18 | 69.62 | 74.96 | 1.25
5% | 85.94 | 76.32 | 79.42 | 83.09 | 78.95 | 80.49 | 1.07
10% | 88.27 | 81.21 | 82.81 | 88.25 | 82.17 | 82.91 | 0.10
100% | 91.42 | 91.30 | 91.35 | 91.42 | 91.30 | 91.35 | 0.00

###  6.1 Transfer learning with limited data

####  6.1.1 Training procedure

We conduct experiments from different subsets of the training data to show the
benefit of our proposed reinforcement finetuning mechanism. For the public
datasets, we use the pretrained LayoutLM weight _layoutxlm-no-
visual_.222https://huggingface.co/taprosoft/layoutxlm-no-visual We use an in-
house pretrained weight to initialize the model for the private datasets.

####  6.1.2 Benchmarking results

We report the results on CORD and SOIRE datasets in Table 3. Overall, we can
observe clearer improvements over the supervised baseline. RL finetuning makes
the marginal improvements in the 10% and 100% data scenarios. The contribution
is more remarkable in the limited data regimes, where on the CORD dataset, we
observe the increase of 18.19% and 6.35% of F1 score for 2% and 5% training
data, respectively. On SROIE, the corresponding improvements are 0.70% and
0.86%. We hypothesize that with large enough amount of data, the backbone
model trained with SL receives abundant training signal to become a strong
backbone, but in limted data scenarios, RL performs better since it can
exploit different aspects of training signals. Since CORD dataset has much
more fields than SROIE, it is harder for SL models to learn in limited data
scenarios on CORD, thus leaving rooms for RL contribution. This is the
rationale behind the large improvements on CORD compared to SROIE dataset.

Table 3 shows the results on our in-house datasets. We observe similar
behaviors of the RL-finetuned models. In most cases, RL finetuning can improve
the performances, noticeably when the performance of SL counterparts are
humble in 2% data scenarios (4.27% and 1.25% F1 score improvements on
Inhouse-1 and Inhouse-2 respectively).

####  6.1.3 Ablation Study

In this section, we investigate the impact of different reward components in
the unified reward function. We use the setting with the 2% training data
scenario, but we ablate each single reward component respectively. Table 4
reports the F1 score of each ablated model on CORD and SOIRE data. Without
string matching and location rewards, the performances drop significantly, but
retain the improvements upon the SL counterpart. We observe the most severe
drop when removing the semantic reward component on both datasets, which
emphasizes the importance of the semantic matching between output and ground
truth answers. Ablating the label reward on CORD dataset results in comparable
performance to that of the full unified reward, but on SROIE dataset, we
observe a large drop, thus confirms the helpfulness of the label reward
component.

Table 4: Effect of ablating different reward components. | CORD | SROIE
---|---|---
Model | Precision | Recall | F1 |  $\Delta$F1 | Precision | Recall | F1 |  $\Delta$F1
SL model | 21.69 | 2.77 | 3.04 | - | 80.93 | 78.08 | 79.46 | -
w/o string matching | 37.87 | 5.46 | 7.79 | 4.75 | 80.91 | 78.17 | 79.67 | 0.21
w/o location | 47.07 | 5.16 | 7.82 | 4.78 | 80.42 | 78.85 | 79.83 | 0.37
w/o label | 31.19 | 17.51 | 2.22 | 19.16 | 80.52 | 78.75 | 79.61 | 0.15
w/o semantic | 2.27 | 2.54 | 2.40 | -0.64 | 81.47 | 77.69 | 79.52 | 0.06
Full unified reward | 40.11 | 15.94 | 21.23 | 18.19 | 80.61 | 79.77 | 80.16 | 0.70

###  6.2 Learning with experts’ feedback

We conduct an interactive experiment that allows a domain expert to train the
system with preference reward via feedback. For this experiment, we sample
five sets with four documents each from the dev set of CORD, use them to get
feedback from experts, and evaluate the results on the test set after each
interaction. Figure 2(b) shows the F1-score with the mean and standard
deviation for five sets, with the result at interaction 0 being from the
backbone using only supervised learning on 100% of the training set. After
three interactions, the average F1-score of five sets increases marginally at
around 0.11%. Yet, considering the small number of documents sampled for
feedback and a decent performance of the backbone at the beginning, this
increase is notable.

(a) Example of interaction interface

(b) CORD: F1 score with human feedback

Figure 2: Learning with experts’ feedback.

##  7 Discussion

This work proposes a novel end-to-end reinforcement learning model with task-
focused reward for document image extraction task. Our experiments show that
for both English and Japanese documents, our model outputs competitive results
with the traditional supervised learning approach when having full access to
training data, while performing significantly better when reducing the amount
of training data, notably the 18.19% improvement in F1-score for 2% of the
CORD training set. In addition, we provide an interactive interface session to
get feedback from experts to improve the model’s performances. Our results
suggest that with as little as two to three interactions, users are able to
witness the changes in output for the betterment. Despite this, the feedback
interface, along with its connection to the RL model, is still in preliminary
state. For future works, one should consider not only the selected candidate
but also the non-selected ones, and how to represent them in the reward model.

## References

  * [1] Xiaojing Liu, Feiyu Gao, Qiong Zhang and Huasha Zhao  “Graph Convolution for Multimodal Information Extraction from Visually Rich Documents”  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Industry Papers)_ , 2021, pp. 32–39  Association for Computational Linguistics, Minneapolis, Minnesota
  * [2] Yiheng Xu et al.  “Layoutlm: Pre-training of text and layout for document image understanding”  In _Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, 2020, pp. 1192–1200
  * [3] Yang Xu et al.  “LayoutLMv2: Multi-modal Pre-training for Visually-rich Document Understanding”  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ Association for Computational Linguistics, 2021, pp. 2579–2591
  * [4] Tuan-Anh D Nguyen, Hieu M Vu, Nguyen Hong Son and Minh-Tien Nguyen  “A Span Extraction Approach for Information Extraction on Visually-Rich Documents”  In _International Conference on Document Analysis and Recognition_ , 2021, pp. 353–363  Springer
  * [5] John Schulman et al.  “Proximal policy optimization algorithms”  In _arXiv preprint arXiv:1707.06347_ , 2017
  * [6] Wenwen Yu et al.  “PICK: Processing Key Information Extraction from Documents using Improved Graph Learning-Convolutional Networks”  In _2020 25th International Conference on Pattern Recognition (ICPR)_ , 2021, pp. 4363–4370
  * [7] Brian Davis et al.  “Visual FUDGE: Form Understanding via Dynamic Graph Editing”  In _Document Analysis and Recognition – ICDAR 2021: 16th International Conference, Lausanne, Switzerland, September 5–10, 2021, Proceedings, Part I_ Springer-Verlag, 2021, pp. 416–431
  * [8] Jacob Devlin, Ming-Wei Chang, Kenton Lee and Kristina Toutanova  “BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding”  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL-HLT 2019, Minneapolis, MN, USA, June 2-7, 2019, Volume 1 (Long and Short Papers)_ Association for Computational Linguistics, 2019, pp. 4171–4186
  * [9] Fei Li, ZhiChao Lin, Meishan Zhang and Donghong Ji  “A Span-Based Model for Joint Overlapped and Discontinuous Named Entity Recognition”  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ Association for Computational Linguistics, 2021, pp. 4814–4828
  * [10] Nguyen Hong Son, Hieu M Vu, Tuan-Anh D Nguyen and Minh-Tien Nguyen  “Jointly Learning Span Extraction and Sequence Labeling for Information Extraction from Business Documents”  In _arXiv preprint arXiv:2205.13434_ , 2022
  * [11] Asli Celikyilmaz, Antoine Bosselut, Xiaodong He and Yejin Choi  “Deep Communicating Agents for Abstractive Summarization”  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers)_ , 2018, pp. 1662–1675
  * [12] Jiwei Li et al.  “Deep Reinforcement Learning for Dialogue Generation”  In _Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing_ Association for Computational Linguistics, 2016, pp. 1192–1202
  * [13] Lijun Wu et al.  “A Study of Reinforcement Learning for Neural Machine Translation”  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ Association for Computational Linguistics, 2018, pp. 3612–3621
  * [14] Duy-Hung Nguyen et al.  “Robust Deep Reinforcement Learning for Extractive Legal Summarization”  In _International Conference on Neural Information Processing_ , 2021, pp. 597–604  Springer
  * [15] Nisan Stiennon et al.  “Learning to summarize with human feedback”  In _Advances in Neural Information Processing Systems_ 33, 2020, pp. 3008–3021
  * [16] Duy-Hung Nguyen et al.  “Make The Most of Prior Data: A Solution for Interactive Text Summarization with Preference Feedback”  In _Findings of the Association for Computational Linguistics: NAACL 2022_ Seattle, United States: Association for Computational Linguistics, 2022, pp. 1919–1930  DOI: 10.18653/v1/2022.findings-naacl.147
  * [17] John Schulman et al.  “High-Dimensional Continuous Control Using Generalized Advantage Estimation”  In _4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings_ , 2016
  * [18] Fangxiaoyu Feng et al.  “Language-agnostic BERT Sentence Embedding”  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ Association for Computational Linguistics, 2022, pp. 878–891
  * [19] Zheng Huang et al.  “Icdar2019 competition on scanned receipt ocr and information extraction”  In _2019 International Conference on Document Analysis and Recognition (ICDAR)_ , 2019, pp. 1516–1520  IEEE
  * [20] Seunghyun Park et al.  “CORD: a consolidated receipt dataset for post-OCR parsing”  In _Workshop on Document Intelligence at NeurIPS 2019_ , 2019
  * [21] Zilong Wang and Jingbo Shang  “Towards Few-shot Entity Recognition in Document Images: A Label-aware Sequence-to-Sequence Framework”  In _arXiv preprint arXiv:2204.05819_ , 2022
  * [22] Hung Le et al.  “Episodic policy gradient training”  In _Proceedings of the AAAI Conference on Artificial Intelligence_ 36.7, 2022, pp. 7317–7325


# Research Challenges in Designing
Differentially Private Text Generation Mechanisms

Oluwaseyi Feyisetan, Abhinav Aggarwal, Zekun Xu, Nathanael Teissier
Amazon
<EMAIL_ADDRESS>
###### Abstract

Accurately learning from user data while ensuring quantifiable privacy
guarantees provides an opportunity to build better Machine Learning (ML)
models while maintaining user trust. Recent literature has demonstrated the
applicability of a generalized form of Differential Privacy to provide
guarantees over text queries. Such mechanisms add privacy preserving noise to
vectorial representations of text in high dimension and return a text based
projection of the noisy vectors. However, these mechanisms are sub-optimal in
their trade-off between privacy and utility. This is due to factors such as a
fixed global sensitivity which leads to too much noise added in dense spaces
while simultaneously guaranteeing protection for sensitive outliers. In this
proposal paper, we describe some challenges in balancing the tradeoff between
privacy and utility for these differentially private text mechanisms. At a
high level, we provide two proposals: (1) a framework called lac which defers
some of the noise to a privacy amplification step and (2), an additional suite
of three different techniques for calibrating the noise based on the local
region around a word. Our objective in this paper is not to evaluate a single
solution but to further the conversation on these challenges and chart
pathways for building better mechanisms.

##  1 Introduction

Privacy has emerged as a topic of strategic consequence across all
computational fields – from machine learning, to natural language processing
and statistics. Whether it is to satisfy compliance regulations, or build
trust among customers, there is a general consensus about the need to provide
privacy guarantees to users whose datasets serve as inputs to arbitrary
functions provided by external processors. Within the mathematical and
statistical disciplines, Differential Privacy [DMNS06] has emerged as a gold
standard for evaluating theoretical privacy claims. At a high level, a
randomized algorithm is differentially private if its output distribution is
_similar_ when the algorithm runs on two neighboring input databases. The
notion of similarity is controlled by a parameter $\varepsilon\geq 0$ that
defines the strength of the privacy guarantee. Similarly, it is possible to
train differentially private deep learning [SS15, ACG+16] models by extending
the methods from the statistical literature to the universal function
approximators in neural networks. However, while DP comes with strong
theoretical guarantees, and the literature around the field is quite mature,
designing differentially private mechanisms for generating text is less
studied.

As a result, within the field of traditional and computational linguistics,
the norm is to apply anonymization techniques such as $k$-anonymity [Swe02]
and its variants. While this offers a more intuitive way of expressing privacy
guarantees as a function of an aggregation parameter $k$, all such methods are
provably non-private [KKMN09]. Nevertheless, recent works such as [FDM19,
FDD19, FBDD20] have attempted to directly adapt the methods of DP to Natural
Language Processing (NLP) by borrowing ideas from the privacy methods used for
location data [ABCP13]. In DP, one way privacy is attained by adding ‘properly
calibrated noise’ to the output of a mechanism [DMNS06], or to gradient
computations for deep learning [ACG+16]. The premise of such ‘DP for text’
methods is predicated on adding noise to the vector representation of words in
a high dimensional embedding space, and projecting the noisy vectors back to
the discrete vocabulary space.

Unlike statistical queries however, language generation comes with a unique
set of problems. Consider a simple counting query where the objective is to
return the number of people who exhibit a certain property $x$. The
sensitivity of such a query is $1$ since a new individual can only increase
the count by $1$. With text however, the sensitivity is much larger and is
driven by the richness of the vocabulary, and how it is represented in the
metric space under consideration. In this paper we propose strategies for
increasing the utility of these ’DP for text’ mechanisms by reducing the noise
required while maintaining the desired privacy guarantees.

##  2 Privacy Implications and Threat Model

We consider a system where users generate training data (as text) which is
then made available to an analyst. The analyst’s utility requirement is to
assess the quality of a downstream metric (e.g., ML model accuracy) derived
from this data. The analyst therefore requires clear form access to the input
data (e.g., for augmentation, aggregation, or annotation) to continuously
improve downstream utility. In this model however – akin to a modular unit in
the overall threat vector of [KMA+19] and specific model of [FBDD20], it is
possible that the analyst learns more information about the user e.g., their
_identity_ , or some _property_ [WE18], than is required to play their role of
improving the utility metric. An example where textual data was used for re-
identification can be seen with the AOL data release [BZH06].

##  3 Challenges in Designing Private Text

Consider a set of $n$ users, each with data $x_{i}\in\mathcal{X}$. Each user
wishes to release up to $m$ messages in a privacy preserving manner while
maximizing the utility gained from the release of the messages. One approach
is for each user to submit their messages $(x_{i},_{1},\ldots,x_{i},_{m})$ in
clear form to a _trusted_ curator. The curator then proceeds to apply a
privacy preserving randomized mechanism $\mathcal{R}(*)$ to the analysis
$\mathcal{A}(x)$ on the aggregated data. The privacy mechanism works by
_injecting noise_ to the results of the analysis. This technique corresponds
to the curator model of DP [DMNS06], however, it requires that the users
_trust_ the curator. This is the proposed approach for preserving privacy in
the upcoming U.S. Census [Abo18]. The curator model results in high utility
since noise is applied only once on the aggregated data; however, a parallel
approach cannot be clearly drawn for private text synthesis.

Another theoretical approach is for each user to apply the encoding or
randomizing mechanism $\mathcal{R}:\mathcal{X}\to\mathcal{Y}^{m}$ to their
data. The resulting $n\cdot m$ messages
$(y_{i},_{1},\ldots,y_{i},_{m})=\mathcal{R}(x_{i})$ for each user is then
passed to the curator for analysis
$\mathcal{A}:\mathcal{Y}^{*}\to\mathcal{Z}$. This corresponds to Local  (LDP)
[KLN+11], since each user randomizes their data _locally_. The model provides
stronger privacy guarantees in the presence of an _untrusted_ curator.
However, it incurs more error than the curator model because it requires
multiple local $\mathcal{R}(x_{i})$ transformations (as opposed to one by the
trusted curator). As a result, it has mainly been successfully adopted by
companies with large user bases (such as Microsoft [DKY17], Google [EPK14],
and Apple [Tea17]) which compensate for the error. The local model is more
amenable for text [FDM19] and the literature builds on this framework.

The error accrued in the local model is exacerbated by the output range of the
randomization function $\mathcal{R}(x_{i})$. As an example, for one-bit
messages (e.g., a coin flip) where $f:\mathcal{X}\to\\{0,1\\}$, the overall
error goes down faster as the number of users increase, given the small output
size of $2$. Using a die roll with $6$ outputs, the noise smooths out a bit
slower. However, for analysis over vector representations of words
$f:\mathcal{X}\to\mathbb{R}^{d}$, where $d$ is the dimensionality of a word
embedding model, and the number of words in the vocabulary could exceed
thousands, the resulting analysis leads to far more noisy outputs. The noise
(and by extension, the error) increases because of the DP promise, i.e., to
guarantee privacy and protect all outliers, there must be a non-zero
probability for transforming any given $x$ to _any_ other $x^{\prime}$. We
loosely correlate this size of the output space with the _sensitivity_ of the
function $f$. Therefore, when the sensitivity is large, more noise is required
to preserve privacy.

The challenge with designing privacy mechanisms for text stems from these
aforementioned issues. We observe that unlike the natural distribution of
values over the number line, the vector representation of words in an
embedding space tends to be non-uniform. The distance between words carries
information as to their semantic similarities, and as a result, there are
sparse regions and dense regions. Conversely, the privacy guarantees from
differential privacy extends to every word in the entire space (leading to the
large noise required to ascertain worst-case protections). This problem is not
unique to the text space, however, it has been better studied in the
statistical privacy literature. For example, the theoretical sensitivity for
computing the median of an arbitrary set of numbers is infinite, but, in most
dataset scenarios, the sensitivity is smaller as values coalesce around the
median [NRS07]. Similar considerations have also been explored in private
release of graph statistics [BBDS13, KNRS13].

In this exploratory paper we examine these challenges from different lenses:

  1. 1.

Can we reduce the noise by deferring additional privacy guarantees to other
amplification mechanisms that do not require noise (e.g., sub-sampling,
shuffling, k-aggregation have all been proposed in the literature [LQS12,
BEM+17]);

  2. 2.

Can we re-calibrate the noise added such that it varies for every word
depending on the density of the space surrounding the current word – rather
than resorting to a single global sensitivity?

To address (1), we propose framing the private data release problem within the
central DP [EFM+19] paradigm by recommending a generalized form of the ESA
protocol of [BEM+17] which we denote as LAC. For (2), we propose three
different methods that can be adopted to directly reduce the noise: density
modulated noise, calibrating the noise to data sensitivity, and truncating the
noise using a variety of approaches.

We now give some preliminaries before expounding into the details of our
proposals.

##  4 Preliminaries and Current Methods

Let $\mathcal{X}^{n}$ be a collection of datasets from users. The Hamming
distance $d_{H}(x,x^{\prime})$ between two datasets
$x,x^{\prime}\in\mathcal{X}^{n}$ is the number of entries on which $x$ and
$x^{\prime}$ differ i.e., $d_{H}(x,x^{\prime})=|\\{i:x_{i}\neq
x^{\prime}_{i}\\}|=\sum_{i=1}^{|\mathcal{X}|}|x_{i}-x_{i}^{\prime}|$. The
datasets $x,x^{\prime}\in\mathcal{X}$ are adjacent (we denote this as $x\sim
x^{\prime}$) if $d_{H}(x,x^{\prime})=1$.

######  Definition 1 (Differential Privacy [DMNS06]).

A randomized algorithm $\mathcal{A}:\mathcal{X}^{n}\to\mathcal{Z}$ is
$\varepsilon$-differentially private if for every pair of adjacent datasets
$x\sim x^{\prime}\in\mathcal{X}^{n}$ and every $\mathcal{Z}\subseteq
Range(\mathcal{A})$,

$\displaystyle\mathsf{Pr}[\mathcal{A}(x)\in\mathcal{Z}]\leq
e^{\varepsilon}\mathsf{Pr}[\mathcal{A}(x^{\prime})\in\mathcal{Z}].$

A DP algorithm protects a user by ensuring that its output distribution is
approximately the same, whether or not the user was in the dataset used as an
input to the algorithm. DP is usually achieved by applying noise drawn from a
Laplace distribution scaled by the sensitivity of the analysis function.

Several pieces of research have demonstrated generalized DP (also known as
$d_{\mathcal{X}}$ privacy) for different metric spaces and distance functions
[CABP13, ABCP13, CPS15, FBDD20, FDM19, FDD19]. For example, [CABP13]
demonstrated how the Manhattan distance metric was used to preserve privacy
when releasing the number of days from a reference point. Similarly, the
Chebyshev metric (chessboard distance) was adapted to perturb the output of
smart meter readings [WE18, CABP13] providing privacy with respect to TV
channels being viewed. Further, the Euclidean distance was utilized by
[ABCP13, CPS15] in a $2$ dimensional coordinate system to privately report the
location of users, and finally, [FDM19] applied the Wasserstein metric in
higher dimensions to demonstrate privacy preserving textual analysis using the
metric space realized by word embeddings.

This work focuses on preserving privacy in high dimensional metric spaces
equipped with the Euclidean metric. To achieve this form of metric
differential privacy ($d_{\mathcal{X}}$ privacy), using a corollary to the
Laplace mechanism, noise is sampled from an $n-$dimensional Laplacian and
added to the output of the desired mechanism.

##  5 Proposal 1: Deferred Amplification

Our mechanism starts with a protocol similar to the privacy strategy of the
local model. Given a set of $n$ users, each with $m$ data submissions
$x_{i}\in\mathcal{X}$. Each user applies the $d_{\mathcal{X}}$ privacy
mechanism $\mathcal{L}:\mathcal{X}\to\mathcal{Y}^{m}$ to their data. The
resulting $n\cdot m$ messages
$(y_{i},_{1},\ldots,y_{i},_{m})=\mathcal{L}(x_{i})$ for each user is then
passed to the curator $\mathcal{C}:\mathcal{Y}^{*}\to\mathcal{Z}$.

Our proposal includes an additional step that amplifies the privacy
guarantees. Between the local noise injection $\mathcal{L}(x)$ and the curator
analysis $\mathcal{C}(y)$, we introduce a privacy amplification step
$\mathcal{A}:\mathcal{Y}^{*}\to\mathcal{Y}^{*}$ which takes in the result of
the message perturbations from all the users
$\mathcal{A}(\cup^{n}_{i=1}\mathcal{L}(x_{i}))$, amplifies the privacy and
outputs it to the curator.

Figure 1: The lac privacy mechanism consists of a local randomizer which adds
the noise, a privacy amplification module and a curator that aggregates the
data.

To get an intuition on how lac can be used to improve utility while preserve
privacy, consider the standard randomized response of [War65]. Given a bit
$b\in\\{0,1\\}$ and privacy parameter $\varepsilon$. To output a privatized
bit $\hat{b}$, we set $\hat{b}=b$ with probability
$p=\frac{e^{\varepsilon}}{1+e^{\varepsilon}}$, otherwise $\hat{b}=1-b$. To
improve the utility of this mechanism, we need to increase $\varepsilon$.
However, in the local model, an adversary can map the output
$\\{\hat{b_{1}},\ldots,\hat{b_{n}}\\}$ to the $n$ corresponding users.
Therefore, the parameter $p$ has to be close to $\frac{1}{2}$ otherwise
$\hat{b}\approx b$ and the privacy guarantees are meaningless. Thus, to
maintain the original (privacy) guarantees (while improving the utility), we
need an additional mechanism that’s different from the bit flipping noise
addition. The desired property is such that the privacy guarantees are still
meaningful when $p\ll\frac{1}{2}$.

In building composite DP algorithms, tools for _privacy amplification_ are
used to design mechanisms that provide additional guarantees than the initial
privacy protocol.

Probably the most studied technique is privacy ‘amplification by sub-sampling’
[CM06, KLN+11, BBG18], which states in its basic form that an $\varepsilon$-DP
mechanism applied to a $q$ fraction sub-sample of the initial population,
yields an $\varepsilon^{\prime}$-DP mechanism, where
$\varepsilon^{\prime}\approx q\varepsilon$. Other approaches such as [LQS12]
and [FDBD19] have proposed augmenting sub-sampling with a $k-$anonymity
parameter. Another class of amplification is by _contractive iteration_
[FMTT18] for privacy preserving ML models.

// Localizer

Input: word $w\in\mathcal{W}$, parameters $m$, for each $n$ users

Output: word $\hat{w}\in\mathcal{W}$

for  _$i\in\\{1,\ldots,m\\}$_ do

Noise $\eta\sim\text{Lap}(\Delta_{f}/\varepsilon)$

$\hat{\phi}=\phi(w)+\eta$

release _$\hat{w}$_

// Amplifier

Input: Multiset $\\{\hat{w_{i}}\\}_{i\in[n]}$, outputs of randomizers

Output: Multiset $\\{\hat{w_{i}}\\}_{i\in[n]}$, uniform permutes of [n]

for  _$i\in\\{n-1,\ldots,1\\}$_ do

$j\leftarrow$ random integer such that $0\leq j\leq i$

exchange $w_{i}$ and $w_{j}$

release _$\\{w\\}$_

// Curator

Input: Multiset $\\{y_{i}\\}_{i\in[n]}$, with $y_{i}\in\mathcal{Y}$

Compute $z=\mathcal{A}(y)$

release _$z$_

Algorithm 1 Composite privacy mechanism

###  5.1 Amplification Model Spotlight: The Shuffler

In this work, we highlight the _shuffle_ mechanism [BEM+17, EFM+19, CSU+19,
BBGN19] to amplify the privacy guarantees. While shuffling on its own offers
no DP guarantees (unlike sub-sampling, which does), when combined with LDP, it
has the advantage of maintaining the underlying statistics of the dataset by
not ‘throwing away’ any of the data. The shuffler de-links data by masking its
origin and confounding its provenance. For shuffling to be a viable
amplification model, the Analyzer and Randomizer outputs must be amenable to
shuffling, and not rely on any discriminating characteristics that link an
individual to their contributions.

The pseudo-code in Alg. 1 provides a high level overview of the composite
privacy mechanism using a shuffler. Each user contributes their data which
passes through a local privacy randomizer. The noisy outputs are then passed
to a shuffler which permutes the order of the source of the perturbed data.
The overall protocol $\mathcal{P}$, thus, consists of ($\mathcal{L}$,
$\mathcal{A}$, $\mathcal{C}$) and is modeled around the _Encode, Shuffle,
Analyze_ (esa) architecture of [BEM+17].

In principle, shuffling can be implemented via multi-party computation (MPC),
mixnets, running the shuffler on secure hardware or via a trusted third party
[MSZ15, CSU+19, BEM+17, ADK+19].

###  5.2 Selecting a Privacy Amplification Model

We provide some high level proposals:

Shuffler: can be used to generate text that’s fed into linear classifiers with
high utility. For example, a mechanism that outputs a sentiment class based on
private perturbed data can still yield high utility on user de-linked and
shuffled data.

Sub-sampler: For other use cases such as personalization which require some
form of user linked data, a sub-sampler can be used instead of a shuffler.
This will be more suitable if the data is reasonably uniform (without
outliers).

K-threshold: with randomized sub-sampling can be used for cases where the
underlying data follows a long tail distribution such as for annotating data
in crowdsourcing or training generalized ML models with user data.

##  6 Proposal 2: Improved Randomizers

The randomizer $\mathcal{R}$ is based on the $d_{\mathcal{X}}$ metric privacy
mechanism described by [FBDD20] on word embeddings where the distance between
word vectors is represented as the Euclidean metric. Alg. 2 presents an
overview of that mechanism. A similar mechanism was also proposed by [FDM19],
however, the distance metric was the Earth mover distance. Similarly, [FDD19]
extended the model to demonstrate preserving privacy using noise sampled from
Hyperbolic space. The metric space of interest is as defined by word embedding
models which organize discrete words in a continuous space such that the
similarity in the space reflects their semantic affinity. Models such as
Word2Vec [MSC+13], GloVe [PSM14], and fastText [BGJM17] create such a mapping
$\phi:\mathcal{W}\to\mathbb{R}^{d}$, where the distance function is expressed
as $d:\mathcal{W}\times\mathcal{W}\to[0,\infty)$. The distance
$d(w,w^{\prime})$ between a pair of words is therefore given as
$\|\phi(w)-\phi(w^{\prime})\|$, where $\|\cdot\|$ is the Euclidean norm on
$\mathbb{R}^{d}$.

Input: string $x=w_{1}w_{2}\cdots w_{\ell}$, privacy param $\varepsilon>0$

for  _$i\in\\{1,\ldots,\ell\\}$_ do

Word embedding $\phi_{i}=\phi(w_{i})$

Sample noise $N$ with density $p_{N}(z)\propto\exp(-\varepsilon\|z\|)$.
Perturb embedding with noise $\hat{\phi}_{i}=\phi_{i}+N$.

Discretization
$\hat{w}_{i}=\text{argmin}_{u\in\mathcal{W}}\|\phi(u)-\hat{\phi}_{i}\|$

Insert $\hat{w}_{i}$ in $i$th position of $\hat{x}$.

release _$\hat{x}$_

Algorithm 2 Privacy Mechanism of [FBDD20]

This mechanism however leads to sub-optimal accuracies due to a lack of
uniformity in the embedding space. In particular, to achieve a certain level
of privacy protection, the amount of noise is controlled by the worst-case
word, which roughly corresponds to the word whose embedding is farther apart
from any other word (i.e., the global sensitivity). Therefore, at a given
level of $\varepsilon$, a unique word like _nudiustertian_ will be perturbed
similarly to a common word like _drunk_ which has over $2,000$ possible
synonyms111https://www.mhpbooks.com/books/drunk/. To improve on this, we
propose a variation of the original mechanism that can provide a fixed level
of plausible deniability [BSG17], measured in terms of the proxy statistics of
[FBDD20] with less noise, thus yielding more accuracy. In other words, the
improved mechanisms should provide the same level of plausible deniability as
the original mechanism, but under a larger value of $\varepsilon$. To achieve
this goal, we propose three different strategies:

  1. 1.

Defining a prior over the word embeddings to account for the space
variability.

  2. 2.

Calibrating the injected noise to the local sensitivity of the metric space.

  3. 3.

Adopting a truncated noise mechanism within an admissible region.

###  6.1 Density-Modulated Noise

We observe that Alg. 2 can be interpreted as an instance of the exponential
mechanism [MT07] together with a post-processing step (Alg. 2: Line $5$).
Further, noise sampling via the exponential mechanism assumes a base measure
$\mu(z)$ with a uniform distribution over the feasible range. Accordingly,
line $3$ of Alg. 2 can be expanded as
$p_{N}(z)\propto\mu(z)\times\exp(-\varepsilon\|z\|)$. However, the
distribution of words in $\mathbb{R}^{d}$ is not uniform over the embedding
space. As a consequence of Zipf’s law, some words occur more frequently in a
dataset and are surrounded by dense regions of similar words in the embedding
space [Gab99].

A natural way to “bias” an exponential mechanism without changing its privacy
properties is to modulate it with a public “prior” $\mu(z)$. For example, such
a prior can be constructed over a publicly available corpus such as Wikipedia
or Common Crawl. The question we address in this section is whether we can
design an appropriate, potentially unnormalized, prior such that the resulting
exponential mechanism that samples from
$p_{N}(z)\propto\mu(z)\times\exp(-\varepsilon\|z\|)$ provides more accurate
answers than the original mechanism under similar privacy constraints. An
important research challenge in this direction is that by incorporating this
correction to improve accuracy, we might end up with a mechanism that is
computationally hard to sample from.

To obtain a prior that will solve the non-uniformity in the privacy mechanism
using a vanilla word embedding is to modulate the distribution by a prior that
captures the distribution of words in $\mathbb{R}^{d}$ induced by the word
embedding. By introducing a prior that assigns high probability to dense areas
of the embedding and low probability to sparse areas of the embedding, we can
achieve the same level of plausible deniability statistics with smaller values
of $\varepsilon$, hence, mitigating the worst-case effect that is observed in
the unmodulated mechanism around sparse areas of the embedding.

One way to produce this prior measure $\mu(z)$ is to take a kernel density
estimator with Radial Basis Function kernels on the resulting embedding, i.e.,
$\mu(z)\propto\sum_{u\in\mathcal{W}}\exp\left(-\|z-\phi(u)\|^{2}/2\sigma^{2}\right)$
for some tuned variance $\sigma^{2}$. However, it is not immediately clear how
to sample from the modulated mechanism that on input $w$ has density
$p_{N}(z)\propto\mu(z)\times\exp(-\varepsilon\|z\|)$ for $\mu(z)$ defined
above. Rather than sampling directly, we can either opt for an approximation
to the distribution, or adopt indirect sampling strategies such as the
Metropolis–Hastings algorithm [MRR+53, Has70].

Another observation is that we don’t need to pay the cost of an expensive
sampling every time we want to use the mechanism. Instead, by introducing the
projection step of the sampled vector to the closest word embedding, we can
represent the mechanism by a $W\times W$ matrix containing the probabilities
$\mathsf{Pr}[M(w)=w^{\prime}]$, where $M$ is the complete mechanism. We can
precompute and store these $||W||^{2}$ probabilities and then use this matrix
to define the output distribution every time we run the mechanism.

However, even though we can potentially make accuracy gains by incorporating
the prior $\mu$ that captures the distribution of words in $\mathbb{R}^{d}$,
we need to assume that the attacker is an informed adversary [DMNS06].
Consequently, given that the adversary knows the prior (e.g., since the word
embeddings are public), the attacker’s objective is to determine the user’s
actual word $w$, given the output $w^{\prime}$ of the mechanism $\mathcal{R}$.
The probability that $w$ is the word that generated $w^{\prime}$ is given by
the posterior probability distribution:

$\displaystyle\mathsf{Pr}(w|w^{\prime})=\frac{\mu(x)\cdot\mathsf{Pr}[\mathcal{R}(w)=w^{\prime}]}{\sum_{w\in\mathcal{W}}\mu(x)\cdot\mathsf{Pr}[\mathcal{R}(w)=w^{\prime}]}.$

The privacy objective is to protect against a Bayesian adversary that can
perform an optimal inference attack [STT+12] of the form:

$\displaystyle\hat{w}=\mathop{argmin}_{\hat{w}\in\mathcal{W}}\sum_{w\in\mathcal{W}}\mathsf{Pr}(w|w^{\prime})d(\phi(\hat{w}),\phi(w))$

where word $\hat{w}$ is the adversary’s inference given the output
$w^{\prime}$ of the randomizer, when the original word is $w$, and $d$ is the
Euclidean distance between the word vectors.

###  6.2 Calibrating Noise to Data Sensitivity

In the proof of [FBDD20], $\hat{w}$ is calibrated at the worst-case distance
$T$ from $w$ and $w^{\prime}$ which is analogous to the global sensitivity. We
can however, have a data dependent sensitivity definition over the metric
space:

######  Definition 2 (Local sensitivity [NRS07]).

The local sensitivity of a function $f:\mathcal{X}^{n}\to\mathbb{R}^{d}$ is
given for $x\sim x^{\prime}\in\mathcal{X}$ as,

$\displaystyle\Delta_{\mathcal{L}_{f}}=\max\limits_{x^{\prime}:d(x,x^{\prime})=1}\|f(x)-f(x^{\prime})\|_{1}$

The local sensitivity of $f$ with respect to $x$ is how much $f(x^{\prime})$
can differ from $f(x)$ for any $x^{\prime}$ adjacent to the input $x$ (and not
any possible entry $x$). We observe that the global sensitivity
$\Delta_{\mathcal{G}_{f}}=\max_{x}\Delta_{\mathcal{L}_{f}}(x)$. However, a
mechanism that adds noise scaled to the local sensitivity does not preserve DP
as the noise magnitude can leak information [NRS07]. To address this, for
example, [NRS07] adds noise calibrated to a _smooth bound_ on the local
sensitivity. The noise is typically sampled from the Laplace distribution.
Thus, if we consider $\hat{w}$ at a distance $0<t<T$, then the local
sensitivity $\Delta_{\mathcal{L}_{f}}$ is:

$\displaystyle{\Delta_{\mathcal{L}_{f}}}^{(t)}=\max\limits_{w^{\prime}:d(w,w^{\prime})\leq
t}\Delta_{\mathcal{L}_{f}}.$ (1)

However, for our rare word $w=$_nudiustertian_ , the local sensitivity might
still leak information on output $\hat{w}$. As a result, we can construct the
smooth sensitivity $\Delta_{\mathcal{S}_{f}}$ as a $\beta-$smooth upper bound
[NRS07] on the local sensitivity. The desired properties of the bound include
that:

(1) $\forall
w\in\mathcal{W}:\hfill\Delta_{\mathcal{S}_{f}}(w)\geq\Delta_{\mathcal{L}_{f}}(w)$

(2) $\forall w,w^{\prime}\in\mathcal{W}:\hfill\Delta_{\mathcal{S}_{f}}(w)\leq
e^{\beta}\cdot\Delta_{\mathcal{S}_{f}}(w^{\prime})$

Observe that the smooth bound is equal to the global sensitivity
$\Delta_{\mathcal{G}_{f}}$ when $\beta=0$. Therefore, the smallest function
$\Delta_{\mathcal{S}^{*}_{f,\beta}}$ that satisfies the two stated properties
is the smooth sensitivity of the underlying function $f$ and can be stated as:

$\displaystyle\Delta_{\mathcal{S}^{*}_{f,\beta}}(w)=\max\limits_{w^{\prime}:d(w,w^{\prime})\leq
t}\big{(}\Delta_{\mathcal{L}_{f}}(w^{\prime})\cdot e^{-\beta
d(w,w^{\prime})}\big{)}$

However, we cannot describe the local and smooth sensitivity this way since
the local sensitivity construction in Def 2 was defined for integer-valued
metrics (such as the Hamming distance). To translate this to real-valued
metrics as is required for $d_{\chi}$-privacy, we can adopt the approach of
[LPP20] for defining the local sensitivity in metric spaces.

First, we consider each word embedding vector as a point in some Banach space.
A Banach space is a vector space with a metric that allows the computation of
vector length and distance between vectors. For example, our $n-$dimensional
Euclidean space of word embeddings, with the Euclidean norm is a Banach space.

Next, we observe from [KNRS13] that the local sensitivity of a function is
similar to its derivative (e.g., taking the limits in Eqn 1 as $t\to 0$).
Therefore, the aim is to find an analog of a suitable derivative for
continuous functions. One option is for the local sensitivity to be defined as
the _Fréchet derivative_ in Banach spaces. [LPP20] described an approach for
this and they demonstrated how to apply noise sampled from the Cauchy
distribution to satisfy the DP guarantees. Additional research would be needed
to explore the direct application of the method of local (and then smooth)
sensitivity calibration to embedding spaces.

#### Truncated Noise Mechanisms

The standard $d_{\chi}$-privacy mechanisms were designed by borrowing ideas
from the privacy methods used for location data [ABCP13]. One of the proposed
approaches in that work was to truncate the mechanism to report only points
within the limits of the area of interest. To achieve this, they define an
‘acceptable area’ of admissible points $\mathcal{A}\subset\mathbb{R}^{2}$
(i.e., location privacy in $2-d$ space) beyond which results are truncated to
the closest point in $\mathcal{A}$. Other truncation mechanisms have been
explored in traditional DP including the truncated Laplacian [GDGK18], and
truncated geometric mechanism within the context of $d_{\chi}$-privacy
[CABP13].

Designing a corollary for text based $d_{\chi}$-privacy requires an approach
to setting the truncation bounds while maintaining the privacy guarantees. We
identify $2$ potential ways of achieving this: (1) Distance based truncation;
and (2) K-nearest neighbor based truncation. To achieve (1) we can define a
distance based limit similar to [ABCP13]. In this approach, a word can only
get perturbed to words within the distance-defined admissible area
$\mathcal{A}\in\mathcal{U}$. The maximum distance $\tau$ between a word and
the farthest word in $\mathcal{A}$ is defined and fixed a-priori. To handle
words that fall outside the noise limits, [ABCP13] proposes a discretization
step to select the closest word in $\mathcal{A}$. Another option is for the
mechanism to concentrate the probability of selecting a word to the admissible
area $\mathcal{A}$, while assigning a residual probability to satisfy the DP
guarantee on the entire set $\mathcal{U}$. Therefore, when the noise exceeds
the distance $\tau$, a replacement is randomly drawn from the set
$\mathcal{U}-\mathcal{A}$.

The downside of this approach is seen in regions of sharply varying density
e.g., in the embedding space where one word has $2,000$ synonyms which
potentially fall within $\mathcal{A}$ and the rare word with no neighbors in
$\mathcal{A}$. Therefore to achieve (2) rather than having a fixed distance
from each word, we can also define the (randomized) $k-$closest words as
delineating our acceptable area. One potential benefit of this is, in dense
spaces, we can select closer candidates while simultaneously guaranteeing that
isolated words are replaced by one of their $k-$nearest neighbors regardless
of how far off it is.

Implementing either of these mechanisms however come with their own set of
challenges. For example, there isn’t a direct way to set a maximum distance
when drawing the multivariate laplacian noise that was proposed by [FBDD20].
One option will be to fix $\tau$, or the distance to the max randomized $k$ as
the local sensitivity described in Sec 6.2. Another option will be to rethink
the entire design of the randomizers such that the noise is not added to the
vector representation of the words, but to these $\tau$ distances.

#### Connections to Related Work

The traditional DP literature contains techniques to limit the privacy
preserving noise added to a mechanism. Just as with the median example, these
approaches take into consideration the actual dataset as opposed to the worst
case guarantees of a possible theoretical construct. In one work, [NRS07]
introduced the notion of smooth sensitivity where a smooth upper bound on the
local sensitivity is used to determine how much noise is added. They
demonstrated this method for privately computing the median of a dataset, and
the number of triangles in a graph.

Similarly, [DL09] introduced a paradigm called _Propose-Test-Release_ (PTR)
where: the algorithm proposes a bound on sensitivity, tests the adequacy of
the bound on the given dataset, and halts if the sensitivity is too high. The
PTR technique is connected to _robust statistics_ which is concerned with
outliers and rounding errors in a dataset [DS10].

In related work, [KNRS13] extended the notion of limiting the noise for
private graph analysis where the degree bound (a function of the number of
nodes in the graph) can be arbitrary. To achieve this, they set a $D$ bound on
the graph which aims to keep the sensitivity low while retaining as large a
fraction of the graph as possible. Similarly within the context of graphs
(specifically, social networks), [BBDS13] introduce the idea of _restricted
sensitivity_ without setting a bound on the degree of the graph. Instead, they
define a hypothesis (a subset of all possible datasets) over which they
compute the sensitivity.

These all describe principled approaches to limit the magnitude of noise
applied to a privacy preserving mechanism in the contexts of statistical and
graph analysis by redefining the sensitivity that controls the noise. As
opposed to the reviewed techniques, our representations are within a metric
space defined by word embeddings. The sensitivity is therefore described over
the vocabulary of the embeddings. Therefore, unlike statistical analysis where
releasing noisy counts still contains informative value, adding noise to word
representations, can result in a rapid degradation of utility.

##  7 Conclusion and Future work

In this proposal paper, we surveyed some of the challenges of building
differentially private mechanisms for generating text based on word
embeddings. We investigated approaches built on the $d_{\chi}$-privacy
framework in Euclidean space. The core issues stem from the non-uniformity of
the metric space defined by embeddings and the need to provide worst case
guarantees for outliers as required by differential privacy. This necessitates
a large amount of noise thus leading to utility impacts on downstream tasks
that rely on the generated text as input features.

Our approach was to explore the resulting utility issues from different
perspectives: first, considering methods of reducing the required noise by
deferring additional guarantees to other privacy amplification mechanisms that
do not require noise (such as shuffling). We then proposed three ways to
reduce the needed noise by accounting for the density around the word under
consideration. These included introducing a prior, re-calibrating the noise,
or truncating the noise. In future work, we plan to explore these approaches
in detail and provide a study on what works, when it works, and why. Our aim
is to provide a principled approach to studying these mechanisms in order to
accelerate the research and drive adoption.

## References

  * [ABCP13] Miguel E Andrés, Nicolás E Bordenabe, Konstantinos Chatzikokolakis, and Catuscia Palamidessi.  Geo-indistinguishability: Differential privacy for location-based systems.  In ACM CCS, pages 901–914. ACM, 2013.
  * [Abo18] John M Abowd.  The US census bureau adopts differential privacy.  In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 2867–2867. ACM, 2018.
  * [ACG+16] Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang.  Deep learning with differential privacy.  In ACM SIGSAC CCS, pages 308–318. ACM, 2016.
  * [ADK+19] Joshua Allen, Bolin Ding, Janardhan Kulkarni, Harsha Nori, Olga Ohrimenko, and Sergey Yekhanin.  An algorithmic framework for differentially private data analysis on trusted processors.  In Advances in Neural Information Processing Systems, pages 13657–13668, 2019.
  * [BBDS13] Jeremiah Blocki, Avrim Blum, Anupam Datta, and Or Sheffet.  Differentially private data analysis of social networks via restricted sensitivity.  In ITCS, pages 87–96. ACM, 2013.
  * [BBG18] Borja Balle, Gilles Barthe, and Marco Gaboardi.  Privacy amplification by subsampling: Tight analyses via couplings and divergences.  In Advances in Neural Information Processing Systems, pages 6277–6287, 2018.
  * [BBGN19] Borja Balle, James Bell, Adrià Gascón, and Kobbi Nissim.  The privacy blanket of the shuffle model.  In CRYPTO, pages 638–667. Springer, 2019.
  * [BEM+17] Andrea Bittau, Úlfar Erlingsson, Petros Maniatis, Ilya Mironov, Ananth Raghunathan, David Lie, Mitch Rudominer, et al.  Prochlo: Strong privacy for analytics in the crowd.  In SOSP, pages 441–459. ACM, 2017.
  * [BGJM17] Piotr Bojanowski, Edouard Grave, Armand Joulin, and Tomas Mikolov.  Enriching word vectors with subword information.  TACL, 5, 2017.
  * [BSG17] Vincent Bindschaedler, Reza Shokri, and Carl A Gunter.  Plausible deniability for privacy-preserving data synthesis.  VLDB Endowment, 10(5):481–492, 2017.
  * [BZH06] Michael Barbaro, Tom Zeller, and Saul Hansell.  A face is exposed for AOL searcher no. 4417749.  New York Times, 9(2008):8, 2006.
  * [CABP13] Konstantinos Chatzikokolakis, Miguel E Andrés, Nicolás Emilio Bordenabe, and Catuscia Palamidessi.  Broadening the scope of differential privacy using metrics.  In PETS, 2013.
  * [CM06] Kamalika Chaudhuri and Nina Mishra.  When random sampling preserves privacy.  In Annual International Cryptology Conference, pages 198–213. Springer, 2006.
  * [CPS15] Konstantinos Chatzikokolakis, Catuscia Palamidessi, and Marco Stronati.  Constructing elastic distinguishability metrics for location privacy.  PETS, 2015.
  * [CSU+19] Albert Cheu, Adam Smith, Jonathan Ullman, David Zeber, and Maxim Zhilyaev.  Distributed differential privacy via shuffling.  In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 375–403. Springer, 2019.
  * [DKY17] Bolin Ding, Janardhan Kulkarni, and Sergey Yekhanin.  Collecting telemetry data privately.  In NeurIPS, 2017.
  * [DL09] Cynthia Dwork and Jing Lei.  Differential privacy and robust statistics.  In STOC, volume 9, pages 371–380, 2009.
  * [DMNS06] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith.  Calibrating noise to sensitivity in private data analysis.  In TCC, pages 265–284. Springer, 2006.
  * [DS10] Cynthia Dwork and Adam Smith.  Differential privacy for statistics: What we know and what we want to learn.  Journal of Privacy and Confidentiality, 1(2), 2010.
  * [EFM+19] Úlfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Abhradeep Thakurta.  Amplification by shuffling: From local to central differential privacy via anonymity.  In ACM-SIAM, 2019.
  * [EPK14] Úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova.  Rappor: Randomized aggregatable privacy-preserving ordinal response.  In ACM SIGSAC CCS, 2014.
  * [FBDD20] Oluwaseyi Feyisetan, Borja Balle, Thomas Drake, and Tom Diethe.  Privacy- and utility-preserving textual analysis via calibrated multivariate perturbations.  In ACM WSDM, 2020.
  * [FDBD19] Oluwaseyi Feyisetan, Thomas Drake, Borja Balle, and Tom Diethe.  Privacy-preserving active learning on sensitive data for user intent classification.  arXiv preprint arXiv:1903.11112, 2019.
  * [FDD19] Oluwaseyi Feyisetan, Tom Diethe, and Thomas Drake.  Leveraging hierarchical representations for preserving privacy and utility in text.  In IEEE ICDM, 2019.
  * [FDM19] Natasha Fernandes, Mark Dras, and Annabelle McIver.  Generalised differential privacy for text document processing.  Principles of Security and Trust, 2019.
  * [FMTT18] Vitaly Feldman, Ilya Mironov, Kunal Talwar, and Abhradeep Thakurta.  Privacy amplification by iteration.  In FOCS, pages 521–532. IEEE, 2018.
  * [Gab99] Xavier Gabaix.  Zipf’s law for cities: an explanation.  The Quarterly journal of economics, 114(3):739–767, 1999.
  * [GDGK18] Quan Geng, Wei Ding, Ruiqi Guo, and Sanjiv Kumar.  Truncated laplacian mechanism for approximate differential privacy.  arXiv preprint arXiv:1810.00877, 2018.
  * [Has70] W Keith Hastings.  Monte carlo sampling methods using markov chains and their applications.  1970\.
  * [KKMN09] Aleksandra Korolova, Krishnaram Kenthapadi, Nina Mishra, and Alexandros Ntoulas.  Releasing search queries and clicks privately.  In WebConf. ACM, 2009.
  * [KLN+11] Shiva Kasiviswanathan, Homin Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith.  What can we learn privately?  SIAM Journal on Computing, 40(3), 2011.
  * [KMA+19] Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Keith Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, Rafael G. L. D’Oliveira, Salim El Rouayheb, David Evans, Josh Gardner, Zachary Garrett, Adrià Gascón, Badih Ghazi, Phillip B. Gibbons, Marco Gruteser, Zaid Harchaoui, Chaoyang He, Lie He, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi, Tara Javidi, Gauri Joshi, Mikhail Khodak, Jakub Konečný, Aleksandra Korolova, Farinaz Koushanfar, Sanmi Koyejo, Tancrède Lepoint, Yang Liu, Prateek Mittal, Mehryar Mohri, Richard Nock, Ayfer Özgür, Rasmus Pagh, Mariana Raykova, Hang Qi, Daniel Ramage, Ramesh Raskar, Dawn Song, Weikang Song, Sebastian U. Stich, Ziteng Sun, Ananda Theertha Suresh, Florian Tramèr, Praneeth Vepakomma, Jianyu Wang, Li Xiong, Zheng Xu, Qiang Yang, Felix X. Yu, Han Yu, and Sen Zhao.  Advances and open problems in federated learning, 2019.
  * [KNRS13] Shiva Prasad Kasiviswanathan, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith.  Analyzing graphs with node differential privacy.  In Theory of Cryptography Conference, pages 457–476. Springer, 2013\.
  * [LPP20] Peeter Laud, Alisa Pankova, and Martin Pettai.  A framework of metrics for differential privacy from local sensitivity.  Proceedings on Privacy Enhancing Technologies, 2020(2):175–208, 2020.
  * [LQS12] Ninghui Li, Wahbeh Qardaji, and Dong Su.  On sampling, anonymization, and differential privacy or, k-anonymization meets differential privacy.  In ASIA-CCS, pages 32–33, 2012.
  * [MRR+53] Nicholas Metropolis, Arianna W Rosenbluth, Marshall N Rosenbluth, Augusta H Teller, and Edward Teller.  Equation of state calculations by fast computing machines.  The journal of chemical physics, 21(6):1087–1092, 1953.
  * [MSC+13] Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean.  Distributed representations of words and phrases and their compositionality.  In NeurIPS, pages 3111–3119, 2013.
  * [MSZ15] Mahnush Movahedi, Jared Saia, and Mahdi Zamani.  Secure multi-party shuffling.  In International Colloquium on Structural Information and Communication Complexity, pages 459–473. Springer, 2015.
  * [MT07] Frank McSherry and Kunal Talwar.  Mechanism design via differential privacy.  In FOCS, volume 7, pages 94–103, 2007.
  * [NRS07] Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith.  Smooth sensitivity and sampling in private data analysis.  In ACM Symposium on Theory of Computing, pages 75–84. ACM, 2007\.
  * [PSM14] Jeffrey Pennington, Richard Socher, and Christopher Manning.  Glove: Global vectors for word representation.  In EMNLP, pages 1532–1543, 2014.
  * [SS15] Reza Shokri and Vitaly Shmatikov.  Privacy-preserving deep learning.  In ACM CCS, pages 1310–1321, 2015.
  * [STT+12] Reza Shokri, George Theodorakopoulos, Carmela Troncoso, Jean-Pierre Hubaux, and Jean-Yves Le Boudec.  Protecting location privacy: optimal strategy against localization attacks.  In ACM CCS, pages 617–627. ACM, 2012.
  * [Swe02] Latanya Sweeney.  k-anonymity: A model for protecting privacy.  IJUFKS, 10(05):557–570, 2002.
  * [Tea17] Apple’s Differential Privacy Team.  Learning with privacy at scale.  Apple Machine Learning Journal, 1(9), 2017.
  * [War65] Stanley L Warner.  Randomized response: A survey technique for eliminating evasive answer bias.  Journal of the American Statistical Association, 60(309):63–69, 1965.
  * [WE18] Isabel Wagner and David Eckhoff.  Technical privacy metrics: a systematic survey.  ACM CSUR, 51(3):57, 2018.

  *[ML]: Machine Learning
  *[DP]: Differential Privacy
  *[NLP]: Natural Language Processing
  *[]:
  *[LDP]: Local   ()