Tessellation-Filtering ReLU Neural Networks

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

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 νι.

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.

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 .

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.