Estimating informativeness of samples with Smooth Unique Information
Authors: Hrayr Harutyunyan
Alessandro Achille
Giovanni Paolini
Orchid Majumder
Avinash Ravichandran
Rahul Bhotika
Stefano Soatto
Venue: ICLR 2021 Poster (2021)
Keywords: sample information
information theory
stability theory
ntk
dataset summarization

Abstract: We define a notion of information that an individual sample provides to the training of a neural network, and we specialize it to measure both how much a sample informs the final weights and how much it informs the function computed by the weights. Though related, we show that these quantities have a  qualitatively different behavior. We give efficient approximations of these quantities using a linearized network and demonstrate empirically that the approximation is accurate for real-world architectures, such as pre-trained ResNets. We apply these measures to several problems, such as dataset summarization, analysis of under-sampled classes, comparison of informativeness of different data sources, and detection of adversarial and corrupted examples. Our work generalizes existing frameworks, but enjoys better computational properties for heavily over-parametrized models, which makes it possible to apply it to real-world networks.

Published as a conference paper at ICLR 2021
ESTIMATING INFORMATIVENESS OF SAMPLES WITH SMOOTH UNIQUE INFORMATION
Hrayr Harutyunyan' 1.2- Alessandro Achille', Giovanni Paolini', Orchid Majumder', Avinash Ravichandran Rahul Bhotika' Stefano Soatto Amazon Web Services," USC Information Sciences Institute brayrhareusc.co edu, faachille, paoling, (xchid)@amazonn com, (ravinash, bhotikar, soattos @amazon.coo
ABSTRACT
We define a notion of information that an individual sample provides to the train- ing of neural network, and we specialize it to measure both how much ple informs the final weights and how much it informs the function computed by the weights. Though related, we show that these quantities have a qualita- tively different behavior. We give efficient approximations of these quantities using a linearized network and demonstrate empirically that the approximation is accurate for real-world architectures, such as pre-traine pre-trained ResNets. We apply these measures to several problems, such as dataset summarization, analysis of under-sampled classes, comparison of informativeness of different data sources, and detection of adversarial and corrupted examples. Our work generalizes ex- isting frameworks but enjoys better computational properties for heavily over- parametrized models, which makes it possible to apply it to real-world networks.
INTRODUCTION
Training a deep neural network (DNN) entails extracting information from samples in dataset and storing it in the weights of the network, so that it may be used in future inference or prediction. But how much information does a particular sample contribute to the trained model? The answer can be used to provide strong generalization bounds (if no information is used, the network is not mem- orizing the sample), privacy bounds (how much information the network can leak about particular sample), and enable better interpretation of the training process and its outcome. To determine the information content of samples, we need to define and compute information. In the classical sense, information is property of random variables, which may be degenerate for the deterministic pro- cess of computing the output of a trained DNN in response posing the problem presents some technical challenges. But beyond technicalities, how can we know whether a given sample is memorized by the network and, if it is, whether is used for inference?
given input (inference). So, even
We propose notion of unique sample information that, while rooted in information theory, cap- tures some aspects of stability theory and influence functions. Unlike most information-theoretii measures, ours can be approximated efficiently for large networks, especially in the case of transfer learning, which encompasses many real-world applications of deep learning. Our definition can be applied to either "weight space" "function space." This allows to study the non-trivial dif- ference between information the weights possess (weight space) and the information the network actually uses to make predictions new samples (function space).
Our method yields a valid notion of information without relying on the randomness of the training algorithm (e.g., stochastic gradient descent, SGD), and works
for deterministic training algo- rithms. Our main work-horse is first-order approximation of the network. This approximation is accurate when the network pre-trained (Mu al.) 2020) as is common in practical applications or is randomly initialized but very wide (Lee et al. 2019), and can be used to obtain closed-form expression of the per-sample information. In addition, our method has better scaling with respect to the number of parameters than most other information measures, which makes it applicable to mas-
Work conducted Amazon Weh Services.

---

Published as a conference paper at ICLR 2021
sively over- wverpparaeetrized models such as DNNs. Our information measure can be computed without actually training the network, making amenable to use in problems like dataset summarization.
We apply our method to remove large portion of uninformative examples from training set with minimum impact on the accuracy of the resulting model (datasct summarization). We also apply our method to detect mislabeled samples, which we show carry more unique information.
To summarize, our contributions are (1) We introduce a notion of unique information that a sample contributes the training of DNN, both in weight space and in function space, and relate it with the stability of the training algorithm; (2) We provide an efficient method to compute unique information even for large networks using linear approximation of the DNN, and without having train network; (3) We show applications to dataset summarization and analysis. The implementation of the proposed method and the code for reproducing the experiments is available at https://
g thub. cww/ awsl
wwwwwwwwwwsssseeeeeeeeeee inteeeeeiifrmaaammm ion
Prerequisites and Notation. Consider a dataset of n labeled examples = {2:]i=1. where 2; (1i, (1), 3y E X and yi R and neural network model fw : X IR. with parameters w R.. Throughout the paper S = {Z1..... 24-1, 2..1...... 2x denotes the set excluding the i- th sample: fwe is often shortened to fr; the concatenation of all training examples is denoted by X; the concatenation of all training labels by Y E R and the concatenation of all outputs by fw (X) "R The loss on the i-th example denoted by (w) and is equal to (r.) - Vi llg. unless specified otherwise. This choice is useful when dealing with linearized models and is justified by Hyi & Belkin (2020), who showed that the meaan-quared error (MSE) loss as effective as cross- entropy for classification tasks. The total loss is ((w) >== L.(w) + E ||w woll2 l1 where À 2 0 is a weight decay regularization coefficient and wo is the weight initialization point. Note that the regularization term differs from standard weight decay || and is more appropriate for linearized neural networks, as it allows us to derive the dynamics analytically (see Sec. of the appendix). Finally, a (possibly stochastic) training algorithm is denoted with mapping A S W, which maps a training dataset S to classifier weights W = =A()). Since the training algorithm can be stochastic, W is a random variable. The distribution of possible weights W after training with the algorithm A on the dataset S' is denoted with PA (w 5). We use several information-theored
[ log p(x)]. mutual information: T(X;Y) = H(X) + HYY - H(X, Kullback-Leible divergence: (p=))))(()(() = Ex-elaa) (log(p(z)/((z)) and their conditional variants (Cover& & Thomas 2006). If y E R. and x E R", then the Jacobian ay is an m X n matrix. The gradient Vzy denotes transpose of the Jacobian By
quantities, such as entropy: H(X) = -E
an n. X m matrix. 0x .
2 RELATED WORK
Our work is related to information-theoreii stability notions (Bassily et al. 2016 Raginsky jet al.] 2016; Feldman & Steinke| 2018) that seek to measure the influence of a sample on the output, and measure generalization. Raginsky et al. (2016) define information stability as Es [ Σm= 7(W: Z: := the expected average amount of unique (Shannon) information that weights have about example. This, without the expectation over S, is also our starting point (eq.) Bassily et al. (016)) define KL-stability sups,s ( (w S) Pl | S')). where S and S' are datasets that differ by one example, while Feldman & Steinke (218)) define average leave- one-out KL stability as sups _ Σm= (L(ps(W [) [ssww S))).. The latter closely resembles our definition (eq. Dp. Unfortunaelly while the weights are continuous, the optimization algorithm (such as SGD) is usually discrete. This generally makes the resulting quantities degenerate (infinite). Most works address this issue by replacing the discrete optimization algorithm with continuous one, such as stochastic gradient Langevin dynamics (Welling& & Teh 2011) or continuous stochastic differential equations that approximate SGD (Li et al.] (017) in the limit. We aim to avoid such assumptions and give a definition that is directly applicable to real networks trained with standard algorithms. To do this, we apply smoothing procedure to a standard discrete algorithm. The final result can still be interpreted as a valid bound on Shannon mutual information, but for a slightly modified optimization algorithm. Our definitions relate informativeness of sample to the notion of algorithmic stability (Bousquet& & Elisseeff [2002] Hardt et al., 2013). where a training algorithm A is called stable if A(S) is close A(S") when the datasets S and S differ by only one sample.
2

---

Published as a conference paper at ICLR 2021
To ensure our quantities are well-defined, we apply smoothing technique which is reminiscent of soft discretization of weight space. In Section 4 we show that a canonical discretization is obtained using the Fisher information matrix, which relates to classical results of Rissanen (1996) on optimal coding length. It also relates to the use of a post-distribution in Achille et (2019), who however use estimate the total amount of information in the weights of network.
We use a first-order approximation (linearization) inspired by the Neural Tangent Kernel (NTK) (Ja- cot al., 2018; Lee et al., 2019) to efficiently estimate informativeness of sample. While NTK predicts that, in the limit of an infinitely wide network, the linearized model is an accurate approxi- mation, we do not observe this on more realistic architectures and datasets. However, we show that, when using pre-trained networks as common in practice. linearization yields an accurate approxi- mation, similarly to what is observed by Mu et al. (2020). (Shwartz-Ziv & Alemi (2000) study the total information contained by an ensemble of randomly initialized linearized networks. They notice that, while considering ensembles makes the mutual information finite, still diverges to infinity as training time goes to infinity. On the other hand, we consider the unique information about a single example, without the neeed for ensembles, by considering smoothed information, which remains bounded for any time. Other complementary works study how information about an input sample propagates through the network (Shwartz Ziv & Tishby] [017] Achille & /201 [axx et al., 2019) or total amount of information (complexity) of classification dataset (Lorena et al. 2019). rather than how much information the sample itself contains.
In terms of applications, our work is related to works that estimate influence of example (Koh & Liang 2017 Toneva et al. 2019| Katharopoulos & Fleuret, 20188] Ghorbani & Zou| 2019 Yoon ct al. 2019). This can be done by estimating the change weights a sample removed from the
Training set, which is addressed by several works (Koh & Liang] 2017 Golatkar et al. 2020 Wu
al., 2020). Influence functions (Cook] 1977 Koh & Liang/ 2017) model removal of a sample as reducing its weight infinitesimally in the loss function, and show an efficient first-order approxima- tion of its effect on other measures (such as test time predictions). We found influence functions to
be prohibitively slow for the networks and data regimes we consider. [Basu et al. (2020) found that influence functions are not accurate for large DNNs. Additionally, influence functions assume that the training has converged, which is not usually the case in practice. We instead use lincarization of neural networks to estimate the effect of removing an example efficiently. We find that this approx- imation is accurate in realistic settings, and that the computational cost scales better with network size, making it applicable to very large neural networks.
Our work is orthogonal that of feature selection: while we aim evaluate the informativeness for the final weights of a subset of training samples, feature selection aims to quantify the informative- ness for the task variable of subset of features. However, they share some high-level similarities. In particular, Kohavi et al. (1997) propose the notion of strongly-relevant feature as one that changes the discriminative distribution when is excluded. This notion is similar to the notion of unique sample information in eq. (I.
3 UNIQUE INFORMATION OF A SAMPLE IN THE WEIGHTS
Consider a (possibly stochastic) training algorithm that, given a training dataset S, returns the weights W of classifier fw. From an information-theone point of view, the amount of unique information a sample 2; = (I; ys) provides about the weights given by the conditional point-wise mutual information:
(I) where S denotes the random variable whose sample is the particular dataset S, and S = S_,, 2()d(((() = Ex/-p(=) [A (w
I(W; 2, = z S_, = S_.) KL(P SS = S) || r(
S S_.)),
r(w S_, = :=:= =
S= S== 2])] denotes the
marginal distribution of the weights over all possible sampling of Z Computing the distribution
r(w S_;) is challenging because of the nigh-dimensionality and the cost of training algorithm A for multiple samples. One can address this problem by using the following upper bound (Lemma B.I.
(L(ps(W| S) || r(w ()))) (I[pa(w] (S) || q(w S_.) - (L( | S_.) || q(w S_.))
(L(Pa(W) S) g( S_:)),
(2)
Hereafter, to avoid notational clutter, we will shorten "S_; S_;" to S_, and "7, 2," to just in all conditionals and cooomation-thhoretit functionals.
3

---

Published as a conference paper at ICLR 2021
which is valid for any distribution q(w (--)) Choosing ( S_-)) PA (w s the distribution
of the weights after training on S-i. gives a reasonable upper bound (see Sec. A. for details):
I(W: 2 S_+)= & KL(pa(W S) PA S-()).
(3)
We call SI( A) A (1 uo| ()) PA S_))) the sample information of w.r.t. algorithm A.
Smoothed Sample Information. The formulation above is valid in theory but, in practice, even SGD is used in deterministic fashion by fixing the random seed and, in the end, obtain just one set of weights rather than distribution of them. Under these circumstances, all the above KL divergences are degenerate, as they evaluate to infinity. It is common address the problem by assuming that A is a continuous stochastic optimization algorithm, such as stochastic gradient Langevin dynamics (SGLD) continuous approximation of SGD which adds Gaussian noise to the gradients. However, this creates a disconnect with the practice, where such approaches do not perform at the state-of-the-arr. Our definitions below aim to overcome this disconnect.
Definition 3.1 (Smooth sample information). Let A be possibly stochastic algorithm. Following eq. (3) we define the smooth sample information with smoothing E2
(1 A) KL(PAg (w 5) PAp (w (S-)).
where we define smoothed weights As( A A(S) + S. with & (N(0E))
Note that if the algorithm is continuous, we can pick Σ + O, which will make S1y(2,, A) SI(2,, A). The following proposition shows how to compute the value of Sly in practice. Proposition 3.2. Let A be a deterministic training algorithm. Then, we have:
+
1 Sly(2i, A) 7 --- w-i),
(5)
where w = A(5) and w-s = A(S_.) are the weights obtained by training respectively with and without the training sample 24. That the value of Sly(z4) depends on the distance between the solutions obtained training with and without the sample 2,, rescaled by E.
The smoothing of the weights by a matrix can be seen as a form of noft-iisceetization. Rather than simply using an isotropic discretization Σ = o²1 - since different filters have different norms and/or importance for the final output of the network it makes sense discretize them differently. In Sections 4 [nd we show two canonical choices for E. One is the inverse of the Fisher information matrix, which discounts weights not used for classification, and the other is the covariance of the steady-state distribution of SGD, which respects the level of SGD noise and flatness of the loss.
4 UNIQUE INFORMATION IN THE PREDICTIONS
SIs:(2,, A) measures how much information an example 2; provides to the weights. Alternatively, instead of working in weight-space, can approach the problem in function-space, and measure the informativeness of training example for the network outputs or activations. The unique information that 2; provides the predictions on a test example is:
I [z ÿ x. S-,) Es (L 2, 22 || rū x. S.)))
where p(z) previously unseen test sample, Φ q(
x, S) the network output on
input r after training on S, and r(ū x, S_,) = (Ø x, S.S... d)())( = E.:9( I, S.S., 2().
Following the reasoning in the previous section, we arrive at
T(2;; Ø x. < KL(G()) x. x, 40 x, S_.))
Again, when training with a discrete algorithm and/or when the output of the network is determin- istic, the above quantity may be infinite. Similar to smooth sample information, we define:
Definition 4.1 (Smooth functional sample information). Let A be a possibly stochastic training algorithu and let be the prediction functional sample information (F-SI) as:
test example a after training S. We define the smooth
F-SI. (zz, A) = ( [KL (go @Zo x. S) 11 (No
x. S-O)]
where Jo -(x S) + n, with n N200022) and yo (Ta x. S) being the distribution of Ta.
4

---

Published as a conference paper at ICLR 2021
We now describe a first-order approximation of the value of F-SIg for deterministic algorithms.
Proposition 4.2. Let A be a deterministic algorithm, = A(S) and w-i A(S-i) be the weights obtained training respectively with and without sample 24- Then,
(- A)
20 B. Re (15 - f (x)
(8)
2n (w - w F.w)" - -w--))),
with F(w) Eg V vw V (x)" being the Fisher information matrix of 90=1 x, S).
By comparing eq. and eq. ( we see that the functional sample information approximated by using the inverse of the Fisher information matrix to smooth the weight space. However, this smoothing is not isotropic as it depends on the point w.
EXACT SOLUTION FOR LINEARIZED NETWORKS
In this section, we derive a close-form expression for Sly and F-Sly using a linear approximation of the network around the initial weights. We show that this approximation can be computed efficiently and, as we validate empirically in Sec. 6 correlates well with the actual informativeness values. We also show that the covariance matrix of SGD's steady-state distribution is canonical choice for the smoothing matrix E of SIy:
Linearized Network. Linearized neural networks class of neural networks obtained by taking the first-order Taylor expansion of a DNN around the initial weights (Lee et al. 2019):
lin (x)
A uw (x) + V (x)) ww= (w - w
These networks are linear with respect to their parameters w, but can be highly non-linear with respect to their input x. One of the advantages of linearized neural networks is that the dynamics of continuous-
or discrete-time gradient descent can be written analytically if the loss function is the mean squared error (MSE). In particular, for continuous-time gradient descent with constant learning rate 77 > 0, we have (Lee et al. 2019):
we = fo (1 ee- (fo(x) - Y), |l (z) = fo(2) + Oolz, 0)(,,))05' (1- (Y fo(X)),
(10)
(11)
gukxnk is the Neural Tangent Kernel (NTK) (Jacot et al. 2018 Lee et al. 2019) and (z, X) = fux))' V. fu(X). I The expressions for networks trained
where V
ww V
with weight decay is essentially the same (see Sec. F.. To keep the notation simple, we will use fan (x) to indicate (x)) from now on.
Stochastic Gradient Descent. As mentioned in Sec. popular alternative approach to make information quantities well-defined is to use continuous-time SGD, which is defined by (Li et al. 2017 Mandt et al. 2017):
dw; - Cw. + m/ A A(w;)dn(t).
(12)
where 17 is the learning rate, is the batch size, (t) is a Brownian motion, and A(w:) ) is the co- variance matrix of the per-sample gradients (see Sec. Cfor details). Let ASGD be the algorithm that returns a random sample from the steady-state distribution of (12), and let AERM be the deterministic algorithm that returns the global minimum w" of the loss L(w) (for a regularized linearized network [(w) is strictly convex). We now show that the non-smooth sample information SI(2,, Ascu) is the same as the smooth sample information using SGD's steady-state covariance as the smoothing matrix and AFRM as the training algorithm.
Proposition 5.1. Let the loss function be regularized MSE, w* be the global minimum of it, and algorithms AsgD and AErS be defined as above. Assuming A(w) is approximately constant around w" and SGD's 's staae covariance remains constant after removing an example, we have
SI(z,, Asan) = Slx(2i, AFRM) 2 (w" w²,)² I' w"_,),
(13)
5

---

Published as a conference paper at ICLR 2021
where Es is the solution of
HE + ΣH = ? -/
(14)
with H -
+ X1) being the Hessian of the loss function.
This proposition motivates the use of SGD's steady-state covariance as a smoothing matrix. From equations (13) and (14) we see that SGD's steady-state covariance is proportional to the flatness of the loss at the minimum, the learning rate, and to SGD's noise, while inversely proportional to the batch size. When H is positive definite, as in our case when using weight decay, the continuous Lyapunov equation (14) has a unique solution, which can be found in O(d)) time using the Bartels- Stewart algorithm (Bartels & Stewart 1972). One particular case when the solution can be found analytically is when A(w") ) and I/ commute, in which case Σ = 2y -H-- -1 For example, this is the case for Langevin dynamics, for which A(w) = o² I in equation 12 In this case, we have
b
Si,, ASGD) Sly AERM)
nols (w" - w".)" H(w" w=;),,
(15)
which was already suggested by Cook (9777) as way to measure the importance of a datum in linear regression.
The definition in Section 4 simplifies for linearized neural net- works: The step from eq. (8) to eq. (9) becomes exact, and the Fisher information matrix becomes This shows that functional sam- be seen weight sample information with discretization E equal F-1. The
Functional Sample Information.
independent of w and equal to F Ez=p(x) ple information functional sample information depends on the training data distribution, which is usually unknown. We can estimate it using validation set:
F-SLo (zi, Ro
[((( - fw_((17)
(16)
20
j=1
-A)(
(17)
20
It is instructive compare the sample weight information of (15) and functional sample information of (17). Besides the constants, the former uses the Hessian of the training loss, while the latter uses the Hessian of the validation loss (without the l regularization term). One advantage of the latter is computational cost: As demonstrated in the next section, we can use equation (16) to compute the prediction information, entirely in the function space, without any costly operation on weights. For this reason, we focus on the linearized F-SI approximation in our experiments. Since o is just multiplicative factor in (T7 we set 1. We also focus on the case where the training algorithm A is discrete gradient descent running for i epochs (equations 10 and
Efficient Implementation. To compute the proposed sample information measures for linearized neural networks, we need to compute the change in weights w W-4 (or change in predictions fw (z) fw,, (z)) after excluding an example from the training set. This can be done without retrain- ing using the analytical expressions of weight and prediction dynamics of linearized neural networks eq. (10) and eq. (TT). which also work when the algorithm has not yet converged (t < oc). We now deseribe series of measures make the problem tractable. First, to compute the NTK matrix
would need to store the Jacobian V (o;) of all training points and compute (x,ffoX)' " (o(X)... This is prohibitively slow and memory consuming for large DNNs. Instead, similarly to Zancato et al. (2020), we use fow-dimensional random projections of per-example Jacobians to obtain prov- ably good approximations of dot products (Achlioptas) 2003 Li et al. 2006). We found that just taking 2000 random weights coordinates per layer provides a good enough approximation of the NTK matrix. Importantly, we consider each layer separately, as different layers may have different gradient magnitudes. With this method, computing the NTK matrix takes O(nkd + n2k2do do) time, where dg R3 10 is the number of sub-sampled weight indices (do < d). We also need to recom- pute O,¹ after removing example from the training set. This can be done in quadratic time by using rank-one updates of the inverse (see Sec. E Finally, when t * oo we need to recompute St after removing example. This can be done in Ō(??k?) time by downdating the eigen- decomposition of O (Gu & Eisenstat, 1995). Overall, the complexity of computing w - w; for all training examples is Onn2k'd +n k² + +C)), C. is the complexity of single pass over the

---

Published as a conference paper at ICLR 2021
Reg.
Method
MNIST MLP
MNIST CNN
Cats and Dogs
scratch
scratch
pretrained
pr. ResNer-18
pr. ResNet-50
Lineurization
0,987
0.193
0.870
0.895
0,968
weights
Infl. functions
0.935
0.319
0.736
0.675
0.897
10
Lincarization
0.977
-0.012
0,964
0.940
0.816
Infl. functions
0.978
0.069
0.979
0.858
0.912
predictions
À
Lincarization
0.993
0.033
0.875
0.877
0.895
Infl. functions
0,920
0.647
0.770
0.530
0.715
10
Lincarization
0.993
0.070
0.974
0.931
0.519
Infl. functions 0.990
0.407
0.954
0.753
0.506
Table 1: Pearson correlations of weight change ||w w-ill3 and validation prediction change Wo (Xmi) - fw (2 norms computed with influence functions and linearized neural networks with their corresponding measures computed for standard neural networks with retraining.
A
Lesst inforrms live elar molee
informativv samples
135
Figure 1: Functional sample information of samples in the iCassava classification task with 1000 samples, where the network is a pretrained ResNet- 18. A: histogram of sample informations, B: 10 least informative samples, C: 10 most informative samples.
training dataset. The complexity of computing functional sample information for m test samples is O(C nmmk2d + (mmnk² + )²)) This depends on the network size lightly, only through C.
EXPERIMENTS
In this section, we test the validity of linearized network approximation in terms of estimating the effects of removing an example and show several applications of the proposed information measures. Additional results and details are provided in the supplementary Sec.
Accuracy of the linearized network approximation. We measure -|w- w-ill and (X.a)) (Xaa) 11 for each sample 2; by training with and without that example. Then, instead training, we use the efficient linearized approximation in Sec. 6 to estimate the same quantities and measure their correlation with the ground-truth values (Table Tp. For comparison, we also estimate these quantities using influence functions (Koh & Liang 2017). We consider two classification tasks: (a) toy MNIST 4 vs classification task and (b) Kaggle Dogs vs. Cats classification task Kaggle 2013). both with 1000 examples. For MNIST we consider a fully connected network with a single hidden layer of 1024 ReLU units (MIP) and a small 4-layer convolutional network (CNN), either trained from scratch or pretrained on EMNIST letters (Cohen al. (017). For cats vs dogs classification, we consider ResNet-18 and ResNet-50 networks (He et al. 2016) pretrained on Ima- geNet. In both tasks, we train both with and without weight decay (l, regularization). The results in Table T that linearized approximation correlates well with ground-truth when the network wide enough (MLP) and/or pretraining used (CNN with pretraining and pretrained ResNets), This is expected, as wider networks can be approximated with linearized ones better (Lee et al.) 2019, and pretraining decreases the distance from initialization, making the Taylor approximation more accurate. Adding regularization also keeps the solution close initialization, and generally increases the accuracy of the approximation. Furthermore, in most cases lincarization gives better results compared to influence functions, while also being around 30 times faster in settings.
Which examples are informative? Fig. D and Fig. of the supplementary, plot the top 10 least and most important samples in iCassava plant disease classification (Mwebaze et al. 2019). the MNIST vs 9, and Kaggle cats vs dogs classification tasks. Especially in the case of the last two, we see that the least informative samples look typical and easy, while the most informative ones look more
7

---

Published as a conference paper at ICLR 2021
104
14 104
12
detruted
Top ScOuRIcy
0.8
0.0
0.6
0.7
0.6
0.2
Edtter (Reodleo))
0.0
Inforrm intermatiennes.co of desmple
Le
0.0
0.0
Informatrattees an eicemppe
2.5
10
0.5
0.0
examples
0.8
(a) Comparing data sources
(b) Detecting mislabeled examples
(c) Summarizing datasets
Figure 2: Applications of functional sample information. (a) Different sources of data for the same task (digit classification) can have a vastly different amount of information. (b) As expected, samples with the wrong labels carry more unique information. (c) Test accuracy as function of the ratio of removed training examples using different strategies.
challenging and atypical. In the case of iCassava, the informative samples are more zoomed on features that are important for classification (e.g., the plant disease spots). We observe that most samples have small unique information, possibly because they are easier or because the dataset may have many
examples. While in the case of MNIST vs 9 and Cats vs. Dogs, the two classes have on average similar information scores, in Fig. Ia we see that in iCassava examples from rare classes (such as 'healthy' and 'cbb') are on average more informative.
Which data source is more informative? In this experiment, we train for 10-way digit classifica- tion where both the training and validation sets consist of 1000 samples, 500 from MNIST and 500 from SVHN. We compute functional sample information for pretrained ResNet- 18 network. The results presented in Fig. 2a tell that SVHN examples are much more informative than MNIST exam- ples. The same result holds if we change the network to be a pretrained DenseNet- 121 (see Fig. 7a). This is intuitive, as SVHN examples have more variety. One can go further and use our information measures for estimating informativeness of examples of dataset A for training classifier for task B, similar to Torralba & Efros (001))
Detecting mislabeled examples. We expect mislabeled example to carry more unique informa- tion, since the network needs to memorize unique features of that particular example to classify it. To test this, we add 10% uniform label noise to MNIST 4 vs Kaggle cats vs dogs, and iCassava classification tasks (all with 1000 examples in total), while keeping the validation sets clean. Fig. 2b plots the histogram of functional sample information for both correct and mislabeled examples in the case of iCassava classification task with a pretrained ResNet- 18, while Fig. Bal and plot that for MNIST 4 vs 9 and Kaggle cats vs dogs tasks, respectively. The results indicate that mislabeled examples are much more informative on average. This suggests that our information measures can be used to detect outliers or corrupted examples.
Data summarization. We subsample the training dataset by removing fraction of the least infor- mative examples and measure the test performance of the resulting model. We expect that removing the least informative training samples should not affect the performance of the model. Note how- ever that, since we are considering the unique information, removing one sample can increase the informativeness of another. For this reason, we consider two strategies: In one compute the informativeness scores once, and remove a given percentage of the least informative samples. In the other we remove 5% of the least informative samples, recompute the scores, and iterate until we remove the desired number of samples. For comparison, we also consider removing the most informative examples ("top" baseline) and randomly selected examples ("random" baseline). The results on MNIST 4 vs 9 classification task with the one-hidden-layer network described earlier, are shown in Fig. 2c Indeed, removing the least informative training samples has little effect on the test error, while removing the top examples has the most impact. Also, recomputing the information scores after each removal steps ("bottom iterative") greatly improves the performance when many samples are removed, confirming that SI and F-SI are good practical measures of unique informa- tion in a sample, but also that the total information in a large group is not simply the sum of the unique information of its samples. Interestingly, removing more than 80% of the least informative examples degrades the performance more than removing the same number of the most informative examples. In the former case, are left with small number of most informative examples, some
8

---

Published as a conference paper at ICLR 2021
of which outliers, while in the latter case are left with the same number of least informative examples, most of which are typical. Consequently, the performance is better in the latter case.
Detecting under-sampled sub-classes. Using CIFAR-10 images, we create dataset of "Pets vs Deer": Pets has 4200 samples and deer 4000. The class "pets" " consists two unlabeled sub-classes, cats (200) and dogs (4000). Since there are relatively few cat images, expect each to carry more unique information. This is confirmed when we compute F-SI for pretrained ResNet-18 (see Fig. p of the supplementary), suggesting that the F-SI can help to detect when an unlabeled sub-class of larger class is under-sampled.
7 DISCUSSION AND FUTURE WORK
The smooth (functional) sample information depends not only on the example itself, but on the net- work architecture, initialization, and the training procedure (i.e. the training algorithm). This has to be the case, since an example can be informative with respect to one algorithm or architecture, but not informative for another one. Similarly, some examples may be more informative at the beginning of the training (e.g., simpler examples) rather than at the end. Nevertheless, we found out that F-ST still captures something inherent in the example. In particular, as shown A.c. of the supplemen- tary, F-ST scores computed with respect different architectures are significantly correlated each other (e.g. around 45% correlation in case of ResNet-50 and DenseNet-121). Furthermore, F-SI scores computed for different initializations are significantly correlated (e.g. around 36%). Simi- larly, F-SI scores computed for different training lengths strongly correlated (see Fig. (5b). This suggests that F-SI computed with respect to one network can reveal useful information for another one. Indeed, this is verified in Sec. [A.4Jof Sec.[A.4Jof the supplementary, where redo the data summarization experiment, but with a slight change that F-SI scores are computed for one network, but another net- work is trained to check the accuracy. As shown in the Fig. 7b the results look qualitatively similar to those of the original experiment.
The proposed sample information measure only the unique information provided by an example. For this reason, it is not surprising that typical examples are usually the least informative, while atypical and rare ones are more informative. This holds not only for visual data (as shown above), but also for textual data (see Sec. A.8 of the supplementary). While the typical examples are usually less informative according to the proposed measures, they still provide information about the deci- sion functions, which is evident in the data summarization experiment removing lots of typical examples was worse than removing the same number random examples. Generalizing sample information to capture this kind of contributions is an interesting direction for future work. Simi- lar to Data Shapley (Ghorbani & Zou| 2019)). one can look at the average unique information an example provides when considering along with random subset of data. One also consider common information, high-order information, synergistic information, and other notions of infor- mation between samples. The relation among these quantities is complex in general, even for variables (Williams & Beer 2010) and is an open challenge.
CONCLUSION
There are many notions of information that relevant understanding the inner workings of neu- ral networks. Recent efforts have focused on defining information in the weights or activations that do not degenerate for deterministic training. We look the information in the training data, which ultimately affects both the weights and the activations. In particular, we focus on the most elemen- tary case, which is the unique information contained understanding more complex notions. However, our approach can be readily generalized to unique information of a group of samples. Unlike most previously introduced information measures, ours is tractable even for real datasets used to train standard network architectures, and does not require restriction to limiting cases. In particular, we can approximate our quantities without requiring the limit of small learning rate (continuous training time), or the limit of infinite network width.
sample, because it can be the foundation for
ACKNOWLEDGMENTTS
We thank the anonymous reviewers whose comments/suggestions helped improve and clarify this manuscript.

---

Published as a conference paper at ICLR 2021
REFERENCES
Alessandro Achille and Stefano Soatto. Emergence of invariance and disentanglement in deep rep- resentations. The Journal of Machine Learning Research, 19():1147-1180, 2018.
Alessandro Achille, Giovanni Paolini, and Stefano Soatto. Where is the information a deep neural network? arXiv preprint
2019.
Dimitris Achlioptas. Database-friendes random projections: lindest-indesstrauss with binary coins. Journal of computer and System Sciences, 66(4):671-687 2003,
R. H. Bartels and G. W. Stewart. Solution of the matrix equation + xb [f4]. Commun. ACM, 15(9):820-88) 826, September 1972. ISSN 0001-0782. doi: 10.1 10.1145/361533.361533
Raef Bassily, Kobbi Nissim, Adam Smith, Thomas Steinke, Uri Stemmer, and Jonathan Ullman. Algorithmic stability for adaptive data analysis. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pp. 1046-1059, 2016.
Samyadeep Basu, Philip Pope, and Soheil Feizi. Influence functions in deep learning are fragile. arXiv preprint arXiv:2006. 14651, 2020.
Olivier Bousquet and André Elisseeff. Stability and generalization. Journal of machine learning research, 2(Mar):499-522 2002.
Gregory Cohen, Saeed Afshar, Jonathan Tapson, and André van Schaik. Emnist: an extension of mnist to handwritten letters. arXiv preprint 0ro.vv/702.05333 2017.
Dennis Cook. Detection of influential observation in linear regression. Technometrics, 19(1): 15-18, 1977.
Thomas M Cover and Joy A Thomas. Elements of information theory. Wiley-Interscience, 2006.
Vitaly Feldman and Thomas Steinke. Calibrating noise to variance in adaptive data analysis. In Conference On Learning Theory, pp. 535-544, 2018.
Amirata Ghorbani and James Zou. Data shapley: Equitable valuation of data for machine learn- ing. volume 97 of Proceedings of Machine Learning Research, pp. 1242-2251, Long Beach, California, USA, 09-15 Jun 2019. PMLR.
Aditya Golatkar, Alessandro Achille, and Stefano Soatto. Forgetting outside the box: Scrubbing deep networks of information accessible from input- observations. Proceedings of the Eu- ropean Conference on Computer Vision (ECCV), 2020.
Ian Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In International Conference on Learning Representations, 2015. URL http://
2xxil..rrg/abs/1122.55577 6572
Ming Gu and Stanley C Eisenstat. Downdating the singular value decomposition. SIAM Journal on Matrix Analysis and Applications, 16(3):793-810, 1995.
Moritz Hardt, Benjamin Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. arXiv preprint arXiv:1509.01240 2015.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference computer vision and pattern recognition, pp- 770-778, 2016.
Like Hui and Mikhail Belkin. Evaluation of neural architectures trained with square loss vs cross- entropy in classification tasks. arXiv preprint arXiv:2006. 07w00000000702.... 2020.
Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural tangent kemnl:: Convergence and gen- cralization in neural networks. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- Bianchi, and R. Gameet Advances in Neural Information Processing Systems 31, pp. 8571- 8580. Curran Associates, Inc., 2018.
10

---

Published as a conference paper at ICLR 2021
Kaggle. Dogs vs. Cats, 2013. URL Utt.ttps///wwwkaagaaacccc//////
overview
Angelos Katharopoulos and Francois Fleuret. Not all samples are created equal: Deep learning with importance sampling. volume 80 of Proceedings of Machine Learning Research, pp. 2525-2534, Stockholmsmässan, Stockholm Sweden, 10-15 Jul 2018. PMLR.
Pang Wei Koh and Perey Liang. Understanding black-box predictions via influence functions. vol- ume 70 of Proceedings of Machine Learning Research, pp. 1885-1894, International Convention Centre, Sydney, Australia, 06-11 Aug 2017. PMLR.
Ron Kohavi, George H John, et al. Wrappers for feature subset selection. Artificial intelligence, 97 (1-2):273-324, 1997.
Jachoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl- Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve linear models under gradient descent. In Advances in neural information processing systems, pp. 8572-8583, 2019.
Ping Li, Trevor J Hastie, and Kenneth W Church. Very sparse random projections. In Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 287-296, 2006.
Qianxiao Li, Cheng Tai, and Weinan E. Stochastic modified equations and adaptive stochastic gradient algorithms. volume 70 of Proceedings of Machine Learning Research, pp. 2101-2110, International Convention Centre, Sydney, Australia, 06-11 Aug 2017. PMLR.
Ana C Lorena, Luis PF Garcia, Jens Lehmann, Marcilio CP Souto, and Tin Kam Ho. How complex is your classification problem? survey on measuring classification complexity. ACM Computing Surveys (CSUR), 52(5):1-34, 2019.
Andrew L. Maas, Raymond E. Daly, Peter Pham, Dan Huang, Andrew Y. Ng, and Christopher Potts. Learning word vectors for sentiment analysis. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguisties: Human Language Technologies, pp. 142-150. Portland, Oregon, USA, June 2011. Association for Computational Linguistics. URL http:
//www. ac www.ww.www......... org/ wwigg//nthin http///tttoooo//111101
Stephan Mandt, Matthew Hoffman, and David Blei. Stochastic gradient descent as approximate bayesian inference. The Journal of Machine Learning Research, 18(1):4873 4907, 2017.
Fangzhou Mu, Yingyu Liang, and Yin Li. Gradients features for deep representation learning. arXiv preprint 2rXiv:2004.05529, 2020.
Ernest Mwebaze, Timnit Gebru, Andrea Frome, Solomon Nsumba, and Jeremy Tusubira. icassava 1019fine-graines visual categorization challenge. arXiv preprint wrXiv:1908.02900 2019.
Jeffrey Pennington, Richard Socher, and Christopher D. Manning. Glove: Global vectors for word
representation. In Empirical Methods in Natural Language ProiegeeePPooe Processing (EMNLP), pp. 1532-1543,
2014. URL http: www. aclweb. org/ antholooyy/D111111
Maxim Raginsky, Alexander Rakhlin, Matthew Tsao, Yihong Wu, and Aolin Xu. Information- theoretic analysis of stability and bias of learning algorithms. In 2016 IEEE Information Theory Workshop (ITW), pp. 26-36 30. IEEE, 2016.
Rissanen. Fisher information and stochastic complexity. IEEE Transactions on Information Theory, 42(1))40047, Jan 1996. ISSN 0018-9448. doi: 10. 10.1109/88.48177
Andrew M Saxe, Yamini Bansal, Joel Dapello. Madhu Advani, Artemy Kolchinsky, Brendan D Traccy, and David D Cox. On the information bottleneck theory of deep learning. Journal of Statistical Mechanics: Theory and Experiment, 2019(12): 2019.
Ravid Shwartz-Ziv and Alexander A Alemi. Information in infinite ensembles of infinitely-wide neural networks. volume 118 of Proceedings of The 2nd Symposium on Advances in Approximate Bayesian Inference, pp. 1-17. PMLR, 08 Dec 2020.

---

Published as a conference paper at ICLR 2021
Ravid Sivartz-Ziv and Naftali Tishby. Opening the black box of deep neural networks via informa- tion. arXiv preprint 10XXv:170330010000 2017.
Christian Szegedy. Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, lan Goodfel- low, and Rob Fergus. Intriguing properties of neural networks. In International Conference on Learning Reprexenlations, 2014. URL http: http::/aaxxi..rrrrtt org/ abs 1312. 62.999999
Mariya Toneva, Alessandro Sordoni, Remi Tachet des Combes, Adam Trischler, Yoshua Bengio, and Geoffrey J. Gordon. An empirical study of example forgetting during deep neural network learning. International Conference on Learning Representations, 2019.
Antonio Torralba and Alexei A Efros. Unbiased look at dataset bias. In CVPR 2011, pp. 1521-1528. IEEE, 2011.
Max Welling and Yee Whye Teh. Bayesian learning via stochastic gradient langevin dynamics. In Proceedings of the 28th International Conference International Conference Machine Learning. ICML' 10M,L11, pp. 681-688, Madison, WI, USA, 2011. Omnipress. ISBN 9781450306195.
Paul L. Williams and Randall D. Beer. Nonnegative decomposition of multivariate information.
CoRR, abs/1004.2515, 2010.
Yinjun Wu, Edgar Dobriban, and Susan Davidson. Deltagrad: Rapid retraining of machine learn- ing models. arXiv preprint arXiv:2006. 14755, 2020.
Jinsung Yoon, Sercan O Arik, and Tomas Pfister. Data valuation using reinforcement learning. arXiv preprint (XXi:1999.116711 2019.
Luca Zancato, Alessandro Achille, Avinash Ravichandran, Rahul Bhotika, and Stefano Soatto. Pre- dicting training time without training. Advances in Neural Information Processing Systems 33, 2020.
A ADDITIONAL RESULTS AND DETAILS
In this section we present additional results and details that were not included in the main paper due to the space constraint.
A. APPROXIMATING UNIQUE INFORMATION WITH LEAVE-ONE-OUT KL DIVERGENCE
In the main text we discussed that I(W; S_;) can upper bounded with (L(PA(W S) || pa(w S_;)). In this subsection evaluate these quantities on toy 2D dataset. The dataset has two classes, each with 40 examples, generated from a Gaussian distribution (see Fig. 3ap. We consider training linear regression on this dataset using stochastic gradient descent for 200 epochs, with batch size equal to and 0.1 learning rate. Fig. 3lotss the distribution PA(W (). Fig. 3c the
distribution PA (w S_,), while Fig. 3d plots the distribution P S S_ 2/), On this example
we get [(W; 24 S_:) 1.3 and (p (5) PA w/ S_:)) 3.0.
2.0
-0.46
-0.47
-0447
-0.47
05
-044
-0.29
0.0
0.50
-35
02
05
3.0
15
0.22
0.34
0.38
0332
0.34
0.56
0.34
0.30
(a) Data
(b) PA(
(w
(c) (A S_.)
(d) B.EPP S_ a/)
Figure 3: A toy dataset and key distributions involved in upper bounding the unique sample infor- mation with lcave-one-out KL divergence.
12

---

Published as a conference paper at ICLR 2021
A.2 WHICH EXAMPLES ARE INFORMATIVE?
In this subsection we present the most and least informative examples for two more classification tasks: MNIST 4 classification with MLP and Kaggle cat vs dog classification with pretrained ResNet- 18 (Fig. D. The results indicate that most informative examples are often the challenging and atypical ones, while the least informative ones are easy and typical ones. For the MLP network on MNIST 4 vs 9 we set t = 2000 and 7 0.001; for the ResNet-18 18 on cats vs dog classification t 1000 and 0.001; and for the ResNet- on iCassava dataset 5000 and r) = 0.0003.
B
Least informative samples
250
9
9
9
9
4
9
4
4
Most informative samples
9
4
9
4
c
4
2e-4
A
Least informative samples
200
cat
cat
200
150
Most informative samples
100
122
10
0.
InSTETT IOSTT 30
Figure 4: Functional sample information of samples in MNIST 4 vs 9 classification task (top) and Dogs vs. Cats (bottom), with A: histogram of sample informations, 10 least informative samples, C: 10 most informative samples.
A.3 ACCURACY OF THE LINEARIZED NETWORK APPROXIMATION
In this subsection we present additional details experiments presented in Table T In all datasets used the validation set also has 1000 samples. The fully connected network, MLP, consists of single layer of 1024 ReLU units. The architecture of the CNN used for the experiments Table is as follow.
Layer
Layer parameters
Cony.
32 filters, 4x4 kernel, stride 2, padding 1, ReLUU activation
Cony.
2 Cony.
32 filters, 4x4 kernel, stride 2. padding 1. ReLU activation
64 filters, 3x3 kernel, stride 1. padding = 0. ReLU activation
Cony,
filters, 3x3 kerne,, stride I, padding 0, ReI.U activation
Fully connected
256 ReLU neurons
Fully connected
lincar unit
In all our experiments, when using pretrained ResNets, we disable the exponential averaging of batch statistics in batch norm layers. The exact details of running influence functions and linearized neural network predictions are presented in Table
A.4 How MUCH DOES SAMPLE INFORMATION DEPEND ON ALGORITHM?
The proposed information measures depend on the training algorithm, which includes the archi- tecture, seed, initialization, and training length. This is unavoidable as one example can be more informative for one algorithm and less informative for another. Nevertheless, in this subsection, we test how much does informativeness depend on the network, initialization, and training time. We consider the Kaggle cats vs dogs classification task with 1000 training examples. First, fixing the training time = 1000, we consider four pretrained architectures: ResNet- 18, ResNet-34, ResNet- 50, and NenseNet-121. The correlations between F-SI scores computed for the four architectures
13

---

Published as a conference paper at ICLR 2021
Experiment
Method
Details
Brute force
2000 epochs, learning rate 0.001, batch size 1000
MNIST MIP (scratch)
Infl. functions
LiSSA algorithm, 1000 recursion steps, scale 1000
Lincarization
2000, leamiing rate
Brute force
1000 epochs, learning
0.01, batch 1000
MNIST CNN (scratch)
Infl. functions Lincarization
LiSSA algorithm. 1000 recursion steps. scale 1000
1 1000, leaming rate 0.01
Brute force
1000 epochs, learnin rute 0.002. batch size 1000
MNIST CNN (pretrained)
Infl. functions
LiSSA algorithm, 1000 recursion steps. scale 1000
Lineurization
t 1000, leamingg rute 0.002
Brute force
500 epochs, learning
0.001, batch size 500
Cats and dogs
Infl. functions
LiSSA algorithm. 50 recursion steps, scale 1000
Linearization
t 1000, learming rate 0.001
Table 2: Details of experiments presented Table |
For influence functions, we add a dumping term with magnitude 0.01 whenever l2 regularization is not used (i.e. 0).
ResNet-18
0.375
250
1.000
0.919
0.556
0.850
0.785
500
0.755
6.898
0.876
ResNet-34
0.244
1.000
0.333
0.287
1000
ResNet-50
2000
0.256
0.992
0.882
DenseNet-121
0.319
0.767
0,452
1.000
4 4000
890
0.998
ResNet-1a
ResNet-34
ResNet-S0
DenseNet-122
t= 0
0.788
0.876
0.948
0.822
0.008
1.000
250
t= 500
t= 1000
t t020
t 4000
La
(a) Varying architecture
(h) Varying training length
Figure 5: Correlations between functional sample information scores computed for different archi- tectures and training lengths. On the left: correlations between F-SI scores of the 4 pretrained networks, all computed with setting = 1000 and r 0.001. On the right: correlations between F-SI scores computed for pretrained 1esNet-18s, with learning rate v 0.001, but varying training lengths i. All reported correlations are averages over 10 different runs. The training dataset consists of 1000 examples from the Kaggle cats vs dogs classification task.
are presented in Fig. 5a We see that F-SI scores computed for two completely different architec- tures, such Re and DenseNet-12 121 have significant correlation, around 45%. Furthermore, there is a significant overlap in top 10 most informative examples for these networks (see Fig. 6). Next, fixing the network be pretrained ResNet-18 and fixing the training length /. 1000, consider changing initialization of the classification head (which is not pretrained). In this case the correlation between F-SI scores 0.364 = 0.066. Finally, fixing the network be ResNet-18 and fixing the initialization of the classification head, we consider changing the number of iterations in the training. We find strong correlations between F-SI scores of different training lengths (see Fig. 5b).
MNIST vs SVHN experiment for DenseNet-121. In this paragraph redo the MNIST vs SVHN experiment (Fig 2ap but for different network, a pretrained DenseNet-121, to test the de- pendence of the results on the architecture choice. The results are presented in Fig. 7a and qualitatively identical to the results derived with a pretrained ResNet18 (Fig. 2ap.
Data summarization with change of architecture. To test how much sample information scores computed for one network are useful for another network. we reconsider the MNIST vs 9 data summarization experiment (Fig. 2ch. This time compute F-SI scores for the original net-
14

---

Published as a conference paper at ICLR 2021
Dog
Cat
Cat
Dog
Cat
Dog
Cat
Dog
Doy
(a)
ResNet-18
Cat
Cat
Cat
Dog
Car
Cot
Cat
Dog
Cat
Cat
(b) ResNet-50
Cat
(c) DenseNet-12)
Figure 6: Top 10 most informative examples from Kaggle cats vs dogs classification task for three pretrained networks: ResNet-18, ResNet-50, and DenseNet-121.
0.9
Text accuracy
0.8
0.6
0.7
0.4
0.2
0.5
benon (taratvv))
0.0
2
3
0.0
0.2
0.4
0.6
0.8
Informativeness of example
10-4
Ratio removed examples
(a) MNVT vs SVHN experiment DenseNet-121
(b) MNIST vs summarization
Figure 7: Testing how much F-SI scores computed for different networks qualitatively differ- ent. On the left: the MNIST vs SVHN experiment with pretrained DesneNet-12) instead pretrained ResNet-18. On the right: Data summarization for the MNIST 4 vs 9 classification task, where the F-SI scores are computed for a mee-iddeen-laye network, but a two- wwo-hidden-laye network trained to produce the test accuracies.
work with one hidden layer, but train a two-hiddden-layer neural network (both layers having 1024 ReLU units). The data summarization results presented in Fig. 7b areare qualitatively and quantitively almost identical to the original results presented in the main text. This confirms that F-Si scores computed for one network can be useful for another network.
A.5 DETECTING INCORRECT EXAMPLES
In this subsection we present results on detecting mislabeled examples for two more classification tasks: MNIST 4 vs classification with an MLP (Fig. 8a) and Kaggle cat vs dog classification with a pretrained ResNet-18 (Fig- (b). The results are qualitatively the same and assert that, indeed, mislabeled examples are more informative,
average. For the ML.P network we set 2000 and 7 = 0.001; for the ResNet-18 18 on the cats vs dog classification task 1000 and r) = 0.001; and for the ResNet-18 the iCassava dataset (in the main text) set t 10000 and 17 0.0001.
A.6 DETECTING
SUB- -LB-CLASSSS
Using CIFAR-10 images, create dataset of "Pets vs Deer": Pets has 4200 samples and deer 4000. The class pets consists of two unlabeled sub-classes, cats (200) and dogs (4000). Since there relatively few images, expect each carry more unique information. Indeed, Fig.
15

---

Published as a conference paper at ICLR 2021
1c5
1c5
2,0
comppted
comupted
1.5
Density
Density
0.8
0.6
0.2
0.0
0.0
0.4
0.6
0.8
1.0
0.00
0.50
1.00
1.25
1.50
Informativeness of
10-4
Informativeness
example
10-4
(a) MNIST 4 vs
(b) Kaggle Dogs vs Cats
Figure 8: Additional results comparing the information content of samples with correct and incorrect labels on MNIST 4 vs and Dogs vs Cats.
shows that this is the case, suggesting that the F-SI can help detecting when an unlabeled sub-class of larger class under-sampled. In this experiment we set & 10000 and r 0.0001.
1e6
0.2
0.0
Infomativeness example
Figure 9: Histogram of the functional sample information of samples from the three subclasses of the Pets vs Deer. Since the sub-class "cat" is under-represented in the dataset, cat images tend to have on average more unique information than dog images, even they belong to the same class.
A.7 DETECTING ADVERSARIAL EXAMPLES
Szegedy al. (2014) shows that imperceptible perturbation to an image can fool neural network into predicting the wrong label (adversarial examples). Goodfellow et al. (2015) further shows that adding adversarial examples to the training dataset improves adversarial robustness and general- ization (adversarial training), which suggests that adversarial examples may be informative for the training process. To test how informative adversarial examples are with respect to normal ones, we consider the Kaggle Cats vs Dogs classification task, consisting of 1000 examples. On this task fine-tune pretrained ResNet-18 18 and for 10% of examples create successful adversarial examples using the FGSM method of (Goodfellow et al. 2015) with 0.01. Then, for these 10% of ex- amples, we replace the original images with the corresponding adversarial ones. With the resulting dataset, consider new pretrained ResNet- 18 and compute F-ST for all training examples, setting t = 1000 and 7 0.001. The results reported in Fig. confirm that adversarial examples are on average more informative than normal ones. Furthermore, the results indicate that one can use F-S1 to successfully detect adversarial examples.
A.8 INFORMATIVE EXAMPLES SENTIMENT ANALYSIS
So far focused on image classification tasks. To test whether the proposed method works for other modalities, we consider a sentiment analysis task, consisting of 2000 samples from the IMDB movie reviews dataset (Maas et al. 2011). We convert words to 300-dimensional vectors using the pretrained GloVe 6B word vectors (Pennington et al. 2014). Then each review is mapped to a vector by averaging all of its word vectors. On the resulting vector apply fully connected neural
16

---

Published as a conference paper at ICLR 2021
164
adverariii normal
0.5
2.5
Informativeness
10-4
Figure 10: Histogram of the functional sample information of samples of the Kaggle cats vs dogs classification task, where 10% of examples are adversarial examples.
network with hidden layer, consisting of 2000 ReLU units. We then compute F-SI scores for all training examples, setting 10000 and r 0.003. Likewise to the case of images, we find that least informative examples are typical and easy (often containing many sentiment-specifie words), while the most informative examples are more nuanced and hard. Additionally, we find that there -16% correlation between the informativeness and length review, possibly because averaging many word vectors makes long reviews similar to each other.
A.9 REMAINING DETAILS
In the experiment of measuring which data source is more informative (Fig. 2a
we set t 20000
and 1) 0.0001. In the experiment of data summarization (Fig. 2c set / 2000 and r 0.001.
B PROOFS
The proof of eq. ( follows from the following more general lemma, applied to the conditional
distribution PA (a( [S -i 24) and its marginal r(x[S_i).
Lemma B.1. Let p(xly) be conditional probability density function, and let p(x) [p(r)y)dP(y) denote its marginal distribution. Then, for any distribution q(z) we have
KL(p(xlu) ((x)) (L(p(x))) [1]()) - ([(p(x)llq(x))
(L(p(rl)) ((x))
where [ g(x)) & J log p(zly)
9(2) (z ( dxdP(y) denotes the conditional version of the
KL divergence (Cover& & Thomus
2006 Section 2.5).
Proof. The last inequality follows from the fact that the KL-divergence is always non-negative. We now prove the first equality:
(L(p(zl)) ll ((()) KL(p(z) d(x))
p(x|z) p(zlv)drdP()) - / log p(z)
log
((x)) p(x)dr
q(x)
(a)
log p(=ly)
q(z) p( dxdP(v) f log p(x)
(ʃ p(ol))dP(w)) dr
q(x))
(b)
log
p(aly)
((x) p( p(xly)ddddPl
log q(x)) p(xll)) p(xl))dxdP())
p(x))
log p(zly)
log p(x)
q(x)) p(aly)dadP(s)
((x)
/ log p(zly) p(zly)drdP())
p(x)
(L(p(xlv) lI p(x)),
17

---

Published as a conference paper at ICLR 2021
where in (a) we use that by definition p(z) p(zly))P(() and in (b) exchange the order of integration.
Propositions 3.2 and 4.2 are trivial, since they just assert that KL divergence between two Gaus- sian distributions with equal covariance matrices E and with means P1 and #22 equal to - (111-2)²'> (N) p2). We present the proof of Proposition 5.1
Proposition B.2 (Prop. 5.1 restated). Let the loss function be regularized MSE, w" be the global minimum of and algorithms ASGD and AERM be defined as in the main text. Assuming A(w) is approximately constant around w and SGD's 's steady-state covariance remains constant after removing an example, we have
SI Zi, AsGn) = SIn(2i, AERM)
(w" -w- x² w-.h;
(18)
2
where E is the solution of
HE + ΣH ? 5 N(w))
(19)
with = (V + XI) being the Hessian of the loss function.
Proof. Assuming A(w) is approximately constant around w", the steady-state distributions of Gaussian distribution with mean w² and covariance E such that:
12
HE + ΣH =
" b A(""),
(20)
where = (V..
AT) is the Hessian of the loss function (Madt et al. 2017
This can be verified by checking that the distribution ((;; w", Σ) satisfies the Fokker-Planck equa- tion (see Sec. DD. Having PAsco S) N(w; w .2) and PAsco (w SS.) N((w; w --;,, we have that
SI(,,, AscD) 2 ((w" - w-.) TE wi.) +.EEEEE + log E- d).
(21)
By the assumption that SGD steady-state covariance stays constant after removing example, i.e. E_; = Σ, equation (2T) simplifies to:
KL Asem (w 5) P Asmo (w S_,)) 2 (w" -- -w- w=
Asem
(22)
By the definition of the AERM algorithm and smooth sample information, this is exactly equal to Sly(2,, AERM).
C SGD NOISE COVARIANCE
9s. and g A D Ik. where k; are sampled independently from (I,...,nn) uniformly at. Then
Assume we have examples and the batch size is 6. Let gi A VwCi(w), 9 A Σm
b gh. - 9 -) gk:
Cov Coviğ.
E
E (gk:
(g). 1
1
(g.
9)(9; =TTTT
bm
i=1
1
9:9
T
696
b
i=1
18

---

Published as a conference paper at ICLR 2021
We denote the per-sample covariance, b Cov (ā. gl with A(w):
A(w) Σ 9:9:
9g" GG -g9" n
where E Rdxn has 9i ss as its columns. We can see that whenever the number of samples times number of outputs is less than number of parameters (nk < d), then A(w) will be rank deficient. Also, note that if we add weight decay to the total loss then covariance A A(w) will not change, as all gradients will be shifted by the same vector.
D STEADY-STATE COVARIANCE OF SGD
In this section we verify that the normal distribution (N; ((;:""; Σ), with w" being the global minimum of the regularization MSE loss and covariance matrix E satisfying the continuous Lyapunov equation (w") A(w") 12 We assume that (a) Aww) is constant in small neighborhood of w= and (b) the steady-state distribution is unique. We start with the Pokker-Planck equation:
H HΣ 3 A
is the steady-state distribution of the stochastic differential equation of eq.
8p(w,t) 01 Σ
i Ow,
82
InV (ww)p( ()
dw,,ūre (Aw)ssp((u;()) ()]
2b j=1
If p(w) Nww w Σ) exp ( (=) (w w²) }} is the steady-state distribution, then the Fokker-Plann becomes:
d 0= Σ
11²
0²
In w. [(w)((w)
+
Sw,Ow, [A()ssp(w))
(23)
Ow.
2b
1=1
i=1
In the case of MSE loss:
V Vwl(w== (f((=))(((zH) yv) + A Vf((X)(((X Y) + Aww,
[2 Vo(==) + \laVoo(())) = V/6(X)V56X)) + AT.
k=1
Additionally, for p(w) the following two statements hold:
p(w) = -p(w))) (w - w²),
ow.
8²
ow,dwy p(w) = DT + p(w) (w - w²)2, - w²),
where Σ,1 is the i-th row of E-1, Let's compute the first term of (3):
VV w. ((w)p(w)] (p(w) (V.6(()) + Aw;)) Vu, p(w))/ (w -ww) w²)l
Ow
d
= p(w)tr (Vf((X)V + AT) - ppw)) Σ (V
- Y) + Awa)) E, (w - w²)
1=1
-P( - p()) ((f(x) Y) -Y V + \w= Wー w²)
(24)
As w* is a critical point of C(w), we have that Voo (X) Y) + Aw"
0. Therefore, we
can subtract p(w) ((fw- (X) - YY (X)( + A(wx) 1 E w²) from 24
Σ Ow: Vu, [(w)(())
= -H) p(w) (If(X) - for (f))) X(w - -w+)") 1-)))->((m w²)
=((W)t((H) p(w)(w -² (V + AI) I-'(w - -w")
= =P(W)u(HH p(w)(w - )²² H (w w²)
(25)
19

---

Published as a conference paper at ICLR 2021
ISOTROPIC CASE: A(w) o²
In the case when A(w) = I2. we have
+ + (p(w)]]E dw,,w (())spP(W)] = v'u((V)((w)) = -:::====-ppiiiiiii -o'p(w))t(E=1)
(w -====) ==)1
Putting everything together in the Fokker-Planch we get:
7 (p(w)tr(H) - p(w)(w "' (w: w"))
+ n²2
26 (
(w - =0)
It is easy to verify that Σ- 2b H is valid inverse covariance matrix and satisfies the equation above. Hence, it is the unique steady-state distribution of the stochastic differential equation. The result confirms that variance is high when batch size is low or learning rate is large. Additionally, the variance is low along directions of low curvature.
no²
NON-ISOTROPIC CASE
We assume A(w) is constant around w" and is equal to A. This assumption is acceptable to degree, because SGD converges to a relatively small neighborhood, in which we can assume A(w) to not change much. With this assumption,
J2 Ow, [Nsjp(w)] = Σ Ars p(w) + p(w) - "² ( w²)
Σ
=-p(w))r(E + p(w) Σ
As. (E (w w* (w w - )
2,
--(()tt(E-1)) A) + (( (w w (w w w+)² --)
--(())t((--)) + p(w)(w -
w² w²))
(26)
It is easy to verify that if EH HΣ ? A. then terms in equations 25 and 26 will be negatives 7
of each other up to a constant 26 implying that p(w) satisfies the Fokker- equation. Note that
Σ-1 26 HA also satisfies the Fokker-Planck but will not be positive definite unless H and A
commute.
E FAST UPDATE OF NTK INVERSE AFTER DATA REMOVAL
For computing weights or predictions of linearized network some time t, we need to compute the inverse of the NTK matrix. To compute the informativeness scores, need to do this inversion n time, each time with one data point excluded. In this section, we describe how to update the inverse of NTK matrix after removing one example in O(n²k²) time, instead of doing the straight- forward (n ))) computation. Without loss of generality let's assume we remove last r rows and corresponding columns from the NTK matrix. We can represent the NTK matrix block matrix:
An
A12
θ
A21
A22
The goal is to compute
ATI from 0,'
We start with the block matrix inverse formula:
An
A12
F
Fr A
A
O5¹
(27)
A21
A22
A A
122
where
Fn = Au - A A21;
(28)
Frz Azz Az1 A A12.
(29)
20

---

Published as a conference paper at ICLR 2021
From
28 have A1 Fi1 A12 A21. Applying the Woodbury matrix identity this
get:
Aii Fn Fn (A22 A21 Fi A22)
(30)
This Eq. (30p gives the recipe for computing ATi- Note that Fii can be read from 0, using 27
A12, Ag1. and A22 can be read from e. Finally, the complexity of computing A using (30) Onn* k-) if we remove one example.
F ADDING WEIGHT DECAY TO LINEARIZED NEURAL NETWORK TRAINING
Let us consider the loss function [(w) = - gradient descent described by the following ODE:
i= (:(w) + - 1 - wol2 12 In this case continuous-
(t) V ()) Y) ())((c(t) wa)
(31)
(x wo) + fo(X) -Y) n)((o(t)) - wo)
(32)
= -n(Va.((X)VV.x(xx) (X)(((t)))))) - wo) + (x)))((X) (- (o)(( Y).
(33)
Let (() A wt) wo. then we have
(t) Aw(t) b.
(34)
Since all eigenvalues of A are negative, this ODE is stable and has steady-state
w -6
(35)
VV (6(X)Vvvfoo))) + V
(36)
The solution wt) is given by:
w(t) = w² + E - w²)
(37)
= = - -[-EAl) Ell)
(38)
Let i A V.. and O, - V., V vo(()). the SVD Vx.)(()) is UDV", then O. UDU and O, VDVT. Additionally, we can extend the columns of U to full basis of nd (denoted with Ú) and append zeros to D (denoted with D) to write down the eigen decomposition ① ÚÚT, With this, we have (9 + -1)-1 ÜD + AI) UUT, Continuing
38 we have
(t) e "'"W""
(39)
= (I - e (0, + XI V
(40)
= (1 AD + UID - fo(x))
(41)
= Ú e -(
(42)
Ú(1 ((+MN
fo()))
(43)
Ū(I m((+AI) (
(44)
(D -D
where 2
E Rdxnk Denoting = (D+ + AI) D and continuing.
0
w(t) Ú(I (DD+NN) ZVT fo(X))
(45)
= U(T - e - D
(Y - -o()))
(46)
UZ(I -MD+NNI -f(())
(47)
=UZV"V(I - -MDDMM (Y so(X))
(48)
=UZVT C -
(49)
-V) - (6((x)
(50)
21

---

Published as a conference paper at ICLR 2021
Solving for outputs.
Having wtt) derived, we can write down dynamics of f((x) for any
ft(z) fo(æ) + V vw.f(z)'((()
(51)
fo(æ) + V Vv.h(==)VV..((()))))))) + - -
(52)
fu()) + Qu(z, A1) - - fo(X)).
(53)
22


Reviews:
[{"review_id": "g9zVJ1MZc9H", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper is written in a very bad way and to my opinion is not acceptable without a significant overhaul. First, there are many typos. For instance, word out in page 1 should be our. Secondly, and much more importantly, notations in the paper are very ambiguous and misleading. For instance, in the \"prerequisites and notations\" section it is mentioned that $A(w|S)$ is a \"conditional distribution\". Yet in the same section, it says that $A(S)$ is the \"output random variable\" of the algorithm. So it is absolutely ambiguous what the notation $A(.)$ actually shows. Does it show a probability distribution? or it shows a random variable? You would guess that if you keep reading the paper, the ambiguity goes away, but you are wrong. As you read through the paper, $A(.)$ is used interchangeably for both a random variable and a probability distribution which absolutely ambiguous. For instance, when you see $KL(A(w | S) || A(w | S_{−i}))$ in equation 3 you would argue that $A(w|S)$ refers to a probability distribution that in Prop. 3.2. you would see that $A(S)$ is used as a random variable. Why are the authors use notation $A(.)$ for both a random variable and a probability distribution. I think to remove ambiguity, all probability distributions should be shown with $P(.), p(.), f(.)$ or things of that nature. I would expect to see this fixed in any future revision of the paper. Also, notations like $m(.)$ are not common for probability distributions and make the paper unreadable. \n\nThe role of smoothing in the paper is not clearly discussed and analyzed in the paper. I understand that it is required to make the KL divergence bounds work by adding continuous noise, but are the authors assume assumptions like this just to get some theoretical bounds? Is such an assumption, a valid assumption? and why? How does it change the results compared to real-world applications?\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "X4X9WVxm0eT", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Update: Thanks for the response. I agree with the other reviewers that the updates have improved the paper.\n\nThis paper presents a way of estimating the informativeness of a single training data point wrt a neural networks weights or it's output function.\n\nOverall I think this paper is well written and interesting, but could benefit from links to other areas of the ML literature (detailed below) and further explanation of some puzzling experimental results.\n\nThe notion of unique information is very similar to the notion of strong relevancy in feature selection (in \"Wrappers for Feature Subset Selection, Kohavi & John, Artificial Intelligence 1996). A feature is strongly relevant iff p(y|x,\\omega) != p(y|\\omega), that is if the presence of the feature changes the conditional distribution of the output conditioned on all the other features. In the same way a datapoint has unique information if the presence of it changes either the weight distribution or the output function. This much follows from the submitted paper. However the Kohavi & John paper also formalises a notion of weak relevance, which means that the presence of a feature changes the conditional distribution of the output given some subset of the other features. To capture all the information in a feature set you need all the strongly relevant features and some of the weakly relevant features (weak relevance means that the information appears multiple times in the feature set but it might not be in the strong relevant features so you need some of them to cover it). There is an information theoretic treatment of strong & weak relevance for feature selection in Brown et al \"Conditional likelihood maximisation: a unifying framework for information theoretic feature selection\", JMLR 2012 which may be of interest as it aligns with some of the presentation in the submitted paper. This notion of weak relevance would help formalise the discusson of least informative datapoints and the data summarisation paragraph in the experiments. The weakly relevant *datapoints* are those which describe the typical distribution of the dataset, a model needs some of them to properly capture the structure, but many of them provide the same information (and thus none will be uniquely informative) and that information may not appear in the uniquely informative datapoints.\n\nThe results in Table 1 are interesting, but there is little discussion of why the linearised formulation fails to capture the informative examples in the CNN trained from scratch. If the estimates diverge when the models become very different, then that is an important issue which should be discussed in more detail, so a reader can determine if the technique will be applicable to their use case.\n\nThe assumption that the SGD steady state covariance is unchanging implies to me that the example isn't very informative as otherwise it would change the loss landscape and thus change the covariance of SGD. Could the authors comment on the strength of this unchanging covariance assumption?\n\nThe informative-ness of datasources section seems to implicitly assume that the label distributions are balanced between the different sources, as otherwise the presence of rarely viewed labels could cause very large differences in the weights (which appears to cause trouble with the approximation technique given table 1). If this is required then it should be noted in the appropriate part of the discussion, otherwise could the authors comment on why it's not required?\n\nMinor comments:\n\n- The referencing style is inconsistent: some references say ICML, some give the volume in PMLR for that year's ICML, arxiv is cited in several different ways etc.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "RjuVgZlkVpJ", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes a measure to compute the information of each training sample. The paper shows that this measure can be computed for a large DNN without having to train the network. The authors show that this measure can be used for applications like data summarization and detection of corrupted data. \n\nMy main concern is that the information measure depends on the initialization, training time, and network architecture. For e.g. the F-SI scores seem to change over time in table 5. Hence, one needs to re-compute the measure for the training samples, with a  change in initialization and training time. The complexity of computing the FI-scores for $m$ examples is $O(n^2 m)$. For MNIST, this is at least $10^{10}$ flops for computing measure of 100 examples. I believe, the authors should discuss efficient recomputation of the measure in case of a change in the algorithm parameters or the error involved if we don't re-compute the measure.\n\n\nMy other concerns are the following:\n1. The data summarization experiments and the detection of more information data sources and examples are network-specific (in this case, pre-trained Resnet 18). It will be more interesting to see if these transfer to other networks. For example, in data summarization experiments, it will be interesting to see if the most informative examples for pre-trained Resnet 18 also help to train another network. The same question holds for SVHN vs MNIST. \n2. In conclusion, the authors claim that their measure can be used for computing the information for a group of samples. However, in the data summarization experiments, the measure is computed for each sample as a separate entity, while groups of samples are removed at a time. Hence, is it possible to compare the current results with an efficient group-theoretic measure for removing groups of samples? I am concerned because simple examples may not have information individually but as a group may hold important information to train a network.\n3. In many sections, the authors have forgotten to mention the network architecture they used to get the plots e.g. in data summarization and detection of under sampled sub-classes experiments. It will be great if the authors can show how the results in these experiments change with a change in architecture, given that the measure depends on the architecture.\n\nI have verified the proofs. They are easy to read and understand. My scores are slightly on the lower side because I believe the computation is too brittle to changes in the algorithm parameters like training time and initialization. I am happy to discuss this with the authors and other reviewers during the discussion period.\n\n\n***After Rebuttal***\nI have read the reviews by other reviewers and the responses of the authors to the questions posed by other reviewers. I enjoyed the additional experiments that the authors added to the paper during the rebuttal. The paper has shown interesting observations on the informative samples present in real-world datasets for different architectures. However, I still believe the method proposed by the paper is too inefficient for simple algorithm changes like changes in initialization. Hence, I am keeping the score the same after the rebuttal.", "extra_scores": {}, "extra_text": {}}, {"review_id": "PNTbyD7UImR", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes a way to estimating sample information in the\ncontext of neural networks.  The authors propose to simplify the definition \nby using a first-order approximation of an arbitrary network's architecture\nand the mean squared error as the loss function.  In addition, a smoothing\nmatrix obtained around the network's steady state is introduced to minimize the\nuncertainty due to limited realizations of a stochastic optimization process.\nThe method is applied to several image classification tasks for illustration.\nThen it is proposed to be used to summarize a dataset, i.e., to remove redundant\nexamples that have minimal impact to training results.\n\nThe derivation of the measure is an interesting exploration of the\nrelationship between an individual sample's information content and\nthe neural network's final trained weights or the network's use of\nsuch weights (the values of the decision function).  This contributes\nto a better understanding of how information is leveraged by neural networks.\n\nThe practical value of the measure itself, on the other hand, is\nquestionable beyond the use of neural networks.\n\nIs there a way to characterize how intrinsic this measure is,\ni.e., to what extent is it tied to the use of neural networks as\nthe classifier?  Note that there are much simpler, well studied ways\nto estimate how normal or abnormal a sample is compared to the rest in\nits class and how much it affects classification difficulty\n(see the above mentioned survey).  Going through these complicated\ncalculations for estimation, do you arrive at something that well\ncorrelates with many others derivable using simpler methods?\n\nYou may want to compare your data summary to what could be obtained\nusing, e.g., \"The Condensed Nearest Neighbor Rule\", Peter Hart, IEEE\nTransactions on Information Theory, May 1968, 515-516.\n\nThe illustrative examples are taken only from image classification.\nIt will be more convincing if other tasks, e.g., text classification,\nare also tried.  Even better, you can show the values of the\nmeasure, and what outliers it can pull out on some extreme cases:\ne.g. randomly labeled samples, or perfectly separable, synthetic\nclasses.\n\nWhat would the measure say for the adversarial samples crafted to fool\na neural network?\n\n\nMisc.:\n\nSection 2, related works:  should also refer to a recent survey that\nincludes many works analyzing the influence of individual samples\non classification difficulty:\n\"How complex is your classification problem? A survey on measuring\nclassification complexity\", by AC Lorena, et al., ACM Computing\nSurveys, 52(5), 1-34.\n\np.5:  in and before Proposition 5.1:  something is missing in what is\nreferred to as \"SGD's steady-state covariance\".  SGD usually refers to\nthe optimization procedure; are you reusing it to denote the dw quantity?\nIf not, what is the quantity whose distribution this covariance is about?\n\nFigure 1B:  why only samples of class cmd are shown?  \nTo make a better illustration, you may want to show both informative\nand non-informative samples for at least two classes.  Also, what do\nthe histograms in Figure 1A tell you about the different classes?\nThe examples from Figure 4 may serve the purpose of illustration\nbetter as they are more familiar objects.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes methods to estimate how informative a single training data is wrt the weights and output of the neural network. All reviewers think this is an interesting problem and the proposed method is easy to implement. On the other hand, the reviewers also raise a few questions: 
1.	There is a large body of work analyzing the informativeness of a feature wrt the model. The authors should compare their work to the feature importance analysis.
2.	The derived informativeness of a data depends not only on the network architecture, but also depends on the training algorithm, such as initialization and number of epochs. This makes the notion of data informativeness less general.
3.	The writing should be substantially improved.

Decision: Accept (Poster)