Linear region enumeration (polyhedral complex traversal / sampling)

methods / Theoretical / Analytical / Linear region enumeration (polyhedral complex traversal / sampling)

Linear region enumeration (polyhedral complex traversal / sampling)

Techniqueadvanced

Recovers a piecewise-linear network's induced polyhedral partition of input space directly, either by exact combinatorial traversal (BFS over the region-adjacency graph, following shared facets between activation patterns) or by grid/Monte-Carlo sampling of forward passes to approximate region boundaries — as opposed to bounding the number of regions purely theoretically without measuring a trained network.

Used in (2 observations)

A real trained 3-layer ReLU classifier's composed linear-region partition is directly visualized on 2D data, and the per-layer regions are neither convex nor connectedmeasured

structure: Linear region arrangement (polyhedral tessellation of input space) · models: 3-layer FC classifier, 2D input, 4-class synthetic data (Balestriero & Baraniuk) · paper: Mad Max: Affine Spline Insights into Deep Learning (expanded from A Spline Theory of Deep Networks, ICML 2018)

A real ReLU network's connectivity graph of polyhedral linear regions converges toward its 2d average-degree bound, with data-containing regions more connectedmeasured

structure: Linear region arrangement (polyhedral tessellation of input space) · models: MNIST fully-connected net [784,5,8,8,8,10] (Gaines & Bi), CIFAR-10 CNN classifier sub-network, post-relu3 (Gaines & Bi), California Housing regression MLP (Gaines & Bi) · paper: Characterizing the Discrete Geometry of ReLU Networks