Certified Robustness to Adversarial Word Substitutions

Introduction

Machine learning models have achieved impressive accuracy on many NLP tasks, but they are surprisingly brittle. Adding distracting text to the input Jia and Liang (2017), paraphrasing the text Iyyer et al. (2018); Ribeiro et al. (2018), replacing words with similar words Alzantot et al. (2018), or inserting character-level “typos” Belinkov and Bisk (2017); Ebrahimi et al. (2017) can significantly degrade a model’s performance. Such perturbed inputs are called adversarial examples, and have shown to break models in other domains as well, most notably in vision Szegedy et al. (2014); Goodfellow et al. (2015). Since humans are not fooled by the same perturbations, the widespread existence of adversarial examples exposes troubling gaps in models’ understanding.

In this paper, we focus on the word substitution perturbations of Alzantot et al. (2018). In this setting, an attacker may replace every word in the input with a similar word (that ought not to change the label), leading to an exponentially large number of possible perturbations. Figure 1 shows an example of these word substitutions. As demonstrated by a long line of work in computer vision, it is challenging to make models that are robust to very large perturbation spaces, even when the set of perturbations is known at training time Goodfellow et al. (2015); Athalye et al. (2018); Raghunathan et al. (2018); Wong and Kolter (2018).

Our paper addresses two key questions. First, is it possible to guarantee that a model is robust against all adversarial perturbations of a given input? Existing methods that use heuristic search to attack models Ebrahimi et al. (2017); Alzantot et al. (2018) are slow and cannot provide guarantees of robustness, since the space of possible perturbations is too large to search exhaustively. We obtain guarantees by leveraging Interval Bound Propagation (IBP), a technique that was previously applied to feedforward networks and CNNs in computer vision Dvijotham et al. (2018). IBP efficiently computes a tractable upper bound on the loss of the worst-case perturbation. When this upper bound on the worst-case loss is small, the model is guaranteed to be robust to all perturbations, providing a certificate of robustness. To apply IBP to NLP settings, we derive new interval bound formulas for multiplication and softmax layers, which enable us to compute IBP bounds for LSTMs Hochreiter and Schmidhuber (1997) and attention layers Bahdanau et al. (2015). We also extend IBP to handle discrete perturbation sets, rather than the continuous ones used in vision.

Second, can we train models that are robust in this way? Data augmentation can sometimes mitigate the effect of adversarial examples Jia and Liang (2017); Belinkov and Bisk (2017); Ribeiro et al. (2018); Liu et al. (2019), but it is insufficient when considering very large perturbation spaces Alzantot et al. (2018). Adversarial training strategies from computer vision (Madry et al., 2018) rely on gradient information, and therefore do not extend to the discrete perturbations seen in NLP. We instead use certifiably robust training, in which we train models to optimize the IBP upper bound Dvijotham et al. (2018).

We evaluate certifiably robust training on two tasks—sentiment analysis on the IMDB dataset (Maas et al., 2011) and natural language inference on the SNLI dataset (Bowman et al., 2015). Across various model architectures (bag-of-words, CNN, LSTM, and attention-based), certifiably robust training consistently yields models which are provably robust to all perturbations on a large fraction of test examples. A normally-trained model has only $8\%$ and $41\%$ accuracy on IMDB and SNLI, respectively, when evaluated on adversarially perturbed test examples. With certifiably robust training, we achieve $75\%$ adversarial accuracy for both IMDB and SNLI. Data augmentation fares much worse than certifiably robust training, with adversarial accuracies falling to $35\%$ and $71\%$, respectively.

Setup

2 Robustness to all perturbations

Let $\mathcal{F}(z,\theta)$ denote the set of losses of the network on the set of perturbed examples defined in (1):

We define the robust loss as $\max\mathcal{F}(z,\theta)$, the loss due to worst-case perturbation. A model is robust at $z$ if it classifies all inputs in the perturbation set correctly, i.e., the robust zero-one loss $\max\mathcal{F}^{\text{0-1}}(z,\theta)=0$. Unfortunately, the robust loss is often intractable to compute, as each word can be perturbed independently. For example, reviews in the IMDB dataset (Maas et al., 2011) have a median of $10^{31}$ possible perturbations and max of $10^{271}$, far too many to enumerate. We instead propose a tractable upper bound by constructing a set $\mathcal{O}(z,\theta)\supseteq\mathcal{F}(z,\theta)$. Note that

Therefore, whenever $\max\mathcal{O}^{\text{0-1}}(z,\theta)=0$, this fact is sufficient to certify robustness to all perturbed examples $B_{\text{perturb}}({z})$. However, since $\mathcal{O}^{\text{0-1}}(z,\theta)\supseteq\mathcal{F}^{\text{0-1}}(z,\theta)$, the model could be robust even if $\max\mathcal{O}^{\text{0-1}}(z,\theta)\neq 0$.

Certification via Interval Bound Propagation

We now show how to use Interval Bound Propagation (IBP) Dvijotham et al. (2018) to obtain a superset $\mathcal{O}(z,\theta)$ of the losses of perturbed inputs $\mathcal{F}(z,\theta)$, given $z$, $\theta$, and $B_{\text{perturb}}({z})$. For notational convenience, we drop $z$ and $\theta$. The key idea is to compute upper and lower bounds on the activations in each layer of the network, in terms of bounds computed for previous layers. These bounds propagate through the network, as in a standard forward pass, until we obtain bounds on the final output, i.e., the loss $f$. While IBP bounds may be loose in general, Section 5.2 shows that training networks to minimize the upper bound on $f$ makes these bounds much tighter Gowal et al. (2018); Raghunathan et al. (2018).

We now discuss how to compute interval bounds for NLP models and word substitution perturbations. We obtain interval bounds for model inputs given $B_{\text{perturb}}({z})$ (Section 3.1), then show how to compute $\mathcal{O}^{i}$ from $\mathcal{O}^{\text{dep(i)}}$ for elementary operations used in standard NLP models (Section 3.2). Finally, we use these bounds to certify robustness and train robust models.

Figure 2 illustrates these bounds. We can view this as relaxing a set of discrete points to a convex set that contains all of the points. Section 4.2 discusses modeling choices to make this box tighter.

2 Interval bounds for elementary functions

Next, we describe how to compute the interval of a node $i$ from intervals of its dependencies. Gowal et al. (2018) show how to efficiently compute interval bounds for affine transformations (i.e., linear layers) and monotonic elementwise nonlinearities (see Appendix 3). This suffices to compute interval bounds for feedforward networks and CNNs. However, common NLP model components like LSTMs and attention also rely on softmax (for attention), element-wise multiplication (for LSTM gates), and dot product (for computing attention scores). We show how to compute interval bounds for these new operations. These building blocks can be used to compute interval bounds not only for LSTMs and attention, but also for any model that uses these elementary functions.

The softmax function is often used to convert activations into a probability distribution, e.g., for attention. Gowal et al. (2018) uses unnormalized logits and does not handle softmax operations. Formally, let $z^{\text{res}}$ represent the normalized score of the word at position $c$. We have $z^{\text{res}}=\frac{\exp(z^{\text{dep}}_{c})}{\sum_{j=1}^{m}\exp(z^{\text{dep}}_{j})}$. The value of $z^{\text{res}}$ is largest when $z^{\text{dep}}_{c}$ takes its largest value and all other words take the smallest value:

Element-wise multiplication and dot product.

Propagating intervals through multiplication nodes therefore requires four multiplications.

Dot products between activations are often used to compute attention scores.This is distinct from an affine transformation, because both vectors have associated bounds; in an affine layer, the input has bounds, but the weight matrix is fixed. The dot product $(z^{\text{dep}}_{1})^{\top}z^{\text{dep}}_{2}$ is just the sum of the element-wise product $z^{\text{dep}}_{1}\odot z^{\text{dep}}_{2}$. Therefore, we can bound the dot product by summing the bounds on each element of $z^{\text{dep}}_{1}\odot z^{\text{dep}}_{2}$, using the formula for element-wise multiplication.

3 Final layer

Classification models typically output a single logit for binary classification, or $k$ logits for $k$-way classification. The final loss $f(z,\theta)$ is a function of the logits $s(x)$. For standard loss functions, we can represent this function in terms of element-wise monotonic functions (Appendix 3) and the elementary functions described in Section 3.2.

Cross entropy: For multi-class, $f(z,\theta)=\text{softmax}(s(x))$. In the binary case, $f(z,\theta)=\sigma(s(x))$, where the sigmoid function $\sigma$ is monotonic.

4 Certifiably Robust Training with IBP

Finally, we describe certifiably robust training, in which we encourage robustness by minimizing the upper bound on the worst-case loss Dvijotham et al. (2018); Gowal et al. (2018). Recall that for an example $z$ and parameters $\theta$, $u^{\text{final}}(z,\theta)$ is the upper bound on the loss $f(z,\theta)$. Given a dataset $D$, we optimize a weighted combination of the normal loss and the upper bound $u^{\text{final}}$,

where $0\leq\kappa\leq 1$ is a scalar hyperparameter.

As described above, we compute $u^{\text{final}}$ in a modular fashion: each layer has an accompanying function that computes bounds on its outputs given bounds on its inputs. Therefore, we can easily apply IBP to new architectures. Bounds propagate through layers via forward passes, so the entire objective (7) can be optimized via backpropagation.

Standard training corresponds to $\epsilon=0$. We train for $T^{\text{init}}$ epochs while linearly increasing $\epsilon$ from to $1$, and also increasing $\kappa$ from up to a maximum value of $\kappa^{\star}$, We then train for an additional $T^{\text{final}}$ epochs at $\kappa=\kappa^{\star}$ and $\epsilon=1$.

To summarize, we use IBP to compute an upper bound on the model’s loss when given an adversarially perturbed input. This bound is computed in a modular fashion. We efficiently train models to minimize this bound via backpropagation.

Tasks and models

Now we describe the tasks and model architectures on which we run experiments. These models are all built from the primitives in Section 3.

Following Alzantot et al. (2018), we evaluate on two standard NLP datasets: the IMDB sentiment analysis dataset (Maas et al., 2011) and the Stanford Natural Language Inference (SNLI) dataset (Bowman et al., 2015). For IMDB, the model is given a movie review and must classify it as positive or negative. For SNLI, the model is given two sentences, a premise and a hypothesis, and is asked whether the premise entails, contradicts, or is neutral with respect to the hypothesis. For SNLI, the adversary is only allowed to change the hypothesis, as in Alzantot et al. (2018), though it is possible to also allow changing the premise.

2 Models

We implemented three models for IMDB. The bag-of-words model (BoW) averages the word vectors for each word in the input, then passes this through a two-layer feedforward network with $100$-dimensional hidden state to obtain a final logit. The other models are similar, except they run either a CNN or bidirectional LSTM on the word vectors, then average their hidden states. All models are trained on cross entropy loss.

SNLI

We implemented two models for SNLI. The bag-of-words model (BoW) encodes the premise and hypothesis separately by summing their word vectors, then feeds the concatenation of these encodings to a 3-layer feedforward network. We also reimplement the Decomposable Attention model Parikh et al. (2016), which uses attention between the premise and hypothesis to compute richer representations of each word in both sentences. These context-aware vectors are used in the same way BoW uses the original word vectors to generate the final prediction. Both models are trained on cross entropy loss. Implementation details are provided in Appendix A.4.

Word vector layer.

The choice of word vectors affects the tightness of our interval bounds. We choose to define the word vector $\phi(w)$ for word $w$ as the output of a feedforward layer applied to a fixed pre-trained word vector $\phi^{\text{pre}}(w)$:

where $g^{\text{word}}$ is a learned linear transformation. Learning $g^{\text{word}}$ with certifiably robust training encourages it to orient the word vectors so that the convex hull of the word vectors is close to an axis-aligned box. Note that $g^{\text{word}}$ is applied before bounds are computed via (4). Equation (4) must be applied before the model can combine information from multiple words, but it can be delayed until after processing each word independently. Applying $g^{\text{word}}$ after the bound calculation would result in looser interval bounds, since the original word vectors $\phi^{\text{pre}}(w)$ might be poorly approximated by interval bounds (e.g., Figure 2a), compared to $\phi(w)$ (e.g., Figure 2b). Section 5.7 confirms the importance of adding $g^{\text{word}}$. We use $300$-dimensional GloVe vectors (Pennington et al., 2014) as our $\phi^{\text{pre}}(w)$.

Experiments

We make three modifications to this approach. First, in Alzantot et al. (2018), the adversary applies substitutions one at a time, and the neighborhoods and language model scores are computed relative to the current altered version of the input. This results in a hard-to-define attack surface, as changing one word can allow or disallow changes to other words. It also requires recomputing language model scores at each iteration of the genetic attack, which is inefficient. Moreover, the same word can be substituted multiple times, leading to semantic drift. We define allowed substitutions relative to the original sentence $x$, and disallow repeated substitutions. Second, we use a faster language model that allows us to query longer contexts; Alzantot et al. (2018) use a slower language model and could only query it with short contexts. Finally, we use the language model constraint only at test time; the model is trained against all perturbations in $N(w)$. This encourages the model to be robust to a larger space of perturbations, instead of specializing for the particular choice of language model. See Appendix A.3 for further details.

Analysis of word neighbors.

One natural question is whether we could guarantee robustness by having the model treat all neighboring words the same. We could construct equivalence classes of words from the transitive closure of $N(w)$, and represent each equivalence class with one embedding. We found that this would lose a significant amount of information. Out of the 50,000 word vocabulary, 19,122 words would be in the same equivalence class, including the words “good”, “bad”, “excellent”, and “terrible.” Of the remaining words, 24,389 ($79\%$) have no neighbors.

Baseline training methods.

Evaluation of robustness.

Certified accuracy: To complement this upper bound, we use IBP to obtain a tractable lower bound on the robust accuracy. Recall from Section 3.3 that we can use IBP to get an upper bound on the zero-one loss. From this, we obtain a lower bound on the robust accuracy by measuring the fraction of test examples for which the zero-one loss is guaranteed to be .

Experimental details.

For IMDB, we split the official train set into train and development subsets, putting reviews for different movies into different splits (matching the original train/test split). For SNLI, we use the official train/development/test split. We tune hyperparameters on the development set for each dataset. Hyperparameters are reported in Appendix A.4.

2 Main results

Table 1 and Table 2 show our main results for IMDB and SNLI, respectively. We measure accuracy on perturbations found by the genetic attack (upper bound on robust accuracy) and IBP-certified accuracy (lower bound on robust accuracy) on $1000$ random test examples from IMDB,We downsample the test set because the genetic attack is slow on IMDB, as inputs can be hundreds of words long. and all $9824$ test examples from SNLI. Across many architectures, our models are more robust to perturbations than ones trained with data augmentation. This effect is especially pronounced on IMDB, where inputs can be hundreds of words long, so many words can be perturbed. On IMDB, the best IBP-trained model gets $75.0\%$ accuracy on perturbations found by the genetic attack, whereas the best data augmentation model gets $35.2\%$. Normally trained models are even worse, with adversarial accuracies below $10\%$.

Certifiably robust training yields models with tight guarantees on robustness—the upper and lower bounds on robust accuracy are close. On IMDB, the best model is guaranteed to be correct on all perturbations of $74.2\%$ of test examples, very close to the $75.0\%$ accuracy against the genetic attack. In contrast, for data augmentation models, the IBP bound cannot guarantee robustness on almost all examples. It is possible that a stronger attack (e.g., exhaustive search) could further lower the accuracy of these models, or that the IBP bounds are loose.

LSTM models can be certified with IBP, though they fare worse than other models. IBP bounds may be loose for RNNs because of their long computation paths, along which looseness of bounds can get amplified. Nonetheless, in Appendix A.7, we show on synthetic data that robustly trained LSTMs can learn long-range dependencies.

3 Clean versus robust accuracy

Robust training does cause a moderate drop in clean accuracy (accuracy on unperturbed test examples) compared with normal training. On IMDB, our normally trained CNN model gets $89\%$ clean accuracy, compared to $81\%$ for the robustly trained model. We also see a drop on SNLI: the normally trained BoW model gets $83\%$ clean accuracy, compared to $79\%$ for the robustly trained model. Similar drops in clean accuracy are also seen for robust models in vision Madry et al. (2017). For example, the state-of-the-art robust model on CIFAR10 Zhang et al. (2019) only has $85\%$ clean accuracy, but comparable normally-trained models get $>96\%$ accuracy.

We found that the robustly trained models tend to underfit the training data—on IMDB, the CNN model gets only $86\%$ clean training accuracy, lower than the test accuracy of the normally trained model. The model continued to underfit when we increased either the depth or width of the network. One possible explanation is that the attack surface adds a lot of noise, though a large enough model should still be able to overfit the training set. Better optimization or a tighter way to compute bounds could also improve training accuracy. We leave further exploration to future work.

Next, we analyzed the trade-off between clean and robust accuracy by varying the importance placed on perturbed examples during training. We use accuracy against the genetic attack as our proxy for robust accuracy, rather than IBP-certified accuracy, as IBP bounds may be loose for models that were not trained with IBP. For data augmentation, we vary $K$, the number of augmented examples per real example, from $1$ to $64$. For certifiably robust training, we vary $\kappa^{\star}$, the weight of the certified robustness training objective, between $0.01$ and $1.0$. Figure 3 shows trade-off curves for the CNN model on $1000$ random IMDB development set examples. Data augmentation can increase robustness somewhat, but cannot reach very high adversarial accuracy. With certifiably robust training, we can trade off some clean accuracy for much higher robust accuracy.

4 Runtime considerations

IBP enables efficient computation of $u^{\text{final}}(z,\theta)$, but it still incurs some overhead. Across model architectures, we found that one epoch of certifiably robust training takes between $2\times$ and $4\times$ longer than one epoch of standard training. On the other hand, IBP certificates are much faster to compute at test time than genetic attack accuracy. For the robustly trained CNN IMDB model, computing certificates on $1000$ test examples took 5 seconds, while running the genetic attack on those same examples took over 3 hours.

5 Error analysis

We examined development set examples on which models were correct on the original input but incorrect on the perturbation found by the genetic attack. We refer to such cases as robustness errors. We focused on the CNN IMDB models trained normally, robustly, and with data augmentation. We found that robustness errors of the robustly trained model mostly occurred when it was not confident in its original prediction. The model had $>70\%$ confidence in the correct class for the original input in only $14\%$ of robustness errors. In contrast, the normally trained and data augmentation models were more confident on their robustness errors; they had $>70\%$ confidence on the original example in $92\%$ and $87\%$ of cases, respectively.

We next investigated how many words the genetic attack needed to change to cause misclassification, as shown in Figure 4. For the normally trained model, some robustness errors involved only a couple changed words (e.g., “I’ve finally found a movie worse than …” was classified negative, but the same review with “I’ve finally discovered a movie worse than…” was classified positive), but more changes were also common (e.g., part of a review was changed from “The creature looked very cheesy” to “The creature seemed supremely dorky”, with $15$ words changed in total). Surprisingly, certifiably robust training nearly eliminated robustness errors in which the genetic attack had to change many words: the genetic attack either caused an error by changing a couple words, or was unable to trigger an error at all. In contrast, data augmentation is unable to cover the exponentially large space of perturbations that involve many words, so it does not prevent errors caused by changing many words.

6 Training schedule

We investigated the importance of slowly increasing $\epsilon$ during training, as suggested by Gowal et al. (2018). Fixing $\epsilon=1$ during training led to a $5$ point reduction in certified accuracy for the CNN. On the other hand, we found that holding $\kappa$ fixed did not hurt accuracy, and in fact may be preferable. More details are shown in Appendix A.5.

7 Word vector analysis

We determined the importance of the extra feedforward layer $g^{\text{word}}$ that we apply to pre-trained word vectors, as described in Section 4.2. We compared with directly using pre-trained word vectors, i.e. $\phi(w)=\phi^{\text{pre}}(w)$. We also tried using $g^{\text{word}}$ but applying interval bounds on $\phi^{\text{pre}}(w)$, then computing bounds on $\phi(w)$ with the IBP formula for affine layers. In both cases, we could not train a CNN to achieve more than $52.2\%$ certified accuracy on the development set. Thus, transforming pre-trained word vectors and applying interval bounds after is crucial for robust training. In Appendix A.6, we show that robust training makes the intervals around transformed word vectors smaller, compared to the pre-trained vectors.

Related Work and Discussion

Recent work on adversarial examples in NLP has proposed various classes of perturbations, such as insertion of extraneous text Jia and Liang (2017), word substitutions Alzantot et al. (2018), paraphrasing Iyyer et al. (2018); Ribeiro et al. (2018), and character-level noise Belinkov and Bisk (2017); Ebrahimi et al. (2017). These works focus mainly on demonstrating models’ lack of robustness, and mostly do not explore ways to increase robustness beyond data augmentation. Data augmentation is effective for narrow perturbation spaces Jia and Liang (2017); Ribeiro et al. (2018), but only confers partial robustness in other cases Iyyer et al. (2018); Alzantot et al. (2018). Ebrahimi et al. (2017) tried adversarial training Goodfellow et al. (2015) for character-level perturbations, but could only use a fast heuristic attack at training time, due to runtime considerations. As a result, their models were still be fooled by running a more expensive search procedure at test time.

Provable defenses have been studied for simpler NLP models and attacks, particularly for tasks like spam detection where real-life adversaries try to evade detection. Globerson and Roweis (2006) train linear classifiers that are robust to adversarial feature deletion. Dalvi et al. (2004) analyzed optimal strategies for a Naive Bayes classifier and attacker, but their classifier only defends against a fixed attacker that does not adapt to the model.

Recent work in computer vision (Szegedy et al., 2014; Goodfellow et al., 2015) has sparked renewed interest in adversarial examples. Most work in this area focuses on $L_{\infty}$-bounded perturbations, in which each input pixel can be changed by a small amount. The word substitution attack model we consider is similar to $L_{\infty}$ perturbations, as the adversary can change each input word by a small amount. Our work is inspired by work based on convex optimization Raghunathan et al. (2018); Wong and Kolter (2018) and builds directly on interval bound propagation Dvijotham et al. (2018); Gowal et al. (2018), which has certified robustness of computer vision models to $L_{\infty}$ attacks. Adversarial training via projected gradient descent (Madry et al., 2018) has also been shown to improve robustness, but assumes that inputs are continuous. It could be applied in NLP by relaxing sets of word vectors to continuous regions.

This work provides certificates against word substitution perturbations for particular models. Since IBP is modular, it can be extended to other model architectures on other tasks. It is an open question whether IBP can give non-trivial bounds for sequence-to-sequence tasks like machine translation (Belinkov and Bisk, 2017; Michel et al., 2019). In principle, IBP can handle character-level typos Ebrahimi et al. (2017); Pruthi et al. (2019), though typos yield more perturbations per word than we consider in this work. We are also interested in handling word insertions and deletions, rather than just substitutions. Finally, we would like to train models that get state-of-the-art clean accuracy while also being provably robust; achieving this remains an open problem.

In conclusion, state-of-the-art NLP models are accurate on average, but they still have significant blind spots. Certifiably robust training provides a general, principled mechanism to avoid such blind spots by encouraging models to make correct predictions on all inputs within some known perturbation neighborhood. This type of robustness is a necessary (but not sufficient) property of models that truly understand language. We hope that our work is a stepping stone towards models that are robust against an even wider, harder-to-characterize space of possible attacks.

Acknowledgments

This work was supported by NSF Award Grant no. 1805310 and the DARPA ASED program under FA8650-18-2-7882. R.J. is supported by an NSF Graduate Research Fellowship under Grant No. DGE-114747. A.R. is supported by a Google PhD Fellowship and the Open Philanthropy Project AI Fellowship. We thank Allen Nie for providing the pre-trained language model, and thank Peng Qi, Urvashi Khandelwal, Shiori Sagawa, and the anonymous reviewers for their helpful comments.

Reproducibility

All code, data, and experiments are available on Codalab at https://bit.ly/2KVxIFN.

References

Appendix A Supplemental material

Gowal et al. (2018) showed how to compute interval bounds for affine transformations and monotonic element-wise functions. Here, we review their derivations, for completeness.

Monotonic scalar functions.

A.2 Numerical stability of softmax

In this section, we show how to compute interval bounds for softmax layers in a numerically stable way. We will do this by showing how to handle log-softmax layers. Note that since softmax is just exponentiated log-softmax, and exponentiation is monotonic, bounds on log-softmax directly yield bounds on softmax.

Let $z^{\text{dep}}$ denote a vector of length $m$, let $c$ be an integer $\in\{1,\dotsc,m\}$, and let $z^{\text{res}}$ represent the log-softmax score of index $c$, i.e.

stably. The standard way to compute this is to normalize $v$ by subtracting $\max_{i}(v_{i})$ before taking exponentials, then add it back at the end. $\operatorname{logsumexp}$ is a standard function in libraries like PyTorch. We will also rely on the fact that if $v$ is the concatenation of vectors $u$ and $w$, then $\operatorname{logsumexp}(v)=\operatorname{logsumexp}([\operatorname{logsumexp}(u),\operatorname{logsumexp}(w)])$.

The upper bound $u^{\text{res}}$ is achieved by having the maximum value of $z^{\text{dep}}_{c}$, and minimum value of all others. This can be written as:

While we could directly compute this expression, it is difficult to vectorize. Instead, with some rearranging, we get

The second term is the $\operatorname{logsumexp}$ of

Since we know how to compute $\operatorname{logsumexp}$, this reduces to computing (15). Note that (15) can be rewritten as

by adding and subtracting $u^{\text{dep}}_{c}$. To compute this quantity, we consider two cases:

Lower bound.

A.3 Attack surface differences

where probabilities are assigned by a pre-trained language model, and the window radius $W$ and threshold $\delta$ are hyperparameters. We use $W=6$ and $\delta=5$. We also use a different language modelhttps://github.com/windweller/l2w from Alzantot et al. (2018) that achieves perplexity of $50.79$ on the One Billion Word dataset (Chelba et al., 2013). Alzantot et al. (2018) use a different, slower language model, which compels them to use a smaller window radius of $W=1$.

A.4 Experimental details

We do not run training for a set number of epochs but do early stopping on the development set instead. For normal training, we early stop on normal development set accuracy. For training with data augmentation, we early stop on the accuracy on the augmented development set. For certifiably robust training, we early stop on the certifiably robust accuracy on the development set. We use the Adam optimizer (Kingma and Ba, 2014) to train all models.

On IMDB, we restrict the model to only use the $50,000$ words that are in the vocabulary of the counter-fitted word vector space of Mrkšić et al. (2016). This is because perturbations are not allowed for any words not in this vocabulary, i.e. $N(w)=\{w\}$ for $w\notin V$. Therefore, the model is strongly incentivized to predict based on words outside of this set. While this is a valid way to achieve high certified accuracy, it is not a valid robustness strategy in general. We simply delete all words that are not in the vocabulary before feeding the input to the model.

For SNLI, we use $100$-dimensional hidden state for the BoW model and a $3$-layer feedforward network. These values were chosen by a hyperparameter search on the dev set. For DecompAttn, we use a $300$-dimensional hidden state and a $2$-layer feedforward network on top of the context-aware vectors. These values were chosen to match Parikh et al. (2016).

Our implementation of the Decomposable Attention follows the original described in Parikh et al. (2016) except for a few differences listed below;

We do not normalize GloVe vectors to have norm 1.

We do not hash out-of-vocabulary words to randomly generated vectors that we train, instead we omit them.

We do randomly generate a null token vector that we then train. (Whether the null vector is trained is unspecified in the original paper).

We use the Adam optimizer (with a learning rate of $1\times 10^{-4}$) instead of AdaGrad.

We use a dropout probability of $0.1$ instead of $0.2$

We do not use the intra-sentence attention module.

A.5 Training schedule

In Table 4, we show the effect of holding $\epsilon$ or $\kappa$ fixed during training, as described in Section 5.6. All numbers are on $1000$ randomly chosen examples from the IMDB development set. Slowly increasing $\epsilon$ is important for good performance. Slowly increasing $\kappa$ is actually slightly worse than holding $\kappa=\kappa^{*}$ fixed during training, despite earlier experiments we ran suggesting the opposite. Here we only report certified accuracy, as all models are trained with certifiably robust training, and certified accuracy is much faster to compute for development purposes.

A.6 Word vector bound sizes

To better understand the effect of $g^{\text{word}}$, we checked whether $g^{\text{word}}$ made interval bound boxes around neighborhoods $N(w)$ smaller. For each word $w$ with $|N(w)|>1$, and for both the pre-trained vectors $\phi^{\text{pre}}(\cdot)$ and transformed vectors $\phi(\cdot)$, we compute

A.7 Certifying long-term memory

We might expect that LSTMs are difficult to certify with IBP, due to their long computation paths. To test whether robust training can learn recurrent models that track state across many time steps, we created a toy binary classification task where the input is a sequence of words $x_{1},\dotsc,x_{L}$, and the label $y$ is $1$ if $x_{1}=x_{L}$ and otherwise. We trained an LSTM model that reads the input left-to-right, and tries to predict $y$ with a two-layer feedforward network on top of the final hidden state. To do this task, the model must encode the first word in its state and remember it until the final timestep; a bag of words model cannot do this task. For perturbations, we allow replacing every middle word $x_{2},\dotsc,x_{L-1}$ with any word in the vocabulary. We use robust training on $4000$ randomly generated examples, where the length of each example is sampled uniformly between $3$ and $10$. The model obtains $100\%$ certified accuracy on a test set of $1000$ examples, confirming that robust training can learn models that track state across many time steps.

For this experiment, we found it important to first train for multiple epochs with no certified objective, before increasing $\epsilon$ and $\kappa$. Otherwise, the model gets stuck in bad local optima. We trained for $50$ epochs using the normal objective, $50$ epochs increasing $\epsilon$ towards $1$ and $\kappa$ towards $0.5$, then $17$ final epochs (determined by early stopping) with these final values of $\epsilon$ and $\kappa$. Note that this dataset is much smaller than IMDB and SNLI, so each epoch corresponds to many fewer parameter updates. We leave further exploration of these learning schedule tactics to future work. We also found it necessary to use a larger LSTM—we used one with $300$-dimensional hidden states.

Appendix B Adversarial examples

In this additional supplementary material, we show randomly chosen adversarial examples found by the genetic attack. We show examples for three different models: the CNN model on IMDB trained normally, with certifiably robust training, and with data augmentation. For each model, we picked ten random development set examples for which the model was correct on the original example, but wrong after the genetic attack. Changed words are marked in bold.