Source-linked AI summary
Estimating Training Data Influence by Tracing Gradient Descent
Garima Pruthi, Frederick Liu, Mukund Sundararajan, Satyen Kale
TL;DR
Training-data influence on predictions is difficult to analyze practically. TracIn traces test-loss changes when examples are used, with a scalable, simple, and general implementation; it identifies mislabeled data effectively, while misuse or inaccuracy can produce harmful fairness judgments.
Problem
The paper studies how to identify the influence of training examples on a test prediction to improve analysis and quality of training data.
Method
TracIn traces changes in test-example loss along the training path, approximating influence with gradients, checkpoints, and selected network layers.
Results
TracIn recovered more than 80% of mislabeled data in the first 20% of the ranking, versus less than 50% for other methods.
Takeaways & Limitations
TracIn offers a simple, general technique for understanding training-data influence across models trained with stochastic gradient descent or variants.
Takeaways & Limitations
Inaccurate influence estimates could incorrectly label a model fair or unfair, with risks amplified when adversaries use the technique.
Abstract
from arXiv · showhide
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.
1 Motivation
The paper studies how individual training examples influence predictions on test examples, motivated by training-data quality as a lever for improving deep learning models.
- TracIn computes the influence of a training example on a test example's prediction.
- The method is proposed as a practical technique for analyzing and improving training data.
- One motivating application is identifying and fixing mislabeled data.
2 Related Work
Prior work studies influence at different targets, including features, training examples, and overall model performance; TracIn instead focuses on training-example influence on a test point's loss.
- Existing methods identify feature influence on individual predictions.
- Other methods identify training-example influence on the model's overall accuracy or loss.
- A closely related method traces training-example influence on overall loss, whereas TracIn targets the loss of a specific test point.
- TracInCP uses checkpoints to replay the training process, drawing intuition from checkpoint ensembling.
3 The Method
TracIn measures how each training example changes a test point's loss along the training trajectory, then approximates and scales this computation using gradients, minibatch attribution, and checkpoints.
- Core idea: TracIn decomposes the test loss reduction from initialization to the final model along the path taken during training.
- Idealized influence: Idealized influence assigns a training example the total test-loss reduction occurring whenever that example is used during iterative optimization.
- Idealized influence: The influences of all training examples on a fixed test point sum to the total loss reduction during training.
- Limitations and extensions: The idealized definition assumes one-example-at-a-time updates and cannot directly redistribute loss changes within minibatches.
- First-order approximation: A first-order approximation estimates each update's test-loss change from the dot product of test and training-example gradients, weighted by the step size.
- Minibatches: For minibatches, TracIn approximates the minibatch influence and attributes equal per-example portions of that influence.
- Practical implementation: Checkpoint-based TracIn replaces iteration-level parameter tracing with checkpoint parameters, assuming each example is visited once between checkpoints for one approximation result.
- Practical implementation: The derivation assumes a particular training form, while the practical checkpoint method is expected to remain similar across optimizer and minibatch variations.
4 Evaluations
Across CIFAR-10 and MNIST, TracIn identifies more mislabeled examples than comparison methods, while approximation and checkpoint choices affect practical performance.
- CIFAR-10: Training on CIFAR-10 mislabelled data reduces test accuracy from 93.4% to 87.0%.Train accuracy remains 99.6% in this setting.
- CIFAR-10: Different checkpoints emphasize different classes of mislabelled examples, supporting checkpoint sampling throughout training.The 30th checkpoint emphasizes deer and frogs, while the 150th emphasizes trucks.
- MNIST: On MNIST, TracIn retrieves a larger fraction of mislabelled examples than representer points and influence functions across inspected-data fractions.Approximate TracIn recovers examples faster than heuristic TracInCP, but only by a small margin.
- MNIST: The first-order approximation achieves a Pearson correlation of 0.978 with the observed loss change across 100 random test points.This evaluates one parameter-update step per test point.
- MNIST: TracInCP correlation improves with more checkpoints, especially when selected checkpoints have high loss-reduction rates.Later checkpoints can be less informative because their loss gradients are small.
5 Applications
TracIn is applied across regression, text classification, and ImageNet vision tasks to generate insights about influential training examples. These applications identify model-based comparables, correlations, and potentially confusing or corrective examples, while the ImageNet case demonstrates scalability.
- Regression: TracIn identifies model-based real-estate comparables by examining proponents for predictions of houses in expensive Palo Alto.The regression application uses proponents to find similar houses indicative of a prediction’s market context.
- Regression: High self-influence examples occur in densely populated locations, whereas low self-influence examples occur in sparsely populated areas.The authors interpret high self-influence as more likely to indicate memorization and the geographic pattern as consistent with where memorization is reasonable or harmful.
- Text classification: For DBPedia, TracIn opponents reveal data introducing correlations between politicians and artists after filtering misclassified training examples.The experiment uses a 560K-example training set and a 70K-example test set, with 95.5% accuracy on both training and test data.
- ImageNet classification: For ImageNet, proponents are mostly same-label images, while opponents expose examples that may confuse the model across related or visually similar classes.Examples include castles for churches, French bulldogs for Boston bull terriers, and loupes or spotlights for wheels.
- ImageNet classification: In the first ImageNet row, the microphone’s differing style suggests augmenting training data with similar images could address the misclassification.The use case applies TracIn to a ResNet-50 trained on the large ImageNet dataset, demonstrating that the method scales.
6 Conclusion
The paper presents TracIn as a simple and general method for understanding how training examples influence predictions. It supports diverse applications, but correct use still depends on human choices about inputs and interpretation.
- TracIn identifies the influence of a training data point on a test point.
- Implementing TracIn requires gradients, checkpoints, and loss functions rather than specialized machinery.
- TracIn applies to models trained with stochastic gradient descent or variants across architectures, domains, and tasks.
- Influence analysis can explain individual predictions and identify mislabelled examples, with other applications expected to emerge.One cited example uses influence to expand hard examples for toxic-speech classifiers.
- Applying TracIn correctly requires human judgment in selecting checkpoints, layers, and loss heads and interpreting sufficiently many influential examples.The authors also caution that the measure should be used meaningfully within a broader context.
8 Broader Impact
The paper frames TracIn as a practical technique for understanding how training data affects predictions, with expected benefits from improving training-data quality. It also identifies risks when the method is inaccurate or misused in human-impacting settings.
- Improving training-data quality is expected to improve model quality, giving the technique an expected positive broader impact.
- For human-impacting models, TracIn could examine connections between biased training data and biased predictions.The paper gives loan-application models as an example.
- An inaccurate analysis could incorrectly label a model as fair or unfair, with this risk amplified when adversaries use the technique to support a claim.The technique could also identify training-data changes that harm predictions broadly or for a narrow category.
A Description of Influence Functions and Representer Point Methods
Influence-function methods approximate the effect of perturbing training examples but require costly inverse-Hessian computations and convergence assumptions. Randomized sketching addresses the computational bottleneck with an unbiased estimator using substantially less memory.
- Influence functions use model optimality conditions to mimic perturbing a single training example and measure its effect on a test example.
- For large deep-learning models, inverse-Hessian computation is costly and complex, and the approach assumes the model has converged.
- Scalable implementation via randomized sketching: Randomized sketching estimates the inverse Hessian to mitigate infeasibility when models have very many parameters.
- Scalable implementation via randomized sketching: The sketched product is an unbiased estimator of the inverse-Hessian gradient product.
- Scalable implementation via randomized sketching: The sketch uses O(dp) memory instead of O(p^2), and is computed by solving a least-squares optimization problem with a customized stochastic-gradient procedure.The procedure uses independently chosen minibatches and Hessian-vector products.
A.2 Representer Point Selection
The representer point method expresses a test point’s logits through weighted similarities to training representations, but requires modifying and retraining the final layer. Its regularization and model-dependence create practical and conceptual limitations relative to explaining test loss.
- Representer point method: The method decomposes each test point’s logits into weighted dot products between its top-layer representation and training representations.The weights in this decomposition represent training-example influence.
- Representer point method: It adds L2 regularization to the final layer and trains that layer to convergence before computing influences.This produces new final-layer parameters rather than using the original model directly.
- Limitations: The resulting procedure requires a complex, memory-intensive line search and may produce influences unfaithful to the original model.The concern follows from the model being changed by final-layer tuning.
- Limitations: Influence functions and TracIn can explain a training example’s effect on test loss or prediction score, whereas representer points do not clearly explain test loss.The comparison concerns the kinds of test-point explanations each method supports.
- Qualitative comparison: On CIFAR-10, all three methods mostly selected cats as proponents and dogs as opponents for a correctly classified cat, while TracIn appeared more type-consistent.For a misclassified automobile, TracIn proponents selected automobiles of a similar variety.
C Low Latency Implementation
TracIn can support low-latency influence retrieval by indexing concatenated checkpoint gradients with approximate nearest-neighbor search. Checkpoint placement and gradient sketching trade storage and computation against approximation quality.
- Approximate retrieval: Concatenated training-point loss gradients from multiple checkpoints can be indexed for approximate nearest-neighbor retrieval of influential examples.The same concatenation is constructed for a test example during analysis.
- Checkpoint selection: Epoch-boundary checkpoints ensure that each training example is visited exactly once between consecutive checkpoints.The procedure can instead sample more densely where loss decreases faster and avoid early fluctuating-loss checkpoints.
- Gradient sketching: Random projections produce low-memory gradient sketches and randomized unbiased influence estimators that can be reused across multiple test points.Increasing projection dimension lowers estimator variance.
F Fast Random Projections for Gradients of Fully-Connected Layers
Fully connected layers enable faster TracIn gradient computations because their weight gradients are rank 1. Exploiting this structure reduces dot-product cost and supports more efficient random-projection implementations.
- Random projections: Random projection of a fully connected-layer gradient can use time and space O((m + n) · d) rather than naive O(mnd).This exploits the layer’s rank-1 gradient structure.
- Rank-1 gradients: A fully connected layer’s weight gradient is rank 1, enabling specialized inner-product computations for TracIn.The relevant computation pairs gradients from two inputs and functions.
- Fast computation: O(m + n) computation replaces the naive O(mn) gradient dot product for a fully connected layer.The fast form computes separate dot products over output-gradient and input vectors, then multiplies them.
- Random projections: Independent random projection matrices yield an unbiased randomized dot product.The construction is intended for low-memory TracIn computations and nearest-neighbor search.
G Additional Results
Additional results include visual analyses on MNIST, California housing, CIFAR-10, and DBPedia, with figures covering approximation quality, mislabeled-example discovery, and qualitative proponents and opponents.
- MNIST: Figure 7 compares per-step loss changes with TracIn influences for 100 MNIST test examples to assess the first-order approximation.The figure is specifically intended to measure approximation quality.
- Mislabeled examples: Figure 8 reports the number of identified mislabeled examples by class across three checkpoints within the top 10% of self-influence rankings.Different checkpoints highlight different labels.
- MNIST: Figure 9 presents proponents and opponents for correctly classified MNIST images across TracIn, representer point, and influence-function methods.Predicted classes are shown in brackets.
- Other datasets: Figure 10 presents TracIn results on the California housing prices dataset.The supplied passage identifies the dataset but does not state a specific outcome.
- DBPedia: Table 2 presents DBPedia text-classification proponents, with all shown examples sharing the same label and prediction.The table is associated with the paper’s text-classification results.