Assessing Robustness of Text Classification through Maximal Safe Radius Computation

Emanuele La Malfa, Min Wu, Luca Laurenti, Benjie Wang, Anthony Hartshorn, Marta Kwiatkowska

Abstract

Neural network NLP models are vulnerable to small modifications of the input that maintain the original meaning but result in a different prediction. In this paper, we focus on robustness of text classification against word substitutions, aiming to provide guarantees that the model prediction does not change if a word is replaced with a plausible alternative, such as a synonym. As a measure of robustness, we adopt the notion of the maximal safe radius for a given input text, which is the minimum distance in the embedding space to the decision boundary. Since computing the exact maximal safe radius is not feasible in practice, we instead approximate it by computing a lower and upper bound. For the upper bound computation, we employ Monte Carlo Tree Search in conjunction with syntactic filtering to analyse the effect of single and multiple word substitutions. The lower bound computation is achieved through an adaptation of the linear bounding techniques implemented in tools CNN-Cert and POPQORN, respectively for convolutional and recurrent network models. We evaluate the methods on sentiment analysis and news classification models for four datasets (IMDB, SST, AG News and NEWS) and a range of embeddings, and provide an analysis of robustness trends. We also apply our framework to interpretability analysis and compare it with LIME.

Introduction

Deep neural networks in Natural Language Processing (NLP) are notoriously "brittle." A model might correctly classify a movie review as positive, but if you swap the word "excellent" for its synonym "prime," the model might suddenly flip its prediction to negative. These are called adversarial examples. While many researchers focus on finding these "attacks," there is a lack of tools to provide formal guarantees—mathematical proof that a model's prediction cannot change within a certain range of perturbations. This paper tackles the gap between empirical "best-effort" attacks and the need for provable safety in text classification by introducing a framework to compute the Maximal Safe Radius (MSR).

Methodology

The MSR represents the minimum distance in the embedding space a word can move before the model changes its prediction. Because computing the exact MSR is an NP-hard problem, the authors propose a dual-bounding approach to approximate it.

Conceptual illustration of the Maximal Safe Radius (MSR) and its dual bounds in the embedding space.

Dual-Bounding Approach

  1. Lower Bound (Guaranteed Robustness): The authors adapt linear bounding techniques originally designed for image recognition—specifically CNN-Cert (for Convolutional Neural Networks) and POPQORN (for Recurrent Neural Networks). These methods use interval arithmetic to propagate a "box" of possible values through the network to prove that the output class remains invariant within a certified radius.
  2. Upper Bound (Adversarial Search): To find the smallest possible change that does break the model, they adapt Monte Carlo Tree Search (MCTS). To ensure the resulting text remains "plausible" and grammatically correct, they employ syntactic filtering to only allow substitutions of the same part-of-speech.

Experimental Analysis

The framework was evaluated on four standard text classification benchmarks: IMDB, SST, AG News, and NEWS. They tested these across various word embeddings, including Keras Custom, GloVe, and GloVeTwitter, with varying dimensionalities (from 5d to 100d).

Key Insights

  • Architecture Matters: Recurrent models (LSTMs) are significantly less robust to changes at the beginning of a sentence. Because LSTMs process text sequentially, a perturbation in the first few words propagates and amplifies through the entire hidden state. CNNs, which look at local regions, do not suffer from this specific "early-word" vulnerability.
  • The Dimensionality Trade-off: Increasing the dimensionality of word embeddings generally decreases robustness. In higher-dimensional spaces, there are more "directions" for an adversarial attack to find a path to the decision boundary.
  • Counter-fitting for Safety: "Counter-fitting"—a technique that forces synonyms to be close and antonyms to be far apart in embedding space—effectively doubles the lower bound of robustness for low-dimensional models.

Interpretability and Saliency

Beyond robustness quantification, the MSR serves as a saliency measure. If a word has a very small MSR, it means the model is highly sensitive to that word, making it a "key" feature for the classification.

MSR-based saliency maps identifying influential words for model interpretability.

The authors show that MSR-based saliency maps can identify influential words that popular tools like LIME miss. Because MSR accounts for the non-linearity of the decision boundary rather than just a local linear approximation, it captures deeper model sensitivities.

Conclusion

This paper provides a rigorous way to certify NLP models against adversarial word substitutions. While the current focus is on CNNs and LSTMs, extending this framework to more complex, attention-based architectures like Transformers (BERT, GPT) is a crucial next step. Additionally, future work will need to address the computational cost of formal verification and improve the capture of semantic nuances in adversarial search.

Summary updated

Abstract

Neural network NLP models are vulnerable to small modifications of the input that maintain the original meaning but result in a different prediction. In this paper, we focus on robustness of text classification against word substitutions, aiming to provide guarantees that the model prediction does not change if a word is replaced with a plausible alternative, such as a synonym. As a measure of robustness, we adopt the notion of the maximal safe radius for a given input text, which is the minimum distance in the embedding space to the decision boundary. Since computing the exact maximal safe radius is not feasible in practice, we instead approximate it by computing a lower and upper bound. For the upper bound computation, we employ Monte Carlo Tree Search in conjunction with syntactic filtering to analyse the effect of single and multiple word substitutions. The lower bound computation is achieved through an adaptation of the linear bounding techniques implemented in tools CNN-Cert and POPQORN, respectively for convolutional and recurrent network models. We evaluate the methods on sentiment analysis and news classification models for four datasets (IMDB, SST, AG News and NEWS) and a range of embeddings, and provide an analysis of robustness trends. We also apply our framework to interpretability analysis and compare it with LIME.
BibTeX
@inproceedings{malfa2020assessing,
  author = {Emanuele La Malfa and Min Wu and Luca Laurenti and Benjie Wang and Anthony Hartshorn and Marta Kwiatkowska},
  title = {{Assessing Robustness of Text Classification through Maximal Safe Radius Computation}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2020},
  url = {https://openreview.net/forum?id=-pakLXoxZ_},
}
Figure