A Tropical Approach to Neural Networks with Piecewise Linear Activations
This work provides incremental theoretical insights into neural network complexity for researchers in machine learning theory.
The authors tackled the problem of bounding the number of linear regions in neural networks with piecewise linear activations, refining an upper bound to min{2^m, sum_{j=0}^n binom(m, j)} for ReLU/leaky ReLU layers and recovering bounds for maxout layers.
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 \binom{m}{j} \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