We flip the usual approach to study invariance and robustness of neural networks by considering the non-uniqueness and instability of the inverse mapping. We provide theoretical and numerical results on the inverse of ReLU-layers. First, we derive a necessary and sufficient condition on the existence of invariance that provides a geometric interpretation. Next, we move to robustness via analyzing local effects on the inverse. To conclude, we show how this reverse point of view not only provides insights into key effects, but also enables to view adversarial examples from different perspectives. Invariance and stability/robustness are two of the most important properties characterizing the behavior of a neural network. Due to growing requirements like robustness to adversarial examples BID16 and the increasing use of deep learning in safety-critical applications, there has been a surge in interest in these properties. Invariance and stability are considered to be the key mechanisms in dealing with uninformative properties of the input BID0 BID6 and are studied from the information theoretical perspective in form of the loss of information about the input BID17 BID11 .Invariance and stability are also tightly linked to robustness against adversarial attacks (Cisse et al., 2017; BID18 BID14 , generalization BID15 Gouk et al., 2018) and even the training of Generative Adversarial Networks BID7 . In general , stability is studied via two basic properties: 1) locally via a norm of the Jacobian BID15 BID14 , 2) globally via the Lipschitz constant (Cisse et al., 2017; BID7 BID18 ). From a high-level perspective, both of these approaches study an upper bound on stability as the Lipschitz constant and a Jacobian norm quantifies the highest possible change under a perturbation with a given magnitude. We, unlike the approaches above, aim to broaden our understanding by analyzing the lowest possible change under a perturbation.More formally, we study which perturbations ∆x do not (or only little) affect the outcome of a network F . Our analysis considers a given input data point x and investigates the ∆x's, such that DISPLAYFORM0 where a small ε > 0 is given. While these properties can be crucial for many discriminative tasks BID6 , the model could be flawed if perturbations that alter the semantics have only a minor impact on the features. This is a reverse perspective on adversarial examples BID16 , which commonly considers small input perturbations that lead to large changes and thus to arbitrary decisions of the network.This flipped view and the study of smallest changes calls for a different approach: we study the instabilities of the inverse instead of the stabilities of the forward mapping. In particular, if F is invariant to perturbations ∆x, then x and x + ∆x lie in the preimage of the output z = F (x), i.e. F is not uniquely invertible. Robustness towards large perturbations induces an instable inverse mapping as small changes in the output can be due to large changes in the input.Based on the piecewise linear nature of ReLU networks BID8 , we characterize the preimage of ReLU-activations as a single point, finite (bounded) or infinite (unbounded) . Further, we study the stability of the linearization of rectifier networks via its singular values. To illustrate these locally changing properties and to demonstrate their tight connection, we visualize the behavior on a synthetic problem in FIG0 . As ReLU-layers are piecewise linear, the local behavior is constant on polytopes. Further, the regions with infinite/finite preimages correspond to regions with condition number of one or zero, while singleton preimages link to condition numbers larger than one. Thus, both properties are tightly connected and investigating one property alone yields an incomplete picture.Our contributions are as follows:• We derive conditions when the preimage of an output of a ReLU-layer has finite or infinite volume or is a single point. Based on these conditions, we derive an algorithm to check these conditions and exemplify its usability by applying it to investigate the preimages of a trained network. (See Section 2.) • We study the stability of the inverse via analyzing the linearization at a point in input space, which is accurate within a polytope. We provide upper bounds on the smallest singular value of a linearization and prove how the removal of uncorrelated features could effect the stability of the inverse mapping. Based on these ideas, we experimentally demonstrate how singular values evolve over the different layers in rectifier networks. (See Section 3.) • We introduce a reverse view on adversarial examples and connect it to invariance and robustness by leveraging our analysis of preimages. (see Section 5) We presented the inverse as an approach to tackle the invariance and robustness properties of ReLU networks. Particularly, we studied two main effects: 1) conditions under which the preimage of a ReLU layer is a point, finite or infinite and 2) how ReLU can effect the inverse stability of the linearization. By deriving approaches to numerically examine these effects, we highlighted the broad range of possible effects. Moreover, controlling such properties may be desirable as our experiment on adversarial examples showed.Besides the open questions on how to control the structure of preimages and inverse stability via architecture design or regularization, we envision several theoretical directions based on our work. Especially, incorporate nonlinear effects like moving between linear regions of rectifier networks could lift the analysis closer to practice. Furthermore, studying similarities of omnidirectionality as a geometrical property and singular values could further strengthen the link between these two crucial properties. Proof (Corollary 2, Equivalences of omnidirectionality) We show the equivalences by proving i) DISPLAYFORM0 Let A ∈ R m×n be omnidirectional, i.e. for every x = 0, it holds that Ax 0. This is equivalent to DISPLAYFORM1 which is ii). The implications from ii) to iii) and from iii) to iv) are obvious. From iv), we have that DISPLAYFORM2 which is equivalent to i), the omnidirectionality of A. Altogether, this shows the equivalence of all four points.Definition 10 (Convex hull) For A ∈ R m×n , the convex hull is defined as DISPLAYFORM3 where a i ∈ R n are the rows of A.Theorem 11 (Stiemke's theorem, see Dantzig (1963) ) Let A ∈ R m×n be a matrix, then the following two expressions are equivalent.• y : Ay 0 DISPLAYFORM4 Here z 0 means that 0 = z 0 . Proof (Theorem 12, Singleton solutions of inequality systems) "⇐" Let (A| I , b| I ) be omnirectional for x 0 . Then it holds that A| I x + b| I = A| I (x − x 0 ) 0. Due to the omnidirectionality of A| I , x 0 is the unique solution of the inequality system A| I x + b| I 0. The existence of a solution for the whole system Ax + b 0 is guaranteed by assumption and therefore x 0 is the unique solution of Ax + b 0. "⇒" Here we will prove " I : (A| I , b| I ) omnidirectional for some p ⇒ solution non-unique".We will start by doing the following logical transformations: This means that A| I is not omnidirectional, because otherwise A| I x 0 + b| I = 0 due to the definition of I, which would lead to the contradiction that (A| I , b| I ) is omnidirectional for x 0 . But this means ∃x = 0 : A| I x 0 as a result of Corollary 2. Since A| I c x 0 + b| I c ≺ 0, we also have ∀x ∃ > 0 : A| I c (x 0 + x) + b| I c ≺ 0. This holds in particular for x , so we define accordingly x * := εx = 0. Therefore, we have A| I c (x 0 + x * ) + b| I c ≺ 0 as well as DISPLAYFORM5 DISPLAYFORM6 Altogether it holds that A(x 0 + x * ) + b 0 with x * = 0, which means that x 0 is a non-unique solution for the inequality system Ax + b 0.Proof (Theorem 4, Preimages of ReLU-layers) We consider the ReLU-layer DISPLAYFORM7 given its output y ∈ R m with A ∈ R m×n , b ∈ R m and x ∈ R n . Clearly, this equation can also be written as the mixed linear system DISPLAYFORM8 This allows us to consider the two cases N (A| y 0 ) = {0} and N (A| y 0 ) = {0}.In the first case , we have a linear system which allows us to calculate x uniquely, i.e. we can do retrieval. This leads us to the second case, the interesting one. In this case we can only recover x uniquely if and only if the system of inequalities "pins down" P N (A|y 0) x, where P V is the orthogonal projection into the closed space V . Formally this requires DISPLAYFORM9 to have a unique solution for x ∈ R n and P N (A|y 0) ⊥ x fixed (given via the equality system). By defining b := b| y 0 + A| y 0 (P N (A|y 0 ) ⊥ x) we have DISPLAYFORM10
We analyze the invertibility of deep neural networks by studying preimages of ReLU-layers and the stability of the inverse. This paper studies the volume of preimage of a ReLU network’s activation at a certain layer, and it builds on the piecewise linearity of a ReLU network’s forward function.  This paper presents an analysis of the inverse invariance of ReLU networks and provides upper bounds on singular values of a train network.