Divide and Slide: Layer-Wise Refinement for Output Range Analysis of Deep Neural Networks

Huang, Chao ORCID: 0000-0002-9300-1787, Fan, Jiameng, Chen, Xin, Li, Wenchao and Zhu, Qi (2020) Divide and Slide: Layer-Wise Refinement for Output Range Analysis of Deep Neural Networks. IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, 39 (11). pp. 3323-3335.

Text
EMSOFT20__cemera_ready.pdf - Author Accepted Manuscript
Download (1MB) | Preview

Official URL: http://dx.doi.org/10.1109/tcad.2020.3013071

Abstract

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.

Item Type:	Article
Uncontrolled Keywords:	Linear programming (LP), mixed-integer linear programming (MILP), neural networks, output range analysis, refinement
Divisions:	Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	22 Sep 2021 11:02
Last Modified:	15 Mar 2024 18:00
DOI:	10.1109/TCAD.2020.3013071
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3137905