PaperlayerView exact revision on arXiv

Source-linked AI summary

Scaling Up Influence Functions

Andrea Schioppa, Polina Zablotskaia, David Vilar, Artem Sokolov

arXiv:2112.03052v1cs.LGcs.CLcs.CV

TL;DR

The paper addresses the difficulty of using influence functions to trace predictions to training data at modern model and dataset scales. It uses Arnoldi iteration to approximate and diagonalize the Hessian efficiently, achieving large speed-ups and evaluations on full-size language and vision Transformers with up to 300M parameters and 100M training examples.

  • Problem

    Influence functions are useful for tracing predictions to problematic training examples, but conventional inverse-Hessian computation is blocked by O(p)-memory and repeated computation at modern scales.

  • Method

    The method uses Arnoldi iteration on a small random data subset to cache a diagonalized dominant-eigenvector subspace of the Hessian instead of repeatedly applying LISSA.

  • Results

    Influence functions achieved 3-4 orders of magnitude speed-ups over LISSA and 10x over TracIn with better or similar accuracy, scaling to models up to 300M parameters and datasets up to 100M examples.

  • Takeaways & Limitations

    The approach enables influence-function analyses on application-relevant models and datasets using standard memory-limited hardware.

  • Takeaways & Limitations

    Correct influence estimates still require locally strictly-convex, twice-differentiable losses, and the method’s time and memory complexities remain unchanged asymptotically.

Abstract

from arXiv · show

We address efficient calculation of influence functions for tracking predictions back to the training data. We propose and analyze a new approach to speeding up the inverse Hessian calculation based on Arnoldi iteration. With this improvement, we achieve, to the best of our knowledge, the first successful implementation of influence functions that scales to full-size (language and vision) Transformer models with several hundreds of millions of parameters. We evaluate our approach on image classification and sequence-to-sequence tasks with tens to a hundred of millions of training examples. Our code will be available at https://github.com/google-research/jax-influence.

1 Introduction

Large-scale, noisy datasets make tracing predictions to training examples increasingly important, but conventional influence functions cannot fit the memory demands of modern models. The paper uses Arnoldi-based Hessian approximation to make influence functions practical for full-size Transformer models and huge datasets.

  • Motivation: Web-scale and heuristically labeled datasets intensify noise, bias, and mislabeled-data problems in DNN training.These issues arise from crawled data, heuristic label pairing, and non-expert annotation.
  • Motivation: Influence functions identify training examples associated with a query prediction’s loss by estimating the effect of infinitesimally up-weighting each example.This provides a theoretically motivated route for diagnosing problematic examples or annotation policies.
  • Limitation: O(p)-memory Hessian inversion and O(r · p) time make LISSA-based influence functions difficult to deploy on models and datasets with hundreds of millions of parameters or examples.The memory requirement is incurred for each training example whose influence is evaluated.
  • Approach: Arnoldi iteration diagonalizes a small dominant-eigenvector subspace of the Hessian, avoiding materialized O(p)-size gradients and repeated LISSA calls.The method estimates the Hessian on a much smaller random subset and caches its diagonalized form.
  • Results: 3-4 orders of magnitude speed-ups over LISSA-powered influence functions and 10x over TracIn were achieved with better or similar accuracy.The evaluation covered language and vision Transformers up to 300M parameters and datasets with 14M to 100M training examples.
  • Impact: The implementation is intended to support influence-function evaluation on application-relevant models and datasets using standard memory-limited hardware.The authors provide an open-source implementation of Arnoldi iteration.

2 Related work

Prior interpretability methods often explain predictions through input-level units, whereas influence functions trace predictions to training examples. Existing accelerations reduce dimensions, data subsets, or iterations, while this work changes the inverse-Hessian procedure itself.

  • Instance-based methods: Instance-based interpretability explains predictions using task-specific input units such as pixels or tokens.Examples include saliency maps, input perturbations, and LIME.
  • Influence functions: Influence functions differ by tracing model predictions back to training examples rather than producing token-level heatmaps.This makes them relevant to data-centric debugging and training-example analysis.
  • Prior acceleration: Prior influence-runtime methods mainly reduce active parameter dimensionality, data-subset cardinality, or iteration count.Other approaches, such as TracIn, simplify the problem into heuristic gradient-based tracking.
  • Relation to prior work: The closest mathematical precedent uses Lanczos iteration to study Hessian spectra across training snapshots, whereas this work approximates Hessians across smaller batches to scale models and datasets.The differing batching strategy supports larger models and datasets at greater speed.

3 Influence and Influence Functions

Influence functions approximate the loss change caused by up-weighting a training example, avoiding infeasible leave-one-out retraining. Their practical bottleneck is repeated Hessian-vector computation, while evaluation uses corruption retrieval and filtering-based proxies.

  • Influence definition: True influence is the loss difference at a query example between models trained without and with a particular training example.Computing it directly would require retraining after removing each example.
  • Influence functions: Influence functions approximate true influence through the loss change from infinitesimally up-weighting a training example.This approximation avoids explicit leave-one-out retraining.
  • Computation: Hessian-vector products can be computed without materializing the Hessian, but repeated HVP calls form the expensive LISSA inverse-Hessian procedure.LISSA estimates inverse HVPs using Hessians approximated on random batches.
  • Computational limitation: O(r · b · p) time is incurred for every queried training example, while O(p)-memory HVPs force single-example batches and can reduce accuracy.These costs make the procedure both time- and memory-expensive even for small iteration counts.
  • Evaluation: Influence methods are evaluated using synthetic-corruption retrieval or changes after filtering high-self-influence points because ground-truth influence labels are unavailable.Both proxies rely on the assumption that high self-influence identifies data outliers.

4 Scaling Influence Functions

The section surveys memory-efficient influence-function approximations and presents Arnoldi iteration as a way to replace the full Hessian with a smaller, approximately invariant subspace. This avoids LISSA-based inversion while retaining influence estimates across large models and datasets.

  • Motivation: O(p)-memory is the major bottleneck for efficient influence-function implementation, motivating approaches that avoid full gradients and Hessians.Existing alternatives include parameter restriction, random selection or projection, and tracing updates, but each introduces approximation or practical limitations.
  • Existing approaches: Parameter restriction and random-selection baselines reduce memory but introduce layer or parameter-subset choices that can change influence estimates.Using one layer can produce estimates different from the full model, while feasible subset size depends on the architecture.
  • Existing approaches: Random projections use forward-mode JVPs and avoid materializing O(p)-size gradients, but the projected subspace need not be H-invariant, causing approximation errors.Arnoldi can retrieve the top eigenvalues with a considerably smaller projection dimension than RandProj.
  • Arnoldi approach: Arnoldi constructs an orthonormal basis for a Krylov subspace and diagonalizes the restricted Hessian to approximate its dominant eigenvalues and eigenvectors.The resulting smaller matrix replaces the full Hessian in the influence calculation, simplifying inversion and dispensing with LISSA.
  • Error analysis: Restricting the quadratic form to the top-k Hessian eigenspace improves its approximation as k increases, while errors associated with smaller eigenvalues matter less.The approximation error is bounded by 1/2|λ_k+1|∥θ∥2^2, and inverse-Hessian noise variance scales approximately as |λ_k|^-2.

5 Experiments

Experiments evaluate Arnoldi-based influence functions across MNIST, machine translation, and vision models, testing retrieval quality, data selection, and scalability. Arnoldi generally offers strong accuracy–runtime trade-offs and enables larger models and datasets, while performance depends on task and model conditions.

  • Method: Arnoldi builds an orthonormal Krylov-subspace basis from Hessian-vector products and distills dominant Hessian eigenvalues and eigenvectors for influence estimation.The method avoids explicitly materializing the full Hessian and replaces LISSA inversion with a low-dimensional diagonalized approximation.
  • Small Model & Data Scale: Digit Recognition: On small MNIST models, Arnoldi outperforms RandProj for eigenvalue estimation and mislabeled-example retrieval as the retained projection size increases.For sufficiently large projection size, Arnoldi can even outperform the exact-Hessian influence estimate because near-zero eigenvalues make exact inversion unstable.
  • Small Model & Data Scale: Digit Recognition: 104x faster: Arnoldi estimated the larger CNN’s Hessian in 353 seconds for p̃ = 10 and n = 200, while LISSA was about 10^4 times slower overall.TracIn achieved the best retrieval quality in this setting but becomes problematic for larger models and datasets.
  • Scaling with Data Size: Machine Translation: On WMT17, Arnoldi outperforms RandProj for retrieving synthetic mislabeled examples, while RandSelect has the poorest retrieval quality and scales poorly in memory.The experiment uses Hessian-vector-product batches of 512 examples for Arnoldi, compared with 64 for RandSelect.
  • Scaling with Model Size: Computer Vision: 15 hours: Arnoldi estimates the top 200 eigenvalues of ViT-L32, with runtime increasing linearly with model size.The experiments extend influence-function evaluation to full-size Transformer models and datasets containing up to 14M ImageNet or 100M Paracrawl examples.

6 Conclusion

The paper introduces an influence-function method that approximately diagonalizes Hessians while avoiding per-example Hessian re-estimation, enabling analysis at large data and model scales. Its effectiveness varies with task nature, convergence, and local convexity, but it enables further influence-based analyses on practical systems.

  • The method approximates Hessian diagonalization and avoids re-estimating Hessians for every training example.
  • It identifies influential or noisy examples in datasets with up to 100M training examples and models with up to 300M parameters.
  • Influence functions can outperform or match random-projection and gradient-based approaches when retrieving synthetically mislabeled data, depending on task conditions.
  • The method enables influence-based analyses on application-relevant models and datasets within acceptable timeframes on standard hardware.

A Approximation of Influence Functions

Influence functions approximate the effect of removing or upweighting a training example by using a quadratic loss model and an inverse Hessian. Restricting the Hessian to dominant eigendirections controls approximation error, while small eigenvalues amplify estimation noise.

  • The analysis models removing a training point by minimizing a quadratic approximation to the training loss around converged parameters.
  • The influence of a training example on a query prediction is obtained from the inverse Hessian applied to training and query gradients.
  • Restricting the Hessian to the top-k eigenspace yields a quadratic form Qk that increasingly approximates Q as k grows.
  • The approximation error is bounded by 1/2|λk+1|∥θ∥2^2 when omitting eigendirections beyond k.
  • Under the stated noisy-Hessian approximation, the estimator is approximately unbiased because the perturbation has approximately zero expected value.
  • Variance in the ek direction scales as |λk|^-2, so small Hessian eigenvalues increase noise in influence estimates.

A.1 Arnoldi iteration for inverse Hessian

The paper favors approximating the Hessian itself with dominant eigencomponents rather than applying Arnoldi directly to the inverse Hessian. Direct inverse-Hessian Arnoldi requires iterative inverse Hessian-vector products and was not competitive in the tested setting.

  • Applying Arnoldi to H^-1 targets the smallest-magnitude eigenvalues of H, but requires iterative inverse HVP estimation such as LISSA.
  • With r LISSA iterations per Arnoldi iteration, the direct inverse-Hessian approach is r times slower.
  • For the larger CNN, testing the direct inverse-Hessian approach with r = 50 did not make it competitive with the proposed approach.
  • Using ˜p = 10 projectors achieved 97.9/91.9 AUC/AP, while ˜p = 100 did not improve on Arnoldi’s 97.9/92.8 retrieval quality.

B.1 Opponents and Proponents

The experiments interpret positive and negative self-influence examples as proponents and opponents, respectively, and examine how gradient normalization affects retrieved examples. Longer training and regularization materially affect retrieval quality and the relative performance of methods.

  • Opponents and Proponents: Positive influence examples are proponents because removing them increases the query loss, whereas negative influence examples are opponents because removing them decreases it.
  • Opponents and Proponents: Gradient normalization makes retrieved proponents more stylistically similar to correctly labeled digit-5 queries, while unnormalized gradients can favor high-gradient mislabeled examples.
  • Opponents and Proponents: For a digit-4 query mislabeled as 9, proponents were incorrectly labeled 4s, while unnormalized opponents were correctly labeled 4s with larger gradients.
  • Longer training: With 100 training epochs and no regularization, CNN accuracy was 69.47%, whereas regularization raised it to 74.3% and improved retrieval conditions.
  • Longer training: TracIn with 10 checkpoints had the best retrieval accuracy for this CNN but was much slower and did not scale to larger models and datasets.
  • Machine translation: The machine-translation evaluation uses heuristic prefilters based on length ratios, long tokens, and edit-distance thresholds to remove likely problematic sentence pairs.

C.2 Experimental Details

The sequence-to-sequence experiments use a Transformer Base configuration with shared tokenization and embeddings, packed batches, and Adam optimization with a warmup-and-decay learning schedule.

  • The Transformer Base model uses a shared 32k SentencePiece vocabulary, 512-dimensional hidden states, 2048-dimensional MLPs, 8 attention heads, and 6 encoder and decoder layers.
  • Weights are shared between the final layer and embeddings, with bfloat16 precision and 0.1 dropout in both attention and MLP components.
  • Sentences are packed to a maximum length of 256, producing approximately 56k non-padding tokens per batch, while optimization uses default Flax Adam settings.
  • The learning rate increases linearly to 0.002 over the first 1k steps and then follows square-root decay, with SacreBLEU used for evaluation.

C.3 Exemplars

Arnoldi self-influence scores organize noisy Paracrawl examples from short, relatively clean segments to increasingly questionable or mislabeled translations. Sentence length correlates with influence only in the cleanest portion of the data.

  • The lowest-influence Paracrawl examples are clean but very short, while higher quantiles contain longer and less reliably translated segments.
  • The 90%-100% quantile includes an incorrect pair of English sentences whose high self-influence reflects the need for memorization.
  • For the 0-10% quantile, longest-sentence length has a Spearman correlation of about 0.5 with influence rank and pval < 10^-6.
  • In the 70%-100% range, the length correlation becomes negative and is only weakly sized.

D.1 Experimental Details for ViT

The experiments examine memory management, noisy-data retrieval, and visual self-influence patterns. Across the reported examples, high self-influence is associated with difficult or mislabeled data, while removing low-influence data can damage generalization more.

  • Experimental setup: Arnoldi iterations are offloaded to host RAM because memory consumption scales linearly with the parameter count, while restart-based reductions remain future work.
  • Experimental setup: On noisy CIFAR-10, the study retrieves synthetic mislabeled examples with ViT using Arnoldi and an effective batch size of 8192 on a four-core TPUv2.
  • ImageNet exemplars: ImageNet samples in the highest self-influence quantiles are often mislabeled or visually ambiguous, whereas lower-quantile samples are more typical.
  • Proponents and opponents: Proponent and opponent visualizations compare normalized and unnormalized influence scores, with normalization filtering out visually dissimilar examples after top-label pre-filtering.
  • Removal experiment: High- and low-self-influence removal tests compare memorization against generalization by retraining ResNet50 after removing equal data fractions.
  • Removal experiment: Removing low-self-influence examples hurts performance more than removing high-self-influence examples in this setting.
  • Implications: The authors frame the estimator as a basis for studying memorization-generalization trade-offs and data-ordering strategies in other applications.
Loading 2112.03052v1…