技术摘要：将核技巧扩展至影响函数

问题陈述

影响函数最初在鲁棒统计中发展，并由 Koh 和 Liang [1] 适配至机器学习领域，提供了一种估算当训练数据点受到扰动或被移除时，模型参数和输出如何变化的方法。这种能力对于机器遗忘、可解释性和隐私保护至关重要。然而，将影响函数的标准应用扩展到大规模深度学习模型时，面临着显著的可扩展性瓶颈。

核心计算挑战在于逆海森矩阵 - 向量积（IHVP），即 $H_{\theta^*}^{-1} \nabla_\theta L_{D_f}(\theta^*)$，该计算用于近似在移除遗忘集 $D_f$ 后参数 ($\theta_r^*$) 的变化。在原始公式中，海森矩阵 $H_{\theta^*}$ 的规模随模型参数数量 ($d_\theta$) 的平方增长。对于大型模型（例如深度神经网络），构建并求逆该矩阵是不可行的。虽然共轭梯度（CG）等迭代方法避免了显式构建海森矩阵，但它们仍依赖于随模型规模增长的海森 - 向量积（HVPs），使得当 $d_\theta$ 相对于数据集规模较大时，该过程计算成本高昂。

方法论

作者提出了一种影响函数的对偶表示，将计算复杂度从随模型规模 ($d_\theta$) 增长转变为随数据集规模 ($|D|$) 和输出维度 ($d_{out}$) 增长。该方法基于可线性化模型理论和神经正交核（NTK）。

1. 线性化与重参数化

该方法假设模型 $f(\cdot, \theta)$ 是“可线性化的”，即其在整个训练过程中的行为可以通过围绕参考点 $\theta'$（通常是初始化点）的线性化来近似。作者定义了一个线性化模型 $f^{lin}$ 以及相应的正则化经验风险 $\hat{L}_D(\theta)$。

推导的关键在于命题 3.1，该命题确立了对于任意数据子集，线性化模型的最优参数与全数据集最优参数之间的差异位于 $\mathbb{R}^{d_\theta}$ 的一个特定线性子空间中：
$$\hat{\theta}_r^* - \hat{\theta}^* = \nabla_\theta f(X, \theta')^\top \Delta \alpha_r^*$$
其中 $\Delta \alpha_r^* \in \mathbb{R}^{d_{out}|D|}$。

这一观察使得作者能够重参数化优化问题。他们不再在高维参数空间 $\theta$ 上进行优化，而是在对偶变量 $\Delta \alpha$ 上进行优化。$\theta$ 空间中的约束问题被转化为 $\Delta \alpha$ 空间中的无约束问题：
$$\tilde{L}_D(\Delta \alpha) := \frac{1}{|D|} \sum_{(x,y) \in D} \left( \ell(g^{lin}(x, \Delta \alpha), y) + \frac{\lambda}{2} \|\phi(\Delta \alpha) - \theta'\|_2^2 \right)$$
其中 $g^{lin}$ 涉及经验 NTK，$K(\cdot, \cdot) = \nabla_\theta f(\cdot, \theta') \nabla_\theta f(\cdot, \theta')^\top$。

2. 对偶影响函数

在 $\Delta \alpha$ 空间中，移除数据点的影响通过求解涉及对偶风险海森矩阵 $H_{\Delta \alpha^*}$ 的线性系统来近似。关键在于，该海森矩阵的规模为 $d_{out}|D| \times d_{out}|D|$，而非 $d_\theta \times d_\theta$。

对偶变量变化的近似值为：
$$\Delta \alpha_r^* \approx \frac{|D_f|}{|D|} H_{\Delta \alpha^*}^{-1} \nabla_{\Delta \alpha} \tilde{L}_{D_f}(0)$$
作者表明该系统可以高效求解。具体而言，如果遗忘集 $D_f$ 较大，待求解的线性系统维度实际上会减小，因为对应于 $D_f$ 的 $\Delta \alpha_r^*$ 的已知分量可以被分离出来。

3. 变化估计

一旦获得 $\Delta \alpha_r^*$，即可利用 NTK 估算测试点的模型输出和损失变化：

• 输出变化：$f^{lin}(x_t, \hat{\theta}_r^*) - f^{lin}(x_t, \hat{\theta}^*) \approx K(x_t, X) \Delta \alpha_r^*$
• 损失变化：通过对偶损失关于 $\Delta \alpha$ 的梯度进行估算。

只要 NTK 具有解析形式，该公式即可用于计算具有无限多参数的模型的影响。

主要贡献

1. 对偶表示：本文提出了影响函数的对偶公式，其计算复杂度取决于数据集规模 ($|D|$) 和输出维度 ($d_{out}$)，而非模型参数数量 ($d_\theta$)。
2. 大型模型的高效性：当 $d_\theta \gg d_{out}|D|$ 时，该方法为原始影响函数提供了一种高效的替代方案。它避免了在庞大的参数空间中计算 HVPs 的需求。
3. 无限宽度的适用性：该框架通过利用解析 NTK，将影响分析扩展至无限宽神经网络，从而能够估算无限参数极限下的参数和输出变化。
4. 计算捷径：作者发现，在对偶空间中，随着遗忘集规模 ($|D_f|$) 的增加，线性系统的规模反而减小，这为大规模遗忘任务提供了一种反直觉的效率提升。

实验结果

作者在 MNIST 和 CIFAR-10 子集上训练的完全连接神经网络（FCNN）和卷积神经网络（CNN）的线性化版本上验证了该方法。

• 运行时间：$\Delta \alpha$ 空间方法在“冷启动”（首次执行）和“热启动”（重复执行）场景中均 consistently 优于原始 $\theta$ 空间方法。随着模型规模相对于数据集规模的增加，性能差距进一步扩大。
• 准确性：遗忘性能（通过遗忘参数与重训练参数之间的相对 $\ell_2$ 距离以及遗忘集上的准确率来衡量）与原始方法相当。
• 正则化 ($\lambda$) 的影响：在非线性模型上的实验表明，较大的正则化常数 $\lambda$ 值使得非线性模型的训练动态更接近其线性化形式。这提高了对偶表示在非线性模型中的可靠性，但代价是测试准确率降低。
• 无限宽网络：该方法成功估算了无限宽 FCNN 和 CNN 的输出及损失变化，估算结果与通过核梯度下降计算的实际变化高度吻合。

意义与主张

本文主张，对偶表示为机器遗忘和影响分析提供了一种可扩展的解决方案，适用于模型规模大到传统参数空间方法无法处理的场景。

• 可扩展性：它使得估算那些在参数空间中评估原始影响函数不可行的模型的影响成为可能。
• 理论扩展：它为分析神经网络无限宽极限下的影响提供了理论桥梁。
• 局限性：作者明确指出，该方法仅限于可线性化模型。虽然较大的正则化 ($\lambda$) 可以将非线性模型近似为可线性化，但这会损害模型性能。此外，该方法需要显式构建或在隐式操作中处理 NTK 矩阵，其规模随数据集规模与输出维度的乘积增长，对于具有大量类别的超大数据集，这可能成为瓶颈。

该工作并未声称能解决所有深度学习模型的遗忘问题，而是提供了一种专门的、高效的工具，适用于数据集规模相对于模型容量较小，或模型可有效被视为线性的场景。