Annealing Genetic-based Preposition Substitution for Text Rubbish Example Generation

1 Introduction

Recent researches have shown that Deep Neural Networks (DNNs) are vulnerable to external perturbation in Natural Language Processing (NLP) field for text classification. Adversarial text examples have attracted much attention from researchers [Papernot et al., 2016; Jia and Liang, 2017; Li et al., 2020; Kwon and Lee, 2022; Wang et al., 2022]. The Adversarial text example is the slightly disturbed original

∗Corresponding author

SNLI

Premise

Before

After

Label

Confidence A man and a woman cross the street in front of a pizza and gyro restaurant.

The people are standing still on the curb.

The within are without among on the until.

Contradiction

95%→100%

MR

Before

After

Label

Confidence It's a tour de force, written and directed so quietly that it's implosion rather than explosion you fear.

It's a among de among, among and among so am-

ong that it's among among than among you among. Positiv e

92%→94%

Figure 1: The rubbish examples crafted by our AGPS.

input. These modifications are usually imperceptible to humans but can trigger DNNs' false prediction, which exposes DNNs' over-sensitivity to small changes. On the contrary, the rubbish example refers to the heavily modified example, where it is totally unrecognizable to humans but has nearly no effect on the model's prediction. Figure 1 lists several rubbish examples in our experiments, where the input words are replaced with meaningless prepositions, but the model still gives high confidence in the true label.

Rubbish examples reflect the under-sensitivity of modern DNNs to a large number of text modifications. [Welbl et al., 2020] emphasized that lack of sensitivity is a challenging issue for neural models, which usually leads to unreliable predictions in real text recognition tasks, such as spam filtering [Guzella and Caminhas, 2009], toxic comment detection [Risch and Krestel, 2020], resume recommendation [Roy et al., 2020], and medical diagnose [Bakator and Radosav, 2018]. Rubbish samples allow the model to leverage spurious clues in the data enough to achieve a high level of performance without understanding task-related textual meaning. Models can achieve strong nominal accuracy on the training set containing rubbish samples by utilizing prediction shortcuts that can not represent a given NLP task, but this leads to severe failure of prediction on samples without these spurious clues. Therefore, exploring potential text rubbish examples is crucial to expose DNNs' vulnerabilities to avoid security risks caused by such under-sensitivity.

The concept of rubbish example is primarily proposed by [Goodfellow et al., 2014; Nguyen et al., 2015] in the computer vision community by fooling images, which are nonsensical to humans as degenerate inputs but can be labeled with high confidence as a specific class by DNNs. In the NLP domain, [Feng et al., 2018] proposed a text rubbish example generation approach named input reduction, which iteratively removes insignificant words from the input sentence while maintaining the model's prediction unchanged. After the word deletions, some of the crafted rubbish examples contain only one or two words, which lack reasonable information for humans to make any predictions but the model can confidently retain the original prediction. However, there are three challenges to the input reduction method. Firstly, it employs the beam search to determine the word deletion priority, while this is usually not guaranteed to produce a globally optimal solution, i.e., deleting the most words. Secondly, during the word removal process, the semantic information of the words is not considered, the remaining words often contain important information for humans to make a correct decision. For example, in the sentiment analysis task, the original input classified as "positive" (i.e., A fascinating and fun film) is transformed into a rubbish example (i.e., fascinating), where the word "fascinating" strongly indicates a positive sentiment. Thirdly, a high-quality rubbish example should not affect the prediction of the DNNs model, but the reduced text usually causes a reduction in average model confidence over most datasets.

In this paper, we propose AGPS, an Annealing Genetic based Preposition Substitution algorithm for text rubbish sample generation to address these problems. Specifically, we first construct a set of substitution candidates by carefully collecting nonsensical prepositions. Each input word can be replaced with any candidate in the set of candidate substitutions, and our goal is to achieve more substitutions without reducing model confidence. In the second step, we present a hybrid Annealing Genetic algorithm to optimize the word replacement priority. Population-based search strategy can realize distributed search in the whole solution space, and skip the sub-optima combined with the Metropolis mechanism of the simulated annealing algorithm. This can make it a greater probability to approach the best rubbish sample, i.e., replacing the maximum number of input words. Extensive experiments demonstrate that the proposed AGPS generates more effective rubbish examples with higher model confidence. Our main contributions are summarized as follows:

• We propose a novel Annealing Genetic based Preposition Substitution to generate text rubbish examples. The AGPS replaces the words with nonsensical prepositions to alleviate the decrease in the model's confidence.
• We design an effective annealing genetic algorithm to optimize the word replacement priority, which steps out of the local optima with a probabilistic strategy. This is significant to find the global optimal of the objective function, i.e., a high word modification rate and high model confidence.
• We evaluate the effectiveness of our AGPS on five pop-

ular datasets by attacking seven representative DNNs models. Experimental results manifest that the AGPS outperforms the baseline and also shows good properties in retraining and transfer attacks.

2 RelatedWorks

In this section, we first introduce the adversarial sample and the rubbish sample, then we briefly review the classical genetic algorithm and the simulated annealing algorithm.

2.1 Textual Adversarial Attack

There is a growing body of research on NLP adversarial samples, where researchers have studied various invariant text transformations for different tasks. [Papernot et al., 2016] first focused on the adversarial samples in Natural Language Processing (NLP) field for text classification and proposed to generate adversarial input sequences on Recurrent Neural Networks (RNN). [Jia and Liang, 2017] fooled reading comprehension systems by linking a distracting sentence to the input paragraph. [Ebrahimi et al., 2017] presented a tokenflipping method, which crafted adversarial samples based on the gradients of the one-hot input vectors. [Zang et al., 2019] developed a sememe-based word substitution method and particle swarm optimization-based search algorithm, which treats word-level attacks as combinatorial optimization problems. [Wang et al., 2022] proposed SemAttack, a unified and effective semantic adversarial attack framework that leverages diverse semantic perturbation functions to generate natural adversarial text.

2.2 Rubbish Examples

Unlike the large volume of research on adversarial examples, the effect of rubbish examples is greatly underestimated. In the text domain, [Feng et al., 2018] introduced rubbish samples to explore the limitations of the NLP interpretation approaches. They achieved this by iteratively removing the least important words from the input while keeping the model predictions constant. The importance of each word is evaluated utilizing gradient-based approximation, and the word deletion optimization is completed using beam search. As a result, valid inputs are gradually transformed into rubbish samples, which lack prominent information to support humans to make a convincing decision but keep the original prediction of DNNs with high confidence. However, employing input reduction to craft rubbish examples has three challenges. Firstly, without the local optimal jump-out strategy, beam search might neglect potential global optimal solutions. Secondly, the rubbish example may contain significant words for effective human predictions since input reduction does not consider the semantics of the words. Thirdly, experiments indicate that in most cases, the reduction of input causes a decrease in model confidence, severely affecting the quality of generated rubbish samples.

2.3 Genetic Algorithm

Inspired by biological evolution in nature, the Genetic Algorithm (GA) is a heuristic algorithm that iteratively searches for the optimal solution by imitating natural selection. Specifically, the quality of population members is evaluated by the fitness function in each generation. Following the principle of survival of the fittest, parents are usually selected based on the fitness of individuals in the current generation. The next generation is generated through crossover and mutation. It has been proven effective in solving the optimization problems such as text clustering [Song and Park, 2009], text classification [Bidi and Elberrichi, 2016], and textual adversarial attacking [Alzantot et al., 2018]. However, there is a contradiction between the convergence speed and the global optimal solution of the basic genetic algorithm, and the basic genetic algorithm is prone to premature convergence.

2.4 Simulated Annealing Algorithm

The Simulated Annealing algorithm (SA) is inspired by the physical annealing procedure of metals. Generally, the SA starts from a high temperature with the initial molecules and aims to optimize the position of these molecules with the temperate drops. At each temperature, the simulation must proceed long enough for the system to reach equilibrium. The Metropolis principle allows the algorithm to jump out of the local optimal by chance. It accepts all solutions that are superior to the current solution and accepts inferior solutions by a probability related to the annealing temperature. The SA has been used in solving the optimization problems such as text summarization [Mosa et al., 2019] and textual adversarial attacking [Yang et al., 2021]. However, SA is highly dependent on the parameters (e.g., initial temperature, chilling temperature, and sampling times at each temperature), and inappropriate cooling methods or too fast cooling speed will also limit the solution quality of the algorithm.

3 Methodology

In this section, we discuss the details of the proposed AGPS algorithm, including the problem definition of black-box rubbish example generation (§ 3.1), the preposition-based word substitution (§ 3.2), and the annealing genetic optimization (§ 3.3). Figure 2 shows the workflow of our AGPS.

3.1 ProblemDefinition

Similar to the adversarial attack, the black-box rubbish example attacker can not access the model architecture, parameters, or gradients. We can only query the target model with supplied inputs to obtain the prediction results and confidence scores, which are closer to a real-world scenario.

Given an input space containing K samples X = {X1,X2, · · · ,XK} and an output space Y = {Y1,Y2, · · · ,YL} containing L labels, the classifier F needs to learn a mapping f : X → Y from any input sample X ∈ X to the correct label Ytrue, by maximizing the posterior probability:

The rubbish sample generation method aims to make heavy modifications to the input X to produce rubbish example X∗ , which is unreadable to humans but does not change the classifier's prediction:

Formally, the objectives are maximizing the difference △X between input X and rubbish output X∗ as shown in Eq. (3)

and simultaneously ensuring the classifier gives high confidence in the original label

Eq. (4) indicates that if the predicted label is not equal to the original label, we regard the modification as a failure and set the confidence to 0. The final objective function balances Eq. (3) and Eq. (4) with a parameter δ

where v is a constant to adjust the function value to an appropriate range. Therefore, the black-box rubbish example generation problem is equal to maximizing the objective function J . To optimize the objective function, we need to address two problems, i.e., (1) how to select substitution candidates, and (2) how to determine the word attack priority.

3.2 Preposition-basedWord Substitution

In this work, we propose to make preposition-based word substitution to produce human unreadable modifications, i.e., △X, because the prepositions usually contain no real semantic information. To this end, we collect 37 commonly used prepositions as a set of meaningless substitutions S. The attack starts with a Part-of-Speech (POS) tagging for each word. To achieve efficiency, we only replace four kinds of input words, i.e., only nouns, adjectives, verbs, and adverbs, and filter out all the other words. For each modifiable word wi, we search for the substitution word w′i from S.

Every w′i ∈ S is a potential candidate for replacing the original word wi. To select the best candidate from S, we define the candidate score as the original label probability:

where

Then we identify the candidate w′i that maximizes the prediction probability of the original label as the best substitution word, i.e.,

This solves the first problem.

3.3 Annealing Genetic Algorithm

After candidate selection, each input word can be replaced as a determined preposition. Then we need to optimize the word modification priority. In this work, we propose an annealing genetic algorithm to determine the attacking sequence, which allows the traditional GA to jump out of local optimal with the Metropolis principle. Specifically, after the crossover, the proposed annealing genetic accepts some individuals with a worse objective value than their parents by a probability. This allows the evolution proceeds to the global optimal solution. Besides, it can also avoid the excessive dependence of the SA on parameters and improve the solution stability.

To detail our algorithm, we first introduce the subroutine Crossover and Mutation.

• Crossover: The input of this subroutine is two parent individuals, i.e. P1 and P2, which are two sentences. It scans each modifiable word in P1 in turn and then exchanges words with the corresponding position of P2, where the input words are independent of each other and have the same crossover probability. This process also follows the substitution principle in section 3.2, i.e., only exchanging nouns, adjectives, verbs, and adverbs.
• Mutation: We adopt a single point mutation strategy. The input of the subroutine is a single individual, which can be the original input sentence or its modification. It randomly selects a modifiable word wi in the original sentence to replace. The substitution candidate w′i belongs to S. The best substitution word selection method follows Eq. (8).

The optimization procedure is given in Algorithm 1. Next, we describe our algorithm step by step.

Firstly, we initialize the first generation by repeating the mutation subroutine for N times to get N population members X0 = {X01 ,X02 , · · · ,X0N } as shown in line 2-4 of Algorithm 1. Then, we obtain the fitness of each population member in the initial generation by querying the victim model function J .

We adopt the proportional selection approach to select the parents to breed the next generation population. To make the well-performing population members have a higher probability of being selected as parents, the ith individual in the current population is selected with a probability proportional pi

Algorithm 1: The proposed AGPS algorithm

Input: Input sentence Xori = (w1, · · · ,wn) Input: DNNs classifier F Output: Rubbish example X∗ 1 Initialization: the population size N = 40, the number of iteration times G = 15, the temperature T = 1000, the attenuation factor α = 0.85, the balance parameter δ = 2.5, the initial rubbish example X∗ = Xori; /* Initialize the first generation */ 2 for i = 1, · · · ,N do 3 X0i ←Mutation(Xori); 4 y0 i = J(X0i ); 5 X∗ = X0argmaxjy0 j ; ▷ Optimal individual /* The Annealing Genetic Starts */ 6 for g = 1, · · · ,G do 7 for i = 1, · · · ,N do 8 Select parents P1 and P2 from Xg-1 with pselect in Eq. (9); 9 child ← Crossover(P1, P2); /* Metropolis accept crossover */ 10 Xgi = PargmaxjJ(Pj); 11 if J (child) ≥ J (Xgi ) then 12 Xgi = child; 13 else 14 p = e-(J (Xgi )-J (child))/T ; 15 r = random(0, 1); 16 if r < p then 17 Xgi = child; 18 childm ← Mutation(Xgi ); /* Metropolis accept mutation */ 19 if J (childm) ≥ J (Xgi ) then 20 Xgi = childm; 21 else 22 p = e-(J (Xgi )-J (childm))/T ; 23 r = random(0, 1); 24 if r < p then 25 Xgi = childm; 26 T = α×T ; ▷ Porportional annealing /* Optimal individual preservation */ 27 for i = 1, · · · ,N do 28 yg i = J(Xgi ); 29 Xgbest = Xgargmaxjyg j ; 30 if J (Xgbest ) > J (X∗ ) then 31 X∗ = Xgbest ; 32 return X∗

to its fitness J (Xi) in line 8.J (Xi)

In the population evolution step, we perform crossover and mutation operations on the selected parent members. Specifically, the new child sample is synthesized by calling the Crossover subroutine. To decide whether the child is accepted or not, we follow the typical Metropolis principle.

If the fitness score of the child is higher than that of the parents, we directly accept it as the next generation population member. Otherwise, we accept an inferior sample by Eq. (10) as shown in lines 14-17. If not accepted, pick the parent with higher fitness to be the child for the next iteration in line 10. Finally, the Mutation subroutine is implemented to the resulting child and the Metropolis principle is employed to determine whether to accept this mutation. As these two subroutines are based on individuals rather than populations, we iteratively perform the Crossover and Mutation subroutine to generate N population members of the new generation.

In line 26, we select the proportional cooling strategy to reduce the temperature

where the attenuation factor α = 0.85.

Then we record the best individuals after each iteration by computing the fitness of all individuals in each generation and preserving optimal individuals to promote the population evolution. Finally, the optimization will be terminated if the evolution reaches the upper bound or it generates a good rubbish example. This solves the second problem.

4 Experiments

We provide the source code in the GitHub 1 to ensure that all the results in this section are reproducible.

4.1 Datasets and VictimModels

We assess the attack performance on five public datasets, such as Stanford Sentiment Treebank (SST-2), Movie Reviews (MR), Stanford Natural Language Inference (SNLI), Quora Question Pairs (QQP), and Microsoft Research Paraphrase Corpus (MRPC).

• SST-2 [Socher et al., 2013] consists of 67349 training examples and 1821 testing samples, and each example is a movie review with binary classes. The task is to predict if the text comment belongs to positive or negative emotions.
• MR [Pang and Lee, 2005] is also a sentiment classification dataset, containing 8530 training data and 1066 test data. Similar to SST-2, all the examples belong to positive or negative comments for movies.
• SNLI [Bowman et al., 2015] is a popular question inference corpus with 550152 examples for training and 10000 examples for testing, where each example consists of a question pair. The two questions are duplicate or not duplicate.
• QQP [Shankar et al., 2017] is another question inference database with the same labels as SNLI, i.e., duplicate and not duplicate. It covers 363846 and 390965 examples in the train set and test set, respectively.

1 https://github.com/soar-create/AGPS

• MRPC [Wang et al., 2018] includes 3668 sentence pairs for model training and 1725 sentence pairs for testing, which can be divided into two categories, i.e., the two sentences are semantically equivalent or not equivalent.

We attack seven victim models to test the capability of our AGPS, such as CNN, LSTM, BERT (bert-baseuncased) [Devlin et al., 2018], DistilBERT (distilbert-baseuncased, distilbert-base-cased) [Sanh et al., 2019], RoBERTa (roberta-base) [Liu et al., 2019], ALBERT (albert-basev2) [Lan et al., 2019], and XLNet (xlnet-base-cased) [Yang et al., 2019]. We download the models from HuggingFace 2 .

4.2 Baseline Method

To evaluate the effectiveness of our AGPS, we compare it with Input Reduction (IR) [Feng et al., 2018]. To the best of our knowledge, this is the single rubbish example generation work in the text field. The IR crafts the rubbish samples by iteratively removing unimportant words from the input with beam search. The objective are (1) craft short rubbish text examples that lack enough information for a human to make a decision, and (2) keep the model's prediction unchanged.

4.3 EvaluationMetrics

We evaluate the quality of rubbish samples with the following three metrics.

Modification rate. The percentage of modified words. Since we only modify the input words with semantic meanings, including nouns, adjectives, verbs, and adverbs, we only take these words into account when reporting the word modification rate.

Model confidence. The true label probability of the classifier for the rubbish sample.

Semantic similarity. The semantic similarity between the original sample and the rubbish sample. Following [Jin et al., 2019; Morris et al., 2020a], we employ the universal sentence encoder (USE) [Cer et al., 2018] with cosine similarity to estimate the semantic similarity.

4.4 Experimental Setup

The parameter settings for our AGPS are given in the initialization, i.e., line 1, of Algorithm 1. For the baseline, we use the author-recommended parameter settings. We randomly select 500 examples from each dataset to implement the text rubbish attack for a fair comparison. In the natural language inference task (i.e., SNLI), we only modify the hypothesis, while keeping the premise unchanged. All experiments are implemented on the NLP attack package TextAttack [Morris et al., 2020b].

4.5 Experimental Results

The experimental results of model confidence, modification rate, and semantic similarity are shown in Table 1. We ask the following three questions to manifest the contributions as claimed in the Introduction section.

2 https://huggingface.co/models

Question 1: Is the preposition substitution better than word deletion in keeping the model's confidence? To answer this question, we list the model confidence on the text rubbish examples generated by IR and our AGPS as well as the original sentences in Table 1. From the Con part, we can see that our AGPS outperforms the baseline by a large margin, i.e. improves by 7.97% on average. Besides, the seven victim models even exhibit higher confidence (by 2.5%) in our AGPS rubbish examples than the original examples. This strongly validates the superiority of preposition-based word replacement in generating text rubbish examples.

Question 2: Is the Annealing Genetic algorithm superior to the beam search in skipping the local optimal? To reply to this question, we list the word modification rate in Table 1, as the common objective of beam search and the annealing genetic is to modify the maximal number of words. The results in Table 1 show that our AGPS improves the Mod by 10.05% in comparison with the baseline. A higher word modification rate indicates a higher quality of the rubbish example because either word deletion or preposition substitution can improve semantic confusion for human readers.

Question 3: Can our AGPS avoid generating semantic consistency text? We answer this question by comparing the semantic similarity in Table 1 'Sim' column. The results imply that our AGPS achieves comparable semantic similarity with IR, i.e., superior to the IR by only 0.0032. However, we observe that the IR frequently preserves important label information in the final rubbish examples. Table 2 exhibits two rubbish examples crafted by IR and AGPS. Intuitively, the IR examples containing 'joyful' clearly suggest a positive sentiment for humans, while AGPS properly solves this problem.

Overall AGPS achieves better performance than the baseline on these three metrics across different datasets, which demonstrates the superiority of our approach.

4.6 Attribution Visualization and Analysis

Feature attribution is a popular strategy for model interpretation. Figure 3 visualizes the word replacement path and the dynamic changes in word importance. Our AGPS example satisfies the definition of rubbish example: (1) humans can not make any predictions for the nonsensical preposition sequence, but (2) the model's confidence is enhanced from 95% to 100%. Besides, we observe three interesting properties of DNNs models. Firstly, the model tends to pay more attention to those unmodified words (e.g. 'it' in the third step), although it is not important before. Secondly, sometimes replacing the most important words does not reduce the model's confidence but increases it, e.g., the 'Ultimately→Through' improves the confidence by 2%. These phenomenons bring challenges to the interpretation methods, which interpret the model properties relying on the word importance [Feng et al., 2018; Ghorbani et al., 2019]. We hope these findings promote the development of model interpretation theory.

4.7 Adversarial Training

Adversarial training is a prevalent defense strategy on adversarial robustness by incorporating adversarial examples into the training set. In this part, we randomly generate and join {500, 1000, 2000} MR rubbish samples as the negative sample set to the training data and retrain the BERT model. Then we re-attack the retrained model to test the defense performance. As shown in Table 3, adversarial training improves the difficulty of attack, because attacking the retrained model with fewer modification rates, lower model confidence, and the rubbish example carries more semantics. Besides, Figure 4 shows the multi-retrain classification accuracy on the test set. Figure 4 illustrates that AGPS brings greater robustness improvement than the baseline.

4.8 Transferability

For rubbish examples, transferability refers to whether the rubbish sample designed for a model F1 can also hold the same prediction on another unknown model F2. We evaluate the transferability on SST-2 dataset. Specially, we collect the rubbish examples crafted for BERT and then test the transferability on four unknown models (CNN, RoBERTa , AlBERT, and DistilBERT). The experimental results in Figure 5 illustrate that both IR and AGPS exhibit high transferability on most models (i.e., RoBERTa, ALBERT, DistilBERT), and our AGPS outperforms IR in most cases.

5 Conclusion

In this paper, we proposed an innovative AGPS algorithm for generating text rubbish examples. The AGPS employs the preposition substitution strategy instead of word deletions to reduce the loss of model confidence. We also designed an annealing genetic algorithm to determine the word modification priority, which allows the optimization to jump out of local optima. The research exposes the under-sensitivity of neural models: the input can be modified to the nonsensical word sequences, but the model even exhibits higher original label confidence. In the future, our works can be employed to test the interpretation methods, and we hope these results encourage further work in improving the robustness and interpretability of natural language models.

Acknowledgments

This work was supported in part by the Yunnan Provincial Major Science and Technology Special Plan Projects (Grant 202202AD080003), in part by the Outstanding Youth Science Foundation Project of Shandong Province (Overseas) (Grant No.2023HWYQ-070), and in part by the Independent Innovation Research Project (Grant No.22CX06059A).