Machine Unlearning

Lucas Bourtoule 等人于 2019年在 arXiv 上发表，并最终在 2021年的 IEEE Symposium on Security and Privacy (S&P) 上正式发表的论文 《Machine Unlearning》。

比较早期的模型，方法比较朴素。

训练阶段 (Training Phase)：

1. 数据分片 (Sharding)：将完整的原始训练数据集 D 分割成 S 个互不相交的数据子集，称为“分片” (Shards)。

2. 数据切片 (Slicing)：将每个分片 Dk 内部的数据再进一步分割成 R 个互不相-交的“切片” (Slices)。

3. 隔离与增量训练 (Isolated & Incremental Training)：为每一个分片 Dk 单独训练一个模型 Mk，过程如下：

   • 步骤 1: 使用随机初始化的参数，仅在第一个切片 Dk,1 上训练模型。训练完成后，保存当前模型的参数状态。
   • 步骤 2: 加载上一步保存的模型参数，然后在 Dk,1 ∪ Dk,2 的数据上继续训练。完成后保存新的模型状态。
   • 重复此过程: 直到模型在所有 R 个切片上都训练完毕。每次加入一个新的切片进行训练后，都要保存一次模型状态。

4. 聚合 (Aggregation)：在需要进行预测时，将输入数据分别送入所有 S 个独立训练好的模型。然后通过“多数投票”等策略将它们的输出结果聚合起来，得到最终的预测结果。

反学习阶段 (Unlearning Phase)：

当收到一个删除数据点 du 的请求时：

1. 定位 (Locate)：首先，确定这个数据点 du 属于哪个分片 Dk 和哪个切片 Dk,r。

2. 回滚 (Rollback)：加载在训练阶段保存的模型状态，具体来说，是加载在第 r 个切片被引入之前保存的状态。

3. 重新训练 (Retrain)：从加载的状态开始，继续执行增量训练过程。但在处理第 r 个切片时，使用剔除了数据点 du 的数据。

4. 完成 (Complete)：只有包含 du 的这一个模型 Mk 被重新训练，其他所有模型完全不受影响。

优化策略

作者提出了如何更智能地进行分片以最小化未来的unlearning成本，称为分布感知的智能分片 (Distribution-Aware Sharding)

我们定义：

• 数据集 D
• 一个常数阈值 C

流程:

1. 排序: 根据每个数据点 du 被请求删除的概率 p(u)，对整个数据集进行升序排序（概率最低的在前）。

2. 初始化: 创建第一个空的分片 D0。

3. 循环分配: 遍历排序后的数据集：

   • 从数据集中取出当前删除概率最低的数据点 du。
   • 将 du 添加到当前的分片 Di 中。

4. 检查阈值: 每次添加后，计算当前分片 Di 的“预期被删除次数” E(χi)。

   • 如果 E(χi) ≥ C:
     • 将刚刚添加的数据点 du 从当前分片 Di 中移出。
     • 创建一个新的空分片 Di+1。
     • 将数据点 du 添加到这个新的分片 Di+1 中。

5. 结束: 重复步骤3和4，直到所有数据点都被分配到某个分片中。

缺点

比较早期的模型，方法比较朴素。

模型参数量大，重新训练就很耗时。

在当时，作者认为遗忘有以下难度。