Estimating Training Data Influence by Tracing Gradient Descent

• TracIn computes the influence of a training example on a test example's prediction.Source: §1 · p. 1
• The method is proposed as a practical technique for analyzing and improving training data.Source: §1 · p. 1
• One motivating application is identifying and fixing mislabeled data.Source: §1 · p. 1

• Existing methods identify feature influence on individual predictions.Source: §2 · p. 1
• Other methods identify training-example influence on the model's overall accuracy or loss.Source: §2 · p. 2
• A closely related method traces training-example influence on overall loss, whereas TracIn targets the loss of a specific test point.Source: §2 · p. 2
• TracInCP uses checkpoints to replay the training process, drawing intuition from checkpoint ensembling.Source: §2 · p. 2

Core idea

• TracIn decomposes the test loss reduction from initialization to the final model along the path taken during training.Source: §3 · p. 2

Idealized influence

• Idealized influence assigns a training example the total test-loss reduction occurring whenever that example is used during iterative optimization.Source: §3.1 · p. 2
• The influences of all training examples on a fixed test point sum to the total loss reduction during training.Source: §3.1 · p. 2

Limitations and extensions

• The idealized definition assumes one-example-at-a-time updates and cannot directly redistribute loss changes within minibatches.Source: §3.1 · p. 2

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.Source: §3.2 · p. 3

Minibatches

• For minibatches, TracIn approximates the minibatch influence and attributes equal per-example portions of that influence.Source: §3.2 · p. 3

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.Source: §3.3 · p. 3
• The derivation assumes a particular training form, while the practical checkpoint method is expected to remain similar across optimizer and minibatch variations.Source: §3.3 · p. 4

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.Source: §4.2 · p. 4
• 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.Source: §4.2 · p. 5

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.Source: §4.3 · p. 6
• 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.Source: §4.3 · p. 6
• 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.Source: §4.3 · pp. 6–7

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.Source: §5.1 · p. 8
• 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.Source: §5.1 · p. 8

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.Source: §5.2 · p. 9

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.Source: §5.3 · p. 9
• 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.Source: §5 · p. 7, §5.3 · p. 9

• TracIn identifies the influence of a training data point on a test point.Source: §6 · p. 9
• Implementing TracIn requires gradients, checkpoints, and loss functions rather than specialized machinery.Source: §6 · p. 9
• TracIn applies to models trained with stochastic gradient descent or variants across architectures, domains, and tasks.Source: §6 · p. 9
• 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.Source: §6 · p. 9
• 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.Source: §6 · p. 9

• Improving training-data quality is expected to improve model quality, giving the technique an expected positive broader impact.Source: §8 · p. 10
• For human-impacting models, TracIn could examine connections between biased training data and biased predictions.The paper gives loan-application models as an example.Source: §8 · p. 10
• 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.Source: §8 · p. 10

• Influence functions use model optimality conditions to mimic perturbing a single training example and measure its effect on a test example.Source: §A.1 · p. 12
• For large deep-learning models, inverse-Hessian computation is costly and complex, and the approach assumes the model has converged.Source: §A.1 · p. 12

Scalable implementation via randomized sketching

• Randomized sketching estimates the inverse Hessian to mitigate infeasibility when models have very many parameters.Source: §A.1 · p. 12
• The sketched product is an unbiased estimator of the inverse-Hessian gradient product.Source: §A.1 · p. 12
• 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.Source: §A.1 · p. 12

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.Source: §A.2 · p. 12
• 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.Source: §A.2 · p. 12

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.Source: §A.2 · pp. 12–13
• 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.Source: §A.2 · p. 13

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.Source: B A Visual Inspection of Proponents… · p. 13, Figure 5 · p. 13, Figure 6 · p. 13

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.Source: C Low Latency Implementation · p. 13

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.Source: D Selecting Checkpoints · p. 14

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.Source: E Random Projection Approximation · p. 14

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.Source: F Fast Random Projections for… · p. 14

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.Source: F Fast Random Projections for… · p. 14

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.Source: F Fast Random Projections for… · p. 14

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.Source: F Fast Random Projections for… · p. 15

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.Source: Figure 7 · p. 15

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.Source: Figure 8 · p. 15

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.Source: Figure 9 · p. 16

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.Source: Figure 10 · p. 17

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.Source: Table 2 · p. 17