Title: TASK-AGNOSTIC ROBUST ENCODINGS FOR COMBATING ADVERSARIAL TYPOS

Abstract: Despite achieving excellent benchmark performance, state-of-the-art NLP models can still be easily fooled by adversarial perturbations such as typos. Previous heuristic defenses cannot guard against the exponentially large number of possible perturbations, and previous certified defenses only work with limited model sizes and simple architectures. In this paper, we construct task-agnostic robust encodings (TARE): sentence representations that improve the robustness of any model for multiple downstream tasks at once, and enable efficient exact computation of robust accuracy (accuracy on worst-case perturbations) for a fixed family of perturbations. The core idea behind TARE is to map sentences through a discrete bottleneck before feeding them to a downstream model. To create robust encodings, we must optimize for two competing goals: the encoding of a sentence must retain enough information about the sentence, but should also map all perturbations of the sentence to the same encoding to ensure invariance to perturbations. Averaged across six tasks from GLUE, a standard suite of NLP tasks, the same encoding leads to robust accuracy of 71.2% when defending against a large family of typos, while a strong baseline that uses a typo corrector achieves only 38.5% accuracy, and training on random typos achieves only 9.9% accuracy.

1. INTRODUCTION:

Recent work has revealed the brittleness of NLP systems to perturbations (Belinkov & Bisk, 2017; Ebrahimi et al., 2017; Ribeiro et al., 2018; Alzantot et al., 2018) . In particular, adversarial typos have fooled systems for hate speech detection (Hosseini et al., 2017) , machine translation (Ebrahimi et al., 2018) , and spam filtering (Lee & Ng, 2005) , among others. In order to build more robust NLP systems, we typically define a set of allowable perturbations, such as a list of plausible typos for each word (Jia et al., 2019; Huang et al., 2019) . Then, we attempt to train models that have high robust accuracy, the worst-case accuracy across all perturbations of each example. An ideal defense against perturbations would produce a single representation that works across different tasks and models, while giving guarantees on the ability of any adversary to hurt model performance.

Previous work does not address all of these goals at once. Some prior work tries to recover the original sentence given a perturbed input (Pruthi et al., 2019; Gong et al., 2019) . Pruthi et al. (2019) apply a typo corrector to inputs before passing them to a model, but do not achieve high robust accuracy on large families of typos. Other prior work confers robustness by changing the training procedure. Adversarial training, which adds adversarial perturbations to the training set, can be applied to any model. However, it only provides limited robustness, due to heuristics used to compute adversarial attacks for text inputs (Ebrahimi et al., 2017) . Certifiably robust training with interval bound propagation (Huang et al., 2019) confers guaranteed robustness, but can only currently be applied to limited model architectures of small size. Neither of these training methods produces a single defense that works across multiple tasks.

Our proposed method simultaneously overcomes the task-specificity or model-specificity of prior approaches, while providing robustness against worst-case perturbations. We construct task-agnostic robust encodings (TAREs): discrete representations of sentences that can be used across many tasks to improve robustness of any downstream model. TAREs are model-agnostic, reusable across tasks, and confer guaranteed robustness via standard training of downstream models, avoiding the computational overhead typically associated with adversarial training. By introducing a discrete We optimize an encoding function α such that for many sentences x, every perturbation of x maps to α(x), providing robustness to perturbations. The same encoding function can be used for multiple tasks, and any model using our encodings as input makes robust predictions.

bottleneck, our robust encodings enable tractable computation of robust accuracy, even when the set of allowed perturbations is combinatorially large. See Figure 1 for an overview of our approach.

The key idea of TARE is to have an encoding function α(x) that maps each token of an input sentence x to an encoding such that each token has the same encoding as all of its possible perturbations. This property, which we term stability, ensures that any model that makes predictions using only the encoding will give the same prediction on all perturbed versions of an input. We also need to ensure that the encodings contain enough information about the input to do the task, which we term fidelity.

We choose α by optimizing a weighted combination of these two objectives. We cast this search over possible encoding functions as a clustering problem over tokens, where each cluster contains tokens that are mapped to the same encoding. We perform this clustering in an unsupervised, task-agnostic fashion, and use the same encoding function for various downstream tasks.

In our experiments, we consider attacks that are allowed to add an edit distance one typo to each word in an input sentence, without changing the first and last character of each word, following prior work (Pruthi et al., 2019) . Using TARE, we significantly improve robust accuracy across six classification tasks from the GLUE benchmark (Wang et al., 2019 ). Our best system, which combines TARE with a BERT classifier (Devlin et al., 2018) , achieves robust accuracy of 71.2% on average across the six tasks. In contrast, a state-of-the-art defense that combines BERT with a typo corrector (Pruthi et al., 2019) gets 38.5% accuracy, and a standard defense that trains BERT on random perturbations gets only 9.9% accuracy in the presence of heuristically generated adversarial typos.

2. SETUP:

Tasks. We consider NLP tasks that require classifying textual input x ∈ X to a class y ∈ Y. For simplicity, we refer to inputs as sentences. Each sentence x consists of tokens x 1 , . . . , x L where each x i ∈ T , the set of all possible tokens, which includes valid perturbations (e.g., typos) of vocabulary words. Let p task denote the distribution over inputs and labels for a particular task of interest. The goal is to learn a model f : X → Y that maps sentences to labels, given training examples (x, y) ∼ p task .

Attack model. We consider an attack model in which the attacker can perturb each token x i of a sentence to some token xi ∈ B(x i ), where B(x i ) is the set of valid perturbations of x i . For example, B(x i ) could be a set of allowed typos of x i (e.g., tokens that are edit distance one from x i ). We define B(x) as the set of all valid perturbations of sentence x. Each token can be perturbed independently, so

EQUATION

Model evaluation. In this work, we use three evaluation metrics for a given task.

First, we evaluate a model on its standard accuracy on the task:

EQUATION

Next, we are interested in models that also have high robust accuracy, the fraction of examples (x, y) for which the model is correct on all valid perturbations x ∈ B(x) allowed in the attack model:

EQUATION

For many models, computing robust accuracy is intractable. It is customary to instead compute accuracy against a heuristic attack a that maps clean sentences x to perturbed sentences a(x) ∈ B(x).

EQUATION

Typically, we compute a(x) via a heuristic search over B(x) for a sentence that f misclassifies. Note that acc attack ≥ acc robust because there could be perturbations that the model misclassifies but are missed by the heuristic search. In general, a high acc attack does not guarantee that the model has high acc robust , which is the actual quantity of interest (Athalye et al., 2018) .

3. TASK-AGNOSTIC ROBUST ENCODINGS:

In this work, we construct task-agnostic robust encodings (TAREs). Informally, TARE enables arbitrary model architectures to achieve high robust accuracy on many standard tasks. We define an encoding function to be a function α : X → Z, where X is the set of sentences and Z ⊆ X . We refer to α(x) as the encoded sentence, or encoding, corresponding to x. A downstream model f down : Z → Y makes predictions using the encoded sentence α(x). We denote f down (α(x)) by f TARE . Because Z ⊆ X , f down can be any model that takes sentences as inputs.

3.1. ROBUSTNESS OF ENCODINGS:

We are interested in obtaining models that are robust, i.e., accurate on all valid perturbations of an input. For some model f TARE that uses our robust encodings, we can guarantee high acc robust (f TARE ) if acc std (f TARE ) is high and f TARE usually makes the same prediction on all x ∈ B(x):

EQUATION

Based on Equation 5, we define two desiderata of α that enable f TARE to achieve high robust accuracy. First, high fidelity of an encoding ensures that it is possible for f TARE to get high standard accuracy. Second, high stability of an encoding upper bounds the second term in (5), ensuring that any model that has high standard accuracy also has high robust accuracy.

Fidelity. First, we must ensure that α(x) contains enough information to perform the task. We say that α has high fidelity if there exists some f down for which f TARE (x) def = f down (α(x)) has high standard accuracy. Fidelity is maximized by having α(x) = x, since this preserves all information about x.

Stability. We now focus on the second term of Equation 5. Consider the simple case where α(x) is constant for all x, i.e. all sentences share the same encoding. Here, trivially f TARE (x) = f TARE (x) ∀ x ∈ B(x) and the second term is 0. For the more general case, we bound the second term of (5) by the stability of an encoding, which we define as the probability over x drawn from p task that all perturbations of x are encoded to the same α(x). Formally, we have Vocabulary words (large font, blue) share an edge if they share a common perturbation (small font, red). We show three different encodings: the bold line corresponds to the encoding with maximal stability (connected component encoding), the dotted lines correspond to maximizing fidelity, and the thin solid lines balance stability and fidelity (agglomerative clusters).

B α (x) = {α(x) | x ∈ B(x)}, (6) Stability(α) = E x∼ptask 1[|B α (x)| = 1] (7) E (x,y)∼ptask max x∈B(x) 1 [f TARE (x) = f TARE (x)] ≤ 1 -Stability(α) (8) When |B α (x)| = 1,

Tradeoff. Note that fidelity and stability are often opposing goals. Fidelity tries to map tokens to themselves while stability tries to map tokens and their perturbations together.

Finally, a robust encoding is task-agnostic if it can be constructed without knowledge of any downstream task, but is still a robust encoding for many downstream tasks. This is challenging, as stability and fidelity are both defined with respect to a task. Stability only depends on the distribution of inputs x, and hence can be approximated using a large, unlabeled text corpus. Fidelity requires labels, and hence is more difficult to approximate. Nonetheless, in the next section, we show how to construct α in an unsupervised, task-agnostic fashion such that for many natural tasks, we can train a model fTARE that achieves high standard accuracy.

4. TASK-AGNOSTIC CONSTRUCTION OF ROBUST TOKEN-LEVEL ENCODINGS:

Now, we describe how to construct robust encodings in a task-agnostic fashion. We focus on tokenlevel encodings, where the encoding of a sentence is the concatenation of the encoding of individual tokens. Formally, we extend α to map tokens w ∈ T to some set Z Tok ⊆ T of encoded tokens. The encoding α(x) for input sentence x can then be written as

EQUATION

We now focus on how to choose α(w) for all w ∈ T , in a task-agnostic fashion.

4.1. ROBUSTNESS OF TOKEN-LEVEL ENCODINGS:

How can we choose a robust token-level encoding α, balancing the competing goals of stability and fidelity? As a running example, consider the five words (large font, blue) in Figure 2 , along with typos of those words (small font, red). We illustrate three different choices of α; for each, we draw a box around tokens that α maps to the same encoded token. α could map all five words to the same encoded token (thick box), map each word to a different encoded token (dashed boxes), or do something in between (thin solid boxes).

First, consider trying to maximize stability. Note that for a sentence x, |B α (x)| = 1 if and only if |B α (x i )| = 1 for all words x i in x, so maximizing stability requires |B α (w)| = 1 for all words w that might appear in x. Consider two words w 1 and w 2 (e.g., "aunt" and "abet" for which there exists a token w ∈ T that could be a perturbation of both (e.g., "auet" is edit distance one from both words). We draw edges between all such word pairs in Figure 2 , and place an example of a typo in B α (w 1 ) ∩ B α (w 2 ) next to each edge. For any such w 1 and w 2 , maximizing stability requires that α(w 1 ) = α(w 2 ), since if they were not equal, α must either map w 1 and w to different encoded tokens (hence, |B α (w 1 )| > 1), or map w 2 and w to different encoded tokens (hence, |B α (w 2 )| > 1).

In Figure 2 , we would therefore have to map all five words to the same encoded token (thick box), as they are in the same connected component in this graph.

However, this mapping clearly has low fidelity, since these five words are all identically encoded. Fidelity is maximized when all information about x is retained, so each word is mapped to a different encoded token (dashed green boxes). Unfortunately, this choice of α has low stability. For the words "art", "abet", and "abrupt", |B α (w)| > 1, since these words and their typos map to at least two different encoded tokens (e.g., "aut", a typo of "aunt", maps to the encoding of "at").

The encoding represented by the thin solid boxes in Figure 2 balances stability and fidelity. Compared to encoding all words identically, it has higher fidelity, since it distinguishes between some of the words (e.g., "at" and "about" are encoded differently). It also has reasonably high stability, since only "abet" has |B α (w)| > 1. Since the word "abet" occurs infrequently in normal English text, the fact that |B α (w)| > 1 for that word will only affect |B α (x)| for a very small fraction of x ∼ p task , for most natural task distributions p task .

With this intuition, we now define two ways to construct α. Our first method will focus on maximizing stability, at the cost of fidelity. Our second method allows us to trade off stability for fidelity, improving both standard and robust accuracy of downstream models. Both methods will construct α in a taskagnostic fashion: we will not reference any task distribution p task , but instead only assume access to a large, unlabeled corpus of English text. Implicitly, we assume that the distribution of sentences x ∼ p task will not differ too much from the distribution of text in our corpus.

4.2. BASELINE: CONNECTED COMPONENT ENCODINGS:

Our first method, connected component encodings, focuses on maximizing stability. Ideally, we would have |B α (w)| = 1 for all w ∈ T , but this is very restrictive, and would lead to very low fidelity. Note that in order to have small B α (x) for most x ∼ p task , it suffices to ensure |B α (w)| = 1 for all tokens that are actually likely to appear in x. Therefore, we define a set of frequent words V ⊆ T , and then make sure that |B α (w)| = 1 for all w ∈ V .

We first create a vocabulary V = {w 1 , . . . , w N } ⊆ T by taking the N most frequent words in a large, unlabeled text corpus. For a word w ∈ V , let ρ(w) denote the fraction of times w occurs in this corpus. Next, we construct the graph G = (V, E) shown in Figure 2 , whose vertex set is our vocabulary V , and its edge set E contains all pairs of vertices that share a common perturbation:

EQUATION

10) Let K be the number of connected components of G, and let C 1 , . . . , C K denote these connected components. For each C j , we define its representative r j to be the word w ∈ C j with largest ρ(w), and set α(w) = r j for all w ∈ C j . Using connected components guarantees that every pair of words w i , w j ∈ V that shares a perturbation will be encoded identically. Mapping to representative words helps us leverage the inductive biases of pre-trained models like BERT (Devlin et al., 2018) .

Extending connected component encodings to out-of-vocabulary tokens. We have defined α for all w ∈ V ; now we must define it for other w ∈ T \ V , such as typos (e.g., "aboupt"). There are two cases. First, suppose there exists w ∈ V such that w ∈ B(w). Then, we define α( w) = α(w). Note that this is well-defined, as we constructed the C j 's to ensure if multiple such w exist, they map to the same encoded token. This choice guarantees |B α (w)| = 1 for all w ∈ V . It may also be the case that w / ∈ B(w) ∀ w ∈ V . In this case, we set α( w) = OOV, a special out-of-vocabulary token.

Connected component encodings and full sentences. We now return to the question of stability at the sentence-level-for which sentences x does |B α (x)| = 1? Connected component encodings ensure that |B α (x)| = 1 as long as x i ∈ V for all words x i in x. However, some task distributions p task may include rare words that are not in our vocabulary V . When x contains a word w / ∈ V , it is possible that |B α (w )| > 1, and hence |B α (x)| > 1. Note that |B α (w )| will still be 1 if all perturbations of w also map to OOV.

4.3. AGGLOMERATIVE CLUSTER ENCODINGS:

Connected component encodings focus on stability at the cost of fidelity. When G has large connected components, the resulting α may not be very useful for downstream tasks, since too many tokens share the same encoding. In particular, two frequent words that do not share a common perturbation will still have the same encoding if there is a path connecting them. In Figure 2 , "at" and "about" are in the same connected component, even though no token is a plausible typo of both words. Since both words are very frequent in general, mapping them to the same encoding creates ambiguity in a large proportion of frequent sentences. Therefore, encoding "at" and "about" differently would significantly improve fidelity. The thin solid boxes in Figure 2 accomplish this goal, at a small cost to stability: recall that only the infrequent word "abet" has |B α (w)| > 1, which is unlikely to affect |B α (x)| for most sentences x.

To take advantage of cases like this, we formally define two task-agnostic objectives on α: one that encourages stability, and one that encourages fidelity. Recall that stability and fidelity are dependent on a particular task distribution p task ; our objectives are task-agnostic approximations of stability and fidelity that empirically generalize to many natural tasks. We then use an agglomerative clustering algorithm to approximately optimize a weighted sum of these objectives, where we view a cluster C j ⊆ V as a set of vocabulary words that share the same encoding under α.

Stability objective. As mentioned previously, it is more important that |B α (w)| = 1 when w is a frequent word, as opposed to an infrequent word, as frequent words are more likely to occur in sentences x ∼ p task . Moreover, even when |B α (w)| > 1, we prefer |B α (w)| to be small to enable efficient computation of robust accuracy, and to aid robustness of f TARE under some assumptions on f down (see Appendix A.3 ). While we do not know what words are frequent in p task , we can approximate this with the corpus word frequencies ρ. We define the stability objective Φ stability as:

EQUATION

Φ stability is minimized when |B α (w)| = 1 for every w ∈ V . Therefore, connected component encodings achieve optimal Φ stability .

Fidelity objective. In addition to stability, we also want to maximize fidelity. Intuitively, α has high fidelity when the ambiguity induced by encoding tokens does not appreciably decrease the accuracy f * . To formalize this intuition, we approximate the accuracy drop due to ambiguity with a loss that measures the distance between each word and its cluster in some vector space, inspired by k-means clustering. Let v i be the N -dimensional indicator vector that is 1 at index i and 0 at all other indices. We represent the cluster C j by a cluster centroid µ j defined as the average of word embeddings in C j , weighted by word frequency:

EQUATION

This definition is motivated by our expectation that downstream models will roughly use such a weighted average to represent each encoded token, similarly to how multiple word senses are known to be encoded in word vectors (Arora et al., 2018) . In general, v i could be any vector, such as a pre-trained word vector for word w i . We choose v i to be an indicator vector to avoid making assumptions about the downstream task. Now, let c(i) denote the j for which w i ∈ C j . We define the ambiguity objective Φ fidelity as

EQUATION

)

Note that if each word is in its own cluster, Φ fidelity is zero. Φ fidelity increases by a small amount if a frequent word and rare word are in the same cluster, and increases more when multiple frequent words are in the same cluster.

Final clustering objective. We introduce a hyperparameter γ ∈ [0, 1] that balances our two objectives. The final objective Φ becomes:

EQUATION

) Note that when γ = 1, we maximize fidelity, so each vocabulary word is assigned to its own cluster. As γ approaches 0, we get the connected component clusters from our baseline, which were designed to be maximize stability.

Defining agglomerative cluster encodings on out-of-vocabulary words. Since Φ involves |B α (w)|, it not only depends on the action of α on all vocabulary words, but also on all perturbations of vocabulary words. We simplify the optimization problem by imposing some constraints on α. In particular, similarly to the connected component encoding, we define α( w) for w / ∈ V in terms of α's action on words in V . Thus, optimizing Φ reduces to choosing α(w) for all w ∈ V .

First, if w / ∈ B(w) for all w ∈ V , we set α( w) = OOV, as before. Otherwise, note that unlike for the connected component clusters, w could now be a perturbation of multiple words with different encodings. We use the simple rule of mapping w to the same encoded token as the most frequent word it could be the perturbation of. Given w / ∈ V , we compute

EQUATION

and define α( w) = α(w ). This ensures that our choice of α( w) does not cause |B α (w )| to increase, but it will cause |B α (w)| > 1 for all w where w ∈ B(w) but α(w) = α(w ). In Figure 2 , we see that for the solid green boxes, we map "abot" to the same encoding as the frequent word "about" rather than the infrequent word "abet", so that B α still has size 1 for "about".

Agglomerative clustering. Now, we have reduced the problem of minimizing Φ to choosing α(w) for each w ∈ V . Recall that any α induces a clustering of V , where each cluster contains a set of words mapped by α to the same encoded token. We use an agglomerative clustering algorithm to approximately minimize Φ. We initialize α by setting α(w) = w for each w ∈ V , which corresponds to placing each word in its own cluster. We then examine each pair of clusters C i , C j such that there exists an edge between a node in C i and a node in C j , in the graph from Section 4.2. For each such pair, we compute the value of Φ if we were to combine them into a single cluster. If no merge operation causes Φ to decrease, we return the current α. Otherwise, we merge the pair that leads to the greatest reduction in Φ, and repeat. To merge two clusters C i and C j , we first compute a new representative r as the w ∈ C i ∪ C j with largest ρ(w). We then set α(w) = r for all w ∈ C i ∪ C j .

Our algorithm is formally defined in appendix A.1.

Agglomerative clustering is fairly slow, as each iteration considers merging O(|E|) pairs of clusters, each of which takes O(N ) time to evaluate. The algorithm can run for up to N iterations. As an optimization, we note that we can run the algorithm in parallel on each connected component of G, as we only consider merges involving nodes in the same connected component.

5. EXPERIMENTS:



Attack surface. The primary attack surface we study is edit distance one (ED1) perturbations.

For each token in the input, the adversary is allowed to insert a lowercase letter, delete a character, substitute a character for any lowercase letter, or swap any two adjacent characters, so long as the first and last characters remain the same as the original token. The constraint on the outer characters is motivated by psycholinguistic studies (Rawlinson, 1976; Davis, 2003) , and was also used in Pruthi et al. (2019) . For example, "the movie was miserable" can be perturbed to "thae mvie wjs misreable" but not "th movie as miserable". Since each token can be independently perturbed, the number of perturbations of a sentence grows exponentially with its length; even "the movie was miserable" has 431,842,320 possible perturbations. Our attack surface encompasses the attack surface used by Pruthi et al. (2019) , and we also allow all substitutions instead of only substitutions of adjacent letters on a QWERTY keyboard, and we perturb every input token as opposed to at most two.

Attack algorithms. We consider two attack algorithms: a brute-force attack and a heuristic attack. The brute-force attack exhaustively searches through all perturbations for an x ∈ B(x) that fools the model, so it exactly computes robust accuracy. Since |B α (x)| is small for many x, the brute-force attack can efficiently compute robust accuracy for models that use TARE by enumerating B α (x).

When |B α (x)| > 10000, which holds for 0.009% of our test examples, we assume the adversary can successfully perturb x. For other models, however, the brute-force attack is intractable, as B(x) is too large to enumerate, so we cannot compute robust accuracy. Instead, we use a heuristic beam search attack with beam size 5. This is still prohibitively expensive as B(x i ) can be large for each token x i , so the attack only tries at most len(x i ) perturbations in each B(x i ). Even against this limited attack, we find that baseline models have low accuracy. Details are provided in Appendix A.6.

Datasets. We use six of the nine tasks from GLUE (Wang et al., 2019) : SST-2, MRPC, QQP, MNLI, QNLI, and RTE. SST-2 (Socher et al., 2013) is a sentiment analysis classification task, MRPC and QQP1 are paraphrase detection tasks (Dolan & Brockett, 2005) , and MNLI, QNLI, and RTE are entailment tasks (Williams et al., 2018; Rajpurkar et al., 2016) . We do not use STS-B and CoLA as they are evaluated on correlation, which does not decompose as an example-level loss. We do not use WNLI, as most submitted GLUE models cannot outperform the majority baseline, and state-of-the-art models are rely on external training data (Kocijan et al., 2019) . We evaluate on the test sets for SST-2 and MRPC, and the publicly available development sets for the remaining tasks. For all datasets, we use 20% of the training set as a validation set. More details are provided in Appendix A.5.

Baseline models. We consider three baseline systems. First, we use a standard BERT model (Devlin et al., 2018) fine-tuned on the training data for each task.2 Second, we augment the training dataset with a single3 random perturbation of each example, and train another BERT model on this augmented data. Data augmentation has been shown to increase robustness to some types of adversarial perturbations (Ribeiro et al., 2018; Jia et al., 2019; Liu et al., 2019) .

Finally, we apply an scRNN (Sakaguchi et al., 2017) typo corrector to the input, as in Pruthi et al. (2019) . Following Pruthi et al. (2019) , we train a task-specific typo corrector on random perturbations to the training set. At test time, inputs are fed through the typo corrector, then to the downstream model. We map out-of-vocabulary words, as defined by the typo corrector's vocabulary, to a neutral word and use BERT as our downstream model, which was the best method from Pruthi et al. (2019) .

Models using TAREs. We run experiments using encoding functions defined using connected components and agglomerative clusters. To form clusters, we use the 100,000 most frequent words from the Corpus of Contemporary American English (Davies, 2008) that are also in GloVe (Pennington et al., 2014) . We form agglomerative clusters using γ = 0.3 which maximizes robust accuracy on SST-2 development set. For both encodings, we train a BERT model on the training data, using α(x) as input. Further details and hyperparameters are provided in Appendix A.2.

5.2. ROBUSTNESS GAINS FROM TASK-AGNOSTIC ROBUST ENCODINGS:

Our main results are shown in Table 1 . We show all three baselines, as well as models using both TAREs: connected component encodings (CONNCOMP) and agglomerative cluster encodings (AGGCLUST). The attack accuracy we report is an upper bound on robust accuracy obtained by running the heuristic attack, which we report since robust accuracy is only computable with TAREs.

Attacking BERT and BERT + Data Augmentation using the heuristic attack results in dramatic performance drops. Even the best performing baseline, Typo Corrector + BERT, can only achieve 38.5% accuracy on average against the heuristic attack, compared to its standard accuracy of 79.5%.

In contrast, TARE provides much greater robustness. AGGCLUST achieve average robust accuracy of 71.2%, 32.7 points higher than the attack accuracy of the best baseline, the typo corrector approach. Moreover, since the heuristic attack covers a tiny fraction of the full perturbation space, the actual gap in robust accuracy is likely higher. AGGCLUST also outperform CONNCOMP in terms of both robust accuracy (by 1.5 points) and standard accuracy (by 3.7 points).

Even though TAREs were constructed in a task-agnostic manner, they consistently have high stability across our tasks. Over AGGCLUST encodings, |B α (x)| = 1 for 25% of examples in RTE and 66% in SST-2, with the other four datasets falling between these extremes (see Appendix A.7). As expected, these numbers are even higher for the connected component encodings. Even when |B α (x)| > 1, it is often quite small, which both helps robust accuracy and makes it efficient to compute.

The primary drawback to our representations is lower standard accuracy, which has also been observed for defenses against adversarial examples in other domains (Madry et al., 2017; Zhang et al., 2019) by 34.9 points. Moreover, using TAREs we can compute the robust accuracy against the worst-case adversary, which we find outperforms the typo corrector by at least 32.7 points. Jia et al., 2019) . Compared with normally trained BERT, the agglomerative cluster encodings lead to a 9.8 point reduction in standard accuracy. Huang et al. (2019) , which defends against character substitution typos using interval bound propagation (IBP), also saw a drop in standard accuracy when building robust models. In fact, on the SST-2 test set, our agglomerative cluster model achieves standard accuracy of 84.6%, 10.2 points higher than their SST-2 model, while being robust to a larger class of typos. We attribute this improvement to our ability to use a stronger downstream model, namely BERT, while IBP was constrained to shallower, less effective models. Despite our standard accuracy drop from normal BERT, our encodings with BERT exceed the performance of even the normally trained model (CNN) used in Huang et al. (2019) by 4.8 points.

5.3. AGGLOMERATIVE CLUSTERING TRADEOFF:

In Figure 3 (b), we plot standard and robust accuracy on SST-2 for AGGCLUST encodings, using different values of γ . Recall that γ = 0 corresponds to the stability maximizing CONNCOMP, and γ = 1 maximizes fidelity by putting each vocabulary word in its own cluster (but still mapping out-of-vocabulary words to OOV). At γ = 0, the gap between standard and robust accuracy is very small, as the only difference is due to out-of-vocabulary words. As γ increases, the standard accuracy increases, but so does the gap between standard and robust accuracy. As a result, robust accuracy increases for a while, then decreases.

5.4. INTERNAL PERMUTATION ATTACKS:

Other work (Belinkov & Bisk, 2017; Sakaguchi et al., 2017) investigates robustness to internal permutations: reorderings of the characters in a word besides the first and last character. TARE can also be used to defend against these perturbations. For the normally trained BERT model, a heuristic beam search attack that uses internal permutations reduces average accuracy from 86.2% to 15.7% across our six tasks. Using connected component clusters defined using the internal permutation attack surface, we achieve robust accuracy of 81.4%. Full details and results are shown in Appendix A.8.

6. DISCUSSION:

Adversarial typos can cause large drops in model performance in settings where correct predictions are critical, such as hate-speech detection (Hosseini et al., 2017) and spam classification (Lee & Ng, 2005) . Ebrahimi et al. (2017) demonstrates that gradient-based attacks can be used to generate adversarial typos, and evaluates on the AG News dataset.

Besides typos, other perturbations can also be applied to text. Prior work considers semantic operations, such as replacing a word with a synonym (Alzantot et al., 2018; Ribeiro et al., 2018) . Our framework can be extended to these perturbations, as they merely define a different set of perturbations B(x i ) for each word x i . Other perturbations, such as syntactic rearrangements (Iyyer et al., 2018) or insertion of distracting text (Jia & Liang, 2017) , are more challenging to incorporate into our framework, and are interesting directions for future work.

Most existing defenses to adversarial perturbations involve specialized training procedures, and cannot be reused for multiple tasks. In computer vision, adversarial training with projected gradient descent yields models that are robust to various types of perturbations (Goodfellow et al., 2015; Madry et al., 2017) . However, it is nontrivial to port these methods to NLP, where inputs and perturbations are discrete. Adversarial training has been used to defend against heuristic attacks and random perturbations (Ebrahimi et al., 2017; 2018; Cheng et al., 2019) , but these models are often not robust to adversarial perturbations generated by more involved search procedures (Ebrahimi et al., 2017) . Using our representations with adversarial training could resolve this issue, since the worst-case attack is readily computable. Huang et al. (2019) and Jia et al. (2019) train NLP models that are robust to worst-case perturbations, but must retrain their entire system for each task and and are restricted to shallow models, as IBP bounds become loose for deep models.

Other defenses are based on various forms of preprocessing. Pruthi et al. (2019) use the typo-corrector from Sakaguchi et al. (2017) to correct perturbed inputs, but only consider cases where one or two tokens in the input are perturbed, and use heuristic search when perturbing two tokens. We consider a much larger attack surface in which every token may be perturbed, and compute exact robust accuracy. Gong et al. (2019) apply a spell-corrector to correct typos chosen to create ambiguity as to the original word, but these typos are not adversarially chosen to fool a model. Edizel et al. (2019) attempt to learn typo-resistant word embeddings, but focus on common typos, rather than worst-case typos. In computer vision, Chen et al. (2019) discretizes pixels to compute exact robust accuracy on MNIST, but their approach generalizes poorly to other tasks like CIFAR-10. Many recent advances in NLP have been fueled by the rise of task-agnostic representations, such as BERT, that facilitate the creation of accurate models for many tasks. Our work shows how to create task-agnostic representations that instead optimize for robustness to perturbations, as many natural tasks require robustness to the same perturbations, such as typos. We hope our work inspires new task-agnostic robust encodings that lead to more robust and more accurate models. C ← C next 8: end for 9: return C Now, we simply have to define the procedure we use to get the best combination.

Algorithm 2 Get Best Combination(C) 1: C opt ← C 2: Φ opt ← Φ(C) 3: for (C i , C j ) ∈ Adjacent Pairs(C) do 4: C comb ← C i ∪ C j 5: C new ← C ∪ C comb \ {C i , C j } {New clusters} 6: Φ new ← Φ(C new ) 7: if Φ new < Φ opt then 8: Φ opt ← Φ new 9: C opt ← C new 10:

end if 11: end for 12: return C opt Recall our graph G = (G, E) used to define the connected component clusters. We say two clusters C i and C j are adjacent, and thus returned by Adjacent Pairs, if there exists a v i ∈ C i and a v j ∈ C j such that (v i , v j ) ∈ G E . The runtime of our algorithm is O(N 2 E) since at each of a possible N total iterations, we compute the objective for one of at most E pairs of clusters. Computation of the objective can be reframed as computing the difference between Φ and Φ new , where the latter is computed using new clusters, which can be done in O(N ) time.

A.2 EXPERIMENTAL DETAILS:

For our methods using transformers, we start with the pretrained uncased BERT (Devlin et al., 2018) , using the same hyperparameters as the pytorch-transformers repo. 4 . In particular, we use the base uncased version of BERT. We use a batch size of 8, and learning rate 2e-5. For examples where |B α (x)| > 10000, we assume the prediction is not robust to make computation tractible. Each typo corrector uses the defaults for training from5 ; it is trained on a specific task using perturbations of the training data as input and the true sentence (up to OOV) as output. The vocabulary size of the typo correctors is 10000 including the unknown token, as in (Pruthi et al., 2019) . The typo corrector is chosen based on word-error rate on the validation set.

A.3 BOUNDING THE DIFFERENCE BETWEEN STANDARD AND ROBUST ACCURACY:

In (6), we show how to ensure robust accuracy if |B α (x)| = 1 for most x ∼ p task . Intuitively, we should be able to get high robust accuracy even if |B α (x)| > 1 but is relatively small. Here, we give a condition on f TARE under which having small average |B α (x)| 2 suffices. In this section, all expectations are taken over (x, y) ∼ p task .

Under review as a conference paper at ICLR 2020 For (x, y) ∼ p task and for encodings e sampled uniformly from B α (x), suppose that for some f down and f TARE (x) def = f down (α(x)), it is unlikely that f TARE (x) = y but f down (e) = y. More specifically, E P e∼Unif(Bα(x)) (f TARE (x) = y ∧ f down (e) = y) 2 (16) should be small, where Unif(B α (x)) denotes the uniform distribution over elements in B α (x). The inclusion of the square helps make our bounds below tighter.

If f down satisfies this, then we can bound the robust accuracy of f TARE in terms of its standard accuracy, its accuracy on random perturbations, and the size of B α (x): First, note that the difference between standard accuracy and robust accuracy can be written as 

In other words, standard accuracy and robust accuracy differ exactly on examples where the model is correct on x, but is incorrect on some e ∈ B α (x). We can upper-bound this by replacing the max operator with a sum: 

This completes the proof.

A.4 CONSTRAINED ADVERSARIES:

Using TARE, we can also consider adversaries that cannot perturb every input token. We may assume that an attacker has a budget of b ≤ L words that they may perturb as in (Pruthi et al., 2019) . Exiting methods for certification (Jia et al., 2019; Huang et al., 2019) require attack to be factorized over tokens, and cannot give tighter guarantees in the budget-constrained case compared to the unconstrained setting explored in previous sections. However, our method lets us easily compute robust accuracy exactly in this situation: we just enumerate the possible perturbations that satisfy the budget constraint, and query the model. Note that b = 0 is simply standard accuracy. Interestingly, for each dataset there is an attack only perturbing 4 tokens with attack accuracy equal to robust accuracy.

:

data.quora.com/First-Quora-Dataset-Release-Question-Pairs

https://github.com/huggingface/pytorch-transformers

On smaller datasets, augmenting with

perturbations per input did not significantly change attack accuracy.

https://github.com/huggingface/pytorch-transformers

https://github.com/danishpruthi/Adversarial-Misspellings

data.quora.com/First-Quora-Dataset-Release-Question-Pairs

Figures and Tables:

Figure 1: Task-agnostic robust encodings confer robustness to adversarial perturbations. Clean inputs x a and x b (blue) can be perturbed to many different sentences, denoted by the sets B(x a ) and B(x b ).We optimize an encoding function α such that for many sentences x, every perturbation of x maps to α(x), providing robustness to perturbations. The same encoding function can be used for multiple tasks, and any model using our encodings as input makes robust predictions.

Figure2: Visualization of three different encodings. Vocabulary words (large font, blue) share an edge if they share a common perturbation (small font, red). We show three different encodings: the bold line corresponds to the encoding with maximal stability (connected component encoding), the dotted lines correspond to maximizing fidelity, and the thin solid lines balance stability and fidelity (agglomerative clusters).

Figure 3(a) plots the distribution of |B α (x)| across test examples in SST-2 and RTE.

Figure 3: (a) Histogram of |B α (x)| for SST-2 and RTE. SST-2 has the highest percentage of inputs x where |B α (x)| = 1, while RTE has the least. On both datasets, |B α (x)| < 9 for most x, and is often 1. CONNCOMP encodings are more stable than the AGGCLUST encodings, at the cost of fidelity. (b) Standard and robust accuracies on SST-2 with agglomerative cluster encodings using different values of γ. While the gap between standard and robust accuracy increases monotonically, robust accuracy increases before decreasing.

acc robust ≥ acc std -E[|B α (x)| 2 ] • E P e∼Unif(Bα(x)) (f TARE (x) = y ∧ f down (e) = y) 2 , (17)Hence, if acc std (f TARE ) is large, and |B α (x)| 2 to be small on average, then robust accuracy will be high.Now we prove (17), which we equivalently write asacc stdacc robust ≤ E[|B α (x)| 2 ] • E P e∼Unif(Bα(x)) (f down (α(x)) = y ∧ f down (e) = y) 2 .

acc stdacc robust = E 1[f down (α(x)) = y] • max e∈Bα(x) 1[f down (e) = y] .

f down (α(x)) = y] • 1[f down (e) = y]   . (20)Applying the Cauchy-Schwarz Inequality, we can bound the right-hand side as:≤ E[|B α (x)| 2 ] • E |B α (x)| • 1[f down (α(x)) = y] • 1[f down (e) = y]expression that is squared inside the second expectation is simply P e∼Unif(Bα(x)) (f down (α(x)) = y ∧ f down (e) = y) .

Figure4plots average robust accuracy across the six tasks using AGGCLUST as a function of b. Note that b = 0 is simply standard accuracy. Interestingly, for each dataset there is an attack only perturbing 4 tokens with attack accuracy equal to robust accuracy.

f TARE outputs the same prediction for all perturbations of x. As |B α (x)| increases, perturbations get mapped to different possible encodings, which may be classified differently by f down . However, even when |B α (x)| > 1, keeping |B α (x)| small enables efficient computation of acc robust (f TARE ) by exhaustively enumerating B α (x). Without using α to collapse B(x) to a small number of encoded sentences, computing robust accuracy is intractable for arbitrary models.

Table content: <table/>

2019; Standard, robust, and attack accuracy on six GLUE tasks against ED1 perturbations. For baseline models, robust accuracy cannot be tractably computed, so we only compute attack accuracy, an upper bound on robust accuracy. Comparing these bounds, our agglomerative cluster encodings outperform the bast baseline, the typo corrector defense proposed byPruthi et al. (

Table content: <table><tr><td>Accuracy</td><td>System</td><td colspan="6">SST-2 MRPC QQP MNLI QNLI RTE</td><td>Avg</td></tr><tr><td/><td>Baselines</td><td/><td/><td/><td/><td/><td/><td/></tr><tr><td/><td>BERT</td><td>93.8</td><td>87.7</td><td>91.2</td><td>84.3</td><td>88.9</td><td>71.1</td><td>86.2</td></tr><tr><td/><td>Data Aug. + BERT</td><td>93.2</td><td>87.1</td><td>90.9</td><td>84.0</td><td>88.5</td><td>69.3</td><td>85.5</td></tr><tr><td>Standard</td><td>Typo Corr. + BERT</td><td>90.6</td><td>82.4</td><td>87.4</td><td>78.5</td><td>80.3</td><td>59.6</td><td>79.8</td></tr><tr><td/><td>TAREs</td><td/><td/><td/><td/><td/><td/><td/></tr><tr><td/><td>Con. Comp. + BERT</td><td>80.6</td><td>79.9</td><td>84.2</td><td>65.7</td><td>73.3</td><td>52.7</td><td>72.7</td></tr><tr><td/><td>Agg. Clust. + BERT</td><td>84.6</td><td>83.8</td><td>85.2</td><td>69.2</td><td>76.4</td><td>59.2</td><td>76.4</td></tr><tr><td/><td>Baselines</td><td/><td/><td/><td/><td/><td/><td/></tr><tr><td/><td>BERT</td><td>8.4</td><td>10.8</td><td>18.8</td><td>0.3</td><td>0.8</td><td>1.4</td><td>6.9</td></tr><tr><td/><td>Data Aug. + BERT</td><td>11.3</td><td>4.4</td><td>22.7</td><td>6.6</td><td>6.6</td><td>7.6</td><td>9.9</td></tr><tr><td>Attack</td><td>Typo Corr. + BERT</td><td>51.3</td><td>41.9</td><td>58.9</td><td>21.5</td><td>34.0</td><td>23.1</td><td>38.5</td></tr><tr><td/><td>TAREs</td><td/><td/><td/><td/><td/><td/><td/></tr><tr><td/><td>Con. Comp. + BERT</td><td>80.2</td><td>79.4</td><td>82.7</td><td>62.3</td><td>71.4</td><td>47.7</td><td>70.3</td></tr><tr><td/><td>Agg. Clust. + BERT</td><td>83.9</td><td colspan="2">82.4 83.4</td><td>65.7</td><td colspan="3">74.2 53.4 73.4</td></tr><tr><td/><td>TAREs</td><td/><td/><td/><td/><td/><td/><td/></tr><tr><td>Robust</td><td>Con. Comp. + BERT</td><td>80.1</td><td colspan="2">79.4 82.1</td><td>61.4</td><td>70.5</td><td>46.6</td><td>69.7</td></tr><tr><td/><td>Agg. Clust. + BERT</td><td>82.2</td><td>80.9</td><td>81.6</td><td>62.9</td><td colspan="3">71.7 49.8 71.2</td></tr></table>

Algorithm 1 Objective-minimizing agglomerative clustering 1: C ← V 2: for i in range(|V |) do

Table content: <table><tr><td>3:</td><td>C next ← Get Best Combination(C)</td></tr><tr><td>4:</td><td>if C = C next then</td></tr><tr><td>5:</td><td>return C</td></tr><tr><td>6:</td><td>end if</td></tr><tr><td>7:</td><td/></tr></table>

Peer review (iclr2020):
This paper explores a method for correcting typos in a *worst-case* way, in which worst case means against, for example, all mistakes of edit distance k for specified k. To me, this is an interesting problem because 1) typos do not work for word vectors, which is the most common input in downstream NLP tasks, 2) minimizing edit distance is a combinatorially hard problem, so all brute force methods are infeasible at scale. The paper provides a nice discussion of these issues, and proposes a graph-based method in which all words + their typo versions form a graph, and either a word is corrected by a representative word which is the most popular amongst connected components, or a softer version of this is used. The paper also describes a tradeoff between stability and fidelity (which I think is better understood as performance degradation) and discusses how this approach that really is task agnostic. Overall, I think the scheme is simple to understand and intuitive as to why it works well. Table 1 also looks like a nice collection of tasks, and the baselines seem reasonable. The main concern I have is I don*t see how the combinatorial nature is reduced. If you are given a corpus and someone writes a typo, what is the procedure? Is that typo already stored in a database, in which case the database is exponentially large in memory? Or do you need to compute edit distances in order to create this graph to begin with, having the combinatorial issue there? If the combinatorial issue is not resolved then I don*t see why this is better than just a nearest neighbor lookup where the distance is edit distance, which otherwise I would suggest as another important baseline. (If the authors can show this is a misunderstanding on my part, and/or include a much more in-depth discussion of the computational complexity of each scheme, I will increase my score.) My other main critique is that some things are a bit vague. For instance, I don*t understand how the sentence embedding is created, though it is discussed--the exact procedure is vague. Also, I don*t really understand equation (5). What is the std taken over? What is the random variable? It seems like the first term should be conditional on the accuracy of a typo-free scheme, since the task can be arbitrarily hard.