Bounding and Counting Linear Regions of Deep Neural Networks
Authors: Thiago Serra, Christian Tjandraatmadja, Srikumar Ramalingam
ICML 2018 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | 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. ... We perform an experiment to count linear regions of small-sized networks with Re LU activation units on the MNIST benchmark dataset (Le Cun et al., 1998). In this experiment, we train rectifier networks with two hidden layers summing up to 22 neurons. |
| Researcher Affiliation | Academia | 1Carnegie Mellon University, Pittsburgh, USA 2The University of Utah, Salt Lake City, USA. |
| Pseudocode | No | The paper includes mathematical formulations and descriptions of a mixed-integer linear formulation but does not present any structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper states: 'The counting code is written in C++ (gcc 4.8.4) using CPLEX Studio 12.8 as a solver and ran in Ubuntu 14.04.4 on a machine with 40 Intel(R) Xeon(R) CPU E5-2640 v4 @ 2.40GHz processors and 132 GB of RAM.' However, it does not provide any link or explicit statement about the public availability of this code. |
| Open Datasets | Yes | We perform an experiment to count linear regions of small-sized networks with Re LU activation units on the MNIST benchmark dataset (Le Cun et al., 1998). |
| Dataset Splits | No | The paper mentions 'training set' and 'testing set' in Figure 6, but does not provide specific details on the dataset splits (e.g., percentages or exact numbers) used for training, validation, or testing. |
| Hardware Specification | Yes | The counting code is written in C++ (gcc 4.8.4) using CPLEX Studio 12.8 as a solver and ran in Ubuntu 14.04.4 on a machine with 40 Intel(R) Xeon(R) CPU E5-2640 v4 @ 2.40GHz processors and 132 GB of RAM. |
| Software Dependencies | Yes | The counting code is written in C++ (gcc 4.8.4) using CPLEX Studio 12.8 as a solver and ran in Ubuntu 14.04.4 |
| Experiment Setup | Yes | In this experiment, we train rectifier networks with two hidden layers summing up to 22 neurons. We train 10 networks for each configuration for 20 epochs or training steps, and we count all linear regions within 0 x 1. |