logo

SCIENTIA SINICA Informationis, Volume 51 , Issue 1 : 27(2021) https://doi.org/10.1360/SSI-2020-0172

Robustness verification of $\boldsymbol~K$-NN classifiers via constraint relaxation and randomized smoothing

More info
  • ReceivedJun 15, 2020
  • AcceptedAug 7, 2020
  • PublishedDec 21, 2020

Abstract


Funded by

国家自然科学基金(61673201,61921006)

南京大学优秀博士研究生创新能力提升计划A


References

[1] Szegedy C, Zaremba W, Sutskever I, et al. Intriguing properties of neural networks. In: Proceedings of International Conference on Learning Representations 2013. Google Scholar

[2] Goodfellow I, Shlens J, Szegedy C. Explaining and harnessing adversarial examples. In: Proceedings of International Conference on Learning Representations 2015. Google Scholar

[3] Biggio B, Roli F. Wild patterns: Ten years after the rise of adversarial machine learning. Pattern Recognition, 2018, 84: 317-331 CrossRef Google Scholar

[4] Weng T, Zhang H, Chen P, et al. Evaluating the robustness of neural networks: an extreme value theory approach. In: Proceedings of International Conference on Learning Representations 2018. Google Scholar

[5] Wong E, Kolter J Z. Provable defenses against adversarial examples via the convex outer adversarial polytope. In: Proceedings of International Conference on Machine Learning 2018. 5283--5292. Google Scholar

[6] Weng T W, Zhang H, Chen H, et al. Towards fast computation of certified robustness for relu networks. In: Proceedings of International Conference on Machine Learning 2018. 5273--5282. Google Scholar

[7] Gehr T, Mirman M, Drachsler-Cohen D, et al. Ai2: safety and robustness certification of neural networks with abstract interpretation. In: Proceedings of IEEE Symposium on Security and Privacy 2018. 3--18. Google Scholar

[8] Wang S, Pei K, Whitehouse J, et al. Efficient formal safety analysis of neural networks. In: Proceedings of Advances in Neural Information Processing Systems 2018. 6367--6377. Google Scholar

[9] Zhang H, Weng T W, Chen P Y, et al. Efficient neural network robustness certification with general activation functions. In: Proceedings of Advances in Neural Information Processing Systems 2018. 4939--4948. Google Scholar

[10] Zhang H, Zhang P, Hsieh C J. RecurJac: an efficient recursive algorithm for bounding Jacobian matrix of neural networks and its applications. In: Proceedings of AAAI Conference on Artificial Intelligence 2019. 5757--5764. Google Scholar

[11] Boiman O, Shechtman E, Irani M. In defense of nearest-neighbor based image classification. In: Proceedings of IEEE Conference on Computer Vision and Pattern Recognition 2008. 1--8. Google Scholar

[12] Weinberger K Q, Saul L K. Distance metric learning for large margin nearest neighbor classification. Journal of Machine Learning Research 2009, 10:207--244. Google Scholar

[13] Xi X, Keogh E, Shelton C, et al. Fast time series classification using numerosity reduction. In: Proceedings of International Conference on Machine Learning 2006. 1033--1040. Google Scholar

[14] Dubey A, van der Maaten L, Yalniz Z, et al. Defense against adversarial images using web-scale nearest-neighbor search. In: Proceedings of IEEE Conference on Computer Vision and Pattern Recognition 2019. 8767--8776. Google Scholar

[15] Papernot N, McDaniel P. Deep k-nearest neighbors: towards confident, interpretable and robust deep learning. 2018,. arXiv Google Scholar

[16] Wang L, Liu X, Yi J, et al. Evaluating the robustness of nearest neighbor classifiers: A primal-dual perspective. 2019,. arXiv Google Scholar

[17] Cohen J M, Rosenfeld E, Kolter J Z. Certified adversarial robustness via randomized smoothing. In: Proceedings of International Conference on Machine Learning 2019. 1310--1320. Google Scholar

[18] Lecun Y, Bottou L, Bengio Y. Gradient-based learning applied to document recognition. Proc IEEE, 1998, 86: 2278-2324 CrossRef Google Scholar

[19] Xiao H, Rasul K, Vollgraf R. Fashion-MNIST: a novel image dataset for benchmarking machine learning algorithms. 2017,. arXiv Google Scholar

[20] Papernot N, McDaniel P D, Goodfellow I J. Transferability in machine learning: from phenomena to black-box attacks using adversarial samples. 2016,. arXiv Google Scholar

[21] Sitawarin C, Wagner D. On the robustness of deep k-nearest neighbors. 2019,. arXiv Google Scholar

[22] Amsaleg L, Bailey J, Barbe D, et al. The vulnerability of learning to adversarial perturbation increases with intrinsic dimensionality. In: Proceedings of IEEE Workshop on Information Forensics and Security 2017. 1--6. Google Scholar

[23] Yang Y Y, Rashtchian C, Wang Y, et al. Robustness for non-parametric classification: a generic attack and defense. In: Proceedings of International Conference on Artificial Intelligence and Statistics 2020. Google Scholar

  • Figure 1

    (Color online) Curves of certified robust errors

  • Figure 2

    (a) Cumulative distribution function and (b) percent point function of the standard normal distribution

  • Figure 3

    (Color online) Comparison between $K$-NN and neural networks for robustness verification. (a) MNIST; protectłinebreak (b) Fashion-MNIST

  • Table 1   Certified robust errors on MNIST
    Radius $\ell_2$ Constraint relaxation ($K$-NN) Random smoothing ($K$-NN) Random smoothing (neural network)
    0 3.3 8.2 8.3
    1 29.3 24.4 30.9
    2 83.3 54.4 73.2
    3 99.6 89.9 97.6
  • Table 2   Certified robust errors on Fashion-MNIST
    Radius $\ell_2$ Constraint relaxation ($K$-NN) Random smoothing ($K$-NN) Random smoothing (neural network)
    0 14.5 19.6 26.4
    1 63.0 39.2 44.9
    2 89.3 63.6 72.1
    3 98.0 84.8 91.5