Title: FUNCTIONAL VS. PARAMETRIC EQUIVALENCE OF RELU NETWORKS

Abstract: We address the following question: How redundant is the parameterisation of ReLU networks? Specifically, we consider transformations of the weight space which leave the function implemented by the network intact. Two such transformations are known for feedforward architectures: permutation of neurons within a layer, and positive scaling of all incoming weights of a neuron coupled with inverse scaling of its outgoing weights. In this work, we show for architectures with non-increasing widths that permutation and scaling are in fact the only function-preserving weight transformations. For any eligible architecture we give an explicit construction of a neural network such that any other network that implements the same function can be obtained from the original one by the application of permutations and rescaling. The proof relies on a geometric understanding of boundaries between linear regions of ReLU networks, and we hope the developed mathematical tools are of independent interest.
Recent investigations into these and other questions have emphasised the role of overparameterisation, or highly redundant function representation. It is now known that overparameterised networks enjoy both easier training (Allen-

1. INTRODUCTION:

Ever since its early successes, deep learning has been a puzzle for machine learning theorists. Multiple aspects of deep learning seem at first sight to contradict common sense: single-hidden-layer networks suffice to approximate any continuous function (Cybenko, 1989; Hornik et al., 1989 ), yet in practice deeper is better; the loss surface is highly non-convex, yet it can be minimised by first-order methods; the capacity of the model class is immense, yet deep networks tend not to overfit (Zhang et al., 2017) .

Our main theorem applies to architectures with non-increasing widths, and shows that there are no other function-preserving parameter transformations besides permutation and scaling. Stated formally:

Theorem 1. Consider a bounded open nonempty domain Z ⊆ R d0 and any architecture (d 0 , . . . , d L ) with

d 0 ≥ d 1 ≥ • • • ≥ d L-1 ≥ 2, d L = 1.

For this architecture, there exists a ReLU network h θ : Z → R, or equivalently a setting of the weights θ (W 1 , b 1 , . . . , W L , b L ), such that for any 'general' ReLU network h η : Z → R (with the same architecture) satisfying h θ (z) = h η (z) for all z ∈ Z, there exist permutation matrices P 1 , . . . P L-1 , and positive diagonal matrices M 1 , . . . , M L-1 , such that

EQUATION

W L = W L P -1 L-1 M -1 L-1 , b L = b L ,

where η (W 1 , b 1 , . . . , W L , b L ) are the parameters of h η .

In the above, 'general' networks is a class of networks meant to exclude degenerate cases. We give a more precise definition in Section 3; for now it suffices to note that almost all networks are general.

The proof of the result relies on a geometric understanding of prediction surfaces of ReLU networks. These surfaces are piece-wise linear functions, with non-differentiabilities or 'folds' between linear regions. It turns out that folds carry a lot of information about the parameters of a network, so much in fact, that some networks are uniquely identified (up to permutation and scaling) by the function they implement. This is the main insight of the theorem.

In the following sections, we introduce in more detail the concept of a fold-set, and describe its geometric structure for a subclass of ReLU networks. The paper culminates in a proof sketch of the main result. The full proof, including proofs of intermediate results, is included in the Appendix.

2. RELATED WORK:

The functional equivalence of neural networks is a well-researched topic in classical connectionist literature. The problem was first posed by Hecht-Nielsen (1990) , and soon resolved for feed-forward networks with the tanh activation function by Chen et al. (1993) , who showed that any smooth transformation of the weight space that preserves the function of all neural networks is necessarily a composition of permutations and sign flips. For the same class of networks, Fefferman & Markel (1994) showed a somewhat stronger result: knowledge of the input-output mapping of a neural network determines both its architecture and its weights, up to permutations and sign flips. Similar results have been proven for single-layer networks with a saturating activation function such as sigmoid or RBF (Kůrková & Kainen, 1994) , as well as single-layer recurrent networks with a smooth activation function (Albertini & Sontag, 1993a; b) .

To the best of our knowledge, no such theoretical results exist for networks with the ReLU activation, which is non-saturating, asymmetric and non-smooth. Broadly related is the recent work by Petersen et al. (2018) and Berner et al. (2019) who study whether two neural networks (ReLU or otherwise) that are close in the functional space have parameterisations that are close in the weight space. This is called inverse stability. In contrast, we are interested in ReLU networks that are functionally identical, and ask about all their possible parameterisations.

In terms of proof technique, our approach is based on the geometry of piece-wise linear functions, specifically the boundaries between linear regions. The intuition for this kind of analysis has previously been presented by Raghu et al. (2017) and Serra et al. (2018) , and somewhat similar proof techniques to ours have been used by Hanin & Rolnick (2019) in the context of counting the number of linear decision regions.

Finally, the sets of equivalent parametrisations can be viewed as symmetries in the weight space, with implications for optimisation. Multiple authors, including e.g. Neyshabur et al. (2015) ; Badrinarayanan et al. (2016) ; Stock et al. (2019) , have observed that the naive loss gradient is sensitive to reparametrisation by scaling, and proposed alternative, scaling-invariant optimisation procedures.

General ReLU network. In this work, we restrict our attention to so-called general ReLU networks. Intuitively, a general network is one that satisfies a number of non-degeneracy properties, such as all weight matrices having non-zero entries and full rank, no two network units exactly cancelling each other out, etc. It can be shown1 that almost all ReLU networks are general. In other words, a sufficient condition for a ReLU network to be general with probability one is that its weights are sampled from a distribution with a density.

More formally, a general ReLU network is one that satisfies the following three conditions.

1. For any unit (l, i), the local optima of h 1:l i do not have value exactly zero. 2. For all k ≤ l and all diagonal matrices (I k , . . . , I l ) with entries in {0, 1},

rank(I l W l I l-1 • • • I k W k ) = min {d k-1 , rank(I k ), . . . , rank(I l-1 ), rank(I l )}. (8)

3. For any two units (l, i), (k, j), any linear region R 1 ⊆ Z of h 1:l i , and any linear region R 2 ⊆ Z of h 1:k j , the linear functions implemented by h 1:l i on R 1 and h 1:k j on R 2 are not multiples of each other.

General networks are convenient to study, as they exclude many degenerate special cases.

The second important class of ReLU networks are so-called transparent networks. Their significance as well as their name will become clear in the next section. For now, we state the definition.

Transparent ReLU network. A ReLU network h : Z → R is called transparent if for all z ∈ Z and l ∈ [L -1], there exists i ∈ [d l ] such that h 1:l i (z) ≥ 0.

In words, we require that for any input, at least one unit on each layer is active.

4. FOLD-SETS:

In this section we introduce the concept of fold-sets, which is key to our understanding of ReLU networks and their prediction surfaces. Since ReLU networks are piece-wise linear functions, a great deal about them is revealed by the boundaries between individual linear regions. A network's fold-set is simply the union of all these boundaries. More formally, if Z is an open set, and f : Z → R is any continuous, piece-wise linear function, we define the fold-set of f , denoted by F(f ), as the set of all points at which f is non-differentiable.

It turns out there is a class of networks whose fold-sets are especially easy to understand; these are the ones we have termed transparent. For transparent networks, we have the following characterisation of the fold-set (which also motivates the name 'transparent').

Figure 1 : A piece-wise linear surface of order one, two and three. 3Lemma 1. If h : Z → R is a general and transparent ReLU network, then

EQUATION

To appreciate the significance of the lemma, suppose we are given some transparent ReLU network function h and we want to infer its parameters. This lemma shows that the knowledge of the endto-end mapping h h 1:L in fact gives us information about the network's hidden units h 1:l i (hence 'transparent'). Moreover, this information is very explicit: we observe the units' zero-level sets, which in the case of a linear unit on a full-dimensional space already determines the unit's parameters up to scaling2 . Of course, dealing with piece-wise linearity and disambiguating the union into its constituent zero-level sets remains a challenge for upcoming sections.

5. PIECE-WISE LINEAR SURFACES:

In this section, we provide a geometric description of fold-sets of transparent networks. Intuitively, the fold-sets look like the sets shown in Figure 1 . The first-layer units of a network are linear, so the component i z | h 1:1 i (z) = 0 of the fold-set ( 9) is a union of hyperplanes, illustrated by the blue lines in Figure 1 . These hyperplanes partition the input space into a number of regions that each correspond to a different activation pattern. For a fixed activation pattern, or equivalently on each region, the second-layer units are linear, so their zero-level sets i z | h 1:2 i (z) = 0 are composed of piece-wise hyperplanes on the partition induced by the first-layer units. This is shown by the orange lines in Figure 1 . More generally, the l th -layer zero-level sets i z | h 1:l i (z) = 0 consist of piece-wise hyperplanes on the partition induced by all lower-layer units. This yields a fold-set that looks like the set in the right pane of Figure 1 , but potentially much more complicated.

We now define these concepts more precisely.

Piece-wise hyperplane. Let P be a partition of Z. We say H ⊆ Z is a piece-wise hyperplane with respect to partition P, if H is nonempty and there exist (w, b) = (0, 0) and P ∈ P such that

H = {z ∈ P | w z + b = 0}.

Piece-wise linear surface. A set S ⊆ Z is called a piece-wise linear surface on Z of order κ if it has a representation of the form S = l∈[κ],i∈[n l ] H l i , where each H l i is a piece-wise hyperplane with respect to the partition induced by k∈[l-1],j∈[n k ] H k j , and no number smaller than κ admits such a representation. Using these definitions, the following lemma formalises the intuition behind Figure 1 .

Lemma 2. If h is a general and transparent ReLU network, then its fold-set is a piece-wise linear surface of order at most L -1.

Figure 2 : A piece-wise linear surface with few intersections between piece-wise hyperplanes. From the fold-set alone (right) it is not possible to determine if a hyperplane emerged from the first layer (left, blue) or from the second one (left, orange).

Figure 3 : Greedy layer assignment to the piece-wise linear surface in Figure 1 .

The final ingredient we will need to be able to reason about the parameterisation of ReLU networks is a more precise characterisation of the fold-set, in particular, the dependence structure between individual piece-wise hyperplanes. For example, consider the piece-wise linear surface in Figure 1 and compare it to the one in Figure 2 . Suppose as before that the blue hyperplanes come from first-layer units, the orange hyperplanes come from second-layer units, and the black hyperplanes come from third-layer units. The difference between Figure 1 and Figure 2 is that if we observe only the fold-set, i.e. only the union of the zero-level sets over all layers (as shown in the right pane of Figure 2 ), then in the case of Figure 2 , it is impossible to know which folds come from which layers. For instance, the blue folds and the orange folds could be assigned to the first and second layer almost arbitrarily; there is not enough information (i.e. intersection) in the fold-set to tell which is which. In contrast, the piece-wise linear surface in the right pane of Figure 1 could in principle be disambiguated into first-, second-and third-layer folds by the following procedure: 1. Take the largest possible union of hyperplanes that is a subset of the fold-set, and assign the hyperplanes to layer one.

2. Take all piece-wise hyperplanes with respect to the partition induced by the first-layer folds, and assign them to layer two.

3. Take all piece-wise hyperplanes with respect to the partition induced by the first-and second-layer folds, and assign them to layer three.

This procedure is not guaranteed to assign all folds to their original layers because it ignores how piece-wise hyperplanes are connected; for example for the piece-wise linear surface in Figure 1 , the procedure yields the layer assignment shown in Figure 3 . However, it is sufficient for our purposes, and it is easier to work with mathematically.

Formally, for a piece-wise linear surface S, we denote k S := {S ⊆ S | S is a piece-wise linear surface of order at most k}.

One can show4 that k S is itself a piece-wise linear surface of order at most k, so one can think of k S as the 'largest possible' subset of S that is a piece-wise linear surface of order at most k. For the piece-wise linear surface in Figure 3 , the set 1 S consists of the blue hyperplanes, 2 S consists of the blue and the orange (piece-wise) hyperplanes, and 3 S = S.

This definition allows us to uniquely decompose S into its piece-wise hyperplanes. Let S = l∈[κ],i∈[n l ] H l i be any representation of S in terms of its piece-wise hyperplanes. We say the rep-

resentation is canonical if each H l i is distinct and l∈[k],i∈[n l ] H l i = k S for all k ∈ [κ].

One can show5 that such a representation exists and is unique up to subscript indexing. Importantly, it assigns a unique 'layer' to each piece-wise hyperplane, its superscript. The dependency graph (see also Figure 4 ) is a way to formally describe the dependencies between piece-wise hyperplanes.

H 1 1 H 1 2 H 2 1 H 2 2 H 2 3 H 2 4 H 3 1 H 3 2

Dependency graph. Let S = l∈[κ],i∈[n l ] H l i be the canonical representation of S.

The dependency graph of S is the directed graph that has the piece-wise hyperplanes H l i l,i as vertices, and has an edge

H l i → H k j iff l < k and relint H l i ∩ cl H k j = ∅.

That is, there is and edge

H l i → H k j if H k j 'depends on' or 'bends at' H l i .

6. MAIN RESULT:

With all the necessary concepts in place, we now put the pieces together and explain the proof idea behind the main result. We restate the theorem here for the reader's convenience. 

EQUATION

W L = W L P -1 L-1 M -1 L-1 , b L = b L , where (W 1 , b 1 , . . . , W L , b L ) are the parameters of h θ , and (W 1 , b 1 , . . . , W L , b L ) are the pa- rameters of h η .

In other words, for architectures with non-increasing widths, there exists a ReLU network h such that knowledge of the input-output mapping h determines the network's parameters uniquely up to permutation and scaling.

The idea behind the proof is as follows. Suppose we are given the function h. Then we also know its fold-set F(h), and if h is general and transparent, the fold-set is a piece-wise linear surface (by Lemma 2) of the form F(h) = l,i z | h 1:l i (z) = 0 . As we have mentioned earlier, this union of zero-level sets contains a lot of information about the network's parameters, provided we can disambiguate the union to obtain the zero-level sets of individual units. This disambiguation of the union is crucial, but is impossible in general. To see why, consider the first-layer units: given F(h), we want to identify

i z | h 1:1 i (z) = 0 . We know that i z | h 1:1 i (z) = 0 is a union of d 1 hyperplanes that is a subset of 1 F(h), so if 1 F(h)

is a union of d 1 hyperplanes, we are done. In general however, F(h) may contain more than d 1 hyperplanes, such as for example in Figure 2 . In such a setting it is impossible to tell which hyperplanes come from the first layer.

z | h l:l-1+k θ [j](z) = 0 = k∈[L-l],j∈[d k ] z | h l:l-1+k η [j](z) = 0 (13)

This is a piece-wise linear surface, whose dependency graph by Lemma 4 contains d l directed paths of length (L-1-l) with distinct starting vertices. Denote these vertices H 1 , . . . , H d l . By Lemma 3,

H i ⊆ z | h l:l-1+λ θ [ι](z) = 0 for some (λ, ι) with λ ≤ (L -l) -(L -1 -l) = 1. We thus obtain i∈[d l ] H i ⊆ i∈[d l ] z | h l θ [ι](z) = 0

, where on the left-hand side we have a union of d l hyperplanes, and on the right-hand side we have a union of at most d l hyperplanes. It follows that the two sides are equal, and by applying the same argument to h η , we get

EQUATION

)

Therefore there must exist a permutation π :

[d l ] → [d l ] such that z | h l θ [i](z) = 0 = z | h l η [π(i)](z) = 0 (15)

for all i. One can show6 that this implies the existence of scalars m 1 , . . . m d l , such that

EQUATION

We know that

m i = 0 because the folds z | h l θ [i](z) = 0 , z | h l η [i](z) = 0 , are nonempty; oth- erwise i∈[d l ] H i could

not be a union of d l hyperplanes. We have thus shown that there exists a permutation matrix P l ∈ R d l ×d l and a nonzero-entry diagonal matrix M l ∈ R d l ×d l such that W l = M l P l W l and b l = M l P l b l . One can also show that the scalars m i are positive. 7For the inductive step, let l ∈ {2, . . . , L -1}, and assume that there exist permutation matrices P 1 , . . . , P l-1 , and positive-entry diagonal matrices M 1 , . . . , M l-1 , such that (65) holds up to layer l -1. Then h 1:l-1 and h l:L η | int Z l-1 θ as we presented above for the case l = 1. We obtain that there exists a permutation matrix P l ∈ R d l ×d l and a positive-entry diagonal matrix

EQUATION

Finally, consider the last layer. We know that h

1:L-1 θ ≡ M L-1 P L-1 h 1:L-1 η , which implies h L θ ≡ h L η • P -1 L-1 M -1 L-1 , i.e. h L θ and h L η • P -1 L-1 M -1 L-1 are identical linear functions supported on the full-dimensional domain Z L-1 θ . It follows that W L = W L P -1 L-1 M -1 L-1 and b L = b L .

Discussion of assumptions. Most of the theorem's assumptions have their origin in Lemma 4. The reason we restrict the domain of h l:L to the interior of Z l-1 is that we want h l:L to be defined on an open set (otherwise fold-sets become unwieldy). For similar reasons, we study only architectures with non-increasing widths; otherwise int Z l-1 may be empty. We conjecture that the theorem does not hold for more general architectures. If it does, the proof will likely go beyond fold-sets.

To guarantee transparency, our construction is such that for each input z ∈ Z and layer l ∈ [L -1], either h 1:l 1 (z) > 0 or h 1:l 2 (z) > 0. Transparency could in principle be achieved with just a single unit, but it would have to be positive everywhere. This is why we impose d l ≥ 2. Guaranteeing transparency for the first layer (whose inputs are not constrained to the positive quadrant) also necessitates boundedness of Z. Boundedness can be lifted if we consider a slightly modified definition of transparency; proofs become more complicated though and we do not consider this crucial. Almost all of the proof carries over to the case of leaky ReLU activations (where σ is defined as σ(u) i = max {αu i , u i } for some small α > 0). The part that does not carry over is our proof that M l has only positive entries on the diagonal: In this part, we compare the slope of h l:L θ for inputs on the positive and negative side of a given ReLU unit, and notice that the negative-side slope is 'singular' in the sense that some basis directions have zero magnitude. This particular argument does not work for the leaky ReLU, though we cannot rule out that a simple workaround exists.

7. DISCUSSION & FUTURE WORK:

In this work, we have shown that for architectures with non-increasing widths, certain ReLU networks are almost uniquely identified by the function they implement. The result suggests that the function-equivalence classes of ReLU networks are surprisingly small, i.e. there may be only little redundancy in the way ReLU networks are parameterised, contrary to what is commonly believed. This apparent contradiction could be explained in a number of ways:

• It could be the case that even though exact equivalence classes are small, approximate equivalence is much easier to achieve. That is, it could be that h θ -h η ≤ is satisfied by a disproportionately larger class of parameters η than h θ -h η = 0. This issue is related to the so-called inverse stability of the realisation map of neural nets, which is not yet well understood. • Another possibility is that the kind of networks we consider in this paper is not representative of networks typically encountered in practice, i.e. it could be that 'typical networks' do not have well connected dependency graphs, and are therefore not easily identifiable. • Finally, we have considered only architectures with non-increasing widths, whereas some previous theoretical work has assumed much wider intermediate layers compared to the input dimension. It is possible that parameterisation redundancy is much larger in such a regime compared to ours. However, gains from over-parameterisation have also been observed in practical settings with architectures not unlike those considered here.

A APPENDIX:

Use the following look-up table to find a particular lemma or theorem and its proof.

Lemma 1

→ Lemma A.15 Lemma 2 → Corollary A.1 Lemma 3 → Lemma A.18 Lemma 4 → Lemma A.17 Theorem 1 → Theorem A.1 A.1 PIECE-WISE LINEAR SURFACES Definition A.1 (Partition). Let S ⊆ Z.

We define the partition of Z induced by S, denoted P Z (S), as the set of connected components of Z \ S. Definition A.2 (Piece-wise hyperplane). Let P be a partition of Z. We say H ⊆ Z is a piece-wise hyperplane with respect to partition P, if H = ∅ and there exist (w, b) = (0, 0) and P ∈ P such that H = {z ∈ P | w z + b = 0}. Definition A.3 (Piece-wise linear surface / pwl. surface). A set S ⊆ Z is called a piece-wise linear surface on Z of order κ if it can be written as S = l∈[κ],i∈[n l ] H l i , where each H l i is a piece-wise hyperplane with respect to P Z ( k∈[l-1],j∈[n k ] H k j ), and no number smaller than κ admits such a representation. Lemma A.1. If S 1 , S 2 are piece-wise linear surfaces on Z of order k 1 and k 2 , then S 1 ∪ S 2 is a piece-wise linear surface on Z of order at most max {k 1 , k 2 }.

Proof. Let S 1 = l∈[k1],i∈[n l ] H l i and S 2 = l∈[k2],i∈[m l ]

G l i be the pwl. surface representations of S 1 , S 2 . Given H l i , consider the partition

EQUATION

We can write H l i = P ∈P H l i ∩ P and denote the nonempty intersections H l i ∩ P as Hl i,j j . Similarly, we decompose G l i = j Ḡl i,j . Then S 1 ∪ S 2 = l∈[max {k1,k2}] ( i,j Hl i,j ∪ i,j Ḡl i,j ), where each Hl i,j and Ḡl i,j is a piece-wise hyperplane wrt.

P = P Z ( k∈[l-1] ( i ,j Hk i ,j ∪ i ,j Ḡk i ,j )).

Given sets Z and S ⊆ Z, we introduce the notation i S := {S ⊆ S | S is a pwl. surface on Z of order at most i}.

(2) (The dependence on Z is suppressed.) By Lemma A.1, i S is itself a pwl. surface on Z of order at most i. Lemma A.2. For i ≤ j and any set S, we have i j S = j i S = i S.

Proof. We will need these definitions:

EQUATION

EQUATION

i j S = {S ⊆ j S | S is a pwl. surface of order at most i}, (5)

EQUATION

Consider first the equality j i S = i S. We know that j i S ⊆ i S because the square operator always yields a subset. At the same time, i S ⊆ j i S, because i S satisfies the condition for membership in (6).

To prove the equality i j S = i S, we use the inclusion j S ⊆ S to deduce i j S ⊆ i S. Now let S ⊆ S be one of the sets under the union in (3), i.e. it is a pwl. surface of order at most i. Then it is also a pwl. surface of order at most j, implying S ⊆ j S. This means S is also one of the sets under the union in (5), proving that i S ⊆ i j S.

Lemma A.3. Let Z and S ⊆ Z be sets. Then one can write k+1 S = k S ∪ i H i where H i are piece-wise hyperplanes wrt. P Z ( k S).

Proof. Let k+1 S = l∈[κ],i∈[n l ] H l i be the pwl. surface representation of k+1 S. If κ ≤ k, then k+1 S = k S and we are done. Otherwise, l∈ 

EQUATION

= l∈[κ],i∈[n l ] H l i is called canonical if l∈[k],i∈[n l ] H l i = k S for all k ∈ [κ], and each H l i is distinct. Lemma A.4. If S = l∈[κ],i∈[n l ] H l

i is a pwl. surface in canonical form, then κ is the order of S.

Proof. Denote the order of S by λ. By the definition of order, λ ≤ κ, and S = λ S. Then, since

EQUATION

It follows that κ = λ.

Lemma A.5. Every pwl. surface has a canonical representation.

Proof. The inclusion l∈[k],i∈[n l ] H l i ⊆ k S holds for any representation. We will show the other inclusion by induction in the order of S. If S is order one, 1 S ⊆ S = i∈[n1] H 1 i holds for any representation and we are done. Now assume the lemma holds up to order κ -1, and let S be order κ. Then by Lemma A.3, S = κ S = κ-1 S ∪ i H κ i , where H κ i are piece-wise hyperplanes wrt. P Z ( κ-1 S). By the inductive assumption, κ-1 S has a canonical representation,

say κ-1 S = l∈[κ-1],i∈[n l ] H l i . We claim that S = l∈[κ],i∈[n l ] H l i is a canonical representation of S. If k = κ, then clearly k S ⊆ S = l∈[κ],i∈[n l ] H l i . If k ∈ [κ -1], then by Lemma A.2, k S = k κ-1 S = l∈[k],i∈[n l ] H l i

, where we have used the canonical representation of κ-1 S.

Finally, distinctness of H l i can be ensured by throwing away duplicates. Lemma A.6. Let Z be an open set. If S is a piece-wise linear surface on Z, and if S =

l∈[κ],i∈[n l ] H l i and S = k∈[κ],j∈[m k ] G k j are two canonical representations of S, then for all l ∈ [κ]

, n l = m l and there exists a permutation π :

[n l ] → [n l ] such that H l i = G l π(i) .

In other words, the canonical representation is unique up to within-order indexing.

Proof. Let k ∈ [κ]. Because both representations are canonical, we have

EQUATION

where H k i and G k j are piece-wise hyperplanes wrt. P Z ( k-1 S). Then for each

EQUATION

where on both sides above we have a union of hyperplanes on an open set. The claim follows.

Definition A.5 (Dependency graph of a pwl. surface). Let S be a piece-wise linear surface on Z, and let S = l∈[κ],i∈[n l ] H l i be its canonical representation. We define the dependency graph of S as the directed graph that has the piece-wise hyperplanes H l i l,i as vertices, and has an edge

H l i → H k j iff l < k and H l i ∩ cl H k j = ∅.

Z. (We will omit the subscript θ when it is clear from the context.) We write f | A to denote the restriction of the function f to the domain A.

Definition A.7 (Activation indicator). A tuple:

I (I 1 , . . . , I L-1 ) is called an activation indicator if I l = diag(i l ) ∈ R d l ×d l and i l ∈ {0, 1} d l for l ∈ [L -1]. It is called non-trivial if i l = 0 for all l ∈ [L -1] and non-trivial up to k if i l = 0 for all l ∈ [k]. Given a parameter vector θ (W 1 , b 1 , . . . , W L , b L

) and an activation indicator I, we introduce the notation

EQUATION

EQUATION

)

(We will omit the argument θ when it is clear from the context.) These quantities characterise the different linear pieces implemented by the network's units. Also define I θ (z) (I θ 1 (z), . . . , I θ L-1 (z)) as the activation indicator for a specific input:

I θ l (z)[i, i] 1 h 1:l i (z) ≥ 0 for all (l, i). Lemma A.7. In a ReLU network with parameters θ = (W 1 , b 1 , . . . , W L , b L ), the pre-activations satisfy h 1:l i (z) ∈ w l i (θ, I) • z + b l i (θ, I) I

, where the indexing runs over all possible activation indicators I. More precisely,

h 1:l i (z) = w l i (θ, I θ (z)) • z + b l i (θ, I θ (z)).

Proof. Left as exercise.

Definition A.8 (Fold-set). Let Z be an open set, and f : Z → R a continuous, piece-wise linear function. We define the fold-set of f , denoted by F(f ), as the set of all points at which f is nondifferentiable. Definition A.9 (Positive / negative in a neighbourhood). Let Z be an open set. The function f : Z → R is positive (negative) in the neighbourhood of z ∈ Z if for any > 0 there exists z ∈ B (z) such that f (z ) > 0 (f (z ) < 0). Definition A.10 (Unit fold-set). Let h θ : Z → R be a ReLU network. We define the unit (l, i) fold-set of h θ , denoted F l i (h θ ), as the set of all z ∈ Z where h 1:l θ [i](z) = 0 and h 1:l θ [i] is positive in the neighbourhood of z. Lemma A.8. Let Z be an open set, and f : Z → R a continuous piece-wise linear function. Then

F(σ • f ) consists of those z ∈ Z that satisfy • f (z) > 0 and z ∈ F(f ), or • f (z) = 0 and f is positive in the neighbourhood of z.

Proof. We will prove that if z satisfies any of the two conditions, then z ∈ F(σ •f ), and if it violates both, then z ∈ F(σ • f ) c . We begin with the latter implication.

Let z be such that f (z) > 0 and z / ∈ F(f ), i.e. f is differentiable at z. Since f is piece-wise linear, there exists > 0 such that all of B (z) lies inside a single linear region of f and f (B (z)) ⊆ (0, ∞]. Then, on B (z), the ReLU behaves like an identity, implying σ • f is differentiable at z, proving that z ∈ F(σ • f ) c . Next, consider z such that f (z) = 0. For it to violate the second condition, there must exist a ball B (z) around z such that f (B (z)) ⊆ (-∞, 0]. (This is also true if f (z) < 0.) Then, on B (z), the ReLU behaves like a constant zero, implying that σ • f is differentiable at z.

We now prove the other implication. If f (z) > 0 and z ∈ F(f ), then there exists > 0 such that f (B (z)) ⊆ (0, ∞], which guarantees that the ReLU behaves like an identity on B (z). In this ball, we have σ

• f = f , so z ∈ F(σ • f ).

If f (z) = 0 and f is positive in the neighbourhood of z, we distinguish several cases. If z / ∈ F(f ), then there exists a ball B δ (z) on which f behaves linearly, i.e. σ(f

(z)) = σ(w z + b), implying z ∈ F(σ • f ). If z ∈ F(f )

and, in addition, there exists a ball B δ (z) such that f (B δ (z)) ⊆ [0, ∞), then the ReLU behaves like an identity on B δ (z) and z ∈ F(σ • f ). The final case is z ∈ F(f ) such that f attains both positive and negative values in its neighbourhood. Since f is piece-wise linear, there exist p, n such that f (z + n) < 0 < f (z + p), and z + p, z

+ n / ∈ F(f ) for all ∈ (0, 1]. Then ∇(σ • f )(z + p) = 0 and ∇(σ • f )(z + n) = 0, yielding z ∈ F(σ • f ).

Lemma A.9. Let Z be an open set, and let f 1 , . . . , f n : Z → R be continuous, piece-wise linear functions. For any w 1 , . . . ,

w n ∈ R, define f = n i=1 w i f i . Then F(f ) ⊆ n i=1 F(f i ).

Proof. Left as exercise.

A.3 GENERAL AND TRANSPARENT RELU NETWORKS:

Lemma A.10. For all θ except a closed zero-measure set,

EQUATION

for all activation indicators I and all k ≤ l.

Proof. First, notice that ( 16) is just a special case of ( 17) with I l equal to the identity matrix. It therefore suffices to prove (17).

To further simplify, we will prove the statement for a single fixed activation indicator I. Then if Θ(I) is the set of networks for which (17) holds given I, and Θ(I) contains all networks except a closed zero-measure set, then also I Θ(I) contains all networks except a closed zero-measure set, proving the lemma.

Let us hence fix I, and let k ∈ [L]. We proceed by induction. For the initial step, notice that the matrix I k W k is just W k with some rows replaced by zeroes. The rank of such a matrix is the same as the matrix obtained by removing the zero rows, which has size (rank(I k ), d k-1 ). For all W k except a closed zero-measure set, this matrix has rank min {d k-1 , rank(I k )}.

For the inductive step, denote Wi :

EQUATION

We assume that rank( Wi-1 ) = r i-1 and want to prove the same for i. Notice that for all W i except a closed zero-measure set, any r i rows of W i are linearly independent and their span intersects with ker( W i-1 ) only at 0. To see this, recall that by the inductive assumption, rank( W i-1 ) = r i-1 , so ker( W i-1 ) has dimension d i-1 -r i-1 . We can concatenate any r i -subset of rows of W i to the basis of ker( W i-1 ) to obtain a matrix of size (r i + d i-1 -r i-1 , d i-1 ), which is a wide matrix, because r i ≤ r i-1 . Hence, its rows are linearly independent for all W i except a closed zero-measure set.

We now prove that rank(I i W i Wi-1 ) = min rank( Wi-1 ), rank(I i ) r i . The "≤" direction is immediate. For the "≥" direction, we distinguish between two cases. If rank(I i ) ≤ rank( Wi-1 ), let v 1 , . . . v ri be the (linearly independent) nonzero rows of I i W i . We want to show that v j Wi-1 j are linearly independent, i.e. that I i W i Wi-1 has at least r i linearly independent rows. If ri j=1 λ j v j Wi-1 = 0, then ri j=1 λ j v j ∈ ker( W i-1 ), which by assumption implies λ j v j = 0. By the independence of {v j }, we obtain λ j = 0, i.e. v j Wi-1 j are linearly independent, and rank(I i W i Wi-1 ) = r i .

If rank(I i ) > rank( Wi-1 ), we can reduce the problem to the case rank(I i ) ≤ rank( Wi-1 ) by observing that rank(I i W i Wi-1 ) ≥ rank(J i W i Wi-1 ) if J i equals I i only with some 1's replaced by 0's. We can thus take any such J i and apply the argument from the previous paragraph to obtain rank(I i W i Wi-1 ) ≥ rank(J i W i Wi-1 ) ≥ r i .

Lemma A.11. For all θ except a closed zero-measure set, the following holds. Let (l, i), (k, j) be any units, let I be an activation indicator non-trivial up to l -1, and let J be an activation indicator non-trivial up to k -1, such that (l, i, I 1:l-1 ) = (k, j, J 1:k-1 ). Then, for all scalars c ∈ R, it holds that [w l i (θ, I), b l i (θ,

I)] = c[w k j (θ, J), b k j (θ, J)].

Proof. First, we exclude from consideration all θ

= (W 1 , b 1 , . . . , W L , b L ) such that e i W l I l-1 W l-1 • • • I k W k e j = 0

for some l, k, i, j, and some I non-trivial up to l -1. Since for any fixed (l, k, i, j, I), the set of θ satisfying the above is the set of roots of a non-trivial polynomial in θ, it is zero-measure and closed. Because there are only finitely many configurations of (l, k, i, j, I), we have thus excluded a closed zero-measure set of parameters. We will denote its complement Θ * .

From now on, we assume θ ∈ Θ * . Notice that the case c = 0 of the lemma is thus automatically satisfied, since

w l i (θ, I) e i W l I l-1 W l-1 • • • I 1 W 1 = 0 by the definition of Θ * .

In the following, we can therefore assume c = 0 and treat (l, i, I) and (k, j, J) symmetrically.

Denote by Θ ¬ ⊆ Θ * the set of parameters θ for which the lemma does not hold; we need to show that Θ ¬ is closed and zero-measure. We start by showing the latter property by contradiction. Suppose Θ ¬ is positive-measure. We know that for all θ ∈ Θ ¬ , there exist triples (l, i, I), (k, j, J) as stated in the lemma, and a scalar c ∈ R such that [w l i (θ, I), b l i (θ, I)] = c[w k j (θ, J), b k j (θ, J)]. Let C denote the set of all triplet-pairs ((l, i, I), (k, j, J)) satisfying the conditions of the lemma; then the previous statement can be written as

EQUATION

)

Since C is finite, there exist ((l, i, I), (k, j, J)) ∈ C for which the set under the union (call it Θ ) is positive-measure.

We now consider two cases. If (l, i) = (k, j), then observe that Θ must contain some θ, θ such that θ

EQUATION

EQUATION

Notice that w l i , w k j do not depend on the b l [i]-component of θ, and neither does b

k j because k ≤ l and (k, j) = (l, i). It follows that [w k j (θ, J), b k j (θ, J)] = [w k j (θ , J), b k j (θ , J)] =: v. Notice also that [w l i (θ , I), b l i (θ , I)] = [w l i (θ, I), b l i (θ, I) + δ].

Putting everything together, we have that

EQUATION

EQUATION

which implies (c -c)v = [0, δ], and in particular w k j (θ, J) = 0. This contradicts the assumption that θ ∈ Θ * and completes the proof for the case (l, i) = (k, j).

If (l, i) = (k, j), then it must be that I

EQUATION

EQUATION

where as before, w Lemma A.12. For all ReLU nets h : Z → R except a closed zero-measure set,

F l i (h) = z ∈ Z | h 1:l i (z) = 0 (26) = z ∈ Z | h 1:l i is positive and negative in the neighbourhood of z (27)

for all units (l, i).

Proof. We provide a proof for a single unit (l, i); the extension to all units follows from the finite number of units.

Let G, H, denote the sets defined on the right-hand sides of ( 26) and ( 27) respectively. Clearly, H ⊆ F l i (h) ⊆ G. We will show that G ⊆ H. Let Y ⊆ R denote the set of all local optima of the function z → W l [i, :] • ȟ1:l-1 (z). Due to piece-wise linearity of the function, and the finite number of pieces, Y is finite. It follows that for all ReLU networks except a closed zero-measure set, -b l [i] / ∈ Y. It is thus guaranteed that h 1:l i never attains a local maximum or minimum at zero. No z ∈ G can therefore be a local maximum or minimum, implying that h 1:l i is both positive and negative in the neighbourhood of z. Hence, z ∈ H. Definition A.11 (General ReLU network). A ReLU network is general if it satisfies Lemmas A.10, A.11 and A.12.

All ReLU networks except a closed zero-measure set are general.

Lemma A.13. If h is a general ReLU network, then F(h 1:l i ) = d l-1 j=1 F( ȟ1:l-1 j

) for all (l, i).

Proof. The inclusion F(h 1:l i ) ⊆ Second, say both I and J are non-trivial up to l -1. From ∇ ȟ1:l-1 k (z 1 ( )) = ∇ ȟ1:l-1 k (z 2 ( )) it follows that I 1:l-1 = J 1:l-1 , we can therefore apply Lemma A.11 to (l, i, I) and (l, i, J). We obtain w l i (I) = w l i (J), implying ∇h 1:l i (z 1 ( )) = ∇h 1:l i (z 2 ( )). Thus, z must be a fold-point of h 1:l i . Finally, say I is trivial up to l -1 and J is non-trivial up to l -1. Then ∇h 1:l i (z 1 ( )) = w l i (I) = 0, whereas Lemma A.11 applied to (l, i, J) with c = 0 yields ∇h 1:l i (z 2 ( )) = w l i (J) = 0. Hence, ∇h 1:l i (z 1 ( )) = ∇h 1:l i (z 2 ( )) and z must be a fold-point of h 1:l i .

trivially. Now assume that F(h 1:l i ) = k∈[l-1],j∈[d k ] F k j (h) holds; we will prove the same statement for l + 1. By Lemma A.8 and Lemma A.13, we have

EQUATION

EQUATION

Since

d l i=1 z ∈ Z | h 1:l i (z) > 0 ⊆ Z, we obtain F(h 1:l+1 ι ) ⊆ k∈[l-1],j∈[d k ] F k j (h) ∪ j∈[d l ] F l j (h) = k∈[l],j∈[d k ]

F k j (h). 

EQUATION

)

Because h is transparent, there exists i ∈ [d l ] : h 1:l i (z) ≥ 0, so for this i we have h 1:l i (z) = 0. However, by Lemma A.12, this implies z ∈ F l i (h) ⊆ F(h 1:l+1 ι ). 

The positivity condition guarantees that (w(P ), b(P )) = (0, 0), so P ∩ F l+1 i is either an empty set or a piece-wise hyperplane. • dim Z l = d l , and

:

See Appendix, Lemmas A.10, A.11 and A.12.

See Appendix, Lemma A.19.

A similar figure has appeared in the work ofRaghu et al. (2017).

See Appendix, Lemma A.1.

See Appendix, Lemmas A.5 and A.6.

See Appendix, Lemma A.19.

See Appendix, Theorem A.1.

Figures and Tables:

Figure 4: A piece-wise linear surface in canonical form and its dependency graph.

Consider a bounded open nonempty domain Z ⊆ R d0 and any architecture (d 0 , . . . , d L ) with d 0 ≥ d 1 ≥ • • • ≥ d L-1 ≥ 2, d L = 1. For this architecture, there exists a ReLU network h θ : Z → R such that for any general ReLU network h η : Z → R (with the same architecture) satisfying h θ (z) = h η (z) for all z ∈ Z, there exist permutation matrices P 1 , . . . P L-1 , and positive diagonal matrices M 1 , . . . , M L-1 , such that

l i does not depend on the b λ [ι]-component. For b l i we now have b l i (θ , J) = b l i (θ, J) and b l i (θ , I) = b l i (θ, I) + d, where d = δe i W l I l-1 • • • W λ+1 e ι and by membership in Θ * , d = 0. From here, we can proceed as in the case (l, i) = (k, j), completing the proof for Θ ¬ being zero-measure. Finally, we show that Θ ¬ is closed. Let θ ∈ Θ * \ Θ ¬ , i.e. for all ((l, i, I), (k, j, J)) ∈ C, the vectors [w l i (θ, I), b l i (θ, I)] and [w k j (θ, J), b k j (θ, J)] are non-colinear. Since w l i , b l i , w k j , b k j are continuous functions in θ, there exists a small enough > 0 such that [w l i (θ , I), b l i (θ , I)] and [w k j (θ , J), b k j (θ , J)] are non-colinear for all θ ∈ B (θ) and all ((l, i, I), (k, j, J)) ∈ C. Hence, Θ * \ Θ ¬ is open, and Θ ¬ is closed.

follows from Lemma A.9. For the other inclusion, let z ∈ F( ȟ1:l-1k ) for some k ∈ [d l-1 ]. Then there exist sequences of points z 1 ( ), z 2 ( ) ∈ B (z) \ d l-1 j=1 F( ȟ1:l-1 j) such that I(z 1 ( )) =: I and I(z 2 ( )) =: J are independent of , and∇ ȟ1:l-1 k (z 1 ( )) = ∇ ȟ1:l-1 k (z 2 ( )). We consider three cases based on the (non-)triviality of I and J.First, suppose both I and J are trivial up to l -1. Then by Lemma A.7,∇ ȟ1:l-1 k (z 1 ( )) = I l-1 [k, k] w l( ).Hence, at least one of I, J, must be non-trivial up to l -1.

show the reverse inclusion; we do so by contradiction.Suppose z ∈ k∈[l],j∈[d k ] F k j (h) \ F(h 1:l+1 ι ), or equivalently z ∈ k∈[l-1],j∈[d k ]

Let h : Z → R be a ReLU network. Then F l+1 i (h) is a union of piece-wise hyperplanes wrt. P Z ( k∈[l],j∈[d k ] F k j (h)).Proof. Since P Z (F(h 1:l+1 i)) is the partition of the input space into the linear regions of h 1:l+1 i , andF(h 1:l+1 i ) ⊆ k∈[l],j∈[d k ] F k j (h) by Lemma A.15, the function h 1:l+1 i is also linear on the regions ofP Z ( k∈[l],j∈[d k ] F k j (h)). For any P ∈ P Z ( k∈[l],j∈[d k ] F k j (h)), denote the slope and bias of h 1:l+1 i on P by w(P ), b(P ). ThenP ∩ F l+1 i (h) = {z ∈ P | w(P ) z + b(P ) = 0(41)and h 1:l+1 i is positive in the neighbourhood of z}.

Let h : Z → R be a ReLU network. Then the set l∈[κ],i∈[d l ] F l i (h) is a pwl. surface of order at most κ. In particular, if h is general and transparent, thenF(h) = l∈[L-1],i∈[d l ] F l i (h) is a pwl. surface of order at most L -1.A.4 MAIN RESULTLemma A.17. For any bounded domain X and any architecture (d 1 , . . . , d L-1 ) withd 0 ≥ d 1 ≥ • • • ≥ d L-1 ≥ 2,there exists a nonempty open set of transparent ReLU networks h : X → R such that for l ∈ [L -1],

At the same time, k S ∪ i∈[n k+1 ] H k+1 i is a pwl. surface of order at most k + 1 because k S is a pwl. surface of order at most k and H k+1 i can be decomposed into piece-wise hyperplanes wrt. P Z ( k S). Therefore, k S ∪ i∈[n k+1 ] H k+1 i ⊆ k+1 S, implying in fact equality. Definition A.4 (Canonical representation of a pwl. surface). Let S be a pwl. surface on Z. The pwl. surface representation S

Table content: <table/>

Peer review (iclr2020):
This paper proves that, modulo permutation and scaling, ReLU networks with non-increasing widths are uniquely characterized by the function they induce (excepting some degenerate cases). This result is not apriori obvious and is of interest. Authors are commended for balancing brevity, intelligibility, and precision. However, it is not clear which elements of the proof technique are inapplicable to leaky ReLUs. It would be helpful to include a brief discussion on this. I recommend acceptance, since I didn*t find any proof errors and the contribution is clear.