A General Computational Framework to Measure the Expressiveness of Complex Networks Using a Tighter Upper Bound of Linear Regions

• URL: http://arxiv.org/abs/2012.04428v1
• Date: Tue, 8 Dec 2020 14:01:20 GMT
• Title: A General Computational Framework to Measure the Expressiveness of Complex Networks Using a Tighter Upper Bound of Linear Regions
• Authors: Yutong Xie, Gaoxiang Chen and Quanzheng Li
• Abstract summary: The upper bound of regions number partitioned by a rec-tifier network, instead of the number itself, is a more practical measurement ofexpressiveness of a DNN. We propose a new and tighter up-per bound regions number for any network structures. Our experiments show our upper bound is tighterthan existing ones, and explain why skip connections and residual structures can improve network performance.
• Score: 13.030269373463168
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The expressiveness of deep neural network (DNN) is a perspective to understandthe surprising performance of DNN. The number of linear regions, i.e. pieces thata piece-wise-linear function represented by a DNN, is generally used to measurethe expressiveness. And the upper bound of regions number partitioned by a rec-tifier network, instead of the number itself, is a more practical measurement ofexpressiveness of a rectifier DNN. In this work, we propose a new and tighter up-per bound of regions number. Inspired by the proof of this upper bound and theframework of matrix computation in Hinz & Van de Geer (2019), we propose ageneral computational approach to compute a tight upper bound of regions numberfor theoretically any network structures (e.g. DNN with all kind of skip connec-tions and residual structures). Our experiments show our upper bound is tighterthan existing ones, and explain why skip connections and residual structures canimprove network performance.

Related papers

• Neural Network Verification with Branch-and-Bound for General Nonlinearities [63.39918329535165]
  Branch-and-bound (BaB) is among the most effective methods for neural network (NN) verification. We develop a general framework, named GenBaB, to conduct BaB for general nonlinearities in general computational graphs. We demonstrate the effectiveness of our GenBaB on verifying a wide range of NNs, including networks with activation functions such as Sigmoid, Tanh, Sine and GeLU.
  arXiv  Detail & Related papers  (2024-05-31T17:51:07Z)
• On Generalization Bounds for Deep Compound Gaussian Neural Networks [1.4425878137951238]
  Unrolled deep neural networks (DNNs) provide better interpretability and superior empirical performance than standard DNNs. We develop novel generalization error bounds for a class of unrolled DNNs informed by a compound Gaussian prior. Under realistic conditions, we show that, at worst, the generalization error scales $mathcalO(nsqrt(n))$ in the signal dimension and $mathcalO(($Network Size$)3/2)$ in network size.
  arXiv  Detail & Related papers  (2024-02-20T16:01:39Z)
• Neural Networks with Sparse Activation Induced by Large Bias: Tighter Analysis with Bias-Generalized NTK [86.45209429863858]
  We study training one-hidden-layer ReLU networks in the neural tangent kernel (NTK) regime. We show that the neural networks possess a different limiting kernel which we call textitbias-generalized NTK We also study various properties of the neural networks with this new kernel.
  arXiv  Detail & Related papers  (2023-01-01T02:11:39Z)
• Tangent Bundle Filters and Neural Networks: from Manifolds to Cellular Sheaves and Back [114.01902073621577]
  We use the convolution to define tangent bundle filters and tangent bundle neural networks (TNNs) We discretize TNNs both in space and time domains, showing that their discrete counterpart is a principled variant of the recently introduced Sheaf Neural Networks. We numerically evaluate the effectiveness of the proposed architecture on a denoising task of a tangent vector field over the unit 2-sphere.
  arXiv  Detail & Related papers  (2022-10-26T21:55:45Z)
• On the Number of Regions of Piecewise Linear Neural Networks [16.78532039510369]
  Many feedforward neural networks (NNs) generate continuous and piecewise-linear (CPWL) mappings. The number of these so-called linear regions offers a natural metric to characterize the expressiveness of CPWL NNs. We introduce a complementary framework to estimate the average number of linear regions produced by a CPWL NN.
  arXiv  Detail & Related papers  (2022-06-17T08:17:28Z)
• Lower and Upper Bounds for Numbers of Linear Regions of Graph Convolutional Networks [11.338307976409707]
  The number of linear regions has been considered a good measure for the expressivity of neural networks with piecewise linear activation. We present some estimates for the number of linear regions of the classic graph convolutional networks (GCNs) with one layer and multiple-layer scenarios.
  arXiv  Detail & Related papers  (2022-06-01T04:32:23Z)
• Deep Architecture Connectivity Matters for Its Convergence: A Fine-Grained Analysis [94.64007376939735]
  We theoretically characterize the impact of connectivity patterns on the convergence of deep neural networks (DNNs) under gradient descent training. We show that by a simple filtration on "unpromising" connectivity patterns, we can trim down the number of models to evaluate.
  arXiv  Detail & Related papers  (2022-05-11T17:43:54Z)
• Counting Substructures with Higher-Order Graph Neural Networks: Possibility and Impossibility Results [58.277290855841976]
  We study tradeoffs of computational cost and expressive power of Graph Neural Networks (GNNs) We show that a new model can count subgraphs of size $k$, and thereby overcomes a known limitation of low-order GNNs. In several cases, the proposed algorithm can greatly reduce computational complexity compared to the existing higher-order $k$-GNNs.
  arXiv  Detail & Related papers  (2020-12-06T03:42:54Z)
• Bounding The Number of Linear Regions in Local Area for Neural Networks with ReLU Activations [6.4817648240626005]
  We present the first method to estimate the upper bound of the number of linear regions in any sphere in the input space of a given ReLU neural network. Our experiments showed that, while training a neural network, the boundaries of the linear regions tend to move away from the training data points.
  arXiv  Detail & Related papers  (2020-07-14T04:06:00Z)
• On the Number of Linear Regions of Convolutional Neural Networks [0.6206641883102021]
  Deep CNNs have more powerful expressivity than their shallow counterparts, while CNNs have more expressivity than fully-connected NNs per parameter. 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.
  arXiv  Detail & Related papers  (2020-06-01T14:38:05Z)
• EdgeNets:Edge Varying Graph Neural Networks [179.99395949679547]
  This paper puts forth a general framework that unifies state-of-the-art graph neural networks (GNNs) through the concept of EdgeNet. An EdgeNet is a GNN architecture that allows different nodes to use different parameters to weigh the information of different neighbors. This is a general linear and local operation that a node can perform and encompasses under one formulation all existing graph convolutional neural networks (GCNNs) as well as graph attention networks (GATs)
  arXiv  Detail & Related papers  (2020-01-21T15:51:17Z)

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.