A Theoretical Framework for Robustness of (Deep) Classifiers against Adversarial ExamplesA Theoretical Framework for Robustness of (Deep) Classifiers against Adversarial ExamplesBeilun Wang and Ji Gao and Yanjun Qi2016
Paper summarydavidstutzWang et al. discuss an alternative definition of adversarial examples, taking into account an oracle classifier. Adversarial perturbations are usually constrained in their norm (e.g., $L_\infty$ norm for images); however, the main goal of this constraint is to ensure label invariance – if the image didn’t change notable, the label didn’t change either. As alternative formulation, the authors consider an oracle for the task, e.g., humans for image classification tasks. Then, an adversarial example is defined as a slightly perturbed input, whose predicted label changes, but where the true label (i.e., the oracle’s label) does not change. Additionally, the perturbation can be constrained in some norm; specifically, the perturbation can be constrained on the true manifold of the data, as represented by the oracle classifier. Based on this notion of adversarial examples, Wang et al. argue that deep neural networks are not robust as they utilize over-complete feature representations.
Also find this summary at [davidstutz.de](https://davidstutz.de/category/reading/).
First published: 2016/12/01 (2 years ago) Abstract: Most machine learning classifiers, including deep neural networks, are
vulnerable to adversarial examples. Such inputs are typically generated by
adding small but purposeful modifications that lead to incorrect outputs while
imperceptible to human eyes. The goal of this paper is not to introduce a
single method, but to make theoretical steps towards fully understanding
adversarial examples. By using concepts from topology, our theoretical analysis
brings forth the key reasons why an adversarial example can fool a classifier
($f_1$) and adds its oracle ($f_2$, like human eyes) in such analysis. By
investigating the topological relationship between two (pseudo)metric spaces
corresponding to predictor $f_1$ and oracle $f_2$, we develop necessary and
sufficient conditions that can determine if $f_1$ is always robust
(strong-robust) against adversarial examples according to $f_2$. Interestingly
our theorems indicate that just one unnecessary feature can make $f_1$ not
strong-robust, and the right feature representation learning is the key to
getting a classifier that is both accurate and strong-robust.