Data attribution · the notes, derived

Data (Attribution) for Alignment, step by step

A derivation-by-derivation companion to Louis Jaburi's Iliad notes

Primary source: iliad-intensive.org/learning/data-attribution (PDF). Slide eyebrows give the section, definition or exercise in the notes.

The route through the notes

One derivative, three readings of "the trained model"

Conventions used on every slide

Summed loss, data weights, upweighting sign

• All derivatives are at $\beta=\mathbf 1$. $\mathcal I=\partial/\partial\beta_i$ is the effect of upweighting; deleting $z_i$ is $\beta_i:1\to0$, so to first order it changes things by $-\mathcal I$.
• SGD in §4 averages over the minibatch: $\frac{\eta_t}{b}\sum_{i\in B_t}$.
• $g_i=\nabla_wL(w^*,z_i)$, $\;g_\phi=\nabla_w\phi(w^*)$.

§1.2 · Definition 1.1

Counterfactual attribution

The simple counterfactual test (after Lewis 1973): $B$ depends on $A$ if, had $A$ not occurred, $B$ would not have occurred. Graded version: attribute $B$ to $A$ iff

1. had $A$ occurred, $B$ would have occurred to a higher degree;
2. had $A$ not occurred, $B$ would have occurred to a lesser degree.

For data, "$A$ not occurring" is deleting $z_i$: the leave-one-out (LOO) counterfactual.

§1.2 · Example 1.2 · Overdetermination

OpenCroissant: two sufficient causes

LOO gives butter and yeast zero credit, though each was a cause.

§1.2 · Example 1.3 · Non-transitivity

Counterfactuals do not chain

• A caused B, and B caused C, counterfactually.
• A did not cause C: with or without the boulder, she is unharmed.
• In training: an example can induce a feature that drives a capability, and still fail the end-to-end LOO test.

§1.3 · Definition 1.4

Shapley value: average the marginal effect over coalitions

Equivalently: order the players at random; $\varphi_i$ is the mean of $v(\text{players before }i\text{, plus }i)-v(\text{players before }i)$.

§1.3 · Shapley on the croissant

Each leavener gets half the credit

§1.3 · Remark

Shapley still dilutes credit, and costs $2^n$ retrainings

• Each leavener was sufficient, so one could argue each deserves full credit, not half.
• $v(S)$ for every subset of a training set means retraining on $2^n$ subsets.
• From here on: local, first-order questions about the one run we have.

§1.4 · Notation and goals

Data weights turn deletion into a derivative

• Data $\mathcal D=\{z_i\}_{i=1}^n$, $z_i=(x_i,y_i)$; model $f_w$, $w\in\mathbb R^{d_p}$; per-example loss $L(w,z_i)=\ell(f_w(x_i),y_i)$.
• Data weights $\beta\in\mathbb R^n$; weighted loss $L(w;\beta)=\sum_i\beta_iL(w,z_i)$.
• The behaviour: a differentiable scalar $\phi:W\to\mathbb R$ (a test loss, a logit, a task average).

Parameter influence (how $\pi$ moves) times the gradient of $\phi$ (how that matters).

§2.1 · Example 2.1

Influence on the mean

Put a fraction $\epsilon$ of the mass at $z$:

Rate of change at $\epsilon=0$: $z-T(F)$. Far-out points move the mean most.

§2.1 · Definition 2.2

The influence function

Assume $w^*=w^*(\mathbf 1)$ is the unique global minimum and $H=\nabla_w^2L(w^*)\succ0$. Then

Next four slides: Exercise 2.1, the derivation.

§2.1 · Exercise 2.1(a)

The implicit function theorem gives a smooth branch

• $\partial F/\partial w$ at $(w^*,\mathbf 1)$ is $H$. Invertible $H$ is the IFT's hypothesis.
• So near $\mathbf 1$ there is a unique $C^1$ branch $\beta\mapsto w^*(\beta)$ of critical points with $F(w^*(\beta),\beta)\equiv0$.
• $H\succ0$ makes it a branch of local minima. Calling it the argmin also needs the global minimizer to stay on this branch as $\beta$ moves (no jump to another basin).

§2.1 · Exercise 2.1(b)

Differentiate the optimality condition

§2.1 · Exercise 2.1(c)

Chain rule to the observable

Both factors are evaluated at $\beta=\mathbf 1$, i.e. at $w^*$.

§2.1 · Reading the formula

Pull, rescale by curvature, project

• $-\nabla_wL(w^*,z_i)$: the descent direction in which upweighting $z_i$ pulls the optimizer.
• $H^{-1}$: flat directions (small eigenvalues) are amplified; a small force in a flat direction moves the minimum a lot.

§2.1 · Connection to leave-one-out

Deletion is one unit step in $\beta_i$

First-order Taylor in $\beta$ at $\mathbf 1$, evaluated a full unit away. How good is that? Exercise 2.2 answers it exactly for least squares.

§2.1 · Exercise 2.2(a)

Least squares: the minimizer

§2.1 · Exercise 2.2(b)

Least squares: the influence function

A residual times an input reshaped by the data's own geometry.

§2.1 · Exercise 2.2(c), step 1

Exact reweighting: subtract the normal equations

Write $\delta:=1-\beta_j$ and $\Delta:=w^*(\beta_j)-w^*$. The reweighted normal equations are

§2.1 · Exercise 2.2(c), step 2

Sherman–Morrison on one vector

Rational in $\beta_j$. This is the ground truth; $h_j$ is the leverage.

§2.1 · Exercise 2.2(d)

Expand in the size of the perturbation

• $k=1$: $-(1-\beta_j)A^{-1}x_jr_j=(\beta_j-1)\,\mathcal I_{\mathrm{param}}(z_j)$. The IF is the linear term, as it must be.
• $k\ge2$: each further term carries another factor $(1-\beta_j)\,h_j$.

§2.1 · Exercise 2.2(e)

At deletion the series has no small parameter left

• $h_j\to0$: the IF ($h_j^0$ term) is essentially exact.
• $h_j\to1$: the higher-order terms dominate; the IF underestimates LOO without bound.

§2.1 · Remark: what is leverage?

Unusual inputs, measured in the data's own metric

§2.2 · Translation to neural networks

Three assumptions fail, three fixes

§2.2 · (1) Damping

Damping is a proximal term in the objective

• At $\beta=\mathbf 1$, $w^*$ is still a critical point (the new term and its gradient vanish there).
• Its Hessian is $H+\lambda I\succ0$; the direct term is still $\nabla_wL(w^*,z_i)$.

§2.2 · Exercise 2.3 · set-up

A degenerate toy: only the product $ab$ matters

§2.2 · Exercise 2.3(a)

The Hessian has rank one; its null space is the valley

Null space $\operatorname{span}(a^*,-b^*)$: the tangent to $ab=\bar z$, generator of the symmetry $(a,b)\mapsto(\alpha a,b/\alpha)$.

§2.2 · Exercise 2.3(b)

Pseudoinverse IF for $\phi=ab$, against exact LOO

§2.2 · Exercise 2.3(c)

Damping makes the answer depend on the minimizer

• $\|v\|^2=a^{*2}+b^{*2}$ varies along the valley, so different minimizers give different damped IFs.
• $\lambda\to0$: back to $(z_i-\bar z)/n$. $\;\lambda\to\infty$: zero; the proximal term forbids moving.

§2.2 · Exercise 2.3(c) · an observable that moves along the valley

For $\phi=a^2$ the damped IF stays finite and depends on the minimizer

§2.2 · (2) Negative curvature

Split the Hessian; keep the half that is never negative

$H_{y}=\nabla_f^2\ell\succeq0$ for squared error and cross-entropy, so $G\succeq0$. The second term vanishes when the output-space residuals $\partial\ell_i/\partial f$ vanish.

§2.2 · (3) Non-converged checkpoints · the PBO

Make $w^*$ optimal by construction

• Term 1: don't change the training predictions (relative to the current model). Term 2: the perturbation. Term 3: damping.
• At $\beta=\mathbf 1$ the middle term is zero and the others are $\ge0$ with equality at $w^*$: $w^*$ is the minimizer, whether or not $\nabla L(w^*)=0$.

§2.2 · (3) The PBRF influence, derived

Run Exercise 2.1 on the PBO

§3 · Susceptibilities

The BIF is one susceptibility

With $\kappa=1$ and $\psi=-L(\cdot,z_i)$, raising $h$ is raising $\beta_i$: that is the BIF.

§3.1 · Definition 3.1

Tempered posterior and Bayesian influence function

For a negative log-likelihood loss at $\beta=\mathbf 1$ this is the Bayesian posterior; otherwise a Gibbs measure. Same mathematics.

§3.1 · Exercise 3.1, step 1

Differentiate the normaliser

§3.1 · Exercise 3.1, step 2

Quotient rule: the derivative is a covariance

No Hessian, no inverse: a covariance under the posterior.

§3.1 · Localization

Localize at the checkpoint we actually have

• The localizer doesn't involve $\beta$, so step 2 goes through unchanged.
• $\gamma$ will turn out to play the role of the damping $\lambda$ (Exercise 3.2(e)).

§3.1 · Practical computation

Estimate the covariance with SGLD draws

• The drift is $\tfrac\epsilon2\nabla\log p_\gamma$ (minibatch estimate) and the noise variance is $\epsilon$: Langevin dynamics for $p_\gamma$.
• After burn-in, the sample covariance of $\big(L(w_t,z_i),\phi(w_t)\big)$ over draws estimates $-\mathrm{BIF}_\gamma$; several chains from $w^*$.

§3.1 · Example 3.2 · Bayesian linear regression

The Gaussian case, computed

$L_j(w)=\frac{(y_j-x_j^\top w)^2}{2\sigma^2}$, prior $\mathcal N(0,\tau^2I)$. Posterior $\mathcal N(\mu,V)$, $V=\big(A/\sigma^2+I/\tau^2\big)^{-1}$, $\mu=V\sum_jx_jy_j/\sigma^2$.

§3.2 · Exercise 3.2(a) · Laplace approximation

Near a nondegenerate minimum, the posterior is nearly Gaussian

Assume every eigenvalue of $H=\sum_i\nabla^2L_i$ is of order $n$ ($cnI\preceq H\preceq CnI$), the prior is smooth and $O(1)$, and the posterior concentrates near $w^*$. Then for large $n$: $\;p(w\,|\,\mathcal D)\approx\mathcal N(w^*,H^{-1})$, $\;\Delta=O(n^{-1/2})$.

§3.2 · Exercise 3.2(b)

Expand both functions; odd terms vanish

• $\mathrm{Cov}(T_k,T_m)$ involves moments of $\Delta$ of total degree $k+m$. A centred Gaussian has zero odd moments, so $k+m$ odd gives 0.
• Each pair of $\Delta$'s brings one factor of $H^{-1}=O(1/n)$: the $(k,m)$ term is $O\big(n^{-(k+m)/2}\big)$.

§3.2 · Exercise 3.2(c)

Leading order: the classical influence function

The IF is the $O(1/n)$ term of the BIF.

§3.2 · Exercise 3.2(d) · Isserlis

The $(2,2)$ term sees the curvature of $\phi$ and $L_i$

• Pairing $\Sigma_{ab}\Sigma_{cd}$ gives $\mathbb E[Q_\phi]\,\mathbb E[Q_i]$, which the covariance subtracts.
• The other two each give $\tfrac14\operatorname{tr}(H_\phi\Sigma H_i\Sigma)$.

§3.2 · The rest of the next order

$(2,2)$ is not the whole $O(1/n^2)$ correction

• Also $O(1/n^2)$, and $(1,3)$ survives for a linear observable.
• The true posterior is not the Gaussian surrogate: the cubic and quartic parts of $L$ (and the prior) shift its covariance at the same order.

§3.2 · Exercise 3.2(e)

Localized posterior: the damped influence function

$\gamma$ plays the role of $\lambda$. The local BIF agrees with the damped IF at leading order and keeps every higher term.

§3.3 · Influence functions as optimal transport · set-up

What is the best way to shift samples?

• Instead of resampling, move each $w\sim p_0$ to $T_\varepsilon(w)=w+\varepsilon\,r(w)$, for a smooth field $r$. Call the result $q_\varepsilon$.
• Which $r$ makes $q_\varepsilon$ closest to $p_\varepsilon$? Cost: $\mathcal F(r,\varepsilon)=\lim_{\kappa\to\infty}\frac1\kappa\mathrm{KL}(q_\varepsilon\,\|\,p_\varepsilon)$.

§3.3 · KL as an expectation over the original samples

Change variables back to $w\sim p_0$

§3.3 · Exercise 3.3(a)

KL in terms of energies

• Log-determinant: $O(1)$, so $\frac1\kappa(\cdot)\to0$.
• Partition term (Laplace's method): $\frac1\kappa\log\frac{Z_\varepsilon}{Z_0}\to\inf_wL-\inf_w\big(L-\varepsilon L_k\big)$. Independent of $r$, but not zero.

§3.3 · Exercise 3.3(b), step 1

Expand at $w^*$, where $\nabla L=0$

So the partition term is $\varepsilon L_k(w^*)+\tfrac{\varepsilon^2}2g_k^\top H^{-1}g_k+O(\varepsilon^3)$.

§3.3 · Exercise 3.3(b), step 2

Add up and complete the square

The first-order terms cancel; the partition function supplies exactly the constant that makes a square.

§3.3 · Exercise 3.3(c)

The IF is the KL-optimal first-order shift

• $H^{-1}g_k$ is how far the minimizer moves when $z_k$ is downweighted: minus the upweighting IF.
• Any other value at $w^*$ costs a positive $O(\varepsilon^2)$, its Mahalanobis distance in the Hessian metric.

§3.3 · Exercise 3.3(d) · degenerate minima

Off the valley is determined; along it is free

• Moving along the minimum set costs nothing at this order.
• Needs $g_k\in\operatorname{Range}(H)$ (else $L-\varepsilon L_k$ can drop faster than $\varepsilon^2$: $L=w^4$, $L_k=w$ gives $-3(\varepsilon/4)^{4/3}$). The absolute cost $\mathcal F(H^+g_k)$ need not be $O(\varepsilon^3)$.

§3.3 · Exercise 3.3(e) · linear-regression check

At finite temperature a shift can't fix the covariance

• Best constant shift: $r=-\mathrm{BIF}$. Consistent with (c): $V^{-1}$ is the energy Hessian and $V^{-1}(-\mathrm{BIF})=-x_ke_k/\sigma^2=\nabla L_k(\mu)$.
• The leftover $\frac{\varepsilon^2}4\operatorname{tr}M^2$ is the covariance change: $O(1)$ against the $O(\kappa)$ energy, so it drops out of $\mathcal F$.

§3.3 · Exercise 3.3(f)

Two exercises, two different claims

§4 · The analogy

Unrolling is to a training run what backprop is to a forward pass

§4.1 · Set-up

SGD with data weights

§4.2 · Step Jacobian and direct effect

Two ingredients, as in backprop

§4.2 · Exercise 4.1(a)

One step: a direct and an indirect effect

§4.2 · Exercise 4.1(b)

Unroll the recursion

Write $r_t=\partial w_t/\partial\beta_i$ and $c_t=-\frac{\eta_t}{b}\mathbf 1[i\in B_t]\nabla L(w_t,z_i)$, so $r_{t+1}=J_tr_t+c_t$, $r_0=0$:

Each time $z_i$ was used: its gradient then, carried forward by every later step. Then $\mathcal I=\nabla\phi(w_T)^\top\,\partial w_T/\partial\beta_i$.

§4.2 · Remark: which question does unrolling answer?

One run, with its randomness frozen

• The formula differentiates a specific trajectory: fixed initialization, batch order, augmentation.
• That answers the single-model question: how would this run have ended?
• The distributional question (expected change over training randomness) needs an average over runs.

§4.2 · Exercise 4.1(c) · preconditioned SGD

Adaptive optimizers, with the preconditioner frozen

Each gradient is premultiplied by the preconditioner of its own step: early in training Adam's $P_t$ is built from little history.

§4.2 · Remark: TracIn

Drop the Jacobians, read the query at each checkpoint

• Set every $J=I$ and evaluate $\nabla\phi$ at $w_t$, not $w_T$.
• An actual minibatch step decreases $\phi$, to first order, by $\frac{\eta_t}b\mathbf 1[i\in B_t]\nabla\phi(w_t)^\top\nabla L_i(w_t)$ through $z_i$. TracIn sums these along the path; TracInCP uses checkpoint similarities as a proxy. Neither asks how the endpoint would move.

§4.2.1 · SOURCE · stationary segments

Freeze curvature within segments

Checkpoints $0=T_0\lt T_1\lt\cdots\lt T_L=T$, $K_\ell=T_\ell-T_{\ell-1}$. Within segment $\ell$:

On an eigenvalue $\sigma$ of $\bar H_\ell$: $e^{-\bar\eta_\ell K_\ell\sigma}$. Stiff directions are forgotten; flat ones are kept.

§4.2.1 · SOURCE · segment response

Within a segment the sum is a geometric series

§4.2.1 · SOURCE · the filter

Unrolling replaces $1/\sigma$ by a filter

• $\sigma\gg1/(\bar\eta K)$: converged directions, $F_r\approx1/\sigma$. $\;\sigma\to0$: barely moved, $F_r\to\bar\eta K$, finite.

§4.2.1 · SOURCE · full formula

Chain the segments

• One segment: the IF with $H^{-1}$ replaced by $F_r$.
• Several: a segment's response is carried through the later segments' frozen Jacobians. With different $\bar H_\ell$ this is not one filter on one gradient.

§4.2.2 · MAGIC · metagradients

Or never form a Jacobian: backprop through training

The backward recursion is backprop through the training loop. For SGD, $B_t=-\frac{\eta_t}{b}\big[\nabla L(w_t,z_i)\,\mathbf 1[i\in B_t]\big]_{i=1}^n$.

§4.2.2 · REPLAY

Regenerate states instead of storing them

1. Save $k$ evenly spaced checkpoints.
2. When the backward pass needs a state in between, replay training forward from the nearest checkpoint.
3. Recurse: a $k$-ary tree of depth $\log_kT$.

$O(k\log_kT)$ stored states, $O(T\log_kT)$ forward work: a logarithmic overhead on training.

§4.2 · Materialize or replay?

SOURCE approximates; MAGIC computes

§4.3 · Exercise 4.2 · set-up

Does unrolling converge to the influence function?

$\varepsilon=0$ is the original run; $\varepsilon=1$ removes $z_k$. Since $\beta_k=1-\varepsilon$, $\;r_t=-\partial w_t/\partial\beta_k$.

§4.3 · Exercise 4.2(a)

The response joins the state: a Markov chain

• Bottom row: Exercise 4.1(a) times $-1$. The plus sign: downweighting pushes against $z_k$'s descent direction.
• $(w_{t+1},r_{t+1})$ depends only on $(w_t,r_t)$ and the fresh i.i.d. batch: a Markov chain, so stochastic-approximation tools apply.

§4.3 · Exercise 4.2(b) · full-batch warm-up

A converged window of $K$ steps

Full batch ($b=n$), constant $\eta$; write $\alpha=\eta/n$, the step on the summed loss. On the window $w_t=w^*$, so

§4.3 · Exercise 4.2(b) · the limit

The run forgets its history and lands on the IF

§4.3 · Exercise 4.2(c) · stochastic case

The ODE the response tracks

• (i) Equilibrium: $Hr=\nabla L(w^*,z_k)$. In the column space of $H$: $r_{\mathrm{IF}}=H^+\nabla L(w^*,z_k)$.
• (ii) Project with $P_0$ onto $\ker H$: $P_0\dot r=P_0\nabla L(w^*,z_k)$, so $P_0r(t)=P_0r(0)+t\,P_0\nabla L(w^*,z_k)$.
• No restoring force along flat directions: the response drifts linearly unless $P_0\nabla L(w^*,z_k)=0$.

§4.3 · Mlodozeniec et al., Theorem 2

Unrolling converges to the IF, up to the flat directions

Almost surely, on SGD trajectories that converge to a local minimum, under the theorem's assumptions. The null-space component need not converge.

§4.4 · Exercise 4.3 · set-up

A deep linear network: influence changes over training

Logistic in each mode. Rise when $e^{2s_kt/\tau}\approx s_k/\mathcal G_k(0)$: $\;t_k^*\approx\frac{\tau}{2s_k}\log\frac{s_k}{\mathcal G_k(0)}$. With a common small initial strength, big modes first.

§4.4 · The notes' decomposition

Perturb $\Sigma_{yx}$: rotate the modes, or change their speed

$A=U^\top\delta U$ and $B=\delta V^\top V$ are skew; $g'_t(s_k)=\partial\mathcal G_k(t)/\partial s_k$; $\delta s_k$ is the change of the $k$-th singular value of $\Sigma_{yx}$.

§4.4 · The rotation entries

The derivative of an SVD

Perturb $\Sigma=USV^\top$ by $\delta\Sigma$; let $E=U^\top\delta\Sigma\,V$. Then $E=AS+\delta S-SC$ with $C=V^\top\delta V$, and for $j\ne k$:

For symmetric $E$ this is $E_{jk}/(s_k-s_j)$, the notes' formula. Check: $S=\operatorname{diag}(3,1)$, $E_{12}=1$, else 0: $A_{12}=-1/8$, not $-1/2$.

§4.4 · Exercise 4.3(a)

Why rotation goes with $\mathcal G$, speed with $g'$

• Rotation ($A\mathcal G$, $\mathcal GB$): turning the basis of a mode that hasn't been learned ($\mathcal G_k\approx0$) changes nothing; the effect scales with what has been learned.
• Speed ($\mathcal G'_\varepsilon$): shifting $s_k$ changes how fast mode $k$ is learned. It matters when $\mathcal G_k(t)$ is sensitive to $s_k$, not when $\mathcal G_k$ is large.

§4.4 · Exercise 4.3(b)

The speed channel is localized at the mode's rise

• $t\ll t_k^*$: $\mathcal G_k\approx\mathcal G_k(0)$ whatever $s_k$ is, so $g'_t(s_k)\approx0$.
• $t\gg t_k^*$: $\mathcal G_k\approx s_k$, so $g'_t(s_k)\to1$, but for a query the network ends up fitting (e.g. realizable, $y_q=Sx_q$) the mode-$k$ residual $\to0$.
• The product $g'_t(s_k)\times(\text{mode-}k\text{ residual})$ peaks near $t_k^*$.

§4.4 · Exercise 4.3(c) · the sign flip

A dog helps a cat, then hurts it, then neither

Inputs (coarse, fine): dog $(1,1)$, cat $(1,-1)$, oak $(-1,1)$, rose $(-1,-1)$; $y=Sx$, $s_1\gt s_2$. Upweight dog; query cat.

Summary

One derivative, three readings, one limit