TropEx: An Algorithm for Extracting Linear Terms in Deep Neural Networks
Authors: Martin Trimmel
Henning Petzka
Cristian Sminchisescu
Venue: ICLR 2021 Poster (2021)
Keywords: linear regions
linear terms
deep learning theory
deep neural networks
rectified linear unit
relu network
piecewise linear function
tropical function

Abstract: Deep neural networks with rectified linear (ReLU) activations are piecewise linear functions, where hyperplanes partition the input space into an astronomically high number of linear regions. Previous work focused on counting linear regions to measure the network's expressive power and on analyzing geometric properties of the hyperplane configurations. In contrast, we aim to understand the impact of the linear terms on network performance, by examining the information encoded in their coefficients. To this end, we derive TropEx, a nontrivial tropical algebra-inspired algorithm to systematically extract linear terms based on data. Applied to convolutional and fully-connected networks, our algorithm uncovers significant differences in how the different networks utilize linear regions for generalization. This underlines the importance of systematic linear term exploration, to better understand generalization in neural networks trained with complex data sets.

Published as a conference paper at ICLR 2021
TROPEX: AN ALGORITHM FOR EXTRACTING LINEAR TERMS IN DEEP NEURAL NETWORKS
Martin Trimmel*! Hemning Petzka" Cristian Sminchiseseu
'Lund University Google Research (martin. trimmel, henning, petzka, eonttiaansminchiseseee.. @math. 1th. se
ABSTRACT
Deep neural networks with rectified linear (ReLUU activations are piecewise linear functions, where hyperplanes partition the input space into an astronomically high number of linear regions. Previous work focused on counting linear regions to measure the network's 's expressive power and on analyzing geometric properties of the hyperplane configurations. In contrast, we aim to understand the impact of the linear terms on network performance, by examining the information encoded in their coefficients. To this end, we derive TropEx, a non-trivial tropical algebra- inspired algorithm to systematically extract linear terms based on data. Applied to convolutional and fully-connected networks, our algorithm uncovers significant differences in how the different networks utilize lincar regions for generalization. This underlines the importance of systematic linear term exploration, to better understand generalization in neural networks trained with complex data sets.
INTRODUCTION
Many of the most widely used neural network architectures, including VGG (Simonyan & Zisserman 2015), GoogLeNee (Szegedy et al. 2013) and ResNet (He al. 2016), make use rectified linear activations (ReLU, (Hahnloser et al. 2000: Glorot et al. [201]] D. L.c. o(x) max(x, 0}) and are therefore piecewise linear functions. Despite the apparent simplicity of these functions, there is a lack of theoretical understanding of the factors that contribute the success of such architectures. Previous attempts of understanding piecewise linear network functions have focused on estimating the number of linear terms, which are the linear pieces (affine functions) that constitute the network function. A linear region is being defined as a maximally connected subset of the input space on which the network function linear. Since computing the exact number of linear regions is intractable, work has focused on obtaining upper and lower bounds for this number (Arora et al. 2016 Serra
al. 2018
Pascanu et al. 2013 Raghu al. 2017: Montular al., 2014] Montúfar 2017] Xiong
et al.
2020 Zhang et al. 2018).
To our knowledge. the currently best upper and lower bounds were
calculated by Serra et al. (2018) Raghu et al. (017)) show these bounds to be asymptotically tight.
All of the mentioned papers share the intuition that the number of linear regions of neural networks measures their expressivity. Since the bounds grow linearly in width and exponentially depth, deep networks are interpreted to have greater representational power. However, these bounds are staggeringly high: the upper bound on the number of linear regions in (Serra et al. 2018) exceeds 10 even for the smallest networks in the universe.) For slightly larger networks, the upper bound exceeds 7000 whereas the lower bound exceeds 1083 linear regions. The number of training samples is generally much smaller than the estimated number of linear regions (< 10$), so that almost none of the linear regions contains training data. This raises the question of how representative the number of linear regions for network performance and how information extracted from training samples passes on to the many linear regions free of data for successful generalization to test data.
experimented
(There are approximately 1080 atoms
There are indications that high number of linear regions is not required for good network perfor- mance. Frankle & Carbin (219) point out that smaller networks perform similarly well as large ones, when suitable initialization of the smaller network can be found from training the larger one. Hence,
Denotes equal contribution.

---

Published as a conference paper at ICLR 2021
Training sample
Test sample
Training sample
sample
Figure 1: A ReLU network function before (left) and after (right) extraction. Left: Hyperplanes separate the input space into linear regions. Most of them do not contain any data points. Each data point occupies its own linear region. Right: After extraction, the function remains unchanged on the linear regions of training samples. Test samples now fall into regions of training samples.
the expressivity of the large network helpful to explore the parameter space, but the small, less expressive network is sufficient achieve high accuracy. Lee et al. (2019) and Croce et al. (2018) modify the training loss to encourage larger linear regions with the goal robustness to adversarial attacks. Hanin & Rolnick (2019b a) argue that in practice there fewer linear regions than expected from the bounds and empirically investigate this for the MNIST data set. All these observations question the explanatory power of astronomically high bounds for the number of linear regions. More recently, the focus of research linear regions has been shifting away from pure counting towards an understanding of the linear regions themselves. ZZang & Wu (2020) study geometric properties of linear regions and notice that batch normalization and dropout, albeit leading to similar network accuracies, produce differently looking linear regions.
Our approach to the understanding of linear regions differs in that it investigates the linear coefficients of linear regions. To this end, we propose TropEx, a tropical algebra-based algorithm extracting linear terms of the network function N (Figure [ using data set X. TropEx outputs an extracted function N(x) containing only the linear terms corresponding to regions on which data lies. As result, A and (X() agree on neighbourhoods of all data points. This creates tool for the study of generalization from new viewpoint, i.c., the perspective of linear regions and their coefficients.
Our contributions are as follows:
A new computational framework representing tropical functions (Definition B.4 matrices to
efficiently perform tropical calculations appearing in networks with rectified linear activations.
derive TropEx, algorithm to systematically extract linear terms from piecewise linear network functions
This framework allows
An application of TropEx to fully-con fully-connected (FCN) and convolutional networks (CNN) reveals that (i) consistently all training and test samples fall into different linear regions; (ii) Simple tasks (MNIST) can be solved with the few linear regions of training samples alone, while this does not hold for more complex data sets. (iii) FCNs and CNNs differ in how they use linear regions free of training data for their performance on test data: Several measures illustrate that CNNs, in contrast to FCNs, tend to learn more diverse linear terms. (iv) We confirm that the number of linear regions alone is not good indicator for network performance and show that the coefficients of linear regions contain information on architecture and classification performance.
BACKGROUND AND OVERVIEW
was recently shown by Charisopoulos & Maragos 2018 Zhang et al. (2018) that ReLU neural network functions the same tropical rational maps. Tropical rational maps exactly those functions where each entry in the output vector can be written as a difference of maxima
Mx( (a ... a (x) max
O (x))
(1)
Link open source implementation:
https::/giithu...co/aatttttttttt
2

---

Published as a conference paper at ICLR 2021
where each a Oij R + IR is affine function with only positive coefficients, taking the form Ej Wy + wo with all wy Ryo. Since the number of terms in (T) dwarfs the number of atoms in the universe, is impossible to obtain this expression in practice. Therefore, we only extract those terms that correspond to linear regions data points. For a fixed data point x E X, the maximum of the network outputs
the affine functions such that ox (x) 2 (x)( dx (x) 2 aig (x) for all i. TropEx extracts ax and ax- The
be written as max; (x) a (xx ax (x), where o Ox
extracted terms can be used to construct tropical map (x) (x)** (x)....... Ndd)) (x)) with maximally enlarged linear regions, given by
N/x0 (x) = max (xx (x).....
(x)) - max (x)......
ExED (x)),
(2)
where there are D; data points x Xkp, given label i by the original network. Being tropical rational map, the function A((*) is again a ReLU neural network function by Zhang et al. (2018). The maximal entries of the two output vectors (hence also the assigned labels) of the extracted function A((A')) and the original network N agree in the neighbourhood of any data point E X'.
We discuss the basics of tropical algebra in Appendix B. and refer to Maclagan & Sturmfels (2015) for detailed introduction. The relation of tropical geometry and ReLU networks is studied in Zhang ct al. 2018); Charisopoulos Maragos (2018); Alfarra et al. (202I).
3
METHOD
3.1 MATRIX REPRESENTATION OF TROPICAL RATIONAL MAPS
If one were to represent tropical rational maps symbolically computer, computations would be too slow. Therefore, we present tropical rational maps as multi-dimensional arrays.
Definition 3.1. Given an affine function a : IR + R; x + Σx WgTk + wo. we will call the vector (wo, W Wd,) its coefficient vector, the scalar wo its constant part and the vector (Wi,..., wa,) its variable part.
We can represent functions Nr : Rdo - R as in equation (1 in the following way: Let the of the matrix A RR and the vector a E Raxt be the variable and the constant parts of the affine functions aty. respectively. (Analogously for A, and a, We can then define (A,, a (x) = max (At x + at where the maximum taken over the rows of the resulting column vector. If we define the formal quotienf matrix-vector pairs by ,A,, a///(A, (x)()) max(A x + at}} max(A 4, x +aa a then (G = (At a/AA a (xx, giving us a matrix- representation of the function NG. An entire network function with output dimensions can then be represented by a list (AA). a , a.)) 1515s
The advantage of the proposed matrix representation of tropical rational maps are natural oper- ations performing calculations that arise for (concatenations of) layers of neural networks (see supplements). A dense layer é Rdd - Rda with ReLU activation is represented as list ((A) : (AA) a, matrix W. respectively, i.e. w max Wij. 0) and w peg max -Wij 0}, the matrix representa- tion of single neuron nx(x) max((w (w. b, 0} is given by
Denoting by Wpps and Wneg the positive and negative part of
P-Pos
(Bpus yncg
A
nog
ax
A,
mey a. = 1eeg
3.2 EXTRACTING LINEAR TERMS OF A CLASSIFICATION NETWORK
We now consider classification neural network / with labels. We show that can represent the network N with a matrix vector pair (A A,.a" a in the denominator that is constant over all output dimensions. The proof is given in Section C.2 of the supplementary material.
This is in line with the tropical algehra notation: a tropical quotient the same usual difference.
3

---

Published as a conference paper at ICLR 2021
Algorithm 3.1 TropEx: Extracting Linear Terms of Neural Network
Inputs: Neural Network A
Data set X' = {(x,, i)} with D; points of label i i)ısig
Output:
Extracted Function N/() = (IAT,a))/(A
1: W, b - weight matrix and bias vector of last layer !
2: CT, . f- column sums of Waeg beeg
3: C+ <- C+C + b
4: for = 1 to s do
5:
A rep( C, Di), a. rep(ct, Dz)
Repetition D; times along the
6: A + rep(C=_ D), a < rep(c_.1)
D D total no of data points
7: Amax < maxima of the columns of all A and A stacked
8: for last layer & in N not yet used do
9:
(N(x), Amax)
merge, (A((), m according to Table
Lemma 3.2. Let N: IR R be the fanction of a ReLU neural network for classification with output neurons. Then there are affine functions aigs aj such that
maxxaaji (x).
iin (x))
N(x)
maxfaī (x))(a((x),... (x),..., (x)).
(3)
maxx(a (x), .... atn (x))
where the maxima of the 07 (x) on the right is subtracted from each entry of the vector on the left In terms of our matrices the classification network N with s labels can be repre- of vecrox-vector pairs. The label is then given by
sented by a list (IA) (0)((=,aa)))
argmax (A,,a)) (x)).
How to get the extracted function ( of ( from the network N. TropEx extracts, for each data point X2 of label i, the affine functions a and a, from the network representation in (3)
such that att(x (x+) 2 (xx),, (xx) 2 dj(xs) for all i. We start with the last layer of the network and inductively merge depend on the type of the layer as shown T Putting things together gives Algorithm [.1 which has the extracted function A/()) as its output. The run-time and storage complexities per data point correspond results in a selection of linear terms based on a data set of points and that the extracted tropical function agrees with the network neighbourhoods of all these points. Its proof and the complete, non-trivial derivation of the algorithm are in the appendix, where we develop a framework that enables caleulations on tropical matrices that correspond to manipulations of the tropical functions they represent. For illustrative purposes, we also present worked-out example of applying TropEx toy neural network there.
layers into the existing matrix pairs. The merge operations
forward passes through the network. Theorem 3.3 states that TropEx indeed
Theorem 3.3. Let N = (N1,...,NN.) Rdd + RR be the function of a ReLU neural network for classification into classes. Let 212) be the network obtained from Algorithm 3.1
applied
to N using data set X [(X,, 1)l S
8, 153 j S D:} of D; data points Xs, given label by N. (There are D points X1 , XD in total). Then, (1) for all labels i, xx max(a;; (x).....a") ...... (x))
where the of and a, extracted from representation of No as in Equation 3 and (2) every data point x has a neighbourhood Uj on which
max (x)..... ..... ( (x)).
the maximum of the extracted function agrees with the maximal network output:
max N (8)
(x)
(x)
max Ni(x) for all x E Uk- IS
particular, (x) and N classify all points Us by assigning the same label.
This implics that every ReI.U neural network classifier can be represented convex function.
4

---

Published as a conference paper at ICLR 2021
Type
Operation
Type
Operation
BNorm
M.,,H,,,, Batchnorm parameters
Maxpool
A, Amax repeat to input shape of A& t set 0 according to
8 F +o
A 4 sA; a At
A max Am/ max
activations of {(xx)
Conv
F. b f filter, bias of
Dense
W, f- weights, bias of
K ConvTrans( A max: FrcE)
K A max Wingg
Amax +K K + Conv Trans Amax: F
Amax f K + Amax WP
a a a+ Ab
a a Ab
A K + ConnTTann(A,.. F)
A K + AW
Flatten
A, Amax f- reshape to input shape of &
L-ReLU
α f- Leaky ReLU parameter
ReLU
Aaj < 0 0ff
Akj f- a Auj if ((xx) S
Table I: Merge operations (Nix), Ama) + (Nix), Ama), according to type of layer f. A₁ denotes
the slice of A corresponding to data point k. 2 denotes all of the network up to and including & Read expressions like A + K + aW as A + K A W + KKA for all
EXPERIMENTS
TropEx extracts function containing only linear terms corresponding to regions which the given data lies. The extracted function agrees with the network on this data. This allows us to compare linear regions of train and test data, separate the network structure from the information contained in the linear coefficients, and to test how well the linear coefficients generalize to test data.
Setup We train neural networks on MNIST LeCun et al. 2010) and CIFARIO Krizhevsky 2009). After training, we use training data points x ( extract linear terms a ( (x) and a (x(er) (x) and construct an extracted function (x)) as in equation 2 For some experiments, we also extract linear terms (....) (x) and (x(t-) (x) corresponding to test data points x (te)) Regarding the architecture, we use fully-connected networks, AlICNN-C from Springenberg et al. (2015) and variations of VGG-B from Simonyan & Zisserman (2015). Section Din the appendix summarizes all architectures we used in our experiments. If not stated otherwise, we use architectures Conv for CNNs and FCN8 for FCNs in our experiments. It is not our goal to train networks to state-of-the-arr performance, but rather to compare variations of simple networks which are composed the layers shown Table [ All layers have ReLU activations except for the last layer where apply softmax output function into the ten respective classes results. Further details the training setup can be found in the appendix.
3 We train five networks of each architecture to ensure the consistency of
Train and Test Linear Regions At first, we investigate how training and test samples are dis- tributed over the linear regions the neural networks. For each data point x, let 0x = at ax be the function corresponding to the linear region on which lies. Observing that ax # dx for all training and test points x, x', we see that all points lic in different linear regions 5 This is not a result of overfitting during training: All data points also occupy different regions when check the linear regions after 1, 3, 5, 10, 15, 20, 30, 40, and 50 epochs of training on CIFAR1O, and from epochs to 20 on MNIST. Therefore explained by test samples falling into the same linear region as training samples (or, in other words, by test samples inducing the same activation pattern training samples).
conclude that generalization capabilities of neural networks cannot be
Examining Function Coefficients With test samples falling into different regions than training samples, it is conceivable that neighboring regions could still be "nearly identical" and test samples would fall into such neighboring regions of training samples. To clarify, ran experiments to test the similarity of linear regions for test samples before and after reduction. We take a test sample and extract the linear coefficient of its linear region in both the original network ' and in the extracted function (X where X' is the training data. For these linear coefficient
4 We also experimented with replacing ReLU with Leaky ReLU. Our observations are in line with what we describe for ReL.U. More details can he found in the appendix, Section E.3 'Except for the small l-yer architecture, where the data points lie 59,850 regions instead of 60,000.
5

---

Published as a conference paper at ICLR 2021
Name FCN MNIST
N vs (((2
W vs true
A(X) vs true
97.7=20.2
98.1
97.64u.2
CNN MNIST
95.7+0.3
99.240.1
95.8
FCN CIFARIO
52.5+3.5
49.2+0.7
38.2+1.5
CNN CIFARIO
30.8
71.1
30.4
Table 2: Results on test data after extraction of linear terms. Column 1: Agreement of network /V' with extracted function Artz), Columns 2&3: Multi-class accuracy W and A/(*), All values are averages over runs and over each of the architectures in table in section DaaiionDooffo the appendix.
vectors, we calculate the (i) angle and (ii) Euclidean norm difference. Figure shows both values for all test samples, where we differentiate between those test points x x(te) that get correctly classified by N/(²) (in blue) and those that get a wrong label (in red). We observe a clear difference between the CNN and the FCN. For CNNs, the coefficient vectors of both training and test affine functions are all close to orthogonal for correctly as well as incorrectly classified points, For FCNs, the angle and distance of correctly classified points are smaller than for incorrectly classified ones, but still far away from zero and therefore rule out the possibility of test samples falling into very similar neighboring regions. Finally, instead of comparing linear coefficients, we also tested the similarity in activation patterns before and after extraction. The results in section E.5 of the appendix show that in each layer approx 80% of neuron activations agree between test and training region, showing that also the activation patterns of test samples deviate considerably and generalization cannot be simply explained by very similar activation patterns.
Convolutional Network
Fully Connected Network
500
30
25
Euclidean Distances
Euclidean Distances
20
15
200
20
3//4
Angles
</4
Angles
n/2
3n/4
Figure 2: Angle and distance between coefficients of the linear regions of test data and training data used for correct (blue) and incorrect (red) classification by the extracted function. All angles for CNNs (left) are close to orthogonal, while FCNs (right) shows clear correlations between angles, distances and correctness of prediction.
Accuracy of the Extracted Functions As predicted by Theorem 3.3 the maximum the extracted function A/() agrees with the maximum of the original network on all training points for each of our networks. In particular, network and extracted function assign the same label to each training point. To investigate how well the coefficients of these linear regions generalize to unseen data, we compare test accuracy of network and extracted function in Table 2 We see consistent difference between CNNs and FCNs across both data sets and all architectures: There is drastic drop in the test accuracy of the CNNs, as opposed
relatively small drop in the accuracy of the FCNs. Interestingly, for MNIST. the extracted tropical function has almost the same test accuracy as the original network. This is surprising as all known bounds on the number of linear regions of the original network suggest numbers of the order of 10 up to over 10 from which we only observe 60.000 after reduction. Hence, for fully-connected networks on a simple task, the coefficients used on training data generalize well to test data, but for complex data, the learned coefficients generalize worse. This is remarkable, since previous studies (Hanin & Rolnick 2019b a Zhang & Wu 2020) of linear regions were forced to base their experiments seems that care must be taken when generalizing observations to more complex tasks. Moreover, the results reveal another difference between FCNs and CNNs that we further investigate.
small data sets (or small networks) for computational reasons, and it

---

Published as a conference paper at ICLR 2021
CNN: Fully-Connacted: Wide
CIFAR10: Agreement tropical labels labels
0.8
0.6
0.4
0.4
0.2
Proportion of layers merged
DMCCMCCNCC
Figure 3: Left: Comparison of average test accuracy (dotted red) and agreement with labels assigned by the original network (blue) for networks Narrow and Wide while being transformed into tropical functions. The letters D.M.C denote dense, maxpooling and convolutional layers, respectively. Right: Average test accuracy for all CIFAR networks while being transformed into tropical function. Fully-connected: dotted blue lines, CNNs: full red lines. The curves show a significant difference between the network types with FCN performance being more stable to extraction of linear regions.
Transformation Process Figure 3 left shows how the test accuracy and agreement with the original network develop during the transformation from full network N to its extracted form A/(2, Starting with the last layer, TropEx iteratively merges layers into an extracted function. The x-axis shows which layers have been merged to an extracted tropical function at each step. The graph shows accuracy values for passing test samples through the original network until the layer that represents the input to the extracted tropical function and then applying this extracted function. At the right end of the plots, all layers have been merged to the tropical function M/(x), There is a clear difference between fully-connected networks and CNNs, which consistent over all networks (Figure 3 right).
Number of linear regions The fully-connected network Wide and the CNN Narrow have the same number of nodes after each parameter layer. Since Narrow has only few connections between its nodes and Wide is fully-connected, it is reasonable to assume that the number of linear regions of Wide is greater than the one of Narrow as its theoretical upper bound is higher. Hence, it would be expected that extraction a fixed number of linear terms resulted in a smaller change of results for an initially worse performing Narrow, but the drop in test accuracy for Narrow is almost 5 times the drop for Wide (36.6% vs 8. 1%). An estimate of the number of linear regions in practice (Appendix (E.) further suggests that Narrow has more linear regions than Wide, both being astronomically high. This all contradicts our intuition about how CNNs and FCNs work from the perspective of network expressivity in terms of bounding the maximal number of linear regions.
Network Training We compare the performance of extracted functions A/(2 during the training of the network N.. Figure disullyss the test accuracy (mean and standard deviation over networks) of the extracted function and the agreement of label assignments of extracted form with the original network function for Narrow (CNN) and Wide (fully-connected) for several epochs. The difference between fully fully-connected and convolutional networks is here even more striking. For the CNN, the agreement between the extracted tropical function and the original network function falls rapidly after only one epoch and only slightly reduces from there. For the FCN, the agreement decreases slowly over the entire 50 training epochs and it never reaches a value as low as the CNN after its first epoch.
Information encoded in linear coefficients The extracted functions all share the same number of linear terms, hence their difference in performance must be explained by the coefficient values. With this in mind, we attempt an interpretation of the above results and hypothesize that the difference lies in how FCN and CNN store important information for the classification task in the coefficients of linear regions. An FCN has the full freedom to compose weights tailored coefficients of linear regions, whereas CNNs impose a structure on the weight space by filters and weight sharing, which results in the incapability to compose tailored linear coefficients for correct label assignments. Instead, the structural properties of convolutions play a significant role in generalization, which we remove by extracting linear terms. This changes the outcome test data as the coefficients of linear regions
7

---

Published as a conference paper at ICLR 2021
alone are limited in meaning. As training progresses, achieve higher accuracy, the FCN reduces the information stored in linear coefficients and also learns to use some structure, so that the removal of this structure could explain the decrease in performance of the extracted function. An experiment, where we visually inspect misclassified images (Appendix [..) is in line with this interpretation suggesting that the object shape is encoded in the linear coefficients of the FCNs, but for CNNs only simple features such as background color are encoded in the linear coefficients of linear regions. We visualize coefficients
E.7 to further support observed differences.
Canvol akional Netorik
Fully Conteccisd Network
0.0
0.5
0.6
Induction
62-
reduation
network rescacorory nenwort
Trast 105T Dcc.CCccyyycccmm relwork
retwork
03
0.0
Fpwrh
Fpore
Figure 4: Mean and standard deviation of the performance of extracted tropical function during training over 5 networks. The performance of the CNN network function suffers strongly from extraction early training, whereas the FCN shows a slow, gradual decline.
Re-training the network The observation of smaller angles for FCNs in further supports our interpretation that coefficient values of linear regions play a larger role in classification for FCNs, since smaller angles together with small Euclidean distance are ex-
Epochs vs Correlations (Training)
CIFAR1 FCN
MNST
Correlations
plained by similarity of the coefficient val-
0.4
ues. This suggests to also compare the sim-
0.2
ilarity of linear coefficients after re- training the network in order to further understand the information encoded in the linear coefficients. Again, we find that the coefficient vectors of two separately trained CNNs are close to or- thogonal, whereas both angles and distances are considerably smaller for FCNs [ Plots are shown in Appendix E.6
-0.2
200
Epoch numbers
Figure 5: Pearson correlation between the linear coef- ficients of two separately trained networks averaged over all input dimensions, Black dots indicate reduc- tion of the learning rate by factor of 10. Coefficients are more correlated after re-training for FCNs than for CNNs, suggesting that FCNs encode more infor- mation in the coefficients of linear regions than CNNs
For each dimension, we additionally compute the Pearson correlation between the linear co- efficients of two separately trained networks over all training samples. We reduce the re- sulting vector to a single number by averag- ing the correlation factors over the dimensions. We experiment with pairs of FCNs and CNNs trained on CIFAR1O on MNIST. Figure [ shows the evolution of the correlation during training, confirming that the similarity of coefficient values is also larger for FCNs than for CNNs if measured by correlation. The correlation of linear coefficients after re-training and convergence for the FCNs is significant. Interestingly, for the networks trained on CIFARIO, we notice jumps in the correlation values precisely when the learning rates get decreased.
'We are comparing linear coefficients of the full network function instead of weight vectors. Whereas symmetries in the parameterization of network function make comparisons of weight vectors complicated, the comparison of linear coefficients is well-defined.
8

---

Published as a conference paper at ICLR 2021
5 CONCLUSION
The function of a ReLU network is piecewise linear, with an astronomically high number of linear regions. We introduced TropEx, algorithm systematically extract linear regions based data points, The derivation is based on a matrix representation of tropical functions that supports efficient algorithmic development. TropEx enables investigations of the linear components of piecewise linear network functions: By extracting the networks' linear terms, the algorithm allows us to compare training and test regions and to systematically analyze their linear coefficients. Applying TropEx to fully-connected and convolutional architectures shows significant differences between linear regions of CNNs and FCNs. Other possible use cases are outlined Appendix [ Our findings indicate potential benefit of shifting focus from counting linear regions to understanding of their interplay, as differences between CNNs and FCNs may found in the coefficients of the extracted linear terms. Several measures of similarity indicate that the linear terms of CNNs are more diverse than those of FCNs and suggest that CNNs efficiently exploit the structure imposed by their architecture, whereas FCNs rely encoding information in the values of linear coefficients.
ACKNOWLEDGEMENTS
This work was supported in part by the European Research Council Consolidator grant SEED, CNCSUEFISCDI PN-IIIPCCFF2016-00
Swedish Foundation for Strategic Research (SSF) Smart Systems Program, well as the Wallenberg AL, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation.
REFERENCES
Motasem Alfarra, Adel Bibi, Hasan Abed Al Kader Hammoud, Mohamed Gaafar, and Bernard Ghanem. On the decision boundaries of neural networks: A tropical geometry perspective. arXiv preprint MXXiv:2002.08838// 2021.
Raman Arora, Amitabh Basu, Poorya Mianjy, and Anirbit Mukherjee. Understanding deep neural networks with rectified linear units. In Proceedings of the 4th International Conference Learning Representations, 2016.
Mikhail Belkin, Daniel J Hsu, and Partha Mitra, Overfitting or perfect fitting? risk bounds for classification and regression rules that interpolate. In Advances in Neural Information Processing Systems, 2018.
Vasileios Charisopoulos and Petros Maragos. A tropical approach to neural networks with piecewise linear activations. arXiv preprint arXiv:1805.08749, 2018.
Dan Claudiu Ciresan, Ueli Meier, Luca Maria Gambardella, and Juergen Schmidhuber. Deep big simple neural nets excel on handwritten digit recognition. arXiv preprint arXiv: 1003.0358, 2010.
Francesco Croce, Maksym Andriushehenko, and Matthias Hein. Provable robustness of relu networks via maximization of linear regions. In Proceedings of the International Conference on Artificial Intelligence and Statistics, 2018.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. Proceedings of the 7th International Conference on Learning Representations, 2019.
Xavier Glorot, Antoine Bordes, and Yoshua Bengio. Deep sparse rectifier neural networks. In Proceedings of the 14th International Conference on Artificial Intelligence and Stutistics, 2011.
Richard H. R. Hahnloser, Rahul Sarpeshkar, Misha A. Mahowald, Rodney J. Douglas, and H. Sebas- tian Seung. Digital selection and analogue amplification coexist cortex-inspired silicon circuit. Nature volume 405, 2000.
Boris Hanin and David Rolnick. Complexity of linear regions in deep networks. In Proceedings of the 36th International Conference on Machine Learning, 2019a.
Boris Hanin and David Rolnick. Deep relu networks have surprisingly few activation patterns. In Advances in Neural Information Processing Systems, 2019b.

---

Published as a conference paper at ICLR 2021
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. In Proceedings of the 15th International Conference Computer Vision, 2015.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the 29th IEEE Conference on Computer Vision and Pullern Recognition, 2016.
Geoffrey E. Hinton, Nitish Srivastava, Alex Krizhevsky, llya Sutskever, and Ruslan R. Salakhutdinov. Improving neural networks by preventing co-adaptation of feature detectors. In arXiv preprint arXiv:1207.0580, 2012.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Proceedings of the 3rd International Conference on Learning Reprexentations, 2015.
Alex Krizhevsky. Learning multiple layers of features from tiny images. Master's thesis, University of Toronto, 2009.
Yann LeCun, Corinna Cortes, and CJ Burges. Mnist handwritten digit database. ATT Labs [Online]. Available: http://yann. lecun. com/exdb/nnist, 2010.
Guang-He Lee, David Alvarez-Melis, and Tommi S. Jaakkola. Towards robust, locally linear deep
networks. In Proceedings of the 7th International Conference on Learning Representations, 2019.
Diane Maclagan and Bernd Sturmfels. Introduction to Tropical Geometry. Graduate Studies in Mathematics, vol. 161, AMS, 2015.
Guido Montúfar. Notes on the number of linear regions of deep neural networks. Presented at Mathematics of Deep Learning, Sampling Theory and Applications, 2017.
Guido F Montufar, Razvan Pascanu, Kyunghyun Cho, and Yoshua Bengio. On the number of linear regions of deep neural networks. In Advances in Neural Information Processing Systems, 2014.
Razvan Pascanu, Guido Montufar, and Yoshua Bengio. On the number of response regions of deep feed forward networks with wise linear activations. arXiv preprint arXiv:1312.6098, 2013.
Maithra Raghu, Ben Poole, Jon Kleinberg, Surya Ganguli, and Jascha Sohl- Sohl-Dickstein. On the expressive power of deep neural networks. In Proceedings of the 34th International Conference on Machine Learning, 2017.
Thiago Serra, Christian Tjandraatmadja, and Srikumar Ramalingam. Bounding and counting linear regions of deep neural networks. Proceedings of the 35th International Conference on Machine Learning, 2018
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. In Proceedings of the 3rd International Conference Learning Representations, 2015.
Jost Tobias Springenberg, Alexey Dosovitskiy, Thomas Brox, and Martin Riedmiller. Striving for simplicity: The all convolutional net. Workshop Truck Proceedings of the 3rd International Conference Learning Representations, 2015.
Christian Szegedy, Wei Liu, Yangqing Jia, Pierre Sermanet, Scott Reed, Dragomir Anguelov, Du- mitru Erhan, Vincent Vanhoucke, and Andrew Rabinovich. Going deeper with convolutions. In Proceedings of the 28th IEEE Conference on Computer Vision and Pattern Recognition, 2015.
Huan Xiong, Lei Huang, Mengyang Yu, Li Liu, Fan Zhu, and Ling Shao. On the number of linear regions of convolutional neural networks. In Proceedings of the 37th International Conference on Machine Learning, 2020.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In Proceedings of the 5th International Conference on Learning Representations, 2017.
10

---

Published as a conference paper at ICLR 2021
Liwen Zhang, Gregory Naitzat, and Lek- Hen- Lim. Tropical geometry of deep neural networks, In Proceedings of the 35th International Conference on Machine Learning, 2018.
Xiao Zhang and Dongrui Wu. Empirical studies on the properties of linear regions in deep neural networks. In Proceedings of the 8th International Conference on Learning Representations, 2020.


Reviews:
[{"review_id": "sKV_uw4yMkO", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This submission proposes a new method that can extract a linear region from the network function such that the region contains a specific data point. Though the problem seems to be complex, the propose method compute linear coefficients \"recursively\" through layers. It only needs the computation of a forward computation. \n\nAlthough I hold the idea that global analysis of the function surface is more important than local analysis, I like the proposed method. \n\nIn the experimental analysis, the paper compares FCN and CNN by checking test performances, the extracted function, and coefficients. There are many interesting observations, but I expect to see some informative conclusions -- what are indications of these observations in terms of improving current methods or interpreting the model? \n\nThe submission devotes a lot of analysis to the difference between FCN and CNN. I think most of the difference is because the CNN has many more linear regions and more complex function surface, which are harder to simplify, comparing to FCN.\n\nIs it possible to look into model and check these coefficients? For example, visualizing the coefficients in images? The visual patterns from two different networks may be very different. \n\nIs it possible to check the local landscape of the function surface? If we add some perturbation to one example, how different coefficients can we get? With that linear region be similar to the original one? This might be useful for studying the robustness of these neural networks. \n\nA few detailed comments:\n\n1. The notation i is overloaded: it indexes both classes and instances. \n2. The unnumbered function in 3.1 uses A matrix to represent two linear functions. Using your notation in (2), they should be different a functions. \n3. More CNN architectures might make this analysis more interesting. For example, the residual links in a ResNet may have some relation with these linear coefficients. Also the analysis of a CNN on cifar10 is more meaningful when it has higher performance. \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "q4Jo0_S2jR", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: This paper studies the role of linear terms in the network performance using nontrivial tropical algebra inspired algorithms. In particular, the paper extracts linear terms associated with the linear regions of only the training points, and uses this to generate an extracted network function. The paper proposes an algorithm TropEx to systematically extract linear terms from piecewise linear network functions built using activation functions such as ReLUs. It is shown that this extracted network can be used for classification on the test data as well. In fully connected networks, such a modeling seems to work well on the test data. In the case of CNNs, the gap between the extracted network and original one is large. The paper argues that the number of linear regions may not be the right metric for expressiveness and generalization. \n\t\n\t\t\t\t\t\nPros:\n\n1) The network function can be represented as the difference between maxima of a really large set of affine functions on the input data as shown in Equation (1). The paper nicely shows that in piecewise linear functions learned using a finite set of training samples, we generate exponential numbers of linear regions. The training data typically falls in a very tiny fraction of these regions, and only these linear regions are important. The general study of the number of linear regions and bounds are driven by quantifying expressiveness of neural networks. This work takes a different approach and attempts to only consider the linear regions associated with the training samples. \n\n\n2) The paper extracts linear terms associated with the linear regions of only the training points, and uses this to generate an extracted network function. The extracted network function N^(x) and the original network N are shown to agree in the neighborhood of the training samples with respect to the assigned labels. \n\n\n3) The paper nicely illustrates that all training and test points fall in different linear regions. \n\n\nCons:\n\n\n1) While the general motivation is nice, the paper makes some strong claims without enough justification. In the list of contributions, the paper claims that the number of linear regions is not a good indicator for network performance. However, there is no formal result of empirical validation that justifies this. The proposed approach to extract network function based on the training data is heavily influenced by the linear regions associated with the training data. \n\n\n2) The paper does not clearly explain what “linear terms” mean and it would be useful to define them formally. Does it refer to the affine functions or the linear coefficients w’s?\n\n\n3) Figure 2 requires some clarification. We take a test sample and compute the coefficients of the affine functions in the original and the extracted function. We compute the difference using Euclidean and angular distance. For CNNs, the coefficient vectors are orthogonal for both correct and incorrectly classified points. In the case of FCNs, the distance of correctly classified points is smaller than for incorrectly classified points. This basically means that the generalization is better in FCN compared to CNNs. \n\n\n4) Table 2 shows that the gap between N and N^(x) is large for CNNs. If the extracted network can produce correct labels for all the training data, it is hard to see why the results are poor for the test data. Considering the large amount of training data, even nearest neighbor methods can perform reasonably well. \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "RbqpIX3Tp7", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper is easy to read and technically sound. It is original and presents an interesting perspective on how to understand the activations of ReLU networks. This could be pave the way for other contributions in areas such as adversarial attacks, pruning and especially generalization theory. \n\nThe algorithm presented is efficient to the point that it can be used for large networks and datasets. And the insights on the differences between a FCN and a CNN are quite significant. It is also surprising that by the large number of linear regions of such a network, that such a high generalization can be achieved for FCNs. \n\nI however believe that the paper would be stronger with the addition of a small experiment, namely, comparing the results from MNIST using Fashion MNIST. Clearly MNIST is too simple, but CIFAR is already too complex. Is F-MNIST an intermediate point? would it still manage to generalize or is the generalization behavior just an outlier for very simple datasets such as MNIST.\n\nYou also mention that the generalization capabilities are not explained by test points falling into the same linear regions as the training samples, but, is it possible that there are overlaps? or that the testing regions are subsets of the training ones? At least for FCNs it seems that your generalization results would indicate this is the case. Furthermore, are neighboring regions smooth on the class label? This would be significant for pruning. \n\nHave you considered estimating the volume of the regions around the training data points? This could also provide more insights into the different behavior of FCNs and CNNs.\n\nIn general, I find the paper very interesting and it could have impact on other significant areas of research in DNNs.\n\n ", "extra_scores": {}, "extra_text": {}}, {"review_id": "2NMr-1ain4L", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes a method for representing a computation of a neural network over a finite set of inputs by a projection onto a set of linear transformations (from the input space) called tropical rational map (TRM).  TRM is essentially a snapshot representing the internal representation of however deep network based on its response to a finite set of inputs.  Authors use this linearised approximation of the network internal to gather information about the complexity and generalisability of its function mapping.  \n\nThe paper is well written, and well presented -  the push of most of the details on tropical algebra to the appendices is appreciated.    I think the idea of a transformation of internal representation from a deep model to a set of linear transformations has some merit, though I am not familiar with tropical algebra, and I can't completely verify all the math from appendices.  I am happy to accept that TRM can approximate network's computation over a finite set of inputs and I agree with the authors that counting linear regions alone might not tell us all that much about complexity of the mappng.  However, I am not sure there is enough in this paper to convince me that TRM evaluated on training data contains enough information to tell us something useful about generalisation capabilities of the underlying model .  Going by Table 2, and the performance of TRM-based classification on CIFAR10, it seems that perhaps overall the TRM is just a linearisation of the neural network.  That is, regardless if the mapping provided by the original network is close to linear (MNIST case) or quite non-linear (CIFAR10 case), the information captured by TRM contains only linear aspects.  I think that might be the reason why performance of TRM-based approxiation for MNIST is similar to the original network and drops from 71% to below 42% (the latter happening to be approximately the accuracy of a linear model on CIFAR10).  \n\nFigure 2 seem to provide more evidence that TRM might only capture information about simpler representation.  The difference of angles between TRM projections inside a FC network due to correctly and incorrectly classified  points are a nice result…but they seem not to capture any differentiating information about dynamics of a representationally richer architecture of a convolutional neural network.  BTW, it is not specified what dataset is Figure 2 evaluated on. \n\nIt seems to me that the whole analysis that is presented in this paper makes an assumption that the regions between the samples used to generate TRP are linear…and so the analysis tells us something about the representation when this assumption is correct (the MNIST case), but not much when the assumption is not corect (CIFAR10 and (presumably) other more complex mappings).  \n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper analyses linear regions in ReLU networks using a new algorithm for extracting linear terms based on the data. The reviewers found the paper to be well written with sound results. While the paper itself provides only modest evidence of the algorithm’s utility (mainly in terms of highlighting some distinctions between fully-connected and convolutional networks), the algorithm and the corresponding new paradigm of exploring linear terms rather than counting regions may prove useful in future analyses. Altogether, I think this paper will interest theorists focusing on ReLU networks and I recommend acceptance.
Decision: Accept (Poster)