Understanding Black-box Predictions via Influence Functions

Pang Wei Koh; Percy Liang

Source-linked AI summary

Understanding Black-box Predictions via Influence Functions

Pang Wei Koh, Percy Liang

arXiv:1703.04730v3Mar 14, 2017stat.MLcs.AIcs.LG

TL;DR

Explaining black-box predictions requires tracing them back through learning to the training data. This paper develops scalable influence-function approximations and finds them useful for understanding, debugging, detecting dataset errors, and constructing training-set attacks.

Problem
Explaining why models make predictions matters, but influence functions remain limited by expensive second-derivative calculations and assumptions of differentiability and convexity.
Method
The paper traces predictions back to training points using influence functions and efficiently approximates them with second-order optimization techniques.
Results
Influence functions proved useful for understanding model behavior, debugging, detecting dataset errors, and creating visually indistinguishable training-set attacks.
Takeaways & Limitations
Viewing models through their training data offers a versatile tool for developing, understanding, and diagnosing machine learning systems.
Takeaways & Limitations
Influence functions capture local changes, while assessing broader subpopulation effects remains an open question because the model may change substantially.

Abstract

from arXiv · show

How can we explain the predictions of a black-box model? In this paper, we use influence functions -- a classic technique from robust statistics -- to trace a model's prediction through the learning algorithm and back to its training data, thereby identifying training points most responsible for a given prediction. To scale up influence functions to modern machine learning settings, we develop a simple, efficient implementation that requires only oracle access to gradients and Hessian-vector products. We show that even on non-convex and non-differentiable models where the theory breaks down, approximations to influence functions can still provide valuable information. On linear models and convolutional neural networks, we demonstrate that influence functions are useful for multiple purposes: understanding model behavior, debugging models, detecting dataset errors, and even creating visually-indistinguishable training-set attacks.

1. Introduction

The paper explains black-box predictions by tracing them through the learning algorithm to the training data, using influence functions to estimate counterfactual training-point effects without retraining. It presents influence functions as a versatile tool for understanding, debugging, detecting dataset errors, and creating adversarial training examples.

Motivation and approach: Influence functions trace a model’s prediction through its learning algorithm back to the training data that produced its parameters.They formalize a training point’s impact by considering its removal or slight modification.
Motivation and approach: Influence functions estimate training perturbation effects in closed form by differentiating through training, avoiding expensive retraining.They characterize how model parameters change when a training point is upweighted infinitesimally.
Applications: Influence functions support understanding model behavior, debugging models, detecting dataset errors, and creating visually indistinguishable adversarial training examples that can flip neural-network test predictions.The paper frames these examples as the training-set analogue of adversarial examples.

2. Approach

The approach estimates how individual training points affect predictions by approximating counterfactual removal or modification through influence functions. It extends this framework to identify influential features and construct training-set attacks, while capturing training effects more accurately than nearest-neighbor similarity.

Point removal: Influence functions approximate the parameter change from removing a training point without retraining the model.They replace removal with a small upweighting and use a quadratic approximation around the empirical risk minimizer.
Test-loss influence: Applying the chain rule yields a closed-form influence estimate for how a training point changes loss at a test point.The method uses the training-point gradient together with the inverse Hessian at the fitted parameters.
Point perturbation: Influence functions also estimate the effect of modifying training inputs or labels, including arbitrary perturbations and discrete data.Moving mass from the original point to its perturbed version smoothly interpolates between the two examples.
Point perturbation: For small continuous perturbations, the input-parameter gradient gives a direction that approximately maximizes a training point’s effect on test loss.This direction can identify influential features and construct training-set attacks.
Comparison with nearest neighbors: Influence functions capture training effects more accurately than Euclidean nearest neighbors by incorporating training loss and Hessian-based resistance.High-loss outliers can dominate influence, while harmful same-label examples may be missed by pixel-space similarity.

3. Efficiently calculating influence

The paper avoids explicitly forming the inverse Hessian by estimating Hessian-inverse vector products with Hessian-vector products, enabling efficient influence computation across all training points. It uses conjugate gradients and stochastic estimation, with the latter providing significant empirical speedups.

Computational challenges: Naively computing influence requires O(np2 + p3) operations and evaluating influence across all training points, which is too expensive for deep networks.The cost arises from Hessian computation and the need to evaluate influence for every training point.
Hessian-vector products: Implicit Hessian-vector products avoid explicitly computing H−1 and allow precomputing stest for efficient dot products with each training-point gradient.A single-term Hessian-vector product typically costs O(p), matching the time for computing that term’s gradient.
Conjugate gradients: Conjugate gradients estimate H−1v using only Hessian-vector evaluations, requiring O(np) time per iteration without explicitly forming the Hessian.Although an exact solution takes p iterations, fewer iterations often provide a good approximation in practice.
Stochastic estimation: Stochastic estimation samples one training point per iteration instead of processing all n points, producing significant speedups and empirically outperforming conjugate gradients.The procedure repeats estimates and averages them to reduce variance, choosing t large enough for stabilization.
Overall complexity: The resulting method computes influence on all training points in O(np + rtp) time, with rt = O(n) empirically yielding accurate results.The same Hessian-vector-product approach also computes perturbation influence using two matrix-vector products.

4. Validation and extensions

Influence functions closely approximate leave-one-out retraining in logistic regression and remain informative when models are non-convex, non-convergent, or use non-differentiable losses. Smooth loss approximations and damping extend their usefulness beyond the assumptions underlying their theory.

4.1 Validation: Influence-function predictions closely matched actual leave-one-out loss changes for logistic regression on 10-class MNIST.The stochastic approximation was accurate with r = 10 repeats and t = 5,000 iterations, and even r = 1 identified the most influential points despite greater noise.
4.2 Non-convex models: Influence functions remained meaningful at non-optimal parameters from early-stopped SGD or non-convex training, despite Hessians with negative eigenvalues.A damped convex quadratic approximation around the obtained parameters enables influence computation in this setting.
4.2 Non-convex models: Pearson’s R = 0.86 measured the correlation between predicted and actual loss changes for a non-converged CNN with damping λ = 0.01.The network was trained for 500k iterations, and its Hessian was not positive definite.
4.3 Non-differentiable losses: For the hinge loss, setting derivatives at the non-differentiable point to 0 caused influence functions to overestimate training-point influence.The zero second derivative could not capture how close support vectors were to the hinge, making the quadratic approximation effectively linear.
4.3 Non-differentiable losses: Pearson’s R = 0.95 showed that SmoothHinge(s, 0.001) produced influence estimates closely matching retraining effects under the original hinge loss.Accuracy remained high across a wide range of smoothing parameters, degrading only when t became too large.

5. Use cases of influence functions

Influence functions expose how models rely on training data, revealing distinct mechanisms behind correct predictions and identifying influential points behind errors. They also support visually indistinguishable training-set attacks, domain-mismatch diagnosis, and efficient dataset repair.

5.1 Model behavior: Inception and RBF SVM models made the same correct prediction but relied on different training-data patterns.Inception emphasized distinctive clownfish characteristics, whereas the RBF SVM behaved like a soft nearest-neighbor function based on pixel distance.
5.2 Training-set attacks: Influence functions crafted visually indistinguishable training images that flipped predictions on separate test images.The attack iteratively modified training points using Ipert,loss, projected changes to preserve their 8-bit representation, and retrained after each iteration.
5.2 Training-set attacks: 16 test-image predictions were flipped by a visually imperceptible change to one training image.The attack targeted 30 test images featuring the first author’s dog and maximized their average loss over 100 iterations with α = 0.02.
5.3 Domain mismatch: Influence functions identified four training children as 30-40 times more influential than the next most influential examples in a hospital-readmission error.The case used logistic regression trained on 20K diabetic patients from 100+ US hospitals, represented by 127 features.
5.4 Dataset errors: Influence-based inspection repaired a dataset with flipped labels while checking fewer points than baselines based on highest training loss.The experiment flipped labels for a random 10% of training data and prioritized points for manual correction using influence functions.

6. Related work

Influence-based diagnostics originated in 1970s statistics and later expanded from linear models to more general models. Related machine-learning work studied robustness, cross-validation, influence-like prioritization, training-set attacks, and correcting test predictions through label changes.

Influence functions: Influence-based diagnostics originated in 1970s statistics and were developed through seminal work by Hampel, Jaeckel, and subsequent researchers.Earlier work focused on removing training points from linear models, with later work extending influence methods to more general models.
Influence functions: In machine learning, influence functions have seen limited use, including studies of robustness and fast cross-validation in kernel methods.Other related work estimated Cook’s distance or defined influence notions specialized to generalized linear models and finite hypothesis classes.
Training-set attacks: The paper’s training-set attack is mathematically equivalent to prior SVM-based work, whose framework was extended to linear and logistic regression, topic modeling, and collaborative filtering.Those studies derived the attack from KKT conditions without considering influence, with equivalent results for continuous data.
Correcting test predictions: Unlike training-set attacks, prior work corrected incorrect test predictions by changing labels on a small training subset, but was limited to OLS and Gaussian process models with continuous labels.The paper applies influence functions to this problem across a larger range of models and datasets with discrete labels.

7. Discussion

The paper presents influence functions as a common tool for understanding model behavior through training data, while noting their locality limits analysis of larger changes. The authors hope this training-data perspective becomes standard for developing, understanding, and diagnosing complex black-box models.

7. Discussion: Influence functions unify applications including training-set attacks, model debugging, and dataset correction by tracing model behavior to its training data.The common idea is that examining how a model was derived from its training data improves understanding of its behavior.
7. Discussion: Influence functions measure the effect of infinitesimally-small ϵ upweighting a point, enabling efficient closed-form estimates that can be surprisingly effective.Their locality makes these estimates tractable, but also limits direct analysis of more global changes such as a hospital subpopulation’s effect.
7. Discussion: The authors hope viewing complex black-box models through their training data becomes a standard toolkit component for developing, understanding, and diagnosing machine learning.They expect high-performing, complex, black-box models to become increasingly prevalent and important.

A. Deriving the influence function Iup,params

The influence function Iup,params is derived for loss minimization using asymptotic arguments, under twice-differentiability and strong convexity assumptions. The derivation tracks the parameter change caused by upweighting a training point through optimality conditions and a Taylor expansion.

A. Deriving the influence function Iup,params: The derivation applies influence functions to loss minimization, or M-estimation, but is based on asymptotic arguments and is not fully rigorous.The paper directs readers to van der Vaart (1998) and other statistics textbooks for a more thorough treatment.
A. Deriving the influence function Iup,params: The empirical-risk minimizer ˆθ is the starting point for deriving Iup,params.The derivation recalls that ˆθ minimizes the empirical risk.
A. Deriving the influence function Iup,params: The derivation assumes that R is twice-differentiable and strongly convex in θ, ensuring a positive-definite Hessian and the existence of H−1.These assumptions are used in the subsequent derivation.
A. Deriving the influence function Iup,params: It defines the parameter change as ∆ϵ = ˆθϵ,z −ˆθ and expresses the desired quantity in terms of this change.Because ˆθ does not depend on ϵ, the parameter change captures the relevant variation.
A. Deriving the influence function Iup,params: The derivation applies first-order optimality conditions to ˆθϵ,z, Taylor-expands as ϵ →0, uses ∇R(ˆθ) = 0, and drops o(ϵ) terms before combining the results.The final expression follows by combining the optimality and Taylor-expansion relations.

B. Influence at non-convergence

When parameters are near but not at a local minimum, parameter influence approximately decomposes into a z-independent component and a component tracking the response to upweighting training point z. This interpretation follows from decomposing the Newton step after upweighting z.

B. Influence at non-convergence: Near, but not at, a local minimum, parameter influence is approximately a z-independent constant plus the parameter change from upweighting z and taking one Newton step.The approximation applies when the model parameters are close to a local minimum but have not converged.
B. Influence at non-convergence: The Newton step decomposes into an existing-gradient component independent of z and a second component responding to the upweighted point z.Influence Iup,params(z) tracks the second component rather than the contribution shared across training points.
B. Influence at non-convergence: Because the empirical-risk gradient is nonzero away from a local minimum, upweighting z changes both the gradient and empirical Hessian before the Newton step.The gradient changes from g to g + ϵ∇θL(z, ˜θ), while the Hessian changes from H˜θ to H˜θ + ϵ∇².