Assessing Robustness of Text Classification through Maximal Safe Radius Computation

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

Abstract: Emanuele La Malfa, Min Wu, Luca Laurenti, Benjie Wang, Anthony Hartshorn, Marta Kwiatkowska. Findings of the Association for Computational Linguistics: EMNLP 2020.

2020.

Introduction

Deep Neural Networks (DNNs) have become the standard for Natural Language Processing (NLP) tasks, yet they remain notoriously brittle. A sentiment analysis model might correctly label a movie review as "positive," but changing a single word like "excellent" to its synonym "great" can cause the prediction to flip to "negative." While the computer vision community has established rigorous methods to measure such sensitivity (robustness), NLP faces unique challenges due to the discrete nature of text and the need for adversarial swaps to maintain semantic and syntactic coherence.

This paper addresses the gap in formal robustness guarantees for NLP. Rather than merely identifying individual adversarial attacks, the authors propose a framework to quantify the Maximal Safe Radius (MSR)—the minimum distance an input can move in embedding space before its classification changes. By defining this "safe zone," the researchers provide a rigorous way to evaluate model reliability against word substitutions.

Methodology: Computing the Maximal Safe Radius

Calculating the exact MSR is an NP-hard problem. To overcome this, the authors "sandwich" the true value between a formal lower bound (guaranteed safety) and an empirical upper bound (vulnerability via search).

Conceptual illustration of the Maximal Safe Radius (MSR) showing the decision boundary, the certified lower bound (Safe N-Ball), and the empirical upper bound.

Formal Lower Bounds

The authors adapt linear bounding techniques, specifically CNN-Cert and POPQORN, to the NLP domain. These tools use interval arithmetic to propagate a "box" of possible perturbations through the network layers. If the entire box remains on one side of the decision boundary, the model is certified robust within that radius. This provides a mathematical guarantee that no plausible word substitution within that distance can flip the model's prediction.

Empirical Upper Bounds via MCTS

To find the smallest perturbation that does flip the label, the framework employs Monte Carlo Tree Search (MCTS). The algorithm treats word substitutions as moves in a game, systematically searching for the most "urgent" words to change to find a successful adversarial example.

The MCTS framework treats word substitutions as a tree search problem to find the smallest perturbation that triggers a classification flip.

To ensure these substitutions are plausible, the authors implement syntactic filtering using Part-of-Speech (POS) tagging and NLTK, preventing replacements that would break the sentence's grammatical structure.

Key Insights and Results

The framework was evaluated on standard benchmarks (IMDB, SST, AG News, NEWS) using CNN and LSTM architectures with various embeddings like GloVe and custom Keras embeddings. Several critical insights emerged:

  • The Dimensionality Trap: Robustness generally decreases as the dimensionality of word embeddings increases. Higher-dimensional spaces offer more "directions" for adversarial attacks to find vulnerabilities in the decision boundary.
  • LSTM Sequence Sensitivity: LSTMs were found to be significantly less robust to perturbations at the beginning of a sentence. Because LSTMs process sequences step-by-step, early changes are amplified through hidden states. In contrast, CNNs treat regions more locally and are less prone to this specific vulnerability.
  • Embedding Polarity: For sentiment tasks, "polarity-constrained" embeddings—which explicitly group synonyms like "good" and "excellent" together—proved more robust than general-purpose embeddings like GloVe.
  • Interpretability: The MSR can serve as a saliency tool. By identifying which words have the smallest safe radius, researchers can create saliency maps. Unlike LIME, which uses linear approximations, the MSR approach accounts for the non-linearities of the model's decision boundary, often identifying influential punctuation or subtle modifiers that other methods miss.

In practical testing on the IMDB dataset, the framework achieved a normalized lower bound of 0.055, providing a formal safety guarantee for single-word substitutions within that radius. Conversely, the MCTS upper bound search was highly effective, finding successful single-word substitutions for 96.5% of tested texts in the NEWS dataset using GloVe 50d embeddings.

Conclusion and Future Work

While the MSR framework provides a rigorous foundation for assessing NLP robustness, challenges remain. Maintaining perfect semantic coherence during substitutions is an ongoing difficulty. Furthermore, while the current work focuses on CNNs and LSTMs, extending these interval-based bounding techniques to the complex internal dynamics of Transformer-based models is a crucial next step for the field. Despite the computational cost of formal certification, this approach offers a vital tool for safety-critical NLP applications where model reliability is paramount.

Summary updated

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