What Neural Networks Memorize and Why: Discovering the Long Tail via Influence Estimation

Abstract

Deep learning algorithms are well-known to have a propensity for fitting the training data very well and often fit even outliers and mislabeled data points. Such fitting requires memorization of training data labels, a phenomenon that has attracted significant research interest but has not been given a compelling explanation so far. A recent work of Feldman (2019) proposes a theoretical explanation for this phenomenon based on a combination of two insights. First, natural image and data distributions are (informally) known to be long-tailed, that is have a significant fraction of rare and atypical examples. Second, in a simple theoretical model such memorization is necessary for achieving close-to-optimal generalization error when the data distribution is long-tailed. However, no direct empirical evidence for this explanation or even an approach for obtaining such evidence were given. In this work we design experiments to test the key ideas in this theory. The experiments require estimation of the influence of each training example on the accuracy at each test example as well as memorization values of training examples. Estimating these quantities directly is computationally prohibitive but we show that closely-related subsampled influence and memorization values can be estimated much more efficiently. Our experiments demonstrate the significant benefits of memorization for generalization on several standard benchmarks. They also provide quantitative and visually compelling evidence for the theory put forth in (Feldman, 2019).

References in corpus (8)

• Understanding Black-box Predictions via Influence Functions
• Overfitting or perfect fitting? Risk bounds for classification and regression rules that interpolate
• The Devil is in the Tails: Fine-grained Classification in the Wild
• Uniform convergence may be unable to explain generalization in deep learning
• An Empirical Study of Example Forgetting during Deep Neural Network Learning
• Representer Point Selection for Explaining Deep Neural Networks
• Does data interpolation contradict statistical optimality?
• Distribution Density, Tails, and Outliers in Machine Learning: Metrics and Applications

Cited by in corpus (11)

• What Do Compressed Deep Neural Networks Forget?
• Training Data Influence Analysis and Estimation: A Survey
• When is Memorization of Irrelevant Training Data Necessary for High-Accuracy Learning?
• Recommendation Unlearning via Influence Function
• Deep Learning on a Data Diet: Finding Important Examples Early in Training
• Toward Better Generalization Bounds with Locally Elastic Stability
• Future Lens: Anticipating Subsequent Tokens from a Single Hidden State
• The Thousand Faces of Explainable AI Along the Machine Learning Life Cycle: Industrial Reality and Current State of Research
• Evolution-aware VAriance (EVA) Coreset Selection for Medical Image Classification
• Pointer Value Retrieval: A new benchmark for understanding the limits of neural network generalization
• Towards the Memorization Effect of Neural Networks in Adversarial Training