本文是NeurIPS 2022入选论文Rethinking Lipschitz Neural Networks and Certified Robustness: A Boolean Function Pespective 的解读。该论文在NeurIPS 2022上荣获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网络的标准方式。我们称一个函数
其中
对于一个分层的神经网络,可以将其看成是一个复合函数
我们因此把问题转化为了如何设计网络的一层使其满足1-Lipschitz性质。对于标准神经网络,我们有
2.1
布尔数据集上的表达能力
本文从拟合布尔函数的新颖角度指出了这一类网络结构表达能力的本质缺陷。所谓布尔函数,指的是输入为布尔向量
一个自然的问题是,我们为什么要研究布尔数据集呢?事实上,布尔数据集和L无穷鲁棒性息息相关。不难发现,布尔数据集上任意两个样本的
那么,标准Lipschitz神经网络能否做到布尔数据集上的鲁棒分类呢?不幸的是,我们有如下的不可能定理:
定理:标准Lipschitz神经网络无法在对称布尔数据集上取得鲁棒性保证,其可验证的鲁棒半径一定不超过
,其中 是输入维度。
这里,对称布尔数据集指的是由对称布尔函数
注:常用的手写数字识别MNIST数据集就是一个布尔数据集,每张图片可以看作一个布尔向量,里面的黑白像素代表0和1。我们的定理可用于理解为什么标准Lipschitz神经网络在这种简单任务上表现也非常差。
2.2
对一般性的Lipschitz函数的表达能力
以上结果可以很容易拓展到一般的Lipschitz函数拟合任务。其核心思想是考虑布尔函数的连续化。具体而言,我们可以找到一类对称的1-Lipschitz连续函数,称为顺序统计量。给定一个向量
我们因此得到了如下的不可能定理:
定理:标准Lipschitz神经网络无法在空间
上拟合顺序统计量函数。进一步地,一定存在一个输入点 ,在该点上函数值的拟合误差大于等于 。
以上定理表明,标准Lipschitz神经网络严重缺乏表达能力,不能表达一些基本的1-Lipschitz连续函数。
三、基于排序的神经网络GroupSort
Anil等人在2019年的一篇ICML论文中首次提出了一个能表达任意1-Lipschitz函数的1-Lipschitz神经网络,称为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无穷距离网络(
接下来,本文将重点介绍目前最先进的Lipschitz网络结构——L无穷距离网络(
论文链接:
ICML 2021: https://arxiv.org/abs/2102.05363
ICLR 2022: https://arxiv.org/abs/2110.06850
L无穷距离网络的设计原理非常简单:它采用基本的L无穷距离神经元来搭建整个网络。L无穷距离神经元可以写为如下形式:
其中向量
4.1
L无穷距离网络的理论性质
L无穷距离神经元最基本的性质是关于
我们接下来同样来研究L无穷距离网络的表达能力。我们证明了两个重要结果(详见本研究团队的ICML和ICLR论文):
定理(ICML 2021):L无穷距离网络能够在紧集上近似拟合任意1-Lipschitz连续函数,且近似误差可以任意小。
定理(ICLR 2022):对任意有
个样本的多分类数据集 ,存在一个两层的L无穷距离网络,其中间隐层大小不超过 ,使得该网络在数据集 上能达到最优的鲁棒性,其可验证鲁棒半径为 。
可以看出,L无穷距离网络有着充足的表达能力。那么,和同样有着充足表达能力的MaxMin网络相比,L无穷距离网络有哪些优势呢?为什么L无穷网络的实际表现要远好于MaxMin网络?下一小节我们将回答这些问题。
4.2
L无穷距离网络与布尔逻辑
首先,一个核心的发现是,L无穷距离网络同样引入了顺序统计量操作。这是因为L无穷距离神经元可以等价的写为如下形式:
当选择合适的参数
引理:L无穷距离神经元可以表达任意文字析取式(literal disjunction)。
根据布尔函数的析取标准型(distunctive normal form)理论,我们便可得到如下定理:
定理:两层的L无穷距离网络能够精确表达任意布尔函数。
此外,我们也证明了:
定理:两层的L无穷距离网络能够精确表达任意顺序统计量。
以上结论与MaxMin网络形成了强烈的对比,表明了浅层L无穷距离网络已经足以表达这些函数。可以看到,L无穷距离网络成功的关键是它使用了高维的顺序统计量,而MaxMin网络只使用了2元的max/min操作,这是制约其表达效率的根本原因。
五、Lipschitz神经网络的统一框架
上述分析强调了顺序统计量对于设计具有良好表达能力的Lipschitz神经网络的重要性。本节中,我们将提出一个统一的框架,它囊括了先前所有的工作,并给出了一个高效的可用于实践的新颖架构。
我们的网络结构设计来源于3类基本Lipschitz函数:(1) 线性1-Lipschitz函数;(2) 逐坐标形式的1-Lipschitz激活函数
其中
然而,和GroupSort类似,SortNet面临着计算开销昂贵的排序操作。为此,本文提出了一个SortNet的特殊版本,它能够在不需要排序的情况下高效训练。其核心思想是,我们只需要计算形如
式中
注:当
六、实验结果
本文进行了广泛的实验,在4个数据集上对共计6种不同扰动阈值比较了各类Lipschitz神经网络以及其他方法的可验证鲁棒准确率(certified robust accuracy)。可以看出:
-
L无穷距离网络的鲁棒准确率能够远远超越MaxMin网络;
-
L无穷距离网络在多个数据集上均能达到SOTA,尤其在标准的CIFAR-10 (eps=8/255)设定下可以超越之前结果5个点以上。
-
SortNet在所有实验中都能够进一步超越L无穷距离网络,尤其在CIFAR-10 (eps=2/255)设定下能够远远超过L无穷距离网络的表现。
-
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).
原文始发于微信公众号(PKU机器学习基础研究实验室):NeurIPS 2022 Oral | 摘下悬在神经网络上的达摩克利斯之剑:从模型层面获得对抗鲁棒性保证