Estimating Training Data Influence by Tracing Gradient Descent

Garima Pruthi, Frederick Liu, Satyen Kale, Mukund Sundararajan

TL;DR

TracIn is a simple and scalable method to determine which training examples most influenced a model's specific prediction. By "tracing" how much a training point reduces the loss of a test point during the gradient descent process, it identifies "proponents" (helpful examples) and "opponents" (harmful or confusing ones) more effectively than previous, more complex methods.

What Problem Does This Paper Address?

Deep learning models are often criticized as "black boxes." When a model makes a mistake—or even when it gets something right—researchers want to know: Which training examples were responsible for this behavior?

Existing techniques, like Influence Functions, attempt to answer this by calculating how the model would change if a specific training point were removed. However, these methods are computationally expensive (requiring the inversion of a massive matrix called a Hessian) and rely on the assumption that the model has fully converged to a global optimum—an assumption that rarely holds true for deep neural networks. The authors of this paper sought a method that is mathematically grounded, easy to implement, and scales to modern, large-scale architectures.

Methods

The core intuition behind TracIn is inspired by the fundamental theorem of calculus: the total change in a test point's loss over the course of training is the sum of the changes induced at each individual step of Gradient Descent.

  1. Idealized TracIn: Every time a training example $z$ is used to update the model, the method calculates how much that specific update reduced the loss on a test example $z'$.
  2. First-order Approximation: To make this efficient, they use a first-order approximation. The influence is calculated as the dot product of the gradients: $\eta_t \nabla \ell(w_t, z) \cdot \nabla \ell(w_t, z')$. If the gradients point in the same direction, the training example is "helping" the model learn the test example.
  3. TracInCP (The Practical Version): Since tracking every single training step is impossible, the authors use checkpoints saved during standard training. They sum the gradient dot products across these checkpoints to estimate the total influence.
  4. Scalability Tricks: To handle massive models like ResNet-50, they suggest "cherry-picking" specific layers (usually the last layer) or using random projections to reduce the dimensionality of the gradients.

Datasets

The authors evaluated TracIn across a diverse range of tasks and datasets:

  • Image Classification: MNIST (digits), CIFAR-10, and ImageNet (1.28M images).
  • Text Classification: DBPedia ontology dataset (560K training examples).
  • Regression: California Housing Prices dataset.

Key Insights and Ideas

  • Dynamic Influence: Unlike previous methods that look at the model only at the end of training, TracIn views influence as a dynamic process. It captures how a training point "teaches" the model at different stages of learning.
  • Self-Influence as a "Red Flag": A training point’s influence on its own loss is a powerful diagnostic tool. If a point has very high "self-influence," it often means the model is struggling to memorize it, which is a classic sign of mislabeled data.
  • Proponents vs. Opponents:
    • Proponents are training examples that look and act like the test case, actively reducing its loss.
  • Opponents are examples that increase the loss on the test case. For instance, if testing on a "church" image, an opponent might be a "castle"—visually similar but belonging to a different class, thus confusing the model.
Examples of proponents and opponents identified by TracIn compared to other methods.
  • Simplicity Wins: TracIn doesn't require second-order derivatives or complex optimization. If you can compute a gradient and save a checkpoint, you can use TracIn.

Key Results

  • Identifying Mislabeled Data: On CIFAR-10, TracIn significantly outperformed Influence Functions and Representer Points. It recovered over 80% of mislabeled examples within the top 20% of its ranked list.
TracIn outperforms baseline methods in identifying mislabeled data and improving test accuracy across CIFAR-10 and MNIST.
  • High Correlation: The practical checkpoint-based version (TracInCP) showed a very high Pearson correlation (0.978) with the "true" influence calculated at every training step.
  • Qualitative Clarity: In ImageNet experiments, TracIn identified highly intuitive proponents. For a misclassified "band-aid" image, it correctly identified that the training proponents were actually "microphones," explaining why the model was confused (the band-aid was held near a mouth like a mic).

Limitations and Future Work

  • Checkpoint Frequency: The accuracy of the method depends on having enough checkpoints. If checkpoints are too far apart, the approximation might miss critical "learning moments" where the loss changes rapidly.
  • Layer Selection: While using only the last layer is efficient, it might miss nuances captured by earlier convolutional layers. The authors suggest "cherry-picking" layers, but this remains a heuristic.
  • Human in the Loop: TracIn identifies influential points, but it cannot definitively say if a point is "bad." A human is still required to inspect the flagged data to decide if it should be removed or relabeled.
  • Future Directions: The authors suggest TracIn could be used for active learning—identifying "hard" examples to prioritize for human labeling to improve the model more efficiently.

Summary updated

Abstract

We introduce a method called TracIn that computes the influence of a training example on a prediction made by the model. The idea is to trace how the loss on the test point changes during the training process whenever the training example of interest was utilized. We provide a scalable implementation of TracIn via: (a) a first-order gradient approximation to the exact computation, (b) saved checkpoints of standard training procedures, and (c) cherry-picking layers of a deep neural network. In contrast with previously proposed methods, TracIn is simple to implement; all it needs is the ability to work with gradients, checkpoints, and loss functions. The method is general. It applies to any machine learning model trained using stochastic gradient descent or a variant of it, agnostic of architecture, domain and task. We expect the method to be widely useful within processes that study and improve training data.
BibTeX
@inproceedings{pruthi2020estimating,
  author = {Garima Pruthi and Frederick Liu and Satyen Kale and Mukund Sundararajan},
  title = {{Estimating Training Data Influence by Tracing Gradient Descent}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=jvr1-4cRN0V},
}
Figure