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:
- 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.
- Downward-Move Function: To improve the precision of initial recursive values, the authors introduce a "downward-move" operation on histograms representing space dimensions.
- Architectural Generalization: The framework is extended to non-standard components:
- Pooling and Unpooling: These are modeled as linear transformations that systematically adjust the space dimension.
- 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).
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