On the Number of Linear Regions of Convolutional Neural Networks

Abstract

One fundamental problem in deep learning is understanding the outstanding performance of deep Neural Networks (NNs) in practice. One explanation for the superiority of NNs is that they can realize a large class of complicated functions, i.e., they have powerful expressivity. The expressivity of a ReLU NN can be quantified by the maximal number of linear regions it can separate its input space into. In this paper, we provide several mathematical results needed for studying the linear regions of CNNs, and use them to derive the maximal and average numbers of linear regions for one-layer ReLU CNNs. Furthermore, we obtain upper and lower bounds for the number of linear regions of multi-layer ReLU CNNs. Our results suggest that deeper CNNs have more powerful expressivity than their shallow counterparts, while CNNs have more expressivity than fully-connected NNs per parameter.

arXiv commentInternational Conference on Machine Learning (ICML) 2020

References in corpus (11)

• Very Deep Convolutional Networks for Large-Scale Image Recognition
• A guide to convolution arithmetic for deep learning
• On the Number of Linear Regions of Deep Neural Networks
• Exponential expressivity in deep neural networks through transient chaos
• Approximating Continuous Functions by ReLU Nets of Minimal Width
• Representation Benefits of Deep Feedforward Networks
• Understanding Deep Neural Networks with Rectified Linear Units
• On the number of response regions of deep feed forward networks with piece-wise linear activations
• Benefits of depth in neural networks
• On the Expressive Power of Deep Neural Networks
• Nearly-tight bounds on linear regions of piecewise linear neural networks

Cited by in corpus (7)

• Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networks
• Piecewise Linear Neural Networks and Deep Learning
• Zen-NAS: A Zero-Shot NAS for High-Performance Deep Image Recognition
• Understanding and Accelerating Neural Architecture Search with Training-Free and Theory-Grounded Metrics
• Sharp bounds for the number of regions of maxout networks and vertices of Minkowski sums
• On the Expected Complexity of Maxout Networks
• Group Whitening: Balancing Learning Efficiency and Representational Capacity