On the Number of Linear Regions of Convolutional Neural Networks

Huan Xiong, Lei Huang, Mengyang Yu, Li Liu, Fan Zhu, Ling Shao
Proceedings of the 37th International Conference on Machine Learning, PMLR 119:10514-10523, 2020.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v119-xiong20a, title = {On the Number of Linear Regions of Convolutional Neural Networks}, author = {Xiong, Huan and Huang, Lei and Yu, Mengyang and Liu, Li and Zhu, Fan and Shao, Ling}, booktitle = {Proceedings of the 37th International Conference on Machine Learning}, pages = {10514--10523}, year = {2020}, editor = {III, Hal Daumé and Singh, Aarti}, volume = {119}, series = {Proceedings of Machine Learning Research}, month = {13--18 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v119/xiong20a/xiong20a.pdf}, url = {https://proceedings.mlr.press/v119/xiong20a.html}, 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.} }
Endnote
%0 Conference Paper %T On the Number of Linear Regions of Convolutional Neural Networks %A Huan Xiong %A Lei Huang %A Mengyang Yu %A Li Liu %A Fan Zhu %A Ling Shao %B Proceedings of the 37th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2020 %E Hal Daumé III %E Aarti Singh %F pmlr-v119-xiong20a %I PMLR %P 10514--10523 %U https://proceedings.mlr.press/v119/xiong20a.html %V 119 %X 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.
APA
Xiong, H., Huang, L., Yu, M., Liu, L., Zhu, F. & Shao, L.. (2020). On the Number of Linear Regions of Convolutional Neural Networks. Proceedings of the 37th International Conference on Machine Learning, in Proceedings of Machine Learning Research 119:10514-10523 Available from https://proceedings.mlr.press/v119/xiong20a.html.

Related Material