Certified Robustness to Adversarial Word Substitutions

Robin Jia; Aditi Raghunathan; Kerem Göksel; Percy Liang

Source-linked AI summary

Certified Robustness to Adversarial Word Substitutions

Robin Jia, Aditi Raghunathan, Kerem Göksel, Percy Liang

arXiv:1909.00986v1Sep 3, 2019cs.CLcs.LG

TL;DR

NLP models can fail under exponentially many label-preserving word substitutions, and existing heuristic or augmentation methods do not provide sufficient coverage or guarantees. This paper trains certifiably robust models with Interval Bound Propagation, which bounds worst-case loss across substitutions. The models reach 75% adversarial accuracy on both IMDB and SNLI, while robustness remains limited in scope and clean accuracy declines.

Problem
NLP models are vulnerable to exponentially large families of label-preserving word substitutions, while heuristic attacks cannot exhaustively search them or guarantee robustness.
Method
The paper uses Interval Bound Propagation to compute an upper bound on worst-case loss and trains models to minimize that bound.
Results
75% adversarial accuracy is achieved on both IMDB sentiment analysis and SNLI natural language inference with certifiably robust training.
Takeaways & Limitations
Certifiably robust training provides guarantees against word-substitution perturbations for particular models and can be extended modularly to other architectures.
Takeaways & Limitations
The work is limited to word substitutions and particular models, and achieving state-of-the-art clean accuracy alongside provable robustness remains open.

Abstract

from arXiv · show

State-of-the-art NLP models can often be fooled by adversaries that apply seemingly innocuous label-preserving transformations (e.g., paraphrasing) to input text. The number of possible transformations scales exponentially with text length, so data augmentation cannot cover all transformations of an input. This paper considers one exponentially large family of label-preserving transformations, in which every word in the input can be replaced with a similar word. We train the first models that are provably robust to all word substitutions in this family. Our training procedure uses Interval Bound Propagation (IBP) to minimize an upper bound on the worst-case loss that any combination of word substitutions can induce. To evaluate models' robustness to these transformations, we measure accuracy on adversarially chosen word substitutions applied to test examples. Our IBP-trained models attain $75\%$ adversarial accuracy on both sentiment analysis on IMDB and natural language inference on SNLI. In comparison, on IMDB, models trained normally and ones trained with data augmentation achieve adversarial accuracy of only $8\%$ and $35\%$, respectively.

1 Introduction

NLP models are vulnerable to exponentially many label-preserving word substitutions, motivating guarantees rather than heuristic search or data augmentation. The paper uses IBP-based certifiable training and reaches 75% adversarial accuracy on both IMDB and SNLI.

Motivation: Adversarial examples can significantly degrade NLP performance despite preserving the input label.Reported perturbations include distracting text, paraphrases, similar-word replacements, and character-level typos.
Problem: Word substitutions create an exponentially large perturbation space because every input word may be replaced with a similar word.The substitutions are intended to preserve grammaticality and labels.
Problem: Heuristic attacks cannot guarantee robustness because exhaustive search over all perturbations is infeasible.The paper frames guaranteed robustness as a central question.
Approach: IBP computes a tractable upper bound on worst-case loss, which the paper uses to obtain robustness guarantees.A small upper bound certifies robustness to the allowed perturbations.
Results: 75% adversarial accuracy is achieved on both IMDB sentiment analysis and SNLI natural language inference with certifiably robust training.On IMDB, normal training reaches 8% and data augmentation 35%; on SNLI, they reach 41% and 71%, respectively.

2 Setup

The setup defines robustness over all examples formed by independently substituting each word with an allowed similar word. Robust loss is the worst-case loss across this exponentially large set, while interval supersets make certification tractable.

2.1 Perturbations by word substitutions: The perturbation set allows each word xi to be replaced by any word in S(x, i), including xi itself.The substitutions are chosen to preserve grammaticality and the original label.
2.1 Perturbations by word substitutions: Bperturb(z) contains every perturbed example (˜x, y) whose substituted words satisfy ˜xi ∈ S(x, i).The label y remains fixed across the perturbation set.
2.2 Robustness to all perturbations: F(z, θ) is the set of model losses over all examples in Bperturb(z).It collects one loss value for each allowed perturbation.
2.2 Robustness to all perturbations: Robust loss is the maximum loss over F(z, θ), corresponding to the worst-case allowed perturbation.Computing it directly is often intractable because words can be perturbed independently.
2.2 Robustness to all perturbations: An outer set O(z, θ) can certify robustness when its worst-case zero-one loss is zero, although loose bounds may prevent certification.The outer set contains the true loss set, so certification is sufficient but not necessary.

3 Certification via Interval Bound Propagation

The paper converts discrete word substitutions into interval bounds and propagates those bounds through neural-network operations using IBP. Training minimizes the resulting upper bound on worst-case loss, enabling scalable certification.

3 Certification via Interval Bound Propagation: IBP propagates upper and lower activation bounds through network layers until it bounds the final loss.The method is modular and can be applied to the architectures’ component operations.
3.1 Bounds for the input layer: Pre-trained word vectors can produce loose interval bounds, while a better-oriented vector space can make the box tighter.Figure 2 contrasts loose and tighter approximations of the substitution vectors’ convex hull.
3.1 Bounds for the input layer: Discrete substitution choices are relaxed into axis-aligned input boxes containing the word vectors for every allowed replacement.For each coordinate, the bounds use the smallest box containing the vectors.
3.2 Interval propagation: IBP supports bounds for affine layers, monotonic nonlinearities, multiplication, dot products, softmax, and standard classification losses.These operations cover feedforward networks, CNNs, LSTMs, and attention-based components.
3.3 Certifiably robust training: Certifiably robust training minimizes a weighted combination of ordinary loss and the IBP upper bound on final loss.The bound objective is optimized by backpropagation through modular forward-pass computations.
3.3 Certifiably robust training: The training schedule gradually enlarges the allowed input intervals and increases the robustness weight.This begins with standard training when ϵ = 0 and ends with full intervals and κ = κ⋆.
3.3 Certifiably robust training: The complete procedure computes an adversarial-loss upper bound modularly and trains models to minimize it efficiently.The approach uses backpropagation over the propagated bounds.

4 Tasks and models

Experiments cover IMDB sentiment analysis and SNLI natural language inference across several architectures. Models use word-vector encoders, with a learned transformation designed to tighten IBP bounds before certification.

Tasks: The experiments use IMDB sentiment analysis and SNLI natural language inference as evaluation tasks.IMDB classifies reviews as positive or negative; SNLI classifies premise–hypothesis pairs as entailment, contradiction, or neutral.
Models: IMDB models include bag-of-words, CNN, and bidirectional LSTM architectures trained with cross-entropy loss.The BOW model averages word vectors before a two-layer feedforward network; CNN and LSTM models average hidden states.
Models: SNLI models include bag-of-words and Decomposable Attention architectures trained with cross-entropy loss.The BOW model separately encodes the premise and hypothesis, while attention computes context-aware word representations.
Word vectors: The word vector φ(w) is produced by applying a feedforward layer to a fixed pre-trained word vector φpre(w).The pre-trained vectors are 300-dimensional GloVe representations.
Word vectors: Learning gword encourages word vectors to align so their substitution convex hull is closely approximated by an axis-aligned box.Applying gword before bound computation avoids the looser bounds caused by poorly approximated pre-trained vectors.

5 Experiments

Experiments evaluate word-substitution robustness using genetic attacks and IBP certificates across IMDB and SNLI, showing robust training substantially outperforms standard training and data augmentation while reducing clean accuracy and adding computational overhead.

5.2 Main results: 75.0% IMDB accuracy against genetic-attack perturbations was achieved by the best IBP-trained model, versus 35.2% for the best data-augmentation model.Normally trained models had adversarial accuracies below 10%.
5.2 Main results: Robust training outperformed data augmentation across many architectures and both IMDB and SNLI, especially on long IMDB inputs with many perturbable words.The evaluation used 1000 random IMDB test examples and all 9824 SNLI test examples.
5.2 Main results: 74.2% of IMDB test examples were guaranteed correct on all perturbations by the best robust model, close to its 75.0% genetic-attack accuracy.For data-augmentation models, IBP could not certify robustness on almost all examples.
5.3 Clean versus robust accuracy: 81% IMDB clean accuracy for a robust CNN was lower than the normally trained model’s 89%, demonstrating a moderate clean-accuracy trade-off.On SNLI, the corresponding BOW comparison was 79% versus 83%.
5.4 Runtime considerations: 2× to 4× longer training epochs accompanied certifiable robustness, while certificates for 1000 IMDB examples took 5 seconds versus over 3 hours for genetic attacks.IBP certificates were faster to compute at test time than genetic-attack accuracy.
5.3 Clean versus robust accuracy: Robust training reduced errors requiring many simultaneous word changes; attacks either changed a few words or failed to trigger an error.Data augmentation did not prevent errors involving many changed words.

6 Related Work and Discussion

Prior NLP robustness work documents failures under several perturbation types, while this paper develops certificates for word substitutions and identifies broader robustness challenges.

Prior work studies adversarial examples from extraneous-text insertion, word substitutions, paraphrasing, and character-level noise.
Data augmentation can help in narrow perturbation spaces but is insufficient for very large perturbation spaces.
Provable defenses have previously targeted simpler NLP models and attacks, including feature deletion and fixed attackers.
The word-substitution attack resembles L∞-bounded vision perturbations, while projected-gradient adversarial training assumes continuous inputs.
The paper provides certificates for word substitutions in particular models, while extension to sequence-to-sequence tasks, insertions, deletions, and state-of-the-art clean accuracy remains open.
The conclusion characterizes certifiable robustness as necessary but not sufficient for models that truly understand language.

A.1 Additional interval bound formulas

This appendix reviews interval bounds for affine transformations and monotonic element-wise nonlinearities, which support propagation through common network layers.

Affine transformations: Affine transformations compute output intervals from bounded inputs using the signs and magnitudes of the weights.The upper bound pairs positive weights with upper inputs and negative weights with lower inputs; the lower bound is computed analogously.
Affine transformations: The affine output interval can be computed with two inner-product evaluations, one using the weights and one using their absolute values.
Monotonic scalar functions: Monotonic scalar functions, including ReLU, sigmoid, and tanh, attain interval extrema at the corresponding input endpoints.

A.2 Numerical stability of softmax

The appendix derives numerically stable interval bounds for softmax through log-softmax and logsumexp computations, treating the target coordinate and all other coordinates separately.

The derivation rewrites the expressions so logsumexp can be evaluated stably and efficiently, including vector concatenation identities.The appendix describes normalization before exponentiation and numerically stable log1p and expm1 evaluations near zero.
Softmax bounds can be obtained from log-softmax bounds because exponentiation is monotonic.
For a target index c, the method bounds its log-softmax score from bounded vector coordinates.The setup assumes lower and upper bounds for every coordinate of the input vector.
Upper bound: The upper bound uses the target coordinate's maximum and the other coordinates' minima.
The implementation selects between two stable cases using whether the shifted quantity exceeds log 2.
Lower bound: The lower bound uses the target coordinate's minimum and the other coordinates' maxima.

A.3 Attack surface differences

The paper changes the attack surface by defining substitutions relative to the original sentence rather than the progressively altered input, and uses a faster language model with longer context.

The prior attack recomputes neighborhoods and language-model scores relative to each altered input, creating a hard-to-define attack surface and permitting repeated substitutions.
The paper pre-computes allowed substitutions from the original sentence and disallows repeated substitutions, reducing semantic drift.
The paper uses a language model with window radius W = 6, whereas the prior method uses W = 1 because its language model is slower.

A.4 Experimental details

The experiments use shared training conventions across settings, with task-specific architecture choices and preprocessing differences for IMDB and SNLI.

Models use early stopping on the development metric corresponding to each training setting.Normal, augmented, and certifiably robust models use normal, augmented, and certifiably robust development accuracy, respectively.
IMDB models are restricted to the 50,000-word counter-fitted vocabulary, and out-of-vocabulary words are deleted before input.This avoids allowing predictions to rely on words that cannot be perturbed.
SNLI BOW models use 100-dimensional hidden states with a 3-layer feedforward network, while DECOMPATTN uses 300-dimensional states and a 2-layer network.The BOW values were selected by development-set hyperparameter search; DECOMPATTN values match Parikh et al. (2016).
All training settings use the same hyperparameters, including plain, data augmentation, and robust training.
The DECOMPATTN implementation omits GloVe normalization and randomly trained out-of-vocabulary vectors, while training a learned null-token vector.
Dropout probability is 0.1, and the intra-sentence attention module is not used.

A.5 Training schedule

Training gradually expands the certified perturbation objective, with the schedule affecting development-set certified accuracy.

Slowly increasing ϵ is important for good performance, while slowly increasing κ is slightly worse than holding κ = κ* fixed.Results are reported as certified accuracy on 1,000 randomly selected IMDB development examples.

A.6 Word vector bound sizes

Robust training produces tighter interval bounds around word-substitution neighborhoods than pretrained vectors and normal training in most tested cases.

The bound-width quantity measures average IBP-box width for a word and its neighbors, normalized by vocabulary-wide coordinate standard deviations.It compares neighborhoods under pretrained vectors φpre(·) and transformed vectors φ(·).
78.2% of words with |N(w)| > 1 had smaller normalized interval-bound widths for robustly trained transformed vectors than for GloVe vectors.The comparison uses a CNN trained robustly on IMDB.
54.5% of words had smaller normalized interval-bound widths under normal training than with GloVe vectors.This was lower than the robust-training result.
The same robust-training pattern was observed across other model architectures.

A.7 Certifying long-term memory

A robustly trained LSTM can certify a long-term memory task requiring it to preserve the first word across many intervening positions.

100% certified accuracy was achieved on 1,000 test examples in the toy long-term memory task.The LSTM was trained on 4,000 randomly generated examples with sequence lengths uniformly sampled from 3 to 10.
The task labels a sequence 1 when its first and last words match and 0 otherwise, while allowing every middle word to be replaced.Solving it requires remembering the first word; a bag-of-words model cannot do so.
The training schedule uses 50 epochs of normal training, 50 epochs increasing ϵ toward 1 and κ toward 0.5, then 17 final epochs with those values.The authors report that pretraining without the certified objective avoids bad local optima.
Each epoch in this toy experiment corresponds to many fewer parameter updates than an epoch on IMDB or SNLI.

B Adversarial examples

The examples show that word substitutions can alter model predictions while preserving the review’s apparent sentiment, across normally trained, certifiably robust, and augmented models.

Adversarial failures: Normally trained examples include adversarial changes that can replace semantically similar wording while changing the model’s prediction.The examples include substitutions such as “discovered” for “found” and “seemed supremely dorky” for “looked very cheesy.”
Label-preserving substitutions: A certifiably robust model example preserves a positive label after small wording changes in a review.The perturbations change wording while leaving the review’s recommendation and positive label intact.
Label-preserving substitutions: Several perturbed reviews retain their original labels despite substitutions such as “neglects” for “fails” and “laughed” for “laugh.”These examples concern positive and negative movie reviews whose stated correct labels remain unchanged after perturbation.