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

Yutong Xie, Yutong Xie 0004, Gaoxiang Chen, Quanzheng LiarXiv 2020 · arXiv

Abstract

The expressiveness of deep neural networks (DNNs) is often characterized by the number of linear regions they can partition the input space into. However, existing upper bounds for this metric are frequently loose or restricted to simple architectures. This paper introduces a novel computational framework that provides a tighter mathematical upper bound for ReLU-based networks. By extending this framework to complex architectures like U-Nets and ResNets, the authors demonstrate how skip connections and residual blocks significantly enhance a network's representational capacity, offering a formal explanation for their empirical success.

Introduction

Deep Neural Networks (DNNs) utilizing Rectified Linear Units (ReLU) function as massive piecewise-linear mappings. The input space is partitioned into numerous convex regions, within each of which the network performs a simple linear transformation. The total number of these "linear regions" serves as a proxy for the network's expressiveness—its ability to represent complex, high-frequency functions.

Calculating the exact number of these regions is computationally intractable for practical networks. While previous research has established upper bounds to estimate this complexity, these bounds were often loose or limited to basic Multilayer Perceptrons (MLPs). This theoretical gap has made it difficult to rigorously quantify the expressiveness of modern, complex architectures like those featuring skip connections or pooling layers.

Methodology

The authors propose a matrix-based computational framework to derive a tighter upper bound. Their approach introduces several key innovations:

  1. Recursive Geometric Analysis: A recursive formula is derived for $\gamma$, a critical parameter in bounding the number of regions, based on the geometric principles of how hyperplanes divide space.
  2. Downward-Move Function: To improve the precision of initial recursive values, the authors introduce a "downward-move" operation on histograms representing space dimensions.
  3. Architectural Generalization: The framework is extended to non-standard components:
  4. Pooling and Unpooling: These are modeled as linear transformations that systematically adjust the space dimension.
  5. Skip Connections and Residual Blocks: These are modeled as concatenations or additions. The analysis shows they preserve or enhance the dimensionality of input regions, preventing the "expressiveness bottleneck" typically seen in deep, narrow MLPs.

Experimental Evaluation

The study primarily focuses on theoretical and computational validation. The authors evaluate their framework across several architectural configurations:

  • MLPs: Varying depths ($k$) and widths ($n_i$).
  • Auto-encoders (AE) vs. U-Nets: To isolate the impact of skip connections.
  • Residual Networks: Comparing standard convolutional stacks against residual counterparts.
  • Input Dimensions: Calculations were performed for input sizes such as $16 \times 16$ and $24 \times 24$ pixels.

Key Insights: The Power of Skip Connections

A central finding is the formal explanation for the success of skip connections. In standard deep networks, the number of regions can be severely limited by narrow "bottleneck" layers. Skip connections bypass these constraints, allowing the network to maintain a significantly higher number of linear regions.

The authors suggest that skip connections improve "partition efficiency"—the capacity of a single hyperplane to simultaneously divide many existing regions. This is quantified in the massive jump in expressiveness when moving from a standard Auto-encoder to a U-Net; for a specific 4-layer configuration, the U-Net's upper bound was found to be approximately $10^{405}$ times larger than that of an equivalent AE without skip connections.

Results

The proposed bound was shown to be strictly tighter (lower and more accurate) than the previous state-of-the-art metric proposed by Serra et al. (2018).

Figure 1: Ratio of the proposed upper bound to the previous state-of-the-art (Serra et al., 2018) across different MLP configurations. A lower ratio indicates a tighter, more accurate bound. Subplot (c) shows the ratio decreasing exponentially as the number of layers $k$ increases.

As shown in the figure above, the advantage of the new framework becomes increasingly pronounced with network depth. In residual networks, adding residual structures increased the expressiveness bound by factors ranging from $1.002 \times$ to over $5 \times$, depending on the specific layer configuration.

Conclusion and Future Work

While this framework provides a significantly tighter bound, it remains an upper bound. A gap still exists between the theoretical maximum and the number of regions actually utilized by a network after training. Additionally, calculating complete values for very high-resolution networks is memory-intensive, limiting current experiments to smaller input sizes. Future research will aim to extend this framework to other modern architectures, such as Transformers and Attention mechanisms, to further unify our understanding of deep learning expressiveness.

Summary updated

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.
BibTeX
@misc{xie2020general,
  author = {Yutong Xie and Yutong Xie and Gaoxiang Chen and Quanzheng Li},
  title = {{A General Computational Framework to Measure the Expressiveness of Complex Networks Using a Tighter Upper Bound of Linear Regions}},
  year = {2020},
  eprint = {2012.04428},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2012.04428},
}
Figure