Algorithmic Determination of the Combinatorial Structure of the Linear Regions of ReLU Neural Networks

• URL: http://arxiv.org/abs/2207.07696v1
• Date: Fri, 15 Jul 2022 18:36:12 GMT
• Title: Algorithmic Determination of the Combinatorial Structure of the Linear Regions of ReLU Neural Networks
• Authors: Marissa Masden
• Abstract summary: We determine the regions and facets of all dimensions of the canonical polyhedral complex. We present an algorithm which calculates this full canonical structure. The resulting algorithm is numerically stable, time in the number of intermediate neurons, and obtains accurate information across all dimensions.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: We algorithmically determine the regions and facets of all dimensions of the canonical polyhedral complex, the universal object into which a ReLU network decomposes its input space. We show that the locations of the vertices of the canonical polyhedral complex along with their signs with respect to layer maps determine the full facet structure across all dimensions. We present an algorithm which calculates this full combinatorial structure, making use of our theorems that the dual complex to the canonical polyhedral complex is cubical and it possesses a multiplication compatible with its facet structure. The resulting algorithm is numerically stable, polynomial time in the number of intermediate neurons, and obtains accurate information across all dimensions. This permits us to obtain, for example, the true topology of the decision boundaries of networks with low-dimensional inputs. We run empirics on such networks at initialization, finding that width alone does not increase observed topology, but width in the presence of depth does. Source code for our algorithms is accessible online at https://github.com/mmasden/canonicalpoly.

Related papers

• Defining Neural Network Architecture through Polytope Structures of Dataset [53.512432492636236]
  This paper defines upper and lower bounds for neural network widths, which are informed by the polytope structure of the dataset in question. We develop an algorithm to investigate a converse situation where the polytope structure of a dataset can be inferred from its corresponding trained neural networks. It is established that popular datasets such as MNIST, Fashion-MNIST, and CIFAR10 can be efficiently encapsulated using no more than two polytopes with a small number of faces.
  arXiv  Detail & Related papers  (2024-02-04T08:57:42Z)
• Algebraic Complexity and Neurovariety of Linear Convolutional Networks [0.0]
  We study linear convolutional networks with one-dimensional and arbitrary strides. We generate equations whose common zero locus corresponds to the Zariski closure of the corresponding neuromanifold. Our findings reveal that the number of all complex critical points in the optimization of such a network is equal to the generic Euclidean distance of a Segre variety.
  arXiv  Detail & Related papers  (2024-01-29T23:00:15Z)
• The Geometric Structure of Fully-Connected ReLU Layers [0.0]
  We formalize and interpret the geometric structure of $d$-dimensional fully connected ReLU layers in neural networks. We provide results on the geometric complexity of the decision boundary generated by such networks, as well as proving that modulo an affine transformation, such a network can only generate $d$ different decision boundaries.
  arXiv  Detail & Related papers  (2023-10-05T11:54:07Z)
• Polyhedral Complex Extraction from ReLU Networks using Edge Subdivision [0.0]
  A neural network consists of piecewise affine building blocks, such as fully-connected layers and ReLU activations. This complex has been previously studied to characterize theoretical properties of neural networks. We propose to subdivide the regions via intersections with hyperplanes induced by each neuron.
  arXiv  Detail & Related papers  (2023-06-12T16:17:04Z)
• 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)
• Dist2Cycle: A Simplicial Neural Network for Homology Localization [66.15805004725809]
  Simplicial complexes can be viewed as high dimensional generalizations of graphs that explicitly encode multi-way ordered relations. We propose a graph convolutional model for learning functions parametrized by the $k$-homological features of simplicial complexes.
  arXiv  Detail & Related papers  (2021-10-28T14:59:41Z)
• Path Regularization: A Convexity and Sparsity Inducing Regularization for Parallel ReLU Networks [75.33431791218302]
  We study the training problem of deep neural networks and introduce an analytic approach to unveil hidden convexity in the optimization landscape. We consider a deep parallel ReLU network architecture, which also includes standard deep networks and ResNets as its special cases.
  arXiv  Detail & Related papers  (2021-10-18T18:00:36Z)
• The Separation Capacity of Random Neural Networks [78.25060223808936]
  We show that a sufficiently large two-layer ReLU-network with standard Gaussian weights and uniformly distributed biases can solve this problem with high probability. We quantify the relevant structure of the data in terms of a novel notion of mutual complexity.
  arXiv  Detail & Related papers  (2021-07-31T10:25:26Z)
• ResNet-LDDMM: Advancing the LDDMM Framework Using Deep Residual Networks [86.37110868126548]
  In this work, we make use of deep residual neural networks to solve the non-stationary ODE (flow equation) based on a Euler's discretization scheme. We illustrate these ideas on diverse registration problems of 3D shapes under complex topology-preserving transformations.
  arXiv  Detail & Related papers  (2021-02-16T04:07:13Z)

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.