Divide and Slide: Layer-Wise Refinement for Output Range Analysis of Deep Neural Networks
Divide and Slide: Layer-Wise Refinement for Output Range Analysis of Deep Neural Networks
复制标题
DOI：
10.1109/tcad.2020.3013071
复制
发表时间：
2020-11
影响因子：
2.9
通讯作者：
Chao Huang;Jiameng Fan;Xin Chen;Wenchao Li;Qi Zhu
中科院分区：
文献类型：
--
作者：
Chao Huang;Jiameng Fan;Xin Chen;Wenchao Li;Qi Zhu
在本文中，我们提出了一种用于神经网络输出范围分析的逐层细化方法。虽然诸如非线性规划（NLP）之类的方法可以在输出范围分析中直接对神经网络带来的高度非线性进行建模，但众所周知，它们通常难以求解。我们建议使用激活函数的凸多边形松弛（过近似）来处理非线性问题。这使我们能够将松弛后的问题编码为一个混合整数线性规划（MILP），并通过调整多边形中的线段数量来控制松弛的紧密程度。从每个神经元的线段数为1开始（这与线性规划（LP）松弛一致），我们的方法逐层选择神经元以迭代地细化这种松弛。为了解决随着细化程度提高整数变量数量增加的问题，我们通过划分和滑动逐层约束来结合基于传播的方法和基于规划的方法。具体来说，给定一个滑动数$s$，对于第$l$层的神经元，我们只对$l - s$和$l$之间的层的约束进行编码。我们表明我们的整体框架是合理的，并提供了一种有效的过近似。在深度神经网络上的实验表明，与现有技术相比，使用我们的方法在输出范围分析精度上有显著提高。
In this article, we present a layer-wise refinement method for neural network output range analysis. While approaches such as nonlinear programming (NLP) can directly model the high nonlinearity brought by neural networks in output range analysis, they are known to be difficult to solve in general. We propose to use a convex polygonal relaxation (overapproximation) of the activation functions to cope with the nonlinearity. This allows us to encode the relaxed problem into a mixed-integer linear program (MILP), and control the tightness of the relaxation by adjusting the number of segments in the polygon. Starting with a segment number of 1 for each neuron, which coincides with a linear programming (LP) relaxation, our approach selects neurons layer by layer to iteratively refine this relaxation. To tackle the increase of the number of integer variables with tighter refinement, we bridge the propagation-based method and the programming-based method by dividing and sliding the layer-wise constraints. Specifically, given a sliding number $s$ , for the neurons in layer $l$ , we only encode the constraints of the layers between $l-s$ and $l$ . We show that our overall framework is sound and provides a valid overapproximation. Experiments on deep neural networks demonstrate significant improvement on output range analysis precision using our approach compared to the state-of-the-art.