DEEPSPLIT: An Efficient Splitting Method for Neural Network Verification via Indirect Effect Analysis

Patrick Henriksen; Alessio Lomuscio

IJCAI 2021poster101 citations

DEEPSPLIT: An Efficient Splitting Method for Neural Network Verification via Indirect Effect Analysis

Abstract

We propose a novel, complete algorithm for the verification and analysis of feed-forward, ReLU-based neural networks. The algorithm, based on symbolic interval propagation, introduces a new method for determining split-nodes which evaluates the indirect effect that splitting has on the relaxations of successor nodes. We combine this with a new efficient linear-programming encoding of the splitting constraints to further improve the algorithm’s performance. The resulting implementation, DeepSplit, achieved speedups of 1–2 orders of magnitude and 21-34% fewer timeouts when compared to the current SoA toolkits.

Machine Learning: Deep LearningMultidisciplinary Topics and Applications: Validation and Verification

BibTeX

@inproceedings{ijcai2021p351,
  title     = {DEEPSPLIT: An Efficient Splitting Method for Neural Network Verification via Indirect Effect Analysis},
  author    = {Henriksen, Patrick and Lomuscio, Alessio},
  booktitle = {Proceedings of the Thirtieth International Joint Conference on
               Artificial Intelligence, {IJCAI-21}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {Zhi-Hua Zhou},
  pages     = {2549--2555},
  year      = {2021},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2021/351},
  url       = {https://doi.org/10.24963/ijcai.2021/351},
}