Reachability Analysis of Deep Neural Networks with Provable Guarantees 论文小结

论文内容

验证深度神经网络的正确性是困难的，我们研究一个关于前馈深度神经网络的一般性可达性问题——给定一个输入集合，使用Lipschitz连续的函数来计算输出，计算这个函数值的上下界。因为神经网络和函数都是利普希茨连续的，所以在这个上下界中的任意数值都是可达的。我们展示了如何通过实例化一个可达性问题来获取安全验证问题，输入范围分析问题和鲁棒性测量问题。我们提出了一种新的基于自适应嵌套优化的算法来解决可达性问题。这个技术已经在一系列深度神经网络上进行了实现和评估，证明了自己的效率，可伸缩性，并且相比现有的最先进的验证方法，能处理类别更广泛的的神经网络。

1.introduction

人们对于深度神经网络和使用了深度神经网络元素的系统还有很多忧虑，比如部署在对安全性要求很高的系统上。为了缓解忧虑，获得人们的信任，深度神经网络需要像飞机，汽车一样被检验。作者认为他研究的这个问题很有用，与许多关键问题有关。

为了验证一个系统，验证方法不仅要提供一个结果，还要提供结果的一个保证，比如误差范围。现存的研究方法包括将问题简化到约束满足问题，这个问题可以被一些方法解决，或者是实行离散向量空间上的搜寻算法。即使它们能够得到一些保证，但有两个缺点。第一，他们的研究主题受到限制，更确切地说，它们只能在进行线性变换（例如卷积层和全连接层）和简单非线性变换（如RELU）的层上奏效，在一些其它重要的层上无法起效，例如sigmod，max pooling和softmax这些广泛运用于最新的神将网络上的层。第二，基于约束的方法的可伸缩性受到求解器的能力和网络大小的显著限制，并且它们只能与只有几百个隐神经元的网络一起工作。然而，最新的神经网络一般都有上百万甚至上亿的隐神经元。

这篇论文提出了一个最新的方法，没有上述缺点，而且提供误差范围，这个方法的灵感来自于最近在全局优化方面的进展。对于在输入维数集合上定义的输入子空间，提出了一种自适应嵌套优化算法。我们的算法的性能不依赖于网络的大小。因此，它可以扩展到大型网络的工作。

2.Related work

安全检验
对抗样本生成
输出范围分析

3.Lipschitz Continuity of DNNs

作者首先介绍了Lioschitz连续的定义，然后说明已经有论文证明了deep neural networks with half-rectified layers (i.e., convolutional or fully connected layers with ReLU activation functions), max pooling
and contrast-normalization layers are Lipschitz continuous
他要证明the softmax layer, sigmoid and Hyperbolic tangent activation functions also satisfy Lipschitz continuity
随后作者用数学方法进行了证明并计算出了各个类别的层的Lipschitz常数

4.Problem Formulation

作者给一些量进行了定义

输出范围量化了深度神经网络对于一个输入的的特定输出（即对于某个标签J的分类概率），带有误差容忍度（此处误差不知是指输入还是输出，我觉得是输出）
输入范围分析可以被泛化成分对数范围分析

作者将展示如何将安全验证问题转化成可达性问题

作者首先定义了什么是安全，然后提出了安全的对偶问题，只要找出一个反例即可

定义：如果两个网络有相同的分类任务，但结构不一样，如有不同的层，参数，即被称为homogeneous

提出了两个关于鲁棒性比较的定义，大概是指误差范围小的鲁棒性比较强

最终，通过实例化一个函数o，我们可以量化一个网络的输出范围，度量一个网络是否安全，比较两个homogeneous网络的鲁棒性，或者对于一个给定网络，两个不同输入集的鲁棒性

5.Confidence Reachability with Guarantees

第三节已经说明一个深度神经网络是利普希茨连续的（与深度，种类，神经元数量无关），所以为了解决可达性问题，必须找出对于给定输入集的全局最大值和最小值

使w=o.f作为级联函数，为了不失一般性，我们假设输入空间X0是盒约束，这显然是可行的，因为图像在进入神经网络之前通常被归一化为[0，1]矩阵。

最小值的计算被简化为求解具有保证收敛到全局最小值的优化问题（最大化问题可以转化为最小化问题）。但是这个问题很难解决，因为这个函数是一个高度非凸函数，通过一般的基于梯度下降的优化方法很难达到全局最小。作者从别的论文里得到灵感，设计了另一个连续函数作为原函数的下界

通过一系列措施，我们可以渐进的获取全局最小值。实际上，我们通过使用一个误差容忍度并迭代多次来控制最终结果.

在下一节，我们创造一个下界，上界队列，并且证明他可以收敛。为了适用于高维度的深度神经网络，我们的方法是受谋篇论文中自适应嵌套优化思想的启发，在具体算法和收敛性证明上存在显著差异。

5.1 One-dimensional Case

设定了一些量，写出了迭代计算的过程，画了个图

5.1.1 Convergence Analysis

提出了收敛的两个条件并进行证明

首先证明下界队列Li是严格单调的，同时也可证明上界队列也是严格单调的

5.1.2 Dynamically Improving the Lipschitz Constant

一个接近于kbest的利普希茨常数可以使得算法的收敛过程更加迅速，设计了一个方法可以根据前一个迭代来动态更新利普希茨常数

5.2 Multi-dimensional Case

基本思想是把多维优化问题分解为一个内嵌一维优化问题队列，然后将这些一维最小化子问题的最小值反向传播到原始维数，得到最终的全局最小值。

5.2.1 Convergence Analysis

使用数学归纳法，从一维推至高维

证明说明，在一维情况下，嵌套格式的整体误差界仅线性地增加。此外，可以应用自适应逼近来优化其性能，而不影响收敛。关键观察是放松嵌套方案固有的严格从属关系，同时考虑多维优化过程中出现的所有单变量子问题。对于所有产生的积极子问题应用数值测量。然后对多维优化问题进行迭代，选择具有最大测量值的子问题，并在该子问题中进行新的尝试。该措施被定义为由一维优化算法生成的最大间隔特性。

6 Proof of NP-completeness

NP完全性：计算复杂性理论中的一个重要概念，它表征某些问题的固有复杂度。一旦确定一类问题具有NP完全性时，就可知道这类问题实际上是具有相当复杂程度的困难问题。

6.1 Upper Bound

首先，一维优化实例与误差边界是线性相关的。通过一系列证明，说明每一次迭代的改进相对于误差界是线性的，这意味着优化过程将相对于区域[a，b]的大小在线性时间内收敛。

对于多维情况，我们注意到，在方程（23）中，为了达到全局最优，不需要改变所有维数Xi，并且维数之间的排序是重要的。因此，我们可以有一个非确定性算法，猜测尺寸的子集连同它们的排序。这些是需要改变从原始输入到全局最优的维度。这个猜测可以在多项式时间内完成。然后，我们可以将一维优化算法从最后一个维度向后应用到第一维。由于一维情形的多项式时间收敛，这个过程可以在多项式时间内完成。因此，整个过程可以用非确定性算法在多项式时间内完成。

6.2 Lower Bound

3-SAT问题

6.2.1 Construction of DNN

构造一个深度神经网络，有四层，一个输入层，两个隐藏层，一个输出层，有n个输入神经元，m个输出神经元

6.2.2 Statistical Evaluation Function o

6.2.3 Reduction

7 Experiments

7.1 Comparison with State-of-the-art Methods

与现存方法的比较，与Reluplex和SHERLOCK 比较

7.2 Safety and Robustness Verification by Reachability Analysis

7.3 A Comprehensive Comparison with the State-of-the-arts

综合比较

8 Conclusion

我们提出、设计和实现了一个深层神经网络的可达性分析工具，它具有可证明的保证，可以应用于具有深层和非线性激活函数的神经网络。实验证明，该工具可用于验证深层神经网络的安全性并定量比较其鲁棒性。我们设想，这项工作标志着迈向一个实际的，有保障的DNS安全验证的重要一步。未来的工作包括在GPU中并行化来提高在ImageNet上训练的大规模模型上的可扩展性，并推广到RNs和深度强化学习等其他深度学习模型。

论文总结

论文的目的是提出一个方法来验证深度神经网络的安全性，研究了一个一般性的可达性问题——给定一个输入集合，使用Lipschitz连续的函数来计算输出，计算这个函数值的上下界。因为神经网络和函数都是利普希茨连续的，所以在这个上下界中的任意数值都是可达的。

作者的基本思路是首先介绍了这个选题的重要性，现存方法的优点和缺点，自己提出的这个新方法的优点，用途和重要性。作者首先介绍了Lipschitz连续的定义，然后说明已经有论文证明了一些常用层的函数是Lipschitz连续的，接着用数学方法证明了另外一些常用函数也是Lipschitz连续的。随后，作者提出了神经网络安全性的定义，并提出了安全性的对偶问题，将之转化成可达性问题，（这里其实我还可能理解的不好，还是不怎么清楚他是怎么将安全性问题转化为可达性问题的）由此，通过实例化一个函数o，作者可以量化一个网络的输出范围，度量一个网络是否安全，比较两个homogeneous网络的鲁棒性，或者对于一个给定网络，两个不同输入集的鲁棒性。之后，作者通过数学方法证明可以得到全局最小值，分别对于一维和高维的例子进行了证明，说明了如何求得全局最小值和收敛性的证明。接着，作者证明了这个问题可以用非确定性算法在多项式时间内完成，构造了一个神经网络的例子来佐证。最后，作者将自己的方法与现存的一些方法通过实验进行了全方位的比较，并通过数据和作图来直观的展现差别。

论文的结论是作者提出、设计和实现了一个深层神经网络的可达性分析工具，可以应用于具有深层和非线性激活函数的神经网络。实验证明，该工具可用于验证深层神经网络的安全性并定量比较其鲁棒性。作者希望将之推广到其他深度学习模型上。