Fast and Exact Enumeration of Deep Networks Partitions Regions
Randall Balestriero Yann LeCun
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.