A Tropical Approach to Neural Networks with Piecewise Linear Activations

Abstract

We present a new, unifying approach following some recent developments on the complexity of neural networks with piecewise linear activations. We treat neural network layers with piecewise linear activations as tropical polynomials, which generalize polynomials in the so-called $(\max ,+)$ or tropical algebra, with possibly real-valued exponents. Motivated by the discussion in (arXiv:1402.1869), this approach enables us to refine their upper bounds on linear regions of layers with ReLU or leaky ReLU activations to $\min \left\{2^m,{\sum }_{j=0}^n\left(\genfrac{}{}{0ex}{}{m}{j}\right)\right\}$, where $n,m$ are the number of inputs and outputs, respectively. Additionally, we recover their upper bounds on maxout layers. Our work follows a novel path, exclusively under the lens of tropical geometry, which is independent of the improvements reported in (arXiv:1611.01491, arXiv:1711.02114). Finally, we present a geometric approach for effective counting of linear regions using random sampling in order to avoid the computational overhead of exact counting approaches

arXiv commentv2: Removed morphological perceptron section and added vertex sampling section. Updated references. 18 pages, 7 figures

References in corpus (9)

• Tropical Geometry of Statistical Models
• Understanding Deep Neural Networks with Rectified Linear Units
• On the number of response regions of deep feed forward networks with piece-wise linear activations
• The operator approach to entropy games
• Log-sum-exp neural networks and posynomial models for convex and log-log-convex data
• Tropicalizing the simplex algorithm
• Minimal half-spaces and external representation of tropical polyhedra
• Pushing the Boundaries of Boundary Detection using Deep Learning
• Tropical Geometry of Deep Neural Networks

Cited by in corpus (11)

• Neurons on Amoebae
• Neural Networks Should Be Wide Enough to Learn Disconnected Decision Regions
• Tropical Polynomial Division and Neural Networks
• Sharp bounds for the number of regions of maxout networks and vertices of Minkowski sums
• Towards Lower Bounds on the Depth of ReLU Neural Networks
• Advances in the training, pruning and enforcement of shape constraints of Morphological Neural Networks using Tropical Algebra
• Tropical Geometry and Piecewise-Linear Approximation of Curves and Surfaces on Weighted Lattices
• Sparse Approximate Solutions to Max-Plus Equations with Application to Multivariate Convex Regression
• Min-Max-Plus Neural Networks
• Bounding The Number of Linear Regions in Local Area for Neural Networks with ReLU Activations
• On the Expected Complexity of Maxout Networks