Fast and Exact Enumeration of Deep Networks Partitions Regions
read the original abstract
One fruitful formulation of Deep Networks (DNs) enabling their theoretical study and providing practical guidelines to practitioners relies on Piecewise Affine Splines. In that realm, a DN's input-mapping is expressed as per-region affine mapping where those regions are implicitly determined by the model's architecture and form a partition of their input space. That partition -- which is involved in all the results spanned from this line of research -- has so far only been computed on $2/3$-dimensional slices of the DN's input space or estimated by random sampling. In this paper, we provide the first parallel algorithm that does exact enumeration of the DN's partition regions. The proposed algorithm enables one to finally assess the closeness of the commonly employed approximations methods, e.g. based on random sampling of the DN input space. One of our key finding is that if one is only interested in regions with ``large'' volume, then uniform sampling of the space is highly efficient, but that if one is also interested in discovering the ``small'' regions of the partition, then uniform sampling is exponentially costly with the DN's input space dimension. On the other hand, our proposed method has complexity scaling linearly with input dimension and the number of regions.
This paper has not been read by Pith yet.
Forward citations
Cited by 5 Pith papers
-
AffineLens: Capturing the Continuous Piecewise Affine Functions of Neural Networks
AffineLens enumerates the continuous piecewise affine regions induced by neural networks within a given bounded input polytope and provides visualizations and region-complexity metrics.
-
AffineLens: Capturing the Continuous Piecewise Affine Functions of Neural Networks
AffineLens computes and visualizes the maximal continuous piecewise affine regions induced by neural networks, supporting batch-norm, pooling, residuals, MLPs and convolutions, and enables empirical comparison of arch...
-
Causal Explanations from the Geometric Properties of ReLU Neural Networks
ReLU networks' division of input space into convex polytopal regions permits direct extraction of causal rules that exactly match the original network's linear behavior in each region.
-
AffineLens: Capturing the Continuous Piecewise Affine Functions of Neural Networks
AffineLens enumerates the maximal continuous piecewise-affine regions induced by neural networks with batch-norm, pooling, residuals and convolutions inside a bounded input polytope and supplies visualizations and reg...
-
Expressivity Saturation: Reduced Affine Region Usage Under Increasing Task Complexity
Piecewise-affine networks realize fewer affine regions than their theoretical capacity when trained on higher-complexity tasks, termed expressivity saturation, alongside a new bound on line-segment probes.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.