--- title: "Tessellation-Filtering ReLU Neural Networks" authors: - "Bernhard A. Moser" - "Michal Lewandowski" - "Somayeh Kargaran" - "Werner Zellinger" - "Battista Biggio" - "Christoph Koutschan" doi: "10.24963/ijcai.2022/463" url: "https://ijcai.org/proceedings/2022/463" pdf: "https://ijcai.org/proceedings/2022/0463.pdf" venue: "Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence" year: 2022 pages: "3335-3341" track: "Main Track" keywords: - "Machine Learning: Theory of Deep Learning" - "Machine Learning: Learning Theory" --- # Tessellation-Filtering ReLU Neural Networks Bernhard A. Moser, Michal Lewandowski, Somayeh Kargaran, Werner Zellinger, Battista Biggio, Christoph Koutschan *Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence*, pages 3335-3341. DOI: [10.24963/ijcai.2022/463](https://doi.org/10.24963/ijcai.2022/463) ## Abstract We identify tessellation-filtering ReLU neural networks that, when composed with another ReLU network, keep its non-redundant tessellation unchanged or reduce it.The additional network complexity modifies the shape of the decision surface without increasing the number of linear regions. We provide a mathematical understanding of the related additional expressiveness by means of a novel measure of shape complexity by counting deviations from convexity which results in a Boolean algebraic characterization of this special class. A local representation theorem gives rise to novel approaches for pruning and decision surface analysis. ## Full text ## 1 Introduction We present a novel approach to analyze and quantify the shape complexity of the decision surface of a deep model based on Rectified Linear Units. To this end, we introduce a special class of functions that reflects the non-convexity characteristics of the decision surface in an extended neighborhood of a point in a Boolean-algebraic way, thus providing a rich mathematical structure for analysis and computation. As main result we provide a Representation Theorem that decomposes the network into a shape complexity part, represented by our special class, and an underlying hyperplane tessellation. For sake of comprehensibility we use an instructive example that resembles the construction of a Cantor set in fractal geometry. The Rectified Linear Unit (ReLU), σ(x) := max(x, 0), x ∈ R, is currently the most commonly used non-linear activation function in deep learning models [Glorot et al., 2011; Szandała, 2021]. It is motivated by the neocortex [Hahnloser et al., 2000] and many of the most widely used neural network models such as VGG [Simonyan and Zisserman, 2015], GoogLeNet [Szegedy et al., 2015] or ResNet [He et al., 2016] are based on the ReLU activation function. ReLU networks do also play a prominent role in theoretical analysis, particularly in the context of understanding complexity and expressiveness of deep neural networks [Mont´ufar et al., 2014; Raghu et al., 2017; Arora et al., 2018; Mont´ufar et al., 2021]. ∗Contact Author Since a deep ReLU neural network (ReLU DNN) represents a piecewise linear function it can be partitioned into affine functions over polyhedral regions, also called linear regions in the literature. The transition from one linear region to another one changes the slopes in the input-output function as well as it changes the activation pattern of firing neurons. A larger number of linear regions therefore indicates greater expressiveness of the underlying DNN architecture. Previous research on understanding ReLU DNNs has focused on analyzing the number of linear regions by searching for lower and upper bounds for a given network architecture in terms of number of network layers and number of neurons [Mont´ufar et al., 2014; Serra et al., 2018]. It is argued that, in general, the number of linear regions grows polynomially with the number of neurons but can grow exponentially with the number of layers, underpinning the intuition that deep neural networks have greater expressiveness than shallow architectures. However there remains a gap in explaining the theoretical bounds found by specifically constructed ReLU DNNs and the number of linear regions observed in practice [Hanin and Rolnick, 2019]. From a topological perspective the concept of Betti numbers has been investigated [Bianchini and Scarselli, 2014] to characterize the connectivity properties of the induced decision function. For a subset S ⊂ Rn there are n Betti numbers [Peterson, 1969], bk(S) ∈ N0, 0 ≤ k ≤ n-1, where b0(S) denotes the number of connected components and bk(S) the number of k-dimensional holes in S. Since geometric bodies with different Betti numbers cannot transformed into each other by means of bicontinuous mappings, Betti numbers provide a consistent notion of complexity of geometric regions, respectively decision surfaces in high-dimensional spaces. For instance, a disc in R2 has no holes, therefore, we have b1(disc) = 0 while b1(circle) = 1, and b1 equals 1 for a 2D-sphere in R3 , while b1 = 2 for a torus. It can be shown that the sum of Betti numbers can grow exponentially in the number of neurons of a deep network while it is limited by polynomial growth for shallow networks [Bianchini and Scarselli, 2014]. To start the discussion we introduce two illustrative examples with decision surfaces without any holes, i.e., with vanishing Betti numbers, but showing different effects when being modeled by means of ReLU DNNs. Example 1. For our first example we start with the function A(x) := max{-3x + 1, 0, 3x - 2} on [0, 1] and its recursively nested composition A(k+1) (x) := A(A(k) (x)), A(1) (x) := A(x), defining decision surfaces (here a 1dimensional decision curve) as upper border of the regions Figure 1: Ragged decision surfaces (k = 2, 3) from Example 1. ![Image](https://ijcai.org/proceedings/2022/fulltext/463/image_000000_04c10eb60f222cedd96fdff70ede5c66fc704efd5064e21ffcc338247d3ef9f3.png) Figure 2: Illustration of in- and out-notches as two types of deviations from convexity. ![Image](https://ijcai.org/proceedings/2022/fulltext/463/image_000001_166a229c124c58c3b6b7ee297bd8d65f26e3dd23d54653829ac9f8781c24b990.png) See Figure 1 for an illustration. Example 2. Our second example is the function that checks whether all elements of a finite list of non-negative values (x1, . . . , xn) ∈ [0,∞)n are strictly positive or not. Despite vanishing Betti numbers, this example shows a complex decision surface approximating a fractal geometry for growing recursion depth, which can be realized in various ways: for example, as a deep network that is constructed from the recursion, but also as a shallow network by modeling each of the zigzag components separately in a first layer and then combining them in a second layer. This also shows that ReLU DNN representations are not unique. Though the second example can be fully characterized by n half-space decisions, its realization by means of a ReLU DNN, e.g., min{x1, x2} = (x1 + x2 - |x1 - x2|)/2 induces a tessellation with an exponential number of linear regions. The examples demonstrate (1) that Betti numbers are a too coarse concept of complexity to represent the expressive power of neural networks, and (2) that there is a gap between expressiveness in terms number of linear regions on the one hand and expressiveness in terms of which decision surfaces can be represented. In this context, shape complexity beyond Betti numbers has received too little attention in the literature until now. To bridge this gap, after fixing notation and providing preliminaries from discrete mathematics in Section 2, we will introduce in Section 3 the central notion of notches to characterize deviations from convexity. As illustrated in Figure 2, we distinguish between in-notches and out-notches. We start in Section 3 with introducing a measure of shape complexity for quantifying non-convexity structures of a decision surface by exploiting invariant geometric properties between a hyperplane tessellation and its representation in the hypercube of activation patterns. In this context a special class of functions come into play which distinguishes by its shape complexity properties, see Section 4. This special class leads to a Local Representation Theorem, which is discussed in terms of relevance and future research, see Section 5. ## 2 Preliminaries The ReLU activation function σ is defined on vectors x = (x1, . . . , xn) ∈ Rn through entry-wise operation, i.e., σ(x) := (max{x1, 0}, . . . ,max{xn, 0}). The architecture A = (Wi, bi)i=1,...,L of a deep neural network (DNN) is specified by a sequence of matrix-vector pairs (Wi, bi) with Wi ∈ Rni×ni-1 and bi ∈ Rni . The number n0 denotes the dimension of the input space, while ni is called the width of the i-th layer. L is the depth of the network and N = ∑Li=1 ni the total number of neural units. Together with the ReLU activation function σ the architecture A = (Wi, bi)i=1,...,L defines an input-output function NL : Rn0 → RnL resulting from the composition of layers with fi(x) := Wi x + bi. For sake of simplicity we focus on binary classification problems. One way to define such a classifier is by means of nL = 2. The maximal value in the final output (αL,1(x0), αL,2(x0)) indicates the class. If αL,1(x0) ≥ αL,2(x0) the point x0 is classified to belong to the class C, otherwise not. Note that this classification rule can be equivalently represented by an (L + 1)- layered network with nL+1 = 1 by setting αL+1(x0) := max{αL,2(x0) - αL,1(x0), 0}. Because of a ≥ b if and only if max{b - a, 0} = 0, the points classified to belong to the class C can be represented as 0-preimage, N -1 (0), of the function N : Rn0 → R0. We are interested in the geometry of 0-preimages of ReLU DNNs and say that two ReLU neural networks are equivalent if their 0-preimages coincide. ## 2.1 Activation Space and Tessellations Given some data point x0 we obtain the neural activation pattern α(x0) = ((N1(x0))T , . . . , (NL(x0))T ) ∈ RN0 . An entry in the activation pattern is either 0 or positive, referred to as non-active (non-firing) or active (firing) status, respectively. The binary activation states, active or not, are represented by a vector πN(x0) in the hypercube HN = {0, 1}N . We call πN : x ↦→ πN(x) ∈ HN the activation pattern mapping w.r.t N. The activation region R(πN(x0)) = {x ∈ Rn0 | πN(x) = πN(x0)} of points x with the same activation pattern πN(x0) ∈ HN results as solution from a finite number of affine inequalities, therefore yielding a (convex) polyhedron [Hein et al., 2018; Shepeleva et al., 2020]. Let denote by Tess[N] the resulting tessellation induced by the ReLU DNN N . The collection of all half-spaces that describe such polyhedral cells as intersections induces another tessellation. We call it its h-tessellation Tessh[N] and its activation pattern mapping πhN (x0), defined accordingly. Note that a cell in Tess[N] is a finite union of cells in Tessh[N]. According to our setup of the classification problem, we distinguish between '0'- and '> 0'-activations patterns, respectively, depending on whether an activation pattern results from a point in N -1 (0) or its complement. We denote by A0 := {πN(x) | x ∈ N -1 (0)} the set of 0-activation patterns, and we define A>0 := {πN(x) | x ∈ Rn0 \ N -1 (0)}; we write Ah0 := {πhN (x) | x ∈ N -1 (0)}, resp., Ah>0 , if the activation patterns refer to the h-tessellation. We call an activation region in-cell if it is contained in the 0-preimage of N, i.e., its associated activation pattern π is an element of A0. Otherwise we call an activation region outcell. A tessellation Tessh[N] can be redundant in the sense that the removal of some of its half-spaces does not change the decision surface. We write effTessh[N] if all redundant half-spaces have been removed, and call it the effective htessellation of N . If only a single entry differs when comparing two activation patterns πA and πB, the corresponding polyhedral activation regions RπA and RπB touch each other by sharing a common polyhedral face. This way we can introduce notions of connectedness and other topological concepts. We say that two activation patterns πA and πB are adjacent if their Hamming distance equals 1, i.e., dH(πA, πB) = 1. A path between πA and πB is a sequence of adjacent activation patterns connecting πA with πB. The shortest path length is given by the Hamming distance d = dH(πA, πB). For M ⊆ HN, we write πA ∼M πB if there is a connecting path in M between πA ∈ M and πB ∈ M. Accordingly a set C of activation patterns is connected if there is a path connecting any pair of points in the set C such that all activation patterns along the path are also in C. A connected component is a maximally connected set. In contrast to Euclidean spaces the shortest path in a Hamming space is not unique. ## 2.2 Convexity in Hamming Space The convexity of a set C in Euclidean geometry is characterized by the property that any line segment connecting two points in the set is also contained in the set C. As a line segment is the shortest path in Euclidean geometry we generalize this concept to the Hamming space as follows. Definition 1 (Convex Sets (Hulls) of Activation Patterns). A set C ⊆ {0, 1}m of activation patterns is convex if and only if it contains all shortest Hamming paths connecting any two points in C. The convex hull convH[C] of activation patterns C ⊆ {0, 1}m is the smallest convex set containing C. The following lemma allows us to reformulate geometric problems in h-tessellations in terms of combinatorial problems in the hypercube Hm = {0, 1}m. A k-dimensional face of Hm consists of all points that agree on a collection of m-k coordinates, thereby forming a hypercube of dimension k. Lemma 1 (Equivalence of Convexity Notions). A convex arrangement of activation regions of an h-tessellation with m half-spaces in Euclidean space corresponds to a convex set of activation patterns in Hamming space, i.e., a face of the hypercube Hm = {0, 1}m, and vice versa. ## 3 Notches and Shape Complexity Instead of counting holes by means of Betti numbers [Bianchini and Scarselli, 2014], we are counting notches, i.e., deviations from convexity, in terms of minimal convex arrangements of activation regions in an h-tessellations that cover the regions of non-convexity. Due to Lemma 1 we can equivalently formulate this notion of a notch in the Hamming space of activation patterns. An out-notch can be characterized as convex region νo of out-cells (resp. activation patterns of outcells) for which there is a shortest path between activation patterns of in-cells visiting νo. See Figure 3 for an illustration. Analogously, we define an in-notch to be a convex region νι of in-cells for which there is a shortest path between activation patterns of out-cells visiting νι. Figure 3: In this arrangement of activation regions of an htessellation there are two possible configurations of out-notches: first, {o1, o2} and {o2, o3} (as shown), and, second, {o1} and {o2, o3}. The red paths indicate corresponding shortest paths between activation patterns of in-cells visiting the out-notches. ![Image](https://ijcai.org/proceedings/2022/fulltext/463/image_000002_71634b6a59bb56a8d19776c14ac9633571c1363c935784824913125d9fe3240e.png) Definition 2 (Notches in Hamming Space). Consider an htessellation of non-trivial cells generated by m many halfspaces with cells being either in- or out-cells. A notch to the set M ⊂ {0, 1}m within the hypercube HM := convH[M] is a face ν ⊆ HM \M that is adjacent to some π1, π2 ∈ M with non-empty overlap with their convex hull convH[{π1, π2}], i.e., dH(ν, π1) = 1, dH(ν, π2) = 1 and convH[{π1, π2}] ∩ ν ̸= ∅. In case of M ⊆ Ah0 we call the notch an out-notch, and if M ⊆ HM \ Ah0 we call it an in-notch. The cardinality of a minimal configuration of notches such that no further notch can be constructed gives the Out-NotchNumber (resp. In-Notch-Number). For convenience we denote HM := convH[M], 〈π∗ 〉 := {π ∈ M | π ∼M π∗ }, and Hπ∗ := convH[〈π∗ 〉]. Definition 3 (Notch Number). Given an h-tessellation ReLU DNN N : Rn → R0, we define the Notch Number w.r.t. the set M, ΘN[M], to be the minimal exhaustive number of notches to M within HM. We write ΘoN in case of M = Ah0 and ΘιN if M = HhA0 \ Ah0 . Further, we define the local versions, Local Out-Notch Number, resp. Local In-Notch Number, at the data point x0, resp. its associated activation pattern π∗ := π(x0) by setting ## 3.1 ReLURepresentation w.r.t. In-Notches We can construct a ReLU DNN N ι by starting with an exhaustive list of in-notches {ν ι1 , . . . , ν ιΘιf } to Rn \ f -1 (0) and checking the condition This can be achieved by setting where N ιk denotes the number of faces of notch ν ιk , and ˜ajk (x0) := σjk d(x0, F ik ) denotes the distance between x0 and the hyperplane containing the k-th face F ik of in-notch ν ιk with the sign σjk ∈ {-1, 1} defined such that ˜ajk (x0) ≤ 0 if x0 ∈ ν ιk . ## 3.2 Reconstruction of h-Tessellation Due to tropical algebra [Zhang et al., 2018; Alfarra et al., 2020; Trimmel et al., 2021], a ReLU DNN N can always be represented in the form of with affine functions aj and bj. Now, let us transform (5) to obtain the form of (4) by means of maxri=1 {ai(x)} + minsj=1 {-bj(x)} = minsj=1 {maxri=1 {ai(x) - bj(x)}}. By setting we obtain an h-tessellation that contains the effective htessellation. ## 3.3 Global Shape Complexity Note that the sum of Out- and In-Notch Numbers, reflects the minimal cardinality of a partition of the input space into (convex) polytopes that allows to correctly represent the decision problem whether a point belongs to the 0-preimage of f or not. As a consequence, ΘN proves to be a property of the decision surface itself which is invariant to the complexity of architectures of ReLU DNNs N realizing the same decision problem. In particular, ΘN remains unchanged if the network architecture is differently encoded say by changing the orientations of the half-spaces, or even by relabeling the classes, i.e., interchanging 0 with > 0 (encoded by 1). In the latter, we obtain a new function ˜ f with ˜ f -1 (0) = f -1 (> 0) and, accordingly, ˜ f -1 (> 0) = f -1 (0), which leads to a change of in- to out-notches and vice versa, so that in the end ΘN remains unchanged. Therefore, it is justified to write synonymously Θf = ΘN . This motivates us to consider ΘN as a measure for the shape complexity of the decision surface of a ReLU DNN N . For x0 ∈ N -1 (0) and π∗ = π(x0) = (α∗ 1 , . . . , α∗m) ∈ Hm, we consider the mapping Tπ∗ : Hm → Hm, (˜α1, . . . , ˜αm) = Tπ∗(α1, . . . , αm) given by The mapping Tπ∗ preserves Hamming distances, dH(Tπ∗(π1), Tπ∗(π2)) = dH(π1, π2), and the convexity property, i.e., M is convex if and only if Tπ∗(M) is convex. Therefore, Θf also remains invariant w.r.t Tπ∗- mappings. This means that, without loss of generality, we may assume that the origin π0 = (0, . . . , 0) ∈ Ah0 . Summarizing these findings give the following theorem. Theorem 1 (Invariance of Shape Complexity). Given a piecewise linear function f : Rn → R0 and let Λf be the class of ReLU DNNs N realizing the decision problem represented by f, i.e., to be able to distinguish between the sets f -1 (0) and f -1 (> 0). Then, ΘN for some N ∈ Λf satisfies: - (1) ΘN is invariant w.r.t. architectures N ∈ Λf ; - (2) ΘN is invariant w.r.t. Tπ∗-mappings in the activation space. ## 4 Tessellation-Filtering ReLUNetworks Fix n,m ∈ N and consider an r-class ReLU neural network V : Rn →Rm0 , given by where V1, . . . , Vm are ReLU DNNs acting on the same domain, i.e., Vi : Rn → R0. We are interested in the construction of a ReLU DNN U : [0,∞)m → [0,∞) such that for any choice of body-ReLU DNN (9) the effective tessellation resulting from its concatenation U ◦ V does not have other cells (resp., hyperplanes) than already contained in the effective tessellation effTessh[V] = ⋃i effTessh[Vi], i.e., Condition (10) enforces that the 0-preimage of U does not introduce an additional intersection with any of the half-spaces of Tessh[V]. This can only be the case if This means that U (-1) (0) is enforced to be the union of sets of the form where Fj is either {0} or [0,∞), j ∈ {1, . . . ,m}. All together we obtain the form where Fψ = F (ψ) 1 × . . . ×F (ψ) m and ψ ∈ Ψ ⊆ {0, 1}m and Note that Fψ in (12) characterizes the in-notches of a ReLU DNN U satisfying (10). By specifying the collection Ψ of innotches by means of (13) and utilizing (4), this allows us to construct Let us denote by tessINVm the set of tessellation-filtering ReLU DNNs (14) on [0,∞)m. Since a coordinate-wise lower-relation ψ∗ ≤ ψ implies ∑mi=1 (1-ψi) yi ≤ ∑mi=1 (1ψi∗) yi, it suffices to consider only the maximal elements ψ ∈ Ψ to evaluate (14). Further note that if ψi0 = 1 for all ψ ∈ Ψ} the convex hull of (UΨ)(-1) (0) has dimension lower than m- 1. To avoid redundancy, therefore we require that Ψ to satisfy max{ψi| ψ ∈ Ψ} = 1 for all i = 1, . . . ,m. In graph theory two sets of vertices are called independent if no two vertices in the set are adjacent. For details see [Kahn and Park, 2022]. Let Im denote the collection of maximally independent sets in the corresponding discrete hypercube. Then, considering only maximal vertices such that the maximum yields the upper vertex (1, . . . , 1) means that Ψ ∈ Im. This establishes a one-to-one correspondence between tessINVr and Im. Due to [Kahn and Park, 2022], |Im| is asymptotically 2m22m/4 , which quantifies the diversity, hence expressiveness, of the special subclass of tessellation-filtering ReLU DNNs in m variables. As Ψ consists of maximal elements, as a byproduct we get a characterization of the In-Notch Number of its induced decision surface in Theorem 2. Theorem 2 (In-Notch Number of U ∈ tessINVm). Let Ψ ∈ Ir and UΨ ∈ tessINVm, then A tessellation-filtering ReLU DNN has the special property that its global In-Notch Number equals its Local In-Notch Number, which turns out to be characteristic. Theorem 3 (tessINVm Characterization). For a ReLU DNN N : [0,∞)m → [0,∞), m ∈ N, we have N is tessellationfiltering if and only if ΘιN (0) = ΘιN . Proof. (11) implies that for all in-notches ν of a tessellationfiltering N we have But ΘιN can only be greater than ΘιN (0) if there are innotches not satisfying (16). Decomposing now the ReLU DNN in a top and a body network, i.e., N = N ′′ ◦ N ′ , and applying the tropical Tessh reconstruction (6) on N ′′ , we obtain a local representation of N at x0 ∈ N -1 (0), which allows us to capture non-convexity characteristics of the decision surface. To simplify notation, we write π′′ := πhN ′′ , π′ := πN ′ and Z := {π′′ (x) | N ′′ (x) = 0}. Let us partition Z = E ∪ G via Applying (8), Tπ′′ (x0) induces the tessellation-filtering ReLU DNN UΨ given by Note that equation (18) also holds on the Hamming ball Bd∗(π′′ (x0)) that does not contain activation patterns from G. (18) can be applied to N by restricting x to the activation region R := {x | π′ (x) = π′′ (x0)}, giving Theorem 4. Figure 4: Ball Bd∗ centered at the marked cell for Example 1 for k = 3. The ball covers non-convexity regions according to the structure of (12), which allows the application of lattice-based computations (20) in order to compute the local shape complexity as outlined. The red dotted lines mark the effective h-tessellation. The white cells (out-notches) have d∗ = 0, while the cells on the bottom (like the black marked) have highest d∗ = 3, indicating lower shape complexity. See Figure 5 for plotted shape complexities. ![Image](https://ijcai.org/proceedings/2022/fulltext/463/image_000003_aa3f47a77814105e4c75d1b051c792b04246f7b32d190433c4788f23b2046f91.png) Theorem 4 (Local Representation Theorem). Given the ReLU DNN N = N ′′ ◦ N ′ and x0 ∈ N -1 (0), then there is a UΨ ∈ tessINVm (m is the number of half-spaces in Tessh(N ′′ )) satisfying for π given by the h-tessellation {hi ◦N ′ | hi ∈ Tessh(N ′′ )} and x ∈ R ∩ Bd∗ (π(x0)), Note that Theorem 4 generalizes the setting of fixing all activation values for a point x0, giving a polyhedron [Hein et al., 2018]. A single cell does not have any (topological) information about the decision surface geometry. Therefore, we enlarge the view by fixing only the activation values for the body part N ′ , resulting in a respectively complex region that cannot be handled easily anymore, see, e.g., [Mont´ufar et al., 2021]. Figure 4 shows such an extended ball. Our theorem opens up a way to make this enlarged environment manageable for shape analysis. Note that already in a second layer we, in general, loose convexity as invariant property between polyhedral arrangements in the input space and the activation space. So, the h-tessellation is necessary if we want to recover convexity properties, which in our view is crucial to be able to characterize shape complexity adequately. Theorem 4 decomposes the network in to purely shape complexity part, represented by UΨ, and an underlying h-tessellation. This way, replacing UΨ by UΨ′ with less shape complexity smooths the surface, thus acting as pruning operator. But, from a practical view, computing the h-tessellation for the whole network is infeasible and the restriction to a reasonable number of top layers is unavoidable. The choice of the top 2 or 3 layers already provides insights regarding the shape complexity. But future research is needed to analyze these aspects in more detail. ## Algorithm 1 Local UΨ Approximation - 1: Initialization. Set ˆE = ∅, G = ∅, compute π0 = π(x0) and Tπ0 due to (8); i = 1; Compute the h-tessellation by means of (6) utilizing tropical algebra [Trimmel et al., 2021]. - 2: Choose xi ∈ D0 and compute Ti = Tπ0 (π(xi)). - 3: Check whether convH[0, Ti] ⊆ N -1 (0) by means of checking whether there is a yj ∈ D1 such that (gj; 1) = Tπ0 (π(yj)) satisfies (gj; 0) ≤ Ti; if yes, then add (gj; 0) to G; choose the next candidate fromD0 and repeat step 2; - 4: If no yj found then check whether Ti is a maximal element of E by iterating e ∈ ˆE via - 4.1: Me = maxNk=1 (Ti - e)k, me = minNk=1 (Ti - e)k; - 4.2: replace {e ∈ E|Me ≥ 1,me ≥ 0} by Ti in E; - 4.3: if Me -me = 2 for all e ∈ ˆE, then Ti is independent to ˆE and, therefore, add Ti to ˆE; - 4.4: goto step 4.1 until all points fromD0 have been checked. 5: Take the elements of ˆE to define Ψ (see (14)). - 6: Due to (20), compute the maximal Hamming distance d∗ = ming∈G{dH(g, 0)}. ## 5 Algorithm and Examples Theorem 4 gives rise to the following algorithm to identify a locally approximating UΨ in a neighborhood B at x0. We show here the part for the top part and write N instead of N ′′ , to simplify notation. We outline an approximating algorithm that checks condition (17) by randomly selected points in a neighborhood B at x0 by means of a sample D0 = {x1, . . . , xK0 } ⊆ N -1 (0) ∩ B for class 0 and sample D1 = {y1, . . . , yK1 } ⊆ N -1 (> 0)∩B for class 1. This way, Algorithm 1 guarantees a lower bound for the local decision surface complexity. After applying the initialization step of computing the h-tessellation, the time complexity of this algorithm is O((K0 +K1)2 ). Analogously to step 4, we can proceed for G to extract an independent set ˆG ⊆ G of minimal elements in G. By this we obtain ΘιN (x0) = | ˆE| and ΘoN (x0) = | ˆG|, which are invariant to the architecture of N. Note that also the resulting region in the input space given by R = ⋃π∈Bδ∗(π(x0)) R(π) remains invariant to the architecture of N. This motivates us to define a shape complexity measure that is invariant of the architecture of N by setting where Vol[R] can be approximated by ∏ni=1 (ρ-1 i +ρ+1 i ) with ρσi = sup{λ ≥ 0| dH(π(x0 + σ λei), π(x0)) ≤ δ∗ }, σ ∈ {-1, +1}. See Figure 5 for plotted S-curves for Example 1. The top curve, y = 1, shows the highest S values triggered by the outnotched with δ∗ = 0. The curves match with our intuition that more rugged regions show higher S values. In general, for Example 1 we obtain S((x, y)) = O(2k ) with k recursions and (x, y) ∈ [0, 1]2 . Note that Example 2 can be modeled by a min, which is a tessellation-filtering ReLU DNN with Ψ = {∑j̸=i ej | i ∈ {1, . . . , n}} consisting of n independent maximal elements and there is only one out-notch given by ∑j ej . Therefore, we get S(x) = O(n) for x ∈ [0, 1]n . Figure 5: Local Shape Complexity S due to (21) for Example 1 for k = 2 and the lines y = 1, resp. y = 1/3 and y = 0. ![Image](https://ijcai.org/proceedings/2022/fulltext/463/image_000004_b07e08e3837b59a695639830fd32cd4c5cfef423017bff2d72a152f5121fcbaf.png) ## 6 Conclusion Our main focus was on revealing invariant properties between tessellations induced by ReLU DNNs and their Hamming cube counterpart, and exploiting them for the purpose of geometrical analysis of decision surfaces. Several insights and research questions for the future follow from this approach: (i) the special subclass of tessellation-filtering ReLU DNNs is distinguished by special properties, for example in connection with shape geometry. It is quite rich, yet mathematically well-manageable due to its relationship to Boolean algebra; this connection, as e.g. the role of ideals for shape analysis, will be topic of future research; (ii) so does the Local Representation Theorem as one of our main results of this paper; (iii) as a byproduct we obtain tools to construct illustrative examples showing that the number of linear regions, often seen as the measure for expressiveness, is highly dependent on the architecture and can be misleading; (iv) the derivation of an architecture-independent measure for local shape complexity is a first step towards exploiting this approach for decision surface analysis. Our shape complexity measure captures local topological properties of the decision surface. Putting in oversimplified terms, it counts the number of non-convex dents. That is, our complexity measure is related to local 'smoothness' properties of neural networks, which are well known to relate to generalization. The generality of our topological characterization will pave the way towards obtaining mathematical insight and evidence for practically relevant questions such as adversarial vulnerability and also generalization capabilities. ## Acknowledgements This research was carried out under the Austrian COMET program (project S3AI with FFG no. 872172, www.S3AI.at, at SCCH, www.scch.at, and project InTribology with FFG no. 872176 at AC2T, www.ac2t.at), which is funded by the Austrian ministries BMK, BMDW, and the provinces of Upper Austria, Lower Austria, and Vorarlberg. ## References 1. [Alfarra et al., 2020] Motasem Alfarra, Adel Bibi, Hasan Hammoud, Mohamed Gaafar, and Bernard Ghanem. On the decision boundaries of neural networks: A tropical ge- ometry perspective. arXiv, 2002.08838, 2020. 2. [Arora et al., 2018] Raman Arora, Amitabh Basu, Poorya Mianjy, and Anirbit Mukherjee. Understanding deep neu- ral networks with rectified linear units. In ICLR 2018, Van- couver, BC, Canada, April 30 -May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018. 3. [Bianchini and Scarselli, 2014] Monica Bianchini and Franco Scarselli. On the complexity of neural network classifiers: A comparison between shallow and deep architectures. IEEE Trans. Neural Networks Learn. Syst., 25(8):1553-1565, 2014. 4. [Glorot et al., 2011] Xavier Glorot, Antoine Bordes, and Yoshua Bengio. Deep sparse rectifier neural networks. In Geoffrey G., D. Dunson, and M. Dudik, editors, Proc. 14th Int. Conf. on Artificial Intelligence and Statistics, vol- ume 15 of Proceedings of Machine Learning Research, pages 315-323, Fort Lauderdale, FL, USA, 11-13 Apr 2011. PMLR. 5. [Hahnloser et al., 2000] Richard Hahnloser, R. Sarpeshkar, M. Mahowald, and Rodney Douglas. Digital selection and analog amplification co-exist in an electronic circuit in- spired by neocortex. Nature, 405:947-951, 01 2000. 6. [Hanin and Rolnick, 2019] Boris Hanin and David Rolnick. Complexity of linear regions in deep networks. In Ka- malika Chaudhuri and Ruslan Salakhutdinov, editors, Pro- ceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, Cali- fornia, USA, volume 97 of Proceedings of Machine Learn- ing Research, pages 2596-2604. PMLR, 2019. 7. [He et al., 2016] Kaiming He, X. Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 770-778, 2016. 8. [Hein et al., 2018] Matthias Hein, Maksym An- driushchenko, and Julian Bitterwolf. Why ReLU networks yield high-confidence predictions far away from the training data and how to mitigate the problem. arxiv, 1812.05720v2, 2018. 9. [Kahn and Park, 2022] Jeff Kahn and Jinyoung Park. The number of maximal independent sets in the Hamming cube. Combinatorica, March 2022. 10. [Montúfar et al., 2014] Guido F Montúfar, Razvan Pascanu, Kyunghyun Cho, and Yoshua Bengio. On the number of linear regions of deep neural networks. In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K. Q. Wein- berger, editors, Advances in Neural Information Process- ing Systems, volume 27. 11. Curran Associates, Inc., 2014. 12. [Montúfar et al., 2021] Guido Montúfar, Yue Ren, and Leon Zhang. Sharp bounds for the number of regions of max- out networks and vertices of Minkowski sums. CoRR, abs/2104.08135, 2021. 13. [Peterson, 1969] F. P. Peterson. Review: Edwin H. Spanier, Algebraic topology. Bulletin of the American Mathemati- cal Society, 75(5):916 -917, 1969. 14. [Raghu et al., 2017] Maithra Raghu, Ben Poole, Jon Klein- berg, Surya Ganguli, and Jascha Sohl-Dickstein. On the expressive power of deep neural networks. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, vol- ume 70 of Proceedings of Machine Learning Research, pages 2847-2854. PMLR, 06-11 Aug 2017. 15. [Serra et al., 2018] Thiago Serra, Christian Tjandraatmadja, and Srikumar Ramalingam. Bounding and counting lin- ear regions of deep neural networks. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th Inter- national Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 4558- 4566. PMLR, 10-15 Jul 2018. 16. [Shepeleva et al., 2020] Natalia Shepeleva, Werner Zellinger, Michal Lewandowski, and Bernhard Moser. ReLU code space: A basis for rating network quality besides accuracy. ICLR 2020 Workshop on Neu- ral Architecture Search (NAS 2020), arXiv preprint arXiv:2005.09903, 2020. 17. [Simonyan and Zisserman, 2015] Karen Simonyan and An- drew Zisserman. Very deep convolutional networks for large-scale image recognition. In Yoshua Bengio and Yann LeCun, editors, ICLR 2015, San Diego, CA, USA, May 7- 9, 2015, Conference Track Proceedings, 2015. 18. [Szandała, 2021] Tomasz Szandała. Review and compari- son of commonly used activation functions for deep neu- ral networks. In Akash Kumar Bhoi et al., editor, Bio- inspired Neurocomputing, pages 203-224. Springer Sin- gapore, 2021. 19. [Szegedy et al., 2015] Christian Szegedy, Wei Liu, and et al. Going deeper with convolutions. In IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2015, Boston, MA, USA, June 7-12, 2015, pages 1-9. IEEE Com- puter Society, 2015. 20. [Trimmel et al., 2021] Martin Trimmel, Henning Petzka, and Cristian Sminchisescu. Tropex: An algorithm for ex- tracting linear terms in deep neural networks. In Interna- tional Conference on Learning Representations, 2021. 21. [Zhang et al., 2018] Liwen Zhang, Gregory Naitzat, and Lek-Heng Lim. Tropical geometry of deep neural net- works. In Jennifer Dy and Andreas Krause, editors, Pro- ceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 5824-5832. PMLR, 10-15 Jul 2018.