Data Shapley in One Training Run

Data Shapley in One Training Run

Jiachen T. Wang Affiliation: Princeton University Prateek Mittal Affiliation: Princeton University Dawn Song Affiliation: UC Berkeley Ruoxi Jia Affiliation: Virginia Tech

Abstract

Data Shapley offers a principled framework for attributing the contribution of data within machine learning contexts. However, the traditional notion of Data Shapley requires re-training models on various data subsets, which becomes computationally infeasible for large-scale models. Additionally, this retraining-based definition cannot evaluate the contribution of data for a specific model training run, which may often be of interest in practice. This paper introduces a novel concept, In-Run Data Shapley, which eliminates the need for model retraining and is specifically designed for assessing data contribution for a particular model of interest. In-Run Data Shapley calculates the Shapley value for each gradient update iteration and accumulates these values throughout the training process. We present several techniques that allow the efficient scaling of In-Run Data Shapley to the size of foundation models. In its most optimized implementation, our method adds negligible runtime overhead compared to standard model training. This dramatic efficiency improvement makes it possible to perform data attribution for the foundation model pretraining stage. We present several case studies that offer fresh insights into pretraining data’s contribution and discuss their implications for copyright in generative AI and pretraining data curation.

Data Shapley 为机器学习里的数据贡献归因提供了一套有原则的框架。但传统定义需要在各种数据子集上反复重训模型，对大规模模型几乎不可行；而且基于重训的定义也无法评估「某一次具体训练」中的数据贡献——实践中往往正是后者更要紧。本文提出 In-Run Data Shapley ：无需重训，专门衡量目标模型这一次训练里各数据源的贡献。它在每一次梯度更新上计算 Shapley 值，并在整段训练过程中累加。我们给出若干技巧，使 In-Run Data Shapley 能扩到基础模型规模；在最优化实现下，相对标准训练的额外运行开销可忽略。效率提升使得在基础模型预训练阶段做数据归因成为可能。文中若干案例为预训练数据贡献提供了新观察，并讨论其对生成式 AI 版权与预训练数据策展的含义。

1 Introduction

In today’s data-driven world, understanding the contribution of each data point is crucial, especially with the advent of foundation models that rely on vast amounts of training data from various sources. The lack of reliable data attribution mechanisms can lead to significant legal and societal issues, resulting in a growing backlash against the broader use of data for model training (Heikkilä, 2023). For instance, there is a risk of violating intellectual property rights, failing to fairly compensate data creators, and disincentivizing them from producing new, high-quality content (Henderson et al., 2023). This has already resulted in legal disputes, such as the New York Times’ lawsuit against Microsoft/OpenAI (Grynbaum & Mac, 2023). Moreover, foundation models are often trained on massive datasets scraped from the internet, which can include low-quality and harmful content (Gao et al., 2020; Raffel et al., 2020; Touvron et al., 2023). Problematic data not only wastes computational resources but also skews model outputs, potentially leading to biased or inaccurate results. By understanding the contribution of each data source, we can identify and mitigate the influence of low-quality data, thereby improving the efficiency and quality of model training.

在当今数据驱动的世界里，弄清每个数据点的贡献至关重要，尤其当基础模型依赖来自多方的海量训练数据时。缺乏可靠的数据归因机制会带来法律与社会风险，并加剧对「用更多数据训模型」的反弹（Heikkilä, 2023）。例如可能侵犯知识产权、未能公平补偿数据创作者，从而抑制高质量新内容的生产（Henderson 等, 2023）。《纽约时报》诉 Microsoft/OpenAI 案已是一例（Grynbaum & Mac, 2023）。此外，基础模型常在从互联网抓取的大规模语料上训练，其中夹杂低质甚至有害内容（Gao 等, 2020；Raffel 等, 2020；Touvron 等, 2023）。问题数据既浪费算力，也会扭曲输出、带来偏差或不准结果。弄清各数据源贡献，才能识别并削弱低质数据的影响，从而提升训练效率与质量。

Since the training data of foundation models comes from multiple stakeholders, it is essential to have an algorithm that can fairly attribute data contributions. In recent years, significant progress has been made in understanding what it means to fairly quantify and attribute data source contributions, with the Shapley value (Shapley, 1953) emerging as a widely adopted framework (Ghorbani & Zou, 2019; Jia et al., 2019b). Originating from cooperative game theory, the Shapley value uniquely satisfies several desirable properties: (1) It assigns equal scores to equally impactful data points, ensuring fairness; (2) the sum of contribution scores equals the total utility, meaning the scores always represent a share of the total utility; (3) it supports additive decomposition across multiple utility functions, allowing for the calculation of contributions to the entire test set by summing the scores of individual test points. As the Shapley value uniquely satisfies these properties, it eliminates the uncertainty and ambiguity surrounding which attribution frameworks should be used conceptually. While there are other non-Shapley data attribution frameworks, such as Datamodels (Park et al., 2023; Ilyas et al., 2022) and influence functions (Koh & Liang, 2017), they lack the clear theoretical foundation and uniqueness provided by the Shapley value.

基础模型训练数据来自多方利益相关者，因此需要能 公平 归因数据贡献的算法。近年对「如何公平量化并归因数据源贡献」进展显著， Shapley 值 （Shapley, 1953）成为被广泛采用的框架（Ghorbani & Zou, 2019；Jia 等, 2019b）。它源于合作博弈论，并唯一满足若干合意性质：(1) 同等影响力的数据点得到同等分数，保证公平；(2) 各贡献分之和等于总效用，分数始终是总效用的份额；(3) 支持跨多个效用函数的可加分解，从而可用各测试点分数之和得到整个测试集上的贡献。正因为唯一满足这些性质，它从概念上消解了「该用哪种归因框架」的含糊。虽有 Datamodels（Park 等, 2023；Ilyas 等, 2022）与影响函数（Koh & Liang, 2017）等非 Shapley 方法，但它们缺少 Shapley 值那种清晰的理论基础与唯一性。

Original Data Shapley definition faces computational & conceptual limitation. However, Data Shapley, i.e., the application of the Shapley value in data attribution, has been limited to very small-scale models. Existing methods (Ghorbani & Zou, 2019) to estimate the Shapley value require retraining the model numerous times using different subsets of data to evaluate the contribution of each data source, making them computationally infeasible for foundation models. On the other hand, retraining-based methods suffer from a conceptual issue often overlooked in the literature: they assess data contribution for a general learning algorithm rather than a particular model. While one might interpret the former as an approximation of the latter, these two quantities can be quite different in practice, especially when the learning algorithm is randomized and sensitive to factors like random initialization and training data order. In many real-life scenarios, however, the primary interest lies in understanding data contribution to the specific model being trained and deployed.

原始 Data Shapley 定义面临计算与概念双重限制 。 将 Shapley 值用于数据归因的 Data Shapley，迄今多局限于极小规模模型。已有估计方法（Ghorbani & Zou, 2019）需在大量不同数据子集上反复重训，以评估各数据源贡献，对基础模型在计算上不可行。另一方面，基于重训的方法还有一个文献中常被忽略的概念问题： 它们评估的是对「一般学习算法」的数据贡献，而非对「某个具体模型」 。 虽可将前者看作后者的近似，但实践中二者可相差甚远，尤其当学习算法带随机性、对初始化与数据顺序敏感时。而许多真实场景真正关心的，正是正在训练并部署的那一个具体模型上的数据贡献。

This paper introduces In-Run Data Shapley, a novel approach that makes fair data attribution applicable to large-scale foundation models. Unlike retraining-based Data Shapley, In-Run Data Shapley quantifies the contribution of each data source to the specific target model of interest .

本文提出 In-Run Data Shapley ，使公平数据归因能用于大规模基础模型。与基于重训的 Data Shapley 不同，它量化的是各数据源对 所关注的特定目标模型 的贡献。

Technical contributions. Our key insight is that ML models are trained using iterative algorithms, where the model performance change in one iteration is sufficiently small to be accurately approximated by first- or second-order Taylor expansions. We show that the Shapley value for the approximated one-step model performance change can be derived analytically via gradient dot-products or gradient-Hessian-gradient products between training and validation data. Hence, we can compute the Data Shapley scores for each model update step, and accumulate the scores throughout the training process. However, the per-sample gradient vectors required for computing the Shapley value in each training iteration introduce significant overhead due to per-sample gradient calculation. To address this challenge, we develop a series of technical tools that enable the exact calculation of gradient dot-products and gradient-Hessian-gradient products in one and two backward passes, respectively, without the need to instantiate any additional gradient vectors or Hessian matrices. Collectively, these tools allow for the efficient computation of In-Run Data Shapley. In particular, with sufficient GPU memory, its most efficient implementation is as fast as regular training.

技术贡献 。 关键洞察是：机器学习模型用迭代算法训练，单步性能变化足够小，可用一阶或二阶 Taylor 展开精确逼近。我们证明，对逼近后的单步性能变化，其 Shapley 值可通过训练与验证数据之间的梯度点积或「梯度-Hessian-梯度」乘积解析求出。于是可在每一步模型更新上计算 Data Shapley 分数，并在整段训练中累加。但每轮训练迭代所需的逐样本梯度会带来显著开销。为此，我们发展一系列技术工具，分别用一次与两次反向传播精确计算梯度点积与梯度-Hessian-梯度乘积，而无需实例化任何额外梯度向量或 Hessian 矩阵。合在一起，这些工具使 In-Run Data Shapley 可高效计算；在 GPU 显存充足时，最高效实现可与常规训练一样快。

Empirical implications. Given the efficient algorithms developed in this paper, for the first time, one can perform data attribution on the scale of foundation model pretraining. While in this paper, we focus on GPT2 and Pythia-410M as a pilot study, our approach is applicable to larger-scale industrial models with sufficient computing resources. We performed various case studies that provide fresh insights into training data’s contribution to the foundation model pretraining.

经验含义 。 有了本文高效算法，首次能在基础模型预训练规模上做数据归因。本文以 GPT2 与 Pythia-410M 作试点，但在算力充足时方法可推广到更大规模工业模型。我们做了多组案例研究，为训练数据对基础模型预训练的贡献提供了新观察。

(1) There is considerable room for improvement in data curation for pretraining (Section 5.3.1). Even well-curated pretraining corpora contain data points that negatively impact the training process. We demonstrate the effectiveness of In-Run Data Shapley in identifying these low-quality data points. By computing In-Run Data Shapley values during training and removing negatively valued data points, we show that the cleaned dataset leads to significantly faster model convergence and improved performance compared to the original dataset. Interestingly, despite the Pile dataset (Gao et al., 2020) already undergoing multiple layers of curation, In-Run Data Shapley assigns negative values to approximately 16% of the data. We found a significant amount of noisy data among them, highlighting the need for improved data curation for foundation model training.

（1）预训练数据策展仍有很大改进空间（第 5.3.1 节） 。 即便精心策展的预训练语料，仍含会伤害训练过程的数据点。我们展示 In-Run Data Shapley 能有效找出这些低质点：训练中计算其值并去掉负值样本后，清洗集相对原集收敛显著更快、性能更好。有趣的是，即便 Pile（Gao 等, 2020）已经过多层策展，In-Run Data Shapley 仍给约 16% 数据赋负值；其中大量噪声数据，凸显基础模型训练仍需更好的数据策展。

(2) Data’s contribution is stage-dependent (Section 5.3.2). In-Run Data Shapley can capture the dynamics of contribution through the course of training, a fine-grained aspect that cannot be captured by prior works. In-Run Data Shapley shows that in the early stages of training, general corpora tend to have a relatively large contribution regardless of the downstream tasks. This is because general corpora help the model learn basic language patterns, grammar, and common knowledge. However, in the later stages of training, the contribution from domain-specific corpora becomes dominant, and the contribution of the general corpus phases out.

（2）数据贡献随训练阶段变化（第 5.3.2 节） 。 In-Run Data Shapley 能刻画训练过程中贡献的动态，这种细粒度是先前工作难以捕捉的。结果显示：训练早期，无论下游任务如何，通用语料往往贡献相对较大——它们帮助模型学习基本语言模式、语法与常识；到后期，领域语料的贡献占主导，通用语料的贡献逐渐消退。

(3) Rethinking copyright in generative AI: contribution beyond memorization (Section 5.3.3). We studied training data’s contribution to validation points of varying similarity levels. We found that even when the validation data is a complete rewrite of the training data while maintaining the topic, the training data still contributes significantly. This finding has implications for the current dialogue around what constitutes a copyright violation in generative AI (Mulligan & Li, 2024). While the unfair use of copyrighted content is generally only considered when the generated data is an almost verbatim replication of the training data, our contribution analysis shows that some data owners should receive a certain royalty share for generated content, even if the output does not closely resemble the copyrighted material.

（3）重思生成式 AI 中的版权：贡献不只等于记忆（第 5.3.3 节） 。 我们研究了训练数据对相似度各异的验证点的贡献，发现即便验证数据是对训练数据的完全改写、仅保留主题，训练数据仍贡献显著。这对当前关于生成式 AI 中何为版权侵权的讨论有启示（Mulligan & Li, 2024）。不公使用版权内容通常只在生成结果近乎逐字复现训练数据时被考虑；而我们的贡献分析表明，即便输出并不酷似版权材料，部分数据所有者仍应对生成内容享有一定版税份额。

2 Background of Data Shapley

In this section, we formalize the setup of data attribution for ML and revisit Data Shapley’s definition.

本节形式化机器学习中的数据归因设定，并回顾 Data Shapley 的定义。

\mathcal{D}_{\text{tr}}:=\{z_{i}\}_{i=1}^{N}

\mathcal{D}_{\text{tr}}:=\{z_{i}\}_{i=1}^{N}

The Shapley value (SV) (Shapley, 1953), originating from game theory, stands out as a distinguished method for equitably distributing total profit among all participating players. Before diving into its definition, we first discuss a fundamental concept: the utility function .

Shapley 值（SV）（Shapley, 1953）源于博弈论，是在参与者之间公平分配总收益的杰出方法。进入定义之前，先引入一个基本概念： 效用函数 。

U

U

U(\cdot)

U(\cdot)

U(S\cup\{z\})-U(S)

U(S\cup\{z\})-U(S)

U_{1},U_{2}

U_{1},U_{2}

U(S)=\texttt{Perf}(\mathcal{A}(S))

U(S)=\texttt{Perf}(\mathcal{A}(S))

Limitations beyond efficiency (detailed in Appendix B.1) : In addition to the high computational costs, we emphasize that retraining-based Data Shapley also suffers from the following limitations: (1) Highly unstable value scores: When stochastic learning algorithms such as SGD are used, the resulting value scores can be highly unstable (Wang & Jia, 2023a). This instability may lead to unreliable results and potential violations of Shapley value’s fairness axioms. (2) Conceptual limitations: Retraining-based Data Shapley measures the average data contribution to the learning process itself, across many retrainings on different data subsets. As a result, it produces attribution scores that apply broadly to the algorithm but fail to reflect the data contribution to a specific training run. On the other hand, providing insights into how individual data points contribute to the deployed model enables more targeted analysis and debugging, thereby improving model interpretability.

效率之外的局限（详见附录 B.1） ：除了计算代价高昂，我们强调基于重训的 Data Shapley 还有如下问题： （1）价值分数极不稳定 ： 使用 SGD 等随机学习算法时，所得分数可高度不稳（Wang & Jia, 2023a），可能导致结果不可靠，甚至违反 Shapley 值的公平公理。 （2）概念局限 ： 它衡量的是跨多次不同子集重训、对「学习过程本身」的平均数据贡献，因而归因分数泛适用于算法，却反映不出对某一次具体训练的贡献。相反，弄清各数据点如何贡献于已部署模型，才能做更有针对性的分析与调试，提升可解释性。

3 In-Run Data Shapley

To address the issues associated with Retraining-based Data Shapley such as high computational costs, value instability, and the inability to assess the contribution towards a specific trained model, we propose a novel data attribution method specifically tailored for a single training run. Our key idea is to leverage the iterative nature of model training and employ a "divide and conquer" approach: breaking down the problem of valuing data contributions for the entire training process into subproblems of valuing data contributions for individual iterations.

为应对基于重训的 Data Shapley 的高计算成本、价值不稳、以及无法评估对特定已训模型贡献等问题，我们提出专为单次训练设计的数据归因方法。关键想法是利用训练的迭代性，采取「分而治之」：把整段训练的数据贡献估值，拆成各单次迭代上的子问题。

U(S)=\texttt{Perf}(\mathcal{A}(S))

U(S)=\texttt{Perf}(\mathcal{A}(S))

\displaystyle U^{(t)}(S;z^{(\mathrm{val})}):=\ell(\widetilde{w}_{t+1}(S),z^{(\mathrm{val})})-\ell(w_{t},z^{(\mathrm{val})}) \tag{1}

\widetilde{w}_{t+1}(S):=w_{t}-\eta_{t}\sum_{z\in S}\nabla\ell(w_{t},z)

\widetilde{w}_{t+1}(S):=w_{t}-\eta_{t}\sum_{z\in S}\nabla\ell(w_{t},z)

U^{(t)}

U^{(t)}

U(S)=\sum_{t=0}^{T-1}U^{(t)}(S)

U(S)=\sum_{t=0}^{T-1}U^{(t)}(S)

D^{(\mathrm{val})}=\{z^{(\mathrm{val})}\}

D^{(\mathrm{val})}=\{z^{(\mathrm{val})}\}

4 Efficient Computation of In-Run Data Shapley

\phi_{z}(U^{(t)})

\phi_{z}(U^{(t)})

U^{(t)}

U^{(t)}

U^{(t)}

\begin{aligned} U^{(t)}(S)&=\ell(\widetilde{w}{t+1}(S),z^{(\mathrm{val})})-\ell(w{t},z^{(\mathrm{val})})\&=\underbrace{\nabla\ell(w_{t},z^{(\mathrm{val})})\cdot(\widetilde{w}{t+1}(S)-w{t})}{U^{(t)}{(1)}(S)}+\frac{1}{2}\underbrace{(\widetilde{w}{t+1}(S)-w{t})^{\intercal}\textbf{H}^{(z^{(\mathrm{val})})}{t}(\widetilde{w}{t+1}(S)-w_{t})}{U^{(t)}{(2)}(S)}+~\text{higher order terms}\end{aligned}

\textbf{H}^{(z^{(\mathrm{val})})}_{t}:=\nabla^{2}\ell(w_{t},z^{(\mathrm{val})})

\textbf{H}^{(z^{(\mathrm{val})})}_{t}:=\nabla^{2}\ell(w_{t},z^{(\mathrm{val})})

U^{(t)}\approx U^{(t)}_{(1)}

U^{(t)}\approx U^{(t)}_{(1)}

Theorem 3 . In-Run Data Shapley considering the first-order approximation has closed-form

定理 3 。 考虑一阶逼近的 In-Run Data Shapley 具有闭式

\displaystyle\phi_{z}\left(U\right)\approx\sum_{t=0}^{T-1}\phi_{z}\left(U^{(t)}_{(1)}\right)

where

其中

\displaystyle\phi_{z}\left(U^{(t)}_{(1)}\right)=-\eta_{t}\nabla\ell(w_{t},z^{(\mathrm{val})})\cdot\nabla\ell(w_{t},z),~~~t=0,\ldots,T-1

z_{i}

z_{i}

U^{(t)}

U^{(t)}

Theorem 4 . In-Run Data Shapley considering the second-order approximation has closed-form

定理 4 。 考虑二阶逼近的 In-Run Data Shapley 具有闭式

\displaystyle\phi_{z}\left(U\right)\approx\sum_{t=0}^{T-1}\left(\phi_{z}\left(U^{(t)}_{(1)}\right)+\frac{1}{2}\phi_{z}\left(U^{(t)}_{(2)}\right)\right) \tag{2}

where

其中

\begin{aligned} \phi_{z}\left(U^{(t)}{(1)}\right)+\frac{1}{2}\phi{z}\left(U^{(t)}{(2)}\right)=\underbrace{-\eta{t}\nabla\ell(w_{t},z^{(\mathrm{val})})\cdot\nabla\ell(w_{t},z)}{\text{\hbox to9.41pt{\vbox to9.41pt{\pgfpicture\makeatletter\hbox{\hskip 4.70488pt\lower-4.70488pt\hbox to0.0pt{\lxSVG@begingroup@{scopebegin=1} \lxSVG@begingroup@{stroke=#000000} \lxSVG@begingroup@{fill=#000000} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width=0.4pt} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{scopebegin=1} {{{}}\lx@inpgf@ignorespaces\hbox{\hbox{{\lxSVG@begingroup@{scopebegin=1} {{}{{{}}}{{}}{}{}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{}{}{}{}{}{{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 6.23 0 C 6.23 3.44 3.44 6.23 0 6.23 C -3.44 6.23 -6.23 3.44 -6.23 0 C -6.23 -3.44 -3.44 -6.23 0 -6.23 C 3.44 -6.23 6.23 -3.44 6.23 0 Z M 0 0}{fill:none} \lx@inpgf@ignorespaces}{{{{\lx@inpgf@ignorespaces}}\lxSVG@begingroup@{scopebegin=1} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{-2.11113pt}{-2.25555pt}\lxSVG@begingroup@{transform=matrix(1.0 0.0 0.0 1.0 -2.92 -3.12)} \pgfsys@hbox{63}\lxSVG@closescope }}}\lxSVG@closescope }}}}\lxSVG@closescope {{{}}}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}} influence of }z\text{ on the loss of }z^{(\mathrm{val})}}+\underbrace{\frac{\eta{t}^{2}}{2}\nabla\ell(w{t},z)^{\intercal}\textbf{H}^{(z^{(\mathrm{val})})}{t}\left(\sum{z{j}\in\mathcal{B}{t}}\nabla\ell(w{t},z_{j})\right)}_{\text{\hbox to9.41pt{\vbox to9.41pt{\pgfpicture\makeatletter\hbox{\hskip 4.70488pt\lower-4.70488pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin=1} \lxSVG@begingroup@{stroke=#000000} \lxSVG@begingroup@{fill=#000000} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width=0.4pt} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin=1} {{{}}\lx@inpgf@ignorespaces\hbox{\hbox{{\lxSVG@begingroup@{_scopebegin=1} {{}{{{}}}{{}}{}{}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{}{}{}{}{}{{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 6.23 0 C 6.23 3.44 3.44 6.23 0 6.23 C -3.44 6.23 -6.23 3.44 -6.23 0 C -6.23 -3.44 -3.44 -6.23 0 -6.23 C 3.44 -6.23 6.23 -3.44 6.23 0 Z M 0 0}{fill:none} \lx@inpgf@ignorespaces}{{{{\lx@inpgf@ignorespaces}}\lxSVG@begingroup@{_scopebegin=1} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{-2.11113pt}{-2.25555pt}\lxSVG@begingroup@{transform=matrix(1.0 0.0 0.0 1.0 -2.92 -3.12)} \pgfsys@hbox{63}\lxSVG@closescope }}}\lxSVG@closescope }}}}\lxSVG@closescope {{{}}}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}} interaction between }z\text{ and other training points}}\end{aligned} \tag{3}

t=0,\ldots,T-1

t=0,\ldots,T-1

z

z

4.2 Efficient Computation of Gradient Dot-product and Gradient-Hessian-Gradient Product

z\in\mathcal{B}_{t}

z\in\mathcal{B}_{t}

\mathcal{B}_{t}=\{z_{1},\ldots,z_{B}\}

\mathcal{B}_{t}=\{z_{1},\ldots,z_{B}\}

\displaystyle\frac{\partial\ell^{(i)}}{\partial\textbf{W}}=\frac{\partial\ell^{(i)}}{\partial\textbf{s}^{(i)}}\otimes\frac{\partial\textbf{s}^{(i)}}{\partial\textbf{W}}=\frac{\partial\ell^{(i)}}{\partial\textbf{s}^{(i)}}\otimes\textbf{a}^{(i)}=\frac{\partial\ell}{\partial\textbf{s}^{(i)}}\otimes\textbf{a}^{(i)}

\ell:=\sum_{j=1}^{B}\ell^{(j)}

\ell:=\sum_{j=1}^{B}\ell^{(j)}

\begin{aligned} \frac{\partial\ell^{(1)}}{\partial\textbf{W}}\odot\frac{\partial\ell^{(2)}}{\partial\textbf{W}}=\left(\textbf{a}^{(1)}\otimes\frac{\partial\ell^{(1)}}{\partial\textbf{s}^{(1)}}\right)\odot\left(\textbf{a}^{(2)}\otimes\frac{\partial\ell^{(2)}}{\partial\textbf{s}^{(2)}}\right)=\left(\left(\textbf{a}^{(1)}\right)^{\intercal}\textbf{a}^{(2)}\right)\left(\left(\frac{\partial\ell^{(1)}}{\partial\textbf{s}^{(1)}}\right)^{\intercal}\left(\frac{\partial\ell^{(2)}}{\partial\textbf{s}^{(2)}}\right)\right)\end{aligned} \tag{5}

\textbf{a}^{(1)},\textbf{a}^{(2)},\frac{\partial\ell^{(1)}}{\partial\textbf{s}^{(1)}},\frac{\partial\ell^{(2)}}{\partial\textbf{s}^{(2)}}

\textbf{a}^{(1)},\textbf{a}^{(2)},\frac{\partial\ell^{(1)}}{\partial\textbf{s}^{(1)}},\frac{\partial\ell^{(2)}}{\partial\textbf{s}^{(2)}}

Remark 2 . While we illustrate our "ghost dot-product" technique using linear layers, it can be extended to other types of layers by leveraging similar decompositions as in Equation (4) that have been developed in differential privacy literature (Rochette et al., 2020; Bu et al., 2022; Li et al., 2021; Bu et al., 2023; Kong & Munoz Medina, 2024).

注记 2 。 虽以线性层说明「ghost 点积」，借助差分隐私文献中已发展的类似分解（式 (4)）（Rochette 等, 2020；Bu 等, 2022；Li 等, 2021；Bu 等, 2023；Kong & Munoz Medina, 2024），可推广到其他层类型。

Computing gradient-Hessian-gradient products in 2 backpropagations (Appendix D.2). For second-order In-Run Data Shapley, an outstanding challenge is how to efficiently compute the pairwise interaction term among training points. In Appendix D.2, we develop a "ghost gradient-Hessian-gradient product" technique for computing the desired quantity through one extra backpropagation pass, without materializing any gradient-sized vectors. This technique leverages several properties of neural network gradients across different layers, and its derivation is complex.

两次反向计算梯度-Hessian-梯度乘积（附录 D.2） 。 对二阶 In-Run Data Shapley，突出挑战是高效计算训练点之间的成对交互项。附录 D.2 给出 「ghost 梯度-Hessian-梯度乘积」 技术：用一次额外反向得到所需量，而不物化任何梯度规模的向量。该技巧利用神经网络跨层梯度的若干性质，推导较复杂。

\sum_{z_{i}\in\mathcal{B}_{t}}\ell_{i}

\sum_{z_{i}\in\mathcal{B}_{t}}\ell_{i}

5 Experiments

In this section, we evaluate In-Run Data Shapley in terms of its efficiency (Section 5.1), fidelity (Section 5.2), and its applications in data attribution for language model pretraining (Section 5.3). In Appendix E.6, we compare a variety of existing data attribution methods in small-scale settings.

本节从效率（5.1）、保真度（5.2）以及语言模型预训练中的数据归因应用（5.3）评估 In-Run Data Shapley。附录 E.6 在小规模设定下比较多种既有数据归因方法。

5.1 Runtime Evaluation

We empirically assess the computational efficiency of In-Run Data Shapley with "ghost dot-product" and "ghost vector-Hessian-vector product" techniques developed in Section 4.2.

我们经验评估第 4.2 节「ghost 点积」与「ghost 向量-Hessian-向量积」技术下 In-Run Data Shapley 的计算效率。

Throughput Regular Training 76.2 First-order Data Shapley (ghost) 70.5 Second-order Data Shapley (ghost) 34.4 First-order Data Shapley (direct) 4.2 Second-order Data Shapley (direct) 1.8 Table 1: Efficiency comparison of different implementations of In-Run Data Shapley. We use throughput, i.e., # training data points being processed per second as the efficiency metric.

	Throughput
Regular Training	76.2
First-order Data Shapley (ghost)	70.5
Second-order Data Shapley (ghost)	34.4
First-order Data Shapley (direct)	4.2
Second-order Data Shapley (direct)	1.8

吞吐量 常规训练 76.2 一阶 Data Shapley（ghost） 70.5 二阶 Data Shapley（ghost） 34.4 一阶 Data Shapley（直接） 4.2 二阶 Data Shapley（直接） 1.8 表 1：In-Run Data Shapley 不同实现的效率比较。效率指标取吞吐量，即每秒处理的训练数据点数。

	吞吐量
常规训练	76.2
一阶 Data Shapley（ghost）	70.5
二阶 Data Shapley（ghost）	34.4
一阶 Data Shapley（直接）	4.2
二阶 Data Shapley（直接）	1.8

2\times

2\times

5.2 Fidelity Evaluation

Figure 1: Comparison between the Monte Carlo-estimated In-Run Data Shapley and First/Second-order In-Run Data Shapley.

图 1：蒙特卡洛估计的 In-Run Data Shapley 与一/二阶 In-Run Data Shapley 的比较。

In this section, we directly assess the approximation accuracy of first- and second-order In-Run Data Shapley. In Appendix E.6, we further compare the performance of In-Run Data Shapley with existing (less scalable) data attribution techniques on standard benchmarks (e.g., mislabeled data detection) as an additional sanity check.

本节直接评估一、二阶 In-Run Data Shapley 的逼近精度。附录 E.6 进一步在标准基准（如错标检测）上与既有（可扩展性较差的）数据归因技术比较，作为额外健全性检查。

3\times 10^{-4}

3\times 10^{-4}

5.3 Case Study: Data Attribution on Pile Dataset

In this section, we present a case study to demonstrate the use cases of In-Run Data Shapley by pretraining on the well-known Pile dataset (Gao et al., 2020). We explore its application in data curation, examine data contribution across different training stages, and investigate relevant corpus detection. Due to computational resource constraints, most of our experiments focus on the GPT-2 and Pythia-410M models, but this is not a limitation of the algorithm itself. With adequate computational resources, our approach can easily be applied to larger-scale models.

本节以知名 Pile 数据集（Gao 等, 2020）上的预训练为例，展示 In-Run Data Shapley 的用例：数据策展、不同训练阶段的数据贡献，以及相关语料检测。受算力限制，多数实验聚焦 GPT-2 与 Pythia-410M，但这并非算法本身的限制；算力充足时方法可轻松用于更大规模模型。

5.3.1 Is Well-curated Dataset Actually Clean? Carefully curated pretraining corpora still contain data points that can adversely affect the training process. Identifying and removing these data points can accelerate model convergence and enhance overall performance, thereby saving computational resources. In this experiment, we demonstrate the effectiveness of In-Run Data Shapley in assessing the data quality of a subset of the Pile dataset. We uniformly select a random subset of Pile with around 10B tokens and train a GPT2 model on this subset. We compute the data attribution results with Pile’s validation set. By filtering out all negatively valued corpora and retraining the model on the cleaned subset, we observe significant improvement in model convergence. For both first- and second-order In-Run Data Shapely, we can achieve around 25% fewer training iterations to reach a test loss of 3.75. Surprisingly, our analysis reveals that around 16% of the training corpora had negative second-order In-Run Data Shapley values. While some of the negatively valued corpora may be attributed to the significant domain shift compared to the validation corpora, we still find many low-quality corpora from Pile, a pretraining dataset that has undergone several layers of data curation (Gao et al., 2020). Examples of low-quality corpora identified can be found in Appendix E.3.

5.3.1 精心策展的数据集真的干净吗？ 即便精心策展的预训练语料，仍含会不利影响训练的数据点。识别并移除它们可加速收敛、提升整体表现，从而节省算力。本实验展示 In-Run Data Shapley 评估 Pile 子集数据质量的效果。我们均匀随机抽取约 10B token 的 Pile 子集并训练 GPT2，用 Pile 验证集做归因。滤掉所有负值语料并在清洗子集上重训后，收敛显著改善：一、二阶 In-Run Data Shapley 都能以约少 25% 的训练迭代达到测试损失 3.75。出人意料，约 16% 训练语料的二阶 In-Run Data Shapley 为负。部分负值或因相对验证语料的显著领域偏移，但我们仍在已经过多层策展的 Pile（Gao 等, 2020）中发现大量低质语料。识别出的低质语料示例见附录 E.3。

Figure 2: Test loss comparison between the original training run and the model trained on the cleaned subset according to different data attribution techniques.

图 2：原训练与按不同数据归因技术清洗子集后训练的测试损失比较。

Figure 2 shows a performance comparison between the original training run and the model trained on the cleaned subsets for GPT2, and additional results on Pythia-410M are available in Appendix E.3.1. We also compare with influence function (Koh & Liang, 2017), which approximates the change in the model’s loss on the test example when the training example is removed from the training set (i.e., the leave-one-out score). We omit TRAK (Park et al., 2023) and other techniques such as datamodel (Ilyas et al., 2022) as they are not scalable to our setting. As we can see, influence function can also filter out low-quality data that can accelerate training convergence. However, the performance is slightly worse than In-Run Data Shapley as the influence function only uses information from the final trained models, which can result in highly noisy value scores since the removal of one training data point might have a negligible effect on the final model performance. The results demonstrate that removing lower-quality data leads to a significantly faster drop in test loss compared to the original training run. This implies that there is still huge room for data curation for well-curated datasets such as Pile.

图 2 比较 GPT2 上原训练与清洗子集训练的表现；Pythia-410M 的补充结果见附录 E.3.1。我们也与影响函数（Koh & Liang, 2017）比较——它近似从训练集去掉某训练样本时测试损失的变化（即留一分数）。省略 TRAK（Park 等, 2023）与 datamodel（Ilyas 等, 2022）等，因其对本设定不可扩展。可见影响函数也能滤掉可加速收敛的低质数据，但略差于 In-Run Data Shapley：它只用最终已训模型的信息，去掉单点对最终表现影响可能微乎其微，价值分数因而噪声很大。结果表明去掉较低质量数据后，测试损失下降显著快于原训练，意味着即便如 Pile 这样已策展的数据集，数据策展仍有巨大空间。

\approx

Similarity Category	In-Run Data Shapley (1st order)	In-Run Data Shapley (2nd order)	Influence Function	BM25
Partial exactly the same	1	1	1	1
Paraphrase	1	1	1	1
Significant paraphrase	32.3	32	39.3	1.6
Similar topic	145.6	141.6	292	20917.3

相似度类别 In-Run Data Shapley（一阶） In-Run Data Shapley（二阶） 影响函数 BM25 部分完全相同 1111 改写 1111 大幅改写 32.3 32 39.3 1.6 相似主题 145.6 141.6 292 20917.3 表 2：上：（左）来自 Wikipedia 的原始训练语料。（右）与左侧 Wikipedia 语料属「相似主题」的合成语料（提示见附录 E.5）。下：对与原始语料相似度不等的验证语料，原始语料在全部训练语料中的（平均）价值排名。 排名基于约 32 万数据点 。

相似度类别	In-Run Data Shapley（一阶）	In-Run Data Shapley（二阶）	影响函数	BM25
部分完全相同	1	1	1	1
改写	1	1	1	1
大幅改写	32.3	32	39.3	1.6
相似主题	145.6	141.6	292	20917.3

G(\lambda)

G(\lambda)

<0

<0

5.3.3 Does Contribution Require Memorization? In this experiment, we evaluate the robustness of different data attribution techniques in identifying relevant individual corpora that have been paraphrased. We start by selecting a data point from the training set and creating several paraphrased versions using GPT-4, with varying levels of paraphrasing (see Appendix E.5 for the prompt). These paraphrased versions form our validation set. We then calculate the average value rank of the original training data for each of its paraphrased versions. In addition to In-Run Data Shapley and influence function, we include the ranking result based on BM25 distance. BM25 (Robertson et al., 2009) featurizes examples by their word frequency statistics (i.e., TF-IDF) to rank the training instances. We use BM25 distance as an oracle for assessing the verbatim or lexical similarity between the validation data (query) and the training data, as opposed to semantic similarity.

5.3.3 贡献是否要求记忆？ 本实验评估不同数据归因技术在识别「已被改写」的相关个体语料上的稳健性。我们从训练集选一点，用 GPT-4 生成不同程度的改写版本（提示见附录 E.5）作为验证集，再计算原始训练数据对其各改写版的平均价值排名。除 In-Run Data Shapley 与影响函数外，还加入基于 BM25 距离的排名。 BM25 （Robertson 等, 2009）用词频统计（即 TF-IDF）特征化样例以排序训练实例。我们用 BM25 距离作为评估验证数据（查询）与训练数据之间字面/词汇相似度——相对语义相似度——的 oracle。

As shown in Table 2, even for a validation data that is a complete rewrite (with a low BM25 distance) but covers relevant topics, the original training data still ranks very high according to both In-Run Data Shapley and influence function. Influence function ranks the original training data lower than In-Run Data Shapley, which may be attributed to the inherent noisy nature of the leave-one-out error estimation. The results of this experiment have important implications for the ongoing discussion about the copyright of generative AI. Specifically, the table presents a compelling example where the original Wikipedia training corpus related to a musician’s experience can significantly contribute to generating a story about a musician, even when the generated story shares no token-wise resemblance to the original training data. This finding supports that training data profoundly influences the capabilities of generative AI models and should be compensated accordingly (Deng & Ma, 2023; Wang et al., 2024b), even when the output does not closely resemble the original copyrighted material or when the model applies output filters to avoid generating verbatim replicates of the training data. This discovery expands the conventional focus on copyright violations, which typically addresses instances of near-verbatim replication, as seen in the dispute between New York Times and OpenAI, to also include cases where the generated content is significantly influenced by copyrighted material without directly replicating it.

如表 2，即便验证数据是完全改写（BM25 距离低）但主题相关，原始训练数据在 In-Run Data Shapley 与影响函数下仍排名很高。影响函数对原始训练数据的排名低于 In-Run Data Shapley，或因留一误差估计固有噪声。该结果对生成式 AI 版权讨论有重要含义。表中有一个有说服力的例子：与某音乐家经历相关的原始 Wikipedia 训练语料，可显著贡献于生成「关于音乐家的故事」，即便生成故事与原训练数据在 token 层面毫无相似。这支持：训练数据深刻影响生成式 AI 能力，应获相应补偿（Deng & Ma, 2023；Wang 等, 2024b）——即便输出并不酷似原版权材料，或模型用输出过滤避免逐字复现训练数据。该发现把版权侵权的传统焦点——多针对近乎逐字复制，如《纽约时报》与 OpenAI 之争——扩展到「生成内容受版权材料显著影响却未直接复制」的情形。

6 Conclusion and Limitations

In this work, we introduce In-Run Data Shapley, a novel data attribution technique that addresses the limitations of Retraining-based Data Shapley. Extensive experiments demonstrate the effectiveness of In-Run Data Shapley in various applications. Here, we discuss the potential limitations of this work.

本文提出 In-Run Data Shapley，一种应对基于重训的 Data Shapley 局限的新数据归因技术。大量实验展示了其在多种应用中的有效性。这里讨论潜在局限。

Availability of validation data before training. One potential limitation of In-Run Data Shapley is that it requires the validation data to be available before training, as the data attribution scores are computed during the training process. However, there are many scenarios where validation data is naturally available before training, such as when using publicly available benchmark datasets, participating in machine learning competitions, or adhering to regulatory requirements. For scenarios where validation data arrives after the model has been trained, a potential solution is to save checkpoints of intermediate models during training and approximate In-Run Data Shapley using these checkpoints, in the same spirit of TracIN-CP described in Pruthi et al. (2020). However, the choice of checkpoints can significantly impact performance, and it is unclear which checkpoints to pick.

训练前验证数据的可用性 。 In-Run Data Shapley 的潜在局限之一是：归因分数在训练过程中计算，因而要求验证数据在训练前可用。不过许多场景下验证数据本来就在训练前可得，例如使用公开基准、参加机器学习竞赛，或满足监管要求。若验证数据在模型训完后才到达，一个可能办法是保存中间检查点，并仿照 Pruthi 等 (2020) 的 TracIN-CP，用这些检查点近似 In-Run Data Shapley。但检查点选择会显著影响表现，选哪些仍不清楚。

Extension to other optimization algorithms. Extending the "ghost" family techniques developed in this work to support Adam and similar optimizers remains an exciting direction for future research. We stress that extending the formulation of In-Run Data Shapley from SGD to Adam is feasible, but the actual challenge lies in computing it efficiently without instantiating each individual gradient vector, which cannot be solved by simple extensions described in Xia et al. (2024).

扩展到其他优化算法 。 将本文「ghost」族技术扩展到 Adam 及类似优化器仍是有吸引力的未来方向。我们强调：把 In-Run Data Shapley 从 SGD 形式推广到 Adam 是可行的，真正挑战在于不实例化每个个体梯度向量而高效计算——这无法被 Xia 等 (2024) 所述的简单扩展解决。

Handling memory constraints. In scenarios where GPU memory constraints prevent large batch sizes, the "ghost" techniques can be extended by using gradient accumulation. This approach accommodates larger training batch sizes by dividing the batch into smaller sub-batches and accumulating gradients over multiple iterations. While this method may increase runtime due to additional backpropagation steps, it maintains the feasibility of the techniques under memory constraints. Improving computational efficiency for large batch sizes remains an important direction for future research.

处理显存约束 。 当 GPU 显存限制大 batch 时，「ghost」技术可通过梯度累积扩展：把大批拆成更小的子批，在多次迭代上累积梯度。虽可能因额外反向增加运行时间，但在显存约束下仍保持可行性。提升大批量时的计算效率仍是重要未来方向。

Acknowledgment

This work is supported in part by the National Science Foundation under grants IIS-2312794, IIS-2313130, OAC-2239622, Amazon-Virginia Tech Initiative in Efficient and Robust Machine Learning, and the Commonwealth Cyber Initiative.

本工作部分得到美国国家科学基金会资助（IIS-2312794、IIS-2313130、OAC-2239622），以及 Amazon-Virginia Tech Initiative in Efficient and Robust Machine Learning 与 Commonwealth Cyber Initiative 的支持。

We thank Meng Ding, Chong Xiang, Chendi Wang for their helpful feedback on the preliminary version of this work.

感谢 Meng Ding、Chong Xiang、Chendi Wang 对本文初稿的有益反馈。

References

Radford et al. (2019) Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. Language models are unsupervised multitask learners. 2019. Raffel et al. (2020) Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. Journal of machine learning research , 21(140):1-67, 2020. Robertson et al. (2009) Stephen Robertson, Hugo Zaragoza, et al. The probabilistic relevance framework: Bm25 and beyond. Foundations and Trends® in Information Retrieval , 3(4):333-389, 2009. Rochette et al. (2020) Gaspar Rochette, Andre Manoel, and Eric W Tramel. Efficient per-example gradient computations in convolutional neural networks. In Workshop on Theory and Practice of Differential Privacy (TPDP) , 2020. Schioppa (2024) Andrea Schioppa. Gradient sketches for training data attribution and studying the loss landscape. arXiv preprint arXiv:2402.03994 , 2024. Shapley (1953) Lloyd S Shapley. A value for n-person games. Contributions to the Theory of Games , 2(28):307-317, 1953. Søgaard et al. (2021) Anders Søgaard et al. Revisiting methods for finding influential examples. arXiv preprint arXiv:2111.04683 , 2021. Touvron et al. (2023) Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al. Llama: Open and efficient foundation language models. arXiv preprint arXiv:2302.13971 , 2023. Wang & Jia (2023a) Jiachen T Wang and Ruoxi Jia. Data banzhaf: A robust data valuation framework for machine learning. In International Conference on Artificial Intelligence and Statistics , pp. 6388-6421. PMLR, 2023a. Wang & Jia (2023b) Jiachen T Wang and Ruoxi Jia. A note on" towards efficient data valuation based on the shapley value”. arXiv preprint arXiv:2302.11431 , 2023b.

Wang & Jia (2023c) Jiachen T Wang and Ruoxi Jia. A note on" efficient task-specific data valuation for nearest neighbor algorithms". arXiv preprint arXiv:2304.04258 , 2023c. Wang et al. (2023) Jiachen T Wang, Yuqing Zhu, Yu-Xiang Wang, Ruoxi Jia, and Prateek Mittal. Threshold knn-shapley: A linear-time and privacy-friendly approach to data valuation. arXiv preprint arXiv:2308.15709 , 2023. Wang et al. (2024a) Jiachen T Wang, Zhun Deng, Hiroaki Chiba-Okabe, Boaz Barak, and Weijie J Su. An economic solution to copyright challenges of generative ai. Technical report, 2024a. Wang et al. (2024b) Jiachen T Wang, Zhun Deng, Hiroaki Chiba-Okabe, Boaz Barak, Weijie J Su, et al. An economic solution to copyright challenges of generative ai. arXiv preprint arXiv:2404.13964 , 2024b. Wang et al. (2024c) Jiachen T Wang, Prateek Mittal, and Ruoxi Jia. Efficient data shapley for weighted nearest neighbor algorithms. arXiv preprint arXiv:2401.11103 , 2024c. Wang et al. (2024d) Jiachen T Wang, Tianji Yang, James Zou, Yongchan Kwon, and Ruoxi Jia. Rethinking data shapley for data selection tasks: Misleads and merits. arXiv preprint arXiv:2405.03875 , 2024d. Wang et al. (2020) Tianhao Wang, Johannes Rausch, Ce Zhang, Ruoxi Jia, and Dawn Song. A principled approach to data valuation for federated learning. In Federated Learning , pp. 153-167. Springer, 2020. Xia et al. (2024) Mengzhou Xia, Sadhika Malladi, Suchin Gururangan, Sanjeev Arora, and Danqi Chen. Less: Selecting influential data for targeted instruction tuning. In Forty-first International Conference on Machine Learning , 2024. Yang et al. (2024) Ziao Yang, Han Yue, Jian Chen, and Hongfu Liu. On the inflation of knn-shapley value. arXiv preprint arXiv:2405.17489 , 2024. Yeh et al. (2022) Chih-Kuan Yeh, Ankur Taly, Mukund Sundararajan, Frederick Liu, and Pradeep Ravikumar. First is better than last for training data influence. arXiv preprint arXiv:2202.11844 , 2022.

Yu et al. (2020) Tianhe Yu, Saurabh Kumar, Abhishek Gupta, Sergey Levine, Karol Hausman, and Chelsea Finn. Gradient surgery for multi-task learning. Advances in Neural Information Processing Systems , 33:5824-5836, 2020.

Appendix A Extended Related Works

A.1 Data Shapley Axioms

Data Shapley is one of the first principled approaches to data attribution being proposed Ghorbani & Zou (2019); Jia et al. (2019b). Data Shapley is based on the famous Shapley value (Shapley, 1953). In almost all of the literature, the Shapley value is being justified as the unique value notion satisfying the following four axioms:

Data Shapley 是最早被提出的有原则数据归因方法之一（Ghorbani & Zou, 2019；Jia 等, 2019b），基于著名的 Shapley 值 （Shapley, 1953）。几乎所有文献中，Shapley 值都被论证为满足以下四条公理的 唯一 价值概念：

U(S\cup\{z_{i}\})=U(S)

S\subseteq D\setminus\{z_{i}\}

In plain words, null player axiom means the Shapley value will assign zero score to data points with no contribution. Symmetry axiom requires equal scores assigned to equally impactful data points, ensuring fairness. Efficiency axiom requires the sum of contribution scores equal to the total utility, meaning the scores always represent a share of the total utility. Linearity axiom means the Shapley value supports additive decomposition across multiple utility functions, allowing for the calculation of contributions to the entire test set by summing the scores of individual test points.

通俗地说， 空参与者 公理要求对无贡献数据点赋零分； 对称性 要求同等影响力的点得同等分，保证公平； 效率 要求贡献分之和等于总效用，分数始终是总效用的份额； 线性性 意味着 Shapley 值支持跨多个效用函数的可加分解，从而可用各测试点分数之和得到整个测试集上的贡献。

A.2 Data Shapley and Friends

Since its introduction in 2019 (Ghorbani & Zou, 2019; Jia et al., 2019b), Data Shapley has rapidly gained popularity as a principled solution for data attribution. Due to the computationally expensive nature of retraining-based Data Shapley, various Monte Carlo-based approximation algorithms have been developed (Jia et al., 2019b; Illés & Kerényi, 2019; Okhrati & Lipani, 2021; Burgess & Chapman, 2021; Mitchell et al., 2022; Lin et al., 2022; Wang & Jia, 2023b; Li & Yu, 2023; Covert et al., 2024), these methods still necessitate extensive computational resources due to repeated model retraining, which is clearly impractical for modern-sized ML models. Many of its variants have been proposed. Kwon & Zou (2022) argues that the efficiency axiom is not necessary for many machine learning applications, and the framework of semivalue is derived by relaxing the efficiency axiom. Lin et al. (2022) provide an alternative justification for semivalue based on causal inference and randomized experiments. Based on the framework of semivalue, Kwon & Zou (2022) propose Beta Shapley, which is a collection of semivalues that enjoy certain mathematical convenience. Wang & Jia (2023a) propose Data Banzhaf, and show that the Banzhaf value, another famous solution concept from cooperative game theory, achieves more stable valuation results under stochastic learning algorithms. Li & Yu (2024) further improves the valuation stability by considering value notions outside the scope of semivalue.

自 2019 年提出以来（Ghorbani & Zou, 2019；Jia 等, 2019b），Data Shapley 迅速成为数据归因的原则性方案。因基于重训的计算昂贵，出现多种蒙特卡洛近似算法（Jia 等, 2019b；Illés & Kerényi, 2019；Okhrati & Lipani, 2021；Burgess & Chapman, 2021；Mitchell 等, 2022；Lin 等, 2022；Wang & Jia, 2023b；Li & Yu, 2023；Covert 等, 2024），但反复重训仍需大量算力，对现代规模模型显然不现实。亦有许多变体：Kwon & Zou (2022) 认为效率公理对许多机器学习应用并非必要，并放松该公理得到 半价值（semivalue） 框架；Lin 等 (2022) 从因果推断与随机实验给出半价值的另一论证；在此框架上 Kwon & Zou (2022) 提出具有某些数学便利的 Beta Shapley ；Wang & Jia (2023a) 提出 Data Banzhaf ，表明合作博弈论中另一著名解概念 Banzhaf 值在随机学习算法下估值更稳；Li & Yu (2024) 进一步考虑半价值范围之外的概念以提升估值稳定性。

The classic leave-one-out error is also a semivalue, where the influence function (Cook & Weisberg, 1980; Koh & Liang, 2017; Grosse et al., 2023) is generally considered as its approximation. A concurrent work (Choe et al., 2024) leverages a similar gradient decomposition technique as our paper to speed up influence function calculation. However, several works have pointed out the fragility of influence function for deep learning models (Basu et al., 2021; Søgaard et al., 2021; Bae et al., 2022), due to the strong assumptions of training convergence and strongly convexity of the loss function. Nguyen et al. (2023) takes a Bayesian view of data attribution and is able to evaluate the variance of LOO. Unlike Nguyen et al. (2023), our work explicitly incorporates specific training randomness (e.g., model initialization, batch ordering) into the utility function definition, providing attribution scores that reflect contributions to the exact training trajectory.

经典留一误差也是半价值， 影响函数 （Cook & Weisberg, 1980；Koh & Liang, 2017；Grosse 等, 2023）一般被视为其近似。同期工作（Choe 等, 2024）用与本文类似的梯度分解加速影响函数计算。但多篇工作指出影响函数对深度学习模型脆弱（Basu 等, 2021；Søgaard 等, 2021；Bae 等, 2022），因其依赖训练收敛与损失强凸等强假设。Nguyen 等 (2023) 从贝叶斯视角做数据归因并能评估 LOO 方差。与 Nguyen 等 (2023) 不同，我们把具体训练随机性（如初始化、批顺序）显式编入效用定义，使归因分数反映对精确训练轨迹的贡献。

Another line of works focuses on improving the computational efficiency of Data Shapley by considering K nearest neighbor (KNN) as the surrogate learning algorithm for the original, potentially complicated deep learning models (Jia et al., 2019a; Wang & Jia, 2023c; Wang et al., 2023; Wang et al., 2024c; Yang et al., 2024). Ghorbani et al. (2020); Kwon et al. (2021); Li & Yu (2023) consider Distributional Shapley, a generalization of Data Shapley to data distribution. In federated learning setting, Wang et al. (2020) proposes a similar idea of computing the Shapley value for each federated learning round.

另一路线用 K 近邻（KNN）作原复杂深度学习模型的代理学习算法，以提升 Data Shapley 计算效率（Jia 等, 2019a；Wang & Jia, 2023c；Wang 等, 2023；Wang 等, 2024c；Yang 等, 2024）。Ghorbani 等 (2020)；Kwon 等 (2021)；Li & Yu (2023) 考虑面向数据分布的 Distributional Shapley。在联邦学习设定下，Wang 等 (2020) 提出对每一联邦轮次计算 Shapley 值的类似想法。

Remark 3 . Randomized Monte Carlo estimators can be inefficient and may produce unstable valuation results, potentially violating fairness axioms of the Shapley value (e.g., the Symmetry axiom) due to inherent approximation errors. In contrast, In-Run Data Shapley does not rely on Monte Carlo estimators. Instead, it computes the exact Shapley value for an approximated utility function via Taylor expansion. This approach adheres to the fairness axioms while ensuring the reliability and consistency of the data valuation results.

注记 3 。 随机蒙特卡洛估计器可能低效，并因固有逼近误差产生不稳估值，可能违反 Shapley 值公平公理（如对称性）。相反，In-Run Data Shapley 不依赖蒙特卡洛；它通过对逼近效用（Taylor 展开）计算精确 Shapley 值，既遵守公平公理，又保证数据估值结果的可靠与一致。

A.3 Comparison with TracIN (Pruthi et al., 2020)

The form of first-order In-Run Data Shapley from Section 4.1 coincides with the TracIN-Ideal in Pruthi et al. (2020). This provides a new understanding of TracIN-Ideal as an approximation to In-Run Data Shapley. Both works face the technical challenge of requiring per-sample gradient computations during a single training run. Pruthi et al. (2020) proposes TracIN-CP, which mitigates the computational burden by examining only a subset of intermediate checkpoints during training. At each checkpoint, the individual gradients for the entire training set are computed, rather than for a sampled batch, under the assumption that each training example is visited exactly once between checkpoints. A recent work (Xia et al., 2024) leverages TracIN-CP, an approximation algorithm for TracIN-Ideal, for instruction-following data selection. This approach, however, may deviate significantly from the original TracIN-Ideal, with the final valuation results heavily dependent on the selected checkpoints. Furthermore, Pruthi et al. (2020)’s implementation is limited to the parameters of the last linear layer due to memory constraints, potentially biasing the measurement of data contribution. For instance, Yeh et al. (2022) suggests that the last layer of a neural network might exhibit a strong "cancellation effect," where the data influence of different examples have large, contradictory magnitudes. Additionally, Schioppa (2024) demonstrates that selecting different layers can distort data attribution scores. In contrast, this work introduces the "ghost dot-product" technique to efficiently compute the first-order In-Run Data Shapley (i.e., TracIN-Ideal) directly and accurately, without additional approximations.

第 4.1 节一阶 In-Run Data Shapley 的形式与 Pruthi 等 (2020) 的 TracIN-Ideal 一致，从而把 TracIN-Ideal 理解为对 In-Run Data Shapley 的一种逼近。两工作都面临单次训练中需逐样本梯度的技术挑战。Pruthi 等 (2020) 提出 TracIN-CP ：只检查训练中部分中间检查点以减轻负担；在每个检查点对整个训练集（而非采样批）算个体梯度，并假设检查点之间每个训练例恰好被访问一次。近期工作（Xia 等, 2024）用 TracIN-Ideal 的近似算法 TracIN-CP 做指令遵循数据选择，但可能显著偏离原 TracIN-Ideal，最终估值严重依赖所选检查点。此外，受显存限制，Pruthi 等 (2020) 的实现仅覆盖最后线性层参数，可能偏置贡献度量——例如 Yeh 等 (2022) 指出末层可能有强「抵消效应」，不同样例影响幅度大且方向矛盾；Schioppa (2024) 也表明选不同层会扭曲归因分数。相反，本文引入「ghost 点积」技术，直接、准确地高效计算一阶 In-Run Data Shapley（即 TracIN-Ideal），无需额外近似。

Appendix B Additional Discussion

In this section, we provide additional discussion about In-Run Data Shapley as well as its comparison with Retraining-based Data Shapley. Figure 4 gives a more detailed overview of our algorithm, and Figure 5 provides a visualized comparison between Retraining-based and In-Run Data Shapley.

本节补充讨论 In-Run Data Shapley，并与基于重训的 Data Shapley 比较。图 4 更细地概览算法，图 5 可视化二者对比。

t

t

Figure 5: Comparison between Retraining-based and In-Run Data Shapley. Retraining-based Data Shapley requires training a model from scratch on all possible subsets of the full training set, which is computationally inefficient and raises concerns about interpretability and stability. In contrast, In-Run Data Shapley acts as a "contribution accountant", efficiently tracking and attributing data value scores to each training example across gradient update steps during a single training run.

图 5：基于重训与 In-Run Data Shapley 的比较。前者需在完整训练集的所有可能子集上从零训练，计算低效且有可解释性与稳定性之忧。后者像「贡献会计」，在单次训练中高效跟踪并为每个训练例跨梯度更新步归因价值分数。

B.1 When is In-Run Data Shapley Desirable for Data Attribution?

While Retraining-based Data Shapley has been widely adopted in the literature, it suffers from several critical issues that limit its practicality and effectiveness. In this section, we discuss these problems from four key aspects: computational efficiency, alignment with the purpose of data valuation, stability of the valuation results, and the choice of training hyperparameters.

尽管基于重训的 Data Shapley 在文献中被广泛采用，它仍有若干严重问题限制其实用性与有效性。本节从四方面讨论：计算效率、与数据估值目的的对齐、估值结果稳定性，以及训练超参选择。

K

K

(2) Retraining-based Data Shapley is unable to assess data contribution to a specific model. Crucially, Retraining-based Data Shapley is not designed to value data contribution towards a specific model. It attempts to quantify the average contribution of each training data point to models trained on different subsets of the data, rather than its contribution to the specific model trained on the full dataset. While one might interpret the former as an approximation of the latter, these two quantities can be quite different in practice, especially when the learning algorithm is randomized and sensitive to factors like random initialization and the order of the data points during training. More importantly, in most real-life scenarios, the primary interest lies in understanding the contribution of each data point to the specific model being trained and deployed.

（2）基于重训的 Data Shapley 无法评估对特定模型的数据贡献 。 关键是：它并非为对某个具体模型估值数据贡献而设计。它试图量化各训练点对「在不同子集上训出的模型」的平均贡献，而非对「在全数据上训出的那个具体模型」的贡献。虽可将前者视为后者近似，实践中二者可相差甚远——尤其当学习算法随机、对初始化与数据顺序敏感时。更重要的是，多数真实场景真正关心的，正是正在训练并部署的那一个模型上各点的贡献。

(3) Retraining-based Data Shapley produces unstable valuation results for stochastic training algorithms. Furthermore, when the training algorithm involves randomness, such as in the case of SGD with random mini-batch selection, the corresponding utility function becomes randomized. Prior work (Wang & Jia, 2023a) suggests that this randomness can introduce substantial noise into the estimated Shapley values, rendering them unreliable and unstable. This instability poses significant challenges for interpreting and using the resulting data valuations, as the scores may vary considerably across different runs of the algorithm, even on the same dataset. Consequently, this limits the practical applicability of Retraining-based Data Shapley when working with stochastic training algorithms, which are prevalent in modern machine learning. We note that similar vulnerabilities to learning stochasticity have been observed for LOO-based data influence scores (e.g., influence function (Koh & Liang, 2017)) in several works (Basu et al., 2021; Søgaard et al., 2021; Nguyen et al., 2023).

（3）对随机训练算法，基于重训的 Data Shapley 估值不稳 。 当训练含随机性（如带随机小批选择的 SGD）时，对应效用函数本身随机。先前工作（Wang & Jia, 2023a）指出，这种随机性会给估计的 Shapley 值引入大量噪声，使其不可靠、不稳定。分数在同数据集上不同运行间可大幅波动，给解释与使用带来挑战，从而限制其在现代机器学习常见随机训练算法下的实用性。我们注意到，若干工作（Basu 等, 2021；Søgaard 等, 2021；Nguyen 等, 2023）对基于 LOO 的数据影响分数（如影响函数（Koh & Liang, 2017））也观察到对学习随机性的类似脆弱。

U(S)

S

In-Run Data Shapley addresses all these issues, making it more desirable for specific scenarios. Firstly, it is computationally efficient as it computes data values during the training run, avoiding the need for multiple retraining iterations. This makes it feasible for modern large-scale ML models. Secondly, it aligns better with the purpose of data valuation by assessing the contribution of each data point to the specific model being trained, providing more relevant insights for real-world applications. Lastly, In-Run Data Shapley offers deterministic valuation results even with stochastic training algorithms, as it incorporates the specific sequence and randomness of the training process into the utility function. Therefore, for scenarios where computational efficiency, model-specific contributions, and result stability are critical, In-Run Data Shapley is a more suitable choice.

In-Run Data Shapley 应对上述所有问题，在特定场景下更可取。首先，它在训练过程中算数据价值，无需多次重训，计算高效，对现代大规模模型可行。其次，它评估各点对正在训练的具体模型的贡献，更对齐数据估值目的，对现实应用更相关。最后，即便训练算法随机，它把具体序列与随机性编入效用，仍给出确定性估值。因此，当计算效率、模型特定贡献与结果稳定性关键时，In-Run Data Shapley 更合适。

U(S)

U(S)

Data attribution should consider specific application scenario. From a broader perspective, the "optimal data attribution" notion heavily depends on the intended application. In the literature, data attribution techniques are being used for various purposes such as data quality assessment, data valuation, and interpreting model predictions. For data quality assessment, we require "algorithm-level data attribution" that measures a data point’s general influence on the learning algorithm, independent of specific training random seeds. On the other hand, when interpreting model decisions, we need model-specific data attribution focused on the particular checkpoint we train. Systematically mapping which data attribution approaches best suit specific application scenarios remains an important direction for future research.

数据归因应考虑具体应用场景。更广地说，「最优数据归因」概念高度依赖预期应用。文献中数据归因被用于数据质量评估、数据估值与解释模型预测等。对数据质量评估，需要 「算法级数据归因」 ，度量点对学习算法的一般影响，独立于具体训练随机种子；而解释模型决策时，需要聚焦所训具体检查点的模型特定归因。系统梳理何种归因方法最适合何种应用场景，仍是重要未来方向。

B.2 When is Retraining-based Data Shapley Desirable for Data Attribution?

Retraining-based Data Shapley is still desirable in several scenarios. Firstly, it is more general and applicable to all learning algorithms, whereas In-Run Data Shapley is only applicable to iterative training algorithms. Secondly, retraining-based Shapley is useful when the goal is to understand the contribution of data points to the general learning process rather than to a specific model. Thirdly, because Retraining-based Data Shapley does not require modifying the internal code of the training algorithm, its estimation algorithm, typically Monte Carlo-based, is straightforward and clean to implement.

基于重训的 Data Shapley 在若干场景仍可取。首先，它更通用，适用于所有学习算法，而 In-Run Data Shapley 仅适用于迭代训练算法。其次，当目标是理解数据点对一般学习过程——而非某个具体模型——的贡献时，基于重训的 Shapley 有用。第三，它无需修改训练算法内部代码，其估计算法（通常基于蒙特卡洛）实现直接、干净。

B.3 Potential Extensions of In-Run Data Shapley to Other Domains

While this work focuses on data attribution for SGD-trained machine learning models, we believe the core idea of In-Run Data Shapley—decomposing contribution analysis into per-iteration assessments—can potentially be extended to other contexts and applications. Here, we discuss some directions.

本文聚焦 SGD 训练的机器学习模型的数据归因，但我们相信 In-Run Data Shapley 的核心想法——把贡献分析分解为逐迭代评估——有望扩展到其他语境与应用。这里讨论若干方向。

Data attribution for iterative learning algorithms that do not use gradient descent. Our framework could potentially extend to iterative learning algorithms that don’t use gradient descent, such as k-means clustering or decision tree learning. Though these algorithms update models differently, they still proceed iteratively (e.g., k-means alternates between assignment and update steps; decision trees are built through recursive partitioning). For such algorithms, we could analyze how each data point influences these discrete update steps and aggregate these influences across iterations, similar to our approach with gradient-based training.

对不用梯度下降的迭代学习算法做数据归因 。 框架或可扩展到 k-means、决策树学习等不用梯度下降的迭代算法。虽更新方式不同，它们仍迭代进行（如 k-means 在分配与更新间交替；决策树经递归划分构建）。对这类算法，可分析各数据点如何影响这些离散更新步，并像梯度训练一样跨迭代聚合影响。

Hyperparameter importance. The framework could potentially be adapted to evaluate hyperparameter contributions during training. One possibility is to set a "baseline" hyperparameter value and assess how choosing a different value impacts each training iteration compared to this baseline. For instance, when evaluating learning rate choices, we could measure how using a specific learning rate value affects model updates compared to using a baseline learning rate. For differentiable hyperparameters, we could leverage Taylor expansion to approximate this difference; for non-differentiable ones, zero-order methods could potentially be used. By accumulating these contributions across training iterations, we could understand hyperparameter impact without requiring multiple complete training runs. At a high level, this view unifies our treatment of training data and hyperparameters - both can be seen as choices that influence each training iteration, where we aim to quantify their impact against baseline scenarios. While technical challenges remain in adapting our method, this direction presents an interesting opportunity for future research.

超参重要性 。 框架或可改编以评估训练中超参的贡献。一种可能是设「基线」超参值，评估相对基线换用另一值对每轮训练的影响。例如评估学习率选择时，可度量用某学习率相对基线学习率如何影响模型更新。对可微超参，可用 Taylor 展开逼近该差；对不可微者，或可用零阶方法。跨迭代累加这些贡献，便有望在无需多次完整训练的情况下理解超参影响。宏观上，这把训练数据与超参统一为影响每轮训练的选择，目标是相对基线量化其影响。虽改编方法仍有技术挑战，该方向是有趣的未来机会。

Feature attribution (e.g., context-attribution for language models). Another possible extension we envision is feature attribution for machine learning models. Feature attribution aims at understanding how each part of the input (like individual words in a sentence or pixels in an image) influences a model’s final prediction. When a model makes a prediction, the input features are processed through multiple layers, with each layer transforming the information before passing it to the next layer. Feature attribution aims to track how this information flows and transforms through the network to determine each input feature’s contribution to the final output. We envision a unified theoretical framework connecting training data attribution and feature attribution, drawing parallels between how information flows during training (through gradient updates) and during prediction (through layer operations). This could lead to more efficient methods for explaining model behavior, particularly for complex architectures like transformers.

特征归因（如语言模型的上下文归因） 。 另一可能扩展是机器学习模型的特征归因：理解输入各部分（句子中的词、图像中的像素）如何影响最终预测。模型预测时，输入特征经多层处理，每层变换信息再传给下一层；特征归因旨在跟踪信息如何在网络中流动与变换，以确定各输入特征对最终输出的贡献。我们设想一个连接训练数据归因与特征归因的 统一理论框架 ，类比训练中信息如何经梯度更新流动，与预测中如何经层运算流动。这或能带来更高效的模型行为解释方法，尤其对 transformer 等复杂架构。

Appendix C Missing Proofs

Theorem 5 (Restate of Theorem 3) . In-Run Data Shapley considering the first-order approximation has closed-form

定理 5 （定理 3 的重述）。 考虑一阶逼近的 In-Run Data Shapley 具有闭式

\displaystyle\phi_{z}\left(U\right)\approx\sum_{t=0}^{T-1}\phi_{z}\left(U^{(t)}_{(1)}\right)

where

其中

\displaystyle\phi_{z}\left(U^{(t)}_{(1)}\right)=-\eta_{t}\nabla\ell(w_{t},z^{(\mathrm{val})})\cdot\nabla\ell(w_{t},z),~~~t=0,\ldots,T-1

x_{j}:=\nabla\ell(w_{t},z_{j})

x_{j}:=\nabla\ell(w_{t},z_{j})

\displaystyle U^{(t)}_{(1)}(S)=-\eta_{t}\sum_{z_{j}\in S}\nabla\ell(w_{t},z^{(\mathrm{val})})\cdot\nabla\ell(w_{t},z_{j}),

z

S\subseteq\mathcal{B}_{t}\setminus z

\displaystyle U^{(t)}_{(2)}(S\cup z)-U^{(t)}_{(2)}(S)=-\eta_{t}\nabla\ell(w_{t},z^{(\mathrm{val})})\cdot\nabla\ell(w_{t},z)

Plugging in the expression to the Shapley value’s definition immediately gives the result. ∎

将该表达式代入 Shapley 值定义即得结果。∎

Theorem 6 (Restate of Theorem 4) . In-Run Data Shapley considering the second-order approximation has closed-form

定理 6 （定理 4 的重述）。 考虑二阶逼近的 In-Run Data Shapley 具有闭式

\displaystyle\phi_{z}\left(U\right)\approx\sum_{t=0}^{T-1}\left(\phi_{z}\left(U^{(t)}_{(1)}\right)+\frac{1}{2}\phi_{z}\left(U^{(t)}_{(2)}\right)\right) \tag{6}

where

其中

\displaystyle\phi_{z}\left(U^{(t)}{(1)}\right)+\frac{1}{2}\phi{z}\left(U^{(t)}{(2)}\right)=\underbrace{-\eta{t}\nabla\ell(w_{t},z^{(\mathrm{val})})\cdot\nabla\ell(w_{t},z)}{\text{\hbox to9.41pt{\vbox to9.41pt{\pgfpicture\makeatletter\hbox{\hskip 4.70488pt\lower-4.70488pt\hbox to0.0pt{\lxSVG@begingroup@{scopebegin=1} \lxSVG@begingroup@{stroke=#000000} \lxSVG@begingroup@{fill=#000000} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width=0.4pt} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{scopebegin=1} {{{}}\lx@inpgf@ignorespaces\hbox{\hbox{{\lxSVG@begingroup@{scopebegin=1} {{}{{{}}}{{}}{}{}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{}{}{}{}{}{{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 6.23 0 C 6.23 3.44 3.44 6.23 0 6.23 C -3.44 6.23 -6.23 3.44 -6.23 0 C -6.23 -3.44 -3.44 -6.23 0 -6.23 C 3.44 -6.23 6.23 -3.44 6.23 0 Z M 0 0}{fill:none} \lx@inpgf@ignorespaces}{{{{\lx@inpgf@ignorespaces}}\lxSVG@begingroup@{scopebegin=1} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{-2.11113pt}{-2.25555pt}\lxSVG@begingroup@{transform=matrix(1.0 0.0 0.0 1.0 -2.92 -3.12)} \pgfsys@hbox{63}\lxSVG@closescope }}}\lxSVG@closescope }}}}\lxSVG@closescope {{{}}}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}} influence of }z\text{ on the loss of }z^{(\mathrm{val})}}+\underbrace{\frac{\eta{t}^{2}}{2}\nabla\ell(w{t},z)^{\intercal}\textbf{H}^{(z^{(\mathrm{val})})}{t}\left(\sum{z{j}\in\mathcal{B}{t}}\nabla\ell(w{t},z_{j})\right)}_{\text{\hbox to9.41pt{\vbox to9.41pt{\pgfpicture\makeatletter\hbox{\hskip 4.70488pt\lower-4.70488pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin=1} \lxSVG@begingroup@{stroke=#000000} \lxSVG@begingroup@{fill=#000000} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width=0.4pt} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin=1} {{{}}\lx@inpgf@ignorespaces\hbox{\hbox{{\lxSVG@begingroup@{_scopebegin=1} {{}{{{}}}{{}}{}{}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{}{}{}{}{}{{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 6.23 0 C 6.23 3.44 3.44 6.23 0 6.23 C -3.44 6.23 -6.23 3.44 -6.23 0 C -6.23 -3.44 -3.44 -6.23 0 -6.23 C 3.44 -6.23 6.23 -3.44 6.23 0 Z M 0 0}{fill:none} \lx@inpgf@ignorespaces}{{{{\lx@inpgf@ignorespaces}}\lxSVG@begingroup@{_scopebegin=1} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{-2.11113pt}{-2.25555pt}\lxSVG@begingroup@{transform=matrix(1.0 0.0 0.0 1.0 -2.92 -3.12)} \pgfsys@hbox{63}\lxSVG@closescope }}}\lxSVG@closescope }}}}\lxSVG@closescope {{{}}}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}} interaction between }z\text{ and other training points}} \tag{7}

t=0,\ldots,T-1

t=0,\ldots,T-1

Proof. We show that

证明。 我们证明

\displaystyle\phi_{z}\left(U^{(t)}_{(2)}\right)=\eta_{t}^{2}\nabla\ell(w_{t},z)\textbf{H}^{(z^{(\mathrm{val})})}_{t}\left(\sum_{z_{j}\in\mathcal{B}_{t}}\nabla\ell(w_{t},z_{j})\right).

x_{j}:=\nabla\ell(w_{t},z_{j})

x_{j}:=\nabla\ell(w_{t},z_{j})

\displaystyle U^{(t)}_{(2)}(S\cup z)-U^{(t)}_{(2)}(S)=\eta_{t}^{2} \\ \displaystyle\left(2\tilde{x}\textbf{H}^{(z^{(\mathrm{val})})}_{t}\left(\sum_{z_{j}\in S}x_{j}\right)+\tilde{x}^{\intercal}\textbf{H}^{(z^{(\mathrm{val})})}_{t}\tilde{x}\right).

Plug the above expression into the Shapley value’s formula, we have

将上式代入 Shapley 值公式，得

\displaystyle\phi_{z}\left(U^{(t)}_{(2)}\right) \\ \displaystyle=\eta_{t}^{2}\left(\tilde{x}^{\intercal}\textbf{H}^{(z^{(\mathrm{val})})}_{t}\tilde{x}+\frac{2}{n_{t}}\sum_{k=1}^{n_{t}}{n_{t}-1\choose k-1}^{-1}\sum_{S\subseteq\mathcal{B}_{t}\setminus\{z\},~|S|=k-1}\left[\tilde{x}^{\intercal}\textbf{H}^{(z^{(\mathrm{val})})}_{t}\sum_{z_{j}\in S}x_{j}\right]\right) \\ \displaystyle=\eta_{t}^{2}\left(\tilde{x}^{\intercal}\textbf{H}^{(z^{(\mathrm{val})})}_{t}\tilde{x}+\tilde{x}^{\intercal}\textbf{H}^{(z^{(\mathrm{val})})}_{t}\left[\frac{2}{n_{t}}\sum_{k=1}^{n_{t}}{n_{t}-1\choose k-1}^{-1}\sum_{S\subseteq\mathcal{B}_{t}\setminus\{z\},~|S|=k-1}\left(\sum_{z_{j}\in S}x_{j}\right)\right]\right) \\ \displaystyle=\eta_{t}^{2}\left(\tilde{x}^{\intercal}\textbf{H}^{(z^{(\mathrm{val})})}_{t}\tilde{x}+\tilde{x}^{\intercal}\textbf{H}^{(z^{(\mathrm{val})})}_{t}\left[\frac{2}{n_{t}}\sum_{k=2}^{n_{t}}{n_{t}-1\choose k-1}^{-1}{n_{t}-2\choose k-2}\left(\sum_{z_{j}\in\mathcal{B}_{t}\setminus\{z\}}x_{j}\right)\right]\right) \\ \displaystyle=\eta_{t}^{2}\left(\tilde{x}^{\intercal}\textbf{H}^{(z^{(\mathrm{val})})}_{t}\tilde{x}+\tilde{x}^{\intercal}\textbf{H}^{(z^{(\mathrm{val})})}_{t}\left[\frac{2}{n_{t}}\sum_{k=2}^{n_{t}}\frac{k-1}{n_{t}-1}\left(\sum_{z_{j}\in\mathcal{B}_{t}\setminus\{z\}}x_{j}\right)\right]\right) \\ \displaystyle=\eta_{t}^{2}\left(\tilde{x}^{\intercal}\textbf{H}^{(z^{(\mathrm{val})})}_{t}\tilde{x}+\tilde{x}^{\intercal}\textbf{H}^{(z^{(\mathrm{val})})}_{t}\left(\sum_{z_{j}\in\mathcal{B}_{t}\setminus\{z\}}x_{j}\right)\right) \\ \displaystyle=\eta_{t}^{2}\left[\tilde{x}^{\intercal}\textbf{H}^{(z^{(\mathrm{val})})}_{t}\left(\sum_{z_{j}\in\mathcal{B}_{t}}x_{j}\right)\right]

∎

Appendix D Technical Details

\textbf{s}=\textbf{a}\textbf{W}

\textbf{s}=\textbf{a}\textbf{W}

D.1 Ghost Dot-Product

\ell^{(i)}:=\ell(w,z_{i})

\ell^{(i)}:=\ell(w,z_{i})

\displaystyle\frac{\partial\ell^{(i)}}{\partial\textbf{W}}=\frac{\partial\ell^{(i)}}{\partial\textbf{s}^{(i)}}\frac{\partial\textbf{s}^{(i)}}{\partial\textbf{W}}=\frac{\partial\ell^{(i)}}{\partial\textbf{s}^{(i)}}\textbf{a}^{(i)}=\frac{\partial\ell}{\partial\textbf{s}^{(i)}}\textbf{a}^{(i)}=\textbf{a}^{(i)}\otimes\textbf{b}^{(i)} \tag{8}

\ell:=\sum_{j=1}^{B}\ell^{(j)}

\ell:=\sum_{j=1}^{B}\ell^{(j)}

\frac{\partial\ell^{(1)}}{\partial\textbf{W}}\odot\frac{\partial\ell^{(2)}}{\partial\textbf{W}}

z_{1},z_{2}

\textbf{a}^{(i)}\in\mathbb{R}^{d_{1}\times 1}

\textbf{a}^{(i)}\in\mathbb{R}^{d_{1}\times 1}

\displaystyle\frac{\partial\ell^{(1)}}{\partial\textbf{W}}\odot\frac{\partial\ell^{(2)}}{\partial\textbf{W}}=\left(\textbf{a}^{(1)}\otimes\textbf{b}^{(1)}\right)\odot\left(\textbf{a}^{(2)}\otimes\textbf{b}^{(2)}\right)=\left(\left(\textbf{b}^{(1)}\right)^{\intercal}\left(\textbf{b}^{(2)}\right)\right)\left(\left(\textbf{a}^{(1)}\right)^{\intercal}\textbf{a}^{(2)}\right)

\frac{\partial\ell^{(1)}}{\partial\textbf{W}}

\frac{\partial\ell^{(1)}}{\partial\textbf{W}}

\textbf{a}^{(i)}\in\mathbb{R}^{d_{1}\times T}

\textbf{a}^{(i)}\in\mathbb{R}^{d_{1}\times T}

\displaystyle\frac{\partial\ell^{(1)}}{\partial\textbf{W}}\odot\frac{\partial\ell^{(2)}}{\partial\textbf{W}}=\left(\textbf{a}^{(1)}\otimes\textbf{b}^{(1)}\right)\odot\left(\textbf{a}^{(2)}\otimes\textbf{b}^{(2)}\right) \\ \displaystyle=\sum_{j,k=1}^{d_{1},d_{2}}\left(\textbf{a}^{(1)}\otimes\textbf{b}^{(1)}\right)_{j,k}\left(\textbf{a}^{(2)}\otimes\textbf{b}^{(2)}\right)_{j,k} \\ \displaystyle=\sum_{j,k=1}^{d_{1},d_{2}}\left(\textbf{a}^{(1)}_{j}\textbf{b}^{(1)}_{k}\right)\left(\textbf{a}^{(2)}_{j}\textbf{b}^{(2)}_{k}\right) \\ \displaystyle=\sum_{j,k=1}^{d_{1},d_{2}}\left(\sum_{t=1}^{T}\textbf{a}^{(1)}_{jt}\textbf{b}^{(1)}_{tk}\right)\left(\sum_{t=1}^{T}\textbf{a}^{(2)}_{jt}\textbf{b}^{(2)}_{tk}\right) \\ \displaystyle=\sum_{t_{1},t_{2}=1}^{T,T}\left(\sum_{j=1}^{d_{1}}\textbf{a}^{(1)}_{jt_{1}}\textbf{a}^{(2)}_{jt_{2}}\right)\left(\sum_{k=1}^{d_{2}}\textbf{a}^{(1)}_{kt_{1}}\textbf{a}^{(2)}_{kt_{2}}\right) \\ \displaystyle=\sum_{t_{1},t_{2}=1}^{T,T}\left(\textbf{a}^{(1)}_{\cdot,t_{1}}\textbf{a}^{(2)}_{\cdot,t_{2}}\right)\left(\textbf{b}^{(1)}_{\cdot,t_{1}}\textbf{b}^{(2)}_{\cdot,t_{2}}\right) \\ \displaystyle=\left(\left(\textbf{b}^{(1)}\right)\left(\textbf{b}^{(2)}\right)^{\intercal}\right)\odot\left(\left(\textbf{a}^{(1)}\right)^{\intercal}\textbf{a}^{(2)}\right)

2T^{2}<d_{1}d_{2}

2T^{2}<d_{1}d_{2}

Remark 5 (Applications of "Ghost" Technique Beyond Data Attribution) . The techniques developed in this work for efficiently computing gradient dot products may be of independent interest, as this operation arises in various machine learning algorithms and applications beyond data attribution. For instance, the "ghost dot-product" technique can be used in calculating the cosine similarity between individual gradients (together with the "ghost clipping" technique), which is frequently being employed to analyze training dynamics (Fort & Ganguli, 2019) and detect adversarial attacks (Dhaliwal & Shintre, 2018). Additionally, gradient similarity is used in active learning to select the most informative data points for labeling (Ash et al., 2019) and in multitask learning to balance the contributions of different tasks (Yu et al., 2020).

注记 5 （「Ghost」技术在数据归因之外的应用）。 本文为高效计算梯度点积发展的技术或有独立兴趣，因该运算出现在数据归因之外的多种机器学习算法与应用中。例如，「ghost 点积」可与「ghost clipping」一道用于计算个体梯度间的余弦相似度，常被用来分析训练动态（Fort & Ganguli, 2019）与检测对抗攻击（Dhaliwal & Shintre, 2018）。此外，梯度相似度用于主动学习以选择最有信息量的标注点（Ash 等, 2019），以及多任务学习中平衡不同任务贡献（Yu 等, 2020）。

D.2 Ghost Gradient-Hessian-Gradient Product

L

L

\displaystyle\nabla\ell^{(1)}\textbf{H}^{(z^{(\mathrm{val})})}\nabla\ell^{(2)} \\ \displaystyle=\sum_{i,j=1}^{L,L}\frac{\partial\ell^{(1)}}{\partial\textbf{W}_{i}}\left(\frac{\partial^{(2)}\ell^{(z^{(\mathrm{val})})}}{\partial\textbf{W}_{i}\partial\textbf{W}_{j}}\right)\frac{\partial\ell^{(2)}}{\partial\textbf{W}_{j}} \\ \displaystyle=\sum_{i,j=1}^{L,L}(\textbf{a}^{(1)}_{i}\otimes\textbf{b}^{(1)}_{i})\left(\frac{\partial^{(2)}\ell^{(z^{(\mathrm{val})})}}{\partial\textbf{W}_{i}\partial\textbf{W}_{j}}\right)(\textbf{a}^{(2)}_{j}\otimes\textbf{b}^{(2)}_{j})

We first look at the Hessian-vector product.

我们先看 Hessian-向量积。

\displaystyle\left(\frac{\partial^{(2)}\ell^{(z^{(\mathrm{val})})}}{\partial\textbf{W}_{i}\partial\textbf{W}_{j}}\right)(\textbf{a}^{(2)}_{j}\otimes\textbf{b}^{(2)}_{j}) \\ \displaystyle=\frac{\partial}{\partial\textbf{W}_{i}}\left[\frac{\partial\ell^{(z^{(\mathrm{val})})}}{\partial\textbf{W}_{j}}(\textbf{a}^{(2)}_{j}\otimes\textbf{b}^{(2)}_{j})\right] \\ \displaystyle=\frac{\partial}{\partial\textbf{W}_{i}}\left[(\textbf{a}^{(z^{(\mathrm{val})})}_{j}\otimes\textbf{b}^{(z^{(\mathrm{val})})}_{j})(\textbf{a}^{(2)}_{j}\otimes\textbf{b}^{(2)}_{j})\right] \\ \displaystyle=\frac{\partial}{\partial\textbf{W}_{i}}\left[(\textbf{a}^{(z^{(\mathrm{val})})}_{j}\textbf{a}^{(2)}_{j})(\textbf{b}^{(z^{(\mathrm{val})})}_{j}\textbf{b}^{(2)}_{j})\right] \\ \displaystyle=\frac{\partial}{\partial\textbf{W}_{i}}\left[\textbf{c}_{j}\textbf{d}_{j}\right] \\ \displaystyle=\textbf{c}_{j}\frac{\partial\textbf{d}_{j}}{\partial\textbf{W}_{i}}+\textbf{d}_{j}\frac{\partial\textbf{c}_{j}}{\partial\textbf{W}_{i}}

\textbf{c}_{j}:=\textbf{a}^{(z^{(\mathrm{val})})}_{j}\textbf{a}^{(2)}_{j}

\textbf{c}_{j}:=\textbf{a}^{(z^{(\mathrm{val})})}_{j}\textbf{a}^{(2)}_{j}

\nabla\ell^{(z^{(\mathrm{val})})}\nabla\ell^{(2)}=\sum_{j=1}^{L}\textbf{c}_{j}\textbf{d}_{j}

\nabla\ell^{(z^{(\mathrm{val})})}\nabla\ell^{(2)}=\sum_{j=1}^{L}\textbf{c}_{j}\textbf{d}_{j}

\displaystyle\frac{\partial\textbf{c}_{j}}{\partial\textbf{W}_{i}} \\ \displaystyle=\frac{\partial}{\partial\textbf{W}_{i}}\left(\textbf{a}^{(z^{(\mathrm{val})})}_{j}\textbf{a}^{(2)}_{j}\right) \\ \displaystyle=\frac{\partial}{\partial\textbf{s}^{(z^{(\mathrm{val})})}_{i}}\left(\textbf{a}^{(z^{(\mathrm{val})})}_{j}\textbf{a}^{(2)}_{j}\right)\otimes\textbf{a}^{(z^{(\mathrm{val})})}_{i}

\frac{\partial\textbf{d}_{j}}{\partial\textbf{W}_{i}}

\frac{\partial\textbf{d}_{j}}{\partial\textbf{W}_{i}}

\displaystyle\frac{\partial\textbf{d}_{j}}{\partial\textbf{W}_{i}}=\frac{\partial}{\partial\textbf{s}^{(z^{(\mathrm{val})})}_{i}}\left(\textbf{b}^{(z^{(\mathrm{val})})}_{j}\textbf{b}^{(2)}_{j}\right)\otimes\textbf{a}^{(z^{(\mathrm{val})})}_{i}

j<i

j<i

\displaystyle\frac{\partial\textbf{d}_{j}}{\partial\textbf{W}_{i}} \\ \displaystyle=\frac{\partial\textbf{b}^{(z^{(\mathrm{val})})}_{j}\textbf{b}^{(2)}_{j}}{\partial\textbf{W}_{i}} \\ \displaystyle=\frac{\partial}{\partial\textbf{W}_{i}}\left(\textbf{b}^{(z^{(\mathrm{val})})}_{j}\textbf{b}^{(2)}_{j}\right) \\ \displaystyle=\frac{\partial}{\partial\textbf{W}_{i}}\left(\frac{\partial\ell^{(z^{(\mathrm{val})})}}{\partial\textbf{s}^{(z^{(\mathrm{val})})}_{i}}\frac{\partial\textbf{s}^{(z^{(\mathrm{val})})}_{i}}{\partial\textbf{a}^{(z^{(\mathrm{val})})}_{i}}\frac{\partial\textbf{a}^{(z^{(\mathrm{val})})}_{i}}{\partial\textbf{s}^{(z^{(\mathrm{val})})}_{i-1}}\ldots\frac{\partial\textbf{a}^{(z^{(\mathrm{val})})}_{j}}{\partial\textbf{s}^{(z^{(\mathrm{val})})}_{j}}\textbf{b}^{(2)}_{j}\right) \\ \displaystyle=\frac{\partial}{\partial\textbf{W}_{i}}\left(\frac{\partial\ell^{(z^{(\mathrm{val})})}}{\partial\textbf{s}^{(z^{(\mathrm{val})})}_{i}}\textbf{W}_{i}\frac{\partial\textbf{a}^{(z^{(\mathrm{val})})}_{i}}{\partial\textbf{s}^{(z^{(\mathrm{val})})}_{i-1}}\ldots\frac{\partial\textbf{a}^{(z^{(\mathrm{val})})}_{j}}{\partial\textbf{s}^{(z^{(\mathrm{val})})}_{j}}\textbf{b}^{(2)}_{j}\right) \\ \displaystyle=\frac{\partial}{\partial\textbf{s}^{(z^{(\mathrm{val})})}_{i}}\left(\frac{\partial\ell^{(z^{(\mathrm{val})})}}{\partial\textbf{s}^{(z^{(\mathrm{val})})}_{i}}\textbf{W}_{i}\frac{\partial\textbf{a}^{(z^{(\mathrm{val})})}_{i}}{\partial\textbf{s}^{(z^{(\mathrm{val})})}_{i-1}}\ldots\frac{\partial\textbf{a}^{(z^{(\mathrm{val})})}_{j}}{\partial\textbf{s}^{(z^{(\mathrm{val})})}_{j}}\textbf{b}^{(2)}_{j}\right)\otimes\textbf{a}^{(z^{(\mathrm{val})})}_{i} \\ \displaystyle~~+\frac{\partial\ell^{(z^{(\mathrm{val})})}}{\partial\textbf{s}^{(z^{(\mathrm{val})})}_{i}}\otimes\left(\frac{\partial\textbf{a}^{(z^{(\mathrm{val})})}_{i}}{\partial\textbf{s}^{(z^{(\mathrm{val})})}_{i-1}}\ldots\frac{\partial\textbf{a}^{(z^{(\mathrm{val})})}_{j}}{\partial\textbf{s}^{(z^{(\mathrm{val})})}_{j}}\textbf{b}^{(2)}_{j}\right) \\ \displaystyle=\frac{\partial}{\partial\textbf{s}^{(z^{(\mathrm{val})})}_{i}}(\textbf{b}^{(z^{(\mathrm{val})})}_{j}\textbf{b}^{(2)}_{j})\otimes\textbf{a}^{(z^{(\mathrm{val})})}_{i}+\textbf{b}^{(z^{(\mathrm{val})})}_{i}\otimes\left(\frac{\partial\textbf{a}^{(z^{(\mathrm{val})})}_{i}}{\partial\textbf{s}^{(z^{(\mathrm{val})})}_{j}}\textbf{b}^{(2)}_{j}\right)

Overall,

总体地，

\displaystyle\frac{\partial\textbf{d}{j}}{\partial\textbf{W}{i}} \ \displaystyle=\frac{\partial}{\partial\textbf{W}{i}}(\textbf{b}^{(z^{(\mathrm{val})})}{j}\textbf{b}^{(2)}{j}) \ \displaystyle=\begin{cases}\frac{\partial}{\partial\textbf{s}^{(z^{(\mathrm{val})})}{i}}\left(\textbf{b}^{(z^{(\mathrm{val})})}{j}\textbf{b}^{(2)}{j}\right)\otimes\textbf{a}^{(z^{(\mathrm{val})})}{i}&j\geq i\\frac{\partial}{\partial\textbf{s}^{(z^{(\mathrm{val})})}{i}}\left(\textbf{b}^{(z^{(\mathrm{val})})}{j}\textbf{b}^{(2)}{j}\right)\otimes\textbf{a}^{(z^{(\mathrm{val})})}{i}+\textbf{b}^{(z^{(\mathrm{val})})}{i}\otimes\left(\frac{\partial\textbf{a}^{(z^{(\mathrm{val})})}{i}}{\partial\textbf{s}^{(z^{(\mathrm{val})})}{j}}\textbf{b}^{(2)}_{j}\right)&j<i\\end{cases}

Hence, we have

因此有

\displaystyle\nabla\ell^{(1)}\textbf{H}^{(z^{(\mathrm{val})})}\nabla\ell^{(2)} \ \displaystyle=\sum_{i,j=1}^{L,L}(\textbf{a}^{(1)}{i}\otimes\textbf{b}^{(1)}{i})\left[\textbf{c}{j}\frac{\partial\textbf{d}{j}}{\partial\textbf{W}{i}}+\textbf{d}{j}\frac{\partial\textbf{c}{j}}{\partial\textbf{W}{i}}\right] \ \displaystyle=\underbrace{\sum_{i,j=1}^{L,L}(\textbf{a}^{(1)}{i}\otimes\textbf{b}^{(1)}{i})\left(\frac{\partial}{\partial\textbf{s}^{(z^{(\mathrm{val})})}{i}}\left(\textbf{c}{j}\textbf{d}{j}\right)\otimes\textbf{a}^{(z^{(\mathrm{val})})}{i}\right)}{\hbox to9.22pt{\vbox to9.22pt{\pgfpicture\makeatletter\hbox{\hskip 4.60942pt\lower-4.60942pt\hbox to0.0pt{\lxSVG@begingroup@{scopebegin=1} \lxSVG@begingroup@{stroke=#000000} \lxSVG@begingroup@{fill=#000000} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width=0.4pt} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{scopebegin=1} {{{}}\lx@inpgf@ignorespaces\hbox{\hbox{{\lxSVG@begingroup@{scopebegin=1} {{}{{{}}}{{}}{}{}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{}{}{}{}{}{{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 6.1 0 C 6.1 3.37 3.37 6.1 0 6.1 C -3.37 6.1 -6.1 3.37 -6.1 0 C -6.1 -3.37 -3.37 -6.1 0 -6.1 C 3.37 -6.1 6.1 -3.37 6.1 0 Z M 0 0}{fill:none} \lx@inpgf@ignorespaces}{{{{\lx@inpgf@ignorespaces}}\lxSVG@begingroup@{scopebegin=1} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{-1.99306pt}{-2.25555pt}\lxSVG@begingroup@{transform=matrix(1.0 0.0 0.0 1.0 -2.76 -3.12)} \pgfsys@hbox{63}\lxSVG@closescope }}}\lxSVG@closescope }}}}\lxSVG@closescope {{{}}}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}}+\underbrace{\sum{i>j}^{L,L}(\textbf{a}^{(1)}{i}\otimes\textbf{b}^{(1)}{i})\left(\textbf{b}^{(z^{(\mathrm{val})})}{i}\otimes\left(\frac{\partial\textbf{a}^{(z^{(\mathrm{val})})}{i}}{\partial\textbf{s}^{(z^{(\mathrm{val})})}{j}}\textbf{b}^{(2)}{j}\right)\right)}_{\hbox to9.22pt{\vbox to9.22pt{\pgfpicture\makeatletter\hbox{\hskip 4.60942pt\lower-4.60942pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin=1} \lxSVG@begingroup@{stroke=#000000} \lxSVG@begingroup@{fill=#000000} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width=0.4pt} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin=1} {{{}}\lx@inpgf@ignorespaces\hbox{\hbox{{\lxSVG@begingroup@{_scopebegin=1} {{}{{{}}}{{}}{}{}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{}{}{}{}{}{{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 6.1 0 C 6.1 3.37 3.37 6.1 0 6.1 C -3.37 6.1 -6.1 3.37 -6.1 0 C -6.1 -3.37 -3.37 -6.1 0 -6.1 C 3.37 -6.1 6.1 -3.37 6.1 0 Z M 0 0}{fill:none} \lx@inpgf@ignorespaces}{{{{\lx@inpgf@ignorespaces}}\lxSVG@begingroup@{_scopebegin=1} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{-1.99306pt}{-2.25555pt}\lxSVG@begingroup@{transform=matrix(1.0 0.0 0.0 1.0 -2.76 -3.12)} \pgfsys@hbox{63}\lxSVG@closescope }}}\lxSVG@closescope }}}}\lxSVG@closescope {{{}}}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}}

For the first part, we have

对第一部分，有

\displaystyle=\sum_{i=1}^{L}(\textbf{a}^{(1)}_{i}\otimes\textbf{b}^{(1)}_{i})\left(\frac{\partial}{\partial\textbf{s}^{(z^{(\mathrm{val})})}_{i}}\left(\sum_{j=1}^{L}\textbf{c}_{j}\textbf{d}_{j}\right)\otimes\textbf{a}^{(z^{(\mathrm{val})})}_{i}\right) \\ \displaystyle=\sum_{i=1}^{L}\left(\textbf{a}^{(1)}_{i}\textbf{a}^{(z^{(\mathrm{val})})}_{i}\right)\left(\textbf{b}^{(1)}_{i}\left(\frac{\partial}{\partial\textbf{s}^{(z^{(\mathrm{val})})}_{i}}\left(\sum_{j=1}^{L}\textbf{c}_{j}\textbf{d}_{j}\right)\right)\right)

\frac{\partial}{\partial\textbf{s}^{(z^{(\mathrm{val})})}_{i}}\left(\sum_{j=1}^{L}\textbf{c}_{j}\textbf{d}_{j}\right)

\frac{\partial}{\partial\textbf{s}^{(z^{(\mathrm{val})})}_{i}}\left(\sum_{j=1}^{L}\textbf{c}_{j}\textbf{d}_{j}\right)

For the second part, we have

对第二部分，有

\displaystyle=\sum_{i>j}^{L,L}(\textbf{a}^{(1)}_{i}\otimes\textbf{b}^{(1)}_{i})\left(\textbf{b}^{(z^{(\mathrm{val})})}_{i}\otimes\left(\frac{\partial\textbf{a}^{(z^{(\mathrm{val})})}_{i}}{\partial\textbf{s}^{(z^{(\mathrm{val})})}_{j}}\textbf{b}^{(2)}_{j}\right)\right) \\ \displaystyle=\sum_{i>j}^{L,L}\left(\textbf{a}^{(1)}_{i}\left(\frac{\partial\textbf{a}^{(z^{(\mathrm{val})})}_{i}}{\partial\textbf{s}^{(z^{(\mathrm{val})})}_{j}}\textbf{b}^{(2)}_{j}\right)\right)\left(\textbf{b}^{(1)}_{i}\textbf{b}^{(z^{(\mathrm{val})})}_{i}\right)

f(i,j):=\textbf{a}^{(1)}_{i}\frac{\partial\textbf{a}^{(z^{(\mathrm{val})})}_{i}}{\partial\textbf{s}^{(z^{(\mathrm{val})})}_{j}}\textbf{b}^{(2)}_{j}

f(i,j):=\textbf{a}^{(1)}_{i}\frac{\partial\textbf{a}^{(z^{(\mathrm{val})})}_{i}}{\partial\textbf{s}^{(z^{(\mathrm{val})})}_{j}}\textbf{b}^{(2)}_{j}

\displaystyle\textbf{a}^{(1)}_{i}\frac{\partial\textbf{a}^{(z^{(\mathrm{val})})}_{i}}{\partial\textbf{s}^{(z^{(\mathrm{val})})}_{j}}\textbf{b}^{(2)}_{j} \\ \displaystyle=\textbf{a}^{(1)}_{i}\frac{\partial\textbf{a}^{(z^{(\mathrm{val})})}_{i}}{\partial\textbf{s}^{(z^{(\mathrm{val})})}_{i-1}}\frac{\partial\textbf{s}^{(z^{(\mathrm{val})})}_{i-1}}{\partial\textbf{a}^{(z^{(\mathrm{val})})}_{i-1}}\ldots\frac{\partial\textbf{s}^{(z^{(\mathrm{val})})}_{j+1}}{\partial\textbf{a}^{(z^{(\mathrm{val})})}_{j+1}}\frac{\partial\textbf{a}^{(z^{(\mathrm{val})})}_{j+1}}{\partial\textbf{s}^{(z^{(\mathrm{val})})}_{j}}\textbf{b}^{(2)}_{j} \\ \displaystyle=\textbf{a}^{(1)}_{i}\frac{\partial\textbf{a}^{(z^{(\mathrm{val})})}_{i}}{\partial\textbf{s}^{(z^{(\mathrm{val})})}_{i-1}}\textbf{W}_{i-1}\ldots\textbf{W}_{j+1}\frac{\partial\textbf{a}^{(z^{(\mathrm{val})})}_{j+1}}{\partial\textbf{s}^{(z^{(\mathrm{val})})}_{j}}\textbf{b}^{(2)}_{j}

\frac{\partial\textbf{a}^{(z^{(\mathrm{val})})}_{j+1}}{\partial\textbf{s}^{(z^{(\mathrm{val})})}_{j}}

\frac{\partial\textbf{a}^{(z^{(\mathrm{val})})}_{j+1}}{\partial\textbf{s}^{(z^{(\mathrm{val})})}_{j}}

f(i,j)

i>j

\mathbf{g}(i,j):=\frac{\partial\textbf{a}^{(z^{(\mathrm{val})})}_{i}}{\partial\textbf{s}^{(z^{(\mathrm{val})})}_{i-1}}\textbf{W}_{i-1}\ldots\textbf{W}_{j+1}\frac{\partial\textbf{a}^{(z^{(\mathrm{val})})}_{j+1}}{\partial\textbf{s}^{(z^{(\mathrm{val})})}_{j}}\textbf{b}^{(2)}_{j}

f(i,j)=\textbf{a}^{(1)}_{i}\mathbf{g}(i,j)

f(i,j)=\textbf{a}^{(1)}_{i}\mathbf{g}(i,j)

\displaystyle\nabla\ell^{(1)}\textbf{H}^{(z^{(\mathrm{val})})}\left(\sum_{m=1}^{B}\nabla\ell^{(m)}\right)

\textbf{H}^{(z^{(\mathrm{val})})}\left(\sum_{m=1}^{B}\nabla\ell^{(m)}\right)

\textbf{H}^{(z^{(\mathrm{val})})}\left(\sum_{m=1}^{B}\nabla\ell^{(m)}\right)

D.3 Merging Batch Selection and Gradient Update in One Backpropagation

z_{i}\in\mathcal{B}_{t}

z_{i}\in\mathcal{B}_{t}

Appendix E Evaluation

E.1 Data Preprocessing & Training Settings & Implementation Details

We conduct the pretraining experiment using the GPT2 (124M) model (Radford et al., 2019) and Pythia-410M (Biderman et al., 2023) on the Pile dataset. Our codebase is adapted from https://github.com/karpathy/nanoGPT/tree/master . We first tokenize and split the entire dataset into chunks, and store them in the disk in numpy array format, which significantly speeds up data loading. The maximum sequence length is set to 1024. The learning rate is set at a maximum of 0.0006, with a minimum learning rate of 0.00006. We use AdamW as the optimizer with a weight decay of 0.1, and beta values set to 0.9 and 0.95. Gradients are clipped at a maximum value of 1.0 to maintain stability during training. The batch size is set to 16, with a learning rate warmup of 2000 iterations. Due to the shortage of computation resources, we stop the training at 500,000 iterations.

我们在 Pile 上用 GPT2（124M）（Radford 等, 2019）与 Pythia-410M（Biderman 等, 2023）做预训练实验。代码库改编自 https://github.com/karpathy/nanoGPT/tree/master。先把整集分词并切成块，以 numpy 数组存盘，显著加速数据加载。最大序列长度 1024；最大学习率 0.0006，最小 0.00006；优化器用 AdamW，权重衰减 0.1，beta 为 0.9 与 0.95；梯度裁剪最大 1.0 以保持稳定；批大小 16，学习率预热 2000 步。因算力不足，训练在 500,000 步停止。

k_{1}=1.5,b=0.75

k_{1}=1.5,b=0.75

Remark 6 . We do not compare with TRAK (Park et al., 2023) as it generally requires aggregating the estimator across multiple trained models for a reasonable performance, and the original codebase is not applicable to Huggingface models. In their original paper, the largest scale experiment is fine-tuning BERT-base.

注记 6 。 我们不与 TRAK（Park 等, 2023）比较：它通常需跨多个已训模型聚合估计器才有合理表现，且原代码库不适配 Huggingface 模型。原论文最大规模实验是微调 BERT-base。

E.2 Additional Fidelity Evaluation

6\times 10^{-4}

6\times 10^{-4}

=6\times 10^{-4}

=6\times 10^{-4}

=5\times 10^{-3}

=5\times 10^{-3}

U^{(t)}

U^{(t)}

U^{(t)}(S;z^{(\mathrm{val})}):=\ell(\widetilde{w}_{t+1}(S),z^{(\mathrm{val})})-\ell(w_{t},z^{(\mathrm{val})})

U^{(t)}(S;z^{(\mathrm{val})}):=\ell(\widetilde{w}_{t+1}(S),z^{(\mathrm{val})})-\ell(w_{t},z^{(\mathrm{val})})

Remark 7 (Difficulty in Extending to Adam) . The techniques developed in this section are specifically tailored for SGD. It is not directly extendable to other popular optimizers like Adam due to their normalization terms. Nonetheless, using SGD as a proxy for Adam allows for efficient data attribution, which is the approach we adopted in practice and has proved to be effective in our experiment. This provides a practical and effective solution for the current scope of our work. Extending these techniques to support Adam and similar optimizers remains an exciting direction for future research.

注记 7 （扩展到 Adam 的困难）。 本节技术专为 SGD 定制，因归一化项而不能直接扩到 Adam 等流行优化器。不过用 SGD 作 Adam 的代理仍可高效做数据归因——这是我们实践中采用的做法，并在实验中证明有效，为当前工作范围提供了务实方案。扩展到 Adam 及类似优化器仍是有吸引力的未来方向。

E.3 Details about Section 5.3.1

In this experiment, we first conduct one training run for 20,000 iterations. Among all the corpus that has been used in the training, we compute their In-Run Data Shapley and filter out all corpus among this subset that has negative contributions to model training. After filtering out the 16% negative valued corpus, we train another model on the remaining dataset for 10,000 iterations with all hyperparameters staying the same.

本实验先做一次 20,000 步训练；在用过的全部语料上计算 In-Run Data Shapley，并滤掉对该子集训练有负贡献的语料。去掉 16% 负值语料后，在剩余数据上以相同超参再训 10,000 步。

Despite the Pile dataset undergoing multiple layers of data curation (Gao et al., 2020), we still find a significant amount of poor-quality corpus through In-Run Data Shapley. For example, we discovered a large amount of corpora in the PubMed Central domain that are simply empty spaces. Figure 9 provides two examples of the corpus that received the lowest In-Run Data Shapley scores. Additionally, we found several corpora with negative values that appear normal, which is likely due to a distribution shift with the validation corpus. Crafting a representative validation set is an important direction for future work.

尽管 Pile 已经过多层数据策展（Gao 等, 2020），我们仍通过 In-Run Data Shapley 发现大量劣质语料。例如 PubMed Central 领域中有大量几乎全是空格的语料。图 9 给出 In-Run Data Shapley 分数最低的两个语料示例。另有若干负值语料看起来正常，很可能因与验证语料存在分布偏移。如何构造有代表性的验证集是重要未来方向。

Corpus with meaningless numbers,2,3,3,1,3,0,3,0,2,0,0, 0,0,0,0,0,0,0,0,0,0,2,0\dots 3,3,3,3,3,3,3,3,1,3,3,\dots 0,0,0,0,0,0,0,0,0,0,2,\dots 3,3,3,3,3,3,3,3,3,0,3,\dots 1,0,0,0,0,0,0,0,0,0,2,\dots 3,3,3,3,3,3,3,2,3,3,1,\dots 0,0,0,0,0,0,0,0,0,0,3,\dots 3,3,3,3,3,1,3,3,3,3,3,\dots 0,0,0,0,0,0,0,0,0,0,1,\dots Figure 9: Examples of low-quality corpus in Pile found by In-Run Data Shapley. Left: a corpus with meaningless numbers. Right: a corpus with meaningless symbols (likely due to errors from web crawling.)

无意义数字的语料,2,3,3,1,3,0,3,0,2,0,0, 0,0,0,0,0,0,0,0,0,0,2,0\dots 3,3,3,3,3,3,3,3,1,3,3,\dots 0,0,0,0,0,0,0,0,0,0,2,\dots 3,3,3,3,3,3,3,3,3,0,3,\dots 1,0,0,0,0,0,0,0,0,0,2,\dots 3,3,3,3,3,3,3,2,3,3,1,\dots 0,0,0,0,0,0,0,0,0,0,3,\dots 3,3,3,3,3,1,3,3,3,3,3,\dots 0,0,0,0,0,0,0,0,0,0,1,\dots 图 9：In-Run Data Shapley 在 Pile 中发现的低质语料示例。左：无意义数字语料。右：无意义符号语料（很可能来自网页抓取错误）。

E.3.1 Data selection performance on Pythia 410M Figure 10 shows a performance comparison between the original training run and the model trained on the cleaned subsets on Pythia-410M. Similar to the results on GPT2, we can see that removing lower-quality data leads to a significantly faster drop in test loss compared to the original training run, highlighting the effectiveness of In-Run Data Shapley across different architectures.

E.3.1 Pythia 410M 上的数据选择表现 图 10 比较 Pythia-410M 上原训练与清洗子集训练的表现。与 GPT2 类似，去掉较低质量数据后测试损失下降显著更快，凸显 In-Run Data Shapley 跨不同架构的有效性。

Figure 10: Test loss comparison between the original training run and model trained on the cleaned subset according to different data attribution techniques for Pythia-410M.

图 10：Pythia-410M 上原训练与按不同数据归因技术清洗子集后训练的测试损失比较。

E.4 Additional Results for Section 5.3.2

In addition to Figure 3, we also plot the average value scores of corpora from each domain, averaged across all corpora within the same domain that has been used in gradient updates, over the first 10,000 gradient update iterations. As training progresses, the magnitude of data value scores converges towards zero, which aligns with the diminishing returns property of neural network training. This indicates that the contribution of data points depends on the order in which they are used during training, an aspect that Retraining-based Data Shapley methods cannot capture. Data points introduced in later stages of training contribute less to model performance improvement.

除图 3 外，我们还绘制各领域语料的平均价值分数——对前 10,000 次梯度更新中用过的同领域语料取平均。随训练推进，数据价值分数的幅度趋向零，符合神经网络训练的收益递减。这表明数据点贡献取决于使用顺序——基于重训的 Data Shapley 无法捕捉这一点。训练后期引入的数据点对性能提升贡献更小。

Figure 11: The change of average contribution for data points from each domain to a corpus of math text (same setting as Figure 3).

图 11：各领域数据点对某数学文本语料平均贡献的变化（设定同图 3）。

E.5 Details about Section 5.3.3

In Section 5.3.3, we use GPT-4 to generate varying levels of paraphrased versions of an original corpus from the training set, categorized as "Partial exactly the same," "Paraphrase," "Significant paraphrase," and "Similar topic." For "Partial exactly the same," the corpus is used as the answer in a creative writing instruction-answer pair. The specific prompt for prompting GPT-4 with examples of the full dialogue are shown in Figure 13, 14, 15. We generate 3 sets of corpus groups, and the experiment results are taken as the average. Figure 12 shows the distribution of calculated In-Run Data Shapley. As we can see, most corpora’s values are around 0, but certain corpora have significantly higher values than the other, which means their contributions are higher for the target validation corpus.

第 5.3.3 节中，我们用 GPT-4 对训练集中原始语料生成不同程度的改写，分为「部分完全相同」「改写」「大幅改写」「相似主题」。「部分完全相同」把该语料用作创意写作指令-答案对中的答案。提示 GPT-4 的具体提示与完整对话示例见图 13、14、15。我们生成 3 组语料群，实验结果取平均。图 12 显示算出的 In-Run Data Shapley 分布：多数语料价值约在 0 附近，但某些语料价值显著更高，意味着它们对目标验证语料贡献更大。

Figure 12: The distribution of calculated In-Run Data Shapley values.

图 12：算出的 In-Run Data Shapley 值分布。

\blacktriangleright

\blacktriangleright

\blacktriangleright

\blacktriangleright

\blacktriangleright

\blacktriangleright

E.5.1 Additional Experiment: Relevant Domain Detection In this additional experiment, we evaluate the effectiveness of different data attribution techniques in identifying relevant domain-specific corpora within the Pile dataset. Specifically, we take a random batch of the validation corpus from sub-domains of the Pile dataset and evaluate the normalized recall@1000 scores . This metric measures the proportion of same-domain corpora as the validation corpora among the 1000 highest-valued corpora, normalized by the global proportion of this domain within the Pile dataset. As shown in Table 3, BM25 performs well on this task in general. Both the first-order and second-order In-Run Data Shapley methods outperform the influence function in detecting relevant domain corpora. Analysis: The influence function only uses information from the final trained models, which can result in highly noisy value scores since the removal of one training data point might have a negligible effect on the final model performance. In contrast, In-Run Data Shapley effectively leverages information from all intermediate checkpoints during model training, providing a more comprehensive and accurate assessment of each data point’s value. While BM25 performs well on most of the domains, there are still cases where In-Run Data Shapley achieves better detection rate, which implies that gradient information may be more useful in determining semantic similarity to some extent.

E.5.1 补充实验：相关领域检测 本补充实验评估不同数据归因技术在 Pile 中识别相关领域语料的效果。具体地，从 Pile 各子域随机取一批验证语料，评估 归一化 recall@1000 ：在价值最高的 1000 条语料中，与验证语料同域的比例，再除以该域在 Pile 中的全局比例。如表 3，BM25 整体表现不错；一、二阶 In-Run Data Shapley 在检测相关领域语料上均优于影响函数。 分析 ： 影响函数只用最终已训模型信息，去掉单点对最终表现影响可能微乎其微，价值分数噪声很大；In-Run Data Shapley 有效利用训练全程中间检查点信息，对每点价值评估更全面准确。虽 BM25 在多数领域表现好，仍有 In-Run Data Shapley 检测率更高的情形，暗示梯度信息在一定程度上对判定语义相似度更有用。

Github EuroParl ArXiv PhilPapers FreeLaw HackerNews StackExchange Wikipedia (en) In-Run Data Shapley (1st order) 30.5 12.7 48.4 0.6 14.6 2.7 16.3 14.5 In-Run Data Shapley (2nd order) 29 14.8 50 0.4 16.9 3.8 20 18.9 Influence Function 17.9 4.1 41.7 0.5 5.7 2.6 6.5 5.5 BM25 18.8 6.3 44.8 1.1 72.6 9.9 37.2 18.6 PubMed Abstracts USPTO Backgrounds PubMed Central Enron Emails NIH ExPorter DM Mathematics Ubuntu IRC Gutenberg (PG-19) In-Run Data Shapley (1st order) 10.4 10.5 30 0.8 1.7 23.5 10.2 8.7 In-Run Data Shapley (2nd order) 16.6 11.1 31.1 1 1.9 24.5 11.5 15.3 Influence Function 10.2 7.4 26.9 0.2 1.2 10.1 4.3 8.8 BM25 28.6 23 53.7 1 4.1 34.6 12.5 25.9 Table 3: Results of relevant domain corpus detection experiment, where the metric is the normalized recall@1000 (i.e., the proportion of the same domain corpora as the validation corpora among the 1000 corpora with the highest values, normalized by the global proportion of this domain among the Pile dataset).

	Github	EuroParl	ArXiv	PhilPapers	FreeLaw	HackerNews	StackExchange	Wikipedia (en)
In-Run Data Shapley (1st order)	30.5	12.7	48.4	0.6	14.6	2.7	16.3	14.5
In-Run Data Shapley (2nd order)	29	14.8	50	0.4	16.9	3.8	20	18.9
Influence Function	17.9	4.1	41.7	0.5	5.7	2.6	6.5	5.5
BM25	18.8	6.3	44.8	1.1	72.6	9.9	37.2	18.6
	PubMed Abstracts	USPTO Backgrounds	PubMed Central	Enron Emails	NIH ExPorter	DM Mathematics	Ubuntu IRC	Gutenberg (PG-19)
In-Run Data Shapley (1st order)	10.4	10.5	30	0.8	1.7	23.5	10.2	8.7
In-Run Data Shapley (2nd order)	16.6	11.1	31.1	1	1.9	24.5	11.5	15.3
Influence Function	10.2	7.4	26.9	0.2	1.2	10.1	4.3	8.8
BM25	28.6	23	53.7	1	4.1	34.6	12.5	25.9

Github EuroParl ArXiv PhilPapers FreeLaw HackerNews StackExchange Wikipedia (en) In-Run Data Shapley（一阶） 30.5 12.7 48.4 0.6 14.6 2.7 16.3 14.5 In-Run Data Shapley（二阶） 29 14.8 50 0.4 16.9 3.8 20 18.9 影响函数 17.9 4.1 41.7 0.5 5.7 2.6 6.5 5.5 BM25 18.8 6.3 44.8 1.1 72.6 9.9 37.2 18.6 PubMed Abstracts USPTO Backgrounds PubMed Central Enron Emails NIH ExPorter DM Mathematics Ubuntu IRC Gutenberg (PG-19) In-Run Data Shapley（一阶） 10.4 10.5 30 0.8 1.7 23.5 10.2 8.7 In-Run Data Shapley（二阶） 16.6 11.1 31.1 1 1.9 24.5 11.5 15.3 影响函数 10.2 7.4 26.9 0.2 1.2 10.1 4.3 8.8 BM25 28.6 23 53.7 1 4.1 34.6 12.5 25.9 表 3：相关领域语料检测实验结果，指标为归一化 recall@1000（即价值最高的 1000 条中与验证语料同域的比例，再按该域在 Pile 中的全局比例归一化）。

	Github	EuroParl	ArXiv	PhilPapers	FreeLaw	HackerNews	StackExchange	Wikipedia (en)
In-Run Data Shapley（一阶）	30.5	12.7	48.4	0.6	14.6	2.7	16.3	14.5
In-Run Data Shapley（二阶）	29	14.8	50	0.4	16.9	3.8	20	18.9
影响函数	17.9	4.1	41.7	0.5	5.7	2.6	6.5	5.5
BM25	18.8	6.3	44.8	1.1	72.6	9.9	37.2	18.6
	PubMed Abstracts	USPTO Backgrounds	PubMed Central	Enron Emails	NIH ExPorter	DM Mathematics	Ubuntu IRC	Gutenberg (PG-19)
In-Run Data Shapley（一阶）	10.4	10.5	30	0.8	1.7	23.5	10.2	8.7
In-Run Data Shapley（二阶）	16.6	11.1	31.1	1	1.9	24.5	11.5	15.3
影响函数	10.2	7.4	26.9	0.2	1.2	10.1	4.3	8.8
BM25	28.6	23	53.7	1	4.1	34.6	12.5	25.9

Original Wikipedia Corpus In 2012, Radhi recruited new ’musicians’ for OAG, who were selected from among the students of Akademi Seni Budaya dan Warisan Kebangsaan (). The new line-up consists of Qi Razali (drums/backing vocals - original drummer \dots A corpus that is partially same Instruction: Write a short story about Radhi and his band OAG as they recruit new members and blend traditional music with alternative sounds. Describe their creative challenges and successes leading up to their new releases. ### Answer: In 2012, Radhi recruited new ’musicians’ for OAG, who were selected from among the students of Akademi Seni Budaya dan Warisan Kebangsaan (). The new line-up consists of Qi Razali (drums/backing vocals - original drummer \dots

原始 Wikipedia 语料 In 2012, Radhi recruited new 'musicians' for OAG, who were selected from among the students of Akademi Seni Budaya dan Warisan Kebangsaan (). The new line-up consists of Qi Razali (drums/backing vocals - original drummer \dots 部分相同的语料 Instruction: Write a short story about Radhi and his band OAG as they recruit new members and blend traditional music with alternative sounds. Describe their creative challenges and successes leading up to their new releases. ### Answer: In 2012, Radhi recruited new 'musicians' for OAG, who were selected from among the students of Akademi Seni Budaya dan Warisan Kebangsaan (). The new line-up consists of Qi Razali (drums/backing vocals - original drummer \dots

Original Wikipedia Corpus In 2012, Radhi recruited new ’musicians’ for OAG, who were selected from among the students of Akademi Seni Budaya dan Warisan Kebangsaan (). The new line-up consists of Qi Razali (drums/backing vocals - original drummer \dots Synthetic "Similar topic" Corpus Instruction: Write a short story about a classical violinist who decides to explore jazz music, detailing her first encounter with a jazz band. ### Answer: Elena, a classically trained violinist known for her precise and emotive performances \dots

原始 Wikipedia 语料 In 2012, Radhi recruited new 'musicians' for OAG, who were selected from among the students of Akademi Seni Budaya dan Warisan Kebangsaan (). The new line-up consists of Qi Razali (drums/backing vocals - original drummer \dots 合成「相似主题」语料 Instruction: Write a short story about a classical violinist who decides to explore jazz music, detailing her first encounter with a jazz band. ### Answer: Elena, a classically trained violinist known for her precise and emotive performances \dots

E.6 Comparison with other data attribution baselines on small-scale models

In this section, we evaluate In-Run Data Shapley using standard benchmarks for data attribution techniques, including mislabeled data detection and data selection. While data attribution scores can generally indicate data quality, they are not specifically optimized for these benchmarks. Furthermore, approximating the Shapley value has intrinsic merit beyond these standard tasks (e.g., for royalty sharing of AI-generated contents (Wang et al., 2024a)). As such, this evaluation primarily serves as a sanity check to confirm that In-Run Data Shapley can reasonably reflect data values. However, state-of-the-art performance is not expected since the method is not designed specifically for these tasks.

本节用数据归因技术的标准基准——包括错标检测与数据选择——评估 In-Run Data Shapley。虽归因分数一般可指示数据质量，但并非专为这些基准优化；且逼近 Shapley 值本身在这些标准任务之外也有内在价值（例如 AI 生成内容的版税分成（Wang 等, 2024a））。因此本评估主要作为 健全性检查 ，确认 In-Run Data Shapley 能合理反映数据价值；因方法并非专为这些任务设计，不期望达到最先进表现。

We compare In-Run Data Shapley with several data attribution baselines, including Retraining-based Data Shapley (Ghorbani & Zou, 2019), KNN-Shapley (Jia et al., 2019a), influence function (Koh & Liang, 2017), Trak (Park et al., 2023), Empirical Influence Functions (Feldman & Zhang, 2020), and Datamodels (Ilyas et al., 2022). We also compare with LESS (Xia et al., 2024), an extension of TracIN-CP tailored for instruction tuning data selection.

我们把 In-Run Data Shapley 与若干数据归因基线比较，包括基于重训的 Data Shapley（Ghorbani & Zou, 2019）、KNN-Shapley（Jia 等, 2019a）、影响函数（Koh & Liang, 2017）、Trak（Park 等, 2023）、经验影响函数（Feldman & Zhang, 2020）与 Datamodels（Ilyas 等, 2022）。也与 LESS（Xia 等, 2024）比较——它是面向指令微调数据选择的 TracIN-CP 扩展。

As some baselines here require multiple model retrainings, we use a subset of 1,000 samples from CIFAR10 and ResNet18 architecture. We evaluate these techniques on two standard tasks for assessing data attribution methods: mislabeled data detection and data selection. We note that recent work (Wang et al., 2024d) questions the suitability of data attribution for data selection, but we include this metric due to its prevalence in existing literature.

因部分基线需多次模型重训，我们使用 CIFAR10 的 1,000 样本子集与 ResNet18 架构。在两个标准任务上评估：错标检测与数据选择。我们注意到近期工作（Wang 等, 2024d）质疑数据归因是否适于数据选择，但因该指标在既有文献中常见，仍予纳入。

T

T

Mislabeled data detection. The results in Table 4 show that KNN-Shapley achieves the highest performance in mislabeled data detection, likely due to its sensitivity to label changes. Retraining-based approaches (Retraining-based Data Shapley, Empirical Influence Functions, Datamodel) have the lowest performance, which can be attributed to Monte Carlo sample inefficiency and stochasticity during retraining, as noted in Wang & Jia (2023a). Among techniques requiring only one training run, Trak does not outperform others, aligning with observations in its original paper (Park et al., 2023) that ensembles are often necessary for high performance. LESS achieves better results by incorporating more information from intermediate checkpoints. In-Run Data Shapley and influence function achieve comparable performance, outperforming all other techniques except KNN-Shapley. The relatively high performance of In-Run Data Shapley is likely due to its deterministic estimation algorithm. Furthermore, it makes use of the information from all intermediate checkpoints.

错标数据检测。 表 4 显示 KNN-Shapley 在错标检测上表现最高，或因其对标签变化敏感。基于重训的方法（基于重训的 Data Shapley、经验影响函数、Datamodel）表现最低，可归因于蒙特卡洛样本效率低与重训随机性，如 Wang & Jia (2023a) 所指出。在只需一次训练的技术中，Trak 未优于其他，与原论文（Park 等, 2023）中常需集成才能高性能的观察一致。LESS 因纳入更多中间检查点信息而更好。In-Run Data Shapley 与影响函数表现相当，优于除 KNN-Shapley 外的所有技术。In-Run Data Shapley 相对较高的表现或因其确定性估计算法，并利用了全部中间检查点信息。

Data selection. Table 5 shows that KNN-Shapley again excels when the selection budget is small. Interestingly, most data attribution techniques perform worse than random baseline for small selection budgets, aligning with observations that selecting data points solely based on attribution scores can harm dataset diversity (Wang et al., 2024d). For larger selection budgets (60%, 80%), single-training-run techniques achieve similar performance levels.

数据选择。 表 5 显示选择预算较小时 KNN-Shapley 再次领先。有趣的是，多数数据归因技术在小预算下差于随机基线，与「仅按归因分数选点会伤害数据集多样性」的观察一致（Wang 等, 2024d）。在更大选择预算（60%、80%）下，单次训练技术达到相近表现水平。

Retraining-based Data Shapley (Ghorbani & Zou, 2019) Empirical Influence Function (Feldman & Zhang, 2020) Datamodels (Ilyas et al., 2022) 0.582 (0.029) 0.552 (0.017) 0.52 (0.008) KNN-Shapley (Jia et al., 2019a; Wang & Jia, 2023c) Influence function (Koh & Liang, 2017) LESS (Xia et al., 2024) 0.76 (0.018) 0.654 (0.054) 0.55 (0.032) 1st Order In-Run Data Shapley (ours) 2nd Order In-Run Data Shapley (ours) Trak (1 cpt) (Park et al., 2023) 0.678 (0.045) 0.680 (0.048) 0.511 (0.012) Trak (5 cpts) (Park et al., 2023) Trak (15 cpts) (Park et al., 2023) Trak (25 cpts) (Park et al., 2023) 0.542 (0.025) 0.609 (0.028) 0.617 (0.021) Table 4: AUROC scores of mislabeled data detection task with various data attribution techniques on CIFAR10 dataset. The higher the AUROC score is, the better the method is. The results are across three different training runs (the randomness comes from construction of corrupted datasets), where we show the standard deviation in (). Methods with top-3 performance are bolded.

Retraining-based Data Shapley (Ghorbani & Zou, 2019)	Empirical Influence Function (Feldman & Zhang, 2020)	Datamodels (Ilyas et al., 2022)
0.582 (0.029)	0.552 (0.017)	0.52 (0.008)
KNN-Shapley (Jia et al., 2019a; Wang & Jia, 2023c)	Influence function (Koh & Liang, 2017)	LESS (Xia et al., 2024)
0.76 (0.018)	0.654 (0.054)	0.55 (0.032)
1st Order In-Run Data Shapley (ours)	2nd Order In-Run Data Shapley (ours)	Trak (1 cpt) (Park et al., 2023)
0.678 (0.045)	0.680 (0.048)	0.511 (0.012)
Trak (5 cpts) (Park et al., 2023)	Trak (15 cpts) (Park et al., 2023)	Trak (25 cpts) (Park et al., 2023)
0.542 (0.025)	0.609 (0.028)	0.617 (0.021)

基于重训的 Data Shapley （Ghorbani & Zou, 2019） 经验影响函数 （Feldman & Zhang, 2020） Datamodels （Ilyas 等, 2022） 0.582 (0.029) 0.552 (0.017) 0.52 (0.008) KNN-Shapley （Jia 等, 2019a；Wang & Jia, 2023c） 影响函数 （Koh & Liang, 2017） LESS （Xia 等, 2024） 0.76 (0.018) 0.654 (0.054) 0.55 (0.032) 一阶 In-Run Data Shapley（本文） 二阶 In-Run Data Shapley（本文） Trak（1 检查点） （Park 等, 2023） 0.678 (0.045) 0.680 (0.048) 0.511 (0.012) Trak（5 检查点） （Park 等, 2023） Trak（15 检查点） （Park 等, 2023） Trak（25 检查点） （Park 等, 2023） 0.542 (0.025) 0.609 (0.028) 0.617 (0.021) 表 4：CIFAR10 上多种数据归因技术在错标检测任务的 AUROC。AUROC 越高越好。结果跨三次不同训练运行（随机性来自损坏数据集的构造），括号内为标准差。表现前三的方法加粗。

基于重训的 Data Shapley（Ghorbani & Zou, 2019）	经验影响函数（Feldman & Zhang, 2020）	Datamodels（Ilyas 等, 2022）
0.582 (0.029)	0.552 (0.017)	0.52 (0.008)
KNN-Shapley（Jia 等, 2019a；Wang & Jia, 2023c）	影响函数（Koh & Liang, 2017）	LESS（Xia 等, 2024）
0.76 (0.018)	0.654 (0.054)	0.55 (0.032)
一阶 In-Run Data Shapley（本文）	二阶 In-Run Data Shapley（本文）	Trak（1 检查点）（Park 等, 2023）
0.678 (0.045)	0.680 (0.048)	0.511 (0.012)
Trak（5 检查点）（Park 等, 2023）	Trak（15 检查点）（Park 等, 2023）	Trak（25 检查点）（Park 等, 2023）
0.542 (0.025)	0.609 (0.028)	0.617 (0.021)

20% 40% 60% 80% Random 0.350 (0.010) 0.461 (0.010) 0.525 (0.004) 0.559 (0.003) Influence function (Koh & Liang, 2017) 0.320 (0.033) 0.450 (0.028) 0.530 (0.015) 0.580 (0.004) Trak (1 cpt) (Park et al., 2023) 0.329 (0.021) 0.443 (0.030) 0.517 (0.016) 0.572 (0.009) Trak (5 cpts) (Park et al., 2023) 0.325 (0.022) 0.445 (0.031) 0.519 (0.018) 0.572 (0.009) Trak (15 cpts) (Park et al., 2023) 0.327 (0.028) 0.446 (0.035) 0.523 (0.018) 0.573 (0.010) Trak (25 cpts) (Park et al., 2023) 0.332 (0.025) 0.443 (0.035) 0.520 (0.018) 0.578 (0.015) LESS (Xia et al., 2024) 0.314 (0.012) 0.460 (0.015) 0.541 (0.006) 0.582 (0.006) Data Shapley (Ghorbani & Zou, 2019) 0.317 (0.047) 0.468 (0.010) 0.527 (0.004) 0.570 (0.008) Datamodels (Ilyas et al., 2022) 0.342 (0.004) 0.465 (0.004) 0.534 (0.010) 0.559 (0.005) Empirical Influence Function (Feldman & Zhang, 2020) 0.342 (0.004) 0.466 (0.016) 0.530 (0.009) 0.568 (0.010) KNN-Shapley (Jia et al., 2019a) 0.354 (0.017) 0.478 (0.007) 0.525 (0.015) 0.563 (0.005) 1st Order In-Run Data Shapley 0.344 (0.009) 0.472 (0.003) 0.541 (0.006) 0.580 (0.004) 2nd Order In-Run Data Shapley 0.342 (0.010) 0.473 (0.008) 0.544 (0.005) 0.580 (0.004) Table 5: Test accuracies when training ResNet18 on high-value data points selected by various data attribution techniques. To be able to compare with techniques that require model retraining, for each training run we randomly sample a size-1000 subset of CIFAR10 dataset (with 10% data points being mislabeled). The results are across three different training runs (the randomness comes from the construction of corrupted datasets), where we show the standard deviation in (). Methods with top-3 performance are bolded.

	20%	40%	60%	80%
Random	0.350 (0.010)	0.461 (0.010)	0.525 (0.004)	0.559 (0.003)
Influence function (Koh & Liang, 2017)	0.320 (0.033)	0.450 (0.028)	0.530 (0.015)	0.580 (0.004)
Trak (1 cpt) (Park et al., 2023)	0.329 (0.021)	0.443 (0.030)	0.517 (0.016)	0.572 (0.009)
Trak (5 cpts) (Park et al., 2023)	0.325 (0.022)	0.445 (0.031)	0.519 (0.018)	0.572 (0.009)
Trak (15 cpts) (Park et al., 2023)	0.327 (0.028)	0.446 (0.035)	0.523 (0.018)	0.573 (0.010)
Trak (25 cpts) (Park et al., 2023)	0.332 (0.025)	0.443 (0.035)	0.520 (0.018)	0.578 (0.015)
LESS (Xia et al., 2024)	0.314 (0.012)	0.460 (0.015)	0.541 (0.006)	0.582 (0.006)
Data Shapley (Ghorbani & Zou, 2019)	0.317 (0.047)	0.468 (0.010)	0.527 (0.004)	0.570 (0.008)
Datamodels (Ilyas et al., 2022)	0.342 (0.004)	0.465 (0.004)	0.534 (0.010)	0.559 (0.005)
Empirical Influence Function (Feldman & Zhang, 2020)	0.342 (0.004)	0.466 (0.016)	0.530 (0.009)	0.568 (0.010)
KNN-Shapley (Jia et al., 2019a)	0.354 (0.017)	0.478 (0.007)	0.525 (0.015)	0.563 (0.005)
1st Order In-Run Data Shapley	0.344 (0.009)	0.472 (0.003)	0.541 (0.006)	0.580 (0.004)
2nd Order In-Run Data Shapley	0.342 (0.010)	0.473 (0.008)	0.544 (0.005)	0.580 (0.004)

20% 40% 60% 80% 随机 0.350 (0.010) 0.461 (0.010) 0.525 (0.004) 0.559 (0.003) 影响函数 （Koh & Liang, 2017） 0.320 (0.033) 0.450 (0.028) 0.530 (0.015) 0.580 (0.004) Trak（1 检查点） （Park 等, 2023） 0.329 (0.021) 0.443 (0.030) 0.517 (0.016) 0.572 (0.009) Trak（5 检查点） （Park 等, 2023） 0.325 (0.022) 0.445 (0.031) 0.519 (0.018) 0.572 (0.009) Trak（15 检查点） （Park 等, 2023） 0.327 (0.028) 0.446 (0.035) 0.523 (0.018) 0.573 (0.010) Trak（25 检查点） （Park 等, 2023） 0.332 (0.025) 0.443 (0.035) 0.520 (0.018) 0.578 (0.015) LESS （Xia 等, 2024） 0.314 (0.012) 0.460 (0.015) 0.541 (0.006) 0.582 (0.006) Data Shapley （Ghorbani & Zou, 2019） 0.317 (0.047) 0.468 (0.010) 0.527 (0.004) 0.570 (0.008) Datamodels （Ilyas 等, 2022） 0.342 (0.004) 0.465 (0.004) 0.534 (0.010) 0.559 (0.005) 经验影响函数 （Feldman & Zhang, 2020） 0.342 (0.004) 0.466 (0.016) 0.530 (0.009) 0.568 (0.010) KNN-Shapley （Jia 等, 2019a） 0.354 (0.017) 0.478 (0.007) 0.525 (0.015) 0.563 (0.005) 一阶 In-Run Data Shapley 0.344 (0.009) 0.472 (0.003) 0.541 (0.006) 0.580 (0.004) 二阶 In-Run Data Shapley 0.342 (0.010) 0.473 (0.008) 0.544 (0.005) 0.580 (0.004) 表 5：按多种数据归因技术选出的高价值数据点训练 ResNet18 的测试准确率。为与需重训的技术可比，每次训练从 CIFAR10 随机抽大小 1000 的子集（其中 10% 错标）。结果跨三次不同训练运行（随机性来自损坏数据集构造），括号内为标准差。表现前三的方法加粗。

	20%	40%	60%	80%
随机	0.350 (0.010)	0.461 (0.010)	0.525 (0.004)	0.559 (0.003)
影响函数（Koh & Liang, 2017）	0.320 (0.033)	0.450 (0.028)	0.530 (0.015)	0.580 (0.004)
Trak（1 检查点）（Park 等, 2023）	0.329 (0.021)	0.443 (0.030)	0.517 (0.016)	0.572 (0.009)
Trak（5 检查点）（Park 等, 2023）	0.325 (0.022)	0.445 (0.031)	0.519 (0.018)	0.572 (0.009)
Trak（15 检查点）（Park 等, 2023）	0.327 (0.028)	0.446 (0.035)	0.523 (0.018)	0.573 (0.010)
Trak（25 检查点）（Park 等, 2023）	0.332 (0.025)	0.443 (0.035)	0.520 (0.018)	0.578 (0.015)
LESS（Xia 等, 2024）	0.314 (0.012)	0.460 (0.015)	0.541 (0.006)	0.582 (0.006)
Data Shapley（Ghorbani & Zou, 2019）	0.317 (0.047)	0.468 (0.010)	0.527 (0.004)	0.570 (0.008)
Datamodels（Ilyas 等, 2022）	0.342 (0.004)	0.465 (0.004)	0.534 (0.010)	0.559 (0.005)
经验影响函数（Feldman & Zhang, 2020）	0.342 (0.004)	0.466 (0.016)	0.530 (0.009)	0.568 (0.010)
KNN-Shapley（Jia 等, 2019a）	0.354 (0.017)	0.478 (0.007)	0.525 (0.015)	0.563 (0.005)
一阶 In-Run Data Shapley	0.344 (0.009)	0.472 (0.003)	0.541 (0.006)	0.580 (0.004)
二阶 In-Run Data Shapley	0.342 (0.010)	0.473 (0.008)	0.544 (0.005)	0.580 (0.004)

Data Shapley in One Training Run

Abstract

1 Introduction

2 Background of Data Shapley

Definition 1(Shapley value (Shapley, 1953)).

定义 1（Shapley 值（Shapley, 1953））。

Theorem 2(Linearity of the Shapley value (Shapley, 1953)).

定理 2（Shapley 值的线性性（Shapley, 1953））。

3 In-Run Data Shapley

Remark 1(Multiple validation points).

注记 1（多个验证点）。

4 Efficient Computation of In-Run Data Shapley

4.1 Approximating U(t)U^{(t)}U(t) with Taylor Expansion

Theorem 3.

定理 3。

Theorem 4.

定理 4。

4.2 Efficient Computation of Gradient Dot-product and Gradient-Hessian-Gradient Product

Remark 2.

注记 2。

5 Experiments

5.1 Runtime Evaluation

5.2 Fidelity Evaluation

5.3 Case Study: Data Attribution on Pile Dataset

5.3.1 Is Well-curated Dataset Actually Clean?

5.3.1 精心策展的数据集真的干净吗？

5.3.2 How Do Data Values Change during Training?

5.3.2 训练过程中数据价值如何变化？

5.3.3 Does Contribution Require Memorization?

5.3.3 贡献是否要求记忆？

6 Conclusion and Limitations

Acknowledgment

References

Appendix A Extended Related Works

A.1 Data Shapley Axioms

A.2 Data Shapley and Friends

Remark 3.

注记 3。

A.3 Comparison with TracIN (Pruthi et al., 2020)

Appendix B Additional Discussion

B.1 When is In-Run Data Shapley Desirable for Data Attribution?

Remark 4(In-run Data Shapley is a model-specific data attribution technique.).

注记 4（In-Run Data Shapley 是模型特定的数据归因技术。）。

B.2 When is Retraining-based Data Shapley Desirable for Data Attribution?

B.3 Potential Extensions of In-Run Data Shapley to Other Domains

Appendix C Missing Proofs

Theorem 5(Restate of Theorem 3).

定理 5（定理 3 的重述）。

Proof.

证明。

Theorem 6(Restate of Theorem 4).

定理 6（定理 4 的重述）。

Proof.

证明。

Appendix D Technical Details

D.1 Ghost Dot-Product

Remark 5(Applications of "Ghost" Technique Beyond Data Attribution).

注记 5（「Ghost」技术在数据归因之外的应用）。

D.2 Ghost Gradient-Hessian-Gradient Product

D.3 Merging Batch Selection and Gradient Update in One Backpropagation

Appendix E Evaluation

E.1 Data Preprocessing & Training Settings & Implementation Details

Remark 6.

注记 6。

E.2 Additional Fidelity Evaluation

E.2.1 Approximation Error for In-Run Data Shapley with larger learning rates

E.2.1 更大学习率下 In-Run Data Shapley 的逼近误差

E.2.2 Approximation Error for Utility Function

E.2.2 效用函数的逼近误差

Remark 7(Difficulty in Extending to Adam).

注记 7（扩展到 Adam 的困难）。

E.3 Details about Section 5.3.1

E.3.1 Data selection performance on Pythia 410M

E.3.1 Pythia 410M 上的数据选择表现

E.4 Additional Results for Section 5.3.2

E.5 Details about Section 5.3.3

E.5.1 Additional Experiment: Relevant Domain Detection

E.5.1 补充实验：相关领域检测

Instruction: Write a short story about a classical violinist who decides to explore jazz music, detailing her first encounter with a jazz band. ### Answer: Elena, a classically trained violinist known for her precise and emotive performances …

Instruction: Write a short story about a classical violinist who decides to explore jazz music, detailing her first encounter with a jazz band. ### Answer: Elena, a classically trained violinist known for her precise and emotive performances …

4.1 Approximating $U^{(t)}$ with Taylor Expansion