基于影响函数的BPR推荐模型高效机器遗忘框架

1. 项目概述：当推荐系统需要“忘记”

在推荐系统的日常运维和迭代中，我们常常面临一个看似矛盾的需求：模型需要从海量用户行为数据中学习，以提供精准的个性化推荐；但同时，由于隐私法规（如GDPR）的合规要求、用户主动删除数据的权利，或是系统需要剔除异常或恶意的注入数据，我们又需要让模型能够“忘记”某些特定的数据。

传统的解决方案简单粗暴：重新训练。把要“忘记”的数据从训练集中剔除，然后用剩下的数据从头开始训练一个新模型。这确实能保证遗忘的彻底性，但代价是巨大的计算开销和时间成本。对于一个拥有数千万甚至上亿交互数据、模型参数庞大的在线推荐系统来说，频繁的完全重训练几乎是不可行的。这就好比为了修改一篇文章里的几个错别字，而选择把整本书重写一遍。

因此，“机器遗忘”应运而生。它的目标不是重新训练，而是通过数学和算法手段，直接、高效地从已训练好的模型中“抹去”特定数据的影响，使模型的状态近似于“从未见过这些数据”一样。这听起来像魔法，但其背后有坚实的数学基础，其中“影响函数”便是一个强有力的工具。

我这次要深入探讨的，正是将影响函数应用于一个特定的、也是业界非常流行的推荐模型——贝叶斯个性化排序。BPR模型的核心在于它不直接预测评分，而是学习用户对物品的偏好排序，这使其能更好地捕捉“用户为什么喜欢A胜过B”的细微差别。然而，这种基于成对比较的学习方式，也让遗忘变得更为复杂：你不仅要移除一个正向的用户-物品交互，还要处理围绕这个交互所构建的一系列“A比B好”的排序关系。

2. 核心思路：用“影响函数”精准定位并消除数据影响

要理解我们提出的框架，首先得弄明白“影响函数”在机器遗忘中扮演的角色。你可以把它想象成模型参数的“灵敏度分析器”。

2.1 影响函数的基本原理

假设我们已经用全部数据集D训练好了一个模型，其最优参数为Θ。现在，我们想评估训练集中某一个或一组数据点z对最终模型参数Θ的“贡献”有多大。影响函数的核心思想是：如果我们给这个数据点z的损失函数增加一个无穷小的权重ε，观察模型参数会如何变化。

数学上，这可以通过对加权后的损失函数进行一阶泰勒展开来近似。最终，数据点z对参数Θ的影响可以近似表示为：I(z) ≈ -H_Θ^{-1} ∇_Θ L(z|Θ)其中，H_Θ是整个数据集损失函数在Θ处的海森矩阵（即二阶导数），∇_Θ L(z|Θ)是数据点z损失函数在Θ处的梯度。

这个公式的直观解释是：一个数据点对模型的影响，正比于模型在该数据点上的“犯错程度”（梯度），但反比于模型在当前参数下的整体“曲率”或“稳定性”（海森矩阵的逆）。如果模型已经很稳定（海森矩阵值大），单个数据点的影响就小；反之，如果模型在某个方向上还很“不确定”，数据点的影响就会被放大。

2.2 从“评估影响”到“执行遗忘”

影响函数原本用于解释模型决策。而我们将其创造性应用于遗忘任务：既然我们能计算出一个数据点对模型参数的“正向”影响，那么理论上，我们只要将这个影响“反向”施加到现有参数上，就能抵消该数据点的贡献，从而实现遗忘。

具体到我们的场景，设需要遗忘的数据子集为D_f。我们的目标是从当前模型参数Θ出发，通过一步计算，得到近似于在剩余数据D_r = D \ D_f上重训练得到的参数Θ‘。

通过严谨的推导（详见原论文Proof A），我们可以得到遗忘后的参数更新公式：Θ‘ ≈ Θ + (1/|D|) * H_Θ^{-1} * ∇_Θ L(D_f|Θ)

这个公式就是整个框架的引擎：

1. ∇_Θ L(D_f|Θ)：计算需要遗忘的数据集D_f在当前模型Θ下的梯度。这代表了D_f当前对模型参数更新的“拉力”。
2. H_Θ^{-1}：计算整个数据集D损失函数的海森逆矩阵。这相当于一个“缩放因子”或“矫正器”，它考虑了模型整体的曲率，确保我们施加的反向更新是恰到好处的。
3. (1/|D|)：一个归一化系数，与原始训练时的数据量相关。
4. Θ + ...：将计算出的“反向影响”加到原始参数上，从而抵消D_f的贡献。

注意：这个推导基于一个关键假设，即要遗忘的数据量|D_f|远小于总数据量|D|。这在实际场景中是合理的，我们通常不会一次性要求模型忘记其大部分知识。对于大规模遗忘，可能需要迭代应用此方法或考虑其他方案。

2.3 BPR模型带来的独特挑战与应对

标准的矩阵分解或点态预测模型，其损失函数（如均方误差）只针对单个用户-物品对。遗忘时，只需移除该对数据的影响。但BPR的损失函数是成对的：L = -log σ(ŷ_ui - ŷ_uj)其中(u, i, j)是一个三元组，i是用户u交互过的正样本物品，j是随机采样的未交互负样本物品。

这意味着，模型从数据(u, i)中学到的，不仅仅是用户u喜欢物品i，更是“在用户u的偏好空间中，物品i应该排在物品j前面”这样一个偏序关系。因此，当我们要求遗忘一个用户-物品交互(u, i)时，我们实际上需要遗忘所有与之相关的三元组(u, i, j)（对于所有采样到的负样本j）。

我们的框架天然地处理了这一点。在计算L(D_f|Θ)时，我们将D_f定义为所有需要遗忘的三元组集合。这样，梯度∇_Θ L(D_f|Θ)就自动包含了需要抹去的所有偏序关系信息。通过一次更新，我们同时移除了正向交互的影响，并破坏了围绕该交互建立起来的排序结构。

3. 实现细节与高效计算策略

理论很优美，但直接套用公式面临巨大的计算挑战。海森矩阵H_Θ的维度是(参数总数×参数总数)。对于拥有数百万甚至上亿参数的推荐模型，存储和求逆这个矩阵是完全不可能的。我们必须寻求高效的近似方案。

3.1 海森向量积与共轭梯度法

我们采用的核心技术是海森向量积配合共轭梯度法来间接求解H_Θ^{-1} v（其中v = ∇_Θ L(D_f|Θ)），而无需显式构造或求逆海森矩阵。

海森向量积是一个技巧，它允许我们仅通过一次额外的反向传播，就计算出H_Θ * z的结果，其中z是任意向量。具体实现依赖于自动微分框架（如PyTorch、TensorFlow）的以下性质：H_Θ * z ≈ [∇_Θ (∇_Θ L(D|Θ)^T * z)] / |D|也就是说，先计算整个数据集损失函数关于参数的梯度g = ∇_Θ L(D|Θ)，然后计算这个梯度与向量z的点积g^T z，再对这个标量结果关于参数Θ求一次梯度，得到的结果就是近似的H_Θ * z。

共轭梯度法是一种迭代算法，用于求解线性方程组A x = b。在我们的场景中，A = H_Θ,b = ∇_Θ L(D_f|Θ)，我们要求解x = H_Θ^{-1} b。CG法的美妙之处在于，它只需要能够计算矩阵A与任意向量的乘积（即矩阵向量积），而不需要直接得到A本身。而这正是HVP所能提供的。

因此，整个求解Θ_update = H_Θ^{-1} * ∇_Θ L(D_f|Θ)的过程可以高效地完成：

1. 定义目标：求解H_Θ * x = ∇_Θ L(D_f|Θ)。
2. 使用共轭梯度法迭代求解x。
3. 在CG法的每一步迭代中，当需要计算H_Θ * p（p为搜索方向向量）时，调用HVP技巧进行计算。

3.2 实操步骤与代码示意

以下是基于PyTorch实现核心遗忘步骤的简化代码框架：

import torch import torch.nn.functional as F from torch.utils.data import DataLoader from tqdm import tqdm def hvp(y, w, v): """ 计算海森向量积 H * v。 y: 损失函数标量值（对整个数据集D）。 w: 模型参数。 v: 向量，其形状与w相同。 """ # 第一次反向传播，计算梯度 dy/dw grad = torch.autograd.grad(y, w, create_graph=True) # 计算梯度与向量v的点积 grad_dot_v = torch.sum(torch.stack([torch.sum(g * v_elem) for g, v_elem in zip(grad, v)])) # 第二次反向传播，计算点积关于w的梯度，即 H * v hvp = torch.autograd.grad(grad_dot_v, w, retain_graph=True) return hvp def conjugate_gradient(hvp_fn, b, max_iter=100, tol=1e-10): """ 共轭梯度法求解 Hx = b。 hvp_fn: 计算 H*p 的函数。 b: 目标向量。 """ x = [torch.zeros_like(p) for p in b] # 初始解 r = [b_elem.clone() for b_elem in b] # 残差 r = b - Hx (初始为b) p = r[:] # 搜索方向 rsold = sum([torch.sum(r_elem * r_elem) for r_elem in r]) for i in range(max_iter): Hp = hvp_fn(p) # 使用HVP计算 H*p alpha = rsold / (sum([torch.sum(p_elem * Hp_elem) for p_elem, Hp_elem in zip(p, Hp)]) + 1e-10) # 更新解和残差 x = [x_elem + alpha * p_elem for x_elem, p_elem in zip(x, p)] r = [r_elem - alpha * Hp_elem for r_elem, Hp_elem in zip(r, Hp)] rsnew = sum([torch.sum(r_elem * r_elem) for r_elem in r]) if torch.sqrt(rsnew) < tol: break p = [r_elem + (rsnew / rsold) * p_elem for r_elem, p_elem in zip(r, p)] rsold = rsnew return x def unlearn_with_influence(model, full_dataset, forget_triples, device): """ 执行基于影响函数的遗忘。 model: 已训练好的BPR模型。 full_dataset: 原始完整训练数据集（用于计算H）。 forget_triples: 需要遗忘的三元组列表 [(u, i, j), ...]。 """ model.eval() params = list(model.parameters()) # 1. 计算遗忘数据集的梯度 v = ∇L(D_f|Θ) loss_f = 0.0 for (u, i, j) in forget_triples: y_ui = model(u, i) y_uj = model(u, j) loss_f += -F.logsigmoid(y_ui - y_uj) loss_f = loss_f / len(forget_triples) v = torch.autograd.grad(loss_f, params, create_graph=True) # 需要create_graph以用于后续HVP # 2. 定义计算整个数据集损失函数y的函数（用于HVP） def compute_full_loss(): total_loss = 0.0 data_loader = DataLoader(full_dataset, batch_size=4096, shuffle=False) for batch in data_loader: u_b, i_b, j_b = batch y_uib = model(u_b, i_b) y_ujb = model(u_b, j_b) batch_loss = -F.logsigmoid(y_uib - y_ujb).mean() total_loss += batch_loss * len(u_b) return total_loss / len(full_dataset) # 3. 定义HVP函数 def hvp_fn(vec): y = compute_full_loss() return hvp(y, params, vec) # 4. 使用共轭梯度法求解 H^{-1} * v print("Solving H^{-1}v using Conjugate Gradient...") h_inv_v = conjugate_gradient(hvp_fn, v) # 5. 应用更新：Θ' = Θ + (1/|D|) * H^{-1} * v with torch.no_grad(): for p, delta in zip(params, h_inv_v): p.data += (1.0 / len(full_dataset)) * delta print("Unlearning completed.") return model

关键操作解析：

• create_graph=True：在计算梯度v时，必须保留计算图，因为后续的HVP计算需要在此基础上进行二次求导。
• 共轭梯度法的收敛性：海森矩阵H_Θ需要是正定的，才能保证CG法收敛。在深度学习模型中，由于非凸性和随机性，这并非绝对保证。实践中，我们通常加入一个很小的阻尼项(H + λI)来确保正定性，其中λ是一个小的正数（如1e-4）。
• 计算开销：虽然避免了显式的海森矩阵求逆，但计算H_Θ^{-1} v仍然需要多次HVP计算（CG法迭代次数次）。每次HVP都需要一次完整的前向-反向传播来计算y，以及一次额外的反向传播。因此，其计算成本与几次完整训练迭代相当，但相比从头重训练（通常需要数十上百轮迭代），效率提升依然是指数级的。

4. 实验验证与效果分析

我们通过在MovieLens-1M和Pinterest两个经典推荐数据集上的实验，全面验证了所提UBPR框架的有效性和高效性。

4.1 实验设置与对比基线

• 数据集：MovieLens-1M（显式反馈转换）和Pinterest（隐式反馈）。我们对每个正向交互采样4个负样本，构建BPR训练三元组。
• 评估指标：
  • 有效性：使用命中率（HR@K）和归一化折损累计增益（NDCG@K）来衡量遗忘后模型的推荐性能是否与“重训练”基准模型接近。K取{1,5,10,20,25,30,40,50,60,80,100}。
  • 效率：直接比较遗忘操作的运行时间。
• 对比方法：
  1. Retrain：黄金标准，在剩余数据上完全重新训练模型。
  2. SISA：将数据分片，独立训练子模型。遗忘时仅重训练受影响的数据片对应的子模型。
  3. RecEraser：一种先进的推荐遗忘框架，同样基于数据分区和模型聚合。

4.2 有效性结果：媲美重训练的遗忘精度

我们在不同遗忘比例（从总数据量的0.01%到0.035%）下进行了测试。核心结论如下：

1. 性能接近重训练：如下图所示，在不同K值和不同遗忘比例下，我们提出的UBPR方法（橙色线）的NDCG曲线与Retrain基线（绿色线）几乎重合。在Pinterest这样的大规模数据集上，NDCG差异基本保持在0.001-0.003以内；在MovieLens上，差异稍大，但也在0.01-0.03的可接受范围内，考虑到模型训练本身的随机性，这个差距是微不足道的。 （此处应插入论文中的Figure 1和Figure 2，展示NDCG@K曲线对比图。图中可见UBPR与Retrain曲线紧贴，显著优于SISA和RecEraser。）

2. HR与NDCG的定量分析：下表展示了在K=10时，各方法在HR@10和NDCG@10上的具体数值。Δ列表示UBPR与Retrain的差值。

数据显示，UBPR在HR指标上几乎与Retrain完全一致（差值在1e-3量级）。在NDCG指标上，MovieLens的差值随遗忘比例增加略有增大，但仍在合理范围；而在数据量更大的Pinterest上，差值始终极小。这验证了我们的理论：在大规模数据集下，基于影响函数的一次近似更新可以达到近乎重训练的效果。

3. 对数据规模的敏感性：实验表明，原始数据集越大，UBPR的遗忘效果相对重训练就越接近。这是因为影响函数的推导基于泰勒展开，其近似精度在参数扰动较小时更高。当原始数据集|D|远大于遗忘集|D_f|时，参数更新量Δ很小，近似效果最好。

4.3 效率结果：数量级的速度提升

效率是机器遗忘的核心价值所在。下图展示了不同方法在不同遗忘比例下的运行时间对比：

（此处应插入论文中的Figure 3，展示运行时间柱状图。图中可见Retrain耗时最长且基本恒定，SISA和RecEraser次之，而UBPR的耗时最短，且几乎不随遗忘比例变化。）

关键发现：

• 显著加速：在MovieLens和Pinterest数据集上，UBPR相比完全重训练（Retrain），速度分别提升了约10倍和8倍。
• 时间构成：Retrain、SISA、RecEraser的时间主要消耗在模型重新训练/部分重训练的迭代过程上，其时间与剩余数据集大小和训练轮数成正比。而UBPR的时间主要消耗在单次计算H_Θ^{-1} v上，这依赖于共轭梯度法的迭代次数和每次迭代中HVP的计算成本。后者通常远小于一次完整的训练周期。
• 存储优势：SISA和RecEraser需要存储多个子模型或大量中间参数，而UBPR只需要保存最终的训练好的模型和用于计算HVP的原始数据集（或一个代表性的数据子集，用于近似计算整个数据集的损失），在存储开销上更具优势。

4.4 深入分析：偏序关系真的被“遗忘”了吗？

为了直观验证UBPR不仅忘记了数据点，还破坏了其学到的偏序关系，我们进行了可视化分析。

可视化分析：我们选取特定用户，使用t-SNE将其嵌入向量及其交互过的正样本物品、对应采样的负样本物品的嵌入向量降维到2D平面进行可视化。下图展示了用户user_0在遗忘前后的变化：

（此处应插入论文中的Figure 4(a)(b)，展示用户-物品在潜在空间中位置关系的变化。）

• 遗忘前：用户点（红色）与正样本物品（方块）在空间中距离较近，而与负样本物品（三角形）距离较远，清晰反映了“用户偏好正样本胜过负样本”的偏序关系。
• 遗忘后：用户点的位置发生了显著偏移。更重要的是，用户与正样本、负样本之间的距离差异变得模糊，甚至出现用户更靠近某些负样本的情况。同时，一些正负样本对之间的距离也缩小了。这表明，UBPR成功地扰乱了模型为该用户学习到的特定偏好结构，实现了对偏序关系的遗忘。

量化度量：我们提出了“正-负偏好比”来衡量一个用户对其正负样本的区分度。PNPR值大于1表示用户更偏好正样本。实验结果显示，在遗忘后，无论是用Retrain还是UBPR，用户的PNPR值都趋近于1，即用户对正负样本不再有明显的偏好区分，这与可视化结果相互印证。

5. 实战心得与避坑指南

在实际实现和应用这个框架时，我踩过不少坑，也总结出一些关键经验。

5.1 海森矩阵正定性的保证

共轭梯度法要求海森矩阵是正定的。但在神经网络的非凸损失 landscape 中，这一点无法保证。直接应用可能导致CG法不收敛或求解不稳定。

解决方案：在实践中，必须为海森矩阵添加一个阻尼项。即在求解Hx = b时，实际求解(H + λI)x = b，其中λ是一个小的正数（如1e-4到1e-6）。这相当于在牛顿法中引入正则化，确保矩阵的正定性，同时也能改善问题的条件数，加速CG收敛。

# 在共轭梯度法的hvp_fn中，实际计算 (H + λI)p def hvp_fn_with_damping(vec, damping=1e-4): Hp = hvp(y, params, vec) # 计算 H*p # 添加阻尼项 λI*p damped_Hp = [Hp_elem + damping * p_elem for Hp_elem, p_elem in zip(Hp, vec)] return damped_Hp

5.2 高效计算HVP与内存管理

计算整个数据集D的损失y以进行HVP，如果数据集非常大，每次CG迭代都遍历全部数据，开销依然可观。

优化策略：

1. 数据子集估计：可以使用一个均匀采样子集D_s ⊂ D来近似计算H_Θ。只要子集足够大且有代表性，就能很好地近似整体曲率。这能大幅减少每次HVP的计算量。
2. 随机估计HVP：甚至可以进一步采用随机估计方法，例如基于Hutchinson估计器，来近似海森矩阵的迹或对角元素，但这对精度有一定影响。
3. 检查点与重计算：在计算∇_Θ L(D|Θ)时，如果模型很大，存储完整梯度可能内存不足。可以采用梯度检查点技术，在需要时重新计算部分前向和反向传播，以时间换空间。

5.3 遗忘范围的界定：三元组的构建

对于BPR模型，确定需要遗忘的D_f（三元组集合）是关键。如果用户请求删除与物品i的所有交互，那么D_f应包含所有以(u, i)为正样本的三元组(u, i, j)。但是，负样本j是随机采样的，我们无法重建训练时所有的负样本。

处理方案：在实践中有两种选择：

• 精确重建：如果训练时记录了每个正样本对应的所有负样本ID，则可以直接使用。
• 近似模拟：更常见的情况是，我们只记录正样本对。此时，在遗忘阶段，可以为每个待遗忘的正样本对(u, i)，重新采样一批负样本j（例如，采样4个），用这些新构建的三元组作为D_f。虽然这与原始训练三元组不完全相同，但由于BPR学习的是分布级的偏好，这种近似在大多数情况下是有效的。实验也验证了这种做法的可行性。

5.4 大规模遗忘与迭代更新

我们的理论推导假设|D_f| << |D|。如果需要遗忘的数据量很大，单次更新Δ可能过大，导致一阶泰勒近似失效，遗忘效果变差。

应对方法：可以采用增量式或迭代式遗忘。将大的遗忘集D_f分成多个小批次{D_f1, D_f2, ...}。对每个小批次，应用一次UBPR更新。这相当于沿着“遗忘路径”进行多步的小更新，每一步都满足小扰动假设，从而在整体上实现大规模遗忘。不过，这也会相应增加计算时间。

6. 总结与展望

基于影响函数的贝叶斯个性化排序机器遗忘框架，为解决推荐系统中高效、精准的数据移除问题提供了一个强有力的工具。它从理论上建立了近似重训练的数学基础，并通过海森向量积与共轭梯度法实现了高效计算。实验证明，该方法在效果上可以逼近完全重训练，在效率上则能提升一个数量级，同时还能有效处理BPR模型特有的偏序关系遗忘问题。

在实际部署中，我们需要权衡精度、效率和存储。对于频繁发生的小规模遗忘请求（如单个用户行使“被遗忘权”），UBPR是非常理想的选择。对于大规模数据更新，可能需要结合分批次迭代遗忘或其他策略。

这个方向仍有探索空间，例如：

• 更稳定的海森逆估计：研究如何用更少的迭代或更稳定的方法来估计H^{-1}v，特别是在模型参数极多的情况下。
• 与其他遗忘机制的融合：能否将影响函数方法与模型剪枝、参数掩码等技术结合，实现更极致的效率或应对更复杂的遗忘场景（如遗忘特定特征）。
• 理论保证的强化：在更宽松的假设下，为近似遗忘提供更严格的理论误差界。

机器遗忘不仅是合规的需求，更是构建可持续、可信赖AI系统的基础能力。这项工作为在复杂的、基于排序的推荐模型中实现这一能力，迈出了扎实的一步。