Polyhedral Complex Extraction from ReLU Networks using Edge Subdivision

• URL: http://arxiv.org/abs/2306.07212v1
• Date: Mon, 12 Jun 2023 16:17:04 GMT
• Title: Polyhedral Complex Extraction from ReLU Networks using Edge Subdivision
• Authors: Arturs Berzins
• Abstract summary: 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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A neural network consisting of piecewise affine building blocks, such as fully-connected layers and ReLU activations, is itself a piecewise affine function supported on a polyhedral complex. This complex has been previously studied to characterize theoretical properties of neural networks, but, in practice, extracting it remains a challenge due to its high combinatorial complexity. A natural idea described in previous works is to subdivide the regions via intersections with hyperplanes induced by each neuron. However, we argue that this view leads to computational redundancy. Instead of regions, we propose to subdivide edges, leading to a novel method for polyhedral complex extraction. A key to this are sign-vectors, which encode the combinatorial structure of the complex. Our approach allows to use standard tensor operations on a GPU, taking seconds for millions of cells on a consumer grade machine. Motivated by the growing interest in neural shape representation, we use the speed and differentiability of our method to optimize geometric properties of the complex. The code is available at https://github.com/arturs-berzins/relu_edge_subdivision .

Related papers

• Neural Networks and (Virtual) Extended Formulations [5.762677915745415]
  We make a step towards proving lower bounds on the size of neural networks by linking their representative capabilities to the notion of the extension complexity $mathrmxc(P)$. We show that powerful results on the ordinary extension complexity can be converted into lower bounds for monotone neural networks.
  arXiv  Detail & Related papers  (2024-11-05T11:12:11Z)
• Towards Explaining Hypercomplex Neural Networks [6.543091030789653]
  Hypercomplex neural networks are gaining increasing interest in the deep learning community. In this paper, we propose inherently interpretable PHNNs and quaternion-like networks. We draw insights into how this unique branch of neural models operates.
  arXiv  Detail & Related papers  (2024-03-26T17:58:07Z)
• On Rademacher Complexity-based Generalization Bounds for Deep Learning [18.601449856300984]
  We show that the Rademacher complexity-based approach can generate non-vacuous generalisation bounds on Convolutional Neural Networks (CNNs) Our results show that the Rademacher complexity does not depend on the network length for CNNs with some special types of activation functions such as ReLU, Leaky ReLU, Parametric Rectifier Linear Unit, Sigmoid, and Tanh.
  arXiv  Detail & Related papers  (2022-08-08T17:24:04Z)
• Algorithmic Determination of the Combinatorial Structure of the Linear Regions of ReLU Neural Networks [0.0]
  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.
  arXiv  Detail & Related papers  (2022-07-15T18:36:12Z)
• 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)
• 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)
• Poly-NL: Linear Complexity Non-local Layers with Polynomials [76.21832434001759]
  We formulate novel fast NonLocal blocks, capable of reducing complexity from quadratic to linear with no loss in performance. The proposed method, which we dub as "Poly-NL", is competitive with state-of-the-art performance across image recognition, instance segmentation, and face detection tasks.
  arXiv  Detail & Related papers  (2021-07-06T19:51:37Z)
• Towards Lower Bounds on the Depth of ReLU Neural Networks [7.355977594790584]
  We investigate whether the class of exactly representable functions strictly increases by adding more layers. We settle an old conjecture about piecewise linear functions by Wang and Sun (2005) in the affirmative. We present upper bounds on the sizes of neural networks required to represent functions with logarithmic depth.
  arXiv  Detail & Related papers  (2021-05-31T09:49:14Z)
• 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)
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces [208.67848059021915]
  We study the exploration-exploitation tradeoff at the core of reinforcement learning. In particular, we prove that the complexity of the function class $mathcalF$ characterizes the complexity of the function. Our regret bounds are independent of the number of episodes.
  arXiv  Detail & Related papers  (2020-11-09T18:32:22Z)
• Measuring Model Complexity of Neural Networks with Curve Activation Functions [100.98319505253797]
  We propose the linear approximation neural network (LANN) to approximate a given deep model with curve activation function. We experimentally explore the training process of neural networks and detect overfitting. We find that the $L1$ and $L2$ regularizations suppress the increase of model complexity.
  arXiv  Detail & Related papers  (2020-06-16T07:38:06Z)

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.