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 feed-forward 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.
 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) . 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-Zhu et al., 2019; Du et al., 2019; Frankle & Carbin, 2019) , and better generalisation (Belkin et al., 2019; Neyshabur et al., 2019; Novak et al., 2018) . However, the specific mechanism by which over-parameterisation operates is still largely a mystery. In this work, we study one particular aspect of over-parameterisation, namely the ability of neural networks to represent a target function in many different ways. In other words, we ask whether many different parameter configurations can give rise to the same function. Such a notion of parameterisation redundancy has so far remained unexplored, despite its potential connections to the structure of the loss landscape, as well as to the literature on neural network capacity in general. Specifically, we consider feed-forward ReLU networks, with weight matrices W 1 , . . . , W L , and biases b 1 , . . . , b L ,. We study parameter transformations which preserve the output behaviour of the network h(z) = W L σ(W L−1 σ(. . . W 1 z + b 1 . . . ) + b L−1 ) + b L for all inputs z in some domain Z. Two such transformations are known for feed-forward ReLU architectures: 1. Permutation of units (neurons) within a layer, i.e. for some permutation matrix P, 2. Positive scaling of all incoming weights of a unit coupled with inverse scaling of its outgoing weights. Applied to a whole layer, with potentially different scaling factors arranged into a diagonal matrix M, this can be written as 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 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 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. 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. We consider these questions important directions for further research. We also hypothesise that our analysis could be extended to convolutional and recurrent networks, and to other piece-wise linear activation functions such as leaky ReLU. 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 , 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 }. We can write H Given sets Z and S ⊆ Z, we introduce the notation (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: j S = {S ⊆ S | S is a pwl. surface of order at most j}, i j S = {S ⊆ j S | S is a pwl. surface of order at most i}, surface of order at most j}. 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. At the same time, 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. Definition A.4 (Canonical representation of a pwl. surface). Let S be a pwl. surface on Z. The pwl. 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 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, Proof. Let k ∈ [κ]. Because both representations are canonical, we have where H k i and G k j are piece-wise hyperplanes wrt. 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
We prove that there exist ReLU networks whose parameters are almost uniquely determined by the function they implement.
{"src": "scitldr-AIC_train", "paper_id": "Bylx-TNKvH"}