Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: 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. 
	
					
Pros:

1) 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. 


2) 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. 


3) The paper nicely illustrates that all training and test points fall in different linear regions. 


Cons:


1) 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. 


2) 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?


3) 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. 


4) 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. 

review_title: TropEx: An Algorithm for Extracting Linear Terms in Deep Neural Networks 

final_score: rating: 6: Marginally above acceptance threshold
review_content: 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. 

Although I hold the idea that global analysis of the function surface is more important than local analysis, I like the proposed method. 

In 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? 

The 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.

Is 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. 

Is 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. 

A few detailed comments:

1. The notation i is overloaded: it indexes both classes and instances. 
2. 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. 
3. 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. 

review_title: Interesting study

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: 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. 

The 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. 

I 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.

You 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. 

Have 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.

In general, I find the paper very interesting and it could have impact on other significant areas of research in DNNs.

 
review_title: Interesting perspective on ReLU networks

final_score: rating: 6: Marginally above acceptance threshold
review_content: 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.  

The 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).  

Figure 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. 

It 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).  


review_title: Tropical rational map is a nice idea, but might not by capturing useful information about non-linear mappings.

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)