Sharp bounds for the number of regions of maxout networks and vertices of Minkowski sums
arXiv:2104.08135
Abstract
We present results on the number of linear regions of the functions that can be represented by artificial feedforward neural networks with maxout units. A rank-k maxout unit is a function computing the maximum of linear functions. For networks with a single layer of maxout units, the linear regions correspond to the upper vertices of a Minkowski sum of polytopes. We obtain face counting formulas in terms of the intersection posets of tropical hypersurfaces or the number of upper faces of partial Minkowski sums, along with explicit sharp upper bounds for the number of regions for any input dimension, any number of units, and any ranks, in the cases with and without biases. Based on these results we also obtain asymptotically sharp upper bounds for networks with multiple layers.
arXiv comment25 pages, 5 figures
References in corpus (13)
- Lectures on 0/1-polytopes
- On the Number of Linear Regions of Deep Neural Networks
- Representation Benefits of Deep Feedforward Networks
- On the number of response regions of deep feed forward networks with piece-wise linear activations
- Deep ReLU Networks Have Surprisingly Few Activation Patterns
- Complexity of Linear Regions in Deep Networks
- Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networks
- Empirical Studies on the Properties of Linear Regions in Deep Neural Networks
- On the Number of Linear Regions of Convolutional Neural Networks
- A Tropical Approach to Neural Networks with Piecewise Linear Activations
- The degree of a tropical basis
- A Sober Look at Neural Network Initializations
- Lefschetz and Lower Bound theorems for Minkowski sums