Achieving Model Robustness through Discrete Adversarial Training (2021)

Abstract: Discrete adversarial attacks are symbolic perturbations to a language input that preserve the output label but lead to a prediction error. While such attacks have been extensively explored for the purpose of evaluating model robustness, their utility for improving robustness has been limited to offline augmentation only. Concretely, given a trained model, attacks are used to generate perturbed (adversarial) examples, and the model is re-trained exactly once. In this work, we address this gap and leverage discrete attacks for online augmentation, where adversarial examples are generated at every training step, adapting to the changing nature of the model. We propose (i) a new discrete attack, based on best-first search, and (ii) random sampling attacks that unlike prior work are not based on expensive search-based procedures. Surprisingly, we find that random sampling leads to impressive gains in robustness, outperforming the commonly-used offline augmentation, while leading to a speedup at training time of ~10x. Furthermore, online augmentation with search-based attacks justifies the higher training cost, significantly improving robustness on three datasets. Last, we show that our new attack substantially improves robustness compared to prior methods.

## introduction adversarial examples are inputs that are slightly, but intentionally, perturbed to create a new example that is misclassified by a model @xcite . adversarial examples have attracted immense attention in machine learning @xcite @xcite for two important, but separate, reasons. first, they are useful for evaluating model robustness, and have revealed that current models are over-sensitive to minor perturbations. second, adversarial examples can improve robustness: training on adversarial examples reduces the brittleness and over-sensitivity of deep learning models to such perturbations @xcite @xcite @xcite @xcite @xcite . training and evaluating models with adversarial examples has had considerable success in computer vision, with gradient-based techniques like fgsm @xcite and pgd @xcite . in computer vision, adversarial examples can be constructed by considering a continuous space of imperceptible perturbations around image pixels. conversely, language is discrete, and any perturbation is perceptible. thus, robust models must be invariant to input modifications that preserve semantics, such as synonym substitutions @xcite , paraphrasing @xcite , or typos @xcite . due to this property of language, ample work has been dedicated to developing discrete attacks that generate adversarial examples through combinatorial optimization @xcite @xcite @xcite . for example, in sentiment analysis, it is common to consider the space of all synonym substitutions, where an adversarial example for an input "such an amazing movie!" might be "such an extraordinary film" (fig. 2 ). this body of work has mostly focused on evaluating robustness, rather than improving it, which naturally led to the development of complex combinatorial search algorithms, whose goal is to find adversarial examples in the exponential space of perturbations. in this work, we address a major research gap in current literature around improving robustness with discrete attacks. specifically, past work @xcite @xcite only considered offline augmentation, where a discrete attack is used to generate adversarial examples and the model is re-trained exactly once with those examples. this ignores online augmentation, which had success in computer vision @xcite @xcite , where adversarial examples are generated in each training step, adapting to the changing model. moreover, simple data augmentation techniques, such as randomly sampling from the space of synonym substitutions and adding the generated samples to the training data have not been investigated and compared to offline adversarial augmentation. we address this lacuna and systematically compare online augmentation to offline augmentation, as well as to simple random sampling techniques. to our knowledge, we are the first to evaluate online augmentation with discrete attacks on a wide range of nlp tasks. our results show that online augmentation leads to significant improvement in robustness compared to prior work and that simple random augmentation achieves comparable results to the common offline augmentation at a fraction of the complexity and training time. moreover, we present a new search algorithm for finding adversarial examples, best-first search over a factorized graph (bff), which alleviates the greedy nature of previously-proposed algorithms. bff improves search by incorporating backtracking, and allowing to re-visit previouslydiscarded search paths, once the current one is revealed to be sub-optimal. we evaluate model robustness on three datasets: boolq @xcite , imdb @xcite , and sst-2 @xcite , which vary in terms of the target task (question answering and sentiment analysis) and input length. surprisingly, we find across different tasks (fig. 1 ) that augmenting each training example with 4-8 random samples from the synonym substitution space performs as well as (or better than) the commonly used offline augmentation, while being simpler and 10x faster to train. conversely, online augmentation makes better use of the extra computational cost, and substantially improves robust accuracy compared to offline augmentation. additionally, our proposed discrete attack algorithm, bff, outperforms prior work by a wide margin. our data and code are available at https://github.com/ mivg/robust_transformers . ## problem setup and background problem setup we focus in this work on the supervised classification setup, where given a training set {x j , y j } n @xmath0, our goal is to learn a mapping a : @xmath1. moreover, we want the model a to be robust, i.e., invariant to a set of pre-defined labelpreserving perturbations to x, such as synonym substitutions. formally, for any natural language input x, a discrete attack space of label-preserving perturbations s(x) ⊂ x is defined. given a labeled example (x, y), a model a is robust w.r.t x, if a(x) = y and for any @xmath2, the output a(x) = a(x). an example @xmath3. we assume a provides not only a prediction but a distribution p a (x) ∈ ∆ |y| over the possible classes, where ∆ is the simplex, and denote the probability a assigns to the gold label by [p a (x)] y . fig. 2 shows an example from sentiment analysis, where a model a is robust, while a is not w.r.t x. robustness is evaluated with robust accuracy @xcite , i.e., the fraction of examples a model is robust to over some held-out data. typically, the size of the attack space s(x) is exponential in the size of x and it is not feasible to enumerate all perturbations. instead, an upper bound is estimated by searching for a set of adversarial attacks, i.e., "hard" examples in s(x) for every x, and estimating robust accuracy w.r.t to that set. improving robustness with discrete attacks since language is discrete, a typical approach for evaluating robustness is to use combinatorial optimization methods to search for adversarial examples in the attack space s(x). this has been repeatedly shown to be an effective attack method on pre-trained models @xcite @xcite @xcite . however, in terms of improving robustness, discrete attacks have thus far been mostly used with offline augmentation (defined below) and have led to limited robustness gains. in this work, we examine the more costly but potentially more beneficial online augmentation. offline vs. online augmentation data augmentation is a common approach for improving generalization and robustness, where variants of training examples are automatically generated and added to the training data @xcite . here, discrete attacks can be used to generate these examples. we consider both offline and online data augmentation and focus on improving robustness with adversarial examples. given a training set {(x j , y j )} n @xmath4, offline data augmentation involves (a) training a model a over the training data, (b) for each training example (x j , y j ), generating a perturbation w.r.t to a (using some discrete attack) and labeling it with y j , and (c) training a new model over the union of the original training set and the generated examples. this is termed offline augmentation because examples are generated with respect to a fixed model a. online data augmentation is this setup, examples are generated at training time w.r.t the current model a. this is more computationally expensive, as examples must be generated during training and not as pre-processing, but examples can adapt to the model over time. in each step, half the batch contains examples from the training set, and half are adversarial examples generated by some dis-crete attack w.r.t to the model's current state. online augmentation has been used to improve robustness in nlp with gradient-based approaches @xcite @xcite , but to the best of our knowledge has been overlooked in the context of discrete attacks. in this work, we are the first to propose model-agnostic online augmentation training, which uses automatically generated discrete adversarial attacks to boost overall robustness in nlp models. ## the attack space an attack space for an input with respect to a classification task can be intuitively defined as the set of label-preserving perturbations over the input. a popular attack space s(x), which we adopt, is the space of synonym substitutions @xcite . given a synonym dictionary that provides a set of synonyms syn(w) for any word w, the attack space s syn (x) for an utterance @xmath5, . . . , w n ) contains all utterances that can be obtained by replacing a word w i (and possibly multiple words) with one of their synonyms. typically, the number of words from x allowed to be substituted is limited to be no more than @xmath6, where @xmath7.1, 0.2} is a common choice. synonym substitutions are context-sensitive, i.e., substitutions might only be appropriate in certain contexts. for example, in fig. 3 , replacing the word "like" with its synonym "similar" (red box) is invalid, since "like" is a verb in this context. consequently, past work @xcite filtered s syn (x) using a context-sensitive filtering function φ x (w i , wi ) ∈ {0, 1}, which determines whether substituting a word w i from the original utterance x with its synonym wi is valid in a particular context. for instance, an external model can check whether the substitution maintains the part-of-speech, and whether the overall semantics is maintained. we define the filtered synonyms substitutions space s φ (x) as the set that includes all utterances x that can be generated through a sequence of no more than d single-word substitutions from the original utterance that are valid according to φ(•, •). in §5.2, we describe the details of the synonym dictionary and function φ. ## best-first search over a factorized graph searching over the attack space s φ (x) can be naturally viewed as a search problem over a directed acyclic graph (dag), @xmath8, e), where each node u @xmath9, and edges e correspond to single-word substitutions, valid according to φ(•). the graph is directed and acyclic, since only substitutions of words from the original utterance x are allowed (see fig. 3 ). because there is a one-to-one mapping from the node u x to the utterance x, we will use the latter to denote both the node and the utterance. discrete attacks use search algorithms to find an adversarial example in s(x). the search is guided by a heuristic scoring function s a (x) := [p a (x)] y , where the underlying assumption is that utterances that give lower probability to the gold label are closer to an adversarial example. a popular choice for a search algorithm in nlp is greedy search, illustrated in fig. 3 . specifically, one holds in step t the current node x t , where t words have been substituted in the source node x 0 = x. then, the model a(•) is run on the frontier, that is, all out-neighbor nodes n (x t ) = {x t+1 | (x t , xt+1 ) ∈ e}, and the one that minimizes the heuristic scoring function is selected: while greedy search has been used for characterflipping @xcite , it is ill-suited in the space of synonym substitutions. the degree of nodes is high -assuming n rep words can be replaced in the text, each with k possible synonyms, then the out degree is o(n rep • k). this results in an infeasible number of forward passes through the attacked model even for a small number of search iterations. to enable effective search through the search space, we (a) factorize the graph such that the outdegree of nodes is lower, and (b) use a best-first search algorithm. we describe those next. graph factorization to reduce the out-degree of a node in the search space and thus improve its efficiency, we can split each step into two. first, choose a position to substitute in the utterance; second, choose a substitution for that position. this reduces the number of evaluations of a per step from o(n rep • k) to o(n rep + k). to estimate the score of a position i, one can mask the word w i with a mask token τ and measure s a (x w @xmath10, where x w @xmath11. we can describe this approach as search over a bi-partite dag ĝ = (u ∪ w, ê). the nodes u are utterances like in g, and the new nodes are utterances with a single mask token the edges e 1 are from utterances to masked utterances: best-first search a factorized graph makes search possible by reducing the out-degree of nodes. however, greedy search is still sub-optimal. this is since it relies on the heuristic search function to be a good estimate of the distance to an adversarial example, which can often be false. consider the example in fig. 3 . the two adversarial examples (with @xmath12.4 or @xmath13.45) are not reachable from the best node after the first step (@xmath14.6), only from the second-best (@xmath15.65). best-first search @xcite overcomes this at a negligible cost, by holding a min-heap over the nodes of the frontier of the search space (alg. 1). in each step, we pop the next utterance, which assigns the lowest probability to the gold label, and push all neighbors into the heap. when a promising branch turns out to be sub-optimal, search can resume from an earlier node to find a better solution, as shown in the blue path in figure 3 . to bound the cost of finding a single adversarial example, we bound the number of forward passes through the model a with a budget parameter b. to further reduce "greedyness", search can use a beam by popping more than one node in each step, expanding all their neighbors and pushing the result back to the heap. our final approach uses best-first search over a factorized graph, and is termed bff. algorithm 1: bff input :model a, factorized graph g, utterance x. heap ← {(x, sa(x)} x * ← x while |heap| > 0 and budget b not exhausted: ## experiments we conduct a thorough empirical evaluation of model robustness across a wide range of attacks and training procedures. ## related work adversarial attacks and robustness have attracted tremendous attention. we discuss work beyond improving robustness through adversarial attacks. certified robustness is a class of methods that provide a mathematical certificate for robustness @xcite @xcite @xcite . the model is trained to minimize an upper bound on the loss of the worst-case attack. when this upper bound is low, we get a certificate for robustness against all attacks. while this approach has had success, it struggles when applied to transformers, since upper bounds are propagated through many layers, and become too loose to be practical. ## conclusions we examine achieving robustness through discrete adversarial attacks. we find that the popular approach of offline augmentation is sub-optimal in both speed and accuracy compared to random sampling, and that online augmentation leads to impressive gains. furthermore, we propose bff, a new discrete attack based on best-first search, and show that it outperforms past work both in terms of robustness improvement and in terms of attack success rate. together, our contributions highlight the key factors for success in achieving robustness through adversarial attacks, and open the door to future work on better and more efficient methods for achieving robustness in natural language understanding. in contrast to txf which is optimistic and factorizes the attack space only once, bff factorizes the space after every step. namely, optimistic greedy search plans the entire search path by evaluating all permissible single-word substitutions. let x w @xmath16. the optimistic greedy algorithm scores each word w i in the utterance with s(w i ) := min @xmath17, that is, the score of a word is the score for its best substitution, and also stores this substitution. then, it sorts utterance positions based on s(w i ) in ascending order, which defines the entire search path: in each step, the algorithm moves to the next position based on the sorted list and uses the best substitution stored for that position. fig. 5 shows the benefit from each of those modifications. budget effect intuitively, higher budgets better approximate an exhaustive search and thus the robustness evaluation as an upper bound should approach its true value. however, due to lack of backtracking in some of the attack strategies, they may plateau early on. in this work, we used @xmath18. empirically, this gives a good estimate on the upper bound of model's robust accuracy, while constraining the computational power needed for the experiments. a natural question is how much tighter the bounds may be if a larger budget is given. fig. 6 depicts an evaluation of strategies' success-rates over the same models as in fig. 4 with a larger budget. as can be seen, while the random attack and txf plateau, bff variants as well as genattack are able to exploit the larger budget to fool the model in more cases. this is especially true in imdb where the search space is considerably larger. we expect this trend of tighter bounds to continue with ever larger budgets, though we note that the rate of improvements decreases with budget and that the ranking between strategies remains unchanged. therefore, we conclude that drawing conclusions about strategies comparison and robustness improvements by evaluating with a budget of 2, 000 suffices.