Cryptanalytic Extraction of Neural Network Models

type

status

date

slug

summary

摘要：

我们认为模型提取的机器学习问题实际上是一个变相的密码分析问题，应该这样研究。 Given oracle access to a neural network 用了他的能力，只有加密和解密的输入和输出能力。给定神经网络的能力，我们引入了一种差分攻击，可以有效地窃取远程模型的参数，最高可达浮点精度。我们的攻击依赖于 ReLU 神经网络是分段线性函数这一事实，因此在关键点的查询会揭示有关模型参数的信息。我们评估了对多个神经网络模型的攻击，并提取了比之前的工作精确 220 倍且需要的查询量减少 100 倍的模型。例如，我们提取一个在 MNIST 数字识别任务上训练的 100,000 个参数神经网络，在一小时内进行 221.5 次查询，这样提取的模型在所有输入上都与预言机一致，最坏情况误差为 2−25，或者在 218.5 个查询中包含 4,000 个参数的模型，最坏情况误差为 2−40.4。

1 引言

过去十年，机器学习（尤其是深度学习）取得了重大进展。在本世纪初被认为完全不可能的任务到了年底几乎完全解决了。 AlphaGo [SHM+16] 在围棋比赛中击败了职业选手，2014 年的壮举被认为至少需要十年才能实现 [Lev14]。 ImageNet 识别基准的准确率从 2010 年的 73% 提高到 2019 年的 98.7%，错误率降低了 20 倍 [XHLL19]。神经网络可以生成逼真的高分辨率图像，人类发现这些图像与实际照片无法区分 [KLA+19]。神经网络在有限的环境中实现比人类医生更高的准确性，例如早期癌症检测 [EKN+17]。使用这些改进的图像识别神经网络。高精度神经网络通常出于至少两个原因而保密。首先，它们被视为竞争优势并被视为商业秘密[Wen90]；例如，早期的系统都不是开源的。其次，被视为提高安全性和隐私性以保持这些模型的秘密。通过完全白盒访问，可以轻松发起规避攻击并生成对抗性示例 [SZS+14，BCM+13]，例如针对滥用或垃圾邮件检测模型。此外，白盒访问允许模型反转攻击[FJR15]：给定经过训练以识别特定人脸的模型，可以重建特定人的可识别图像。同样，给定一个针对包含敏感数据（例如信用卡号）的文本进行训练的语言模型，白盒攻击者可以从训练模型中提取这些敏感数据 [CLE+19]。幸运的是，对于机器学习模型的提供者来说，重现神经网络通常很昂贵。造成这种成本的原因有三个：首先，大多数机器学习需要大量的训练数据，而收集这些数据的成本可能很高；其次，神经网络通常需要超参数调整，需要训练许多模型来确定最佳的最终模型配置；第三，在收集到的训练数据和正确配置的模型的情况下，即使执行最终的训练运行也是昂贵的所有上述原因，很明显（a）对手出于各种原因获取现有部署的神经网络的副本，并且（b）保护模型的秘密非常重要。在实践中，公司通过仅发布允许查询访问的 API 或发布设备上的模型来确保这些模型的保密性，但试图防篡改和混淆源以使其难以从设备中提取。上述薄弱的保护形式常常被认为是不够的。“安全推理”领域通过引入安全功能评估 (SFE) 的工具对此进行了改进，该工具允许相互不信任的合作方评估 f (x)，其中 f 由一方持有，x 由另一方持有。各种提案通常应用完全同态加密[Gen09，GBDL+16]、乱码电路[Yao86，RWT+18]或两者的组合[MLS+20]。根据标准 SFE 保证，安全推理“不会隐藏预测结果所揭示的[关于函数 f ]的信息”[MLS+20]。然而，这一系列工作通常隐含地假设预测的总泄漏很小，并且从其输出中恢复函数将很困难。总的来说，很明显，保护神经网络模型的保密性在实践和学术研究界都被认为很重要。这就引出了我们在本文中研究的问题：给定预言机（黑盒）对目标模型的访问权限，是否可以提取神经网络的相同副本？虽然这个问题并不新鲜 [TZJ+16,MSDH19,JCB+19,RK19]，但我们认为模型提取应该作为密码分析问题来研究为此，我们专注于在理想化环境中进行模型提取，其中机器学习模型作为可获取的oracle提供，但没有计时或其他辅助通道。此设置捕获公开的模糊模型、预测 API 和安全推理的设置。

1.1 模型提取作为密码分析问题

本文的主要观点是模型提取与密码学中一个经过充分研究的问题密切相关：分组密码的密码分析。非正式地，对称密钥加密算法是一个密钥函数 Ek : X → Y，它将输入（明文）x ∈ X 映射到输出（密文） y ∈ Y。我们期望所有实际重要的密码至少具有抵抗力，自适应选择明文攻击下的密钥恢复，即给定一些有限数量的（自适应选择的）明文/密文对 {(xi, yi)} 加密算法被设计成使得密钥 k 不能被计算有限的对手提取。将此与机器学习进行对比。神经网络模型（非正式地）是一个参数化函数 fθ : X → Y，它将输入（例如图像）x ∈ X 映射到输出（例如标签）y ∈ Y。模型提取攻击自适应地查询神经网络以获得一组输入/输出，揭示有关权重 θ 的信息。神经网络的设计并不是为了抵御此类攻击。

因此，从适当的角度来看，执行模型提取攻击（在 Oracle 访问函数 fθ 的情况下学习权重 θ）与对非传统“加密”算法执行选择明文攻击类似。

鉴于密码学领域花了数十年的时间来设计能够抵御选择明文攻击的加密算法，如果神经网络（在其设计中甚至没有考虑此类攻击）不会受到攻击，那将是非常令人惊讶的。更糟糕的是，密码设计的主要目标是抵御此类攻击的稳健性。另一方面，机器学习模型主要设计为在某些基础任务上准确，这使得所选明文安全神经网络的设计成为更具挑战性的问题。

模型提取与标准密码分析之间存在三个区别，这使得模型提取变得非常重要且值得研究。首先，攻击成功的标准不同。虽然即使不学习密钥位，密码破解也可以成功——例如通过将算法与伪随机函数区分开来，但只有揭示（部分）实际模型参数 θ 的“完全破解”对于模型提取来说才有意义。

其次，早期对密钥密码的类比并不完美。神经网络通常采用高维输入（例如图像）并返回低维输出（例如单个概率）。与密钥多对一函数（例如 MAC）的密码分析进行类比几乎更合适。然而，MAC 的安全特性与机器学习模型的安全特性有很大不同，例如，第二原像在神经网络中是预期的，而不是回避的。

最后，实践中最大的区别是机器学习模型处理定点或浮点实数而不是有限域算术。因此，考虑到无限精确的浮点数学，我们的攻击有许多组件将被大大简化，但考虑到现代机器学习的现实，需要更复杂的攻击技术。

1.2 Our Results

我们引入了一种差分攻击，它可以有效地执行功能等效的神经网络模型提取攻击。我们的攻击跟踪神经网络对几个条目不同的示例对的评估，并使用它来逐个恢复神经网络的层（类似于分组密码的轮次）。为了评估我们攻击的有效性，我们形式化了先前工作 [JCB+19] 中引入的保真度定义，并量化了模型提取攻击成功的程度：-

定义 1. 两个模型 f 和 g 在 S 上是 ( , δ)-功能等价的，如果

表 1. 我们的提取攻击的精度比之前的工作精确几个数量级，并且对于更深的神经网络来说查询效率更高几个数量级。表示为 a-b-c 的模型是全连接神经网络，输入维度为 a、一个包含 b 个神经元的隐藏层和 c 个输出；正式定义参见第 1 节。 2. 标有 † 的条目在十次尝试后仍无法恢复网络。

表 1 报告了我们在各种模型大小和架构上的差分攻击的结果，报告了集合（模型的输入空间）上的 (ε, δ) 函数等价性，以及直接测量 max |θ − θˆ|，直接测量实际模型权重 θ 和提取的权重 θˆ 之间的误差（如第 6.2 节所述）

本文的其余部分结构如下。我们介绍了 Sect. 中使用的符号、威胁模型以及攻击者目标和假设。 2. 在教派中。在第 4 章中，我们引入了一种理想化的攻击，假设无限精度算术，提取 (0, 0) 功能等效的神经网络。第 5 节开发了这种攻击的实例，该攻击在实践中使用有限精度算术产生 (ε, δ) 功能等效的攻击。

1.3 relate work

模型提取攻击分为两类[JCB+19]：任务精度提取和保真度提取。第一篇研究任务准确性提取的论文 [TZJ+16] 引入了窃取类似模型的技术，这些模型近似解决自然数据分布上的相同底层决策任务，但不一定与预言机的预测精确匹配。虽然该领域存在进一步的工作[CCG+18，KTP+19]，但我们转而关注保真度提取，其中对手的目标是在预言机模型的预测相对于地面事实不正确时忠实地再现预言机模型的预测。 [TZJ+16]再次研究了这个问题，并为完全线性模型的情况开发了（我们现在称之为）功能等效提取。

然后，这种攻击通过理论结果进行了扩展，定义并给出了一种对具有一层的神经网络执行功能等效提取的方法，假设预言机可以访问梯度[MSDH19]。随后通过应用有限差分来估计梯度，开发了这种在实践中有效的单层攻击的具体实现，处理浮点不精确性[JCB+19]。与此相关的并行工作也扩展了这些结果，重点关注更深层次的网络，但需要数千万到数亿的查询[RK19]；虽然理论结果扩展到深层网络，但实践中的实现仅提取前两层。我们的工作建立在所有这四个结果的基础上，开发了一种方法，该方法的准确度提高了 106 倍，所需的查询量减少了 103 倍，并且适用于更大的模型。

即使没有查询访问，也可以仅使用缓存侧通道 [BBJP19] 窃取模型，尽管保真度低于我们引入的攻击，精确度提高了 220 倍。其他攻击的目标是超参数提取，即提取有关模型的高级详细信息：通过什么方法进行训练、是否包含卷积或相关问题 [WG18]。还可以通过缓存侧通道窃取超参数[HDK+20]。

最近的工作研究了统计查询（SQ）模型[DGKP20]中具有随机权重的深度神经网络的可学习性，表明可学习性随着网络深度呈指数下降。这一系列工作并未解决非 SQ 模型中提取的密码难度——这正是本工作在实证环境中解决的问题。

虽然与我们的问题没有直接关系，但值得注意的是，我们并不是第一个将神经网络视为另一种类型的数学函数，无需任何机器学习的具体知识即可进行分析的人。沙米尔等人。 [SSRD19]通过考虑神经网络的抽象模型，解释了对抗性示例[SZS+14，BCM+13]的存在，这些示例捕获了对机器学习分类器的逃避攻击。

在许多地方，我们的攻击从密钥分组密码的密码分析中汲取灵感，最突出的是差分密码分析[BS91]。我们既不假设也不要求熟悉该领域，但知情的读者可能会喜欢某些相似之处。

2 Preliminaries

本文研究了神经网络作为函数 f : X → Y 的抽象。我们的结果独立于选择函数 f 的任何方法（例如随机梯度下降），并且独立于函数 f 的任何效用。因此，机器学习知识既不是期望的，也不是必要的。

2.1 Notation and Definitions

定义 2. k 深度神经网络 fθ(x) 是由 θ 参数化的函数，它从输入空间 X 获取输入并在输出空间 Y 中返回值。函数 f 由在线性层之间交替的函数序列组成fj 和非线性函数（按分量作用）σ：

我们专门研究和上的神经网络。（直到第 5 节，我们假设浮点数可以准确地表示 )

定义 3. 神经网络的第层由仿射变换给出。权重是一个 dj × dj−1 矩阵；偏差 b(j) ∈ Rdj 是 dj 维向量。

虽然将每个层 fj 表示为全矩阵乘积是层最通用的定义，称为全连接，但通常层具有更多结构。例如，在对图像进行操作的神经网络中通常使用（离散）卷积。卷积层将输入视为 n × m 矩阵，并将其与内核（例如 3 × 3 矩阵）进行卷积。然而，重要的是，始终可以将卷积表示为矩阵乘积。

定义 4. 神经元是接收输入并将其传递给激活函数 σ 的函数。总共有 N = Σk−1 j=1 dj 个神经元。

在本文中，我们专门研究 ReLU [NH10] 激活函数，由 σ(x) = max(x, 0) 给出。我们的结果是 ReLU 神经网络是分段线性函数这一事实的基本结果。

定义 5. 神经网络的架构捕获 f 的结构：(a) 层数，(b) 每层的维度，以及 (c) 对权重 A 施加的任何附加约束和偏差。

我们使用简写 a-b-c 神经网络来表示每个维度的大小；例如，10-20-5 神经网络的输入维度为 10，一层有 20 个神经元，输出维度为 5。此描述完全表征了全连接网络的 f 结构。在实践中，只有少数架构代表了大多数已部署的深度学习模型[ZL16]，并且开发新架构是研究中极其困难和活跃的领域[HZRS16，SIVA17，TL19]。

定义6. fθ 的参数θ 是在训练神经网络的过程中获得的权重和偏差的具体分配。

描述产生参数 θ 的训练过程超出了本文的范围：只要知道训练过程通常计算量很大并且训练是一个不确定的过程就足够了，因此多次训练同一模型将给出不同的参数组。

2.2 Adversarial Goals and Resources

模型提取攻击中有两方：返回 fθ(x) 的Oracle ，以及向Oracle 生成查询 x 的对手。

定义 7. 模型参数提取攻击接收预言机对参数化函数（在我们的例子中是 k 深度神经网络）和的架构的访问，并返回一组参数，目标是为与尽可能相似。

在本文中，我们使用 ^ 符号来表示提取的参数。例如，θˆ 指的是模型 θ 的提取权重。

提取的权重与先前工作研究过的Oracle模型之间存在一系列相似性定义[TZJ+16，JCB+19，KTP+19]；我们重点关注对抗性优势由定义 1 中的 (ε, δ) 功能等效提取定义的设置。与对称密钥原语的密码分析类似，模型提取攻击成功的程度由 (a)模型所选输入的数量，以及 (b) 所需的计算量。

假设。我们对预言机 O 和攻击者的知识做出了一些假设。（我们认为其中许多假设都不是根本性的，可以放宽。删除这些假设留待未来的工作。）

结构知识。我们需要了解神经网络的架构。

全域输入。我们从 X 提供任意输入。

完整的输出。我们直接从模型 f 接收输出，无需进一步处理（例如，仅返回最有可能的类别而没有分数）

精确的计算。 f 使用 64 位浮点算术指定和计算。

标量输出。不失一般性，我们要求输出维度为 1，即。

ReLU 激活。所有激活函数 (σ) 都是 ReLU。

这是我们工作的唯一基本假设。切换到任何非分段线性的激活将阻止我们的攻击。然而，如前所述，所有最先进的模型都专门使用 ReLU 激活函数（分段线性推广）[SIVA17、TL19]

3 Overview of the Differential Attack

图 1. 我们对 1 个深神经网络进行提取攻击的示意图。令 x 为一个输入，该输入恰好导致一个神经元的值为零。所有其他神经元的二阶微分都变为零，因为它们要么完全不活动，要么完全活动。因此，该微分的值等于在其临界点进入神经元的权重与离开该神经元的权重的乘积。

单层网络: 考虑一个单层神经网络，输入为 x，输出为 f(x)。网络的权重矩阵为 A。对于ReLU激活函数，有 f(x) = ReLU(Ax)。

二阶导数: 几乎所有情况下，f(x) 的二阶导数都为 0，除了某些神经元处于临界点的情况。假设第 j 个神经元 ηj 处于临界点，即 (Ax)_j = 0。此时，考虑沿着基向量 e_i 的二阶方向导数：

临界点: 当 ηj 处于临界点时，f(x) 在该点附近可以近似为一个线性函数。因此，二阶导数可以表示为：

其中，A_{ji} 是输入层第 i 个神经元到隐藏层第 j 个神经元的权重，A_j^{out} 是隐藏层第 j 个神经元到输出层的权重。对于单输出网络， A_j^{out} 即为连接第 j 个隐藏神经元到输出的权重。

权重恢复: 通过选择合适的输入 x，使不同的神经元 ηj 处于临界点，并计算相应的二阶方向导数，可以得到一组方程。通过求解这些方程，可以恢复权重矩阵 A。

核心原理：
ReLU 激活的神经网络是分段线性函数，几乎所有地方二阶导数都为零，除了某些“临界点”（即神经元的输出刚好等于零，处于正负区间的边界）。
在这些临界点上，二阶导数的值直接揭示了连接权重的一部分信息，甚至可以通过一些数学变换（可逆的）直接得到这些权重。

提取方法：
第一层权重恢复： 对于简单线性函数 f(x)=a⋅x+b，方向导数 ∂f/∂ei=ai （ai 是权重向量中的第 i 个元素）。因此，只需要针对标准基向量 ei 进行查询，就可以恢复权重。

对于深层网络，使用二阶方向导数 ∂2f/∂ei2 ，在选取合适输入 x（使某些神经元处于临界点）后，计算二阶导数即可逐步恢复每一层的权重矩阵。

逐层剥离：
恢复完第一层权重后，将第一层“剥离”掉，重复同样的操作来提取后续层的权重，直到恢复完整个网络。

鉴于预言机可以访问函数 fθ，我们可以通过沿任意方向的有限差分来估计 ∂fθ。对于由 f (x) = a · x + b 定义的简单线性函数，其方向导数满足，其中 ei 是基向量，ai 是向量 a 的第 i 个条目，可以直接恢复其通过查询这些精心选择的输入来确定权重。

对于深度神经网络，我们考虑二阶偏向导数,。ReLU 神经网络是分段线性函数，几乎在任何地方都具有，除非该函数在负区域和正区域之间的边界（即处于其临界点）有一些神经元 ηj 。我们证明，在 x 点评估的偏导数的值使得神经元 ηj 处于这样的临界点，实际上直接揭示了某些可逆变换 T 的权重 ——因此对手可以学习。通过沿着所有基向量 ei 和所有神经元 ηj 重复这种攻击，我们可以恢复完整的矩阵 A(1)。一旦我们提取了第一层的权重，我们就能够“剥离”该层并重新对神经网络的第二层进行攻击，重复到最后一层。我们的攻击有三个核心技术难点：

💡

恢复神经元符号。对于每个神经元 η，我们的攻击并不完全恢复，即的第 i 行，而是恢复标量倍数。虽然失去常数 α > 0 会使神经网络保持在相同的等价类中，但 α 的符号很重要，我们必须区分权重向量和 − 。我们构建了两种解决此问题的方法，但在一般情况下，我们需要指数工作（但查询数量是线性的）。

💡

控制隐藏层状态。在第一层，我们可以直接逐项计算导数，测量每个标准基向量的，以恢复。在网络的更深处，我们无法沿着标准的基向量移动。更糟糕的是，对于每个输入 x，平均有一半的神经元处于负区域，因此它们的输出同样为 0；当发生这种情况时，不可能沿着值为零的边缘学习权重。因此，我们需要开发技术来引发每个神经元的行为，以及将每行的部分恢复聚集在一起以形成完整恢复的技术。

💡

处理浮点不精确性。在实践中使用有限精度神经网络实施我们的攻击会带来额外的复杂性。为了估计二阶偏导数，我们需要查询仅有少量差异的输入，将提取的第一权重矩阵的精度降低到 20 位，或大约。这个的误差一开始并不大，但这个误差会影响我们恢复下一层的能力，随着我们在网络中的深入，它会成倍地累积。在第二层中，误差已经放大到，这可以完全阻止第三层的重建：我们对隐藏状态的预测视图与实际隐藏状态有很大不同，因此我们的攻击完全失败。我们通过两种方式解决这个问题。首先，我们引入数值稳定的方法，假设所有先前层都已被高精度提取。其次，我们开发了一种精度细化技术，该技术将神经网络的前第一个层的前缀提取到 n 位精度，并返回提取到 2n 位精度（最高浮点容差）的 j 深度模型）。

4 Idealized Differential Extraction Attack

我们现在介绍我们的 (0, 0) 功能等效模型提取攻击，它假设无限精度算术并恢复完全功能等效的模型。回想一下我们的攻击假设（第 2.2 节）；使用这些，我们从对 0 深度（第 4.1 节）和 1 深度（第 4.2 节）神经网络的两次“减少回合”攻击开始，然后继续进行收缩的 k 深度提取（第 4.1 节）。 4.3）和扩展（第 4.4 节）神经网络。第 5 节改进了这种理想化的攻击，使其能够以有限的精度发挥作用。

4.1 Zero-Deep Neural Network Extraction

零深度神经网络是线性函数。通过求解线性系统寻找与线性无关的解来提取。然而，让我们以不同的方式看待这个问题，以阐明我们对更深网络的攻击策略。考虑并行评估和，其中

如果，的第 i 个标准基向量（例如, ，则

这使我们能够直接读取的权重。换句话说，我们执行有限差分来估计的梯度，由给出。

4.2 One-Deep Neural Network Extraction

许多使深度神经网络提取复杂化的重要问题开始出现在 1 深度神经网络中。由于该函数不再完全线性，因此我们需要多个阶段才能完全恢复网络。为此，我们将逐层进行，提取第一层，然后使用 0 深度神经网络攻击来恢复第二层。

图 2.（左）1 深度神经网络的几何结构。三个实线对应于神经元的“临界超平面”。我们通过虚线上的二分搜索来识别每个神经元的一个临界点。（右）对于每个发现的临界点，我们计算沿轴 e1 和 e2 的二阶偏导数以计算超平面的角度。

对于本文的其余部分，拥有针对当前问题的两种不同的心理模型将很有用。首先是图 1 中所示的符号视图。该视图直接研究通过神经网络的信息流，表示为线性层和非线性变换的交替序列。这个视图有助于理解我们攻击的代数步骤。第二个是几何视图。由于神经网络在真实向量空间上运行，因此可以通过绘制景观的二维切片来可视化它们[MSDH19]。图 2（左）包含此类图的示例。每条黑色实线对应于神经元将符号从正变为负（反之亦然）而在空间中引起的梯度变化——现在忽略其余的线。神经网络提取的问题对应于恢复这些神经元引起的超平面的位置和角度：一般来说，对于输入维度，平面的维度为。

在图 2 中，这些临界点的位置与穿过平面绘制的黑色实线完全对应。观察到，因为我们将自己限制在 ReLU 神经网络，所以函数是分段线性的并且几乎在任何地方都可无限微。梯度在所有点上都有明确定义，除非存在处于其临界点的神经元。提取 A(1) 直到符号为止的行。从功能上讲，本小节中介绍的攻击之前已出现在文献 [MSDH19，JCB+19] 中。通过以不同的方式构建它，我们的攻击将扩展到更深的网络。

定义 8. 计算的前层（直到并包括但不包括）的函数表示为。特别是, 。

定义 9. 在应用非线性变换之前，第层的隐藏状态是函数的输出

层是之后第个隐藏状态的线性变换。

定义 10. 表示在处求值时神经元的输入（在应用之前）。表示神经元的层数。第一层从开始。

定义 11. 当时，神经元处于临界点。我们将此输入称为处于临界点这一事实的见证，用表示。如果，则 η 有效，否则无效。

假设，它导致神经元处于临界点（即，其值完全为零）。因为我们使用的是 ReLU 激活函数，所以这是该神经元当前处于“非活动”状态（即，对分类器的输出没有贡献）但将变为“活动”（即，对输出做出贡献）的点，如果它变得稍微积极。进一步假设只有这个神经元处于其临界点，并且对于所有其他神经元我们有对于常数。

考虑神经网络对示例对的两次并行执行。首先将 ei 定义为 X = RN 的标准基向量。通过查询两对输入 (x*, x* + ei) 和 (x*, x* − ei)，我们可以估计有限的差分。

考虑数量。因为 x* 引入了 ηj 的临界点，{α+, α−} 中的一个神经元将处于活动状态，而另一个将处于非活动状态。如果 A(1) 中没有两列共线，

则只要，我们保证神经网络中的所有其他神经元将保持与以前相同的状态 - 活动或不活动。因此，如果我们计算差值 |αi+ − αi−|，流入和流出所有其他神经元的梯度信息将被抵消，我们将只剩下沿着边缘从输入坐标 i 流向神经元 ηj 的梯度信息输出。具体来说，我们可以将 1 深度神经网络写为

因此或。然而，如果我们在新的基向量上重复上述过程，则或将保持。至关重要的是，沿坐标成立的两个关系中的任何一个都将与在坐标 k 上成立的相同关系。因此我们可以除掉来得到权重对的比率

计算的每一行直到标量，此外我们需要计算达到对应的缩放因子。因为我们知道在神经元上引入临界点，因此其值为零。观察到的大小并不重要。我们总是可以将常数推入权重矩阵并得到功能上等效的结果。然而，的符号确实很重要。

提取行符号

考虑任意神经元的单个输入。令，以便 h 的至少一个元素完全为零。如果我们假设 A(1) 是收缩的（第 4.4 节研究非收缩网络），那么我们可以找到任何向量 h 的原像 x。特别地，令 ei 为空间 Rd1 中的单位向量。然后我们可以计算原像 x+ 使得 f^1(x+) = h + ei 和原像 x− 使得 f^1(x−) = h − ei。

因为 xi 见证了神经元 ηi 处于其临界点，所以我们将得到 f (x+) = f (xi) 或 f (x−) = f (xi)。这些等式中的一个恰好为真，因为 σ(h−ei) = σ(h)，但当 hi = 0 时 σ(h+ei) = σ(h)。因此，如果第二个等式成立，那么我们知道我们的提取的第 i 行的猜测具有正确的符号。然而，如果第一个等式成立，那么我们提取的第 i 行的猜测具有不正确的符号，因此我们将其反转（以及偏差 b(1) i ）。我们对每个神经元 ηi 的临界点重复此过程，以完全恢复完整第一层的符号。

寻找关键点的存在

剩下的只是展示如何为第一层上的每个神经元找到见证人。我们在输入空间中选择一条随机线（图 2 左侧的虚线），并沿着它搜索偏导数中的非线性。任何非线性一定是由 ReLU 改变符号引起的，定位 ReLU 改变符号的特定位置将为我们提供一个临界点。我们通过二分搜索来做到这一点。

首先，我们取一个随机初始点以及一个大范围。我们对中的非线性进行二分搜索。也就是说，对于给定区间 [t0, t1]，如果，我们就知道该区间存在临界点。如果这些数量相等，我们不搜索区间，否则我们继续二分搜索。

提取第二层

一旦我们完全恢复了第一层权重，我们就可以“剥离”权重矩阵和偏差，剩下的就是提取最终的线性层，从而减少到 0 深度提取。

4.3 k-Deep Contractive Neural Networks

将上述攻击扩展到深度神经网络会遇到一些以前的工作无法有效解决的复杂问题；

由于不同层上的 ReLU 可能同时会出现临界点。

由于 1 深网络只有一层，因此所有 ReLU 都发生在该层上。因此，在搜索过程中找到的所有关键点都将对应于该层上的神经元。对于 k 深度网络来说，情况并非如此，如果我们想从提取第一层开始，我们将必须删除非第一层关键点。（而且，一般来说，为了提取第 j 层，我们必须删除非第 j 层的关键点。）

权重恢复过程需要完全控制输入

为了能够直接读取权重，我们在基向量 ei 上查询网络。对于深度网络来说，实现这一点并不总是可能的，我们必须考虑到我们可能只能在非正交方向上进行查询的事实。

恢复行符号需要计算任意隐藏状态的原像。

我们的行符号过程要求我们能够反转，这通常意味着我们需要开发一种方法来计算的原像。

4.3.1 Extracting Layer-1 Weights with Unknown Critical Point Layers

假设我们有一个函数，它为第一层中的每个神经元返回至少一个临界点（意味着），但从不返回任何更深层的临界点。我们认为上面的精确差分攻击仍然可以正确恢复深度神经网络的第一层。我们做出以下观察。设为无临界点的输入，即 . 将定义为函数，以便对于足够小的区域，我们有，即

这里，是 0-1 对角矩阵，当神经元不活动时，对角线上是 0，当神经元活动时，对角线上有是1：

其中是第一层的第个神经元。重要的是，只要足够接近，每个都是一个常数。虽然是未知的，但只要我们只进行梯度查询，它的值并不重要。到目前为止，这一观察结果符合分段线性的定义。

现在考虑一些输入，它恰好见证了神经元上的一个临界点。形式上，，但。然后

其中再次是矩阵，但现在不同的是，（并且只有）是的函数，返回具有两个值之一的对角矩阵，具体取决于的值。因此我们不能再将矩阵乘积折叠成一个矩阵，而只能得到

但是我们已经解决了1层深度的神经网络权重回复情况，也就相当于，并且通过与之前的方法一样去掉 我们就可以恢复 的比率。

寻找第一层的关键点

假设我们有一组输入，因此每个都是神经元的输入，而是未知的。根据收集者的论点（假设一致），对于，其中 N 是神经元总数，每个神经元至少有两个关键输入。

通常情况下，让作为第一层上的同一个神经元的关键输入，即。然后，执行权重恢复从每个关键输入开始的过程（通过有限差分）将产生正确的权重向量直至标量.

通常，的元素不会作为第一层的神经元关键输入。通常情况下让和成为更深层上任何神经元的关键输入。我们声称我们将能够检测到这些错误情况：提取算法的输出将显得是随机且不相关的。非正式地说，因为我们正在运行一种攻击，旨在提取实际上位于较后一层的神经元上的第一层神经元，所以当在和（或任何任意的）上运行时，该攻击不太可能偶然给出一致的结果.

形式上，令且。很有可能，。因此，当对执行提取过程时，我们在函数上进行计算，而在上进行提取则在上进行计算。因为，这将给出不一致的结果。

因此，我们的第一层权重A的恢复如下。

对于所有输入运行权重恢复过程以恢复每个关键超平面的单位长度法向量。我们应该期望只看到一次大量向量（因为它们是运行第层或更大神经元提取的结果），以及少量出现重复的向量（因为它们是在第一层）。给定第一层，我们可以将神经网络从深神经网络简化为深神经网络并重复攻击。然而，我们必须解决以下两个小节中讨论的两个困难.

4.3.2 Extracting Hidden Layer Weights with Unknown Critical Points

当提取第一层权重矩阵时，我们能够计算每个输入基向量的，从而使我们能够直接从偏导数中“读出”第一层权重的比率。然而，对于更深的层，精确控制隐藏层并仅更改一个坐标以执行有限差分是很重要的。让表示我们正在提取的当前层。首先对 dj + 1 个方向进行采样，并令

从这里我们可以构造一个方程组：设并求解向量 w，使得。和以前一样，我们运行权重恢复过程，假设每个特殊输入对应于正确层上的关键点。与不正确层上的神经元相对应的关键输入将给出可以丢弃的不相关错误。

Unifying partial solutions。上述算法忽略了一个重要问题。对于给定的关键点，从获得的隐藏向量可能有几个（平均一半）神经元是负向的，因此任何的神经元都为零。这使得仅从最小二乘法的一次应用中恢复完整的权重向量是不可能的——只能计算那些非零条目的权重。一种解决方案是搜索，使得逐个分量；然而，这样做通常是不可能的，因此我们不会进一步考虑此选项。

相反，我们将通过Unifying 处理过程提取权重的多次尝试结合在一起。如果和见证了同一神经元的关键点，并且部分向量具有条目并且部分向量具有条目定义，那么只要非空，就可以通过将两个部分解统一在一起来恢复所有条目的比率，如下所示。

观察到这个过程还允许我们检查和是否见证了同一个神经元达到其关键点。如果，那么只要 A(j) 中不存在两行具有个互为标量倍数的条目,将两个部分解放一起，就会有一个唯一的解。如果上述Unifying 处理失败——因为不存在单个标量 c 使得 ——则和不是同一神经元处于关键点的关键输入。

4.3.3 Recovering Row Signs in Deep Networks

1 层收缩符号恢复过程仍然适用于“充分收缩”神经网络，其中在层存在，因此对于所有 h ∈ Rdj 且存在原像且。如果神经网络具有足够的收缩性，那么很容易看出前面描述的攻击将会起作用（因为我们已经假设了必要的成功标准）。

在 1 深网络的情况下，满足且满足上述要求即可。一般来说，是必要的，但这还不够，即使每个层都是一个满射。由于每个隐藏层之后都有一个 ReLU 激活，因此在计算原像时不可能将负值发送到第二层 fj 中。

因此，为了找到的原像，我们必须更加小心地发起攻击：而不是不是仅仅搜索使得另外还要求分量。这确保我们能够递归计算并通过归纳计算使得。

无需任何查询即可测试网络是否具有足够的收缩性，这很简单：尝试上述方法来找到原像 x；如果失败，则中止并尝试以下（更昂贵的）攻击过程。否则就是收缩的。

4.4 k-Deep Expansive Neural Networks

Contractive Neural Networks 和 Expansive Neural Networks区别

虽然大多数小型神经网络是收缩性的，但实际上几乎所有有趣的神经网络都是扩张性的：某些中间层上的神经元数量大于该层的输入数量。几乎所有先前的方法仍然适用于此设置，但有一个例外：列符号恢复过程。因此，我们需要制定新的战略。

恢复最后一层的符号

观察到最后一层的符号信息没有丢失：因为没有 ReLU 激活，并且我们可以直接用最小二乘法求解权重，所以我们不会丢失符号信息。

恢复倒数第二层上的符号

假设我们已经完全提取了函数（倒数第三层），并进一步提取了权重和偏差直至行的符号。还剩下三个未知量：符号向量、和。假设我们被给予使得。然后就可以通过蛮力同时解决所有三个未知数。

定义 12. 设表示将矩阵的行乘以中的相应坐标。因此，。

设。枚举 s 的所有赋值并计算。我们知道，如果我们正确猜测符号向量 s，则系统将存在解方程这是零深度提取问题，只需调用一次最小二乘法即可有效解决该问题，这使我们能够通过强制执行符号位—完全恢复倒数第二层的符号以及最后一层的值（和符号）。

不幸的是，这个过程无法扩展以恢复第层及更早层的符号。它依赖于有效测试程序（即最小二乘法）的存在来求解最后一层。如果我们在第层尝试这种强力策略来测试我们的符号分配是否正确，我们将需要运行完整的第层提取过程，从而对Oracle产生指数级的查询。

然而，我们可以使用下面这个想法，以便即使在网络中的早期层，也可以仅使用线性数量的查询来恢复符号（但在隐藏层的宽度上仍然是指数工作）

Recovering signs of arbitrary hidden layers：

假设我们得到了一些样本集合，其中某个神经元位于我们提取后的层上：。那么我们就知道应该存在一个单个未知向量和偏差使得对于所有而言。这为我们提供了一个有效的过程来测试第 j 层上的给定符号分配是否正确。和之前一样，我们枚举所有可能的符号分配，然后检查是否可以恢复这样一个向量 v。如果可以，则分配是正确的；否则，分配是正确的。如果不是，那就错了。剩下的只是展示如何实现此过程以获得这样的输入集合。

4.4.1 The Polytope Boundary Projection Algorithm 多面体边界投影算法

定义 13. 包含的第层多胞形是点集，因此对于所有，。

图 3.（左）k 深度神经网络的几何结构，遵循 [RK19]。由神经元 η0、η1、η2 导出的临界超平面位于第一层并且是线性的。由神经元 η3、η4 导出的临界超平面位于第二层，并被第一层神经元“弯曲”。由神经元 η5 导出的临界超平面是第三层上的神经元，并被前两层上的神经元弯曲。（右）超平面遵循程序的图。给定关键点 x 的初始关键输入，沿着超平面到达双临界点 x′。要找到它下一步去哪里，请沿着虚线执行二分搜索并找到输出 y。

据观察，只要不是临界点的关键输入，周围的第层多胞形就是一个开放的凸集。在图3中，每个封闭区域是一个层多面体，由和形成的三角形是一个层多面体。给定输入和方向，我们可以计算距离，使得值位于由层 1 到 k 定义的多胞体的边界处。也就是说，从 x 开始，沿着方向 Δ 行进，当第 j 层或更早的神经元第一次到达临界点时，我们就停止。正式地，我们定义

当我们将神经网络提取到第 j 层时，我们才会计算。因此，我们针对提取的函数和神经元值函数执行计算，因此计算该函数不需要查询。在实践中，我们通过二分搜索来求解 α。

4.4.2 Identifying a Single Next-Layer Witness

给定正确提取的网络和层的权重（直到符号），我们的符号提取过程需要对层 j 上的关键点进行一些见证。我们首先执行标准的二分搜索扫描来查找集合，其中每个集合都是未知层上某个神经元的见证。通过检查中是否有的情况下，过滤掉层或更早的临界点是很简单的。即使我们还没有求解层 j 的符号，仍然可以计算它们是否处于临界点，因为的临界点是的临界点。这将消除层或更低层上关键点的任何见证。

现在我们必须过滤掉严格晚于 j 的层上的任何临界点。令表示 j 层或更高层上的潜在见证人（已经过滤掉 j − 1 层或更早层上的关键点）。通过有限差分，估计在 x = x* 处评估的。选择垂直于 g 并因此平行于临界超平面的任意随机向量 r。设 α = Proj1..j(x*, r)。如果事实证明 x* 是 j 层上临界点的见证，那么对于所有 < α，我们必须有 x* + r ∈ W(η*)。重要的是，我们也有相反的情况：当 δ > α 的概率很高时，我们有 x* + δr ∈ W(η*)。然而，请注意，如果 x* 不是 j 层上神经元的见证，那么这两个条件之一将为假。我们已经排除了早期神经元的见证，因此如果 x* 是 j′ > j 层上后一个神经元的见证，那么第 j′ 层多胞形不太可能与第 j 层多胞形具有相同的形状，并且因此我们会发现这个事实。在两个多胞体实际上相同的情况下，我们可以发起以下攻击，如果失败，我们就知道我们的初始输入位于错误的层上。

4.4.3 Recovering Multiple Witnesses for the Same Neuron

上述过程产生一个见证人 x* ∈ W(η*)，使得 L(η*) = j + 1。我们将其扩展为见证人 W 的集合，其中所有 x ∈ W 都有 x ∈ W(η*)，要求集合是多样化的：

定义 14. 输入 S 的集合在 j 层是完全多样化的，如果对于所有 η 且 L(η) = j 且对于 s ∈ {−1, 1} 存在 x ∈ S 使得。

非正式地，j 层的多样性意味着，如果我们考虑到 j 层空间的投影（通过计算 x ∈ S 的 f1..j(x)），对于每个神经元 η ，将至少有一个输入 x+ ∈ S神经元是正的，并且至少有一个输入 x− ∈ S 使得神经元是负的。

我们的程序如下。令 n 垂直于 x* 所在的超平面。选择一些 r，其中 r · n = 0 并令 α = Proj1..j(x*, r) 将 x′ = x* + αr 定义为第 j 层多胞体边界上的点。特别是，这意味着我们仍然有 x′ ∈ W(η*) （因为 r 垂直于 n），而且对于某些神经元 L(ηu) < j （通过构造 α），x′ ∈ W(ηu) 。将此输入 x′ 称为双临界点（因为它同时见证两个临界点）。

从这一点 x′ 开始，我们希望获得一个新点 y，这样我们仍然有 y ∈ W(η*)，但 y 也在神经元 ηu 的另一侧，即，。图 3（右）给出了该过程的示意图。为了沿着 x* 的路径前进，我们首先需要在新的超平面上找到它的临界点，刚刚被神经元 ηu 弯曲。我们通过从神经元 ηu 的超平面（图 3 中的虚线）远离且平行于超平面开始执行临界点搜索来实现这一点。这将返回一个点 y，我们可以从该点继续执行以下过程的超平面。

几何视图在这里误导了我们：因为该图是二维投影，所以从临界点 y 看来，我们只能沿两个方向行进：远离 x′ 或朝向 x′。远离是更好的选择，朝向 x' 不会帮助我们构造一组完全不同的输入。

然而，d0 维输入空间通常具有保留在神经元 η* 上的 (d0−1) 维。我们服从教派。 5.5.1 一种选择连续方向的有效方法。现在，观察选择一个随机方向最终会成功构建一个完全多样化的集合，但效率极低：存在比选择下一个方向更好的策略。

4.4.4 Brute Force Recovery

给定这个集合 S，我们现在可以通过强力工作恢复正确的符号分配，如下所示。如上所述，计算一组完全不同的输入 {xi} 并定义 hi = f1..j(xi)。然后，对于符号 s ∈ {−1, 1}dj 的所有可能的 2dj 分配，计算猜测的权重矩阵 Aˆ(sj) = s Aˆ(j)。如果我们猜测正确的向量 s，那么我们将能够计算对于每个 xi ∈ S。最后，我们知道将存在一个向量 w = 0 和偏差 bˆ，这样对于所有 hi，我们有 hˆiw + b = 0。之前，如果我们对 s 的猜测是错误的，那么就会有相反的结果.概率不存在有效的线性变换 w, b。因此，我们可以通过线性数量的查询和指数工作来恢复符号

5 Instantiating the Differential Attack in Practice

上述理想化的攻击可以有效地提取神经网络模型，但存在两个问题。

首先，许多算法在数值上不稳定，并且在提取的权重中引入小误差。由于第 i 层中的错误会复合并导致第 j > i 层中的进一步错误，因此有必要将错误保持在最低限度。

其次，攻击需要比必要的更多的选择输入；我们开发了需要更少查询或重复使用以前查询过的样本的新算法。阅读本节。接下来的每个小节都独立于周围的小节，并修改了第 4 节中介绍的算法。为简洁起见，我们假设完全了解原始算法并共享相同的符号。读者可能会发现在继续阅读每个小节之前回顾原始算法很有帮助。

5.1 提高提取层的精度

给定一个精确提取到第 j 层的神经网络，使得 f^1..j−1 在功能上等价于 f1..j−1，但是由于对于提取攻击，我们现在将展示如何将其扩展到功能上与 f1..j 等效的精炼模型 f ̃1..j。在具有无限精度浮点运算的理想化环境中，这一步是完全没有必要的；然而，根据经验，此步骤会导致提取层权重的相对误差从 2−15 变为 2−35 或更好。

开始，选择一个神经元 η，其中 L(η) = j。通过查询已经提取的模型 fˆ1..j，分析计算见证人 {xi}dj i=1，使得每个 xi ∈ Wˆ (η)。这不需要对模型进行查询，因为我们已经提取了这个部分模型。如果 Aˆ(j) 和 bˆ(j) 完全正确，则 W(η;·) ≠ Wˆ(η;·)，因此每个计算出的临界点 xi 将恰好是真实模型 f 的临界点，因此 V( η; xi) ≠ 0。但是，如果计算中存在任何不精确之处，那么对于一些小的。通常我们会得到

幸运的是，给定这个 xi ，很容易计算 x′i 使得 V(η; x′i) = 0。为此，我们对随机 Δ ∈ Rd0 进行采样，并将我们的二分搜索过程应用于范围 [xi + Δ ，xi−Δ]。这里我们应该选择 Δ，使得 ‖Δ‖ 足够小，以至于它穿过的唯一临界点是由神经元 η 引起的临界点，但又足够大，以便它能够可靠地找到 η 的真正临界点。

对每个见证人 xi 重复此过程会为同一神经元 η 提供一组见证人 {x′i}dj i=1。我们计算 hi = f^1..j−1(x′i) 作为层 j 将接收作为输入的隐藏向量。假设 hi 已经是精确的，所以 f^1..j−1 ≈ f1..j−1。因为 x′i 见证了神经元 η 的值为 0，所以我们知道 A(nj) · hi = 0，其中 n 对应于 A(j) 中神经元 η 的行。

理想情况下，我们会用最小二乘法求解这个结果系统。然而，在实践中，有时从 x → x′ 的转换会失败，因为 x′ 不再是同一个神经元 η′ 的见证人。当存在比真实神经元 η 更接近 x 的其他神经元（即 η′）时，就会发生这种情况。由于最小二乘法对于异常值并不稳健，因此该过程可能无法改进解决方案。我们采取两个步骤来确保这种情况不会发生。首先，观察到如果 Δ 较小，则捕获错误神经元 η' 的可能性比捕获正确神经元 η 的可能性下降得更快。因此，我们将 Δ 设置得足够小，以至于大约一半的寻找证人 x' 的尝试都会失败。其次，我们应用一种（更）稳健的方法来确定满足方程 [JOB+18] 解的向量。然而，即使将这两种技术结合起来，有时也无法找到有效的解决方案来提高质量。当这种情况发生时，我们拒绝这个提议的改进并保留原始值。

我们的攻击可以通过以下鲁棒统计问题的解决方案来改进：给定一个（已知）集合，使得对于某些（未知）权重向量 w，我们有对于足够小的、足够大的 δ > 0.5 和 δ|S| > N ，有效地将向量 w 恢复到高精度。

5.2 Efficient Finite Differences

本文中的大多数方法都是基于计算神经网络 f 的二阶偏导数，因此有必要开发一种鲁棒的梯度估计方法。整个第 4部分，我们计算 f 沿方向 α 的偏导数，在 x 处评估，步长 ε 为

为了更早地计算二阶偏导数，我们首先以不同的步长 0 向 x* + 0e1 迈出一步，然后计算该位置的一阶偏导数，从而计算 αi+ 和 αi−。然而，由于浮点不精确，不希望有两个步长（0 控制从 x* 到步长的距离，并在计算偏导数时控制步长）。更糟糕的是，我们必须得到 0，因为如果那么当计算沿 ei 的偏导数时，我们可能会穿过超平面并错误地估计一阶偏导数。因此，我们计算

我们既沿着 ei 步进，又沿着相同的 ei 求偏导数（对于 −ei 也类似）。这消除了对额外超参数的要求，并允许步长大几个数量级，但引入了一个新错误：我们现在在执行提取时丢失了行中条目的相对符号，并且只能恢复。

提取列标志。接下来我们恢复值。幸运的是，相同的差分过程允许我们使用以下观察来学习这些信息：如果 A(1) i,j 和 A(1) i,k 具有相同的符号，则沿 ej + ek 方向移动将导致它们贡献补充。如果他们有不同的迹象，他们的贡献就会相互抵消。也就是说，如果

we have:

and therefore that

我们可以重复这个过程来测试每个 A(1) i,j 是否与（例如） A(1) i,1 具有相同的符号。然而，我们仍然不知道任何单个 A(1) i,j 是正数还是负数——我们仍然必须像之前那样恢复行符号

5.3 Finding Witnesses to Critical Points

在整篇论文中，我们需要能够找到关键点的证人。 4.2 节使用简单的二分搜索来实现这一点，但 (a) 在实践中不精确，(b) 查询效率低下。我们改进了 [JCB+19] 开发的证人搜寻程序。我们再次在两个示例 u、v 之间进行插值，并令 xα = (1−α)u+αv。之前，只要偏导数不等于 ∂f (xα) = ∂f (xβ)，我们就重复进行二分查找，需要 p 个查询才能获得值 x* 的 p 位精度。然而，观察到如果 xα和 xβ 恰好在一个神经元 i 的符号上不同，那么我们可以直接计算 V(ηi; x*) = 0 处的位置 x*，但是对于所有其他 ηj，我们有

图 4. 高效、准确的证人发现。（左）如果 xα 和 xβ 仅在一个 ReLU 上不同（如左图所示），我们可以精确地识别 ReLU 达到临界点的位置 x*。（中）如果有多个 ReLU 不同（如右图所示），我们可以检测到这种情况已经发生：从与虚线相交推断出的在 x* 处计算的 f^(·) 的预测值实际上并不等于f(x*)。（右）这个程序并不健全，仍然可能错误地识别关键点；在实践中我们发现这些很少见。

这种方法如图 4 所示，并且依赖于 f 是具有两个分量的分段线性函数这一事实。通过测量 f (xα) 和 ∂f (xα)（分别为 f (xβ) 和 ∂f (xβ)），我们可以找到图 4（左）中左线和右线的斜率和截距。这使我们能够求解它们的预期交集 (x*, f^(x*))。通常，如果有两个以上的线性段，如图中间所示，我们会发现真实的函数值f(x*)将与我们通过计算得到的期望函数值fˆ(x*)不一致。路口;然后我们可以再次执行二分查找并重复该过程。

然而，我们从这个过程中失去了一些健全性。正如我们在图 4（右）中看到的，可能会出现许多 ReLU 单元在 xα 和 xβ 之间改变符号的情况，但 f^(x*) = f(x*)。在这种情况下，我们会错误地返回 x* 作为临界点，并错过范围内的所有其他临界点。幸运的是，这种错误情况是病态的，在实践中不会发生。

5.3.1 Further Reducing Query Complexity of Witness Discovery

假设我们已经提取了神经网络的前 j 层，并且想要执行上述临界点查找算法来识别 xα 和 xβ 之间的所有临界点。请注意，我们不需要从前 j 层收集任何更多的关键点，但运行二分搜索仍然可以恢复它们。为了绕过这个问题，我们可以分析性地将 S 计算为 xα 和 xβ 之间提取的神经网络 fˆ1..j 上关键点的所有见证人的集合。只要到目前为止提取的网络 f^ 是正确的，我们就可以保证 S 中的所有点也是真实 f 的临界点的见证人。我们不查询范围 (xα, xβ)，而是执行 |S| + 1 种不同的搜索。将 S 的元素排序为 {si}|S| i=1 使得 si < sj =⇒ |xα − si| < |xα - sj|。滥用符号，令 s1 = xα 且 s|S| = xβ。然后，对 i = 1 到 |S| 的每个不相交范围 (Si, Si+1) 执行二分搜索− 1 并返回并集。

5.4 Unification of Witnesses with Noisy Gradients

回想一下，为了提取 Aˆ(l)，我们提取候选候选 {ri} 并搜索在多个坐标上一致的对 ri、rj。这允许我们合并 ri 和 rj 以恢复（最终）A^(l) 的完整行。对于浮点误差，Sect. 中的统一算法。 4.3 由于多种原因失败。我们的核心算法计算超平面的法线，返回成对比率 Aˆ(1) i,j /Aˆ(1) i,k ；整个宗门。 4 不失一般性，我们设置 A^(1) i,1 = 1。不幸的是，在实践中，由于数值不稳定性的不同影响，失去了通用性。考虑以下情况：对于 α 0，A(l) i,1 < 10−α，但对于所有其他 k，A(l) i,k ≥ 1。那么将会有更多（相对）权重 A(l) i,1 的浮点不精确性高于其他权重。在归一化之前，无需担心，因为绝对误差不大于任何其他误差。然而，所描述的算法现在通过将每个其他坐标 A(l) i,k 除以 A(l) i,1 来对其进行归一化，从而污染了这些值的精度。因此我们调整我们的解决方案。在第 l 层，我们得到一个向量集合 R = {ri}in=1，因此每个 ri 对应于某个（未知）神经元 ηi 的提取。首先，我们需要一种算法将项目聚类到集合 {Sj}jdl=1 中，以便 Sj ⊂ R 并且 Sj 中的每个向量对应于第 l 层上的一个神经元。然后我们需要统一每个集合 Sj 以获得 Aˆ(l) j 的最后一行。

使用图聚类创建子集 S。设表示从簇n 中提取的行的第a个坐标。首先构造一个图 G = (V, E)，其中每个向量 ri 对应于一个顶点。设 δ(k) ij = |r(k) i − r(k) j |表示沿 k 轴的行 ri 和行 rj 之间的差；然后，当近似0范数足够大时，连接从 ri 到 rj 的边。我们计算 G 的连通分量并将每一组 Sj 划分为一个连通分量。观察到，如果 = 0，那么这个过程正是前面描述的，将条目完全一致的向量配对；实际上，我们发现 ε = 10−5 的值就足够了。

统一每个簇以获得行权重。我们构造三维 Mi,a,b = r(ai)/r(i) b 。给定 M ，对标量 cab 的一个很好的猜测是，使得 r(ai) = r(i) b · Cab 沿着尽可能多的坐标 i 是赋值 Cab = mediani Mi,a,b，其中估计误差为 eab =stdev Mi,a,b。如果所有 ra 都是完整的并且没有不精确性，那么 Cab 将没有错误，因此 Cab = Cax·Cxb。然而，由于它确实存在误差，因此我们可以通过观察来迭代改进猜测的 C 矩阵：如果误差 eax + exb < eab，则猜测的赋值 Cax·Cxb 是比 Cab 更好的猜测。因此我们替换 Cab ← Cax · Cxb 并更新 eab ← eax + exb。我们迭代这个过程，直到没有进一步的改进。然后，最后，我们选择最优维度 a = arg mina Σ b eab 并返回向量 Ca。请注意，此过程紧随构造两个部分条目 ri 和 rj 的并集，只是我们沿着每个坐标可能的最佳轴执行它。

5.5 Following Neuron Critical Points

第 4.4.3 节开发了构建一组见证者的技术，以证明同一神经元处于关键点。我们现在在数值上稳定这个过程。和之前一样，我们从输入 x* ∈ W(η*) 开始，计算 x* 处临界平面的法向量 n，然后选择满足 r·n = 0 的 r。 n 的计算必然有一些浮点错误，所以 r 也会。这意味着当我们计算 α = Proj1..j(x*, r) 并让 x′ = x* + rα 时，所得的 x′ 几乎完全是某个神经元 ηu 的见证，其中 L(ηu) < j，（因为该计算是在精确提取的模型），但 x′ 可能已经偏离了 η* 引起的原始临界平面（图 5）。

图 5. 数值稳定的临界点跟踪算法。（左）从点 x′ 计算沿 η* 的平行方向，部分步进到 x1 并将其细化为 x2，然后完成步进到 x′。（右）从x′开始增长越来越大的正方形，直到有四个以上的交点；返回 y 作为最大正方形上 η* 上的点。

为了解决这个问题，在计算 α 后，我们首先采取较小的步长，令 x1 = x* + r√α。然后，我们通过在区域 x1 − n 到 x1 + n 上执行一小步二分搜索，将该点的位置细化为点 x2 。如果计算 n 时没有错误，则 x1 = x2，因为两者都已经是 η* 的见证人。如果不是，则所有错误均已更正。给定 x* 和 x2，我们现在可以计算 α2 = Proj1..j(x*, x2 − x*) 并令 x ̄′ = x* + (x2 − x*)α2 实际上将成为两个神经元的见证同时地。

接下来我们给出一个稳定的方法来计算 y，它是 η* 的见证，并且是 ηu 的另一边。先前的过程需要平行于 ηu 和无限小的位移进行搜索，但是如果尚未准确地知道 ηu 给出的超平面的法线，则这在数值上不稳定。相反，我们执行以下过程。选择两个等长的正交向量 β、γ 和，并对描绘出坐标为 x ̄′ ± β ± γ 的正方形周长的线段进行二分查找。当 ‖β‖ 很小时，穿过的临界点数量正好是 4 个：两个是因为 ηu，两个是因为 η*。只要临界点的数量保持为 4，我们就将 β 和 γ 的长度加倍。最终，当正方形的周长与另一个神经元 ηz 相交时，我们将发现四个以上的临界点。此时我们停止增加盒子的大小，并可以通过丢弃落在 etau 上的点来计算 eta* 的连续方向。然后我们可以选择 y 作为 η* 上与最大平方二分搜索相交的点。