PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Vitaly Feldman, Chiyuan Zhang

arXiv:2008.03703v1cs.LGstat.ML

TL;DR

The paper asks why deep networks memorize labels, including apparently useless outliers and mislabeled examples, and whether Feldman’s long tail theory explains this behavior. It introduces computationally feasible subsampled memorization and influence estimators to test the theory empirically. Across standard benchmarks, memorization improves accuracy on atypical, visually similar examples, providing quantitative and visual support for the theory.

  • Problem

    Classical generalization theory does not explain why deep networks memorize outliers and mislabeled examples, while Feldman’s long tail explanation lacked direct empirical validation.

  • Method

    The paper develops subsampled estimators of training-example memorization and train-to-test influence, replacing computationally prohibitive direct estimation with random-subset calculations.

  • Results

    Memorized examples have significant marginal utility across benchmarks and often improve accuracy on visually similar, atypical test examples, supporting the long tail theory.

  • Takeaways & Limitations

    Memorization appears important for accuracy on long-tailed data, particularly for under-represented subpopulations, while most memorization occurs in learned deep representations.

  • Takeaways & Limitations

    Accurate influence and memorization estimation requires training thousands of models and therefore significant computational resources.

Abstract

from arXiv · show

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).

1 Introduction

The paper investigates why deep networks memorize outliers and mislabeled examples despite classical generalization theory treating memorization as harmful. It empirically tests Feldman’s long tail theory using subsampled memorization and influence estimators, finding that memorization can improve accuracy on atypical, visually similar test examples.

  • Motivation: Deep networks commonly fit training labels, including obvious outliers and mislabeled examples, but classical theory does not explain this behavior.Classical analyses balance empirical error against complexity or stability, although fitting such examples does not improve generalization error.
  • Long tail theory: Feldman’s long tail theory proposes that memorization is necessary for near-optimal generalization when rare and atypical subpopulations form a substantial part of the distribution.Useful long-tail examples may be statistically indistinguishable from useless outliers and mislabeled examples, making some useless memorization unavoidable.
  • Empirical approach: The paper addresses the lack of direct empirical tests by estimating training-example memorization and each training example’s influence on test-example accuracy.It develops subsampled estimators because direct estimation would require computationally prohibitive numbers of training runs.
  • Results: Aside from MNIST, a significant fraction of examples have large memorization estimates, and memorized examples provide greater marginal utility than equally sized random subsets.On ImageNet, approximately 32% of examples have memorization estimates at least 0.3, with marginal utility approximately 3.4% versus approximately 2.6% for a random 32% subset.

2 Estimation and Selection Procedures

The section defines subsampled memorization and influence estimators that replace prohibitively many leave-one-out training runs with training on random subsets. It also describes threshold-based pair selection and the estimator settings used in experiments.

  • Estimator definitions: Memorization is the influence of a training example on the model’s accuracy for that same example.It is defined as self-influence: mem(A, S, i) = infl(A, S, i, (x_i, y_i)).
  • Estimator definitions: Subsampled influence measures an example’s expected effect relative to a random subset of m training examples rather than the full dataset.The subset is formed by sampling m − 1 examples excluding i, then adding i, making the resulting dataset uniform over size-m subsets containing i.
  • Efficient estimation: O(1/σ2) models estimate subsampled influence with standard deviation σ, avoiding the O(n/σ2) models required for direct influence estimation.The direct approach would require training separately for every example, while the subsampled estimator uses repeated random-subset training.
  • Estimator computation: The algorithm samples t random subsets of size m, trains one model per subset, and compares predictions when each training example is included versus excluded.It returns memorization estimates for all training examples and influence estimates for all training–test pairs.
  • Estimator computation: The experiments use m = 0.7 · n, with t = 2000 trials for ImageNet and t = 4000 for MNIST/CIFAR-100.The subset size balances estimator closeness to full influence against obtaining enough subsets that exclude each example.
  • Pair selection: Selected pairs satisfy memorization and influence thresholds and have matching labels, while thresholding can introduce selection bias near the cutoff.The authors use θ_mem = 0.25 and θ_infl = 0.15; repeated CIFAR-100 selection produced a Jaccard similarity of at least 0.7.

3 Empirical Results

Across MNIST, CIFAR-100, and ImageNet, memorized examples have substantial marginal utility, and high-influence training examples often account for accuracy on individual test examples. Estimates are interpretable and remain consistent across architectures, while last-layer-only estimation fails to recover full-network memorization and influence.

  • Memorization and marginal utility: Estimated memorization values align with intuitive examples: typical images score near 0, while atypical, ambiguous, or mislabeled examples score near 1.Examples were visualized across ImageNet, CIFAR-100, and MNIST.
  • Memorization and marginal utility: Removing high-memorization examples reduces test accuracy more than removing the same number of randomly selected examples.This comparison controls for the reduction in training-set size caused by removal.
  • Influence and marginal utility: 35/1015/1641 high-influence pairs were identified on MNIST/CIFAR-100/ImageNet, with 31/774/1298 unique test examples influenced above 0.15 by a single training example.The corresponding unique-test-example fractions were 0.33%/8.88%/2.92% of each test set.
  • Influence and marginal utility: 76.06 ± 0.28% versus 73.52 ± 0.25% test accuracy yields a 2.54 ± 0.2% benefit from retaining CIFAR-100 high-influence training examples.On highly influenced test examples, accuracy was 72.14 ± 1.32% with these examples and 45.38 ± 1.45% without them.
  • Examples of high-influence pairs: Very high influence scores above 0.4 usually correspond to near duplicates or images from the same photo set, while over 80% of detected influences are below 0.4.Lower-influence pairs are generally visually similar without usually coming from the same set.
  • Estimation consistency and architectures: Memorization and influence estimates are consistent across ResNet50, ResNet18, Inception, and DenseNet100, but last-layer-only models produce much worse influence estimates and fail to detect memorized examples.Linear models achieved 75.8 ± 0.1% accuracy, versus 72.3 ± 0.3% for 70%-data ResNet50 models, yet identified only 38 versus 18,099 examples above memorization 0.25.

4 Discussion

The experiments support the long-tail explanation: neural networks memorize not only useless outliers and mislabeled examples, but also atypical training examples that improve accuracy on visually similar test examples. The study also identifies computational and methodological boundaries for its conclusions.

  • Memorized examples include atypical training instances that significantly improve accuracy on visually similar test examples, alongside outliers and mislabeled examples.Most training and test examples appear in only one such pair, supporting the long-tail interpretation.
  • The results indicate that accuracy on long-tailed data depends on memorizing labels, with larger effects for under-represented subpopulations.The marginal effect depends on the number of available examples and data variability.
  • Most memorization occurs in representations derived by training a deep neural network, leaving the detailed training-process mechanism for future work.
  • The influence and memorization estimators are model-agnostic, computationally feasible, and essentially as accurate as true leave-one-out influences.The authors emphasize interpretability and ease of implementation relative to existing approaches.
  • High-accuracy estimation requires training thousands of models, creating substantial computational demands and motivating more efficient proxy estimators.The authors provide computed CIFAR-100 and ImageNet values to support future work.

A Proof of Lemma 2.1

The proof rewrites leave-one-out influence terms as conditional expectations over random subsets, allowing both terms to be estimated from shared model samples. It then bounds estimator error using empirical Bernoulli variance and concentration arguments.

  • The first influence term equals the prediction probability conditioned on the sampled subset containing example i.
  • Shared random subsets can estimate each example’s first term by selecting trained models whose sampled index set contains i.
  • The second influence term is analogously represented by prediction probability conditioned on example i being excluded from the sampled subset.
  • The final estimator subtracts the exclusion-conditioned estimate from the inclusion-conditioned estimate, using 1/2 when an estimate has no supporting samples.
  • The error analysis combines Bernoulli empirical-mean variance with a Chernoff bound for insufficient sample counts.
  • In practice, training only subsets of size m approximately preserves the size-(m−1) models and improves efficiency by a factor of 2.

B Details of the Experimental Setup

The experiments use ResNet50-based ImageNet and CIFAR-100 setups, plus MNIST, trained with stochastic gradient descent and momentum. The authors note that these architectures and training procedures are not state of the art because the study requires thousands of model trainings.

  • The implementation uses one Tesla P100 GPU for most jobs and eight P100 GPUs for ImageNet.
  • ImageNet and CIFAR-100 use ResNet50, with the CIFAR-100 input stem modified for 32 × 32 images.
  • ImageNet training uses SGD with momentum 0.9, batch size 896, base learning rate 0.7, and 100 epochs.
  • CIFAR-100 training uses SGD with momentum 0.9, batch size 512, base learning rate 0.4, and 160 epochs.
  • MNIST models use SGD with momentum 0.9, base learning rate 0.1, batch size 256, and 30 epochs.
  • The architectures and training algorithms are not state of the art because state-of-the-art training would make thousands of model trainings infeasible.

C Selection Procedure for Examples of Influence Estimates

Influence-figure examples are selected through a fixed ranking and spacing procedure designed to avoid cherry-picking. The method samples three groups of five training examples across the sorted influence range and visualizes them against four test examples.

  • Training examples are sorted by their highest influence on a test example before visualization.
  • The procedure selects 3 consecutive sets of 5 examples with indices spread evenly through the sorted list.
  • Each selected group is visualized with 4 test examples.
Loading 2008.03703v1…