A recent study by Feldman (2020) proposed a long-tail theory to explain the memorization behavior of deep learning models. However, memorization has not been empirically verified in the context of NLP, a gap addressed by this work. In this paper, we use three different NLP tasks to check if the long-tail theory holds. Our experiments demonstrate that top-ranked memorized training instances are likely atypical, and removing the top-memorized training instances leads to a more serious drop in test accuracy compared with removing training instances randomly. Furthermore, we develop an attribution method to better understand why a training instance is memorized. We empirically show that our memorization attribution method is faithful and share our interesting finding that the top-memorized parts of a training instance tend to be features negatively correlated with the class label. In recent years, there has been an increasing amount of interest in the machine learning community to understand the memorization behaviour of deep neural network models. Studies have shown that deep learning models often have sufficient capacities to memorize training examples (Zhang et al., 2017; Arpit et al., 2017). A number of recent studies tried to understand how memorization helps generalization (Chatterjee, 2018; Feldman, 2020; Montanari and Zhong, 2020; Khandelwal et al., 2020, 2021) In NLP, memorization of training examples by deep learning models is also often observed (Li and Wisniewski, 2021; Lewis et al., 2021; Raunak et al., 2021), and existing studies usually see memorization as something that hinders generalization. For example, Elangovan et al. (2021) tried to measure the amount of data leakage in NLP datasets in order to assess a model's ability to memorize vs. its ability to generalize. However, recently Feldman (2020) proposed a long-tail theory, which states that memorization is necessary for generalization if the data follows a long-tail distribution. This theory was later empirically validated by Feldman and Zhang (2020), but their validation was done in only the computer vision domain. It is therefore interesting and useful for us to study whether the long-tail theory also holds in NLP; such validation would help us better understand the utility of memorization in the context of NLP. The long-tail theory states that if the training data form a long-tail distribution, where there are many small sub-populations that are atypical instances, and if these small sub-populations are also present in the test data, then memorizing these atypical instances helps the model generalize to the test data. In order to validate this long-tail theory in the context of NLP, we follow the experiments and analyses on image classification done by Feldman and Zhang (2020). Specifically, we aim to answer the following questions in this paper: (1) On a few typical NLP tasks, are the training instances memorized by deep learning models indeed atypical instances? (2) Does memorizing these training instances lead to lower generalization error on the test instances? In addition, observing that it is not always straightforward to understand why a training instance is being memorized, we study the following novel research question: (3) Can we provide some explanation about why a training instances is memorized? To be more specific, can we attribute the memorization score of a training instance to its individual tokens such that we can quantify which tokens require the most memorization by the model? To answer these research questions, we first adopt self-influence (Koh and Liang, 2017) as our memorization scoring function. Compared with the estimator proposed by Feldman and Zhang (2020), our self-influence function is also theoretically mo-6265 tivated but has the advantage that it is easy for us to derive a memorization attribution method for the third research question above. We present the self-influence function in Section 2.1, and in Section 2.2, we present our novel memorization attribution method. We conduct experiments on three NLP tasks: sentiment classification, natural language inference (NLI) and text classification. Our experiments and analyses demonstrate that the training instances with the highest memorization scores tend to be atypical , at least on sentiment classification and NLI. On all three tasks, we find that removing the top-memorized training instances results in significantly dropped test performance, and the drop is markedly higher compared with removing a random subset of training instances. We also evaluate our memorization attribution method and find that our method can indeed identify input tokens that require the most memorization. Finally, we apply our memorization attribution method to sentiment classification and to an image classification dataset, and we share the interesting finding that the highly-memorized input features tend to be those that are negatively correlated with the class labels. Our code and data are available at https://github.com/ xszheng2020/memorization . To validate the long-tail theory in the context NLP, let us first review the main claims of the theory. First, the long-tail theory hypothesizes that training instances with the same class label has a long-tail distribution, with instances at the tail end being those atypical instances that need to be memorized. To verify this assumption, we first identify those training instances that are memorized by a trained deep learning model and then check if they are indeed atypical. Specifically, we follow Feldman and Zhang (2020) and adopt self-influence to measure memorization, but we use the influence function proposed by Koh and Liang (2017) to define self-influence. Second, the long tail theory states that memorization of the atypical training instances leads to lower generalization error, because the atypical training instances belong to subpopulations that also have presence in the test data. To verify this statement, we check whether removing the memorized training instances would lead to more significant performance drop on the test data than removing a random sample of training instances. It is worth noting that the approach outlined above follows the experiments conducted by Feldman and Zhang (2020) to validate the long tail theory on image classification. Furthermore, we want to pinpoint which parts of a memorized instance are most critical for memorization. In other words, since each training instance is assigned a memorization score, can we attribute the memorization score to different parts of the input of this instance? This presumably can help us better understand which parts of the input need to be memorized the most. We follow the idea from Integrated Gradients (IG) (Sundarara-jan et al., 2017) and derive a formula to compute memorization attribution. The high level idea of Feldman (2020) to define memorization is that memorization measures how the prediction on a training instance z = ( x, y ) (where x is the observation and y is the label) changes when z is removed from the training data. This notion is closely related to the influence function defined by Koh and Liang (2017), which measures how much the loss at a test point z test is influenced by a slight upweighting of a training instance z in the training loss function. While influence function is generally used to measure the influence of a training instance on a test instance, if we use it to measure the influence of a training instance on itself , i.e., to measure self-influence, then this self-influence corresponds to the general notion of memorization defined by Feldman (2020). Adopting the influence function defined by Koh and Liang (2017), we define the memorization score for a training instance z as follows: M remove ( z ) def =  dP ( y | x ;   ,  z ) d (cid:12)(cid:12)(cid:12)(cid:12)  =0 , (1) where   ,  z represents the parameters of the model trained with the instance z down-weighted by  , P ( y | x ;  ) is the conditional probability using  . Thus M remove ( z ) is the amount of change of P ( y | x ;  ) when the instance z is down-weighted by a small amount  . After several steps of derivation (details to be given in Appendix A), the computation of Eqn 1 follows the following formula: M remove ( z ) =   P ( y | x ;   )  H  1     L ( z,   ) , (2) 6266 where   is the parameters of the model trained with all instances, L is the loss function (cross entropy in our implementation) and H   = 1 n (cid:80) ni =1  2  L ( z i ,   ) , where ( z 1 , z 2 , . . . , z n ) are the training instances. In order to better understand why an instance is memorized, we propose a fine-grained notion of memorization at feature level instead of instance level, i.e., to attribute the memorization score of an instance to its individual features. Our proposed memorization attribution method is general and can be applied to any input representation. For NLP tasks, this means we attribute the memorization score defined above to each token of the input sequence. For images, this would be to attribute the memorization scores to pixels. For this memorization attribution, we borrow the idea from Integrated Gradients (IG) (Sundararajan et al., 2017), which is a gradient-based attribution method for understanding which parts of a test instance are more responsible for its prediction. In particular, the IG method requires an uninformative baseline input x  as a reference point. Similarly, here we also assume a baseline x  . This baseline is supposedly an instance that does not have any influence on any test instance, and in our implementation, we use an sequence of the same length as x but consisting of only the [MASK] tokens. We first consider the influence of replacing z = ( x, y ) with the baseline z  = ( x  , y ) (which is similar to perturbation-based influence from (Koh and Liang, 2017)): M replace ( z ) def =  dP ( y | x ;   ,z  ,  z ) d (cid:12)(cid:12) (cid:12)(cid:12)  =0 , (3) where   ,z  ,  z represents the parameters resulting from moving  mass from z to z  , i.e., adding z  to the training data and giving it a weight of  in the loss function while reducing the weight of the original z by  . Thus M replace ( z ) is the amount of change of P ( y | x ;  ) when a small amount  of z is replaced by the uninformative z  . It is worth pointing out that we can regard M replace ( z ) as an alternative way of measuring the amount of memorization of z , similar to how perturbation-based influence is an alternative way of measuring influence in (Koh and Liang, 2017). M replace ( z ) =  s   L ( z,   )    L ( z ,   ) , (4) where s = H  1     P ( y | x ;   ) . (For more details, please refer to Appendix B.) The advantage of using this alternative measure of memorization is that M replace ( z ) can be decomposed into a linear combination of scores, each corresponding to a single token in the input sequence. For NLP applications, the input x usually corresponds to an embedding matrix X  RN  d (where N is the number of tokens and d is the embedding dimensions). We can show that M replace ( z ) =  N (cid:88) t =1 d (cid:88) l =1 r t,l ( X t,l  X  t,l ) , (5) where r = (cid:104) (cid:82) 1  =0 dg ( X  +  ( X  X  )) dx d (cid:105) s and g ( X ) =   L (( X , y ) ,   ) , which can be efficiently computed by the hessian-vector product (Pearlmut-ter, 1994). For more details, please refer to Appendix B. The memorization attribution of the t -th token is thus given by  (cid:80) dl =1 r t,l  ( X t,l  X  t,l ) . With the memorization score defined in Eqn 2 and the memorization attribution score defined in Eqn 5, we now conduct experiments to answer the three research questions raised in Section 1. datasets: SST-2 (Socher et al., 2013): This is a dataset for sentence-level binary (positive vs. negative) sentiment classification. It consists of 6,920 training instances, 872 development instances and 1,821 test instances. SNLI (MacCartney and Manning, 2008): This is a dataset for natural language inference, which aims to predict the entailment relation (contradiction, neutral or entailment) between a premise and a hypothesis. We combine the contradiction and neutral classes into a single non-entailment class, and randomly sample 10k training instances, 6,658 development instances and 6,736 test instances. into 10 topic-based classes. We randomly sample 10k training instances, 10k development instances and 10k test examples. In addition, we also use CIFAR-10 (Krizhevsky et al., 2009), which is a dataset for 10-class image classification. We randomly sample 10k training instances, 5k development instances and 10k test instances. For some tasks, we down-sample the training set because influence function is known to be expensive to compute. For all NLP tasks, we adopt the pre-trained Distill-BERT model (Sanh et al., 2019) that consists of 6 transformer layers, where each layer consists of 12 attention heads. We use the final hidden state of the [CLS] token for classification. 1 For CIFAR-10, we extract visual grid features using a pre-trained ResNet50 (He et al., 2016) first and then train a MLP classifier on top of that. We use the SGD optimizer, setting the learning rate, momentum and batch size to 0.01, 0.9 and 32, respectively. We tune other hyper-parameters on the development set manually. Although influence function is model-dependent and therefore models trained with different random seeds may produce different memorization scores for the same training instance, we found that in practice, ranking training instances based on memorization scores obtained from models trained by different random seeds produces similar rankings across different models. Thus, we only consider a single model checkpoint for computing our self-influence based memorization scores in the following experiments. (See Appendix C for the exact description.) For memorization attribution, the number of Riemann Sum steps is set to be 50. 3.2 Checking Memorized Instances Group Negative Positive Top-10% 35.80 74.00 All 23.24 86.39 Bottom-10% 14.92 94.52 Table 1: The average percentage of positive phrases over (1) the top-10% memorized positive/negative instances, (2) all positive/negative instances, and (3) the bottom-10% memorized positive/negative instances. In the first set of experiments, we use our self-influence-based memorization scoring function as defined in Eqn. 1 to rank the training instances. Our goal is to check if the top-memorized instances are indeed atypical instances. However, it is difficult to measure the typicality of instances. We note that in the prior work (Feldman and Zhang, 2020) where the authors tried to validate the longtail theory on computer vision datasets, there was not any quantitative experiment, and the authors relied only on qualitative analysis (i.e., manual inspection of the top-ranked instances) to show that memorized instances tend to be atypical. In our experiments, we perform two kinds of checking: (1) First, we adopt qualitative evaluation as Feldman and Zhang (2020) did on both SST-2 and SNLI. For Yahoo! Answers, however, because each instance contains a long document, it is not easy for humans to judge whether or not an instance is atypical. (2) Second, we define quantitative measures of typicality on sentiment analysis because annotations are available on this dataset and these annotations allow us to define some form of typicality. For SST-2, we judge whether or not the top-ranked memorized instances are atypical in two ways: (1) The first is based on a heuristic metric. We check the percentage of positive phrases in an instance, where phrase-level sentiment polarity labels are from the annotations provided by SST-2. Intuitively, a typical positive sentence should have a relatively high percentage of positive phrases and a typical negative sentence should have a relatively low percentage of positive phrases. We collect such statistics from SST-2 based on the phrase-level annotations and found that this is to a large extent true. For example, more than 75% of positive sentences have at least 78.31% of positive phrases and more than 75% of negative sentences have at most 35.73% of positive phrases. (See Appendix D for details.) Therefore, by checking the percentage of positive phrases inside a positive or negative instance, we can in a way judge whether that instance is typical or atypical. When calculating the percentage of positive phrases inside a sentence, we apply Laplace smoothing. (2) We also manually inspect the top-ranked and bottom-ranked training instances based on the memorization scores and use our human knowledge to judge whether the top-ranked ones are atypical while the bottom-ranked ones are typical. Table 1 shows the average percentage of positive phrases in the top-10% of the memorized positive (or negative) training instances and the bottom-10% of the memorized positive (or negative) training instances. As a reference point, we also show the average percentage over all positive (or negative) training instances. We can see that the top-10% memorized instances indeed are atypical. Specifically, those negative sentences with high memorization scores have a high percentage of positive phrases on average (35.80%), clearly higher than the average percentage of positive phrases of all negative instances (23.24%). This makes the top-memorized negative instances very different from typical negative instances. On the other hand, the bottom-10% negative instances (i.e., those instances that are not memorized) have clearly much lower percentage of positive phrases (14.92%), which is what we expect for typical negative instances. Similar observations can be made with the positive training instances. Overall, the results in Table 1 suggest that indeed the top-memorized training instances in SST-2 are atypical. Table 2. We can see that the top-ranked memorized instances tend to express their overall opinions in an indirect way. These sentences often contain a contrast between positive and negative opinions. We therefore believe that they are atypical for sentiment classification. On the other hand, the bottom-ranked instances, i.e., those with 0 memorization scores, tend to directly expression their opinions with strong opinion phrases, and we believe these represent common instances. For the task of natural language inference, it is hard to come up with a heuristic metric like the one used for sentiment classification. We therefore focus on manual inspection of the top-ranked and bottom-ranked training instances. In Table 3 we show the top-3 and bottom-3 memorized training instances from SNLI. We can see from the table that in the top-ranked memorized non-entailment instances, the hypothesis tends to be much shorter than the premise and there tends to be no obvious contradiction. In contrast, the bottom-ranked non-entailment instances tend to be contradictions where there are obvious contradictory words/phrases in the premise and the hypothesis, such as bicycle vs. motor-cycle, player vs. cat and posing for a picture vs. eating his lunch. We hypothesize that the top-ranked non-entailment instances are atypical because they do not have obvious signals of non-entailment such as the contradictory word pairs we see in the bottom-ranked non-entailment instances. For entailment cases, we find that the top-ranked instances often contain word pairs that are synonyms but are rare in the training data. For example, we find that the word pair keyboard and piano appears only two times in the training data, which implies that this instance is an atypical example. Similarly, we find that the word/phrase pair iPod and mp3 player appear only once in the training data. On the other hand, the bottom-ranked entailment instances tend to be those where the hypothesis contains less information than the premise, which may be a common type of entailment instances. In the second set of experiments, we check whether memorizing those training instances with the highest memorization scores leads to better performance on the unseen test data. To do so, we compare the performance of the model on test data when top-ranked memorized training instances are removed during training versus the performance when the same number of randomly selected training instances are removed. If memorization is beneficial for the test data, then we would expect to see larger performance drop when top-ranked memorized training instances are removed than when random training instances are removed. Therefore, the amount of performance drop represents the marginal effect of the memorized instances on the test accuracy. We show the test accuracy in Figure 1 when X % of the training instances are removed, where we set X to a few different values. We re-train the model 5 times and show the average test accuracy as well as the standard deviation. We also show the lowest absolute memorization score of the topX % of training instances in Figure 1. For reference, here we also use CIFAR-10 to verify that our self-influence estimation using the influence function works similarly to the influence estimator used by Feldman and Zhang (2020). We can observe the following from Figure 1: (1) On CIFAR-10 (Figure 1(d)), we see that clearly the test accuracy drops more significantly when top-ranked memorized training instances instead of random training instances are removed. Because Feldman and Zhang (2020) reported the same observation, this suggests that our memorization score based on the influence function proposed by Koh and Liang (2017) works similarly to the memorization estimator used by Feldman and Zhang (2020). This verifies the reliability of our memorization scoring function. (2) On SST-2, Yahoo! Answers and SNLI, we can see that consistently when the same percentage of training instances are removed, removing top-ranked memorized instances has a clearly bigger impact on the test accuracy compared with removing random instances. For example, on SST-2, the marginal utility of the top-30% memorized training example is about 1.44 percentage points (vs. 0.70 percentage points for random subset of 30% of training examples). This verifies that on SST-2, Yahoo! Answers and SNLI, memorizing those training instances could help improve the performance on the test data. In this section, we evaluate whether our memorization attribution method is faithful, i.e., whether it indeed picks up tokens that have higher self-influence. Intuitively, if the memorization attribution method detects those memorized tokens in a training instance faithfully, then removing these tokens in that instance should result in a lower influence I of the perturbed instance on its original form (details to be given in Appendix A). We therefore define a metric called Reduction Rate as follows: 1 |Z| (cid:88) z Z I ( z, z )  I ( z \ attr , z ) I ( z, z ) , (6) where Z is the set of top memorized training instances and z \ attr is the perturbed input where the topk % memorized tokens are replace by the baseline token [MASK] . We can see that this Reduction Rate measures how much self-influence has been reduced after the top-memorized tokens are replaced with [MASK] . 2 Figure 2 demonstrates the significant effect of the removal of the top-memorized tokens from the top-memorized training instances. One could ask whether this effect is solely due to the input perturbation. To answer this question we include in the 2 We consider only top10% memorized instances due to computation constraints. comparison the reduction rate of random attribution, i.e., we randomly remove some tokens from the training instances. We can see that removing tokens picked up by our memorization attribution method results in a much larger Reduction Rate until almost 90% of the tokens are removed. This result suggests that our memorization attribution method can indeed identify those tokens in a training instance that have high self-influence on that instance. To better understand why certain training instances are memorized, we apply our memorization attribution method to SST-2, Yahoo! Answers and CIFAR-10. We do not discuss our memorization attribution method applied to the NLI task because we find that it is not easy to interpret the results. In some other studies (e.g., Han et al. (2020)), people have also reported different behaviours of NLI from tasks relying on shallow features such as sentiment classification and topic-based text classification. CIFAR-10, in most cases our memorization attributions are easy to be interpreted by humans. In particular, without any cherry-picking, we select those instances with the highest memorization scores to present. We find that interestingly, for both SST-2 and CIFAR-10, the trained deep learning model tends to memorize those parts of an instance that are negatively correlated with the class label of that instance, as shown in Table 4 and Figure 3. 3 On SST-2, for example, the model needs to memorize positive phrases such as tremendous promise and intriguing and alluring that show up in an overall negative instance. On CIFAR-10, we observe that for images that are easily mis-classified, the model memorizes those pixels that are associated with the wrong class label, or in other words, pixels that are negatively correlated with the correct class label. For example, the cat image shown in Figure 3 looks like a frog. The model memorizes those pixels (shown in red) around the tummy of the cat 3 For Yahoo! Answers, because each instance is long, due to the space limit, we show the memorization attributions in the Appendix E. 6271 Content Label starts out with tremendous promise introducing an intriguing and alluring premise only to fall prey to a boatload of screenwriting cliches that sink it faster than a leaky freighter Neg mr wollter and ms seldhal give strong and convincing performances but neither reaches into the deepest recesses of the character to unearth the quaking essence of passion grief and fear Neg this is a monumental achievement in practically every facet of inept filmmaking joyless idiotic annoying heavy handed visually atrocious and often downright creepy Neg the director mark pellington does a terrific job conjuring up a sinister menacing atmosphere though unfortunately all the story gives us is flashing red lights a rattling noise and a bump on the head Pos this is a fascinating film because there is no clear cut hero and no all out villain Pos the film is reasonably entertaining though it begins to drag two thirds through when the melodramatic aspects start to overtake the comedy Pos Table 4: The top-3 memorized training instances for each class from SST-2. because those pixels make the image look like a frog image. Similarly, in the dog image, which looks like a horse, the memorized pixels (shown in red) are around the body of the dog, and these pixels make the image look like a horse image. On the other hand, the dog's head in this image, which is a typical dog's head, has negative memorization attribution scores, which means it does not need to be memorized. Given the interesting results above, we believe that model developers can gain insights about what a model finds hard to learn from other training instances (and thus has to memorize), and model developers can subsequently take actions like upweighting memorized instances or collecting similar data to improve the performance on certain subpopulations if desired. The long-tail theory: The long-tail theory proposed by Feldman (2020) is relatively new and has not been systematically validated in NLP. Our work is the first to empirically check the validity of this theory on NLP tasks. Raunak et al. (2021) used the long-tail theory to explain hallucinations under source perturbations in Neural Machine Translation. They assume the theory holds in NMT rather than validating the theory itself as we do. Kong and Chaudhuri (2021) investigated the memorization phenomenon for Variational Auto-Encoder also via self-influence. Memorization vs. generalization: It is wellknown that deep learning models possess strong capabilities to memorize training instances (Zhang et al., 2017; Arpit et al., 2017). In the context of NLP, Li and Wisniewski (2021) showed that BERT is more likely to memorize shallow patterns from the training data rather than uncover abstract properties. Some recent work has tried to combine interpolation methods with deep learning methods to generalize via memorization (Khandel-wal et al., 2020, 2021). However, previous work using interpolation methods did not explain why memorization is necessary in the first place. Our work follows the long-tail theory that views memorization as beneficial to generalization when the data follows a certain type of long-tail distribution. There has also been some work studying forget-ting, which is related to memorization (Toneva et al., 2018; Yaghoobzadeh et al., 2021). However, in this paper we do not study this forgetting phenomenon. Influence functions: Influence functions have been studied for large-scale deep neural networks by Koh and Liang (2017) and gained much attention in recent years. In the context of NLP, Han et al. (2020) explored the usage of influence functions to explain model predictions and unveil data artifacts. Meng et al. (2020) proposed a combination of gradient-based methods and influence functions to examine training history and test stimuli simultaneously. Our work, however, adopts influence function as a tool to measure memorization. In this paper, we empirically examine a recently proposed long-tail theory in the context of NLP. We use sentiment classification, natural language inference and text classification to check the validity of the long-tail theory in NLP. We also propose a memorization attribution method to reveal which parts of an instance are being memorized. There are two major takeaway messages: (1) Our experiments empirically validated the long-tail theory on the three NLP datasets, showing that memorization is important for generalization, offers an alternative view and helps NLP researchers to see the value of memorization. (2) Our attribution method can be a tool to help model developers better understand the memorization behaviours of a model and possibly further improve the model. Our work empirically validated the long-tail theory in the context of NLP, offering an alternative view to the relationship between memorization and generalization. This will help NLP researchers see the value of memorization. However, previous work showed that neural networks can be vulnerable to privacy attacks such as membership inference attacks because these models are able to memorize training instances, and sometimes sensitive private information may be contained in the training instances (Shokri et al., 2017; Zhang et al., 2017; Feldman and Zhang, 2020). Thus, there is a tradeoff between the accuracy of a model and the privacy of the data. In other words, although memorization can help reduce generalization error (as we showed in this paper), it also increases the vulnerability of the system to privacy attacks, which raises ethical concerns. inverting the hessian matrices. To reduce the computation costs, i.e., power consumption, we may adopt other influence estimators like TracIn (Pruthi et al., 2020), which is hessian-free and thus faster. This research is supported by the Singapore Ministry of Education (MOE) Academic Research Fund (AcRF) Tier 1 grant.
abstain result method objective objective result abstain abstain other abstain abstain abstain method abstain method objective abstain objective abstain abstain abstain objective method objective result result method other method abstain method method abstain method abstain method method method method abstain abstain method method abstain method abstain abstain method abstain abstain abstain method method other abstain method abstain abstain abstain abstain other abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain result abstain abstain abstain abstain abstain other other other other other abstain abstain abstain abstain abstain abstain abstain abstain result abstain result result result result result result abstain abstain result abstain abstain abstain abstain abstain result abstain abstain abstain abstain result result abstain result abstain abstain abstain result abstain result abstain result abstain abstain abstain result other objective other method other other other other other method other method other other other method objective method objective result result abstain abstain abstain abstain abstain abstain method other