Fetching the paper…

Reading the bibliography…

2018

Reachability Analysis of Deep Neural Networks with Provable Guarantees

Ruan, Wenjie, Huang, Xiaowei, Kwiatkowska, Marta

Original
PDF
Post on X

Understand

Verifying correctness of deep neural networks (DNNs) is challenging.

We study a generic reachability problem for feed-forward DNNs which, for a given set of inputs to the network and a Lipschitz-continuous function over its outputs, computes the lower and upper bound on the function values.
Because the network and the function are Lipschitz continuous, all values in the interval between the lower and upper bound are reachable.
We show how to obtain the safety verification problem, the output range analysis problem and a robustness measure by instantiating the reachability problem.

Reachability Analysis of Deep Neural Networks with Provable Guarantees · Around

Built on

S. Piyavskii, “An algorithm for finding the absolute extremum of a function,” USSR Computational Mathematics and Mathematical Physics , vol. 12, no. 4, pp. 57–67, 1972
1972
Earlier work this paper cites.
A. Torn and A. Zilinskas, Global Optimization . New York, NY, USA: Springer-Verlag New York, Inc., 1989
1989
Earlier work this paper cites.
H. H. Sohrab, Basic real analysis . Springer, 2003, vol. 231
2003
Earlier work this paper cites.
L. Pulina and A. Tacchella, “An abstraction-refinement approach to verification of artificial neural networks,” in Computer Aided Verification . Springer Berlin Heidelberg, 2010, pp. 243–257
2010
Earlier work this paper cites.
C. Szegedy, W. Zaremba, I. Sutskever, J. Bruna, D. Erhan, I. Goodfellow, and R. Fergus, “Intriguing properties of neural networks,” arXiv:1312.6199v4 , 2013
Original
2013
Earlier work this paper cites.
I. J. Goodfellow, J. Shlens, and C. Szegedy, “Explaining and Harnessing Adversarial Examples,” ArXiv e-prints , Dec. 2014
2014
Earlier work this paper cites.
A. M. Nguyen, J. Yosinski, and J. Clune, “Deep neural networks are easily fooled: High confidence predictions for unrecognizable images,” CoRR , vol. abs/1412.1897, 2014. [Online]. Available: http://arxiv.org/abs/1412.1897
Original
2014
Earlier work this paper cites.
N. Papernot, P. D. McDaniel, S. Jha, M. Fredrikson, Z. B. Celik, and A. Swami, “The limitations of deep learning in adversarial settings,” CoRR , vol. abs/1511.07528, 2015. [Online]. Available: http://arxiv.org/abs/1511.07528
Original
2015
Earlier work this paper cites.
D. Amodei, C. Olah, J. Steinhardt, P. Christiano, J. Schulman, and D. Mané, “Concrete problems in ai safety,” arXiv preprint arXiv:1606.06565 , 2016. [Online]. Available: https://arxiv.org/pdf/1606.06565.pdf
Original
2016
Earlier work this paper cites.

Similar

V. Gergel, V. Grishagin, and A. Gergel, “Adaptive nested optimization scheme for multidimensional global search,” Journal of Global Optimization , vol. 66, no. 1, pp. 35–51, 2016
2016
Cited alongside, same era.
S. Moosavi-Dezfooli, A. Fawzi, O. Fawzi, and P. Frossard, “Universal adversarial perturbations,” CoRR , vol. abs/1610.08401, 2016. [Online]. Available: http://arxiv.org/abs/1610.08401
Original
2016
Cited alongside, same era.
N. Carlini and D. A. Wagner, “Towards evaluating the robustness of neural networks,” CoRR , vol. abs/1608.04644, 2016. [Online]. Available: http://arxiv.org/abs/1608.04644
Original
2016
Cited alongside, same era.
X. Huang, M. Kwiatkowska, S. Wang, and M. Wu, “Safety verification of deep neural networks,” in Computer Aided Verification . Springer Berlin Heidelberg, 2017, pp. 3–29
2017
Cited alongside, same era.

Then

W. Xiang, H.-D. Tran, and T. T. Johnson, “Output reachable set estimation and verification for multi-layer neural networks,” arXiv preprint arXiv:1708.03322 , 2017
Original
2017
Later among the works it cites.
N. Narodytska, S. P. Kasiviswanathan, L. Ryzhyk, M. Sagiv, and T. Walsh, “Verifying properties of binarized deep neural networks,” CoRR , vol. abs/1709.06662, 2017. [Online]. Available: https://arxiv.org/abs/1709.06662
Original
2017
Later among the works it cites.
R. Ehlers, “Formal verification of piece-wise linear feed-forward neural networks,” in International Symposium on Automated Technology for Verification and Analysis . Springer, 2017, pp. 269–286
2017
Later among the works it cites.
J. Z. Kolter and E. Wong, “Provable defenses against adversarial examples via the convex outer adversarial polytope,” arXiv preprint arXiv:1711.00851 , 2017
Original
2017
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

G. Katz, C. Barrett, D. Dill, K. Julian, and M. Kochenderfer, “Reluplex: An efficient smt solver for verifying deep neural networks,” arXiv preprint arXiv:1702.01135 , 2017

2017

Cited alongside, same era.

A. Lomuscio and L. Maganti, “An approach to reachability analysis for feed-forward relu neural networks,” CoRR , vol. abs/1706.07351, 2017. [Online]. Available: http://arxiv.org/abs/1706.07351

2017

Cited alongside, same era.

S. Dutta, S. Jha, S. Sanakaranarayanan, and A. Tiwari, “Output range analysis for deep neural networks,” arXiv preprint arXiv:1709.09130 , 2017

2017

Cited alongside, same era.

C.-H. Cheng, G. Nührenberg, and H. Ruess, “Maximum resilience of artificial neural networks,” in Automated Technology for Verification and Analysis , D. D’Souza and K. Narayan Kumar, Eds. Cham: Springer International Publishing, 2017, pp. 251–268

2017

Cited alongside, same era.

R. Bunel, I. Turkaslan, P. H. Torr, P. Kohli, and M. P. Kumar, “Piecewise linear neural network verification: A comparative study,” arXiv preprint arXiv:1711.00455 , 2017

2017

Cited alongside, same era.

W. Ruan, X. Huang, and M. Kwiatkowska, “Reachability analysis of deep neural networks with provable guarantees,” The 27th International Joint Conference on Artificial Intelligence (IJCAI) , 2018

2018

Closest in time.

Y. Sun, M. Wu, W. Ruan, X. Huang, M. Kwiatkowska, and D. Kroening, “Concolic testing for deep neural networks,” arXiv preprint arXiv:1805.00089v1 , 2018

2018

Closest in time.

W. Ruan, M. Wu, Y. Sun, X. Huang, D. Kroening, and M. Kwiatkowska, “Global robustness evaluation of deep neural networks with provable guarantees for L0 norm,” arXiv preprint arXiv:1804.05805v1 , 2018

2018

Closest in time.

M. Wicker, X. Huang, and M. Kwiatkowska, “Feature-guided black-box safety testing of deep neural networks,” in Proc. 24th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS’18) , 2018, pp. 408–426

2018

Closest in time.

V. Grishagin, R. Israfilov, and Y. Sergeyev, “Convergence conditions and numerical comparison of global optimization methods based on dimensionality reduction schemes,” Applied Mathematics and Computation , vol. 318, pp. 270–280, 2018

2018

Closest in time.