删除机器学习模型中的认证数据

引用：

Chuan Guo,Tom Goldstein,Awni Hannun,et al. Certified Data Removal from Machine Learning Models[J],2020

摘要

良好的数据管理需要根据数据所有者的请求删除数据。这就提出了一个问题，即一个隐含存储训练数据信息的受过训练的机器学习模型，是否以及如何会受到这种移除请求的影响。是否有可能从机器学习模型中“移除”数据 ϵ。我们为线性分类器开发了一个认证删除机制，并以经验研究学习设置，在其中该机制是实际的。

1. 介绍

机器学习模型通常在第三方数据上进行训练，当一方要求将其数据从此类在线平台上移除时，就会产生这样一个问题，即此类请求将如何影响在移除之前受训的模型。当模型受到数据中毒攻击的负面影响时，也会出现类似的问题。因此在不从头开始重新训练模型的情况下，是否可能从模型中“删除”数据 ϵ

我们在一个称为认证移除的框架中研究这个问题，理论上保证对手不能提取从模型中移除的训练数据的信息。受差异隐私(Dwork,2011)的启发，认证删除边界模型之间的最大分歧训练的数据集与一些实例删除和模型训练的数据集，从不包含那些实例。这保证了成员资格推理攻击对从模型中移除的数据不成功。强调认证移除是一个非常强的移除概念;在实际应用中，较少约束的概念同样可以满足数据所有者移除的期望

2. 除认证

D 是一个固定的训练数据集，A 是一个(随机)学习算法，它训练一个模型输出 h∈H，即 A:D→H。我们想从 A 的输出中移除一个训练样本 x∈D。

为此，我们定义了一个数据删除机制 M 应用于 A (D)，目的是消除 x 的影响。如果移除成功，m 的输出应该很难与应用的 Dx 的输出区分开来。对于>0，使用删除机制执行-认证的 removal(-CR)来学习算法 A，如果 ∀T 三角形数据集 H,D 三角形 X, X∈D

还定义了一个更宽松的概念(ϵ, δ)-如果 ∀T ⊆ H,D ⊆ X,x ∈ D 的删除:

概念上，δ 上界方程 1 中最大散度界失败的概率。

具有 ϵ = 0 的琐碎的认证删除机制 M 完全忽略了 A(D)，直接评估 A(Dx)，也就是说，它设置 M(A(D),D,x) =A(Dx)。这种删除机制对许多模型来说是不切实际的，因为它可能需要在每次删除训练样本时重新训练模型。需要寻找去除成本为 O(n)或更少的机制 M，它具有较小的常数，其中 n = |D|是训练集大小。

参数不可分辨性的不足。完全删除另一个替换选择是通过断言的输出，M (A (D), D, x)是足够接近的(D x)。考虑线性回归量训练数据集 D = {(e_1, 1), (e_2, 2),…,(e_d, d)}，其中 e_i 是 R_d 的标准基向量。用 0 初始化的回归向量，或者具有权重衰减惩罚的回归向量，将在 w_i (e_i, i)上设置一个非零权重，在 d 中包含，在 w_i 上设置一个零权重。在这种情况下，留下 w_i 非零仍然显示(e_i, i)出现在训练中。

不同隐私的关系。我们的认证移除方法与不同的隐私有关，但有重要的区别。差异隐私声明：

其中 D 和 D’仅在一个样本中不同。由于 D 和 D x 仅在一个样本中不同，因此可以直观地看出 A 的差异隐私是认证移除的充分条件。

虽然差别隐私是一个充分条件，但它不是认证移除的必要条件。因此，我们将认证删除的研究视为分析效用和删除效率之间的权衡，从零开始的再培训和不同的隐私在光谱的两端，而删除中间。

3. 删除机制

3.1 线性分类器

用 D = {(x_1, y_1)，…，(x_n, y_n)}分为 n 个样本的训练集，∀i: x_i∈R^d，对应的目标为 y_i。我们假设学习算法 A 试图最小化线性模型的正则化经验风险

认证移除的方法如下。首先定义一个移除机制，给定要移除的训练数据点(x, y)，生成一个近似等于 L(w;D (x, y))的唯一极小值的模型 w−。由这种机制产生的模型可能仍然包含关于(x, y)的信息，特别是如果梯度 ∇L(w−;D (x, y))非零，它将揭示关于删除的数据点的信息。为了隐藏这一信息，我们在训练时对模型参数施加足够大的随机扰动。

去除机制。在不丧失一般性的前提下，我们假设我们的目标是移除最后一个训练样本(x_n, y_n)。具体地说，定义了一种有效的去除机制，该机制可以在 D’= D x_n, y_n)的情况下近似地最小化 L(w;D’)。首先，表示样本(xn, yn)处的损失梯度 ∆= λw∗ ∇' ((w∗)>x_n, y_n)和 Hw∗=∇2L(w∗;D’)处的 Hessian。我们考虑 Newton 更新删除机制 M:

这是应用于被移除点(x_n, y_n)的梯度影响的一步牛顿更新。更新

也被称为训练点(x_n, y_n)对参数向量 w∗ 的影响函数。

这个牛顿更新的计算成本是由形成和反 Hessian 矩阵的成本决定的。随后的 Hessian 反转使得移除时的移除机制为 O(d3);反演可以利用高效的线性代数库和 gpu。

为了限制这种去除机制的近似误差，我们观察到:∇L(w−;D’)只有当 w− 是 L(·;D’)的唯一极小值时才为零。我们还观察到，梯度残差范数||∇L(w−;D’)||反映了 L(·;D’)最小值在 w− 近似下的误差。我们推导了去除机制的梯度剩余范数的上界(参见方程 3)

定理 1。假设 ∀(x_i, y_i)∈D,w∈R^d: ||∇' (w>x_i, y_i)||≤C.同时假设 y’’是 γ-Lipschitz, ||x_i||≤1 对于所有(x_i, y_i)∈D，则:

损失扰动。通过定理 1 获得小的梯度范数||∇L(w−;D’)||不能保证经过认证的去除。特别地，梯度残差的方向可能泄露关于被“移除”的训练样本的信息。为了隐藏这一信息，我们在训练时使用了的损失扰动技术。它通过一个随机的线性项来扰乱经验风险:

让 A(D’)是 Lb(·;D’)的一个精确的最小值 1，并且让~ A(D’)是 Lb(·;D’)的一个近似的最小值。具体地说，让~ w 是由 a 产生的一个近似解决方案。这意味着梯度剩余是:

定理 2。假设 b 来自一个具有密度函数 p(·)的分布，对于任意 b1,b2∈R^d 满足||b1−b2||≤ϵ’，我们有:

实现认证的去除。将定理 2 与定理 1 中的梯度剩余范数界 ϵ’结合，可以用定理 2 证明去除。安全参数 ϵ 和 δ 取决于 b 采样时的分布。我们保证(ϵ，δ)认证去除以下两个合适的分布 p(b)

定理 3。假设 A 是返回损失 L_b(w;D)的唯一最优值的学习算法，M 是牛顿更新删除机制(参见公式 3)。假设 k∇L(w−;D’)k2≤ϵ ‘，对于某个可计算界 ϵ’> 0。我们对 M 有以下保证:

1.如果 b 来自密度为

那么对于 A M 等于 ϵ-CR;

2.如果

那么 M 等于(ϵ，δ)-CR 为 A，

3.2 实际考虑

最小二乘和逻辑回归。上述经过认证的移除机制可用于最小二乘和逻辑回归，这在机器学习的现实应用中是普遍存在的。

逻辑回归假设 ∀i: y_i∈{−1， 1}，并使用损失函数

其中 σ(·)表示 sigmoid 函数，

损失梯度和 Hessian 由:

梯度范数的数据依赖界。定理 1 中的界包含一个常数因子 1/λ^2，对于小数据集的实际应用可能太过松散。幸运的是，我们可以在梯度残差上推导出一个数据相关的边界，该边界可以有效地计算，并且在实践中更加严格。回想一下，L(·;D’)的 Hessian 的形式是:

由方程 4 得到

已知二阶导数 y’’的 Lipschitz 常数 l’’，我们可以这样约束它

多个删除。去除 T 后的最坏情况梯度残差范数可以在 T 中线性缩放。我们可以用 T 的归纳法来证明这一点。假设去除 T≥1 次后的梯度残差为 uT ||uT||≤t0，其中 ϵ’为一次去除的梯度残差范数界。设 D^(T)为去掉 T 个数据点的训练数据集。考虑修正的损失函数 L^(T) b(w;D^(T)) = Lb(w;D^(T))−u> Tw，并设 wt 为 T 去除后的近似解。那么 wT 是 L^(T) b(w;D^(T))的一个精确解，因此，上述定理可以应用于 L(T) b(w;D^(T))，证明牛顿更新近似 wT 1 有梯度残差 u’，范数最大为 ϵ’。然后:

因此，去除 T 1 后 Lb(w;D(T))的梯度残差为 u_T 1:= uT u’，其范数最多为(T 1) ϵ’乘以三角形不等式。

批量删除。在某些场景中，数据删除可能不需要在数据所有者请求删除之后立即进行。这可能允许批量移除多个训练样本一次移除，以提高效率。Newton 更新删除机制自然支持这个扩展。在不丧失一般性的前提下，假设要移除的训练数据批次为 Dm= {(x*(n−m 1), y*(n−m 1))，…(x_n,y_n)}。定义:

批量移除更新为:

我们得到了与定理 1 和推论 1 相似的分批移除梯度残差范数的边界。

定理 4。在定理 1 相同的正则性条件下，我们得到:

定理 4 中的梯度剩余界是随着移除的次数进行二次缩放的，而不是在逐个移除示例时进行线性缩放。误差的增加是由于对 Hessian 的更粗略的近似，也就是说，在当前的解决方案中只计算一次 Hessian，而不是对每个删除的数据计算一次。

减少在线计算。牛顿更新要求形成和反转黑森。虽然对于较小的 d，反演的 O(d3)成本相对有限，并且可以在 gpu 上高效地进行反演，但形成 Hessian 的成本是 O(d2n)，这对于大数据集可能是有问题的。

当计算数据依赖界时，可以使用类似的技术来计算术语

它涉及(n−1)× d 数据矩阵 X 与 d 维向量的乘积。通过离线形成 X 的奇异值分解，并通过求解 d × d 矩阵上的特征分解问题，应用在线降日期来形成 X− 的奇异值分解，我们可以将该计算的在线分量减少到 O(d3)。结果表明，该方法减少了

的计算量，仅涉及 d × d 矩阵和 d 维向量，这使得在线计算成本与 n 无关。

伪代码。我们提供了用于训练启用删除的模型和用于(ϵ，δ)-CR 牛顿更新机制。在训练过程中(算法 1)，我们通过抽样一个高斯噪声向量 b，在训练损失中加入一个随机线性项。根据定理 3，σ 的选择决定了“去除预算”:可以产生的最大梯度剩余范数为 σϵ/c。在优化训练损耗时，任何对强凸损耗函数具有收敛保证的优化器都可以在算法 1 中找到最小值。我们在实验中使用了 L-BFGS，因为它是我们尝试过的最有效的优化器。

在移除过程中(算法 2 中的第 19 行)，我们应用批量 Newton 更新(等式 6)，并使用推论 2(算法 2 中的第 15 行)计算梯度残差范数边界。变量 β 在所有移除过程中累积梯度残差范数。如果预先确定的预算 σϵ/c，我们使用算法 1 在剩余的数据点上从头开始训练一个新的删除启用模型。

3.3 非线性模型

深度学习模型通常将线性模型应用于网络在 ImageNet 等公共数据集上预训练后提取的特征的视觉任务，或从公共文本语料库的语言模型训练用于自然语言任务。在这样的设置中，我们只需要担心从应用到特征提取器输出的线性模型中删除数据。

当特征提取器也对私有数据进行训练时，我们可以对线性模型使用我们的认证去除机制，该模型应用于差分私有特征提取网络的输出。

定理 5。假设 Φ 是一个随机学习算法，它是(ϵDP， δDP)-差异私有，和 Φ 的输出被用于线性模型通过最小化 Lb 和使用去除机制，保证(ϵCR,δCR)认证的去除。然后整个程序保证(ϵDP ϵCR,δDP δCR)认证的删除。

这种方法相对于以一种差异私有的方式训练整个网络的优点是，线性模型可以使用更小的扰动来训练，这可能会大大提高最终模型的准确性。

4. 实验

4.1 线性逻辑回归

我们首先在 MNIST 数字分类数据集上进行实验。为简单起见，我们限制在区分数字 3 和 8 的二进制分类问题上，并使用算法 1 训练正则化逻辑回归器。

λ 和 σ 的影响。培训 removal-enabled 模型使用算法 1 需要选择两个 hyperparameters: L2-regularization 参数 λ,和标准差 σ,取样扰动向量 b。图 1 显示的影响 λ 和 σ 之前删除测试准确性和预期数量的支持。将支撑移除数固定在 100(中间地块)时，σ 值与 ϵ(参看算法 2 的第 16 行)，因此更高 ϵ 结果 σ 较小，精度提高。增加 λ 可以在重新训练之前进行更多的移除，因为它减少了梯度残差范数，但是非常高的 λ 值会对测试精度产生负面影响，因为正则化项占了最大的损失。

图 1. MNIST 的线性逻辑回归。梯度残差范数(在对数尺度上)作为移除数量的函数

梯度剩余范数界限的严密性。在算法 2 中，我们使用推论 1 和推论 2 中的数据依赖界来计算去除误差的每数据或每批估计，而不是定理 1 和定理 4 中的最坏情况界。图 1 显示了不同边界的值作为删除点数量的函数。考虑两种移除场景:单点移除和批量移除，批大小为 m = 10。我们观察到三种现象:(1)最坏情况边界(浅蓝色和浅绿色)比数据依赖边界(深蓝和深绿色)高几个数量级，这意味着使用数据依赖边界时，支持的移除数要高几个数量级。(2)梯度残差范数边界的累加和在单个和批量移除数据相关边界上近似为线性。(3)依赖于数据的范数边界与梯度残差范数(虚线)的真值之间存在较大的差距，这表明我们的去除机制的实用性可以通过更严格的分析进一步提高。

梯度残差规范与移除难度。依赖于数据的界由更新

的范数控制，该范数测量移走点对参数的影响，并且根据被移走的训练样本而变化很大。图 3 显示了

的 10 个最大和最小值对应的训练样本。这些样本表明，移除异常值更难，因为模型倾向于记住它们的细节，它们对模型的影响很容易与其他样本区分开来。

4.2 非线性 Logistic 回归使用公共，预先训练的特征提取器

我们考虑一种常见的场景，即特征提取器根据公共数据进行训练，而线性分类器使用非公共数据对这些特征进行训练。我们研究了两个任务:(1)LSUN 数据集上的场景分类和(2)斯坦福情感树库数据集上的情感分类。我们将 LSUN 数据集细分为每类 100K 个图像。

对于 LSUN，我们使用 ResNeXt-101 模型提取特征，对 1B 张 Instagram 图片进行训练，并在 ImageNet 上进行微调。对于 SST，我们使用预训练的 RoBERTa 语言模型提取特征。在移除时，我们使用算法 2 与 ϵ= 1，δ= 1e-4。

结果 LSUN。我们将 10 路 LSUN 分类任务缩减为 10 个单对全的任务，并对反例进行子采样，以确保在所有二元分类问题中正类和负类是平衡的。由于训练样本并不总是需要从所有 10 个分类器中删除，所以子采样的好处是删除。图 3(左)显示了测试准确性和 LSUN 上预期移除数量之间的关系。(λ， σ)的值显示在每个点旁边，最左边的点对应于训练一个不支持移除的规则模型。该模型在需要重新培训之前支持超过 10,000 次移除，但代价是准确性略有下降(从 88.6%降至 83.3%)。

图 2. MNIST 训练数字按范数排序

图 3. 线性模型训练公共特征提取器

风场。SST 是一种情感分类数据集，通常用于基准语言模型。在预测电影评论是否正面的二元分类任务中，我们使用了 SST。图 3(右)显示了准确性和支持的删除数量之间的权衡。常规模型(最左边的点)获得了 89.0%的测试精度，这与竞争性先前工作的性能相匹配。与之前一样，在测试精度的小损失的情况下支持大量的移除;去除的计算成本比重新训练模型的计算成本低 870 倍。

4.3 使用差分私有特征提取器的非线性 Logistic 回归

当公共数据无法用于训练特征提取器时，可以在私有数据上训练差分私有特征提取器，并应用定理 5 从最终(启用删除)线性层中移除数据。与使用的方法训练整个模型相比，这种方法一个主要的优势是最终的线性层可以部分纠正私有特征提取器产生的噪声特征。

我们在街景房号数字分类数据集上对该方法进行了评估。为了公平的比较，我们固定 δ = 1e-4 和训练(ϵDP/10，δ)-private 的 CNNs 的范围内的值 ϵDP。由联盟约束的团体隐私，结果模型支持到那时(ϵDP,δ)-CR 删除。

为了度量定理 5 用于认证数据删除的有效性，我们还培训了一个(ϵDP/10,δ/10)-differentially 私有 CNN，并从其倒数第二线性中提取特征。我们在算法 1 中使用这些特征训练 10 个单对全分类器，总失效概率最多为 9δ/10。与 LSUN 上的实验类似，我们在每个二进制分类器中对负面示例进行子采样，以加快删除速度。对 ϵCR≈ϵDP/10，从而达到(ϵ， δ)-CR 与 ϵ= ϵDP ϵCR≈ϵDP ϵDP/10。

图 5 显示了测试准确性和 ϵ 完全私有和 Newton 更新删除方法。对于较小的值或 ϵ，训练私有特征提取器(蓝色)和使用算法 1 训练线性层比训练完全差分私有模型(橙色)获得更高的测试精度。特别是在 ϵ≈0.1，全差异私有基线的准确率仅为 22.7%，而我们的方法获得了 71.2%的测试精度。从 private 提取器上训练的线性模型中移除只需要 0.27 秒，相比之下，当从零开始重新训练 CNN 时需要超过 1.5 小时。

5. 总结

我们研究了一种从机器学习模型中快速“移除”数据的机制，直到一种不同的私有保证:移除后的模型与从一开始就没有看到被移除数据的模型无法区分。在未来的工作中至少还有四个挑战。(1) Newton 更新移除机制需要反求 Hessian 矩阵，这可能是有问题的。(2)不支持去除非凸损失模型。(3)我们的数据依赖界与真正的梯度残差范数之间存在较大的差距。(4)有些应用可能需要开发替代的、约束较少的数据删除概念。

致谢

本文由南京大学软件学院 2021 级硕士冯翔翻译转述，尹伊宁审核。