Discrete Adversarial Attacks and Submodular Optimization with Applications to Text Classification

Adversarial examples are carefully constructed modifications to an input that\ncompletely change the output of a classifier but are imperceptible to humans.\nDespite these successful attacks for continuous data (such as image and audio\nsamples), generating adversarial examples for discrete structures such as text\nhas proven significantly more challenging. In this paper we formulate the\nattacks with discrete input on a set function as an optimization task. We prove\nthat this set function is submodular for some popular neural network text\nclassifiers under simplifying assumption. This finding guarantees a $1-1/e$\napproximation factor for attacks that use the greedy algorithm. Meanwhile, we\nshow how to use the gradient of the attacked classifier to guide the greedy\nsearch. Empirical studies with our proposed optimization scheme show\nsignificantly improved attack ability and efficiency, on three different text\nclassification tasks over various baselines. We also use a joint sentence and\nword paraphrasing technique to maintain the original semantics and syntax of\nthe text. This is validated by a human subject evaluation in subjective metrics\non the quality and semantic coherence of our generated adversarial text.\n