Enumeration of max-pooling responses with generalized permutohedra
This work addresses a theoretical problem for researchers in machine learning and combinatorics, focusing on understanding the mathematical properties of max-pooling, but it is incremental as it builds on existing geometric methods without direct practical applications.
The paper tackles the problem of analyzing the combinatorics of max-pooling layers in convolutional neural networks by counting the number of linearity regions, which is equivalent to counting vertices of certain polytopes. It provides generating functions and closed formulas for the number of vertices and facets in 1D max-pooling and for vertices in a special 2D case.
We investigate the combinatorics of max-pooling layers, which are functions that downsample input arrays by taking the maximum over shifted windows of input coordinates, and which are commonly used in convolutional neural networks. We obtain results on the number of linearity regions of these functions by equivalently counting the number of vertices of certain Minkowski sums of simplices. We characterize the faces of such polytopes and obtain generating functions and closed formulas for the number of vertices and facets in a 1D max-pooling layer depending on the size of the pooling windows and stride, and for the number of vertices in a special case of 2D max-pooling.