NeurIPS22 Oral｜摘下悬在神经网络上的达摩克利斯之剑：从模型层面获得对抗鲁棒性保证

本文是NeurIPS 2022入选论文Rethinking Lipschitz Neural Networks and Certified Robustness: A Boolean Function Pespective 的解读。该论文在NeurIPS 2022上以三个strong accept的得分荣获Oral Presentation（排名前1.7%）。该论文由北京大学王立威教授课题组完成，其中作者张博航为北京大学智能学院2019级博士生；作者姜度为北京大学智能学院2022级博士生；作者贺笛为北京大学智能学院助理教授。

本文从理论角度系统探究了深度学习领域的核心问题：是否能够从模型层面出发，设计出具有天然对抗鲁棒性的神经网络？

对于基本的L无穷鲁棒性问题，本文揭示了Lipschitz神经网络的表达能力与其拟合布尔函数能力之间的深刻联系。从这一角度，本文首先指出了标准Lipschitz神经网络表达能力的本质缺陷，并进一步探究了近期所提出的新型网络结构（如L无穷网络）背后的深层次机理。最后，本文提出了一个鲁棒性神经网络的统一框架，称为SortNet（排序网络），该网络结构在CIFAR-10、ImageNet等多个数据集上均取得了SOTA的表现。

论文链接: https://arxiv.org/abs/2210.01787

一、对抗鲁棒性背景介绍

众所周知，深度神经网络在实际应用中存在着一个严重的缺陷——不具有鲁棒性(robustness) 。例如，对于标准的分类任务，尽管ResNet等现代神经网络已经能够在ImageNet等数据集上取得卓越的表现，但往往对输入图片加上一个人眼看不见的微小扰动，就足以让网络预测出完全错误的结果。我们把扰动后的图片称为对抗样本(adversarial example)。对抗样本的广泛存在对深度学习的安全性和可靠性造成了严峻的挑战，并制约了其在自动驾驶、医疗等领域的应用前景，成为了悬在深度学习头顶的一把达摩克里斯之剑。

那么为什么神经网络的鲁棒性很差呢？其核心原因在于，将神经网络看成一个从输入到输出的函数时，该函数的Lipschitz常数过大。 具体而言，Lipschitz性质从数学上刻画了神经网络输出随输入扰动变化剧烈的程度。因此，如果我们能够设计Lipschitz常数受限的神经网络，便自然获得了可证明的鲁棒性(certified robustness)。

然而，本文的理论结果表明，简单地限制神经网络的Lipschitz常数往往会损害模型的表达能力（即拟合数据的能力）。用数学的语言来说，我们所要研究的核心问题是：如何设计Lipschitz常数受限的神经网络，同时仍具备足够的表达能力，可以拟合任意Lipschitz连续函数？ 本文将系统回答这个问题。

二、标准Lipschitz神经网络的表达能力

我们先来考虑一种构建Lipschitz网络的标准方式。我们称一个函数 是 Lipschitz的, 如果对于任意输入 ，下式都成立:

其中 是任意一种范数, 用于度量 之间的距离。本文考虑标准的L无穷鲁棒性, 对应于 范数。

对于一个分层的神经网络, 可以将其看成是一个复合函数 , 其中 表示第 层。根据复合函数的Lipschitz性质，如果我们限制每一层对应的函数 都是1-Lipschitz 的，那么整个网络 也是1-Lipschitz的。

我们因此把问题转化为了如何设计网络的一层使其满足1-Lipschitz性质。对于标准神经网络, 我们有

其中矩阵 和向量 是网络参数, 是激活函数（如ReLU或tanh）。对于这样的标准网络结构, 如果想让 是1-Lipschitz的, 只需要保证 的大小受限, 即 , 且 是1Lipschitz函数即可（这对于ReLU或tanh等常见的激活函数显然都成立）。我们把这样的网络称为标准Lipschitz网络。

2.1 布尔数据集上的表达能力

本文从拟合布尔函数的新颖角度指出了这一类网络结构表达能力的本质缺陷。所谓布尔函数, 指的是输入为布尔向量 , 输出也为布尔值 (0或1）的离散函数。对于每个布尔函数 , 都对应着一个二分类问题以及相应的布尔数据集 。

一个自然的问题是, 我们为什么要研究布尔数据集呢? 事实上, 布尔数据集和 无穷鲁棒性息息相关。不难发现, 布尔数据集上任意两个样本的 距离都是1, 这表明布尔数据集的样本具有很好的可区分性(well-separated)。因此, 对任意布尔数据集, 存在着一个分类器能够取得完美的鲁棒性（精确来说, 其 鲁棒半径可以达到1/2）。

那么, 标准Lipschitz神经网络能否做到布尔数据集上的鲁棒分类呢? 不幸的是, 我们有如下的不可能定理：

定理：标准Lipschitz神经网络无法在对称布尔数据集上取得鲁棒性保证, 其可验证的鲁棒半径一定不超过 , 其中 是输入维度。

这里, 对称布尔数据集指的是由对称布尔函数 生成的数据集。它满足样本 的类别 不依赖于 中元素的输入顺序。例如, 两个最基本的布尔函数是逻辑与以及逻辑或, 它们都是对称布尔函数。以上定理表明, 即使是对于最简单的逻辑函数对应的数据集, 标准Lipschitz神经网络仍几乎不能取得任何鲁棒性保证, 其鲁棒半径 在高维情况下将衰减到0。

注：常用的手写数字识别MNIST数据集就是一个布尔数据集，每张图片可以看作一个布尔向量，里面的黑白像素代表0和1。我们的定理可用于理解为什么标准Lipschitz神经网络在这种简单任务上表现也非常差。

2.2 对一般性的Lipschitz函数的表达能力

以上结果可以很容易拓展到一般的Lipschitz函数拟合任务。其核心思想是考虑布尔函数的连续化。具体而言, 我们可以找到一类对称的1-Lipschitz连续函数, 称为顺序统计量。 给定一个向量 , 它的第 阶顺序统计量是其各分量排序后的第 大值, 记为 。可以看出, 第 阶顺序统计量正是布尔函数 在实数空间上的连续化。特殊地, 最大值函数 max 是逻辑或的连续化, 而最小值函数 是逻辑与的连续化。

我们因此得到了如下的不可能定理：

定理：标准Lipschitz神经网络无法在空间 上拟合顺序统计量函数。进一步地, 一 定存在一个输入点 , 在该点上函数值的拟合误差大于等于 。

以上定理表明，标准Lipschitz神经网络严重缺乏表达能力，不能表达一些基本的1-Lipschitz连续函数。

三、基于排序的神经网络GroupSort

Anil等人在2019年的一篇ICML论文中首次提出了一个能表达任意1-Lipschitz函数的1-Lipschitz神经网络，称为GroupSort网络。它的基本思想是使用一种新颖的GroupSort层替代传统网络的激活函数。每一层神经网络可写为如下函数：

其中 和 是该层的参数。GroupSort层将输入分组并排序, 输出各组排序结果连接后得到的向量, 如下图所示。

我们的理论结果对GroupSort为什么能够有充足的表达能力给出了深刻理解。简而言之，GroupSort层的引入使得网络能够计算顺序统计量，从而避免了传统网络表达能力上的本质缺陷。

3.1 MaxMin网络的表达能力

然而，GroupSort层的引入导致计算时需要昂贵的排序操作。因此在实际应用中，通常将组的大小取为2，这样只需要计算两两元素的最大值和最小值（如上图所示）。这种特殊情况对应的网络被称为MaxMin网络。按照冒泡排序的思想，多层MaxMin网络够表达任意组大小的单层GroupSort网络，因此其表达能力仍是充足的。

不幸的是，我们的理论指出，当进一步考虑表达效率时，MaxMin网络仍存在严重缺陷。我们证明了如下两个核心结论：

定理：MaxMin网络无法用少于 层拟合顺序统计量函数, 其中 是输入维度。

定理：MaxMin网络无法用少于 层拟合一般的布尔函数, 其中 是输入维度。

因此，MaxMin网络需要极深的结构才能有拟合任意1-Lipschitz连续函数的表达能力。 这与经典的表达能力理论形成了鲜明的对比：一个著名的结论是，2层传统神经网络就已经能表达任何连续函数。我们的结果给出了MaxMin网络在实际应用中效果为什么仍然不能令人满意的核心原因。

3.2 更进一步的理解

为什么MaxMin网络需要如此深的深度才能拟合布尔函数呢？我们在这里提供一个更强的结论。我们发现，MaxMin网络拟合布尔函数的能力等价于2元布尔电路！ 2元布尔电路指的是有两个输入的与门、或门和单输入非门构成的有向无环电路，如下图所示。

这一结论的严格证明详见论文。其本质原因是，MaxMin层中的基本操作max和min恰好对应了两个输入的逻辑与和逻辑或运算，而线性层可以表达逻辑非（通过取负操作）。通过这一等价性，我们可以深刻理解为什么拟合布尔函数需要很深的MaxMin网络。根据基本的布尔电路理论，这是由于存在一些布尔函数使得只有足够深的布尔电路才能够表达。

四、L无穷距离网络( -distance net)

接下来，本文将重点介绍目前最先进的Lipschitz网络结构——L无穷距离网络( -distance net)。L无穷距离网络在2021年的ICML论文中被本研究团队首次提出，之后在2022年ICLR论文中取得了远超先前SOTA的实验结果，尤其在CIFAR-10数据集上领先了先前工作超过5个点，且计算开销仅为之前工作的10%-20%。L无穷距离网络开创了从模型层面实现对抗鲁棒性的里程碑。

论文链接：
ICML 2021: https://arxiv.org/abs/2102.05363

ICLR 2022: https://arxiv.org/abs/2110.06850

L无穷距离网络的设计原理非常简单：它采用基本的L无穷距离神经元来搭建整个网络。L无穷距离神经元可以写为如下形式：

其中向量 是神经元的输入, 和 是神经元的参数, 是神经元的输出。L无穷距离神经元和传统神经元的区别见下图所示。

4.1 L无穷距离网络的理论性质

L无穷距离神经元最基本的性质是关于 范数是1-Lipschitz连续的。基于这一性质，我们可以自然的得出，以L无穷距离神经元为基本组件搭建出的整个L无穷距离网络也是1-Lipschitz连续的。这使得L无穷距离网络具有严格可验证的对抗鲁棒性。

我们接下来同样来研究L无穷距离网络的表达能力。我们证明了两个重要结果（详见本研究团队的ICML和ICLR论文）：

定理（ICML 2021）：L无穷距离网络能够在紧集上近似拟合任意1-Lipschitz连续函数，且近似误差可以任意小。

定理（ICLR 2022）：对任意有 个样本的多分类数据集 , 存在一个两层的L无穷距离网络，其中间隐层大小不超过 , 使得该网络在数据集 上能达到最优的鲁棒性, 其可验证鲁棒半径为 。

可以看出，L无穷距离网络有着充足的表达能力。那么，和同样有着充足表达能力的MaxMin网络相比，L无穷距离网络有哪些优势呢？为什么L无穷网络的实际表现要远好于MaxMin网络？下一小节我们将回答这些问题。

4.2 L无穷距离网络与布尔逻辑

首先，一个核心的发现是，L无穷距离网络同样引入了顺序统计量操作。这是因为L无穷距离神经元可以等价的写为如下形式：

当选择合适的参数 和 时, L无穷距离神经元可以表达max函数（1阶顺序统计量）, 从而能够表达逻辑或。此外, 式中的绝对值使得L无穷距离神经元可以进行取负操作。两者结合便得到了如下引理：

引理：L无穷距离神经元可以表达任意文字析取式(literal disjunction)。

根据布尔函数的析取标准型(distunctive normal form)理论，我们便可得到如下定理：

定理：两层的L无穷距离网络能够精确表达任意布尔函数。

此外，我们也证明了：

定理：两层的L无穷距离网络能够精确表达任意顺序统计量。

以上结论与MaxMin网络形成了强烈的对比，表明了浅层L无穷距离网络已经足以表达这些函数。可以看到，L无穷距离网络成功的关键是它使用了高维的顺序统计量，而MaxMin网络只使用了2元的max/min操作，这是制约其表达效率的根本原因。

五、Lipschitz神经网络的统一框架

上述分析强调了顺序统计量对于设计具有良好表达能力的Lipschitz神经网络的重要性。本节中，我们将提出一个统一的框架，它囊括了先前所有的工作，并给出了一个高效的可用于实践的新颖架构。

我们的网络结构设计来源于3类基本Lipschitz函数：(1) 线性1-Lipschitz函数；(2) 逐坐标形式的1Lipschitz激活函数 ; (3) 顺序统计量。其基本神经元可以写为如下形式:

其中 sort 函数对于输入向量求出各阶顺序统计量。以该神经元为基本组件所构建的网络称为SortNet（排序网络）。可以证明, GroupSort/MaxMin网络和L无穷距离网络都是SortNet网络的特例。

然而, 和GroupSort类似, SortNet面临着计算开销昂贵的排序操作。为此, 本文提出了一个 SortNet的特殊版本, 它能够在不需要排序的情况下高效训练。其核心思想是, 我们只需要计算形 如 的值, 而并不需要计算中间的排序结果 本身。当 满足特殊的性质时, 可以有高效的计算方法。具体而言, 我们考虑当 满足指数衰减的性质, 即 。对于这一特殊情况，可以推导出下面的等式：

式中 是一个随机向量, 每个分量满足参数为 的伯努利分布。为了计算 , 我们可以采用随机的方式采样 , 并计算等式右边的平均值, 而等式右边只需要计算max操作, 不再需要昂贵的排序操作。此外, 一个有趣的发现是, 这种随机训练的方法实际上类似于深度学习中的 dropout技术, 而 正是dropout mask。因此, 可以预期上述训练方式不仅非常高效, 还有助于提升模型的泛化表现。

注: 当 时, 退化为 , 此时模型只使用一阶顺序统计量max。可以发现, SortNet在这种情况下退化为了L无穷距离网络。对于一般的 , 所有顺序统计量均被使用。实验中我们将 的取值当作一个超参数, 通常取0.3左右会有比较好的表现。

六、实验结果

本文进行了广泛的实验，在4个数据集上对共计6种不同扰动阈值比较了各类Lipschitz神经网络以及其他方法的可验证鲁棒准确率(certified robust accuracy)。可以看出：

1. L无穷距离网络的鲁棒准确率能够远远超越MaxMin网络；
2. L无穷距离网络在多个数据集上均能达到SOTA，尤其在标准的CIFAR-10 (eps=8/255)设定下可以超越之前结果5个点以上。
3. SortNet在所有实验中都能够进一步超越L无穷距离网络，尤其在CIFAR-10 (eps=2/255)设定下能够远远超过L无穷距离网络的表现。
4. L无穷距离网络和SortNet的训练非常高效。SortNet在ImageNet大规模数据集上的训练速度远远超过基线方法。

6.1 MNIST手写数字识别

6.2 CIFAR-10图像分类

6.3 TinyImageNet和ImageNet图像分类

七、总结与展望

在这一工作中，我们对如何设计具有良好表达能力的Lipschitz网络进行了系统和深刻的研究，这对于从模型层面取得可验证的对抗鲁棒性具有重要意义。我们的一系列理论结果首次指出了L无穷鲁棒性和拟合布尔函数之间的密切联系，这使得我们能够对先前工作为什么失败或为什么能够取得成功有一个全新的理解。基于这些理论结果，我们提出了Lipschitz网络的统一框架，在囊括所有先前工作的同时，在多个实验中取得了更加优越的表现。

未来，我们的研究团队还将对神经网络鲁棒性和表达能力等深度学习领域的基本问题进行更进一步的研究。我们旨在通过对这些核心问题的理论研究，指导学术界和工业界设计更好、更强有力的深度学习模型和算法。同时，我们也欢迎对此感兴趣的同学联系、加入我们！

参考文献：

[1] Towards Certifying L-infinity Robustness using Neural Networks with L-inf-dist Neurons; Bohang Zhang, Tianle Cai, Zhou Lu, Di He, Liwei Wang. ICML 2021.
[2] Boosting the Certified Robustness of L-infinity Distance Nets; Bohang Zhang, Du Jiang, Di He, Liwei Wang. ICLR 2022.
[3] Rethinking Lipschitz Neural Networks and Certified Robustness: A Boolean Function Perspective; Bohang Zhang, Du Jiang, Di He, Liwei Wang. NeurIPS 2022 (Oral).

公众号后台回复“CCF2022”2022（拟定）目录PDF下载～