Sample based Explanations via Generalized Representers
Authors: Che-Ping Tsai
Chih-Kuan Yeh
Pradeep Kumar Ravikumar
Venue: NeurIPS 2023 poster (2023)
Keywords: explainable machine learning
sample based explanation
representer point
TL;DR: We propose a general class of sample based explanations of machine learning models that satisfy a natural set of axiomatic properties.

Abstract: We propose a general class of sample based explanations of machine learning models, which we term generalized representers. To measure the effect of a training sample on a model's test prediction, generalized representers use two components: a global sample importance that quantifies the importance of the training point to the model and is invariant to test samples, and a local sample importance that measures similarity between the training sample and the test point with a kernel. A key contribution of the paper is to show that generalized representers are the only class of sample based explanations satisfying a natural set of axiomatic properties. We discuss approaches to extract global importances given a kernel, and also natural choices of kernels given modern non-linear models. As we show, many popular existing sample based explanations could be cast as generalized representers with particular choices of kernels and approaches to extract global importances. Additionally, we conduct empirical comparisons of different generalized representers on two image classification datasets.

Sample based Explanations via Generalized Representers
Che-Ping Tsai
Chih-Kuan Yeh Google Deepmind j jason65220gai1.. com
Pradeep Ravikumar Machine Learning Department Camnegie Mellon University pradeepr&cs. cmu. edu
Machine Learning Department Carnegie Mellon University chepingt@andres. cmu edu
Abstract
We propose general class of sample based explanations of machine learning models, which we term generalized representers. To measure the effect of a training sample
model's test prediction, generalized representers use two components: a global sample importance that quantifies the importance of the training point the model and invariant test samples, and local sample importance that measures similarity between the training sample and the test point with a kernel. A key contribution of the paper to show that generalized representers are the only class of sample based explanations satisfying a natural set of axiomatic properties. We discuss approaches extract global importances given kernel, and also natural choices of kernels given modern non-lineat models. As we show, many popular existing sample based explanations could be cast as generalized representers with particular choices of kernels and approaches to extract global importances. Additionally, we conduct empirical comparisons of different generalized representers two image and two text classification datasets.
Introduction
As machine learning becomes increasingly integrated into various aspects of human life, the demand for understanding, interpreting, and explaining the decisions made by complex AI and machine learning models has grown. Consequently, numerous approaches have been proposed in the field of Explainable AI (XAD). Feature based explanations interpret models by identifying the most relevant input features (114), while sample based explanations do so via the most relevant training samples ( Although different methods emphasize different aspects of the model, some may even have conflicting philosophies
( To address this issue, there have been growing calls within the which could help align XAI
XAI community for more objective or normative approaches (TO 12 techniques more effectively with human needs.
One of the most straightforward approaches to assess the effectiveness of explanations is by evaluating their utility in downstream applications [ [4] However, such evaluations be costly, particularly during the development stages of explanations, as they often necessitate the involvement of real human users. As result, well- grounded, axiom-based evaluation can be beneficial for designing and selecting explanations for implementation. Axioms can be viewed as theoretical constraints that dictate how explanations should behave in response specific inputs. A notable example is the Shapley value [15., which originated in cooperative game theory and has gained popularity XAI due to its appealing axiomatic properties. Nonetheless, while axiomatic approaches have been widely applied in identifying significant features 4 16 [i7], feature interactions [8] [9] and high-level
concepts (00. they have not been extensively discussed in sample based explanations.
WWok done in Carnegie Mellon Univerisity.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

In this work, we propose set of desirable axioms for sample based explanations. We then show that any sample based attributions that satisfy (a subset of) these axioms are necessarily the product of two components: a global sample importance, and a local sample importance that is a kernel similarity between a training sample and the test point. We term the explanations in this form generalized representers.
We note that the efficiency axiom (detailed in the sequel) can only be satisfied if the model function lies in the RKHS subspace spanned by the training kernel representers, which is indeed typically the case. Otherwise, we could ask for the smallest error in satisfying the efficiency axiom which can be cast as an RKHS regression problem. Thus, given kernel, extracting global importances can be cast as solving an RKHS regression problem, by recourse RKHS representer theorems [2I]. We additionally also propose tracking representers that scalably compute the global importance by tracking kernel gradient descent trajectories.
The class of generalized representers allow for the user to specify a natural kemel given the model they wish explain, perhaps drawn from domain knowledge. We discuss some natural automated choices given modern non-linear models. Specifically, we discuss the kernel with feature maps specified by last-layer embeddings, neural tangent kernels [22], and influence function kernels [5]. Many existing sample-based explanation methods such as representer point selection 7 and influence functions [5] can be viewed as specific instances of the broad class of generalized representers. As we show. TracIn [ could be viewed as a natural extension of generalized representers that uses multiple kernels, and computes multiple corresponding global and local importances. We empirically compare different choices of generalized representers for neural networks on two image and two text classification datasets.
1.1 Related work
Axiomatic attribution in XAI: The most common line of work that incorporates axioms in the design of explanations is the family of Shapley values [15]. that originates from cooperative game theory. This line of work first tackles the attribution problem by converting it into set value function and then applying the Shapley value. The Shapley value is widely used feature-based explanations 4 6 2 feature-interaction explanations [ [9 concept-based explanations 200
and sample-based explanations
[
We note that the axiomatic framework for sample-based explanations in data Shapley g
has distinct purposes and interpretations to ours. Generalized representers assess the significance of training samples with respect to specific test sample's prediction. In contrast, data Shapley assesses training sample importance via training loss and can be directly adapted to orginal Shapley value axioms. Consequently, while there are shared axiomatic principles between the two frameworks, the generalized representers require a different approach due to their additional focus on a specific test sample. We will delve into detailed comparison of these distinctions in Section S
Sample based explanations: Existing sample-basee based explanation approaches can be separated into retraining-based and gradient- approaches 24 Retraining-bused approaches are based on the measurement of the difference between a model prediction with and without a group of
training samples 8 25 [4] Gradient-based methods estimate data influence based similarities
between gradients. The majority of methods build upon the three theoretical frameworks, namely: (I) Representer theorems
7 35. (2) beasiann-bsed influence functions
[5] 3 and (3)
Decomposing the training loss trajectory 6 46 In this work, we show that most gradient-based methods can be viewed generalized representers.
Problem Definition
We consider the task of explaining supervised machine learning model f Rd + R. given inputs x E Rd, where d is the input dimension We are interested in explaining such models f() in terms of the training points D == {(4, y with each training sample (x4, y:) E Ød x R. We denote a sample explanation functional ΦD F D x Rdd + IR.. as a mapping that takes a real-valued
Note that we assume a single-die digeensoiii output for notational convenience. In the appendix, we show that development can be extended to valued outputs by using vector-output kernel functions.

---

model E F, training data points D, and an arbitrary test data point x E R as imput, and outputs vector of explanation weights (&D(f. (x), V1), x).......... @D (X,, Nn), x)] R" with each value corresponding to an importance score of each training sample to the test point. In the sequel, we will suppress the explicit dependence on the entire set of training points in the notation for the explanation functional and the dependence on the training label V/- Also, to make clear that the first data point
argument is the training sample, and the second the test sample, we will use of X; + x) E IR to denote the sample explanation weight for to explain the prediction of the model f(-) for the test point x.
Axioms for Sample based Explanations
In this section, we begin by presenting collection of axioms that describe various desirable charac- teristics of sample based explanations.
Definition 1 (Efficiency Axiom), For any model f, and test point æ E , sample based explanation <(+) salisfies the efficiency axiom iff:
Σ
The efficiency axiom entails that the sum of the attributions to each training sample together adds up the model prediction at the test point. This a natural counterpart of the efficiency axioms used in the Shapley values 40
Definition 2 (Self- Exlf-Exxlanntion Axiom). A sample based explanation Φ(.) satisfies the self-explanation axiom iff there exists any training point x; having no effect itself. i.e. Φlf, x,) 0, the truining point should not impact any other points, i.e. $b x; x) = 0 for all x E RR.
The sellaaxxlnnntion axiom states that if the label y/8 does not even have an impact on the model's prediction for x, it should not impact other test predictions. This axiom shares a similar intuition as the dummy axiom in the Shapley values [15] since both axioms dictate that explanations should be zero if training sample has impact the model. However, the self-explanation axiom requires different theoretical treatments due to the additional focus in generalized representers of explaining a model prediction
particular test sample.
Definition 3 (Symmetric Zero Axiom). A sample explanation 6(-) satisfies the symmetric zero axiom iff any two training points x,, Xj such that if o(f, x;
+ x;) * 0 and @(f,x; + +x,) # 0, then
$(ʃ, x; + x,) = < , -x)
The symmetric-zero axiom underscores the bidirectional nature of "oothogonaalty". It emphasizes that if a sample has no impact on another sample, this lack of correlation is mutual and implies that they orthogonal.
Definition 4 (Symmetric Cycle Axiom). A sample explanation o(-) satisfies the symmetric cycle axiom isf for any set of training points Xty: Nio with possible duplicates, and Xtx Xxy it holds that:
II olf + x
II (f Xt..i x...
Let us first consider the vacuous of two points: X1, X2, for which the axiom is the tautology that: o(f,xi x1 + x2)0(f,x X2 + xi) = Φ(f, x2 + xi ())o(f.x + X2). Let us next look at the case with three points: X1, X2, X3, for which the axiom entails:
o(f.x x2)x - xx)o(f.x; + +11) = x2)o(f.x; + xi)o(fxxı - +x3)
It can be seen that this is generalization of simply requiring that the explanations be symmetric as the symmetry axiom the Shapley values. fact, the unique explanation satisfying this and other listed axioms is in general not symmetric. The axiom could also be viewed as a conservation or path independence law, in that the flow of explanation based information from a point x; to itself in cycle is invariant to the path taken.
3

---

Definition 5 (Continuity Axiom). A sample based explanation o(-) satisfies the continuity axiom iff is continuous wrt the test data point x. for any fixed training point X,
lim @U, x; - x') = &[J, - -)). x x
Such continuity is a minimal requirement on the regularity of the explanation functional, and which ensures that infinitesimal changes to the test point would not incur large changes the explanation functional.
Definition 6 (Irreducibility Axiom). sample explanation 6(-) satisfies the irreducibility axiom iff
for any number of training points X1. .... Xk.
x1) @ X1)
x(fxx1,22)
xf,
((f,x2,
off,x2,
del
2 0.
((, Xk. x1)
Φ(ʃ, X2)
@lf, Xk, xx)
sufficient condition for an explanation 66.) to satisfy the irreducibility axiom is for
lø(f, x; + x,)1 Σ
10 + +x,]1
since this makes the matrix above strictly diagonally dominant, and since the diagonal entries are non-negative, by the Gershgorin circle theorem, the eigenvalues are all non-negative as well, so that the determinant in turn is non-negative.
The continuity and irreducibility axiom primarily serves a funetion-analytic purpose by providing sufficient and necessary conditions of kernel being Mercer kernel, which requires that the kernel function be continuous and positive semi-definite
We now ready investigate the class of explanations that satisfy the axioms introduced above. Theorem 7. An explanation functional .(f...) satisfies the contimuity, relf-explanation, symmetric zero. symmetric cycle, and irreducibility axioms for any training samples D containing n training samples (x,, y.) E Rd x for all E [m]] iff
o(Sx; - x) = Kx(xx, Vi E [n].
for some R and some continuous positive-definii definite kernel K Rd x Rd R R.
This suggests that a sample explanation dff, x; x) a, (x,, x) has two components: a weight Og associated with just the training point x; independent of test points, and similarity K(x;, x) between the training and test points specified by a Mercer kernel. Following Yeh et al. [7). we term the first component the global importance of the training sample and the second component the local importance that measures similarities between training and test samples.
Once we couple this observation together with the efficiency axiom, one explanation that satisfies these properties is:
f(x) Σ Ed(sx: + xx 5=1
Σ a.KK <x,(X;; x) for any IR.
This can be seen to hold only if the target function I lies in the RKHS subspace spanned by the kernel evaluations of training points. When this is not necessarily the case, then the efficiency axiom (where the sum of training sample importances equals the function value) exactly, cannot be satisfied exactly, We can however satisfy the efficiency axiom approximately with the approximation error arising from projecting the target function ff onto the RKHS subspace spanned by training representers.
This thus provides very simple and natural framework for specifying sample explanations: (1) specify Mercer kernel K (...) so that the target function can be well approximated by the corre- sponding kernel machine, and (2) project the given model onto the RKHS subspace spanned by kernel evaluations on the training points. Each of the sample explanation weights then has a natural specification in terms of global importance associated with each training point (arising from the projection of the function onto the RKHS subspace, which naturally does not depend on any test points), as well as a localized component that is precisely the kernel similarity between the training and test points.

---

4 Deriving Global Importance Given Kernel Functions
The previous section showed that the class of sample explanations that satisfy a set of key axioms naturally correspond to an RKHS subspace. Thus, one needs, order to specify the sample explanations, is to specify Mercer kernel function K and solve for the corresponding global importance weights a. In this section, we focus on the latter problem, and present three methods to compute the global importance weights given some kernel K.
4.1 Method I: Projecting Target Function onto RKHS Subspace
The first method is to project the target function onto the RKHS subspace spanned by kernel evaluations on the training points. Given the target function f. loss function L R R + I and training dataset D = {(x; V/ )i= (potentially, though not necessarily used to train f), and user-specified Mercer kernel K, our goal is to find a projection fx of the target model onto the RKHS subspace defined by Hn = span( {K (x,,)) +)]=))) To accomplish this, we formulate it as a RKHS regression problem:
A
fx = argmin
Σ f(x.)) + ll
(4)
EKH
where Hx as the RKHS defined by kernel K. || || : Hx + TR is the RKHS norm, and À is regularization parameter that controls the faithfulness and complexity of the function fx. The loss function L can be chosen as the objective function used to train the target function f to closely emulate the behavior of target function f and its dependence on the training samples D. By the representer theorem [1], the regularization term ||5x< added here ensures that the solution lies in the RKHS subspace Hi, spanned by kernel evaluations. Indeed, by the representer theorem 21I, the minimizer of Eqn. can be represented fx(+) Ei= a; a;K((s;;) (Xx: for some R", which allows us to reparameterize Eqn. 4
A TaT Taa }
n
â argmin a
C
Σ a (ayK((xa xx),
+ 2
(5)
n
where K Raxn is the kernel gram matrix defined Kij K (x,;))) for i.j E [n]. and x;)) (xxK((;;)))
use the fact that || = (E a; (x,, Em= a;
Va To. By solving the
first-order optimality condition, the global importance must be in the following form:
Proposition 8. (Surrogate derivative) The minimizer of Eqn. can be represented as fK E .xx,,,,)), where
â E (a' +o null(K)) and of 1 (c(f Vi E [m].
(6)
nd 0fx(xx)
We call of the surrogate derivative since is the derivative of the loss function with respect to the surrogate function prediction.
af can be interpreted as the measure of how sensitive fx is changes in the loss function. Although the global importance a solved via Eqn. may not be unique as indicated by the above null(K)} result in the same
results, the following proposition ensures that all a E {a* surrogate function fx = Σi a; K(x;.))
Proposition 9. For any null(K), the function J = E V2 K ((x,,) specified by the span of kernel evaluations with weights a zero fucntion, such that fx(x) 0.ror all Rdd
The proposition posits that adding any e E null(K) to a" has no effect on the function fx. Therefore, we use a" to represent the global importance captures the sensitivity of the loss function the prediction of the surrogate function.
5

---

We note that one can draw from standard correspondences between gradient descent with finite stopping and ridge regularization (e.g. [50]), to in turn relate the iterates of the kernel gradient descent updates for any finite stopping at T iterations to regularized RKHS regression solutions for some penalty A. The above procedure thus provides a potentially scalable approach to compute the 4.2 Method 2: Approximation Using the Target Function
Given the derivation of global importance weights a" in Eqn. 6 we next consider a variant replacing the surrogate function prediction fx (xs) with the target function prediction fxx;): Definition 10 (Target derivative). The global importance computed with derivatives of the loss function with respect to the target function prediction is defined as:
(z)) Vi Vi [n],
of
0f(z))
where C(.-) is the loss function used train the target function.
crucial advantage of this variant that we no longer need solve for an RKHS regression problem. There are several reasons why this approximation is reasonable. Firstly, the loss function in Eqn. D
encourages the surrogate function to produce similar outputs as the target function, so that fx (x;) approximately equal to fx;).. Secondly, when the target function exhibits low training error, which is often the case for overparameterized neural networks that typically in interpolation regime, we can assume that fxx) is close to yı- Consequently, the target derivative can serve as an approximation of the surrogate derivative in Eqn. As will show below, the influence function approach [ is indeed as the product between the target derivative and the influence function kernel.
4.3 Method Tracking Gradient Descent Trajectories
Here, we propose more scalable variant we term tracking representers that accumulates changes in the global importance during kernel gradient descent updates when solving Eqn.
Let $ : IR + H be feature map corresponding to the kernel K, so that ((x, x') (Ø(x), @ (x')). We can then cast any function the RKHS as (x) = (0, (())) for some parameter E H. Suppose we
solve the unregularized projection problem in Eqn. 4 via stochastic gradient descent updates on the
parameter 8: g(t) ((-
[ ΣiEBO) ff (x 0= where we use ((t)
((
and (9) to denote the minibatch and the learning rate. The corresponding updates to the function is then given by "kernel gradient descent" updates: fk (x) (x) fk -it-1) (x) (x,,(,,)),, where
n0 |888
EVEBOO
acc (x)))xxxx)x)))) The function at step T can then be represented as:
au
05k 01(111()))
DC(st--1) 11 (xx:) ((x)) T
aciSK
fK (T) (x) Σ (T) K(x,, x) JK (0) (x) with 0j (7= Σ
(8)
B
Dfk-1((x
tHE B(S)
Definition 11 (Tracking representers). Given a finite set of steps T. we term the global importance weights obtained via tracking kernel gradient descent tracking representers:
n1()
aLIK (CC (xx),
of
Σ
a (1-1)) (x))))(()))
BE
corresponding global importances: in order to calculate the global importance a; (T). we need to
simply monitor the evolution of (t) when the sample x; is utilized at iteration t. In our experiment, we use the following relaxation for further speed up:
(1 OC(F(t-2) (x)), BOJ
Σ
(10)
-x(:))(xx))
(E
where we assume the target model is trained with (stochastic) gradient descent, (x;) denotes the target model at tth iteration during training, and B(O) and 17(*) are the corresponding mini-batch and learning rate. Similar to the intuition of replacing the surrogate derivative with to target derivative, we track the target model's training trajectory directly instead of solving Eqn. with kernel gradient descent.

---

Choice of Kernels for Generalized Representers
Previously, we discussed approaches for deriving global importance given user-specified kernels, which can in general be specified by domain knowledge relating to the model and the application domain. In this section, we discuss natural choices of kernels for modern non-linear models. Moreover, we show that existing sample based explanation methods such representer points 7 and influence functions representers. We also discuss TracIn than single kernel.
[ could be viewed as making particular choices of kernels when computing general natural extension of our framework to multiple rather
6
5.1 Kernel 1: Penultimate-layer Embeddings
A common method for extracting a random feature map from neural network is to use the embed- dings of its penultimate layer 52 Let &e, TRd RR denote the mapping from the input to the second last layer. The target model f can be represented as
f(x) = t9, (x) T
(11)
where O2 E Re is the weight matrix of the last layer. That is, we treat the deep neural network as linear machine on top of learned feature map. The kernel function is then defined as (x, z) =
(#e, (x), & (z)), vx, E Rd. This is the case with most deep neural network architectures, where the feature map &e. is specified via deep compositions of parameterized layers that take the form of fully connected layers, convolutional layers, or attention layers among others. While the last-layer weight matrix 2₂ may not lie in the span of (Po, (x:)) 1=1- we may solve the its explanatory surrogate function using Eqn. 44.
Corollary 12. (Representer point selection (Z]) The minimizer of Eqn. 4 instantiated with (x)(x,) (De, (x), L (z)), Vx, z Rd, can be represented as
1 aL(fk(x)) (x:) fx(-) = Σ aeKin(xss)) where as nd 0fk(x,)
"
Vi [n].
(12)
1=1
The above corollary implies that O₂ = Σ.= a; 0g (x:). other words, the RKHS regularization
Eqn. can be expressed as [| 1 11@211 which is equivalent L,2 regularization. Conse-
quently. the representer point selection method proposed in Yeh et al. ? can be generalized to our framework when we use last-layer embeddings as feature maps.
5.2 Kernel 2: Neural Tangent Kernels
Although freezing all layers except for the last layer a straightforward way to simplify neural networks to linear machines, last-layer representers may overlook influential behavior that is present in other layers. For example, Yeh et al. (53) shows that representation in the last layer leads to inferior results for language models. On the other hand, neural tangent kernels (NTK) 22 have been demonstrated as more accurate approximation of neural networks (54/566) By using NTKs, we use gradients with respect model parameters feature maps and approximate neural networks with the corresponding kernel machines. This formulation enables us to derive a generalized representer that captures gradient information of all layers.
For a neural network with scalar output fe Rd + R parameterized by a vector of parameters 0 e I2,, the NTK is kernel K Rd x Rd + I defined by the feature maps (x 8fa(x),
00
ONTK,O(x,7) (x = 10 Of((z)
(13)
00
00
Connection to TracIn 66: TracIn measures the change in model parameters from the start to the end of training. While is intractable due the need to store model parameters of all iterations, Pruthi et al. [6] used cCeckpoints(CP) a practical relaxation: given model parameters ((1) and learning rates (1)) all model checkpoints t O.... ,T, the formulation of TracInCP is given
7

---

below
7
(1) (xx))) Ua)
fff(x))
TTaclaC (x), - x) =
00
00
18=01)
1=0
(1))
K NTK. (x;,
(14)
@fo(x:)
0000
local importance
global importance
When the learning rate constant throughout the training process, TracInCP can be viewed generalized representer instantiated with target derivative as global importances and NTK (Eqn. (I3)
as the kernel function, but uses different kernels on different checkpoints.
5.3 Kernel 3: Influence Function Kernel
The influence functions kernel:
can also be represented as a generalized representer with the following
(x) (fe(z)
(x)
Of6(z)
K (x, 2)
(15)
00
0e
00
00
H1*
where Ho 1 E 8 ((). the Hessian matrix with respect to target model parameters. 802
n The influence function then can be written as:
Jnn (x)) - x) (x ve)
00 Hg 1 0,((())
(c(So(xs). 8K)
Kint, (x,, x)
(16)
00
Ox((x;))
local importance
global importance
Therefore, the influence function can seen as a member generalized representers with target derivative global importance (Definition TO and the influence function kernel. Influence func- tions [57] were designed to measure how would the model's 's predictions change if training input perturbed for convex models trained with empirical risk minimization. Consequently, the inversed Hessian matrix describes the sensitivity of the model parameters in each direction.
6 Experiments
In the experiment, we compare different representers within our proposed framework on both vision and language classification tasks. We use convolutional neural networks (CNN) since they are widely recognized deep neural network architectur. We compare perforamnce of different choices of kernels and different ways to compute global importance. Existing generalized representers, such as influence functions [ representer point selections [53 and TracIn 6 are included in our experiment.
6.1 Experimental Setups
DEL (x, k. Φ). as our primary evaluation metric. The metric measures the difference between models' prediction score on x when we remove top-k negative impact samples given by method á and the prediction scores of the original models. We expect DEL_ to be positive since models' prediction scores should increase when remove negative impact samples. To evaluate deletion metric at different k, we follow Yeh et al. 53 and report area under the curve (AUC): AUC-DEL_ = >n DEL (x, kú Q) m, where k < k2 < ... < km is predefined sequence of k.
Evaluation metrics: We use case deletion diagnostics 53 53.
57
58
We choose i; 0.02in for i 1.. with n as the size of the training set. The average of each metric is calculated across 50/200 /200 randomly initialized neural networks for vision/language data. For every neural network, sample-bass based explanation methods are computed for 10 randomly selected testing samples.
We replace the loss function on the test point ((f(x), y) with the target function prediction f(x) to measure training point influence the predictions.

---

Datasets and models being explained: For image classification, we follow Pruthi et al. G and use MNIST 59 and CIFAR-I0 10 160] datasets. For text classification, follow Yeh al. 5 and use Toxicity and AGnews I datasets, which contain toxicity comments and news of different categories respectively. Due to computational challenges in computing deletion diagnosties, we subsample the datasets by transforming them into binary classification problems with each class containing around 6, 000 training samples. The CNNs we use for the four datasets comprise 3 layers. For vision datasets, the models contain around 95, 000 parameters. For text datasets, the total number of parameters in the model is 1, 602, 257 with over 90% of the parameters residing in the word embedding layer that contains 30, 522 trainable word embeddings of dimensions 48. Please refer to the Appendix C for more details on the implementation of generalized representers and dataset constructions.
Datasets
Methods
Experiment 1- Comparison different global importance for generalized representers
Kemeess
NTK final
Random
Global importance
surrogate derivative
target derivative
tracking
Selection
MNIST CIFAR-10 10
1.88 0.25 2.27 + 0.18
0.30
2.81 + 0.20
3.26
0.19
0.136 +: 0.10
Toxicity
1.10 +: 0.21
2.08
0.23
0.15 + 0.19
AGnews
1.88 +: 0.27
2.56
0.27
0.19 + 0.26
Experiment Comparison different kernels for generalized representers
Global importance
tracking
Kernels
last final-final
NTK init
NTK midkle
NTK final
Inf final
MNIST
3.18 + 0.46
0.49
3.52 + 0.48
0.49
CIFAR-10
2.26 + 0.13
1.35 = 0.20
2.67 0.19
3.26 = 0.19
3.46 0.19
Toxicity
1.34 0.22
0.63 +: 0.22
1.90 0.23
2.08 0.23
0.42 + 0.20
AChnww
0.27
2.56
0.92 0.261
Experiment Comparison
generalized representers
Existing gencralized representers
Novel generalized representers
Methods
Infiuence function
Representer ?
NTK-final (tracking)
Inf-final (tracking)
TracInCP
MNITT CIFAR 10
4.20
0.52
2.36 0.32
2.51 0.30
3.52 + 0.48
3.66 0.49
2.84
0.20
3.02 0.21
1.65 1 0.19
3.26 1. 0.19
3.48 0.19
Toxicity
1.59 = 0.23
0.26 0.20
0.37 4: 0.19
2.08
0.23
0.42 0.20"
AGinews
2.18
0.27
0.75 0.26
0.86
0.25
2.56 0.27
0.92 0.26"
Table I: Case deletion diagnostics, AUC-DEL.., for removing negative impact training samples
on four different datasets. 95% confidence interval of averaged deletion diagnostics on 50 10- 500( or 200 x 10 = 2000) samples is reported for vision (or language) data. Larger AUC-DEL- is better. Init, middle, and final denote initial parameters (((), parameters of a middle checkpoint (TT/2), and final parameters ((T) for neural networks trained with T epochs. tWe only use the last-layer parameters compute influence functions as in [ 53 since the total number of parameters too large for text models.
6.2 Experimental Results
The results are shown in Table We also provide deletion curves we compute AUC-DEL.. for in the Appendix.
I. Comparison of different global importance: In the first experiment, fix the kernel to be the NTK computed on final model parameters, and we compare different methods for computing global importance in Section 말 We do not compute the surrogate derivative the text datasets since the total numbers of parameters are too large, making the computation infeasible.
http://groups. di. http://rroopoo..uiiir...ttee///a httppp/ttgggttll//lleea corpus_oouucooeee wtw.:uuooooooooooiiaeeeeee.e html

---

We observe that tracking has the best performance, followed by targer derivative and then surrogate derivative. This could be due to the loss flattening when converged and the loss gradients becoming less informative. Consequently, accumulating loss gradients during training is the most effective approach. Moreover, if tracking is not feasible when training trajectories are not accessible, we may use larger derivafive instead of surrogate derivative as an alternative to explain neural networks since they have similar performance.
II. Comparison of different kernels: Next, we fix the global importance tracking and compare different kernels in Section D We employ the tracking representers to compute global importance since it showed the best performance in the previous experiment. We can see that the influence function kernel performs the best in the vision data sets, and the NTK-final kernel has the best performance language data sets. Note that influence functions exhibit distinctly contrasting performances on image and text data, which could be attributed to our reliance solely on last-layer parameters for influence function computation on language datasets. This finding aligns with the conclusions of Yeh et al. [53], who suggest that the last layer gradients provide less informative insights for text classifiers.
In summary, these findings indicate that NTK-final is a dependable kernel selection due to its consistent high performance across all four datasets, while also offering a computational efficiency advantage over the influence function kernel. These results also demonstrate that accessing target model checkpoints for computing kernels unnecessary since NTK and influence function on the final model already provide informative feature maps.
III. Comparison of different generalized representers: Finally, we compare the new generalized representer with other existing generalized representers. We categorize TracInCP, the influence function, and the representer point as existing generalized representers: TracInCP can be viewed as an ensemble of generalized representers with target derivatives using the Neural Tangent Kernel. The influence function can be expressed as the influence function kernel with the target derivative. Lastly, the representer point can be seen form of generalized representer that utilizes the last-layer kernel and the surrogate derivative.
We find that the Inf-final has comparable performance TracInCP and they outperform other approaches. Although TracInCP has the best performance on MNIST, requires accessing different checkpoints, which requires significant amount of memory and time complexity. In contrast, the NTK and Inf tracking representers are more efficient since they only require tracking gradient descent trajectories during training without the need for storing checkpoints.
Conclusion and Future work
In this work, we present generalized representers that are the only class of sample based explanations that satisfy set of desirable axiomatic properties. We explore various techniques for computing generalized representers in the context modern non-linear machine learning models and show that many popular existing methods fall into this category. Additionally, we propose tracking representers that track sample importance along the gradient descent trajectory. In future work, it would be of interest to derive different generalized representers by altering different global importance and choices of kernels, as well as investigating their applicability to diverse machine learning models and modalities.
8 Acknowledgements
We acknowledge the support of DARPA via FA8750-23-2-1015 ONR via N00014-23-1-2366, and NSF via IIS- 110-1909..6.
References
[1] Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. Why should trust you?: Explaining the predictions of any classifier. In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, pages 1135-1144, ACM, 2016.
10

---

[2] Ramprasaath R Selvaraju, Michael Cogswell, Abhishek Das, Ramakrishna Vedantamand, Devi Parikh, and Dhruv Parikh. Grad-cam: Visual explanations from deep networks via gradient- based localization. International conference on computer vision, 2017.
[3] Daniel Smilkov, Nikhil Thorat, Been Kim, Fernanda Viégas, and Martin Wattenberg. Smooth- grad: removing noise by adding noise. arXiv preprini 17X6.v/700.038255 2017.
[4] Scott Lundberg and Su-In Lee. A unified approach to interpreting model predictions. In Advances in Neural Information Processing Systems, pages 4765-4774, 2017.
[5] Pang Wei Koh and Percy Liang. Understanding black-box predictions via influence functions. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pages 1885-1894. JMLR. org, 2017.
[6] Garima Pruthi, Frederick Liu, Satyen Kale, and Mukund Sundararajan. Estimating training data influence by tracing gradient descent. Advances in Neural Information Processing Systems, 33, 2020.
[7] Chih-Kuan Yeh, Joon Kim, lan En-Hsu Yen, and Pradeep K Ravikumar. Representer point selection for explaining deep neural networks. In Advances in Neural Information Processing Systems, pages 9291 1-9301, 2018.
[8] Amirata Ghorbani and James Zou. Data shapley: Equitable valuation of data for machine learning. In International Conference on Machine Learning, pages 2242-2251. PMLR, 2019.
[9] Satyapriya Krishna, Tessa Han, Alex Gu, Javin Pombra, Shahin Jabbari, Steven Wu, and Himabindu Lakkaraju. The disagreement problem in explainable machine learning: A practi- tioner's perspective. arXiv preprint arXiv:2202.01602, 2022.
[10] W James Murdoch, Chandan Singh, Karl Kumbier, Reza Abbasi-Asl, and Bin Yu. Definitions, methods, and applications in interpretable machine learning. Proceedings of the National Academy of Sciences, 1 166(44)220711222008
2019.
[11] Finale Doshi-Veles and Been Kim. Towards a rigorous science of interpretable machine learning. arXiv preprint arXiv: htt::/722 770.00868, 2017.
[12] Blair Bilodeau, Natasha Jaques, Pang Wei Koh, and Been Kim. Impossibility theorems for feature attribution. arXiv preprint 2rX1::2212.11170, 2022.
[13] Valerie Chen, Nari Johnson, Nicholay Topin, Gregory Plumb, and Ameet Talwalkar. Use-case- grounded simulations for explanation evaluation. arXiv preprint arXiv:2206.0223 022556 2022.
[14] Kasun Amarasinghe, Kit T Rodolfa, Sérgio Jesus, Valerie Chen, Vladimir Balayan, Pe- dro Saleiro, Pedro Bizarro, Ameet Talwalkar, and Rayid Ghani. On the importance of application-grounded experimental design for evaluating explainable ml methods. arXiv preprint arXiv:2206. 13503, 2022.
[15] Lloyd S Shapley. A value for n-person games. Contributions to the Theory of Games, 2(28): 307-317, 1953.
[16] Mukund Sundararajan, Ankur Taly, and Qiqi Yan. Axiomatic attribution for deep networks, In International Conference on Machine Learning. 2017.
[17] Chih-Kuan Yeh, Cheng- Yu Hsieh, Arun Suggala, David I Inouye, and Pradeep K Ravikumar. On the (in) fidelity and sensitivity of explanations. Advances in Neural Information Processing Systems, 32, 2019.
[18) Che-Ping Tsai, Chih-Kuan Yeh, and Pradeep Ravikumar. Faith-shap: The faithful shapley interaction index. Journal of Machine Learning Research, 24(94):1-42 2023.
[19] Mukund Sundararajan, Kedar Dhamdhere, and Ashish Agarwal. The shapley taylor interaction index. In International Conference on Machine Learning, pages 9259-9268 PMLR, 2020.

---

[20] Chih-Kuan Yeh, Been Kim, Sercan Arik, Chun-Liang Li, Tomas Pfister, and Pradeep Ravikumar. On completeness-awee aware concept-base based explanations in deep neural networks. Advances in Neural Information Processing Systems, 33:20554- 20565, 2020.
[21] Bernhard Schölkopf, Ralf Herbrich, and Alex Smola. A generalized representer theorem. In International conference on computational learning theory, pages 1166-226. Springer, 2001.
[22] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. Advances in neural information processing systems, 31, 2018.
[23] Scott M Lundberg, Gabriel G Erion, and Su-In Lee. Consistent individualized feature attribution for tree ensembles. arXiv preprint 1.XXiv:802.033000 2018.
[24] Zayd Hammoudeh and Daniel Lowd. Training data influence analysis and estimation: A survey. arXiv preprint wtXiv:2212.046122 2022.
[25] Tianhao Wang and Ruoxi Jia. Data banzhaf: A data valuation framework with maximal robustness to learning stochasticity. arXiv preprint 4rXiv:2205.15466, 2022.
[26] Andrew Ilyas, Sung Min Park, Logan Engstrom, Guillaume Leclerc, and Aleksander Madry. Datamodels: Predicting predictions from training data. arXiv preprint arXiv:2202.00622, 2022.
[27] Yongchan Kwon and James Zou, Beta shapley: a unified and noise-reduced data valuation framework for machine learning. arXiv preprint arXiv:2 / 10.14099, 2021.
[28] Tom Yan and Ariel D Procaccia. you like shapley then you 'll love the core. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 5751-5759, 2021.
[29] Chiyuan Zhang, Daphne Ippolito, Katherine Lee, Matthew Jagielski, Florian Tramèr, and Nicholas Carlini. Counterfactual memorization in neural language models. arXiv preprint arXiv:2112. 12938, 2021.
[30] Ziheng Jiang, Chiyuan Zhang, Kunal Talwar, and Michael C Mozer. Characterizing structural regularities of labeled data in overparameterizee models. arXiv preprint arXiv:2002.03206, 2020.
[31] Ruoxi Jia, Fan Wu, Xuehui Sun, Jiacen Xu, David Dao, Bhavya Kailkhura, Ce Zhang, Bo Li, and Dawn Song. Scalability vs. utility: Do we have to sacrifice one for the other data importance quantification? In Proceedings of the IEEF/CVF Conference on Computer Vision and Pattern Recognition, pages 8239-82477 2021.
[32] Jinsung Yoon, Sercan Arik, and Tomas Pfister. Data valuation using reinforcement learning. In International Conference on Machine Learning, pages 10842-10851. PMLR, 2020.
[33] Amirata Ghorbani, Michael Kim, and James Zou. A distributional framework for data valuation. In International Conference on Machine Learning, pages 3535-3544, PMLR, 2020.
[34] Ruoxi Jia, David Dao, Boxin Wang. Frances Ann Hubis, Nick Hynes, Nezihe Merve Gürel, Bo Li, Ce Zhang, Dawn Song, and Costas Spanos. Towards efficient data valuation based on the shapley value. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1167-1176. PMLR, 2019.
[35] Yuanyuan Chen, Boyang Li, Han Yu, Pengcheng Wu, and Chunyan Miao. Hydra: Hypergradient data relevance analysis for interpreting deep neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 7081-7089, 2021.
[36] Yi Sui, Ga Wu, and Scott Sanner. Representer point selection via local jacobian expansion for post-hoc classifier explanation of deep neural networks and ensemble models. Advances in neural information processing systems, 34:23347-23358, 2021.
[37] Jonathan Brophy, Zayd Hammoudeh, and Daniel Lowd. Adapting and evaluating influence- estimation methods for gradient- decision trees. arXiv preprint arXiv:2205.00:3 2022.
12

---

[38] Sung Min Park, Kristian Georgiev, Andrew Ilyas, Guillaume Leclere, and Aleksander Madry. Trak: Attributing model behavior at scale. arXiv preprint arXiv:2303.44186, 2023.
[39] Andrew Silva, Rohit Chopra, and Matthew Gombolay. Cross-loss influence functions to explain deep network representations. In International Conference on Artificial Intelligence and Statistics, pages 1-17. PMLR, 2022.
[40] Andrea Schioppa, Polina Zablotskaia, David Vilar, and Artem Sokolov. Scaling up influence functions. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 8186, 2022.
[41] Rui Zhang and Shihua Zhang. Rethinking influence functions of neural networks in the over-parameterized regime. In Proceedingy of the AAAI Conference on Artificial Intelligence, volume 36, pages 9082-9090, 2022.
[42] Samyadeep Basu, Philip Pope. and Soheil Feizi. Influence functions in deep learning are fragile. arXiv preprint arXiv:2006. 14651, 2020.
[43] Han Guo, Nazneen Fatema Rajani, Peter Hase, Mohit Bansal, and Caiming Xiong. Fastif: Scalable influence functions for efficient model interpretation and debugging. arXiv preprini arXiv:2012. 15781, 2020.
[44] Elnaz Barshan, Marc-Etienne Brunet, and Gintare Karolina Dziugaite. Relatif: Identifying explanatory training samples via relative influence. In International Conference on Artificial Intelligence and Statistics, pages 1999-1909. PMLR, 2020.
[45] Samyadeep Basu, Xuchen You, and Soheil Feizi. On second-order group influence functions for black-box predictions. In International Conference on Machine Learning, pages 715-724.
PMLR, 2020.
[46] Hugo Thimonier, Fabrice Popineau, Arpad Rimmel, Bich-Liên Doan, and Fabrice Daniel. Tracinad: Measuring influence for anomaly detection. In 2022 International Joint Conference on Neural Networks (IJCNN), pages 1-6. IEEE, 2022.
[47] Satoshi Hara, Atsushi Nitanda, and Takanori Maehara. Data cleansing for models trained with sgd. Advances in Neural Information Processing Systems, 32, 2019.
[48] Maximilian Mozes, Tolga Bolukbasi, Ann Yuan, Frederick Liu, Nithum Thain, and Lucas Dixon. Gradient-based automated iterative recovery for parameter-efficient tuning. arXiv preprint arXiv:2302.06599 2023.
[49] Lloyd S. Shapley. A value for n-person games, page 31-40. Cambridge University Press, 1988. doi: 10.1017/CB0978051522222 15274446611184440000
[50] Arun Suggala, Adarsh Prasad, and Pradeep K Ravikumar. Connecting optimization and regularization paths. Advances in Neural Information Processing Systems, 31, 2018.
[51] Jachoon Lec, Yasaman Bahri, Roman Novak, Samuel S Schoenholz, Jeffrey Pennington. and Jascha Sohl-Dickstein. Deep neural networks as gaussian processes. arXiv preprint 17X1v:1711.00165. 2017.
[52] Richard Zhang, Phillip Isola, Alexei Efros, Eli Shechtman, and Oliver Wang. The unrea- sonable effectiveness of deep features perceptual metric. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 586-595, 2018
[53] Chih-Kuan Yeh, Ankur Taly, Mukund Sundararajan, Frederick Liu, and Pradeep Ravikumar. First is better than last for training data influence. arXiv preprint arXiv:2202. 2022.
[54] Alexander Wei, Wei Hu, and Jacob Steinhardt. More than a toy: Random matrix models predict how real-world neural representations generalize. In International Conference Machine Learning, pages
PMLR, 2022.
[55] Philip M Long. Properties of the after kernel. arXiv preprint arXiv:2105.10583 2021.
13

---

[56] Sadhika Malladi, Alexander Wettig, Dingli Yu, Danqi Chen, and Sanjeev Arora. A kernel-based view of language model fine-tuning, arXiv preprint arXiv:2210.05643, 2022.
[57] Dennis Cook and Sanford Weisberg. Residuals and influence in regression. New York: Chapman and Hall, 1982.
[58] Xiaochuang Han, Byron C Wallace, and Yulia Tsvetkov. Explaining black box predictions and unveiling data artifacts through influence functions. arXiv preprint (rxXi::0005006676 2020.
[59] Yann LeCun and Corinna Cortes. MNIST handwritten digit database. 2010. URL http:
/yann. www..n. www. http//dddbmnnis//////mmmm
[60] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[61] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6988, 2014.
[62] Naman Agarwal, Brian Bullins, and Elad Hazan. Second-order stochastic optimization in linear time. stat, 15, 2016.
[63] James Mercer. Xvi. functions of positive and negative type, and their connection the theory of integral equations. Philosophical transactions of the royal society of London. Series A, containing papers of a mathematical or physical character, 2094444-4588)4415444 1909.
14


Reviews:
[{"review_id": "UzZxEb7XVW", "reviewer": "Reviewer_83iG", "summary": "This paper studies and proposes a set of desirable axioms for sample based explanations. This further demonstrates that the only solution satisfying the set of desirable axioms has the form of $\\alpha_i K(x_i,x)$ (i.e., the product of two components: a global sample importance, and a local sample importance that is a kernel similarity between a training sample and the test point) where $K(.,.)$ is a psd kernel function. Moreover, Many existing sample-based explanation methods such as representer point selection [7], influence functions [5], and TracIn [6]  can be viewed as specific instances of the broad class of generalized representers. ", "questions": "Please address my questions in the weakness section.", "limitations": "The authors did not address the limitations and potential negative societal impact of their work", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The set of desirable axioms makes sense and the link between kernel theory and sample based explanations through set of desirable axioms is interesting.\n\nThe viewpoints to connect the sample based explanations through the set of desirable axioms and the existing sample-based explanation methods is interesting.\n\n\n ", "weaknesses": "Training and learning a kernel model to approximate a given black-box function are challenging and computationally expensive.\n\nMethod 2: approximation using the target function is not convincing to me because it has a loose connection to the kernel theory and the  local sample importance is unclear in this method.\n\nMethod 3 seems to be most practical, but it requires the feature map $\\Phi$ is fixed. \n\nRegarding, Kernel 1: Penultimate-layer Embeddings, it is still unclear to me how to store $\\alpha$ and compute the score $\\alpha_i K(x_i,x)$ if the feature map $\\Phi_{\\theta_1}$ is updated all the times and we have multiple kernels along with the training progress.\n\nFor Kernel 2 and 3, the proposed approach serves as a tool to explain [5] and [6] rather than introduce a new approach. \n\nThe experiments conduct only for binary classification with limited data although the conclusion is interesting.\n\n\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to read and review our paper! We are grateful for your feedback. Please see our responses below.\n\n**Regarding whether we propose new approaches or explain existing approaches**: One of our key goals was to provide an axiomatic framework for a large class of sample based explanations. Thus, the fact that two of the most practically successful sample based explanations (influence functions and TracIn) could be viewed as direct or slightly extended instantiations of our framework is an important indication of the generality of the framework, as well as an indirect validation of the relevance of the corresponding set of axioms specifying the framework. Nonetheless, note that our framework is much more general than influence functions or TracIn, and allow for a suite of other approaches; for instance, with a domain-knowledge specified kernel.\n\n\n**Regarding computing global importance $\\alpha$ with changing kernels**: Dealing with a changing kernel for general non-linear models is still a open problem; what people in the NTK field do now is to extract a kernel representation of the model on a particular checkpoint, i.e. a initialized model or a pretrained model, and use the corresponding kernel machine to approximate the original model [54,56]. In this work, we follow this approach [54,56] in the NTK literature and also compare empirical performance of different choices of kernels and different model checkpoints in the experiment section.\n\nFurthermore, from our experimental findings, it appears that employing multiple kernels might not lead to improvements in the deletion curve metric. For instance, in the case of TracInCP[6], which utilizes NTK from multiple checkpoints, we observed that although this approach does not yield significant benefits, it substantially escalates computational and storage cost. Consequently, we advocate the use of a fixed kernel from the final model as it suffices for sample-based explanations, avoiding unnecessary complexity and resource burden.\n\n**Experiments**: We provide another experiment of CNN on language data in the Appendix, and similar trends are observed. We plan to merge the two experiments and put them in the main text. We hope the experiment on the text data may provide a more convincing conclusion.\n\n**Limitation of our work**: We outline potential societal impact in the appendix and mention possible future directions in the conclusion section.\n\n**Regarding computing global importance $\\alpha$ and choices of kernels**: We discuss choices of kernel functions and the computation of global importance in Section 4 and 5 respectively, and we believe that any kernel choice in Section 5 can be combined with any method in Section 4. Specifically, users may specify a kernel according to their domain knowledge related to models and applications. Next, for methods 1 and 3, users need to fix the kernel and solve the corresponding RKHS regression. For method 2, they only need to compute the derivative of training samples with respect to the loss."}, {"review_id": "zyIafr15Fn", "reviewer": "Reviewer_3USW", "summary": "This paper studies a new framework for generating sample-based explanations for black-box machine learning algorithms. To explain a black-box model, the basic idea of sample-based explanations is to quantify how each training data is influencing the prediction of certain test data. The main contribution of this work is to give a natural set of axioms for defining explanation functional, and showed the equivalence of every explanation function that satisfies these axioms with Mercer kernels. Under this framework, the paper studies how to define the importance function based on given kernel functions and discusses some popular choices of kernel functions in the context of deep learning. ", "questions": "The paper would also be strengthened by additional discourse on the axioms, which are a key element of the study. How do existing sample-based representers fare against these axioms? Furthermore, is the axiom set minimal in its essence? For example, is it possible that the continuity axiom may not hold in some practical situation? The kernel function doesn't have to be continuous without the continuity axiom.\n\nAlthough the authors present the tracking representer as \"a more scalable variant\" due to its reduced computational burden, it consistently outperforms the other two approaches. Could this be partially attributed to early stopping? In addition, the target derivative is proposed as an approximation to avoid solving the Reproducing Kernel Hilbert Space (RKHS) regression, but it also consistently outperforms the original surrogate derivative. It would be beneficial to have further commentary on these points.", "limitations": "The authors have adequately addressed the limitations.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "This paper studies a very interesting and important question within the realm of interpretable (explainable) machine learning, making a very neat connection between a natural set of axioms for the explanation functional and kernel functions. The study is substantial and showcases promising results from numerical studies. ", "weaknesses": "The authors may benefit from expanding their discussion on the selection of kernels. For instance, the Inf-final kernel outperforms all other kernels in Table 1 but lags significantly in Table 2, according to the supplementary material. Given this inconsistency, it seems slightly misleading to simply promote the influential kernel in the main body of the paper without a more thorough discussion.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your encouraging words and constructive comments. Your questions are answered below.\n\n**Seemingly Inconsistent experimental results of Influence function kernel**: When dealing with language data, we calculate the influence function kernel using the last-layer embeddings [5,53]. This choice is made because the word embedding layer contains a substantial number of parameters, making it computationally impractical to compute the exact influence function. However, it has been suggested in [53] that the embedding layer is essential for computing sample influences. We think that the inf-final kernel may not perform as well as the NTK-final kernel due to the absence of the embedding layer's information.\n\nWe plan to merge the two experimental results to the main text and our conclusion would be that the inf-final kernel performs the best whenever all parameters are considered. Otherwise, NTK-final would be the best choice.\n\n**Additional discourse on axioms**:  Most gradient-based sample-based explanations [24], including representer point selections, influence functions, and TracIn (when the corresponding kernel is fixed), satisfy the proposed axioms since they can be represented as generalized representers. On the other hand, retraining-based sample-based explanations [8, 25, 27] compute model prediction changes after removing one or more training samples and retraining the model. These approaches can not be computed using one single model and can not be represented as generalized representers. \n\nThe current set of axioms are minimal since the theorem demonstrates the set of axioms imply the explanations to be generalized representers and it also holds conversely. Additionally, the continuity axiom is crucial to ensure that the kernel qualifies as a Mercer kernel. As most kernels used in the current machine learning literature are Mercer kernels, continuity becomes an essential aspect of our analysis. However, when dealing with explanations for non-continuous models, it is plausible that the corresponding kernel may not be continuous. Extending our axiomatic framework to accommodate such scenarios is an interesting subject for future work.\n\n**Tracking representer**: As indicated by TracIn [6], accessing early checkpoints can be advantageous in identifying influential samples, given that neural networks tend to memorize and overfit to training data. Therefore, the improved performance of tracking representers on the deletion curve metric may be partially attributed to their capacity to retain valuable loss information throughout the training process.\nAlso, since the target derivative more accurately reflects the sensitivity of model to the training loss, the target derivative may perform better on the deletion curve metric.\n"}, {"review_id": "vCThC9Xqbf", "reviewer": "Reviewer_SFDZ", "summary": "In this study, the authors conducted an axiomatic analysis of a measure that quantifies the influence of a given training data on predictions.\nUnder several axioms, the authors demonstrated that an effective measure of influence is limited to the form of a suitable coefficient multiplied by a continuous and positive definite kernel function.\nBased on this finding, the authors showed that many existing influence metrics can actually be expressed in the form of a suitable coefficient multiplied by a kernel function.\nFurthermore, the authors proposed a new measure by combining Representer Point Selection and Neural Tangent Kernel.", "questions": "* Please discuss the validity of the axioms introduced in the paper. When they are appropriate and when they may be not?\n* What are the similarities and differences between the axioms employed in Data Shapley [8] and the axioms considered in this study?\n\n---\nI have read the authors' rebuttal.\nThe difference of the current study and Data Shapley [8] is partly solved.\nI strongly believe it should be discussed in detail in the paper.", "limitations": "The authors mentioned some possible future directions that are not addressed in the current study.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The strength of this study lies in the axiomatic analysis of the measure of data influence.\nUnder Continuity Axiom, Self-Explanation Axiom, Symmetric Zero Axiom, Symmetric Cycle Axiom, and Irreducibility Axiom, the authors demonstrated that an effective measure of influence is limited to the form of a suitable coefficient multiplied by a continuous and positive definite kernel function.\nFurthermore, based on this finding, the authors showed that many existing metrics for measuring influence can indeed be expressed in the form of a suitable coefficient multiplied by a kernel function.\nThe reorganization of these existing influence metrics from an axiomatic perspective represents a novel and significant contribution of this study.", "weaknesses": "An essential weakness of this study is the insufficient discussion regarding the validity of various axioms.\nWhile Continuity Axiom appears to naturally require the continuity of the measure, the validity of the other axioms, Self-Explanation Axiom, Symmetric Zero Axiom, Symmetric Cycle Axiom, and Irreducibility Axiom, is not necessarily evident from the current discussions in the paper.\nIn fact, Data Shapley [8] employs different axioms.\nSince the choice of axioms determines the appropriate measure, the discussion of the validity of these axioms becomes crucial in the axiomatic analysis.\nWhile the authors provide some intuitive explanations, they seem insufficient as a discussion on the validity of these axioms.\nFor example, what are the similarities and differences between the axioms employed in Data Shapley [8] and the axioms considered in this study?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review. We sincerely appreciate your time in reading the paper and we are grateful for your feedback! Our responses are given below.\n\n**Validity of axioms**:  The axioms of the generalized representers encompass both practical and mathematical implications for what an explanation should look like in ideal scenarios. Some axioms focus on the practical aspects of explanations when certain conditions are met, while others maintain important mathematical relationships.\n\nFor instance, the self-explanation and symmetric-zero axioms address scenarios where a sample has no impact on another sample. The self-explanation axiom emphasizes that when a sample has no influence, not even on itself, it is likely to have minimal impact on the model and should consequently have little or no influence on other samples as well. This highlights the practical aspect of explanations, indicating that non-influential samples should not significantly affect model outputs. \n\nThe symmetric-zero axiom underscores the bidirectional nature of “orthogonality“. It emphasizes that if a sample has no impact on another sample, this lack of correlation is mutual and implies that they are orthogonal. This axiom becomes particularly reasonable in cases where ML models treat all training samples equally. In such scenarios, the symmetric-zero axiom suggests that “orthogonal” features have no impact on each other.\n\nOn the other hand, the continuity and irreducibility axiom primarily serves a function-analytic purpose by providing sufficient and necessary conditions of a kernel being a Mercer kernel, which requires that the kernel function be continuous and positive semi-definite. We note that without the two axioms, the theorem still holds in both directions but the kernel function only needs to be symmetric, which is the minimal condition of being a kernel function. Since Mercer kernels have proven to be practically useful and successful in ML (including for algorithmic reasons that explicitly leverage these properties), we decide to preserve the two axioms to make the theorem more grounded to practical usage. \n\n**Comparison to axioms of Data Shapley**: Data Shapley and generalized representers have distinct purposes and interpretations. Data Shapley is used to quantify the importance of individual training samples. In contrast, generalized representers assess the significance of training samples with respect to a specific test sample's prediction. Consequently, the axiomatic properties of these two approaches differ.\n\nFor instance, both Data Shapley and generalized representers adhere to a similar axiom, the self-explanation axiom or the dummy axiom, which dictates that explanations should be zero if a training sample has no impact on the model. However, they require a different theoretical treatments due to the additional focus in generalized representers of explaining a model prediction on a particular test sample (we note that this is also the setting for popular sample explanations such as influence functions, and TracIn). The additional facet of a test input introduces an extra degree of freedom, requiring another axiom to ensure uniqueness of the generalized representers. To this end, the symmetric-zero axiom further expands the notion of the dummy axiom by considering scenarios where one sample has no impact on another sample's prediction. Thus to summarize, the distinction between Data Shapley and Generalized Representers arises from the different contexts and purposes of these two explanation techniques. We thank the reviewer for this important question, and will be sure to add this discussion to the final version of the paper.\n"}, {"review_id": "cDDjc08ACv", "reviewer": "Reviewer_nmaD", "summary": "The paper proposes a unifying framework for sample-based explanation methods via generalised representers. The framework proposes to approximate a general nonlinear predictive function using a surrogate from the Reproducing Kernel Hilbert Space (RKHS) (Surrogate function $f(x)=\\sum_{i=1}\\phi(x_i,x)=\\sum_{i=1}\\alpha k(x_i,x)$). The underlying explanation function $\\phi$ is both necessary and sufficient to satisfy a given set of axioms (aka efficiency, continuity, self-explanation, symmetric zero, symmetric cycle, irreducibility axioms) and can be decomposed in two parts, namely a global component, viz. the alpha coefficients (constant over the whole input space), and a local one, viz. the kernel similarity between the evaluating point and each training instance (which clearly depends on the input). Existing sample-based explanation frameworks, including TracInCP, influence functions and representer points, are shown to be particular instantiations of the proposed framework depending on the choice of the alpha coefficients and the kernel function. Additionally, the framework suggests a new sample-based explanation strategy to reduce the computational storage burden of TracInCP. Experiments are conducted over a CNN model on CIFAR10 and MNIST, thus empirically highlighting the benefits of different choices of alpha coefficients and kernel functions.", "questions": "Overall, I liked the overall formalisation of sample-based explanation techniques. Can you please elaborate more on the following two aspects?\n1. Additional considerations/insights that can be drawn from the analysis.\n2. Scope of validity of experimental results. Are the observations valid for instance on other and larger network architectures than simple CNNs?\n\nPlease, find below a list of possible points to improve the presentation:\n1. Is Method 2 in Section 4.2 necessary for the presentation?\n2. Line 206 should $\\nabla_{\\theta}$  be replaced with $\\nabla_{f_\\theta}$?\n3. Line 222 replace the correct reference and Line 224 remove “show”\n4. Would it better to summarise sample-based explanation strategies in the form of a table, thus highlight the different choices of alpha and kernel functions and the difference with the proposed strategy?\n5. Can you please highlight more the difference between TracInCP and your strategy?\n\n", "limitations": "No additional suggestions to improve the paper", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "\n1. The idea of unifying existing sample-based explanation approaches is elegant, original and novel ( **Originality** )\n2. Overall, the paper is clear and self-contained ( **Clarity** ). Perhaps, the presentation can be improved by taking into account some of the suggestions highlighted in the Questions section.", "weaknesses": "1. Code is not available. It would be good to release the code for replicating the analysis ( **Reproducibility** ).\n2. While the theory unifying different sample-based explanation approaches is nice, the observations that can be drawn from it are rather limited to the analysis on the choice of different alpha/kernel functions ( **Significance** ).\n3. The experimental analysis uses rather small and simple neural networks and represents a simple proof of concept (**Quality**). Since the authors compare against TracInCP, they should consider using the same experimental settings of the main paper (namely using ResNet architecture).\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful for the review, and we truly value the time you dedicated to reading our paper. Our point-to-point responses to your comments are given below.\n\n\n**Code release**: We are working on reorganizing the code, and plan to release it when the paper is published.\n\n\n**Additional insights from analysis**: The analysis gives us insights of how these axioms guarantee the explanations to take on the unique form. The symmetric cycle axiom ensures that the explanation should have the form consisting of a global importance and a kernel similarity term. \nThe self-explanation axiom and the symmetric zero axiom address scenarios where explanations may become zero. Specifically, the self-explanation axiom handles the case where a training sample has no impact on the model and ensures that the global importance should be zero in this case. On the other hand, the symmetric zero axiom emphasizes that the similarity measure must remain symmetric even when one of the explanations is zero. \nLastly, the irreducibility axiom ensures the kernel function be a Mercer kernel by ensuring the kernel is positive semidefinite.\n\n\n**Scope of Experiments**: Our experimental setting requires retraining models to be explained for over 10,000 times, so we decided to perform experiments on smaller models due to limited computational resources on both image and language data (see appendix).\nFor larger models, we expect similar trends, which can be partially supported in other studies. Particularly, Trak [38] employs influence kernels and empirically demonstrates that it outperforms existing methods by a large margin for large models like ResNet-50 and Transformer. The observation aligns with our finding when comparing different kernels. Moreover, experiments in Yeh et al. [53] show that information in early layers is more important when computing data influences for transformers. It is also observed in our language data experiments on smaller models since the NTK-final outperforms last layer embeddings in Table 2 in the appendix.  \n\n\n**Comparison to TracInCP**:  Our proposed tracking representers share similar intuition with TracInCP as they both tracking gradient descent trajectories. However, a crucial difference is that TracInCP employs a changing NTK kernel as it accesses different checkpoints in the training process. While it may leads to more accurate approximation, TracInCP requires storing training checkpoints and performing inference on each of them, resulting in an increased computational and storage cost proportional to the number of checkpoints.\nOn the contrary, the tracking representer only requires NTK from the final model. It accumulates derivative information using the global importance, as shown in definition 11, which significantly improves efficiency. Remarkably, our experiments demonstrate that this approach achieves comparable performance to TracInCP while being more computationally efficient. \n\n\n**Suggestions for improving presentations**:  Thank you for the suggestions. We have corrected the typos in our draft. A table listing choices of global importance and kernel functions of existing sample-based approaches and proposed algorithms is also added. Also, the target derivative approach is important to the paper since it is the global importance used by existing approaches like the influence function and TracInCP (when learning rate is constant). \n\n\n"}]

Author rebuttal:

Meta-review: Most reviewers tend to accept the paper, and one reviewer champions the paper with a score of 7. Therefore, I would recommend acceptance of the paper. In the rebuttal phase, one reviewer requires further clarification about how the axioms of Data Shapley and the axioms of Generalized Representers differ in the setting. Please take the review into account in the revision of the paper.
Decision: Accept (poster)