引用
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 矩阵恒等式和矩阵因式分解技能可用于导出用于更新线性模型的快速而明确的公式。
模块化 在删除高效学习的高下文中，模块化是打算状态或模型参数对数据集特定划分的依赖性的限定。在这种模块化下，我们可以隔离须要重新打算的特天命据处理模块，以便考虑数据集的删除。模块化在数据的维度与数据集大小比较较小的制度中该当是最有效的，许可数据集的分区来捕获主要的构造和特色。
量化 许多模型都具有从数据集空间到模型空间的连续性-对数据集的眇小变动应导致对模型(分布在)模型的眇小变动。在统计和打算学习理论中，这个想法被称为不稳定。我们可以通过量化从数据集到模型的映射来利用稳定性。量化在参数数量与数据集大小比较较少的制度中最为有效。
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 级硕士于亚东翻译转述，刘子夕审核。