PaperlayerView exact revision on arXiv

Source-linked AI summary

Bounding and Counting Linear Regions of Deep Neural Networks

Thiago Serra, Christian Tjandraatmadja, Srikumar Ramalingam

arXiv:1711.02114v4cs.LGcs.AIcs.NEmath.OCstat.ML

TL;DR

The paper addresses the gap between empirical DNN architecture design and theory by studying the number of linear regions in piecewise-linear networks. It develops bounds, counting methods, and analyses of bottlenecks, showing that depth does not always increase regions over shallow networks and that region count may not reflect capacity when layers are too small.

  • Problem

    Empirical results largely govern DNN choices of depth and piecewise-linear activation functions, motivating theoretical study of their linear-region complexity.

  • Method

    The paper derives dimension-aware bounds for rectifier and multi-layer maxout networks and models DNNs with mixed-integer formulations for exact region enumeration or counting.

  • Results

    The bounds are exact for one-dimensional rectifier-network inputs, while shallow rectifier networks can have more regions than deep ones when input dimension exceeds neuron count.

  • Takeaways & Limitations

    Linear-region counts can compare similar DNN configurations when no layer is too small, but may overstate capacity when a low-dimensional bottleneck is present.

  • Takeaways & Limitations

    Empirical region-count behavior resembling the bottleneck bound is initial evidence about the bound rather than evidence about the exact maximal number of regions.

Abstract

from arXiv · show

We investigate the complexity of deep neural networks (DNN) that represent piecewise linear (PWL) functions. In particular, we study the number of linear regions, i.e. pieces, that a PWL function represented by a DNN can attain, both theoretically and empirically. We present (i) tighter upper and lower bounds for the maximum number of linear regions on rectifier networks, which are exact for inputs of dimension one; (ii) a first upper bound for multi-layer maxout networks; and (iii) a first method to perform exact enumeration or counting of the number of regions by modeling the DNN with a mixed-integer linear formulation. These bounds come from leveraging the dimension of the space defining each linear region. The results also indicate that a deep rectifier network can only have more linear regions than every shallow counterpart with same number of neurons if that number exceeds the dimension of the input.

1. Introduction

The paper studies how depth and piecewise-linear activations affect DNN expressiveness through linear-region counts, combining improved theoretical bounds with exact counting in trained rectifier networks.

  • Motivation: Greater depth and PWL activations such as ReLUs are common in successful architectures, while their theoretical relationship to architecture design remains incomplete.The paper frames this as a gap between empirical practice and theory.
  • Motivation: DNN expressiveness is studied through how PWL networks partition input space into linear regions.Functions with more regions are treated as more complex or more representationally powerful.
  • Contributions: The paper provides tighter upper and lower bounds for maximal ReLU linear regions, exact when the input dimension is one, and the first upper bound for multi-layer maxout networks.These results directly improve prior work by Montúfar, Raghu, and Arora.
  • Contributions: For ReLU networks, shallow architectures can have more maximal linear regions than deep architectures when input dimension exceeds the number of neurons.This comparison was not inferable from prior bounds and addresses large-input settings.
  • Contributions: A mixed-integer linear formulation enables exact enumeration or counting of linear regions in trained networks.The method is demonstrated on rectifier networks for MNIST, supporting bound evaluation and potential accuracy-region correlation analysis.

2. Notations and Background

The paper models ReLU DNNs as PWL maps whose regions are determined by activation patterns, and explains how successive layer hyperplanes partition transformed spaces.

  • Network notation: A feedforward ReLU DNN maps n0-dimensional inputs to outputs through hidden-layer activations and a final linear output layer.Each hidden layer uses a weight matrix and bias vector with ReLU activations.
  • Definitions: A linear region is the set of inputs producing the same activation pattern across the network.An activation pattern records which ReLU units are active in each layer.
  • Definitions: The paper’s activation-pattern definition can differ from the literature’s maximal-connected-linear-set definition in degenerate cases, but its bounds apply to both.Different patterns may yield adjacent regions with the same linear function under the paper’s definition.
  • Geometric interpretation: Each ReLU acts like a hyperplane divider within a region, while later-layer boundaries are transformed by earlier layers and may bend or become disconnected.A two-input, three-layer example partitions the input space into 20 regions.
  • Geometric interpretation: An arrangement of n hyperplanes divides a d-dimensional space into at most the Zaslavsky bound, attained in general position and matching the single-layer ReLU maximum.Deep networks further partition regions, but subsequent hyperplanes operate on spaces shaped by earlier transformations.

3. Tighter Bounds for Rectifier Networks

The paper derives tighter bounds for linear regions in rectifier networks by tracking the dimension of each region’s image through the layers. It also characterizes bottlenecks, exact one-dimensional cases, and when shallow networks outperform deep ones for large input dimensions.

  • Upper bound: Theorem 1 gives a tighter upper bound on rectifier-network regions, tight for one layer and matching the maximal single-layer count.The bound is obtained by constraining each layer’s contribution using current and preceding widths.
  • Upper bound: The bound improves on Montúfar (2017) and recovers the asymptotic O(n^Ln_0) rate when input dimension is constant and all layer widths equal n.The earlier bound follows by relaxing the terms n_l − j_l.
  • Bottleneck effect: Smaller early layers create a bottleneck because the indices governing later-layer region counts are limited by preceding widths.Removing a neuron from an earlier layer decreases the bound at least as much as removing one from an equally wide later layer.
  • Empirical relation: The bound’s bottleneck behavior is also reflected by trained-network region counts, although this correspondence concerns empirical behavior rather than exact maximal counts.The paper explicitly distinguishes this observation from a property proved only for the upper bound.
  • Deep versus shallow: When input dimension is large, shallow rectifier networks can attain more regions than deep networks with the same total number of neurons.For equal-width deep networks, the depth maximizing the bound decreases as input dimension increases; both deep and shallow networks can still attain exponentially many regions in sufficiently large dimensions.
  • Proof mechanism: The proof tracks the image dimension of each linear region, which cannot increase after falling to a lower value and therefore limits subsequent hyperplane partitions.For a region S at layer l, this dimension equals the rank of the product of the gated weight matrices through layer l.
  • Exact one-dimensional case: For input dimension one and sufficiently wide layers, the upper bound is exact: with n_l = n and n_l ≥ 3, the maximal count is characterized exactly.The one-dimensional result resolves whether the preceding upper and lower bounds are tight in this setting.

4. An Upper Bound on the Number of Linear Regions for Maxout Networks

The paper derives an upper bound for the number of linear regions in deep maxout networks and characterizes its asymptotic growth for equal-width layers.

  • Upper bound: Unlike ReLU bounds, the maxout analysis gives dimensionality a smaller role because maxout units need not have an inactive zero-output state.The distinction motivates techniques adapted from the ReLU analysis while changing how dimensionality enters the bound.
  • Upper bound: Theorem 10 gives an upper bound on regions for networks with L layers and rank-k maxout units, using layer widths and input dimension.The bound is expressed through d_l = min{n_0, n_1, ..., n_l}.
  • Asymptotic behavior: O((k^2n)^L n_0) is the asymptotic upper bound when all layers have width n, n ≥ n_0, and n_0 = O(1).This describes the maximal region count for equal-width deep maxout networks under the stated asymptotic conditions.

5. Exact Counting of Linear Regions

The paper formulates a bounded-input rectifier network as a mixed-integer linear model whose feasible solutions reproduce network outputs and support exact region counting.

  • Formulation: A bounded polyhedral input domain permits a mixed-integer linear formulation that maps neural-network regions from input space to output space.The assumption covers common settings such as image pixels constrained between 0 and 1.
  • Formulation: Continuous variables represent inputs, neuron outputs, and final outputs, while complementary neuron variables and binary indicators encode activation states.The formulation uses h^0 for inputs, h^l_i for neuron outputs, y = h^(L+1), and z^l_i for activation choices.
  • Correctness: Theorem 11 states that, when each weighted preactivation is bounded by M, fixing x in constraints (1)–(6) yields the network output y.Thus the formulation is exact for the network mapping under the stated big-M condition.
  • Counting: The one-tree approach resumes branch-and-bound after finding an optimal solution, enabling systematic counting of feasible integer solutions.The method can also count feasible solutions within a threshold of the optimum.
  • Counting: Maximizing the minimum output of active neurons addresses boundary cases where binary activation indicators could otherwise cause double-counting.The objective selects strictly positive active outputs in the non-degenerate cases being counted.

6. Experiments

Experiments count exact linear regions in small trained ReLU networks on MNIST and compare the counts with theoretical bounds and classification errors.

  • Experimental setup: 10 networks per configuration were trained for 20 epochs or training steps, using two hidden layers with a total of 22 neurons.The experiment counted all regions within 0 ≤ x ≤ 1.
  • Bounds: Figure 1 reports average, minimum, and maximum region counts for each configuration alongside bounds from Theorem 1 and prior work.Theorem 1's upper bound is reported as tighter than the bounds of Montúfar et al. (2014) and Montúfar (2017).
  • Error comparisons: Figure 6 compares the number of regions with training cross-entropy error and testing misclassification rate, while colors encode the widths of the first two layers.Red-to-blue indicates increasing first-layer width and decreasing second-layer width.
  • Error comparisons: Networks with an intermediate layer of one or two neurons were excluded from Figure 7 because very high training and test errors were expected.Figure 7 therefore focuses on DNNs whose minimum width is at least 4.

7. Discussion

The discussion links region counts to layer-width bottlenecks, input dimension, depth, and accuracy, while cautioning that many regions need not imply good generalization.

  • Bottlenecks: Reducing an early-layer width irrecoverably lowers the image dimension of regions, limiting how much later layers can partition them.Experiments support this bottleneck through asymmetric region counts when one layer grows while another shrinks.
  • Depth and dimension: Shallow networks can attain more regions than deep networks when input dimensions exceed the number of neurons.This extends the comparison beyond settings where depth is expected to increase expressiveness.
  • Depth and dimension: The depth maximizing the theoretical upper bound increases with unit count and decreases with input size.Whether the same dependence holds for actual region counts remains an open question.
  • Generalization: Configurations with extremely many regions may generalize poorly if individual training points occupy separate regions and similarly labeled regions lack compositional relations.This is presented as a possible generalization concern rather than an established failure.
  • Accuracy and capacity: For configurations without very narrow layers, initial evidence relates training and classification accuracies to region counts, but large counts can misrepresent capacity when a layer is too small.The discussion therefore suggests examining the shape of linear regions in addition to their number.

Appendices

The appendices provide most theorem and lemma proofs, and discuss counting on unrestricted inputs and a mixed-integer formulation for maxout networks.

  • The appendices contain most proofs for the upper and lower bounds on linear regions.
  • They discuss counting linear regions on unrestricted input domains.
  • They present a mixed-integer formulation for maxout networks.

A. Analysis of the Bound from Theorem 1

The bound analysis characterizes how input dimension, layer widths, depth, and bottlenecks affect region counts. It establishes comparisons between deep and shallow rectifier networks, including cases where shallow networks have more regions.

  • Two-layer networks: For two layers, R(n0, n1, n2) ≤ R(n0, n1 + n2) when n0 ≥ n1 and n0 ≥ n2.The inequality is strict when n0 > n1.
  • Two-layer networks: B(n0, n1 + 1, n2) > B(n0, n1, n2 + 1) when n0 ≥ n1 + 1 and n0 ≥ n2 + 1.Under these conditions, moving one neuron from the second layer to the first increases the bound.
  • Bottlenecks: The bottleneck effect propagates through all subsequent layers, not only the layer immediately after the bottleneck.The large-input-dimension assumption is needed because the input itself can bottleneck later layers.
  • Bottlenecks: 47 > 46: B(4, 3, 2, 1) exceeds B(4, 4, 1, 1), so moving neurons earlier does not always increase the bound.
  • Equal-width networks: B(n, n, ..., n) ≤ B(n, 2n, ..., 2n) for networks with at least four layers after halving depth and doubling widths.The inequality is equality for L = 1 and strict for L ≥2.
  • Deep versus shallow networks: When the input dimension exceeds the total neurons, a shallow rectifier network can have more regions than an equally sized deeper network.For n0 ≥ Ln, the analysis gives R(n0, n, ..., n) < 2^Ln = R(n0, Ln).

C. Proof of Lemma 4

Lemma 4 bounds the regions induced by hyperplanes using the rank of their weight matrix. The proof reduces the problem to the row space, where Zaslavsky’s theorem applies.

  • A set of m hyperplanes in R^d defined by Wx + b = 0 induces at most P^rank(W) regions.
  • The hyperplane arrangement in R^d has the same number of regions as its restriction to the row space R(W).Points differing by a vector in Ker(W) have identical hyperplane-side assignments.
  • The rank-based bound follows because R(W) has dimension rank(W), allowing Zaslavsky’s theorem to limit its region count.

D. Proof of Theorem 7

The proof constructs a one-dimensional ReLU zigzag with an extra region and uses it to obtain exact and lower-bound results for deeper rectifier networks. The construction preserves high-dimensional region images for further partitioning.

  • One-dimensional construction: For input dimension one and nl ≥3 at every layer, the maximal region count is exactly the product bound stated in Theorem 7.
  • One-dimensional construction: The improved construction uses n ReLUs to create n + 1 regions by replacing a zero-dimensional region with one whose image has dimension one.It shifts neurons forward and reverses the direction of the third neuron.
  • One-dimensional construction: A zigzag function replicated through composition places a scaled copy of the entire function inside each linear region.
  • One-dimensional construction: The construction parameterizes ordered breakpoints 0 < t1 < ... < tn < 1 and chooses neuron directions, weights, and biases to realize alternating zero-to-one and one-to-zero pieces.The proof solves the resulting equations by back-substitution after selecting valid breakpoint values.
  • One-dimensional construction: t1 = 1/(2n+1) and ti = (2i−1)/(2n+1) for i = 2, ..., n give valid breakpoints for the construction.
  • Higher-dimensional lower bound: For n0-dimensional inputs with nl ≥ 3n0, the lower-bound construction assigns floor(nl/n0) ReLUs per independent one-dimensional network and multiplies their region counts.The independence of the subnetworks yields a product of activation-pattern counts.

F. Proof of Theorem 9

Theorem 9 constructs rectifier networks whose region count grows through an initial wide layer followed by one-dimensional layers. The resulting network has an explicit exponential-in-depth region count.

  • Construction: For any m ≥1 and w ≥2, a rectifier network with n0 inputs and layer size 2m + w(L −1) attains the stated region construction.The construction uses an initial layer of size 2m and remaining layers of size w.
  • Proof strategy: The proof combines a first layer with 2m ReLUs and subsequent one-dimensional layers from Theorem 7.The first layer represents a function with the stated region count, while each remaining layer contributes the one-dimensional construction.

G. Proof of Theorem 10

Theorem 10 bounds regions in multi-layer rank-k maxout networks by accounting for hyperplane arrangements within existing regions and limiting their effective rank by the smallest layer dimension. The surrounding formulation results show that rectifier regions can also be represented and counted with mixed-integer methods.

  • Maxout bound: Theorem 10 gives an upper bound on the maximal regions of an L-layer rank-k maxout network with layer widths n_l and input dimension n0.The bound is developed by extending the single-layer hyperplane-arrangement argument across layers.
  • Maxout versus ReLU: Unlike ReLU, maxout does not guarantee rank reductions, so the analysis fully relaxes the rank constraint.The distinction motivates using the dimension minimum rather than an automatic rank decrease through layers.
  • Dimension control: At layer l, the number of regions induced within a region S is bounded using d_l = min{n0, n1, . . . , n_l}.The effective rank of the relevant hyperplane arrangement is at most this minimum dimension.
  • Network-wide bound: The rank-k maxout network’s total region count is bounded by multiplying the per-layer bounds across layers.This follows because the partitioning of regions can be considered independently.
  • Mixed-integer representation: A rectifier DNN with polytope input has a mixed-integer representable input-output mapping, enabling mixed-integer optimization analysis of trained networks.The formulation represents activation patterns and linear regions as unions of polyhedra; bounded input permits a sufficiently large M.
  • Exact counting: If the input is unrestricted, the number of linear regions can be counted using formulation P when M is sufficiently large.The counting argument requires one representative point from each linear region.
Loading 1711.02114v4…