PaperlayerView exact revision on arXiv

Source-linked AI summary

Training Data Influence Analysis and Estimation: A Survey

Zayd Hammoudeh, Daniel Lowd

arXiv:2212.04612v3cs.LG

TL;DR

Modern models’ use of training data is increasingly opaque, while anomalous training instances can degrade generalization. This survey formalizes competing influence definitions, organizes influence methods into a taxonomy, and compares their assumptions, complexity, strengths, and weaknesses to guide method selection.

  • Problem

    Training data influence is difficult to understand in opaque modern models, despite training data determining model behavior and anomalous instances degrading generalization.

  • Method

    The survey formalizes pointwise influence and reviews influence-analysis methods from empirical and theoretical perspectives, comparing their assumptions, asymptotic complexities, strengths, and limitations.

  • Results

    The survey finds that influence-analysis methods have different perspectives and definitions, with no single method applying to all situations.

  • Takeaways & Limitations

    Researchers and practitioners should match influence-analysis methods to their individual use cases by understanding each method’s strengths and limitations.

  • Takeaways & Limitations

    RelatIF requires estimating an HVP for every training instance, which is expensive and often highly inaccurate in deep models.

Abstract

from arXiv · show

Good models require good training data. For overparameterized deep models, the causal relationship between training data and model predictions is increasingly opaque and poorly understood. Influence analysis partially demystifies training's underlying interactions by quantifying the amount each training instance alters the final model. Measuring the training data's influence exactly can be provably hard in the worst case; this has led to the development and use of influence estimators, which only approximate the true influence. This paper provides the first comprehensive survey of training data influence analysis and estimation. We begin by formalizing the various, and in places orthogonal, definitions of training data influence. We then organize state-of-the-art influence analysis methods into a taxonomy; we describe each of these methods in detail and compare their underlying assumptions, asymptotic complexities, and overall strengths and weaknesses. Finally, we propose future research directions to make influence analysis more useful in practice as well as more theoretically and empirically sound. A curated, up-to-date list of resources related to influence analysis is available at https://github.com/ZaydH/influence_analysis_papers.

1 Introduction

Training data underlies model decisions, yet its relationship to predictions is opaque and difficult to analyze, especially in large overparameterized models. This survey organizes influence-analysis perspectives and methods to help researchers select approaches for specific applications.

  • Motivation: Anomalous training instances, including distribution shifts, measurement errors, non-representative samples, and labeling mistakes, degrade generalization performance.Poison instances can also be inserted to manipulate specific predictions.
  • Motivation: Training-data biases can encode protected-characteristic disparities and translate into real-world harm.The introduction gives recidivism classification as an example involving different false-high-risk rates for Black and white defendants.
  • Motivation: Training data influence analysis apportions credit and blame for specific model behavior to individual training instances.Influence can be defined, for example, by the change in model performance after deleting an instance, or relatively by comparing instances’ effects.
  • Motivation: Exact influence analysis can be NP-complete in the worst case for multilayer parametric models, motivating computationally efficient estimators.Estimators approximate true influence but rely on assumptions about model architecture and the learning environment, producing different advantages and disadvantages.
  • Survey scope: The paper provides the first comprehensive survey of influence-analysis techniques and their differing perspectives.It formalizes influence definitions, categorizes impactful methods, compares strengths, weaknesses, assumptions, and complexities, and reviews applications and future directions.
  • Survey scope: The survey emphasizes general and parametric-model methods, while giving less attention to non-parametric methods and excluding related areas such as data pruning and active learning.The authors state that they focus on the most impactful methods rather than covering every method in detail.

2 General Notation

The paper standardizes notation for datasets, instances, models, parameters, losses, optimization iterations, sampling, and alternate training sets. This notation supports later definitions and method-specific analyses.

  • Set notation: Sampling notation m∼B indicates that a set of cardinality m is drawn uniformly at random from B; power sets and set subtraction use 2A and A \ B.For singleton sets, the sampling and subtraction notation is simplified.
  • Datasets and instances: A training instance is zi := (xi, yi), with dataset D := {zi}n_i=1 and test instances denoted zte := (xte, yte).Features lie in X ⊆ R^d, dependent values lie in Y, and yte need not be the true value for xte.
  • Models and evaluation: A model f : X → Y is parameterized by θ ∈ R^p and trained on all or part of dataset D.Model performance is evaluated with a loss function ℓ, and empirical risk is written L(z; θ), where smaller risk is better.
  • Optimization: First-order optimization updates parameters iteratively from initial θ(0) through θ(t), using the previous parameters, loss, batch B(t), and learning rate η(t).The notation applies primarily to overparameterized models with p ≫ d trained over T iterations.
  • Optimization: Superscript “(t)” indicates that a symbol applies to training iteration t.The notation distinguishes parameters and related quantities across optimization steps.
  • Alternate training sets: Alternate training sets, such as D \ zi, receive distinct parameter notation for models trained without a particular instance.When training uses all of D, the subscript D is omitted from θ(t).

3 Overview of Influence and Influence Estimation

Influence analysis quantifies how training instances affect model behavior, from individual predictions to broader test distributions, while exact measurement can be computationally intractable. The survey organizes influence methods into retraining-based analyses and gradient-based estimators, comparing their assumptions, complexities, strengths, and weaknesses.

  • Alternative perspectives: Group influence measures a set of training instances’ combined effect on a specific test prediction.The scope of influence can instead extend across an entire test data distribution.
  • Influence estimation: Exact influence can require repeating all training in the worst case, motivating approximate influence estimators with different assumptions and mathematical formulations.These trade-offs balance tractability against approximation of true influence.
  • Pointwise influence: Pointwise influence measures one training instance’s effect on one test instance under a specified quality measure.Model architecture, training algorithm, full training set, and random seed are treated as fixed and implicit.
  • Early pointwise influence: A single outlier can have unbounded pointwise influence on least-squares parameters and predictions.The cited example shows an outlier substantially shifting the fitted model so that predictions on training values become poor.
  • Method taxonomy: Retraining-based methods measure influence by training models on different subsets, whereas gradient-based estimators use training–test gradient alignment during or after training.The survey compares seven primary methods using assumptions, asymptotic complexities, strengths, and weaknesses.
  • Alternative perspectives: Coherent groups often have influence greater than the sum of their individual pointwise influences, showing that influence may be non-additive.Non-additive influence estimators also exist, so additivity is not required.
  • Alternative perspectives: Expected influence averages an instance’s influence across stochastic model retrainings, which can vary substantially.This perspective is useful when the random component of training is unknowable beforehand.

4 Retraining-Based Influence Analysis

Retraining-based influence measures compare model behavior across training sets, making few assumptions but incurring substantial computational cost. The section presents LOO, Downsampling, and related methods that trade exactness, stability, flexibility, and scale.

  • Framework: Retraining-based influence compares a model trained with an instance against one trained without it, applying to parametric and non-parametric models.This formulation is the foundation of retraining-based influence analysis.
  • Framework: Retraining makes no assumptions about the learning environment, but its flexibility comes at the expense of high computational cost.Gradient-based estimators require stronger assumptions, some of which do not hold for deep models.
  • Leave-one-out influence: LOO requires training (n + 1) models and is among the few influence measures computable exactly in polynomial time for deterministic model classes and algorithms.Its simplicity also makes LOO human-intelligible and compatible with any model architecture.
  • Downsampling: Downsampling mitigates LOO’s dependence on n and instability from stochastic training by estimating expected LOO influence across an ensemble of randomly sampled submodels.It is statistically consistent, with high-probability error bounds determined by K and m.
  • Downsampling: Downsampling is more scalable and flexible than LOO but still requires potentially prohibitive upfront computation to train multiple models.It has been applied to all pointwise influence estimates on ImageNet with more than 14 million instances.
  • Shapley value: Shapley value offers a theoretically grounded, flexible influence measure that can evaluate varying training-set sizes and detect behavior missed by LOO or Downsampling.Its linearity axiom permits estimating pointwise and joint values without repeating data collection, while small subsets may improve poison detection.
  • Shapley value: TMC-Shapley usually requires on the order of n permutations and has full time complexity O(n^2T), whereas kNN Shapley is linear in n and requires no retraining.kNN Shapley’s main computational cost is sorting instances by distance and it can serve as a surrogate for more complex models.
  • Related methods: Banzhaf value weights subsets differently from Shapley value and has been shown to produce more variance-robust rankings and sometimes outperform Shapley value.The comparison concerns training-variance robustness and empirical performance.

5 Gradient-Based Influence Estimation

Gradient-based estimators trade retraining cost for assumptions about optimization, differentiability, curvature, and model representations. Static methods can be efficient but limited, while dynamic methods such as TracIn and HyDRA capture training-time effects with different computational and accuracy trade-offs.

  • Influence functions: Influence functions eliminate model retraining, but computing the test-instance quantity can take hours and must be repeated for each test instance.Retraining may become faster when many test instances amortize its upfront cost.
  • Representer point: Representer point is highly scalable and efficient but detects only behavior apparent in the model’s final linear layer.Its final-layer focus can miss influential behavior visible in earlier layers.
  • TracInCP: TracInCP analyzes all training instances at selected checkpoints, assigns identical instances identical estimates, and routinely outperforms TracIn on many tasks.Empirical evaluations often use far fewer checkpoints than total training iterations, with loss-changing checkpoints generally preferred over evenly spaced ones.
  • TracIn: TracIn avoids Hessian computation, can use full-model gradients, requires neither stationarity nor convergence, and can identify when during training an instance is influential.Its dynamic analysis may detect instances that static estimators miss because they appear uninfluential at the end of training.
  • HyDRA: HyDRA accumulates training hypergradient effects and can provide more accurate LOO estimates than influence functions on non-convex models.It shares TracIn’s lack of convexity and stationarity assumptions while trading incremental speed for lower precision with respect to the test instance.
  • Computational trade-offs: HyDRA’s incremental cost is O(np), whereas its full time complexity is O(npT); after one-time training-instance unrolling, it can be much faster than TracIn.RelatIF instead requires an HVP for every training instance, which is expensive and often inaccurate in deep models; renormalized influence functions avoid those additional HVPs.

6 Applications of Influence Analysis

Influence analysis is applied across data quality, security, fairness, explainability, and data-selection tasks. These applications use influence to identify consequential training instances, guide data choices, or diagnose model behavior.

  • Data cleaning: Influence analysis supports data cleaning by identifying anomalous training instances associated with labeling errors, non-representative samples, noisy features, or missing features.The goal is to improve overall model performance by removing problematic training data.
  • Security: Influence analysis helps study poisoning, backdoor, and evasion attacks by identifying unusually influential training instances or perturbed test instances.Malicious training instances must be influential to achieve an attacker’s objective, while evasion attacks perturb only test instances.
  • Fairness: Leave-one-out influence has been proposed as a fairness measure when including a single training instance fundamentally changes a model’s decision.The measure treats such sensitivity as potentially unfair or capricious in decisions such as lending or hiring.
  • Explainability: Influence analysis provides example-based and other explanations by identifying training instances that contributed to a prediction, including a misprediction.It can communicate why a model made a particular prediction through visual examples such as training images.
  • Data selection and augmentation: Influence-guided subsampling, active learning, and data augmentation select or construct data using estimated instance influence.Influence-based subsampling can perform at least as well as full-data training in expectation under mild assumptions, while influence-guided augmentation outperforms random augmentation at higher computational cost.

7 Future Directions

The survey identifies priorities for making influence analysis more representative, scalable, verifiable, and useful beyond pointwise attribution. It emphasizes group influence, certification, specialization, surrogate validation, and objective evaluation.

  • Emphasizing Group Influence over Pointwise Influence: Most predictions are moderately influenced by multiple training instances, making group influence important beyond pointwise attribution.Pointwise influence is especially limited for overparameterized models because individual instances mainly affect distributional tails, while group effects can be approximately supermodular.
  • Certified Influence Estimation: Certified influence estimators could upper-bound group influence and support guarantees that deleting a fixed number of instances will not change predictions.Existing certified defenses often rely on architecture-specific techniques and provide coarse bounds.
  • Improved Scalability: Analyzing one test instance can take several hours or more, motivating influence estimators that are at least an order of magnitude faster.Shortcuts and model- or modality-specific specialization may improve speed and accuracy but require thorough testing and verification.
  • Surrogate Influence and Influence Transferability: Surrogate models may improve influence analysis, but they require rigorous empirical evaluation to identify risks and blind spots.The survey leaves open whether compact surrogates beyond a model’s linear layer are suitable.
  • Evaluation: Influence-estimation evaluation should use quantifiable, verifiable ground truth and broader application settings rather than superficial data-cleaning experiments or visual eye tests.The survey questions whether narrow cleaning studies test the promise of explaining black-box predictions and notes that visual assessments lack ground truth and invite bias.

8 Conclusions

Influence estimation remains computationally expensive and potentially inaccurate, yet existing applications demonstrate practical promise. Because methods differ in definitions and perspectives, users must match methods to their strengths and limitations.

  • Conclusion: Influence estimation is computationally expensive and can be prone to inaccuracy, motivating the need for fast certified estimators.The conclusion identifies these as central shortcomings while calling for further progress.
  • Conclusion: Although no single influence method fits every situation, most use cases should have at least one method that fits well.Researchers and practitioners therefore need to understand the strengths and limitations of different methods.

Nomenclature

The paper organizes notation through general, training-related, and influence-estimator-specific references. These tables provide shared symbols and method-specific nomenclature for the survey’s analyses.

  • General nomenclature: Table 2 provides the general nomenclature reference used throughout the document.It establishes notation shared across the influence-analysis methods.
  • Training notation: Table 3 summarizes nomenclature related to model training.Its scope is training-related notation rather than method-specific symbols.
  • Method-specific nomenclature: Table 4 details hyperparameters and symbols specific to individual influence-analysis methods.The supplemental reference distinguishes method-specific nomenclature from the general and training-related tables.

B Influence Analysis Method Definition Reference

This reference section collects formal definitions and equation references for influence-analysis methods, including perturbation-based and hypergradient formulations. It also records related-method abbreviations and source citations.

  • Table 5 indexes influence-analysis method formal definitions by equation number and citation.
  • Perturbation formulations define an instance’s effect through infinitesimal changes to its training weight or risk.The formulation connects perturbing an instance’s weight with its effect on the empirical risk minimizer, and extends the idea to minibatches.
  • Minibatch perturbation definitions use an indicator for batch membership and scale the instance loss to ensure complete removal at ϵ_i = −1/n.
  • HyDRA’s unrolling derivation distinguishes cases where an instance is outside or inside a minibatch and incorporates risk-gradient and Hessian terms.
  • The reference also documents the vanilla-gradient-descent hypergradient update and a fast HyDRA approximation that drops Hessian-associated terms.The approximation is described as the basis of the fast-approximation update rule; comparable complexity is noted for extending TracIn to momentum or adaptive optimization.
Loading 2212.04612v3…