Laplace Sample Information: Data Informativeness Through a Bayesian Lens

Thank you for reviewing our work and pointing out strengths and weaknesses.

About the novelty. How this method is different from the influence function based method. Both methods require some calculation on the higher-order derivative. Based on the given context, I find it a bit hard to differentiate the differences.

Thank you for the comment. The conceptual difference between our method and Influence functions is substantial: Influence functions approximate the influence of an individual sample by solely considering the loss of a sample, as well as the Hessian at the location of convergence of the model. However, the presence of a single data point can influence the entire training trajectory of the model, yielding a completely different set of converged weights. Thus, estimating the influence by starting from a converged model as done by influence functions is merely an extrapolation of the true counterfactual influence of the sample (in fact, influence functions are known to be fragile [1, 2, 3]). LSI is based on leave-one-out retraining, which estimates the actual influence of a data point and is thus a full data attribution method [4]. However, as noted in the discussion of the manuscript, this comes at the cost of additional time complexity. However, seeing as it is parallelizable, LSI remains computationally tractable even for larger datasets.

About the calculation LSI in line 212, I could not understand how exactly $\hat{\theta}^{-i}$ and $\Sigma^{-i}$ are estimated. Here the technical detail is very limited, therefore I could not understand why estimating these can be done after training. Please give clear details how LSI is calculated.

$\hat{\theta}^{-i}$ and $\Sigma^{-i}$ are described in lines 206 and 208 of the original manuscript and constitute the final weights of the trained model with the left out datapoint and the curvature of the loss landscape at the final weights respectively. While the first is approximated with the probe model, the latter is computed using automatic differentiation given the final weights.

(Minor) The paper is a bit large by itself, 32Mb ! I could not properly read the results due to its large file.

Thank you for your feedback regarding the file size. We understand that the large file size may have affected readability primarily due to high-resolution figures and a lengthy appendix. To address this, we plan to replace some SVG files with high-resolution PNGs, reducing the overall file size and improving accessibility for readers.

I would like author to discuss its potential negative implications of this methods such as data leakage issue.

Thank you for this comment. Unfortunately, we are uncertain what you mean by “data leakage issue”. Would you please clarify so that we can address any concerns meaningfully.

If you are referring to data points influencing each other, since we do real LOO retraining, we expect no data leakage between the points.

In case you mean data privacy concerns, refer to Appendix F, where we include a discussion and investigation of the parallels between LSI and Differential Privacy, a standard algorithmic privacy technique, which we also intend to explore in future work.

[1] Samyadeep Basu, Phillip Pope, and Soheil Feizi. “Influence Functions in Deep Learning Are Fragile”. In: International Conference on Learning Representations (ICLR). 2021

[2] Andrew Ilyas, Sung Min Park, Logan Engstrom, Guillaume Leclerc, and Aleksander Madry. “Datamodels: Predicting Predictions from Training Data”. In: International Conference on Machine Learning (ICML). 2022

[3] Ekin Akyurek, Tolga Bolukbasi, Frederick Liu, Binbin Xiong, Ian Tenney, Jacob Andreas, and Kelvin Guu. “Towards Tracing Factual Knowledge in Language Models Back to the Training Data”. In: Findings of EMNLP. 2022.

[4] Cook, R. Dennis; Weisberg, Sanford. (1982). Residuals and Influence in Regression.

Dear Reviewer qsLf,

We appreciate your input. Having carefully addressed your comments, we hope that it clarifies the points you raised. Could you confirm if our response has clarified your concerns, or if there are additional aspects that you feel still need to be addressed? We are happy to engage in a discussion during the remaining rebuttal period.

Compare LSI to Influence and TRAK

Thank you for the suggestion. We already include a comparison to other existing methods in Appendix A, namely for pointwise sliced mutual information and smooth unique information. We opted for these metrics, as they are based on estimating the mutual information of a sample point and the weights and are thus closest to LSI. The values or our method correlate well with both of these, while pointwise sliced mutual information and smooth, unique information are uncorrelated. This indicates that these two methods measure distinct but related quantities, while LSI measures both.

Influence functions estimate the influence of an individual sample by solely considering the loss of a sample, as well as the Hessian at the location of convergence of the model. However, the presence of a single data point can influence the whole training trajectory of the model, yielding a completely different set of converged weights. Thus, estimating the influence by starting from a converged model as done by influence functions is a hypothetical extrapolation of the true influence (in fact, influence functions are known to be fragile [1, 2, 3]). Thus, these two measures estimate two different things.

However, as Influence functions are widely used in practice, we agree that comparing LSI with Influence functions is beneficial for contextualizing our work. Therefore we will include the comparison in the camera-ready version of the manuscript by extending Appendix A.

Our comparison shows that, while LSI is moderately correlated with TRAK as well as influence scores, there are distinct samples that carry high unique information (as measured by LSI) but have low influence or Trak scores. Further investigation revealed that a subset of these strongly uncorrelated examples are mislabeled or strongly out-of-distribution samples. This indicates that (1) while Influence functions and TRAK measure quantities that are related to the unique information(2) LSI allows for detecting out-of-distribution samples which both influence functions and TRAK miss. This is in line with the known fragility of Influence functions and TRAK and supports the use of our method.

Comparison of the computational complexity of LSI

Thank you for the thoughtful comment. You are raising a valid point. However, comparing LSI with existing methods is more complex than solely comparing based on the computational complexity. In fact, all data-attribution methods are trading off computational complexity, accuracy, and scalability. Therefore, it is very much dependent on the circumstances in which data attribution method is to be preferred, as none is objectively better than any other. LSI is linear in time O(kN) (k as the number of training steps and N as the number of samples) and constant O(N) (with N as the number of parameters of the probe) in space when using our proposed diagonal Hessian approximation. LSI is, therefore very efficient w.r.t. space complexity, it is well-founded as an approximation of the pointwise conditional mutual information and shown to be robust. Additionally, the space requirements of LSI remain constant w.r.t. the sample count.

Comparably, Influence Functions and their approximations at worst require the computation of the Hessian, which is O(N^2) in time and space, and also its inversion, which is O(N^3) in time and most importantly, are additionally known to be fragile [1, 2, 3] as they estimate the influence of a sample based on a one Newton step from the converged model. Recently proposed TRAK [4] speeds up influence functions by reducing them to logistic regression, which consequently shares the same fragility problems of influence functions and comes at the cost of introducing additional approximation errors. Smooth unique Information [5] requires space that scales with the dimensionality of the dataset and is thus not applicable to larger datasets (> 1000 samples). [6, 7] requires the training of hundreds of subsampled models until convergence to estimate the influence of samples.

Therefore, while it is possible to compare our numerical compare our method with other measures, it would not provide a full picture of the complicated task of data attribution and its inherent trade-offs.

[1] Samyadeep Basu et al. “Influence Functions in Deep Learning Are Fragile” (2021)

[2] Andrew Ilyas et al. “Datamodels: Predicting Predictions from Training Data” (2022)

[3] Ekin Akyurek et al. “Towards Tracing Factual Knowledge in Language Models Back to the Training Data”. (2022)

[4] Park, Sung Min, et al. "Trak: Attributing model behavior at scale." (2023).

[5] Harutyunyan, Hrayr, et al. "Estimating informativeness of samples with smooth unique information." (2021).

[6] Vitaly Feldman and Chiyuan Zhang. “What Neural Networks Memorize and Why: Discovering the Long Tail via Influence Estimation” (2020)

[7] Ilyas, Andrew, et al. "Datamodels: Predicting predictions from training data." (2022).

The reliance on the Laplace approximation assumes that the model parameters follow a multivariate Gaussian distribution. While the authors justify this through the central limit theorem, it would be better to provide empirical justifications, especially for highly complex or non-convex loss landscapes.

Thank you for the comment, you are raising a valid point, and we had the same concern. That is why we conducted experiments investigating the applicability of LSI on neural networks prior to their convergence, which you can find in Appendix E of the original manuscript. Our results show that after a brief warm-up period of a few epochs, the order of samples established via LSI does not substantially change. This indicates that even though LSI formally requires the convergence of the model, it remains applicable far prior to convergence.

Moreover, while our experiments consider a Gaussian posterior distribution of the weights, our method can be extended to other (more sophisticated) posterior approximation methods. An investigation thereof is included in Appendix G of the original manuscript, where we extend LSI to the recently proposed Riemann Laplace approximation.

The method relies on approximations of the Hessian, particularly when using diagonal approximations for large models. It would be better to analyze how this approximation affects LSI in different neural architectures.

Thank you for this comment, which is a valid concern we also shared. We would like to refer you to Appendix B, comparing the sample ordering established with LSI computed with different approximations of the Hessian. Our experiments show that LSI computed on the diagonal approximation correlates excellently with LSI computed on the full Hessian (Spearman’s Rank Correlation Coefficient of 0.93). This aligns with concurrent research showing that the Hessian of later layers of neural networks is diagonal dominant [1]. Appendix B also includes the same analysis with respect to the KFAC representation of the Hessian.

Furthermore, Appendix C of the original manuscript compares the sample ordering established with LSI computed on the probe model vs. the sample ordering of LSI computed on a CNN. With excellent correlation (also Spearman’s Rank Correlation Coefficient of 0.93) our results indicate that the LSI computed on the probe model is a suitable approximation.

[1] Elsayed, Mohamed, et al. "Revisiting Scalable Hessian Diagonal Approximations for Applications in Reinforcement Learning." (2024).

Thank you for raising the score and the additional feedback.

We have now uploaded a revised version of the original submission, including the comparison of LSI with TRAK in appendix H, which also includes a short remark on the difference of influence estimation (as done by TRAK) and data attribution with LSI. We agree that the main body of the work would benefit from an empirical evaluation. However, as there is no ground truth in data valuation, this often requires extensive discussion and, therefore, space. Consequently, we decided to move the comparison to the beginning of the appendix to allow the main body to focus on our contribution while making the empirical comparisons easily accessible and deliberately referring to it in the main body.

(Note, that we chose to append the comparison of LSI and TRAK here to not mess with references on appendices of the original manuscript we made in the rebuttel and will reposition it as Appendix B in the camera ready version of the work.)

Moreover, the revised Version of the document includes an additional experiment on human mislabeled data in Appendix I as well as it being smaller in size (in terms of memory) to aid with readability.

If you have any remaining concerns, please let us know so we can address them.

Thank you for reviewing our work and pointing out strengths and weaknesses.

Computational Cost

Thank you for the comment, you are raising a valid point. We approximate the Hessian with its diagonal which is far more efficient to compute. However, our method is not constrained to a specific type of Hessian approximation, indicating that future advances in Hessian approximation will also benefit the computation of LSI. An experiment showing that the diagonal approximation correlates well with the full Hessian for a model small enough for the full Hessian to be tractable is already part of the manuscript (Appendix B). Moreover, we also tested the correlation between the diagonal approximation and a Kronecker-factored Hessian approximation (KFAC), which is efficient enough to be used even in very large models (see e.g. Grosse et al, Studying Large Language Model Generalization with Influence Functions, 2023). In all cases, we found that the diagonal Hessian correlates excellently. To address your comment specifically, we will also add the following table to the manuscript in Appendix B:

Moreover, we show an excellent correlation in approximation quality of the probe model to training a full model in Appendix C. The speedup of the LOO retraining through employing the probe model depends on the size of the initial model and can thus not directly be reported as an attribute of the method, but was on the order of three magnitudes in our experimental settings, as stated in the original manuscript in the experimental section in line 252.

Limitations of Probe Model

Thank you for the comment. We provide data supporting this claim in Appendix C of the original manuscript. Concretely, we compute Spearman’s Rank correlation coefficient between LSI scores computed using the probe model vs. LSI scores computed on a full model (CNN). Here, we find an excellent correlation, suggesting that the probe model accurately captures the LSI computed on the full model.

Understanding the Effectiveness of LSI

Thank you for your comment. We are unsure about the meaning of “statistical measurements about the comparisons/differences between high and low LSI samples.” If our response below does not fully address your concern, we would appreciate further clarification so we can provide a more detailed answer. In the paper, we provide extensions of our LSI computed on individual samples to subsets of data. Section 4.3 shows that the visual correctness of our LSI extends to subsets of data, demonstrating the consistency of our findings. Larger-scale experiments using Vision and Language Transformers (CLIP) are presented in Section 4.2, showing the scalability of our approach. Additionally, we compare LSI to other metrics, including Pointwise Sliced Mutual Information and Smooth Unique Information in Appendix A. These results indicate that LSI is a better approximation of the mutual information than any of these methods. Moreover, other than these metrics, LSI remains computationally tractable. On the topic of mislabelled data detection, we would like to point out that this was not the primary focus of our paper, which is focused on data attribution. We thus used LSI as an informativeness measure to assess the impact of mislabeled data. Our experiments show that the unique sample information as measured by LSI increases with label flipping for most samples.

Experiments on Real-world Mislabeled Samples

Thank you for this recommendation. We have conducted an additional experiment of detecting mislabeled data on Cifar-10N, and found the following. Similar to label flipping, samples with human labeling errors, on average, have higher LSI as they carry more unique information. However, the difference to correctly labeled samples is not as big as with label flipping. This follows the intuition of unique information, as a distant brown animal (correct label: deer, given wrongfull label: dog) does not carry as much unique information, as there are also other images of distant brown animals labeled as dogs, as if it would have been labeled as an airplane. The corresponding figure will be included in the manuscript appendix. Note that Cifar-10H is unsuitable for this purpose as it solely provides mislabeled targets for the test split of the dataset and can, therefore not be investigated.

Dear Reviewer 6Bs2, Thank you for your review. At this point, our progress depends on your response. We would greatly appreciate it if you could share your thoughts on whether our reply to your review addresses some of your concerns or provide guidance on how we might resolve any remaining issues before the end of the rebuttal period.

Thank you for reviewing our work and pointing out strengths and weaknesses.

The novelty of the proposed method might be limited as the Laplacian approximation is widely used in the Bayesian machine learning community.

Thank you for your comment. Your criticism here seems to be centered on the novelty of the Laplace approximation itself rather than on how we have applied it in our work. The novelty of our work is using the Laplace approximation as a foundational tool for determining sample informativeness. This reliance on a proven method is a strength, ensuring our approach is built on a solid theoretical basis. To the best of our knowledge, the Laplace approximation has not been employed in the context of data attribution. We hope this clarifies the originality and value of our proposed method.

Theoretically, formal results are lacking to support the effectiveness of the proposed method.

Thank you for your feedback. The assertion that theoretical support is lacking is not correct. While we do not provide a standalone proof of the KL divergence's properties, this is unnecessary, as they are well-established in the cited literature. Moreover, the LSI is based on sample information (SI) as proposed by [1]. It thus formally approximates the pointwise conditional mutual information of the samples and the weights of the neural network. LSI provides a computationally tractable implementation of the theoretically well-motivated SI which can be used for data attribution, at which we succeed. For a detailed formal derivation of sample information from the pointwise conditional mutual information, we refer you to [1], as referenced in line 149 of the original manuscript. The derivation of LSI from SI is provided in the manuscript in section 3.

Large experiments involving large datasets and models are lacking, which results in that this work might have little influence in practice.

We appreciate your feedback regarding the scale of the experiments. We acknowledge that our work does not yet demonstrate applicability at the scale of very large datasets, such as those on the scale of ImageNet. However, we believe it is important to view this limitation within the broader context of data attribution research, particularly for methods that offer rigorous theoretical guarantees. Large-scale experiments are a challenge for most data attribution methods that aim to provide formal guarantees due to the inherent trade-offs between computational cost, tractability, and accuracy ([1] is solely capable of acting on subsets of a few thousand samples, [2] provides results solely on MNIST and a 900 sample subset of ImageNet, [3] requires training of hundreds of models and results are provided solely on CIFAR-10 and FMoW, [4] reduces the data attribution tasks to logistic regression, [5] required the training of hundreds of models from scratch with the number of models increasing with the dataset size). Our work addresses these trade-offs by making significant progress toward practical applicability, even if scaling to the largest datasets remains beyond the current scope. Given that our method is parallelizable, our method is applicable to arbitrary datasets and models without encountering computability issues, contrary to methods which suffer from memory scaling limitations. Thus, the primary constraint limiting our ability to conduct experiments at larger scales is computational resources rather than any intrinsic limitation of our method.

Typos exist in Lines 194-195: shownAppendix.

Thank you for spotting the typo, we will fix it.

[1] Harutyunyan, Hrayr, et al. "Estimating informativeness of samples with smooth unique information." (2021).

[2] Koh, Pang Wei, and Percy Liang. "Understanding black-box predictions via influence functions." International conference on machine learning. PMLR, 2017.

[3] Ilyas, Andrew, et al. "Datamodels: Predicting predictions from training data." (2022).

[4] Park, Sung Min, et al. "Trak: Attributing model behavior at scale." (2023).

[5] Vitaly Feldman and Chiyuan Zhang. “What Neural Networks Memorize and Why: Discovering the Long Tail via Influence Estimation”. In: Advances in Neural Information Processing Systems (NeurIPS). Vol. 33. 2020, pp. 2881–2891

Dear Reviewer j9mc,

Thank you for your valuable feedback. At this stage, our progress hinges on your response. We would greatly appreciate it if you could share your thoughts on whether our reply to your review resolves some of your concerns or provide guidance on how we might address any remaining issues before the rebuttal period concludes.