PaperlayerView exact revision on arXiv

Source-linked AI summary

SAFER: A Structure-free Approach for Certified Robustness to Adversarial Word Substitutions

Mao Ye, Chengyue Gong, Qiang Liu

arXiv:2005.14424v1cs.LGcs.CLcs.CRstat.ML

TL;DR

Synonymous word substitutions can fool NLP models while preserving sentence meaning, and certifying robustness requires accounting for an exponentially large set of possible changes. The paper uses black-box randomized smoothing to certify arbitrary model structures, and reports significant gains over recent methods on IMDB and Amazon, including 87.35% certified accuracy on IMDB with BERT.

  • Problem

    Synonymous substitutions can preserve sentence meaning yet alter model predictions, and certifying against all such changes requires checking an exponentially large candidate set.

    Source: §1 · p. 1

  • Method

    The method applies random word substitutions and uses the resulting ensemble's statistical properties to certify robustness through black-box queries, without requiring model-structure information.

    Source: §1 · p. 2

  • Results

    The method significantly outperforms recent certified-robustness methods on IMDB and Amazon, reaching 87.35% certified accuracy on IMDB with BERT.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The approach extends randomized smoothing to discrete and structured NLP inputs and applies to arbitrary black-box-queryable models.

    Source: §1 · p. 2

    The synonym-network-based perturbation-set construction is heuristic and may not be optimal.

    Source: §5 · p. 5

Abstract

from arXiv · show

State-of-the-art NLP models can often be fooled by human-unaware transformations such as synonymous word substitution. For security reasons, it is of critical importance to develop models with certified robustness that can provably guarantee that the prediction is can not be altered by any possible synonymous word substitution. In this work, we propose a certified robust method based on a new randomized smoothing technique, which constructs a stochastic ensemble by applying random word substitutions on the input sentences, and leverage the statistical properties of the ensemble to provably certify the robustness. Our method is simple and structure-free in that it only requires the black-box queries of the model outputs, and hence can be applied to any pre-trained models (such as BERT) and any types of models (world-level or subword-level). Our method significantly outperforms recent state-of-the-art methods for certified robustness on both IMDB and Amazon text classification tasks. To the best of our knowledge, we are the first work to achieve certified robustness on large systems such as BERT with practically meaningful certified accuracy.

1 Introduction

The paper addresses synonymous substitutions that preserve sentence meaning but can fool NLP models, while certification must account for an exponentially large set of substitutions. It proposes black-box randomized smoothing for arbitrary model structures and reports gains over IBP-based methods on IMDB and Amazon, including BERT.

1 Introduction

  • Certification against synonymous substitutions must rule out every meaning-preserving replacement, an exponentially large search even when the synonym table is known.The attacker replaces words with synonyms while seeking to change the model output.Source: §1 · p. 1
  • IBP-based certified defenses operate on continuous inputs, so their word-embedding input formulation does not apply to character-level or subword-level models.The paper notes that character- and subword-level models are widely used in practice.Source: §1 · p. 1
  • Randomized smoothing applies random word substitutions and uses ensemble statistics to construct provable certification bounds for black-box models without structural requirements.The approach extends randomized smoothing to discrete and structured NLP inputs.Source: §1 · p. 2
  • 87.35% certified accuracy on IMDB with BERT; the method significantly outperforms recent certified-robustness methods on IMDB and Amazon.Previous certified robust methods were not applicable to BERT.Source: §1 · p. 2

2 Adversarial Word Substitution

The section defines synonym substitutions as changes to at most R words using predefined synonym sets, with the intended meaning preserved. Certified robustness requires consistently correct predictions across all such perturbations, a difficult check when the candidate set grows exponentially.

2 Adversarial Word Substitution

  • A word's predefined synonym set includes the word itself, and the synonymous relation is assumed symmetric.The set can be built using GLOVE.Source: §2 · p. 2
  • An attacker may replace at most R of the sentence's L words with synonyms, seeking a sentence that preserves meaning for human readers but changes the model output.The perturbation set comprises candidate adversarial sentences formed by these substitutions.Source: §2 · p. 2
  • Certified robustness requires correct predictions for every possible word-substitution perturbation; checking candidates grows exponentially with R, and the paper focuses on the hardest case, R = L.The certification criterion is defined relative to the sentence's true label.Source: §2 · p. 2

3 Certifying Smoothed Classifiers

The method smooths a classifier by averaging predictions over random word substitutions, then certifies robustness using bounds on the smoothed classifier. Its practical procedure estimates those bounds from black-box model outputs and can train the base classifier with perturbation-based augmentation.

3 Certifying Smoothed Classifiers

  • The perturbation distribution independently replaces each input word uniformly with a word from its perturbation set, constructed from top-K nearest GloVe neighbors.The perturbation sets are distinct from synonym sets, and their size is controlled by K.Source: §3 · pp. 2–3

3.1 Certified Robustness

  • Randomized smoothing bounds changes in class scores under adversarial substitutions, avoiding optimization over candidate sentences by evaluating the original input.The bounds are tight under the stated assumptions; with access only to the two relevant class scores, they cannot be improved without further model information.Source: §3.1 · pp. 3–4
  • A sentence is certified when Δ_X is positive, a condition that can be checked using Monte Carlo estimates of the smoothed classifier's class probabilities.Concentration inequalities quantify finite-sample approximation error and support a statistical test at a chosen significance level.Source: §3.1 · p. 3
  • The certification procedure is structure-free: it requires only black-box assessments of model outputs on randomly perturbed inputs.It does not require structural information about either the base model or the smoothed classifier.Source: §3.1 · p. 3

3.2 Practical Algorithm

  • The practical pipeline derives perturbation sets from synonym sets, samples perturbed sentences, averages their outputs to estimate Δ_X, and uses that estimate to decide certification.The method can also train the base classifier with perturbation-based data augmentation to improve the smoothed classifier's accuracy.Source: §3.2 · p. 4
  • For BERT, the method uses the model to construct feature maps and fine-tunes only the top-layer weights with data augmentation.The paper states that this approach can leverage pre-trained models such as BERT.Source: §3.2 · p. 4

4 Experiments

Experiments compare the method with IBP on IMDB and Amazon using several model types, with all sentence words eligible for perturbation. The method improves certified accuracy in the reported comparisons, while increasing K trades clean accuracy for smoother predictions.

4 Experiments

  • The evaluation covers IMDB and Amazon with text CNN, Char-CNN, and BERT, comparing against IBP while allowing the attacker to perturb all sentence words.The synonym sets use words with at least 0.8 cosine similarity in a post-processed GloVe space.Source: §4 · p. 4
  • The perturbation set uses synonym-connected words ranked by GloVe similarity, with K controlling its size and the smoothness–accuracy trade-off.K = 100 is the default.Source: §4 · p. 4

4.1 Main Results

  • On Amazon, certified accuracy improves from 14.00% with IBP to 24.92% with the proposed method.The reported comparison also says the method outperforms IBP on both IMDB and Amazon.Source: §4.1 · p. 5, Table 1 · p. 5
  • On IMDB, BERT reaches 87.35% certified accuracy, versus 79.74% for the IBP baseline under the same setting.The method also applies to Char-CNN, a character-level model.Source: §4.1 · p. 5, Table 2 · p. 5

4.2 Trade-Off between Clean Accuracy and Certified Accuracy

  • As K increases, clean accuracy and the gap between clean and certified accuracy both decrease; the best certified accuracy occurs at K = 100.Table 3 reports clean and certified accuracy for the smoothed text CNN on IMDB across K values.Source: §4.2 · p. 5, Table 3 · p. 5

5 Conclusion

The paper concludes that its certification method guarantees robustness to the allowed perturbations and is structure-free, allowing application to pretrained and character-level models. It identifies perturbation-set construction as a key open limitation and other NLP attacks as future scope.

5 Conclusion

  • The method is structure-free and can be applied to pretrained models such as BERT and character-level models such as Char-CNN.The authors contrast this applicability with prior work by Jia et al. (2019) and Huang et al. (2019).Source: §5 · p. 5
  • The perturbation-set construction is heuristic and may not be optimal, motivating exploration of more efficient construction methods.The authors also identify extending certification to attacks such as out-of-list attacks as future work.Source: §5 · p. 5

A.1 Bounding the Error of Monte Carlo Estimation

This appendix bounds Monte Carlo estimation error and uses the bound to frame certification as a hypothesis test.

A.1 Bounding the Error of Monte Carlo Estimation

  • The appendix uses Hoeffding’s concentration inequality and a union bound to bound non-asymptotic Monte Carlo estimation error.The bound is stated for independent samples drawn from ΠX and confidence parameter δ.Source: §A.1 · p. 7
  • Certification is framed as testing whether ∆X > 0, which indicates that the smoothed model is certified robust at X.The procedure rejects the null hypothesis at significance level δ when the stated bound permits it.Source: §A.1 · p. 7
  • The experiments set δ = 0.01 and use n = 5000 Monte Carlo samples.Source: §A.1 · p. 7

A.2 Proof of the Main Theorems

This appendix section gives proofs of the theorems in the main text.

A.2 Proof of the Main Theorems

  • The appendix section provides proofs for the theorems stated in the main text.Source: §A.2 · p. 7

A.2.1 Proof of Proposition 1

The proof connects the stated robustness criterion for the smoothed classifier to a sufficient condition for certification.

  • Certification at X requires fRS(X′) to equal y for every X′ in SX.Source: §A.2.1 · p. 7
  • The criterion expresses invariance of the smoothed classifier's prediction across the perturbation set SX.Source: §A.2.1 · p. 7
  • ΔX > 0 implies condition (3), and therefore certified robustness.Source: §A.2.1 · p. 7

A.2.2 Proof of Theorem 1

The proof bounds the smoothed classifier’s behavior by reducing the relevant optimization problems to variational optimization and identifying an extremal adversarial sentence.

  • The proof frames the bounds as variational optimization and applies a Lagrange multiplier to the constrained problem.Source: §A.2.2 · p. 8
  • Under Theorem 1’s assumptions, Theorem 3 gives an upper bound for the optimization problems in Lemma 1: up(X, c) ≤ min(gRS(X, c) + qX, 1).Source: §A.2.2 · p. 8
  • The synonym-set identity is applied under the assumption that each word and its synonym have equal synonym-set cardinalities.Source: §A.2.2 · p. 9
  • The constructed X* is an optimal solution to the maximization over synonym-substituted sentences.The proof also states Q(X, X*) ≥ Q(X, X′) for competing X′.Source: §A.2.2 · pp. 9–10
  • For the scalar optimization in (4), the stated optimum uses λ*=0 when p≤q and λ*=1 when p≥q.The corresponding solutions are 0 and (p − qX), respectively.Source: §A.2.2 · p. 9

A.2.3 Proof of Theorem 2

The proof supports Theorem 2 by constructing randomized smoothing classifiers that satisfy the desired property across cases defined by pA, pB, and q.

  • The proof constructs a randomized smoothing classifier to establish the desired property.Source: §A.2.3 · p. 11
  • For pA ≥ q and pB + q ≤ 1, the proof allocates disjoint U1 and U2 subsets of SX ∩ SX* to define the classifier.Source: §A.2.3 · p. 11
  • For pA < q and pB + q ≤ 1, U1 is chosen from SX − SX* and U2 from SX ∩ SX* before defining the classifier.Source: §A.2.3 · p. 11
  • The case pA ≥ q and pB + q > 1 cannot occur because it would imply pA + pB > 1.Source: §A.2.3 · p. 11

B Additional Experiment Details

The experiments allow all sentence words to be perturbed, estimate ΔX with Monte Carlo draws, and use different training durations for the two datasets.

Loading 2005.14424v1…