Towards Fast Computation of Certified Robustness for ReLU Networks
Towards Fast Computation of Certified Robustness for ReLU Networks
复制标题
DOI：
--
复制
发表时间：
2018-04
期刊：
影响因子：
--
通讯作者：
Tsui-Wei Weng;Huan Zhang;Hongge Chen;Zhao Song;Cho-Jui Hsieh;D. Boning;I. Dhillon;L. Daniel
中科院分区：
文献类型：
--
作者：
Tsui-Wei Weng;Huan Zhang;Hongge Chen;Zhao Song;Cho-Jui Hsieh;D. Boning;I. Dhillon;L. Daniel
·一般整流线性单元（ReLU）网络的鲁棒性是一个NP完全问题[Katz，Barrett，Dill，Julian和Kochenderfer CAV 17]。虽然找到确切的最小对抗失真是困难的，但给出最小失真的认证下限是可能的。目前可用的方法计算这样的界限是耗时的或提供低质量的界限，太松散，是有用的。在本文中，我们利用了ReLU网络的特殊结构，并提供了两种计算效率高的算法Fast-Lin和Fast-Lip，它们能够通过使用适当的线性函数Fast-Lin来约束ReLU单元，或者通过约束局部Lipschitz常数Fast-Lip来证明最小失真的非平凡下界。实验表明：（1）我们提出的方法提供的边界接近（差距是2- 3倍）精确的最小失真发现的Reluplex在小型MNIST网络，而我们的算法是超过10,000倍的速度;（2）我们的方法提供类似的边界质量（差距在35%以内，通常在10%左右;有时我们的边界甚至更好）对于更大的网络，与基于解决线性规划问题的方法相比，我们的算法要快33- 14，000倍;（3）我们的方法能够在单个CPU核心上在几十秒内解决多达7层的大型MNIST和CIFAR网络，其中超过10，000个神经元。此外，我们表明，事实上，没有多项式时间算法可以近似找到近似比为0.99\ln n$的ReLU网络的最小对抗性失真，除非$\mathsf{NP}$=$\mathsf{P}$，其中$n$是网络中的神经元数量。
Verifying the robustness property of a general Rectified Linear Unit (ReLU) network is an NP-complete problem [Katz, Barrett, Dill, Julian and Kochenderfer CAV17]. Although finding the exact minimum adversarial distortion is hard, giving a certified lower bound of the minimum distortion is possible. Current available methods of computing such a bound are either time-consuming or delivering low quality bounds that are too loose to be useful. In this paper, we exploit the special structure of ReLU networks and provide two computationally efficient algorithms Fast-Lin and Fast-Lip that are able to certify non-trivial lower bounds of minimum distortions, by bounding the ReLU units with appropriate linear functions Fast-Lin, or by bounding the local Lipschitz constant Fast-Lip. Experiments show that (1) our proposed methods deliver bounds close to (the gap is 2-3X) exact minimum distortion found by Reluplex in small MNIST networks while our algorithms are more than 10,000 times faster; (2) our methods deliver similar quality of bounds (the gap is within 35% and usually around 10%; sometimes our bounds are even better) for larger networks compared to the methods based on solving linear programming problems but our algorithms are 33-14,000 times faster; (3) our method is capable of solving large MNIST and CIFAR networks up to 7 layers with more than 10,000 neurons within tens of seconds on a single CPU core. In addition, we show that, in fact, there is no polynomial time algorithm that can approximately find the minimum $\ell_1$ adversarial distortion of a ReLU network with a $0.99\ln n$ approximation ratio unless $\mathsf{NP}$=$\mathsf{P}$, where $n$ is the number of neurons in the network.