引用

Ginart A, Guan M Y, Valiant G, et al. Making ai forget you: Data deletion in machine learning[J].

摘要

最近激烈的讨论集中在如何让个人控制他们的数据何时可以使用和不能使用。在本文中，我们提出了一个框架，研究当不再允许部署从特定用户数据派生的模型时该怎么办。特别是，我们提出了从训练的机器学习模型中有效删除单个数据点的问题。对于许多标准 ML 模型，完全删除个人数据的唯一方法是在剩余数据上重新训练整个模型，这在计算上通常不切实际。我们研究了在 ML 中实现高效数据删除的算法原理。对于 k 均值聚类的特定设置，我们提出了两种可证明的高效删除算法，它们在 6 个数据集的删除效率平均提高了 100× 以上，同时生成了与规范 k-means++基线具有可比统计质量的聚类。

1. 介绍

个人可以随时决定他们不希望其个人数据被特定实体用于特定目的，继续使用直接训练已删除数据的人工智能系统可能被视为非法。此外，所谓的模型反转攻击已经证明了对手从训练的 ML 模型中提取用户信息的能力。

删除一个样本点后，满足请求删除的一种朴素方法是根据剩余 n-1 样本重新训练模型，然而成本可能相当高，因此，我们认为高效的数据删除是机器学习模型和 AI 系统的基本数据管理操作，就像关系数据库或其他经典数据结构一样。

本文的关键组成部分包括引入删除高效学习，我们将数据删除作为一个在线问题，从中产生了最佳删除效率的概念。我们使用 k 均值聚类问题对删除有效学习进行了案例研究。我们提出了两种删除效率算法，它们(在某些制度下)实现了最佳删除效率。根据经验，在六个数据集上，我们的方法相对于规范 Lloyd 算法，在摊销运行时中平均实现了超过 100× 加速。同时，提出的删除效率算法在聚类质量的三个不同统计指标上的表现与规范算法相当。最后，我们综合了一个算法工具箱，用于设计删除高效的学习系统。我们将我们的工作总结为三个贡献：(1)我们在机器学习的背景下正式化了有效数据删除的问题和概念。(2)提出两种不同的 k 均值聚类删除效率解，具有理论保证和较强的实证结果。(3)从我们的理论和实验中，我们综合了设计删除高效学习系统的四个一般工程原理。

2.相关工作

确定性删除更新：如简介中所述，已知某些规范学习算法存在有效的删除操作，包括线性模型和某些类型的懒惰学习技术。

数据删除和数据隐私：在机器学习中保护数据的相关想法不会导致有效的数据删除，而是试图使数据私有或不可识别。支持高效删除的算法不必是私有的，私有的算法不必支持高效删除。数据删除的挑战只有在存在计算限制的情况下才会出现，另一方面，隐私也带来了统计挑战。

3.问题阐述

本节描述设置，并在机器学习算法和模型的上下文中定义数据删除和删除效率的概念，最后总结了了用于设计删除高效学习算法的高级原则。

我们用 D={x1,...，xn}表示数据集，由 n 个数据点组成的集合，每个数据点 xi∈Rd;为简单起见，我们通常将 D 表示为 n×d 实值矩阵。设 A 表示将数据集映射到假设空间 H 中的模型的算法。算法 A 可以对任何大小的数据集进行操作。

定义 3.1.数据删除操作：我们为学习算法 A，RA(D，A(D)，i)定义了一个数据删除操作，它将数据集 D，模型 A(D)和索引 i∈{1,...,n}映射到 H 中的某个模型。如果对于所有 D 和 i，随机变量 A(D−i)和 RA(D，A(D)，i)在分布上相等，则这样的运算是数据删除运算，A(D−i)=dRA(D，A(D)，i)。在这里，我们专注于确切的数据删除：从模型中删除训练点后，模型应该就像从一开始就没有看到过这个训练点一样。

计算挑战 每个学习算法 A 都支持简单的数据删除操作，对应于在删除指定的数据点后简单地对新数据集进行重新训练，即在数据集 D−i 上运行算法 A。正因此，数据删除的挑战是计算性的：1)我们能否设计一个学习算法 A，并支持数据结构，以便实现计算高效的数据删除操作？2)对于什么算法 A，是否存在数据删除操作，该操作在数据集大小中的时间亚线性运行，或者至少在计算原始模型 A(D)所需的时间内以亚线性运行？3)对 A(D)中包含的元数据的内存占用的限制如何影响数据删除算法的效率？

数据删除作为在线问题 给定 n 个数据点的数据集、特定的训练算法 A 及其相应的删除操作 RA，可以考虑 m≤n 不同索引的流，i1，i2,...,im∈{1,...,n}，对应于要删除的数据点序列。然后，在线任务是设计一个数据删除操作，该操作一次给定一个索引ij，并且必须在给定索引 ij 时输出 A(D−{i1,...,ij})。目标是最大限度地减少摊销计算时间。

在线数据删除中，会出现摊销运行时的简单下限。所有(顺序)学习算法 A 在自然假设（A 必须至少处理一次每个数据点）的情况下，要在 Ω(n)时间内运行。此外，在最好的情况下，A 带有常量时间删除操作(或删除预言机)。

我们将实现此下限的算法称为删除效率。对于许多基本学习范式来说，获得严格的上限和下限是一个悬而未决的问题。在本文中，我们对 k 均值聚类进行了一个案例研究，表明我们可以在不牺牲统计性能的情况下实现删除效率。

3.1 删除高效机器学习系统的一般原则

线性 使用线性计算允许进行简单的后处理，以撤消单个数据点对一组参数的影响。一般来说，Sherman-Morrison-Woodbury 矩阵恒等式和矩阵因式分解技术可用于导出用于更新线性模型的快速而明确的公式。

懒惰 懒惰学习方法将计算延迟到推理时间，导致琐碎的删除。惰性学习最简单的例子之一是 k-最近邻，在删除时从数据集中删除一个点会直接转换为推理时的更新模型。从某种意义上说，懒惰可以被解释为将计算从训练转移到推理。作为副作用，删除可以大大简化。

模块化 在删除高效学习的上下文中，模块化是计算状态或模型参数对数据集特定划分的依赖性的限制。在这种模块化下，我们可以隔离需要重新计算的特定数据处理模块，以便考虑数据集的删除。模块化在数据的维度与数据集大小相比较小的制度中应该是最有效的，允许数据集的分区来捕获重要的结构和特征。

量化 许多模型都具有从数据集空间到模型空间的连续性-对数据集的微小更改应导致对模型(分布在)模型的微小更改。在统计和计算学习理论中，这个想法被称为不稳定。我们可以通过量化从数据集到模型的映射来利用稳定性。量化在参数数量与数据集大小相比较少的制度中最为有效。

4.删除高效集群

数据删除是机器学习的普遍挑战。由于其简单性，本文专注于 k-means 聚类作为案例研究。我们提出了两种算法用于删除高效 k 均值聚类。在 k 均值的上下文中，我们将输出质心视为我们有兴趣从中删除数据点的模型。我们总结了我们提出的算法和状态理论运行时复杂性以及统计性能保证。

4.1 量化 k 均值

我们提出了 Lloyd 算法的量化变体，作为 k 均值聚类的删除有效解，称为 Q-k 均值。通过量化每次迭代时的质心，算法的质心相对于高概率的删除是恒定的。在这种量化稳定性的概念下，可以支持有效的删除，因为大多数删除都可以解决，而无需从头开始重新计算质心。这里介绍该算法的精简版本(算法 1)。

Q-k-means 也遵循迭代协议，但与 Lloyd 算法有四个关键区别。首先，在更新分区之前，质心在每次迭代中都会被量化。量子化将每个点映射到均匀晶格的最近顶点。为了去偏置量化，我们对晶格应用随机相移。其次，在整个计算过程中的各个步骤中，我们将优化状态记忆到模型的元数据中，以便在删除时使用。第三，引入了一个平衡校正步骤，该步骤通过基于先前质心的动量项对当前质心进行平均来补偿 γ-不平衡的聚类。显式地，对于某些 γ∈(0，1)，如果|πκ|≤γn/k，则认为任何分区 πκ 都是 γ-不平衡的，我们可能认为 γ 是最小簇大小与平均簇大小的比率。第四，由于量化，迭代不再保证降低损失，因此，如果损失在任何迭代中增加，都会提前终止。

Q-k-means 中的删除很简单。通过从训练时保存的元数据，我们可以验证删除特定数据点是否会导致与训练期间实际计算的量化质心不同。如果是这种情况，我们必须从头开始重新训练以满足删除请求。否则，我们可以通过更新元数据以反映指定数据点的删除，但不必重新计算质心。Q-k-means 直接依赖于量化原理来实现预期的快速删除。Q-k-means 还利用线性原理来回收计算。由于质心计算在数据点中是线性的，因此很容易确定由于在删除时删除而导致的质心更新。

删除时间复杂度 Q-k-means 通过量化质心来支持删除，因此它们可以稳定地抵抗小的扰动。

定理 4.1. 设 D 是大小为 n 的[0，1]d 上的数据集。修复 Q-k-means 的参数 T、k、ε 和 γ。Q-k-means 预期在时间 O(m2d5/2/ε)内完成 m 次删除，其概率超过在量化阶段的随机性和 k-means++初始化。

理论统计性能 设L∗ 为特定问题实例的最佳损失。一般来说，实现最优解决方案是 NP-Hard。但我们可以用 k-means++近似它，从而实现 EL++≤(8logk+16)L∗。

推论 4.1.1. 设L是一个随机变量，表示 Q-k-means 在大小为 n 的特定问题实例上的损失。则 EL≤(8logk+16)L∗+ ε[(8logk+16)L∗]1/2+ndε2/4。

4.2分而治之k-Means

"分而治之"k-means (DC-k-means) 在高层次上，DCk-means 的工作原理是将数据集划分为小的子问题，将每个子问题作为独立的 k-means 实例求解，然后递归地合并结果。我们在这里提供了 DC-k-means 的伪代码。

DC-k-means 在高度为 h 的完美 w-ary 树上运行。原始数据集作为统一的多项式随机变量划分到树中的每个叶子中，其中数据点作为试验，留下作为结果。在每片叶子上，通过 k-means++求解一定数量的质心。将叶子合并到它们的父节点中时，构造一个新的数据集，该数据集由每个叶子的所有质心组成。然后，通过另一个 k-means++实例计算父级的新质心，为简单起见，我们在树中的所有子问题中固定 k。利用树层次结构来模块化计算对数据的依赖。在删除时，我们只需要从一个叶子到根重新计算子问题。此观察结果使我们能够支持快速删除操作。我们的方法与预先存在的分布式 k-means 算法是不同的(不仅因为它被修改为删除，而且还因为它在一般的根树上运行)。

类似于在 Q-k-means 中如何作为删除效率和统计性能之间进行权衡的旋钮，对于 DC-k-means，我们想象 w 也可以用作类似的旋钮。统计性能对树宽 w 的依赖性在理论上不如 Q-k-means 对的依赖性那么容易处理，但统计性能往往会随着 w 的增加而下降。

正如我们在实验中所展示的那样，深度-1 DC-k-means 证明了删除时间和统计性能之间在经验上令人信服的权衡。此算法还有其他各种潜在的扩展，例如在聚类质量沿树上传播时对质心进行加权，或探索更深树的统计性能。

删除时间复杂度 为了进行后续的渐近分析，对于 ρ∈(0，1)，可以考虑将树宽度 w 参数化为 w=Θ(nρ)，将 k 和 T 视为小常量。

命题 4.2 设 D 是大小为 n 的 Rd 上的数据集。修复 DC-k-means 的参数 T 和 k。设 w=Θ(nρ)和 ρ∈(0，1)然后，使用深度 1、w-ary 分而治之树，DC-k-means 在预期支持在时间 O(mmax{nρ，n1−ρ}d)内完成 m 次删除，其概率超过数据集分区中的随机性。

4.3 在线删除设置中的摊销运行时复杂性

推论4.2.1. 对于 ε=Θ(n −β ), 0<β<1，如果 α≤(1-β)/2,那么 Q-k-means 算法是 α-删除高效的。

推论4.2.2. 对于 w = Θ(n ρ ), 0 < ρ < 1, 深度 1 的 w-ary 分而治之树, 如果 α<1−max{1−ρ,ρ}，则 DC-k-means 在期望上是 α-删除高效的。

5 实验

本节将通过对算法的摊销运行时和在线删除请求模拟流的聚类质量进行基准测试，为算法提供概念验证。规范 Lloyd 算法作为基线，将这个基线简单地称为 k-means，并将我们提出的两种方法称为 Q-k-means 和 DC-k-means。

数据集 五个真实的公开数据集：Celltype，Covtype，MNIST，Postures，Botnet，以及由高斯混合模型制成的合成数据集。所有数据集都附带了真实值标签用来评估聚类方法的统计质量。

在线删除基准测试 我们模拟了 1000 个删除请求的流，这些请求是随机统一选择的，无需替换。算法在完整数据集上训练一次，然后运行其删除操作以满足流中的每个请求，从而在每个请求中生成一个中间模型。对于规范 k-means 基线，通过从头开始重新训练来满足删除。

协议 为了衡量统计绩效，我们使用三个衡量集群质量的指标进行评估。为了衡量删除效率，我们测量挂钟时间以完成我们的在线删除基准测试。我们对每个数据集上的每个方法运行五个重复，并在所有结果中包括标准偏差。

5.1 统计性能指标

为了评估我们算法的聚类性能，最明显的指标是 k-means 目标的优化损失。为了彻底验证提出的算法的统计性能，我们还包括两个规范聚类分析性能指标。轮廓系数：此系数测量一种相关性(介于-1 和+1 之间)，用于捕获每个聚类的密度以及不同聚类的分离程度。分数越高，表示聚类密度越大，分离程度越高。归一化互信息(NMI)：此数量测量分配的聚类与实况标签的一致性，分数越高，表示一致性越好。

5.2 结果

在表 1-表 3 中展示了 3 种算法在 6 个数据集中每个数据集上的统计聚类性能。表 1 展示了所提出的方法在 k-means++基线上的优化损失率。表 2 展示了 clusters 的轮廓系数。表 3 展示了 NMI。表 4 展示了每种方法的训练和删除的摊销总运行时间。总体而言，我们看到三种方法的统计聚类性能良好。

此外，我们发现两种提出的算法都产生了数量级的加速。正如理论分析所预期的那样，当维度相对于样本数量较低时，Q-k-means 提供更多的加速，而 DC-k-means 在维度上更一致。

特别要注意的是，MNIST 具有我们尝试的数据集中最高的 d/n 比率，其次是 Covtype，这两个数据集分别是 Q-k-means 提供最小加速的数据集。另一方面，对于固定 d ，DC-k-means 在 n 增加时提供持续增加的加速提升。此外，我们看到 Q-k-means 在其删除效率方面往往具有更高的方差，因为质心稳定性的随机性比数据集分区中的随机性具有更大的影响。我们注意到，1000 次删除量不到测试的每个数据集的 10%，并且在整个基准测试中统计性能几乎保持不变。图 1 将在线删除基准上的摊销运行时绘制为流中删除次数的函数。

6 讨论

目前，删除高效监督方法的主要选择是线性模型、支持向量机和非参数回归。虽然在这里的分析侧重于聚类的具体问题，但提出的四个设计原则，将作为删除高效学习算法的支柱。这些方法在其他监督学习技术中的具有潜在应用。

分段回归 分段(或分段)线性回归是规范回归模型的常见松弛。通过将 Q-k-means 与线性最小二乘回归相结合，应该可以支持分段回归的变体。

核回归 随机傅里叶特征风格的核回归可以很容易地修改，以支持大规模监督学习的高效删除。随机要素不依赖于数据，因此只有要素空间上的线性图层需要更新以进行删除。

决策树和随机森林 量化也是决策树的一种有前途的方法。通过量化或随机化决策树拆分标准，似乎可以支持有效的删除。此外，随机森林与装袋具有天然的亲和力，这自然可以用来强加模块化。

深度神经网络和随机梯度下降 一系列研究已经观察到神经网络训练对量化和修剪的鲁棒性。可以利用这些技术在 SGD 样式优化期间量化梯度更新，从而实现与 Q-k-means 中相关的参数稳定性概念。这将需要更大的批量大小和更少的梯度步骤才能很好地扩展。近似删除方法也有可能克服大型神经模型精确删除方法的缺点。

7 结论

在这项工作中，我们提出了大规模学习系统的删除效率概念，提出了可证明的删除效率无监督聚类算法，并确定了可能使其他学习算法和范式的删除效率成为可能的潜在算法原理。我们只是触及了理解学习系统中删除效率的表面。在整个过程中，我们做了一些简化的假设，使得我们的系统中只有一个模型和一个数据库。我们还假设基于用户的删除请求仅对应于单个数据点。了解具有许多模型和许多数据库的系统以及复杂的用户到数据关系中的删除效率是未来工作的重要方向。

致谢

本文由南京大学软件学院 2021 级硕士于亚东翻译转述，刘子夕审核。