EXCESSIVE INVARIANCE CAUSES ADVERSARIAL VULNERABILITY
Year: 2019

Abstract:
Despite their impressive performance, deep neural networks exhibit striking failures on out-of-distribution inputs. One core idea of adversarial example research is to reveal neural network errors under such distribution shifts. We decompose these errors into two complementary sources: sensitivity and invariance. We show deep networks are not only too sensitive to task-irrelevant changes of their input, as is well-known from -adversarial examples, but are also too invariant to a wide range of task-relevant changes, thus making vast regions in input space vulnerable to adversarial attacks. We show such excessive invariance occurs across various tasks and architecture types. On MNIST and ImageNet one can manipulate the class-specific content of almost any image without changing the hidden activations. We identify an insufficiency of the standard cross-entropy loss as a reason for these failures. Further, we extend this objective based on an informationtheoretic analysis so it encourages the model to consider all task-dependent features in its decision. This provides the first approach tailored explicitly to overcome excessive invariance and resulting vulnerabilities.

text: Despite their impressive performance, deep neural networks exhibit striking failures on out-of-distribution inputs. One core idea of adversarial example research is to reveal neural network errors under such distribution shifts. We decompose these errors into two complementary sources: sensitivity and invariance. We show deep networks are not only too sensitive to task-irrelevant changes of their input, as is well-known from -adversarial examples, but are also too invariant to a wide range of task-relevant changes, thus making vast regions in input space vulnerable to adversarial attacks. We show such excessive invariance occurs across various tasks and architecture types. On MNIST and ImageNet one can manipulate the class-specific content of almost any image without changing the hidden activations. We identify an insufficiency of the standard cross-entropy loss as a reason for these failures. Further, we extend this objective based on an informationtheoretic analysis so it encourages the model to consider all task-dependent features in its decision. This provides the first approach tailored explicitly to overcome excessive invariance and resulting vulnerabilities.

heading: 1 INTRODUCTION
text: Adversarial vulnerability is one of the most iconic failure cases of modern machine learning models (Szegedy et al., 2013) and a prime example of their weakness in out-of-distribution generalization. It is particularly striking that under i.i.d. settings deep networks show superhuman performance on many tasks (LeCun et al., 2015), while tiny targeted shifts of the input distribution can cause them to make unintuitive mistakes. The reason for these failures and how they may be avoided or at least mitigated is an active research area (Schmidt et al., 2018; Gilmer et al., 2018b; Bubeck et al., 2018).
So far, the study of adversarial examples has mostly been concerned with the setting of small perturbation, or -adversaries (Goodfellow et al., 2015; Madry et al., 2017; Raghunathan et al., 2018).
Perturbation-based adversarial examples are appealing because they allow to quantitatively measure notions of adversarial robustness (Brendel et al., 2018). However, recent work argued that the perturbation-based approach is unrealistically restrictive and called for the need of generalizing the concept of adversarial examples to the unrestricted case, including any input crafted to be misinterpreted by the learned model (Song et al., 2018; Brown et al., 2018). Yet, settings beyond -robustness are hard to formalize (Gilmer et al., 2018a).
We argue here for an alternative, complementary viewpoint on the problem of adversarial examples. Instead of focusing on transformations erroneously crossing the decision-boundary of classifiers, we focus on excessive invariance as a major cause for adversarial vulnerability. To this end, we introduce the concept of invariance-based adversarial examples and show that class-specific content of almost any input can be changed arbitrarily without changing activations of the network, as illustrated in figure 1 for ImageNet. This viewpoint opens up new directions to analyze and control crucial aspects underlying vulnerability to unrestricted adversarial examples.
The invariance perspective suggests that adversarial vulnerability is a consequence of narrow learning, yielding classifiers that rely only on few highly predictive features in their decisions. This has also been supported by the observation that deep networks strongly rely on spectral statistical regularities (Jo & Bengio, 2017), or stationary statistics (Gatys et al., 2017) to make their decisions, rather than more abstract features like shape and appearance. We hypothesize that a major reason for this excessive invariance can be understood from an information-theoretic viewpoint of crossentropy, which maximizes a bound on the mutual information between labels and representation, giving no incentive to explain all class-dependent aspects of the input. This may be desirable in some cases, but to achieve truly general understanding of a scene or an object, machine learning models have to learn to successfully separate essence from nuisance and subsequently generalize even under shifted input distributions.
Our contributions:
• We identify excessive invariance underlying striking failures in deep networks and formalize the connection to adversarial examples.
• We show invariance-based adversarial examples can be observed across various tasks and types of deep network architectures.
• We propose an invertible network architecture that gives explicit access to its decision space, enabling class-specific manipulations to images while leaving all dimensions of the representation seen by the final classifier invariant.
• From an information-theoretic viewpoint, we identify the cross-entropy objective as a major reason for the observed failures. Leveraging invertible networks, we propose an alternative objective that provably reduces excessive invariance and works well in practice.

heading: 2 TWO COMPLEMENTARY APPROACHES TO ADVERSARIAL EXAMPLES
text: In this section, we define pre-images and establish a link to adversarial examples.
Definition 1 (Pre-images / Invariance). Let F : Rd → RC be a neural network, F = fL ◦ · · · ◦ f1 with layers fi and let Fi denote the network up to layer i. Further, let D : Rd → {1, . . . , C} be a classifier with D = arg maxk=1,...,C softmax(F (x))k. Then, for input x ∈ Rd, we define the following pre-images
(i) i-th Layer pre-image: {x∗ ∈ Rd | Fi(x∗) = Fi(x)}
(ii) Logit pre-image: {x∗ ∈ Rd | F (x∗) = F (x)}
(iii) Argmax pre-image: {x∗ ∈ Rd | D(x∗) = D(x)},
where (i) ⊂ (ii) ⊂ (iii) by the compositional nature of D. Moreover, the (sub-)network is invariant to perturbations ∆x which satisfy x∗ = x+ ∆x.
Non-trivial pre-images (pre-images containing more elements than input x) after the i-th layer occur if the chain fi ◦ · · · ◦ f1 is not injective, for instance due to subsampling or non-injective activation functions like ReLU (Behrmann et al., 2018a). This accumulated invariance can become problematic if not controlled properly, as we will show in the following.
We define perturbation-based adversarial examples by introducing the notion of an oracle (e.g., a human decision-maker or the unknown input-output function considered in learning theory): Definition 2 (Perturbation-based Adversarial Examples). A Perturbation-based adversarial example x∗ ∈ Rd of x ∈ Rd fulfills:
(i) Perturbation of decision: D(x∗) 6= o(x∗) and D(x) 6= D(x∗), where D : Rd → {1, . . . , C} is the classifier and o : Rd → {1, . . . , C} is the oracle.
(ii) Created by adversary: x∗ ∈ Rd is created by an algorithm A : Rd → Rd with x 7→ x∗.
Further, -bounded adversarial ex. x∗ of x fulfill ‖x− x∗‖ < , ‖ · ‖ a norm on Rd and > 0.
Usually, such examples are constructed as -bounded adversarial examples (Goodfellow et al., 2015). However, as our goal is to characterize general invariances of the network, we do not restrict ourselves to bounded perturbations. Definition 3 (Invariance-based Adversarial Examples). Let G denote the i-th layer, logits or the classifier (Definition 1) and let x∗ 6= x be in the G pre-image of x and and o an oracle (Definition 2). Then, an invariance-based adversarial example fulfills o(x) 6= o(x∗), while G(x) = G(x∗) (and hence D(x) = D(x∗)).
Intuitively, adversarial perturbations cause the output of the classifier to change while the oracle would still consider the new input x∗ as being from the original class. Hence in the context of - bounded perturbations, the classifier is too sensitive to task-irrelevant changes. On the other hand, movements in the pre-image leave the classifier invariant. If those movements induce a change in class as judged by the oracle, we call these invariance-based adversarial examples. In this case, however, the classifier is too insensitive to task-relevant changes. In conclusion, these two modes are complementary to each other, whereas both constitute failure modes of the learned classifier.
When not restricting to -perturbations, perturbation-based and invariance-based adversarial examples yield the same input x∗ via
x∗ = x1 + ∆x1, D(x ∗) 6= D(x1), o(x∗) = o(x1) (3) x∗ = x2 + ∆x2, D(x ∗) = D(x2), o(x ∗) 6= o(x2), (4)
with different reference points x1 and x2, see Figure 2. Hence, the key difference is the change of reference, which allows us to approach these failure modes from different directions. To connect these failure modes with an intuitive understanding of variations in the data, we now introduce the notion of invariance to nuisance and semantic variations, see also (Achille & Soatto, 2018).
Definition 4 (Semantic/ Nuisance perturbation of an input). Let o be an oracle (Definition 2) and x ∈ Rd. Then, a perturbation ∆x of an input x ∈ Rd is called semantic, if o(x) 6= o(x+ ∆x) and nuisance if o(x) = o(x+ ∆x).
For example, such a nuisance perturbation could be a translation or occlusion in image classification. Further in Appendix A, we discuss the synthetic example called Adversarial Spheres from (Gilmer et al., 2018b), where nuisance and semantics can be explicitly formalized as rotation and norm scaling.
2.1 USING BIJECTIVE NETWORKS TO ANALYZE EXCESSIVE INVARIANCE
As invariance-based adversarial examples manifest themselves in changes which do not affect the output of the network F , we need a generic approach that gives us access to the discarded nuisance variability. While feature nuisances are intractable to access for general architectures (see comment after Definition 1), invertible classifiers only remove nuisance variability in their final projection (Jacobsen et al., 2018). For C < d, we denote the classifier as D : Rd → {1, ..., C}. Our contributions in this section are: (1) Introduce an invertible architecture with a simplified readout structure, allowing to exactly visualize manipulations in the hidden-space, (2) Propose an analytic attack based on this architecture allowing to analyze its decision-making, (3) Reveal striking invariance-based vulnerability in competitive classifiers.
Bijective classifiers with simplified readout. We build deep networks that give access to their decision space by removing the final linear mapping onto the class probes in invertible RevNet-classifiers and call these networks fully invertible RevNets. The fully invertible RevNet classifier can be written as Dθ = arg maxk=1,...,C softmax(Fθ(x)k), where Fθ represents the bijective network. We denote z = Fθ(x), zs = z1,...,C as the logits (semantic variables) and zn = zC+1,...,d as the nuisance variables (zn is not used for classification). In practice we choose the first C indices of
the final z tensor or apply a more sophiscticated DCT scheme (see appendix D) to set the subspace zs, but other choices work as well. The architecture of the network is similar to iRevNets (Jacobsen et al., 2018) with some additional Glow components like actnorm (Kingma & Dhariwal, 2018), squeezing, dimension splitting and affine block structure (Dinh et al., 2017), see Figure 3 for a graphical description. As all components are common in the bijective network literature, we refer the reader to Appendix D for exact training and architecture details. Due to its simple readout structure, the resulting invertible network allows to qualitatively and quantitatively investigate the task-specific content in nuisance and logit variables. Despite this restriction, we achieve performance on par with commonly-used baselines on MNIST and ImageNet, see Table 1 and Appendix D.
Analytic attack. To analyze the trained models, we can sample elements from the logit pre-image by computing xmet = F−1(zs, z̃n), where zs and z̃n are taken from two different inputs. We term this heuristic metameric sampling. The samples would be from the true data distribution if the subspaces would be factorized as P (zs, zn) = P (zs)P (zn). Experimentally we find that logit metamers are revealing adversarial subspaces and are visually close to natural images on ImageNet.
Thus, metameric sampling gives us an analytic tool to inspect dependencies between semantic and nuisance variables without the need for expensive and approximate optimization procedures.
Attack on adversarial spheres. First, we evaluate our analytic attack on the synthetic spheres dataset, where the task is to classify samples as belonging to one out of two spheres with different radii. We choose the sphere dimensionality to be d = 100 and the radii: R1 = 1, R2 = 10. By training a fully-connected fully invertible RevNet, we obtain 100% accuracy. After training we visualize the decision-boundaries of the original classifier D and a posthoc trained classifier on zn (nuisance classifier), see Figure 4. We densely sample points in a 2D subspace, following Gilmer et al. (2018b), to visualize two cases: 1) the decision-boundary on a 2D plane spanned by two randomly chosen data points, 2) the decision-boundary spanned by metameric sample xmet and reference point x. In the metameric sample subspace we identify excessive invariance of the classifier. Here, it is possible to move any point from the inner sphere to the outer sphere without changing the classifiers predictions. However, this is not possible for the classifier trained on zn. Most notably, the visualized failure is not due to a lack of data seen during training, but rather due to excessive invariance of the original classifier D on zs. Thus, the nuisance classifier on zn does not exhibit the same adversarial vulnerability in its subspace.
Attack on MNIST and ImageNet. After validating its potential to uncover adversarial subspaces, we apply metameric sampling to fully invertible RevNets trained on MNIST and Imagenet, see Figure 5. The result is striking, as the nuisance variables zn are dominating the visual appearance of the logit metamers, making it possible to attach any semantic content to any logit activation pattern. Note that the entire 1000-dimensional feature vector containing probabilities over all ImageNet classses remains unchanged by any of the transformations we apply. To show our findings are not a particular property of bijective networks, we attack an ImageNet trained ResNet152 with a gradientbased version of our metameric attack, also known as feature adversaries (Sabour et al., 2016). The attack minimizes the mean squared error between a given set of logits from one image to another image (see appendix B for details). The attack shows the same failures for non-bijective models. This result highlights the general relevance of our finding and poses the question of the origin of this excessive invariance, which we will analyze in the following section.

heading: 3 OVERCOMING INSUFFICIENCY OF CROSSENTROPY-BASED INFORMATION-MAXIMIZATION
text: In this section we identify why the cross-entropy objective does not necessarily encourage to explain all task-dependent variations of the data and propose a way to fix this. As shown in figure 4, the nuisance classifier on zn uses task-relevant information not captured by the logit classifier Dθ on zs (evident by its superior performance in the adversarial subspace).
We leverage the simple readout-structure of our invertible network and turn this observation into a formal explanation framework using information theory: Let (x, y) ∼ D with labels y ∈ {0, 1}C . Then the goal of a classifier can be stated as maximizing the mutual information (Cover & Thomas, 2006) between semantic features zs (logits) extracted by network Fθ and labels y, denoted by I(y; zs).
Adversarial distribution shift. As the previously discussed failures required to modify input data from distribution D, we introduce the concept of an adversarial distribution shift DAdv 6= D to formalize these modifications. Our first assumptions for DAdv is IDAdv (zn; y) ≤ ID(zn; y). Intuitively, the nuisance variables zn of our network do not become more informative about y. Thus, the distribution shift may reduce the predictiveness of features encoded in zs, but does not introduce or increase the predictive value of variations captured in zn. Second, we assume IDAdv (y; zs|zn) ≤ IDAdv (y; zs), which corresponds to positive or zero interaction information, see e.g. (Ghassami & Kiyavash, 2017). While the information in zs and zn can be redundant in this assumption, synergetic effects where conditioning on zn increase the mutual information between y and zs are excluded.
Bijective networks Fθ capture all variations by design which translates to information preservation I(y;x) = I(y;Fθ(x)), see (Kraskov et al., 2004). Consider the reformulation
I(y;x) = I(y;Fθ(x)) = I(y; zs, zn) = I(y; zs) + I(y; zn|zs) = I(y; zn) + I(y; zs|zn) (5)
by the chain rule of mutual information (Cover & Thomas, 2006), where I(y; zn|zs) denotes the conditional mutual information. Most strikingly, equation 5 offers two ways forward:
1. Direct increase of I(y; zs)
2. Indirect increase of I(y; zs|zn) via decreasing I(y; zn).
Usually in a classification task, only I(y; zs) is increased actively via training a classifier. While this approach is sufficient in most cases, expressed via high accuracies on training and test data, it may fail under DAdv . This highlights why cross-entropy training may not be sufficient to overcome excessive semantic invariance. However, by leveraging the bijection Fθ we can minimize the unused information I(y; zn) using the intuition of a nuisance classifier.
Definition 5 (Independence cross-entropy loss). Let Fθ : Rd → Rd a bijective network with parameters θ ∈ Rp1 and F̃θ(x) = softmax(Fθ(x)1,...,C). Furthermore, let Dθnc : Rd−C → [0, 1]C be the nuisance classifier with θnc ∈ Rp2 . Then, the independence cross-entropy loss is defined as:
min θ max θnc LiCE(θ, θnc) = C∑ i=1
−yi log F̃ zsθ (x)i︸ ︷︷ ︸ =:LsCE(θ) +
C∑ i=1
yi logDθnc(F zn θ (x))i︸ ︷︷ ︸
=:LnCE(θ,θnc)
.
The underlying principles of the nuisance classification loss LnCE can be understood using a variational lower bound on mutual information from Barber & Agakov (2003). In summary, the minimization is with respect to a lower bound on ID(y; zn), while the maximization aims to tighten the bound (see Lemma 10 in Appendix C). By using these results, we now state the main result under the assumed distribution shift and successful minimization (proof in Appendix C.1):
Theorem 6 (Information IDAdv(y; zs) maximal after distribution shift). Let DAdv denote the adversarial distribution and D the training distribution. Assume ID(y; zn) = 0 by minimizing LiCE and the distribution shift satisfies IDAdv (zn; y) ≤ ID(zn; y) and IDAdv (y; zs|zn) ≤ IDAdv (y; zs). Then,
IDAdv (y; zs) = ID(y;x).
Thus, incorporating the nuisance classifier allows for the discussed indirect increase of IDAdv (y; zs) under an adversarial distribution shift, visualized in Figure 6.
To aid stability and further encourage factorization of zs and zn in practice, we add a maximum likelihood term to our independence cross-entropy objective as
min θ max θnc L(θ, θnc) = LiCE(θ, θnc)− d−C∑ k=1 log (pk(F zn θ (x)k)|det(J
x θ )|)︸ ︷︷ ︸
=:LMLEn (θ)
, (6)
where det(Jxθ ) denotes the determinant of the Jacobian of Fθ(x) and pk ∼ N (βk, γk) with βk, γk learned parameter. The log-determinant can be computed exactly in our model with negligible additional cost. Note, that optimizing LMLEn on the nuisance variables together with LsCE amounts to maximum-likelihood under a factorial prior (see Lemma 11 in Appendix C).
Just as in GANs the quality of the result relies on a tight bound provided by the nuisance classifier and convergence of the MLE term. Thus, it is important to analyze the success of the objective after training. We do this by applying our metameric sampling attack, but there are also other ways like evaluating a more powerful nuisance classifier after training.

heading: 4 APPLYING INDEPENDENCE CROSS-ENTROPY
text: In this section, we show that our proposed independence cross-entropy loss is effective in reducing invariance-based vulnerability in practice by comparing it to vanilla cross-entropy training in four aspects: (1) error on train and test set, (2) effect under distribution shift, perturbing nuisances via metameric sampling, (3) evaluate accuracy of a classifier on the nuisance variables to quantify the class-specific information in them and (4) on our newly introduced shiftMNIST, an augmented version of MNIST to benchmark adversarial distribution shifts according to Theorem 6.
For all experiments we use the same network architecture and settings, the only difference being the two additional loss terms as explained in Definition 5 and equation 6. In terms of test error of the logit classifier, both losses perform approximately on par, whereas the gap between train and test error vanishes for our proposed loss function, indicating less overfitting. For classification errors see Table 2 in appendix D.
Robustness under metameric sampling attack. To analyze if our proposed loss indeed leads to independence between zn and labels y, we attack it with our metameric sampling procedure. As we are only looking on data samples and not on samples from the model (factorized gaussian on nuisances), this attack should reveal if the network learned to trick the objective. In Figure 7 we show interpolations between original images and logit metamers in CE- and iCE-trained fully invertible RevNets. In particular, we are holding the activations zs constant, while linearly interpolating nuisances zn down the column. The CE-trained network allows us to transform any image into any class without changing the logits. However, when training with our proposed iCE, the picture changes fundamentally and interpolations in the pre-image only change the style of a digit, but not its semantic content. This shows our loss has the ability to overcome excessive task-related invariance and encourages the model to explain and separate all task-related variability of the input from the nuisances of the task.
A classifier trained on the nuisance variables of the cross-entropy trained model performs even better than the logit classifier. Yet, a classifier on the nuisances of the independence cross-entropy trained model is performing poorly (Table 2 in appendix D). This indicates little class-specific information in the nuisances zn, as intended by our objective function. Note also that this inability of the nuisance classifier to decode class-specific information is not due to it being hard to read out from zn, as this would be revealed by the metameric sampling attack (see Figure 7).
shiftMNIST: Benchmarking adversarial distribution shift. To further test the efficacy of our proposed independence cross-entropy, we introduce a simple, but challenging new dataset termed shiftMNIST to test classifiers under adversarial distribution shifts DAdv . The dataset is based on vanilla MNIST, augmented by introducing additional, highly predictive features at train time that are randomized or removed at test time. Randomization or removal ensures that there are no synergy effects between digits and planted features under DAdv . This setup allows us to reduce mutual information between category and the newly introduced feature in a targeted manner. (a) Binary shiftMNIST is vanilla MNIST augmented by coding the category for each digit into a single binary pixel scheme. The location of the binary pixel reveals the category of each image unambigiously, while only minimally altering the image’s appearance.
At test time, the binary code is not present and the network can not rely on it anymore. (b) Textured shiftMNIST introduces textured backgrounds for each digit category which are patches sampled from the describable texture dataset (Cimpoi et al., 2014).
At train time the same type of texture is underlayed each digit of the same category, while texture types across categories differ. At test time, the relationship is broken and texture backgrounds are paired with digits randomly, again minimizing the mutual information between background and label in a targeted manner. See Figure 8 for examples1.
It turns out that this task is indeed very hard for standard classifiers and their tendency to become excessively invariant to semantically meaningful features, as predicted by our theoretical analysis. When trained with cross-entropy, ResNets and fi-RevNets make zero errors on the train set, while having error rates of up to 87% on the shifted test set. This is striking, given that e.g. in binary shiftMNIST, only one single pixel is removed under DAdv , leaving the whole image almost unchanged. When applying our independence cross-entropy, the picture changes again. The errors made by the network improve by up to almost 38% on binary shiftMNIST and around 28% on textured shiftMNIST. This highlights the effectiveness of our proposed loss function and its ability to minimize catastrophic failure under severe distribution shifts exploiting excessive invariance.

heading: 5 RELATED WORK
text: Adversarial examples. Adversarial examples often include -norm restrictions (Szegedy et al., 2013), while (Gilmer et al., 2018a) argue for a broader definition to fully capture the implications for security. The -adversarial examples have also been extended to -feature adversaries (Sabour et al., 2016), which are equivalent to our approximate metameric sampling attack. Some works (Song et al., 2018; Fawzi et al., 2018) consider unrestricted adversarial examples, which are closely related to invariance-based adversarial vulnerability. The difference to human perception revealed by adversarial examples fundamentally questions which statistics deep networks use to base their decisions (Jo & Bengio, 2017; Tsipras et al., 2019).
Relationship between standard and bijective networks. We leverage recent advances in reversible (Gomez et al., 2017) and bijective networks (Jacobsen et al., 2018; Ardizzone et al., 2019; Kingma & Dhariwal, 2018) for our analysis. It has been shown that ResNets and iRevNets behave similarly on various levels of their representation on challenging tasks (Jacobsen et al., 2018) and that iRevNets as well as Glow-type networks are related to ResNets by the choice of dimension splitting applied in their residual blocks (Grathwohl et al., 2019). Perhaps unsurprisingly, given so many similarities, ResNets themselves have been shown to be provably bijective under mild conditions (Behrmann et al., 2018b). Further, excessive invariance of the type we discuss here has been shown to occur in non residual-type architectures as well (Gilmer et al., 2018b; Behrmann et al., 2018a). For instance, it has been observed that up to 60% of semantically meaningful input dimensions on the adversarial spheres problem are learned to be ignored, while retaining virtually perfect performance (Gilmer et al., 2018b). In summary, there is ample evidence that RevNet-type networks are closely related to ResNets, while providing a principled framework to study widely observed issues related to excessive invariance in deep learning in general and adversarial robustness in particular.
Information theory. The information-theoretic view has gained recent interest in machine learning due to the information bottleneck (Tishby & Zaslavsky, 2015; Shwartz-Ziv & Tishby, 2017; Alemi et al., 2017) and usage in generative modelling (Chen et al., 2016; Hjelm et al., 2019). As a consequence, the estimation of mutual information (Barber & Agakov, 2003; Alemi et al., 2018; Achille & Soatto, 2018; Belghazi et al., 2018) has attracted growing attention. The concept of group-wise independence between latent variables goes back to classical independent subspace analysis (Hyvärinen & Hoyer, 2000) and received attention in learning unbiased representations, e.g. see the Fair Variational Autoencoder (Louizos et al., 2015). Furthermore, extended cross-entropy losses via entropy terms (Pereyra et al., 2017) or minimizing predictability of variables (Schmidhuber, 1991) has been introduced for other applications. Our proposed loss also shows similarity to the GAN loss (Goodfellow et al., 2014). However, in our case there is no notion of real or fake samples, but exploring similarities in the optimization are a promising avenue for future work.
1Link to code and dataset: https://github.com/jhjacobsen/fully-invertible-revnet

heading: 6 CONCLUSION
text: Failures of deep networks under distribution shift and their difficulty in out-of-distribution generalization are prime examples of the limitations in current machine learning models. The field of adversarial example research aims to close this gap from a robustness point of view. While a lot of work has studied -adversarial examples, recent trends extend the efforts towards the unrestricted case. However, adversarial examples with no restriction are hard to formalize beyond testing error. We introduce a reverse view on the problem to: (1) show that a major cause for adversarial vulnerability is excessive invariance to semantically meaningful variations, (2) demonstrate that this issue persists across tasks and architectures; and (3) make the control of invariance tractable via fully-invertible networks.
In summary, we demonstrated how a bijective network architecture enables us to identify large adversarial subspaces on multiple datasets like the adversarial spheres, MNIST and ImageNet. Afterwards, we formalized the distribution shifts causing such undesirable behavior via information theory. Using this framework, we find one of the major reasons is the insufficiency of the vanilla cross-entropy loss to learn semantic representations that capture all task-dependent variations in the input. We extend the loss function by components that explicitly encourage a split between semantically meaningful and nuisance features. Finally, we empirically show that this split can remove unwanted invariances by performing a set of targeted invariance-based distribution shift experiments.

heading: 7 ACKNOWLEDGEMENTS
text: We thank Ryota Tomioka for spotting a mistake in the proof for Theorem 6. We thank thank the anonymous reviewers, Ricky Chen, Will Grathwohl and Jesse Bettencourt for helpful comments on the manuscript. We gratefully acknowledge the financial support from the German Science Foundation for the CRC 1233 on ”Robust Vision” and RTG 2224 ”π3: Parameter Identification - Analysis, Algorithms, Applications”

heading: A SEMANTIC AND NUISANCE VARIATION ON ADVERSARIAL SPHERES
text: Example 7 (Semantic and nuisance on Adversarial Spheres (Gilmer et al., 2018b)). Consider classifying inputs x from two classes given by radii R1 or R2. Further, let (r, φ) denote the spherical coordinates of x. Then, any perturbation ∆x, x∗ = x + ∆x with r∗ 6= r is semantic. On the other hand, if r∗ = r the perturbation is a nuisance with respect to the task of discriminating two spheres. In this example, the max-margin classifierD(x) = sign ( ‖x‖ − R1+R22 ) is invariant to any nuisance perturbation, while being only sensitive to semantic perturbations. In summary, the transform to spherical coordinates allows to linearize semantic and nuisance perturbations. Using this notion, invariance-based adversarial examples can be attributed to perturbations of x∗ = x + ∆x with following two properties
1. Perturbed sample x∗ stays in the pre-image {x∗ ∈ Rd | D(x∗) = D(x)} of the classifier
2. Perturbation ∆x is semantic, as o(x) 6= o(x+ ∆x).
Thus, the failure of the classifier D can be thought of a mis-alignment between its invariance (expressed through the pre-image) and the semantics of the data and task (expressed by the oracle).
Example 8 (Mis-aligned classifier on Adversarial Spheres). Consider the classifier
D(x) = sign ( ‖x1,...,d−1‖ −
R1 +R2 2
) , (7)
which computes the norm of x from its first d − 1 cartesian-coordinates. Then, D is invariant to a semantic perturbation with ∆r = R2 −R1 if only changes in the last coordinate xd are made.
We empirically evaluate the classifier in equation 7 on the spheres problem (10M/2M samples setting (Gilmer et al., 2018b)) and validate that it can reach perfect classification accuracy. However, by construction, perturbing the invariant dimension x∗d = xd + ∆xd allows us to move all samples from the inner sphere to the outer sphere. Thus, the accuracy of the classifier drops to chance level when evaluating its performance under such a distributional shift. To conclude, this underlines how classifiers with optimal performance on finite samples can exhibit non-intuitive failure modes due to excessive invariance with respect to semantic variations.

heading: B APPROXIMATE GRADIENT-BASED METAMERIC SAMPLES
text: We use a standard Imagenet pre-trained Resnet-154 as provided by the torchvision package (Paszke et al., 2017) and choose a logit percept y = G(x) that can be based on any seed image. Then we optimize various images x̃ to be metameric to x by simply minimizing a mean squared error loss of the form:
LMSE(G(x), G(x̃)) = 1
K K∑ k=1 (G(x)k −G(x̃)k)2 (8)
in the 1000-dimensional semantic logit space via stochastic gradient descent. We optimize with Adam in Pytorch default settings and a learning rate of 0.01 for 3000 iterations. The optimization thus takes the form of an adversarial attack targeting all logit entries and with no norm restriction on the input distance. Note that our metameric sampling attack in bijective networks is the analytic reverse equivalent of this attack. It leads to the exact solution at the cost of one inverse pass instead of an approximate solution here at the cost of thousands of gradient steps.

heading: B.1 ADDITIONAL BATCH OF METAMERIC SAMPLES
text: C INFORMATION THEORY
Computing mutual information is often intractable as it requires the joint probability p(x, y), see (Cover & Thomas, 2006) for an extensive treatment of information theory. However, following variational lower bound can be used for approximation, see (Barber & Agakov, 2003). Lemma 9 (Variational lower bound on mutual information). Let X,Y be random variables with conditional density p(y|x). Further, let qθ(y|x) be a variational density depending on parameter θ. Then, the lower bound
I(Y ;X) = h(Y )− h(Y |X) = h(Y ) + EXEY |X log qθ(y|x) + EX(p(y|x) ‖ qθ(y|x)) ≥ h(Y ) + EXEY |X log qθ(y|x)
holds with equality if p(y|x) = qθ(y|x).
While above lower bound removes the need for the computation of p(y|x), estimating the expectation EY |X still requires sampling from it. Using this bound, we can now state the effect of the nuisance classifiation loss. Lemma 10 (Effect of nuisance classifier). Define semantics as zs = Fθ(x)1,...,C and nuisances as zn = Fθ(x)C+1,...,d, where (x, y) ∼ D. Then, the nuisance classification loss yields
(i) Minimization of lower bound on ID(y; zn): θ∗ = arg minθ LnCE(θ, θ∗nc) minimizes Iθ∗nc(y; zn), where Iθ∗nc(y; zn) ≤ ID(y; zn) and θ ∗ nc = arg maxθ2 LnCE(θ, θnc).
(ii) Maximization to tighten bound on ID(y; zn): Under a perfect model of the conditional density, Dθ∗nc(zn) = p(y|zn), it holds Iθ∗nc(y; zn) = ID(y; zn).
Proof. To proof above result, we need to draw the connection to the variational lower bound on mutual information from Lemma 9. Let the nuisance classifier Dθnc(zn) model the variational posterior qθnc(y|zn). Then we have the lower bound
I(y; zn) ≥ h(y) + EznEy|zn logDθnc(zn) =: Iθnc(y; zn). (9)
From Lemma 9 follows, that if Dθnc(zn) = p(y|zn), it holds I(y; zn) = Iθnc(y; zn). Hence, the nuisance classifier needs to model the conditional density perfectly. Estimating this bound via Monte Carlo simulation requires sampling from the conditional density p(y|zn). Following (Alemi et al., 2017), we have the Markov property y ↔ x ↔ zn as labels y interact with inputs x and representation zn interacts with inputs x. Hence,
p(y|zn)p(zn) = p(y, zn)
= ∫ X p(x, y, zn)dx
= ∫ X p(zn|x, y)p(y|x)p(x)dx
= ∫ X p(zn|x)p(y|x)p(x)dx = Ex[p(zn|x)p(y|x)].
Including above and assuming Fθ(x) = zn to be a deterministic function, we have
EznEy|zn logDθnc(zn) = ExEy|xEzn|x logDθnc(zn) = ExEy|x logDθnc(zn).
Lemma 11 (Effect of MLE-term). Define semantics as zs = Fθ(x)1,...,C and nuisances as zn = Fθ(x)C+1,...,d, where (x, y) ∼ D. Then, the MLE-term in equation 6 together with cross-entropy on the semantics
θ∗ = arg min θ LsCE(θ) + LMLEn(θ)
minimizes the mutual information I(zs; zn).
Proof. Let z̃s = softmax(zs). Then minimizing the loss terms LsCE and LMLEn is a maximum likelihood estimation under the factorial prior
p(z̃s, zn) = p(z̃s)p(zn) (10)
= Cat((z̃s)1, . . . , (z̃s)C) d−C∏ k=1 pk(zn)k, (11)
where Cat is a categorical distribution. As softmax is shift-invariant, softmax(x + c) = softmax(x), above factorial prior for z̃s and zn yields independence between logits zs and zn up to a constant c. Finally note, the log term and summation in LMLEn and LCE is re-formulation for computational ease but does not change its minimizer as the logarithm is monotone.

heading: C.1 PROOF OF THEOREM 6
text: From the assumptions follows IDAdv (y; zn) = 0. Furthermore, we have the assumption
IDAdv (y; zs|zn) ≤ IDAdv (zs; y),
excluding synergetic effects in the interaction information (Ghassami & Kiyavash, 2017). By information preservation under homeomorphisms (Kraskov et al., 2004) and the chain rule of mutual information (Cover & Thomas, 2006), we have
IDAdv (y;x) = IDAdv (y; zs, zn)
= IDAdv (y; zn) + IDAdv (y; zs|zn) ≤ IDAdv (y; zs).
As zs = F (x)1,...,C is obtained by the deterministic transform F , by the data processing inequality (Cover & Thomas, 2006) we have the inequality IDAdv (y;x) ≥ IDAdv (y; zs). Thus, the claimed equality must hold.

heading: C.2 MUTUAL INFORMATION BOUNDED
text: Remark 12. Since our goal is to maximize the mutual information I(y; zs) while minimizing I(y; zn), we need to ensure that this objective is well defined as mutual information can be unbounded from above for continuous random variables. However, due to the data processing inequality (Cover & Thomas, 2006) we have I(y; zn) = I(y;Fθ(x)) ≤ I(y;x). Hence, we have a fixed upper bound given by our data (x, y). Compared to (Belghazi et al., 2018) there is thus no need for gradient clipping or a switch to the bounded Jensen-Shannon divergence as in (Hjelm et al., 2019) is not necessary.

heading: D TRAINING AND ARCHITECTURAL DETAILS
text: All experiments were based on a fully invertible RevNet model with different hyperparameters for each dataset. For the spheres experiment we used Pytorch (Paszke et al., 2017) and for MNIST, as well as Imagenet Tensorflow (Abadi et al., 2016).

heading: D.1 SPHERES EXPERIMENTS
text: The network is a fully connected fully invertible RevNet. It has 4 RevNet-type ReLU bottleneck blocks with additive couplings and uses no batchnorm. We train it via cross-entropy and use the Adam optimizer (Kingma & Ba, 2014) with a learning rate of 0.0001 and otherwise default Pytorch settings. The nuisance classifier is a 3 layer ReLU network with 1000 hidden units per layer.
We choose the spheres to be 100-dimensional, with R1 = 1 and R2 = 10, train on 500k samples for 10 epochs and then validate on another 100k holdout set. We achieve 100% train and validation accuracy for logit and nuisance classifier.

heading: D.2 MNIST EXPERIMENTS
text: We use a convolutional fully invertible RevNet with additional actnorm and invertible 1x1 convolutions between each layer as introduced in Kingma & Dhariwal (2018). The network has 3 stages, after which half of the variables are factored out and an invertible downsampling, or squeezing (Dinh et al., 2017; Jacobsen et al., 2018) is applied. The network has 16 RevNet blocks with batch norm per stage and 128 filters per layer. We also dequantize the inputs as is typically done in flow-based generative models.
The network is trained via Adamax (Kingma & Ba, 2014) with a base learning rate of 0.001 for 100 epochs and we multiply the it with a factor of 0.2 every 30 epochs and use a batch size of 64 and l2 weight decay of 1e-4. For training we compare vanilla cross-entropy training with our proposed independence cross-entropy loss. To have a more balanced loss signal, we normalize LnCE by the number of input dimensions it receives for the maximization step. The nuisance classifier is a fullyconnected 3 layer ReLU network with 512 units. As data-augmentation we use random shifts of 3 pixels. For classification errors of the different architectures we compare, see Table 2.
D.3 IMAGENET EXPERIMENTS
We use a convolutional fully invertible RevNet with 4 stages, 4 RevNet blocks per stage and invertible downsampling after each stage, as well as two invertible downsamplings on the input of the
network. The first three stages consist of additive and the last of affine coupling layers. After the final layer we apply an orthogonal 2D DCT type-II to all feature maps and read out the classes in the low-pass components of the transformation. This effectively gives us an invertible global average pooling and makes our network even more similar to ResNets, that always apply global average pooling on their final feature maps. We train the network with momentum SGD for 128 epochs, a batch size of 480 (distributed to 6 GPUs), a base learning rate of 0.1, which is reduced by a factor of 0.1 every 32 epochs. We apply momentum of 0.9 and l2 weight decay of 1e-4.

Review summaries:
This paper studies a new perspective on why adversarial examples exist in machine learning -- instead of seeing adversarial examples as the result of a classifier being sensitive to changes in irrelevant information (aka nuisance), the authors see them as the result of a classifier being invariant to changes in relevant (aka semantic) information. They show how to efficiently find such adversarial examples in bijective networks. Moreover, they propose to modify the training objective so that the bijective networks could be more robust to such attacks.

This paper explores adversarial examples by investigating an invertible neural network. They begin by first correctly pointing out limitations with the commonly adopted "l_p adversarial example" definition in literature. The main idea involves looking at the preimage of different embeddings in the final layer of an invertible neural network. By training a classifier on top of the final embedding of the invertible network the authors are able to partition the final embedding into a set of "semantic variables", which are the components used for classification of the classifier, and a set of "nuisance variables" which are the complement of the logit variables. This partition allows the authors to define entire subspaces of adversarial images by holding the logit variables fixed and varying the nuisance variables, and applying the inverse to these modified embeddings. The authors are able to find many incorrectly classified images with this inversion technique. The authors then define a new loss which minimizes the mutual information between the nuisance variables and the predicted label.