PaperlayerView exact revision on arXiv

Source-linked AI summary

Towards the Unification and Robustness of Perturbation and Gradient Based Explanations

Sushant Agarwal, Shahin Jabbari, Chirag Agarwal, Sohini Upadhyay, Zhiwei Steven Wu, Himabindu Lakkaraju

arXiv:2102.10618v4cs.LG

TL;DR

Complex, proprietary models can be hard for decision makers to understand and trust, motivating post hoc explanations and more rigorous analysis of how explanation methods relate. The paper derives closed forms and finite-sample bounds for SmoothGrad and C-LIME, showing expected-output equivalence and robustness; experiments report that SmoothGrad converges faster and is more robust than C-LIME.

  • Problem

    Complex, proprietary predictive models can be difficult to understand, while rigorous theory and systematic connections between perturbation- and gradient-based explanations remain limited.

    Source: §1 · pp. 1–2

  • Method

    The paper derives closed-form explanations for SmoothGrad and continuous-data C-LIME, proves their expected-output equivalence and robustness, and derives finite sample complexity bounds.

    Source: §1 · p. 2

  • Results

    Experiments found that both methods needed fewer perturbations than theory predicts, while SmoothGrad converged faster and was more robust than C-LIME, especially at lower variance.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Expected-output equivalence links gradient-based SmoothGrad and perturbation-based C-LIME and supports proving robustness for both methods.

    Source: §1 · p. 2

    SmoothGrad and C-LIME do not generally provide sparse explanations, though adding a regularizer can promote sparsity.

    Source: §5 · p. 5

Abstract

from arXiv · show

As machine learning black boxes are increasingly being deployed in critical domains such as healthcare and criminal justice, there has been a growing emphasis on developing techniques for explaining these black boxes in a post hoc manner. In this work, we analyze two popular post hoc interpretation techniques: SmoothGrad which is a gradient based method, and a variant of LIME which is a perturbation based method. More specifically, we derive explicit closed form expressions for the explanations output by these two methods and show that they both converge to the same explanation in expectation, i.e., when the number of perturbed samples used by these methods is large. We then leverage this connection to establish other desirable properties, such as robustness, for these techniques. We also derive finite sample complexity bounds for the number of perturbations required for these methods to converge to their expected explanation. Finally, we empirically validate our theory using extensive experimentation on both synthetic and real world datasets.

1. Introduction

The paper connects gradient-based SmoothGrad and perturbation-based C-LIME, showing that their explanations converge to the same expected output and are robust in the large-sample limit. Experiments also find faster convergence and greater robustness for SmoothGrad than C-LIME, with lower perturbation variance benefiting both.

1. Introduction

  • In high-stakes settings, decision makers need understandable models to assess trust and reliance, detect potential bias, and develop improvements.Source: §1 · p. 1
  • Despite empirical studies of explanation behavior, rigorous theory and systematic connections between perturbation- and gradient-based methods remain limited.Prior analyses covered modified SmoothGrad or tabular LIME, while this work studies original SmoothGrad and a non-discretized LIME variant.Source: §1 · pp. 1–2
  • Closed-form explanations for SmoothGrad and continuous-data C-LIME converge to the same output in expectation as the number of perturbed samples grows.SmoothGrad is gradient-based, while C-LIME is perturbation-based.Source: §1 · p. 2
  • In the large-sample limit, both methods satisfy Lipschitz continuity, making their explanations robust to small input changes.The paper presents this as the first proof that a LIME variant is robust.Source: §1 · p. 2
  • The paper derives finite sample complexity bounds for the perturbations needed by SmoothGrad and C-LIME to converge to their expected outputs, and proves both methods are linear.Source: §1 · p. 2
  • Across synthetic and real-world experiments, both methods needed fewer perturbations than theory predicts; SmoothGrad converged faster and was more robust than C-LIME, especially at lower variance.Smaller perturbation variance also let both methods converge faster and exhibit robustness with fewer samples.Source: §1 · p. 2

2. Preliminaries

The section introduces local feature-attribution methods and sets up a continuous-feature LIME variant for comparison with SmoothGrad. Both methods explain individual predictions using nearby inputs, with the paper specifying its sampling and fitting assumptions.

2.1. SmoothGrad

  • SmoothGrad averages gradients at nearby inputs to reduce the noise that can make vanilla gradients highlight random features and miss important ones.Its empirical explanation uses a neighborhood sample, while its expected explanation replaces the sample average with an expectation.Source: §2.1 · p. 2

2.2. LIME

  • LIME explains a prediction by fitting an interpretable model to predictions on perturbed examples near the input.The paper's definition omits LIME's default feature-discretization step.Source: §2.2 · p. 3

2.3. Our Setting and Assumptions

  • C-LIME uses continuous features, Gaussian perturbations, an unweighted linear fit, and no regularizer; the explanation reports feature weights, omitting the intercept by centering.The paper restricts its explanation class to linear models and assumes Gaussian samples centered at the input with covariance Σ = σ²I; it notes that many results also hold for arbitrary Σ.Source: §2.3 · p. 3

3. Equivalence and Robustness

With a shared Gaussian distribution for gradient computation and perturbation, SmoothGrad and C-LIME have identical expected explanations. The paper also establishes Lipschitz robustness under specified conditions and describes how its bound varies with gradient magnitude and perturbation variance.

3.1. Equivalence

  • For any function and input, SmoothGrad and C-LIME have identical expected explanations when both use the same Gaussian distribution and its covariance is invertible.For diagonal covariance, each coefficient depends only on the covariance between the function output and the corresponding feature; with Σ = σ²I, it is cov(f(a), a_i)σ⁻².Source: §3.1 · p. 4

3.2. Robustness

  • Both methods are L-Lipschitz when the function's gradient is bounded and Σ = σ²I, with L = ∇f_max/(2σ).The proof establishes SmoothGrad's Lipschitzness and uses the equivalence result to infer it for C-LIME.Source: §3.2 · p. 4
  • The Lipschitz constant grows with gradient magnitude and as perturbation variance decreases, but does not depend on input dimension.Thus the stated dimension independence holds alongside the bound's dependence on gradient magnitude and σ².Source: §3.2 · p. 4

4. Convergence Analysis

The section derives finite-sample bounds for how quickly empirical SmoothGrad and C-LIME explanations approach their expected values. The bounds describe dependence on error tolerance, failure probability, and parameters of the sampling setting.

4. Convergence Analysis

  • The section derives finite-sample convergence bounds for both SmoothGrad and C-LIME to their expected explanations.For C-LIME, the stated theorem concerns f : R^d → [−1, 1] and Gaussian sampling with Σ = σ²I.Source: §4 · p. 4
  • For SmoothGrad, n ≥ C(∇f_max/ϵ)² ln(d/δ) samples suffices for convergence within ϵ with probability at least 1 − δ.The bound assumes a function with bounded gradient and holds for any covariance matrix Σ.Source: §4 · p. 4
  • For fixed σ² and x, the C-LIME sample-complexity bound scales as 1/ϵ² and ln(1/δ); it also grows as σ² or ∥x∥₂ approaches zero or becomes large.The text attributes the small-regime growth in the analysis to a bound on the inverse product matrices, and says large-variance growth matches the intuition that accurate estimates require more samples.Source: §4 · p. 5

5. Additional Properties

SmoothGrad and C-LIME satisfy linearity and proportionality under the stated conditions. These properties support composing explanations for linear combinations, but the methods generally do not produce sparse explanations.

5. Additional Properties

  • Both SmoothGrad and C-LIME are linear in the function being explained for a fixed covariance matrix.The explanation of a linear combination of functions is the same linear combination of their explanations.Source: §5 · p. 5
  • This linearity lets users derive explanations for linear compositions from previously computed explanations when computing them is expensive.The paper identifies this as useful for reducing the need to compute new explanations directly.Source: §5 · p. 5
  • For a linear underlying function, both methods produce explanations proportional to its weights, providing a sanity check for explainability methods.The paper contrasts this with Garreau & von Luxburg (2020), whose C-LIME multiplier may differ by feature.Source: §5 · p. 5
  • In general, SmoothGrad and C-LIME do not provide sparse explanations, including for non-sparse linear functions.The paper notes that sparsity can be promoted with a regularizer and studies regularized C-LIME in Appendix D.Source: §5 · p. 5

6. Experiments

Experiments on synthetic and real-world classification datasets examine equivalence and robustness as perturbation counts and other parameters vary. The observed distances decrease with more perturbations, while convergence is faster for SmoothGrad and for smaller perturbation variance.

6.1. Experimental Setup

  • The experiments use a simulated dataset and two UCI classification datasets, with continuous features normalized and perturbations sampled from N(x, σ2I).The real-world tasks are bankruptcy prediction and online-shopping purchase prediction; the datasets were chosen for their real-valued features.Source: §6.1 · pp. 5–6

6.2. Equivalence

  • Across all three datasets, the average L1 distance between SmoothGrad and C-LIME explanations decreases with more perturbations, with equivalence reached at as few as 100.This is fewer perturbations than the finite-sample estimates in the theory predict.Source: §6.2 · p. 6, Figure 2 · p. 6

6.3. Robustness

  • Across all three datasets, the average maximum distance approaches zero for both methods; SmoothGrad saturates closer to zero and faster, at about 200 perturbations.The authors interpret this as greater robustness for SmoothGrad at fixed finite perturbation counts.Source: §6.3 · p. 7, Figure 3 · p. 7

6.4. Sensitivity Analysis

  • On Bankruptcy, both methods reach equivalence and robustness faster with smaller σ2, while theory predicts more perturbations as σ2 approaches zero or becomes very large.The authors suspect this difference reflects worst-case bounds involving the inverse of a sampled covariance matrix, which can grow as σ2 approaches zero.Source: §6.4 · p. 7
  • On Bankruptcy, convergence slows when model accuracy falls from 96% to 86%.The comparison uses models trained for 60 and 16 epochs, respectively.Source: §6.4 · p. 7

7. Related Work

Related work spans inherently interpretable models and post hoc explanations, including local perturbation-based and gradient-based methods. Prior studies examine vulnerabilities and properties of post hoc methods, but the cited work does not explore deeper connections between these explanation classes.

7. Related Work

  • Inherently interpretable models include trees, lists, sets, prototypes, and generalized additive models, while post hoc explanations have drawn interest for complex models such as deep neural networks.The passage notes that complex models often achieve higher accuracy than simpler models (Ribeiro et al., 2016).Source: §7 · p. 7
  • Post hoc methods vary by model access, approximation scope, search technique, and explanation unit; local approaches include perturbation-based LIME and SHAP and gradient-based SmoothGrad.The cited work also includes counterfactual and global explanation approaches.Source: §7 · p. 8
  • Prior work raises reliability and robustness concerns and analyzes some methods theoretically, but does not explore deeper connections between perturbation- and gradient-based techniques.The passage cites concerns that explanations may be unfaithful or change with small input perturbations.Source: §7 · p. 8

8. Future Work

The paper identifies extensions to other explanation families as future directions. Its appendix derives closed forms for SmoothGrad and C-LIME and connects them by showing those expressions are equal.

8. Future Work

  • Future work could connect other perturbation- and gradient-based methods, relate them to counterfactual explanations, and extend analysis beyond feature attribution to rule- or prototype-based methods.The passage names SHAP and Integrated Gradients as examples for further study.Source: §8 · p. 9

A.1. Equivalence

  • The appendix derives closed-form expected outputs for SmoothGrad and C-LIME using Gaussian perturbations around the point being explained.For SmoothGrad, it invokes Stein’s Lemma; for C-LIME, it derives the linear least-squares solution.Source: §A.1 · p. 11

Connecting SmoothGrad and C-LIME

A.2. Robustness

A bounded function smoothed by Gaussian perturbations is Lipschitz, and the proof transfers this robustness result from SmoothGrad to C-LIME through their equivalence.

A.2. Robustness

  • If h is bounded by hmax, its Gaussian-smoothed function g is hmax/(2σ)-Lipschitz in L2.The proof applies this result to the gradient of f for SmoothGrad; the equivalence result gives C-LIME the same Lipschitz constant.Source: §A.2 · p. 12

B. Proofs of Section 4

The proofs establish finite-sample convergence for SmoothGrad and C-LIME by bounding their empirical outputs around their expectations. The C-LIME analysis controls separate terms and combines them with a union bound.

B.1. Convergence Analysis of SmoothGrad

  • SmoothGrad’s empirical output averages gradients sampled around x, and bounded gradients support a Chernoff-bound convergence argument followed by a union bound across dimensions.The proof states a per-dimension failure probability of at most δ/d before the union bound.Source: §B.1 · p. 12

Term 1

  • The denominator’s first term is the Gaussian covariance matrix’s smallest eigenvalue, σ², while its second term is the smallest eigenvalue of a rank-1 matrix, 0.Source: Term 1 · p. 13

Term 3

  • The matrix Bernstein inequality in the subexponential case gives a probability guarantee of at least 1 − δ/6 when n ≥ C ln(d/δ)/σ⁴.C is an absolute constant.Source: Term 3 · p. 14

B.2. Convergence Analysis of C-LIME

  • With probability at least 1 − δ, C-LIME’s empirical average is within ε in L2 of its expected output after the proof’s term bounds are combined.The proof combines the bounds using a union bound.Source: Term 3 · p. 14

C. Proofs of Section 5

The appendix proofs address linearity and proportionality, then derive a closed form for the regularized C-LIME explanation. The formula expresses the fitted explanation using an expectation and a covariance-adjusted input displacement.

C.1. Linearity

  • The proof of Proposition 2 invokes Theorem 1, but the supplied passage ends before stating what follows from that theorem or what Proposition 2 establishes.Source: §C.1 · p. 14

C.2. Proportionality

  • The proportionality proof reduces the claim to SmoothGrad and shows its gradient is a scalar multiple of the classifier’s coefficient vector at every input.The proof writes the gradient as k(x1, …, xd)(a1, …, ad).Source: §C.2 · pp. 14–15

D. Regularization

  • With L2 regularization, the C-LIME fit has a closed form combining the expected model output with a covariance-weighted displacement from x.The displacement term uses cov(f(a), a)(Σ + λI)⁻¹(a − x), with a drawn from N(x, Σ).Source: D. Regularization · p. 15

E. Additional Experimental Results

The additional figures plot equivalence and robustness for SmoothGrad and C-LIME across perturbation counts. They cover two datasets and, on the simulated data, functions with varying accuracy.

E. Additional Experimental Results

  • Figure 6 plots equivalence and robustness for SmoothGrad and C-LIME on the Simulated dataset across perturbation counts and σ² settings.Each plot uses L1 distance on the y-axis and number of perturbations on the x-axis.Source: Figure 6 · p. 16
  • Figure 7 plots equivalence and robustness for SmoothGrad and C-LIME on the Online Shopping dataset across perturbation counts and σ² settings.Each plot uses L1 distance on the y-axis and number of perturbations on the x-axis.Source: Figure 7 · p. 16
  • Figure 8 plots equivalence and robustness for SmoothGrad and C-LIME on the Simulated dataset using functions with varying accuracies.Each plot uses L1 distance on the y-axis and number of perturbations on the x-axis.Source: Figure 8 · p. 16
  • Figure 9 plots equivalence and robustness for SmoothGrad and C-LIME on the Online Shopping dataset using functions with varying accuracies.Each plot uses L1 distance on the y-axis and number of perturbations on the x-axis.Source: Figure 9 · p. 16

Related papers

Loading 2102.10618v4…