SEQPATE: DIFFERENTIALLY PRIVATE TEXT GENERATION VIA KNOWLEDGE DISTILLATION
Year: 2021

Abstract:
Protecting the privacy of user data is crucial when training neural text generation models, which may leak sensitive user information during generation. Differentially private (DP) learning algorithms provide guarantees on identifying the existence of a training sample from model outputs. PATE is a DP learning algorithm that fits large models well, such as GPT. In this paper, we propose SeqPATE that adapts PATE to text generation while satisfying DP. There are two key challenges in adapting PATE to text generation: (i) obtaining sequence-level supervision for text generation, and (ii) reducing noise required to protect the privacy given a large output space (i.e. vocabulary size). For (i), we generate pseudo input and reduce the sequence generation problem to the next word prediction. For (ii), we reduce the output space with top-k and top-p selection strategy that dynamically filters the candidate words; and we refine the teacher aggregation of PATE to avoid the low agreement rates due to voting over the large output space. To limit the privacy loss, we design an efficient knowledge distillation to reduce the frequency of distilling from the private data. We apply SeqPATE to a simple text generation task (sentence completion) and achieve 39% and 28% gains in Bleu4 on two datasets.

text: Protecting the privacy of user data is crucial when training neural text generation models, which may leak sensitive user information during generation. Differentially private (DP) learning algorithms provide guarantees on identifying the existence of a training sample from model outputs. PATE is a DP learning algorithm that fits large models well, such as GPT. In this paper, we propose SeqPATE that adapts PATE to text generation while satisfying DP. There are two key challenges in adapting PATE to text generation: (i) obtaining sequence-level supervision for text generation, and (ii) reducing noise required to protect the privacy given a large output space (i.e. vocabulary size). For (i), we generate pseudo input and reduce the sequence generation problem to the next word prediction. For (ii), we reduce the output space with top-k and top-p selection strategy that dynamically filters the candidate words; and we refine the teacher aggregation of PATE to avoid the low agreement rates due to voting over the large output space. To limit the privacy loss, we design an efficient knowledge distillation to reduce the frequency of distilling from the private data. We apply SeqPATE to a simple text generation task (sentence completion) and achieve 39% and 28% gains in Bleu4 on two datasets.

heading: 1 INTRODUCTION
text: Recent work showed that sensitive user information in training corpora, such as address and name, can be extracted from text generation models (Carlini et al., 2019; 2020). Providing privacy guarantees to the text used to train text generation models has become a critical problem. Differential privacy (DP) provides provable guarantees against the identification of individuals in the dataset. Deep learning models with DP guarantees ensure the existence of a specific training sample cannot be detected.
The most popular DP algorithm for deep learning is Noisy-SGD (Song et al., 2013; Bassily et al., 2014; Abadi et al., 2016), which adds noise to the gradients. However, the advantage of NoisySGD is weaken as the model becomes larger (Yu et al., 2020), and NoisySGD requires a per-example gradient clip, which causes non-convergence and system overheads (Zhu et al., 2020; Bu et al., 2021). Applying Noisy-SGD to large text generation models (e.g. GPT-2) requires additional tricks such as memory reduction (Li et al., 2021) and advanced fine-tuning strategies (Yu et al., 2021). PATE (Papernot et al., 2017) is a DP learning model using a teacher-student framework: a student accessing non-sensitive data distills knowledge from the aggregated predictions of multiple teachers trained on sensitive data. Calibrated noise is added to the aggregated predictions to satisfy DP. PATE can handle large models since its privacy cost derives from the knowledge distillation instead of the model parameters. PATE takes advantage of non-sensitive data which is also available in our scenario.
In this paper, we propose, SeqPATE, a DP learning algorithm for text generation that exploits both sensitive and non-sensitive data by knowledge distillation. Specifically, we adapt PATE for text generation. The adaptation is challenging due to the sequential generation and the large output space (i.e. vocabulary size) in text generation. Firstly, to obtain the sentence-level supervision for text generation, directly applying PATE needs to roll out all teachers to produce a sentence (i.e. all teachers must vote to generate a word, which is then used as the input for the next word prediction). Running inference for a large number of teachers can be costly. Secondly, the large output space results in (i) low agreement rate among teachers and (ii) large noise required by DP, both would significantly hurt task performance.
To avoid sequential generation, we generate pseudo data using a pre-trained language model such that teachers only need to provide token-level supervision given the pseudo input. To handle the large output space, we aggregate teachers’ outputs by interpolating their output distributions instead of voting with argmax predictions. To reduce the noise scale, we propose strategies to dynamically filter candidate words that only keep words with large probabilities. Further, we design an efficient knowledge distillation strategy that only queries the teacher when the student has poor performance.
We evaluate our method on sentence completion, a simple but representative task of text generation. Compared to baselines including Noisy-SGD (Kerrigan et al., 2020), SeqPATE improves Bleu4 by 39% and 28% on two datasets with meaningful privacy protection 1. We observe SeqPATE works particularly well under relatively strong privacy protection (e.g., ε ≤ 2) compared to Noisy-SGD. Our contribution is threefold: (i) Our model significantly surpasses baselines and makes DP algorithm achieve satisfactory performance on text generation; (ii) We propose several practical strategies to enable SeqPATE to handle text generation with a sequential of classifications over larger output spaces; (iii) We are the first to adapt PATE, an effective DP algorithm, to text generation.

heading: 2 PROBLEM SETUP
text: Our goal is to achieve the privacy protection defined by DP in text generation: preventing attackers from inferring whether a sample or an n-gram appears in the training set. (Formal definition in Sec. 5)
PATE assumes students are trained on unlabeled non-sensitive data. Similar to PATE, our setting contains two textual datasets: 1. a private set Dpri from a corpus with sensitive information. 2. a public set Dpub without sensitive information (e.g. incomplete or masked text spans) or data contributors (e.g. volunteers) have no objection to publishing their data. Algorithms are required to protect the privacy on the private set and can ignore the privacy protection on the public set. The final goal is to do well on the private set during inference.
Text generation is to generate a sequence of words S = {w1, w2, . . . , wl}. Our application is a simple text generation task, sentence completion, which aims to generate the remaining part of a sentence w1:l given its prefix p1:l′ , where p1:l′ and w1:l are the abbreviation of {p1, p2, . . . , pl′} and {w1, w2, . . . , wl} respectively. p1:l′ and w1:l compose a complete sentence. We collect some input prefixes p1:l′ to compose the public set Dpub and the original samples (complete sentences) compose the private set Dpri. Such a setting fits for some real-world text generation applications: in dialog systems, the training samples from online services consist of questions and responses. The questions from customer service staffs or service robots can be public and the response from users carrying individual information should be private. In writing assistants where a sample has an input prompt and an essay body, the prompt can be public but the body written by data contributors is private.

heading: 3 BACKGROUND ON DP AND PATE
text: Differential privacy (DP) (Dwork et al., 2006; 2014) is a quantifiable definition of privacy that provides provable guarantees on identifications of individuals in the dataset. ML algorithms with DP guarantee ensure that each individual training sample has a degree of plausible deniability, i.e., the trained model is just as likely as to have been trained on an alternative dataset without that sample.
PATE, designed for classification tasks, takes advantage of an unlabeled public dataset Dpub and also trains on a labeled private Dpri in a semi-supervised scenario. PATE is model-agnostic and treats models as black-boxes. PATE (Papernot et al., 2017) achieves DP via a teacher-student framework with M teacher models and a student model, where the student learns from the private data via knowledge distillation through teachers. PATE consists of three parts,
• Teacher models are trained on the private set Dpri . Dpri is shuffled and divided into M disjoint subsets, and m-th subset serves as the training set for m-th teacher model fmϕ .
• Teacher aggregation merges teachers’ outputs. After teachers’ training, each teacher fmϕ conducts the prediction (classification) on student’s training set Dpub. To satisfy DP, PATE aggregates M
1We choose ε = 2. DP with ε ∈ [0.1, 5] is regarded as a meaningful protection (Triastcyn & Faltings, 2020).
teachers’ by voting with their top-1 predictions. PATE adds noise to aggregated teacher outputs so that attackers cannot access the exact outputs to infer original information in samples.
• A student model fθ is trained on the public set Dpub and distills knowledge from private set (via the teachers) without accessing the private samples. In this way, the sensitive information in the private set is preserved even if the student’s architecture and parameters are public or reverse-engineered by an adversary. We publish only the student model for prediction.

heading: 4 APPROACH
text: Fig. 1 shows an overview of the SeqPATE. Given the public prefix (e.g., “Cats sit”), we first obtain pseudo inputs by generating the remaining part of the whole sentence (e.g., “Cats sit on the mats”) using a pre-trained language model (Sec. 4.1). The teachers’ output distributions are then averaged to provide word-level supervision on the whole sentence (Sec. 4.2). To reduce the noise over large output space and limit the privacy loss, we propose top-k / top-p selection to dynamically filter the unimportant candidates and propose efficient knowledge distillation to reduce the number of teacher queries (Sec. 4.3). Our training algorithm is shown in Appendix A.

heading: 4.1 STUDENT MODEL
text: Conventional text generation models generate words in a sentence step-by-step and left-to-right. Naively applying PATE to the above paradigm requires all the teachers to be roll out to obtain supervision at every step, where all the teachers aggregate to generate a word at each step and the word acts as the next input for all teachers. This means we should conduct all teachers’ inferences simultaneously and interdependently, which is costly in both computation (involving hundreds of teachers) and privacy costs.
Hence, in SeqPATE, we employ GPT to generate pseudo sentences and conduct teacher inference and student training on the pseudo sentences. Firstly, given a prefix in Dpub, we employ the public released pre-trained GPT to conduct the inference to complete a pseudo sentence. All the generated pseudo sentences compose the student’s training set, denoted as D̃pub. Secondly, we conduct teacher inference and student training on the sample S = {w1, w2, . . . , w|S|} from D̃pub. At the i-th step, for the training of conventional text generations, the student learns to generate a word ŵi given its previous words w1:i−1. At the i-th step, our teachers conduct the inference to generate ŵi given the input w1:i−1 from the sample S. Then, each teacher provides its output for aggregation. All teachers share the same input with the student so that the outputs of teachers and student are aligned and comparable.

heading: 4.2 TEACHER AGGREGATION
text: The original PATE aggregates teacher results by taking the majority vote of the predicted labels from all the teachers. However, this aggregation strategy does not fit for the large output space in text generation. This is because the number of votes for each candidate may be very low and it would result in low agreement. For example, multiple candidates may tie for the top-1 prediction.
Therefore, inspired by (Hinton et al., 2015; Chen et al., 2020), we aggregate M teachers’ results by averaging their output distributions, where each teacher model is trained on one of the disjoint subsets divided from the private set Dpri. At the i-th step on teacher inference, the m-th teacher model fmϕ predicts a word ŵi with a probability pmϕ (ŵi). Then, our model aggregates all teachers’ probabilities by averaging pϕ(ŵi) = 1M ∑M m=1 p m ϕ (ŵi). Like most DP methods, our model adds noises so that the privacy impact can be analyzed and bounded. Different from PATE that adds noise to vote numbers, we add noise to the aggregation of teachers’ output distributions. Following (Papernot et al., 2018), we apply the Gaussian mechanism which adds i.i.d. N (0, σ2) to each coordinate, where σ controls the strength of privacy protection (more details in Sec. 5).

heading: 4.3 SUPERVISION ON THE STUDENT MODEL
text: Reducing output space via top-k or top-p selection. Recall that the teacher output is a distribution over all words in the vocabulary, and the noise must be added to each coordinate to satisfy DP. To reduce the output dimension (hence the amount of noise), we only assign the probability mass to a subset of candidates Wi. For all teachers and the student, we assign zero probability mass to any candidates not in Wi and re-normalize distribution as shown in Eq. 1, where g(·) is the normalizing function. This operation means the words not in Wi will never occur in student’s training and teachers’ supervision, so those words do not need noise to provide protection.
g(p(ŵi | w1:i−1)) =  p(ŵi | w1:i−1)∑ w∈Wi p(w | w1:i−1) if ŵi ∈ Wi
0 otherwise. (1)
We determine the subset Wi by two selection strategies: top-k and top-p. In the top-k selection, at i-th step, we select the top-k candidates according to the probabilities generated by the student model. Further, inspired by nucleus sampling (Holtzman et al., 2019), we propose a top-p selection that chooses the minimum k where the cumulative probability of the top-k words is larger than a constant close to 1 (e.g. 0.95) such that the candidate set covers a large proportion of the distribution. We note that the candidate selection is based on the student’s output on public or already released input, thus not affecting the privacy guarantee. This choice improves the privacy-utility tradeoff by adaptively allocating the available privacy budgets to release the information more relevant to the task.
Efficient knowledge distillation. Reducing the number of querying teachers results in better privacy protection. Therefore, we acquire teacher supervision only when the student has poor performance. Concretely, we measure student’s performance on each token by comparing its output distribution with the ground truth token (from D̃pub). Let rwi be the rank of the ground truth token wi in the student’s predicted distribution, (i.e. the number of tokens with higher or equal probability). The student model acquires the teachers’ supervision only if rwi is larger than a certain threshold rc. We note that the selection of tokens relies only on the student and is independent of the teachers, thus the selection does not cause additional privacy loss.
Training objectives. Different from the semi-supervised setting in PATE, our student model is supervised by both teachers’ aggregation and labels from the pseudo public set D̃pub, since text generation corpora are naturally labeled, unlike in classification tasks. Even if the pseudo set D̃pub provides only pseudo samples, the labels from those samples are also useful given that the number of querying teachers is limited due to privacy concerns. The student’s loss function consists of two parts as shown in Eq. 2,
• LKLi shows teachers’ supervisions. The student learns from teachers by minimizing KL divergence between the student output distribution pθ and the merged teacher output distributions pϕ.
• LNLLi shows the supervisions from the pseudo public set D̃pub generated by GPT. As conventional language models, our student model is trained by negative log-likelihood (NLL) loss on D̃pub. The words wi in the training sample is naturally the label for the student fθ(w1:i−1) at the i-th step.
LKLi = KL
( g( 1
M ( M∑ m=1 pmϕ (· | w1:i−1) +N (0, σ2))) ∥ pθ(· | w1:i−1)
) ,
LNLLi = − log pθ(wi | w1:i−1), L = ∑
S∈D̃pub
|S|∑ i=1 (LNLLi + λLKLi ). (2)
where Li is loss at i-th step, |S| denotes the length of sentence S, and λ balances the two terms. Meanwhile, the noise scale σ is discussed in Sec. 5. g(·) is the re-normalization function used in Eq. 1 that re-normalizes the aggregated probabilities on the selected top-k or top-p words with noise 2. According to the efficient knowledge distillation strategy, at each step, the loss Li is the combination of LNLLi and LKLi if the student needs teachers’ supervision; otherwise, Li = LNLLi .

heading: 5 PRIVACY ANALYSIS

heading: 5.1 PRELIMINARY OF DIFFERENTIAL PRIVACY
text: Let D, D′ denote two neighboring datasets which differ at only one individual. Definition 1 (Differential privacy). For ε > 0 and δ ≥ 0, a randomized algorithm M : Xn → Y is (ε, δ)-differentially private if for any neighboring datasets D ∼ D′ and any S ⊆ Y ,
Pr[M(D) ∈ S] ≤ eε · Pr[M(D′) ∈ S] + δ
The definition ensures that it is information-theoretically impossible for an adversary to infer whether the input dataset is D or D′ even with arbitrary side information. The definition is also future proof thanks to its closure to post-processing. Lemma 2 (Post-processing). If M obeys (ε, δ)-DP, then for any function f , f ◦M is also (ε, δ)-DP.
One notable property of DP is that it automatically protects the privacy of groups of multiple units.
Lemma 3 (Group privacy). An (ε, δ)-DP mechanism M on individuals is (kε, e kε−1 eε−1 δ)-DP on groups of size k for all integers k ≥ 1. Lemma 4 (Analytical Gaussian mechanism (Balle & Wang, 2018)). For a numeric query f : Xn → Rd over a dataset D, the randomized algorithm that outputs f(D) + Z where Z ∼ N (0, σ2Id) satisfies (ε, δ(ε))-DP for all ε ≥ 0 and δ(ε) = Φ( ∆2σ − εσ ∆ )− e εΦ(− ∆2σ − εσ ∆ ). where ∆ := ∆ (f) 2 = maxD∼D′ ∥f(D)− f(D′)∥2 is the global L2 sensitivity of f and Φ is the CDF function of N (0, 1).
The above is the (ε, δ)-DP of a single Gaussian mechanism, and the following lemma shows that we can use the same result for an adaptive composition of a sequence of Gaussian mechanisms. Lemma 5 (Composition of Gaussian mechanisms (Dong et al., 2019)). The adaptive composition of a sequence of Gaussian mechanisms with a noise level σ1, σ2, . . . and global L2 sensitivity ∆1,∆2, . . . satisfies (ε, δ(ε))-DP for all ε ≥ 0 and δ(ε) ≤ δM(ε) where M is a Gaussian mechanism with noise multiplier σ/∆ = (∑ i(∆i/σi) 2 )−1/2 .
Specifically, the adaptive composition of a k identical Gaussian mechanism with noise multiplier σ satisfies the same privacy guarantee of that of a single Gaussian mechanism with a noise multiplier σ/ √ k. By fixing k and ε, we can calibrate the noise by choosing an appropriate σ in our algorithm.
2Mathematically, the input of the g(·) may be negative and we re-normalize it to 0. Practically, we observed being negative is extremely rare since the M is very big (2000) and the first term dominates the input of g(·)

heading: 5.2 DIFFERENTIAL PRIVACY AT THE SAMPLE LEVEL
text: Recall that we partition the private dataset to M disjoint subsets, and train a teacher model on each subset. Let vector xi ∈ R|V| denote the probability distribution predicted by the i-th teacher model for a specific word, where |V| is the vocabulary size. The function f(D) := ∑M i=1 xi is the sum of the probability distributions predicted over all teachers. Since the dataset is disjoint and also has no repeating sample, changing one sample will only affect one teacher model. For neighboring datasets D, D′, let j denote the index of different teacher models, i.e., xj ∈ D and x′j ∈ D′ are different. Then, the sensitivity ∆ in Lemma 4 & 5 is (Detailed deduction in Appendix B),
∆ := ∆ (f) 2 = ∥f(D)− f(D′)∥2 ≤ ∥xj − x′j∥2 ≤
√ 2,
Then, adding noise calibrated in Lemma 5 to each coordinate is sufficient to preserve (ε, δ(ε))-DP for f(D). Finally, when we extract top-k coordinates of f(D) (Sec. 4.3), the privacy guarantee also holds according to the post-processing property. Intuitively, the information about whether a sample occurs in the private training set is protected and the protection satisfies (ε, δ(ε))-DP.

heading: 5.3 DIFFERENTIAL PRIVACY OF USER’S SECRET PHRASES
text: The above analysis focuses on DP at the sample level, but the privacy guarantee also applies to individual users (who contributed many samples), which prevents each user’s secret phrases (or text spans), such as SSN number, phone number, and addresses from being memorized (or generated as is) by the model. Consider a secret phrase t that occurs st times (st ≥ 1) in the private set. We obtain DP guarantee for each t separately 3 in the following two scenarios. In the first scenario where the teachers’ data is not partitioned by users, the protection on t satisfies (stε, e stε−1 eε−1 δ)-DP according to the group privacy lemma.
SeqPATE allows us to partition the teachers’ training data by users. In this scenario, adding or removing a user (and all her samples) only affects one teacher, thus the same privacy guarantee we have derived for sample-level DP applies to the user level, too. As a result, our approach enjoys stronger guarantee than naively applying the group privacy lemma. Our approach depends only on the total number of teachers affected, which is bounded by s̃t := min{st,# of users who know t}. s̃t is often 2 or 3 (e.g., husband and wife, parents and child), even if st is large. Clearly, adding or removing a phrase t will result in a sensitivity √ 2s̃t, and the exact (ε, δ(ε, s̃t))-DP for phrase t can be obtained according to Lemma 4 & 5, where δ(ε, s̃t) = Φ( s̃t√2σ − εσ√ 2s̃t )− eεΦ(− s̃t√ 2σ − εσ√ 2s̃t
). The above user-level protection is also one merit of SeqPATE that NoisySGD does not have.
How does DP prevent memorization? We remark that the protection against unintended memorization of a model follows from the definition of DP. Consider the attack by (Carlini et al., 2019), which uses a language model to predict a secret phrase t given a prefix. By the closure to post-processing, the prediction also satisfies DP. Take S to be the undesirable event that the model correctly generates the phrase t. The definition of DP implies that the probability of S to happen when t is part of the training data is at most eε larger than the probability of an alternative model trained without t in the data. The chances for the latter model to generate a sequence with t is astronomically small, thus DP implies that the probability of S under the former model needs to be just as small.

heading: 6 EXPERIMENTS

heading: 6.1 EXPERIMENTAL SETTING
text: We evaluate our model on two datasets. AirDialog dataset (Wei et al., 2018) consists of 1M utterances from custom service dialog about flight booking; Europarl v6 dataset 4 consists of 2M English sentences collected from European Parliament. Pre-trained GPT-2 (Radford et al., 2018) provides initial parameters for comparing methods. Before student training, we conduct additional fine-tuning on the public data D̃pub via NLL loss to provide initialization. We evaluate the quality of generated
3A formal definition of this is called personalized differential privacy, first seen in (Ghosh & Roth, 2011) 4www.statmt.org/europarl
texts with PPL (Perplexity, the lower the better) and B-n (Bleu-n, the higher the better) (Papineni et al., 2002) and evaluate the performance of privacy protection with P-n, which is the fraction of unique n-grams in model generated texts that can be found in the private text (lower score indicates fewer privacy leaks). Our base model is GPT2-small and the default number of teacher models is 2,000. The batch size is 32 for all comparing methods and the λ in Eq. 2 is 20. (See details about datasets, settings, metrics, implementation, and more experimental results in Appendix C to L).

heading: 6.2 OVERALL PERFORMANCE
text: Table 1 shows the performance on the two datasets. Pri-GPT is the GPT model trained on the private set Dpri without privacy protection, acting as an upper bound on the task performance. The high P-n scores on Pri-GPT show most generated n-grams may come from Dpri, indicating a serious issue with privacy leaks in current text generation models. Pub-GPT uses the pre-trained GPT model to our setting without fine-tuning. Pub-GPT+D̃pub is further fine-tuned on the pseudo data and outperforms Pub-GPT, indicating that the pseudo dataset helps in this task (Experiments in Appendix L also verify that.). The two baselines do not involve any information from the private data, so their P-n are the upper bound and their utlities are the worst (note that our goal is to do well on Dpri in inference). DP learning algorithms are our main baselines. Pub-GPT+DP-SGD is initialized by Pub-GPT and further trained on Dpri with DP-SGD (Noisy-SGD) (Abadi et al., 2016; Kerrigan et al., 2020). PubGPT+DP-SGD+D̃pub further fine-tunes the Pub-GPT+DP-SGD on D̃pub. The small gap between the two methods demonstrates DP-SGD cannot utilize D̃pub well. Our method, SeqPATE, significantly outperforms the DP baselines (+39.3% and +28.0% in Bleu4) while ensuring the same strength of privacy protection in terms of P-n and ε. Note that, we conduct the experiments based on the sample level privacy of ε = 2 mentioned in Sec. 5.2, and the experimental results also reflect the protection on users’ secret phrase t mentioned in Sec. 5.3. However, the strength of the protection is weaker than the sample-level protection. The model satisfies (ε, δ(ε, s̃t))-DP or (stε, e stε−1 eε−1 δ)-DP on the secret phrase t (ε = 2) as mentioned in Sec. 5.3. SeqPATE does better in empirical metrics on privacy compared to DP-SGD even if ε = 2 is the same theoretically; this provides empirical evidence of our discussion in Sec. 5.3 on providing stronger guarantees for phrases that appear more than once.
The curves in Fig. 2 show the private-utility tradeoff of all DP algorithms in AirDialog (subfigure a & b) and Europarl v6 (subfigure c & d) dataset 5. DP with ε ∈ [0.1, 5] is considered to provide a meaningful protection, and we observe that SeqPATE outperforms DP-SGD in this range. SeqPATE
5For non-DP methods, we consider ε to be zero for baselines without using private data and ε to be infinity for baselines without privacy protection.
does not work better than DP-SGD when ε ≥ 5. The reason is DP-SGD approaches Pri-GPT as ε approaches infinity (i.e. the noise approaches 0). However, SeqPATE with an infinite ε is still weaker than Pri-GPT because each teacher in SeqPATE is trained on a small partition of the full data. The grey lines show the performance of Pub-GPT+D̃pri and the area above the line indicates that the DP methods outperform Pub-GPT+D̃pri (DP methods on the private data outperforms the non-DP methods on the non-private data). The area indicates a range where DP methods (with private data) are useful for this application. Our method always reaches that area when ε ≥ 1 but DP-SGD hardly exceeds the grey line, the very trivial baseline, with ε ≤ 5.
AirDialog Europarl v6 PPL B-4 P-4 PPL B-4 P-4
top-p 13.67 0.78 0.17 37.80 0.55 0.45 top-k=1 18.37 0.25 0.09 46.25 0.53 0.45 top-k=10 14.57 0.79 0.21 45.90 0.55 0.40 top-k=50 13.50 0.70 0.18 37.91 0.53 0.40 top-k=100 13.96 0.76 0.19 38.48 0.57 0.50 top-k=200 14.65 0.72 0.17 39.55 0.53 0.46
Table 3: Analyses about top-k and top-p strategies.

heading: 6.3 ABLATION STUDIES AND FURTHER ANALYSES
text: In the ablation studies (Table 2), SeqPATE mainly outperforms its variants shown in rows 2 to 7 verifying the effectiveness of our strategies, where −X represents SeqPAET’s variant without the strategy X . −Merge P is the variant aggregating the teachers by voting instead of merging the probabilities. Its poor performance shows that voting is not suitable for text generation with a large output space where the voting leads to low agreement rates. −KL means the student learns from the aggregation of teachers’ top-1 predictions via NLL loss instead of KL loss. The sharp performance drop on −KL indicates the importance of KL loss. The performance of −NLL slightly decreases, indicating that NLL loss makes a little contribution to SeqPATE. The reason is that we have pre-trained on the student’s training set via NLL before student training. The promotion caused by efficient knowledge distillation (Effi KD) on AirDialog is larger than that on Europarl v6, which shows the “clever” student (e.g. models on AirDialog with low PPL and high Bleu) benefits more from this strategy since it can sharply save the privacy cost and spend the cost where the student strongly needs. −Gaussian means we use Laplace mechanism as mentioned in PATE instead of Gaussian mechanism, which shows that the Gaussian mechanism works better. −All indicates discarding all above strategies, which is similar to but not equivalent to the original PATE (the difference is that PATE needs to roll out all teachers (Sec. 4.1), which disables PATE from working on text generation). The poor performance of −All verifies that the original PATE is not adaptive to text generation. Table 3 shows the performance of the top-p and top-k selection strategies (Sec. 4.3). As shown in row 1, our full model employs the top-p selection (the threshold µ = 0.95) surpasses most variants with manually chosen k (rows 2 to 6). A selection with a too small k (k = 1 & k = 10) implies discarding too much useful information from the supervision (k = 1 is different to −KL in Table 2, which uses Top-1 of teachers’ results). A selection with oversize k results in involving more useless noise: the candidates with very small probabilities should be rarely sampled during generation but random noise may increase their probabilities, so models may generate words that are misled by the noise. Supervisions on top-k candidates with k = 50 and k = 100 yields relatively good performance.
Tables 4 & 5 in the Appendix shows more teachers lead to better results since the noise assigned to each teacher drops linearly as the teacher’s numbers go up (as Eq. 2). We choose ε = 2 for all results in Table 2 to 5. P-n for all the results in a dataset to be roughly on the same level, except for some methods (e.g. row 2 in Table 3) that perform very badly in all metrics. It shows SeqPATE has the stable performance of protection if ε is fixed (no matter which variant and strategy do we use).

heading: 7 RELATED WORK
text: Privacy protection is becoming crucial in deep learning models. Research in this area can be categorized into three directions (Liu et al., 2021). Encryption approaches are to add encryption on
training data (Brickell et al., 2007; Bost et al., 2015) or machine learning (ML) models (Aono et al., 2017). Aggregation approaches generally come along with distributed training where many parties join the training of an ML model with the purpose of maintaining the privacy of the dataset from each party (Shokri & Shmatikov, 2015; Konečnỳ et al., 2016). Obfuscation approaches reduce the precision of the data or model by importing noise into the original input (Zhang et al., 2018), model parameters (Rubinstein et al., 2012), or model gradients (Abadi et al., 2016; McMahan et al., 2018).
As a sub-topic of the obfuscation approach, differential privacy (DP) (Dwork et al., 2006; 2014) formally defines and quantifies privacy. ML models with DP guarantee (Wang et al., 2015; Park et al., 2016; Ziller et al., 2021) prevents the existence of individual training examples from being detected (Carlini et al., 2019). Some researchers protect the privacy of empirical risk minimization (ERM) classifier (Chaudhuri et al., 2011) and SVM (Rubinstein et al., 2012) with DP. Following (Song et al., 2013), DP-SGD (Abadi et al., 2016) achieves DP on deep learning models by applying the noise to the clipped gradients. (Bu et al., 2020). Pichapati et al. (2019) adaptively clip the gradient on DP-SGD. PATE (Papernot et al., 2017) transfers the knowledge from teacher models trained on private data with injected noise to a student model. KNN-PATE (Zhu et al., 2020) refines PATE by accessing only the k-nearest neighbors from the private set instead of the whole private set. The above approaches are not customized for text generation models.
One direction of privacy protection in text generation is to protect author-level (user-level) information. The methods prevent attackers from inferring the author attributes (e.g. gender, age) (Li et al., 2018) and the relation between sensitive information and authors (Mireshghallah et al., 2021). Shokri et al. (2017) and Song & Shmatikov (2019) infer the membership (whether a given user’s data is used to train the model) given a black-box model. Another direction is to prevent attackers from extracting sensitive information in the training set by analyzing the generated outputs (Nakamura et al., 2020; Kerrigan et al., 2020), which is an urgent need since Carlini et al. (2020) achieve the extraction. Our application focuses on this direction. In this direction, some researchers use regularization, including dropout (Srivastava et al., 2014) and quantization (Hubara et al., 2017), to restrict the model capacity to avoid models memorizing too much original text from the privacy training set (Carlini et al., 2019). Anonymization methods (Maeda et al., 2016; Suzuki et al., 2017) detects sensitive text spans in training sets and replace the spans with non-sensitive texts. The above methods are non-DP algorithms, which make sense intuitively but do not provide quantifiable and provable guarantees for privacy protection.
Some researchers apply DP to text generation. For user-level privacy, ER-AE (Bo et al., 2021) augments the semantic information in the generated text to hide authors’ writing styles for authorship anonymization. McMahan et al. (2018) propose a recurrent language model with a DP guarantee against the identification of the users. Kerrigan et al. (2020) adapt DP-SGD to text generation, which prevents the (not the user-level) sensitive training data from being extracted from text generation models. Some of our concurrent works also follow this direction. Li et al. (2021) apply DP-SGD to large pre-trained language models and reduce the memory usage of those models. Yu et al. (2021) propose a framework to carry some advanced fine-tuning strategies on pre-trained language models with DP-SGD.

heading: 8 CONCLUSION
text: In this paper, we propose, SeqPATE, a framework to protect the privacy of the training data for text generation model with DP guarantees. SeqPATE achieves a good privacy-utility tradeoff by leveraging both private and public data. As an extension of PATE, SeqPATE can handle the sequential generation paradigm with large output space at each step and thus is adaptive for text generation models. We avoid rolling out the teachers by providing pseudo inputs for teacher inference and student training and aggregate teachers by merging probabilities instead of voting. We further reduce the output space by top-k or top-p selection and limit the privacy loss via an efficient knowledge distillation. SeqPATE improves the baselines a lot and makes the private data useful to text generation with a meaningful strength of privacy protection. In the future, we will apply SeqPATE to some real-world applications, e.g. dialog systems and writing assistants.

heading: 9 REPRODUCIBILITY STATEMENT
text: We’ve submitted our source code as the supplementary material. We introduce the two datasets we used in Appendix C, where we introduce the details about the dataset and also append the link or citation of the dataset. For all our experiments, we adopt autodp (Wang et al., 2019) — an open-source library that implements the analytical Gaussian mechanism for privacy accounting and calibration. The experimental setting and hyper-parameters can be found in Appendix D. Since we propose a new metric in our experiments, we introduce the new metric with detailed equations in Appendix E.

heading: 10 ETHICAL CONSIDERATIONS
text: This paper aims to protect privacy in training the text generation models, so our paper is designed for tackling some ethical issues about privacy concerns in some existing text generation models (e.g. GPT-2). In terms of motivation and the algorithm, our paper would not cause ethical issues.
However, we should also consider some special situations where someone intentionally applies our model to illegal applications. Someone may employ text generation models to create fake news or misinformation and protect himself or herself from being detected. For this purpose, they may use our model for their illegal application. In the future, we will add some constraints to our model so that our model cannot generate text for illegal applications (e.g. fake news).
In addition, we know large ε (e.g. ε = 500) cannot provide a meaningful protection. We should carefully use our model and cannot assume the model is perfect no matter what parameters (ε and δ) do we use. One possible unethical application is to collect the data from users who believe our model can fully protect their privacy regardless of the strength of privacy protection (in terms of the value of ε). Hence, we kindly remind the researchers, who will use this model, to pay more attention to the strength of privacy protection. Further, we should prevent some researchers to collect the data from users who do not have a correct understanding of our algorithm, and the data collectors should make it clear that the potential risk in releasing data to our model.

heading: A ALGORITHM FOR THE TRAINING OF SEQPATE
text: The pseudo codes of SeqPATE’s training is shown in Algorithm 1.
Algorithm 1 Training of SeqPATE
Require: Dpri,Dpub: datasets, GPT : a pre-trained GPT model. 1: {fmϕ }Mm=1: M teacher models, fθ: a student model, fΘ: a student model for self pre-training, 2: {ϕm}Mm=1 ← GPT , Θ← GPT # Initialize teachers and the student for self pre-training. 3: GPT generates a pseudo dataset D̃pub based on Dpub. 4: {Dprim }Mm=1 ← Dpri # Divide private dataset into m subsets. 5: for all m in M do 6: Train teacher fmϕ on Dprim 7: end for 8: Teachers {ϕm}Mm=1 conduct inference on D̃pub to get pmϕ (wi | w1:i−1) required in Eq. 2 for all samples. 9:
10: Train fΘ on D̃pub # self pre-training for the student. 11: θ ← Θ # Initialize the student model. 12: 13: while not converge do 14: for all batch of samples {S}batchsize in D̃pub do 15: Student fθ conducts feed-forward on {S}batchsize. 16: for all sample S in the batch {S}batchsize do 17: for all token wi in sample S do 18: pϕ(wi | w1:i−1) = 1M ∑M m=1 p m ϕ (wi | w1:i−1) # Aggregate teachers’ outputs 19: Select only top-k or top-p predicted tokens as student’s output. 20: Obtain LKLi and LNLLi as Eq. 2. # Noise is added into LKLi to protect the privacy. 21: Get L by combining LKLi and LNLLi # Efficient knowledge distillation. 22: end for 23: end for 24: Update ϕ respect to L. 25: end for 26: end while

heading: B DETAILED DEDUCTION OF THE SENSITIVITY IN SENTENCE LEVEL DP
text: We obtain Eq. 3 from Sec. 5.2.
∆ (f) 2 = ∥f(D)− f(D′)∥2 ≤ ∥xj − x′j∥2 = ( |V|∑ v=1 (xjv − x′jv)2 )1/2
(3)
We know (xjv − x′jv)2 is smaller than |xjv − x′jv| since |xjv − x′jv| ∈ (0, 1) for each v. Hence, we have, ( |V|∑
v=1
(xjv − x′jv)2 )1/2 ≤ ( |V|∑
v=1
|xjv − x′jv| )1/2 ≤ ( |V|∑
v=1
|xjv + x′jv| )1/2
We know |a+ b| = a+ b when a, b ∈ (0, 1), so we have,( |V|∑ v=1 |xjv + x′jv| )1/2 = ( |V|∑ v=1 xjv + |V|∑ v=1 x′jv )1/2 = ( 1 + 1 )1/2 ≤ √ 2,
In summary, the upper bound of the sensitivity is,
∆ (f) 2 = ∥f(D)− f(D′)∥2 ≤ ∥xj − x′j∥2 =
√ 2,

heading: C DETAILS ABOUT THE DATASETS
text: The AirDialog dataset (Wei et al., 2018) consists of 402,038 dialogues and each dialogue consists of more than two utterances. We treat each utterance as a sentence in our sentence completion task. We obtain the Europarl v6 dataset from a machine translation benchmark 6 and we only use the monolingual English dataset with 2,015,440 raw sentences.
For the above datasets, we filter the short sentence with less than eight tokens. Then, the first four tokens act as the prefix, and the rest of the tokens acts as the output (ground-truth). We split each datasets into a private set Dpri and a public set Dpub. For the AirDialog dataset, the private set contains 0.95M/5K/50K samples for training/validation/testing and the public set contains 40K/5K for training/validation. For the Europarl v6 dataset, the private set contains 1.72M/10K/50K samples for training/validation/testing and the public set contains 40K/5K for training/validation. The vocabulary size for the two datasets is set to 50K and we replace the tokens out of the vocabulary with a special token.

heading: D DETAILS ABOUT THE EXPERIMENTAL SETTING
text: All the comparing algorithms use the same base model, the GPT-small, which has 12 stacked layers as mentioned in the original paper (Radford et al., 2018). The pre-trained GPT model comes from the official website 7. All the methods are initialized by the pre-trained GPT model. We used the Adam optimization scheme (Kingma & Ba, 2015) and we adjust the initial learning rate for all the comparing methods with a range of 0.01 ∼ 0.00001, which means we conducted a systematic search of the hyper-parameter space among all methods. We set the batch size as 32 for all the comparing baselines. We truncate the sentences with the maximal sentence length of 40. In the top-p strategy, the threshold µ is 0.95. The factor λ balancing the KL loss and NLL loss mentioned in Eq. 2 is 20.

heading: E DETAILS ABOUT THE EVALUATION METRICS
text: To measure the quality of generation, PPL is a widely used metrics in text generation, especially language modeling, which measures the perplexity of generating the next token. B-n (Bleu-n) (Papineni et al., 2002) measures the degree of the n-gram matching between the generated results and the ground-truth text.
To measure the performance of privacy protection (we can also treat it as the privacy leak of the models), we aim to give an intuitive understanding of the protection on text generation scenario (even if the factor ε in DP indicates the strength of privacy protection according to the DP theorem). Hence, we propose a new metric, P-N, indicating how many generated n-grams can be found in the private set Dpri. We define NY as the set of unique n-grams in a generated sentence Y and define NDpri as the set of unique n-grams in the private data Dpri. As shown in Eq. 4, P-N is the ratio of the n-grams that occurs in the two sets over n-grams occurs only in NY weighted by idf, where the idf is the inverse frequency of this n-gram indicating the sensitivity of this n-gram (Rare n-grams are likely to carry sensitive information, such as SSN number and address). P-N ranges from 0 to 1 and lower P-N indicates the more strong privacy protection (less privacy leak from the models).
For the choice of value N, we note that P-N with a very small value of N can hardly reflect the privacy loss since the uni-grams and bi-grams are very easy to be generated even if the model did not meet it from the private dataset Dpri. For example, the N=1 does not make sense because it only reflects the vocabulary overlapping between two datasets. Thus, we choose 3 and 4 as the value of N.
6The description is in www.statmt.org/europarl; the data comes from statmt.org/wmt11/trainingmonolingual.tgz
7github.com/openai/gpt-2
NY = {n-gram ∈ Y} NDpri = {n-gram ∈ Dpri}
P-N =
∑ n∈NY∩NDpri
idfn∑ m∈NY idfm
(4)

heading: F ANALYSES ABOUT THE NUMBER OF TEACHER MODELS
text: Table 4 and Table 5 show the analyses about SeqPATE’s performance with different teacher number on our two datasets.

heading: G THE COMPUTATIONAL COST OF SEQPATE
text: It seems that our model requires huge computational resources and a costly infrastructure to run. But in fact, our model is able to train and inference on a single GPU machine. In this section, we will introduce some simple strategies we used in our implementation and also introduce the total computational cost of our model.
Memory usage and hard-disk space usage. Since our method uses a large number of teachers, the naive implementation of loading all teachers into memory for aggregation is impractical. However, note that our algorithm only needs to access each teacher’s top-k prediction. Therefore, we train teacher models sequentially. Once a teacher model is trained, we obtain its top-k prediction (k=200 in our experiments) on the public training data and save the results (i.e. k probabilities). Then, we discard the teacher model. Finally, SeqPATE only needs teacher supervision on a small number of samples. In our experiments, training on 1∼2k teacher labeled samples is sufficient. Overall, saving teachers’ inference results uses 8∼16G. The memory usage is similar to that of a GPT2 model because we do not load all teacher models into memory and instead run inference sequentially and merge teachers’ predictions offline.
Training time. While we have a large number of teachers, each teacher is trained on only a small fraction of the entire dataset. Thus the time it takes to train all teachers is roughly equal to the time of training a single GPT2 model on the full dataset (of 1∼2M samples in our experiments). In summary, with simple tricks, the teacher training and aggregation steps are not much more expensive than training a GPT2 model. Compared to standard NLG model training, our algorithm does not require special hardware or distributed learning.
H ADDITIONAL EXPERIMENTS ON LARGER ε AND LARGER δ
We adopted stronger privacy protection at ε=2 and δ=1e-9 in Table 1, which results in a quite large utility gap between SeqPATE and the non-private training method (Pri-GPT) on the AirDialog dataset. Actually, our model performance can be increased a lot if we conduct weaker privacy protection (i.e. using a larger ε and a larger δ). In Table 6, we show the experimental results with ε=3 and δ=1e-6 on AirDialog dataset.
I HANDLE LARGE ε: USING FEWER TEACHERS
As shown in Fig. 2, when we use large ε, our SeqPATE cannot obtain better performance than DP-SGD. As discussed in Sec. 6.2, the reason is that the amount of training samples for each teacher model is quite small in our model (especially, when the teacher number is large). We note that this can be improved by using fewer teachers. As shown in Table 7, we conduct experiments on AirDialog dataset with fewer (i.e. 100) teachers and larger ε (i.e. 50 and 500), where SeqPATE outperforms DP-SGD. For DP-SGD, we choose Pub-GPT+ DP-SGD instead of Pub-GPT+DP-SGD+D̃pub since Pub-GPT+ DP-SGD obtains higher performance when ε is large.

heading: J EVALUATING PRIVACY LEAK IN ANOTHER METRIC (EXPOSURE)
text: We have evaluated the performance of privacy protection in P-3 and P-4. We also conduct experiments on another metric, exposure, to evaluate the privacy leak. The exposure is proposed by (Carlini et al., 2019). To calculate the score, we use three kinds of patterns “is <word> | are <word> | <digital>”. The repetitions r are 100 for all patterns, and the lengths of sampled words or digits are three. The candidate words are randomly sampled from the whole vocabulary and the digits are randomly sampled from {0, 1, ..., 9}. We calculate the average exposure score over the three kinds of patterns. We follow the implementation of the exposure score from 8.
Table 8 shows the experimental results, where the results are consistent with the results on P-3 and P-4 mentioned in Table 1. For example, in both metrics, the privacy leak in AirDialog is more serious than that in Europarl v6 and the gap between Pri-GPT and SeqPATE on AirDialog is larger than that on Europarl v6.
8github.com/tensorflow/privacy/tree/master/tensorflow privacy/privacy

heading: K ADDITIONAL EXPERIMENTS WHEN THE DATASET IS SMALLER
text: To verify our performance on smaller datasets, we produce a small dataset by randomly sampling 50k samples from the AirDialog dataset. The experimental results are shown in Table 9. In such a small dataset, our method still outperforms the DP-SGD with ε = 2 and δ = 1e-9.
.
L THE CONTRIBUTION OF THE PSEUDO PUBLIC DATASET D̃pub
We conducted experiments to verify the contribution of pseudo dataset D̃pub to our task on AirDialog dataset. The results in Table 10 shows that using D̃pub can prompt the performance a lot, where the promotion can be found in both SeqPATE and DP-SGD methods.

heading: M THE ILLUSTRATION OF A RUNNING EXAMPLE.
text: Here, we will use an example to show our training processing. In this example, the prefix from the public dataset Dpub is “I want to book”. We feed the prefix to pre-trained GPT2 to generate a pseudo sentence “I want to book a flight from Tokyo to Hawaii.”. The pseudo sentence will serve as an example in the pseudo public dataset D̃pub. We feed the pseudo sentence to the teacher models to conduct the teacher inference and also feed it to the student model to conduct the feed-forward of the student training. Teacher models output the probability distributions on all words (10 words, in total) of the sentence. Then, we aggregate all teachers’ probability distributions and add the calibrated noise on the aggregated distributions. The student model also generates the corresponding probability distributions on those words and we conduct the efficient knowledge distillation and top-k or top-p selection over the student’s probability distributions. For example, if the student model can do well on the words (“I”, “want”, “book”, “flight”, and “Tokyo”), the student will only query the teachers’ output distributions on the rest of words (“to”, “from”, “to”, and “Hawaii”) through the KL loss mentioned in 2. Besides, the student is always supervised by the NLL loss on the whole pseudo sentence (“I want to book a flight from Tokyo to Hawaii.”). Finally, the student model conducts back-propagation according to the above losses.

Review summaries:
This paper tries to adapt the PATE (Private Aggregation of Teacher Ensembles) framework for DP training of machine learning models to the setting of text generation. There are some significant challenges in adapting PATE to this framework.  PATE as originally proposed is designed to work for classification tasks with a small number of labels. Text generation or next word prediction has too many labels and a direct application of PATE doesn't work. This paper solves this issue by aggregating only top-k predictions of each teacher where the top-k is computed using the prediction of the student on public data and so doesn't leak extra privacy. The paper also crucially uses public data and large pretrained models like GPT2 to further improve the performance of DP learning using PATE on private data.  They claim that their approach improves upon DPSGD/Noisy SGD (which is the standard DP algorithm for deep learning) significantly on some standard benchmarks.

This paper proposes a variant of PATE (from ICLR 2018), a method intended for standard supervised learning tasks. The present work instead focuses on natural language generation, an inherently sequential task, which introduces new challenges. Relative to PATE (and assuming knowledge of it), some differences in the method involve: extending the public data sentences into "pseudo sentences" using GPT-2, simultaneously performing training on all prefixes of the pseudo sentences, averaging the teacher model output distributions rather than aggregating their max score (i.e., their prediction), and using the student model to reduce the support size for said output distributions. Experimental evaluation is provided for two datasets, AirDialog and Europarl_v6. Perplexity and BLEU scores improve upon those which do not use the private data, and those which use previous methods with the private data. 

This paper proposes to protect the privacy of text generation models, which may leak sensitive information of the training data. Specifically, the authors propose SeqPATE, which applies the PATE framework to large-scale language models such as GPT. By reducing the output space and aggregating the supervision from teacher models, SeqPATE can help reduce the privacy cost. Empirical evaluation on two private text corpus shows that SeqPATE achieves a good trade-off between utility and privacy. 

This paper proposes SeqPATE that adapts PATE to text generation while satisfying differential privacy. To overcome the challenge of obtaining sequence-level supervision for text generation, it first generates pseudo inputs by completing the prefix using GPT-2 (a pre-trained language model) and thus reduces the problem to the next word prediction. Then it applies the PATE framework to privately train a student model with several algorithmic innovations, including (1) aggregating teachers' models by averaging their output distributions; (2) reducing output space by top-k/top-p selection; (3) efficient knowledge distillation by only querying the teachers' models when the student model performs poorly. (4) using both public labels and teachers' aggregation to supervise the learning. The paper gives privacy analysis and also shows it can offer privacy guarantees on user-level and secret n-grams. The paper also provides extensive experimental results and shows that it outperforms other DP learning algorithms when the \eps is small (<5). The experiments demonstrate the practicality of the algorithm.