Interpreting Black Box Predictions using Fisher Kernels

1 Introduction

• The paper frames example-based interpretation as a route to more informed decision systems and better understanding of model behavior.Prior work cited by the authors motivates using examples to support human learning and understanding [15].Source: §1 · p. 1
• The authors provide convergence guarantees for greedy SBQ over discrete candidate sets and derive more scalable variants with constant-factor guarantees.They note that SBQ estimates an expected function value using discrete sample points.Source: §1 · p. 2
• The method selects salient training points to explain black-box test predictions and uses greedy SBQ to select a subset that approximates the test distribution in a model-induced space.The embedding uses Fisher kernels to quantify similarity under the trained model.Source: §1 · pp. 1–2
• The approach recovers influence-function interpretability as a special case and presents applications to three real-world use cases.The cited related work targets individual test predictions; selecting multiple points required an unmotivated heuristic extension.Source: §1 · p. 2

2.1 Fisher Kernels

• Fisher kernels map examples using gradients of log likelihood at fitted parameters, with the Fisher information matrix rescaling their dot product.The practical Fisher kernel drops this matrix, but the authors use the full kernel because dropping it significantly affected their method's performance.Source: §2.1 · pp. 2–3
• In the toy example, Fisher similarity accounts for labels and log-likelihood gradient direction, unlike the RBF comparison based on distance.The figure compares the closest and farthest 40 points to a selected green point under each similarity.Source: Figure 1 · p. 3

2.2 Bayesian Quadrature

• Bayesian quadrature estimates an expectation with a weighted sum of a few function evaluations; its Gaussian-process posterior supplies a mean and variance for the estimate.The weights can be non-uniform, and candidate points can be chosen to minimize posterior variance.Source: §2.2 · pp. 3–4
• SBQ greedily samples points to minimize posterior variance when computing an approximate integral.The notation defines the kernel matrix from pairwise kernel evaluations and weights from kernel evaluations against the distribution.Source: §2.2 · pp. 3–4

3 Prototype Selection using Fisher Kernels

• A Fisher-kernel Gaussian-process prior and SBQ select a weighted subset of training points to approximate the test or validation loss integral.The training samples need not have positive measure in the test distribution because the smoothening GP prior operates over the embedding space.Source: §3 · p. 4
• SBQ balances selecting points clustered in feature space, which reduces variance through z, against diversity, since nearby selections can increase variance.The tradeoff arises because nearby points decrease the eigenvalues of K−1.Source: §3 · p. 4

3.1 An Efficient Greedy Algorithm

• The implementation precomputes each training point’s kernel-similarity sum over the test set in O(nt) time and stores a vector of size t.Here, t is the training-set size and n is the test-set size.Source: §3.1 · p. 4
• The greedy algorithm updates the inverse kernel matrix using a block-matrix result, avoiding explicit inverses and requiring only kernel-oracle access.The algorithm is also described as inherently parallelizable over multiple cores.Source: §3.1 · pp. 4–5

4 Analysis

• For discrete candidate atoms, the forward greedy algorithm has a linear convergence rate; Theorem 2 also gives an alternative sufficient condition for exponential convergence when the optimum lies at the boundary.That condition uses a lower sparse-eigenvalue requirement over the greedy selection set plus any r-sized subset.Source: §4 · pp. 5–6
• Theorem 2 bounds v(SG)−v(S⋆) by ε(v(∅)−v(S⋆)) for the greedy set SG relative to the optimal set S⋆.The theorem states a condition on k; the convergence-rate discussion measures iterations to ε accuracy, with stochastic and distributed guarantees in expectation.Source: §4 · pp. 5–6

4.1 Scalability

• Standard SBQ may be too slow for massive datasets and requires an O(m^2) training-set kernel matrix; faster or distributed variants trade off convergence rate or distribute the kernel.The passage presents these variants with corresponding convergence rates.Source: §4.1 · p. 6

5.1 Choosing training data points

• For negative log-likelihood loss, the Hessian entries equal inner products of loss gradients, so first-order information suffices for the influence-function connection.The paper says this makes the Hessian calculation used by Koh and Liang [17] redundant in this setting.Source: §5.1 · p. 7
• With negative log-likelihood loss, influence-function selection is a special case of the Fisher-kernel problem for one test point and r = 1.The connection is based on the practical Fisher kernel.Source: §5.1 · p. 7
• The connection extends influence functions to multiple training and test points and gives theoretical approximation guarantees for selecting multiple training points.It also interprets the selection objective as minimizing Fisher-RKHS distance between a test point and a training point.Source: §5.1 · p. 7

5.2 Unified view of adversarial attacks

• With Fisher-RKHS distance as the objective and a training-example perturbation constraint, the training-side update is a projected-gradient step for the attack formulation.The paper frames this as a special case of projected gradient ascent.Source: §5.2 · p. 7
• The equivalence unifies training- and test-side attacks and provides a principled way to target multiple test examples rather than attacking them separately.The paper notes that methods for robustness to test-side attacks can also be applied to training-side attacks.Source: §5.2 · p. 8

6 Experiments

• The experiments use set influence for data cleaning and summarization, and evaluate the full Fisher kernel for fixing mislabeled examples.The paper presents these use cases to illustrate framework flexibility and generalization beyond influence functions.Source: §6 · p. 8

6.1 Data Cleaning: removing malicious training data points

• Removing selected MNIST points improved accuracy through Sel200, but Sel300 declined; random removal generally hurt, and Sel200 exceeded the manually curated 50-point set.The manually curated set was selected from the top 300 points based on how ill-formed the digits appeared.Source: §6.1 · p. 8, Figure 2 · p. 9

6.2 Fixing Mislabeled Examples

• On Enron1, the method consistently outperforms self-influence and random selection in test accuracy and the fraction of flipped labels fixed as curation proceeds.Figure 3 compares SBQ with influence functions for fixing flipped labels.Source: Figure 3 · p. 9, §6.2 · p. 10

6.3 Data Summarization

• Across ChemReact and CovType, Fisher selection achieves better test log-likelihood performance than random subsets and coresets at the same subset sizes.Figure 4 compares the methods across subset sizes and includes full-training-set performance.Source: §6.3 · p. 10, Figure 4 · p. 11

• The proof maps the problem to linear regression in the induced RKHS, equates greedy SBQ with forward feature selection, and uses discrete-optimization results for convergence guarantees.The posterior weight calculation corresponds to least-squares fitting on the selected features.Source: §A.1 · p. 13
• MMD measures divergence between distributions over a function class; restricting that class to an RKHS allows kernel-based evaluation.For the Bayesian-quadrature weights, the expected variance equals MMD squared between the target distribution and the weighted selected-point distribution.Source: §A.1 · p. 13
• Posterior-evaluation weights make the weighted feature sum the orthogonal projection of the target mean embedding onto the span of selected features.The resulting weight optimization is equivalent to minimizing squared MMD for the selected points.Source: §A.1 · pp. 13–14
• Greedy forward selection for λ-weakly submodular objectives has a (1 − 1/e^λ) approximation guarantee; here the weak-submodularity parameter depends on the kernel spectrum.The function is described as m/M-weakly submodular, with m and M determined by sparse eigenvalues.Source: §A.1 · p. 14
• Transferring the Euclidean regression result to a general RKHS requires bounded RKHS norms or bounded candidate-atom norms.Under those assumptions, the cited results translate to the general RKHS setting.Source: §A.1 · p. 14