Enumeration of max-pooling responses with generalized permutohedra

• URL: http://arxiv.org/abs/2209.14978v2
• Date: Sat, 23 Sep 2023 22:39:04 GMT
• Title: Enumeration of max-pooling responses with generalized permutohedra
• Authors: Laura Escobar, Patricio Gallardo, Javier Gonz\'alez-Anaya, Jos\'e L. Gonz\'alez, Guido Mont\'ufar and Alejandro H. Morales
• Abstract summary: Max-pooling layers are functions that downsample input arrays by taking the maximum over shifted windows of input coordinates. 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.
• Score: 39.58317527488534
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• MaxCutPool: differentiable feature-aware Maxcut for pooling in graph neural networks [5.524804393257921]
  We propose a novel approach to compute the MAXCUT in attributed graphs, i.e., graphs with features associated with nodes and edges. Our approach is robust to the underlying graph topology and is fully differentiable, making it possible to find solutions that jointly optimize the MAXCUT along with other objectives.
  arXiv  Detail & Related papers  (2024-09-08T14:06:25Z)
• Polynomial-Time Solutions for ReLU Network Training: A Complexity Classification via Max-Cut and Zonotopes [70.52097560486683]
  We prove that the hardness of approximation of ReLU networks not only mirrors the complexity of the Max-Cut problem but also, in certain special cases, exactly corresponds to it. In particular, when $epsilonleqsqrt84/83-1approx 0.006$, we show that it is NP-hard to find an approximate global dataset of the ReLU network objective with relative error $epsilon$ with respect to the objective value.
  arXiv  Detail & Related papers  (2023-11-18T04:41:07Z)
• Data Topology-Dependent Upper Bounds of Neural Network Widths [52.58441144171022]
  We first show that a three-layer neural network can be designed to approximate an indicator function over a compact set. This is then extended to a simplicial complex, deriving width upper bounds based on its topological structure. We prove the universal approximation property of three-layer ReLU networks using our topological approach.
  arXiv  Detail & Related papers  (2023-05-25T14:17:15Z)
• Lower Bounds on the Depth of Integral ReLU Neural Networks via Lattice Polytopes [3.0079490585515343]
  We show that $lceillog_(n)rceil$ hidden layers are indeed necessary to compute the maximum of $n$ numbers. Our results are based on the known duality between neural networks and Newton polytopes via tropical geometry.
  arXiv  Detail & Related papers  (2023-02-24T10:14:53Z)
• Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
  We present two new classes of algorithms for efficient field integration on graphs encoding point clouds. The first class, SeparatorFactorization(SF), leverages the bounded genus of point cloud mesh graphs, while the second class, RFDiffusion(RFD), uses popular epsilon-nearest-neighbor graph representations for point clouds.
  arXiv  Detail & Related papers  (2023-02-02T08:33:36Z)
• Reconstruction of Convex Polytope Compositions from 3D Point-clouds [3.04585143845864]
  Reconstructing a composition (union) of convex polytopes that perfectly fits the corresponding input point-cloud is a hard optimization problem. We propose a pipeline that first extracts a set of planes, then partitions the input point-cloud into weakly convex clusters and finally generates a set of convex polytopes as the intersection of fitted planes for each partition. Finding the best-fitting convex polytopes is formulated as a optimization problem over the set of fitted planes and is solved using an Evolutionary Algorithm.
  arXiv  Detail & Related papers  (2021-04-27T00:14:55Z)
• Sharp bounds for the number of regions of maxout networks and vertices of Minkowski sums [1.1602089225841632]
  A rank-k maxout unit is a function computing the maximum of $k$ linear functions. We present results on the number of linear regions of the functions that can be represented by artificial feedforward neural networks with maxout units.
  arXiv  Detail & Related papers  (2021-04-16T14:33:21Z)
• A Parallelizable Lattice Rescoring Strategy with Neural Language Models [62.20538383769179]
  A posterior-based lattice expansion algorithm is proposed for efficient lattice rescoring with neural language models (LMs) for automatic speech recognition. Experiments on the Switchboard dataset show that the proposed rescoring strategy obtains comparable recognition performance. The parallel rescoring method offers more flexibility by simplifying the integration of PyTorch-trained neural LMs for lattice rescoring with Kaldi.
  arXiv  Detail & Related papers  (2021-03-08T21:23:12Z)
• Maximal function pooling with applications [4.446564162927513]
  Maxfun pooling is inspired by the Hardy-Littlewood maximal function. It is presented as a viable alternative to some of the most popular pooling functions, such as max pooling and average pooling. We demonstrate the features of maxfun pooling with two applications: first in the context of convolutional sparse coding, and then for image classification.
  arXiv  Detail & Related papers  (2021-03-01T20:30:04Z)
• Implicit Convex Regularizers of CNN Architectures: Convex Optimization of Two- and Three-Layer Networks in Polynomial Time [70.15611146583068]
  We study training of Convolutional Neural Networks (CNNs) with ReLU activations. We introduce exact convex optimization with a complexity with respect to the number of data samples, the number of neurons, and data dimension.
  arXiv  Detail & Related papers  (2020-06-26T04:47:20Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.