Elamur Research⌕
☰
home / papers / 2019 / Achieving Verified Robustness to Symbol Substitutions via Interval Bound Propagation

Achieving Verified Robustness to Symbol Substitutions via Interval Bound Propagation

Paper · 2019 · Po-Sen Huang, Robert Stanforth, Johannes Welbl et al.

Summary

Neural text classifiers can be fooled by small edits such as swapping a word for a synonym or flipping characters. Adversarial training and data augmentation reduce this weakness, but they cannot show that no stronger attack exists. The authors (DeepMind / UCL) instead aim to formally certify robustness. They work with word- and character-level HotFlip-style substitutions on Stanford Sentiment Treebank (SST) and AG News. Their key step is to over-approximate the set of perturbed inputs. They take the convex hull of single-substitution embeddings and scale it up to cover multiple substitutions, which gives a simplex in embedding space. Interval Bound Propagation (IBP) then pushes this simplex through the network. This yields cheap worst-case bounds that also serve as an extra training objective. Models trained this way stay close to normal models in nominal accuracy but are far more often verifiably robust. On both datasets they reach the best exhaustively verified accuracy. Exhaustive search, by contrast, shows that adversarial training gives a false sense of security. The paper is presented as the first application of verification and verifiable training to NLP.

Key points

  • The perturbation space is a dilated simplex built from single-symbol substitutions. This is much tighter than an axis-aligned box, which would allow every token to change at once.
  • IBP verification costs only two forward passes per sample, one for upper and one for lower bounds. Exhaustive search grows exponentially with the perturbation radius. For SST character-level, the maximum space in the reported test sets exceeds 1.4 million sentences.
  • With standard GloVe, bounds stay loose unless the model is trained to be IBP-verifiable.
  • Counter-fitted embeddings (Mrkšić et al., 2016; built with PPDB and WordNet) shrink the simplex. They raise the share of IBP-verified examples by up to 33.2% (normal training, radius 1), with a mild drop in nominal accuracy.
  • Limitations: only shallow CNN and fully connected models were studied. Recurrent and self-attention architectures are left for future work.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓University College LondonLondon · United Kingdom59 works · 16,463 citations

📚 Shelves 5 Computer Science · 9,086 works Artificial Intelligence · 8,889 works Arts and Humanities · 9,296 works Language and Linguistics · 9,206 works Computational Theory and Mathematics · 116 works

Cite

Cite as Po-Sen Huang, Robert Stanforth, Johannes Welbl, Chris Dyer, Dani Yogatama, Sven Gowal, Krishnamurthy Dvijotham and Pushmeet Kohli. 2019. Achieving Verified Robustness to Symbol Substitutions via Interval Bound Propagation. Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP).

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/d19-1419

@inproceedings{huang2019achieving,
  title = {{Achieving Verified Robustness to Symbol Substitutions via Interval Bound Propagation}},
  author = {Po-Sen Huang, Robert Stanforth, Johannes Welbl, Chris Dyer, Dani Yogatama, Sven Gowal, Krishnamurthy Dvijotham and Pushmeet Kohli},
  booktitle = {Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)},
  year = {2019},
  doi = {10.18653/v1/d19-1419},
  url = {https://doi.org/10.18653/v1/d19-1419}
}

References

45 references, 14 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Anish Athalye, Nicholas Carlini, and David A. Wagner. 2018. Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples. In ICML, pages 274–283. find
  2. Christel Baier and Joost-Pieter Katoen. 2008. Principles of Model Checking. MIT press. find
  3. Clark Barrett and Cesare Tinelli. 2018. Satisfiability modulo theories. In Handbook of Model Checking, pages 305–343. Springer. find
  4. Yonatan Belinkov and Yonatan Bisk. 2018. Synthetic and natural noise both break neural machine translation. In International Conference on Learning Representations. find
  5. Nicola Bertoldi, Richard Zens, and Marcello Federico. 2007. Speech translation by confusion network decoding. In Proc. ICASSP. find
  6. Rudy Bunel, Ilker Turkaslan, Philip HS Torr, Pushmeet Kohli, and M Pawan Kumar. 2017. Piecewise linear neural network verification: a comparative study. arXiv preprint arXiv:1711.00455. — [arXiv:1711.00455](https://arxiv.org/abs/1711.00455) find
  7. Nicholas Carlini, Guy Katz, Clark Barrett, and David L Dill. 2017. Ground-truth adversarial examples. arXiv preprint arXiv:1709.10207. — [arXiv:1709.10207](https://arxiv.org/abs/1709.10207) find
  8. Nicholas Carlini and David Wagner. 2017. Adversarial examples are not easily detected: Bypassing ten detection methods. In Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security, pages 3–14. ACM. find
  9. Chih-Hong Cheng, Georg Nührenberg, and Harald Ruess. 2017. Maximum resilience of artificial neural networks. In International Symposium on Automated Technology for Verification and Analysis, pages 251–268. Springer. find
  10. Minhao Cheng, Jinfeng Yi, Huan Zhang, Pin-Yu Chen, and Cho-Jui Hsieh. 2018. Seq2Sick: Evaluating the robustness of sequence-to-sequence models with adversarial examples. CoRR, abs/1803.01128. — [arXiv:1803.01128](https://arxiv.org/abs/1803.01128) find
  11. Krishnamurthy Dvijotham, Sven Gowal, Robert Stanforth, Relja Arandjelovic, Brendan O’Donoghue, Jonathan Uesato, and Pushmeet Kohli. 2018. Training verified learners with learned verifiers. arXiv preprint arXiv:1805.10265. — [arXiv:1805.10265](https://arxiv.org/abs/1805.10265) find
  12. Christopher Dyer, Smaranda Muresan, and Philip Resnik. 2008. Generalizing word lattice translation. In Proceedings of ACL-08: HLT, pages 1012– 1020, Columbus, Ohio. Association for Computational Linguistics. our card
  13. Javid Ebrahimi, Anyi Rao, Daniel Lowd, and Dejing Dou. 2018. HotFlip: White-box adversarial examples for text classification. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pages 31–36. Association for Computational Linguistics. our card
  14. Allyson Ettinger, Sudha Rao, Hal Daumé III, and Emily M. Bender. 2017. Towards linguistically generalizable NLP systems: A workshop and shared task. In Proceedings of the First Workshop on Building Linguistically Generalizable NLP Systems. find
  15. Juri Ganitkevitch, Benjamin Van Durme, and Chris Callison-Burch. 2013. PPDB: The paraphrase database. In Proceedings of the 2013 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 758–764, Atlanta, Georgia. Association for Co… our card
  16. Max Glockner, Vered Shwartz, and Yoav Goldberg. 2018. Breaking NLI systems with sentences that require simple lexical inferences. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pages 650–655, Melbourne, Australia. Association for… our card
  17. Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. 2014. Explaining and harnessing adversarial examples. arXiv preprint arXiv:1412.6572. our card
  18. Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Uesato, Relja Arandjelovic, Timothy A. Mann, and Pushmeet Kohli. 2018. On the effectiveness of interval bound propagation for training verifiably robust models. CoRR, abs/1810.12715. — [arXiv:1810.12715](https://arxiv.org/abs/1810.12715) find
  19. Matthew Honnibal and Ines Montani. 2017. spaCy 2: Natural language understanding with Bloom embeddings, convolutional neural networks and incremental parsing. To appear. find
  20. Mohit Iyyer, John Wieting, Kevin Gimpel, and Luke Zettlemoyer. 2018. Adversarial example generation with syntactically controlled paraphrase networks. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Vo… our card
  21. Robin Jia and Percy Liang. 2017. Adversarial examples for evaluating reading comprehension systems. In Empirical Methods in Natural Language Processing (EMNLP). our card
  22. Guy Katz, Clark Barrett, David L Dill, Kyle Julian, and Mykel J Kochenderfer. 2017. Reluplex: An efficient SMT solver for verifying deep neural networks. In International Conference on Computer Aided Verification, pages 97–117. Springer. find
  23. Diederik P. Kingma and Jimmy Ba. 2015. Adam: A method for stochastic optimization. International Conference on Learning Representations. find
  24. Alexey Kurakin, Ian Goodfellow, and Samy Bengio. 2016. Adversarial examples in the physical world. arXiv preprint arXiv:1607.02533. — [arXiv:1607.02533](https://arxiv.org/abs/1607.02533) find
  25. Yitong Li, Trevor Cohn, and Timothy Baldwin. 2017. Robust training under linguistic adversity. In Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics: Volume 2, Short Papers, pages 21–27. find
  26. Xunying Liu, Xie Chen, Yongqiang Wang, Mark J. F. Gales, and Philip C. Woodland. 2016. Two efficient lattice rescoring methods using recurrent neural network language models. IEEE/ACM Trans. Audio, Speech & Language Processing, 24(8):1438–1449. find
  27. Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. 2018. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations. our card
  28. George A. Miller. 1995. WordNet: A lexical database for English. Commun. ACM, 38(11):39–41. our card
  29. Matthew Mirman, Timon Gehr, and Martin Vechev. 2018. Differentiable abstract interpretation for provably robust neural networks. In Proceedings of the 35th International Conference on Machine Learning, volume 80, pages 3578–3586. find
  30. Nikola Mrkšić, Diarmuid Ó Séaghdha, Blaise Thomson, Milica Gašić, Lina M. Rojas-Barahona, Pei-Hao Su, David Vandyke, Tsung-Hsien Wen, and Steve Young. 2016. Counter-fitting word vectors to linguistic constraints. In Proceedings of the 2016 Conference of the North American Chapter of the Associ… find
  31. Takashi Onishi, Masao Utiyama, and Eiichiro Sumita. 2010. Paraphrase lattice for statistical machine translation. In Proceedings of the ACL 2010 Conference Short Papers, pages 1–5, Uppsala, Sweden. Association for Computational Linguistics. find
  32. Jeffrey Pennington, Richard Socher, and Christopher Manning. 2014. GloVe: Global vectors for word representation. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 1532–1543. Association for Computational Linguistics. our card
  33. Matthew Peters, Mark Neumann, Mohit Iyyer, Matt Gardner, Christopher Clark, Kenton Lee, and Luke Zettlemoyer. 2018. Deep contextualized word representations. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technolog… our card
  34. Aditi Raghunathan, Jacob Steinhardt, and Percy Liang. 2018. Certified defenses against adversarial examples. In International Conference on Learning Representations. find
  35. Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. 2018. Semantically equivalent adversarial rules for debugging NLP models. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 856–865. Association for Computational Linguisti… find
  36. Dinghan Shen, Guoyin Wang, Wenlin Wang, Martin Renqiang Min, Qinliang Su, Yizhe Zhang, Chunyuan Li, Ricardo Henao, and Lawrence Carin. 2018. Baseline needs more love: On simple word-embedding-based models and associated pooling mechanisms. In Proceedings of the 56th Annual Meeting of the Association… our card
  37. Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D. Manning, Andrew Ng, and Christopher Potts. 2013. Recursive deep models for semantic compositionality over a sentiment treebank. In Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, pages 1631–… find
  38. Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. 2013. Intriguing properties of neural networks. arXiv preprint arXiv:1312.6199. our card
  39. Dimitris Tsipras, Shibani Santurkar, Logan Engstrom, Alexander Turner, and Aleksander Madry. 2019. Robustness may be at odds with accuracy. In International Conference on Learning Representations. find
  40. Jonathan Uesato, Brendan O’Donoghue, Pushmeet Kohli, and Aron van den Oord. 2018. Adversarial risk and the dangers of evaluating against weak attacks. In ICML, pages 5032–5041. find
  41. Eric Wallace, Shi Feng, Nikhil Kandpal, Matt Gardner, and Sameer Singh. 2019. Universal trigger sequences for attacking and analyzing NLP. In Empirical Methods in Natural Language Processing (EMNLP). find
  42. Shiqi Wang, Kexin Pei, Justin Whitehouse, Junfeng Yang, and Suman Jana. 2018. Formal security analysis of neural networks using symbolic intervals. In 27th USENIX Security Symposium (USENIX Security 18), pages 1599–1614, Baltimore, MD. USENIX Association. find
  43. Lily Weng, Huan Zhang, Hongge Chen, Zhao Song, Cho-Jui Hsieh, Luca Daniel, Duane Boning, and Inderjit Dhillon. 2018. Towards fast computation of certified robustness for ReLU networks. In Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learni… find
  44. Eric Wong and Zico Kolter. 2018. Provable defenses against adversarial examples via the convex outer adversarial polytope. In International Conference on Machine Learning, pages 5283–5292. find
  45. Xiang Zhang, Junbo Zhao, and Yann LeCun. 2015. Character-level convolutional networks for text classification. In Advances in Neural Information Processing Systems, pages 649–657. our card

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/huang-2019-achieving-verified-robustness-symbol-substitutions/