Comparing Linear Regions in ReLU-Type Networks: Theory and Monte Carlo Methods

In this work, we provide a complete characterization of the uniqueness of linear patterns for generic fully connected neural networks activated by ReLU or leaky ReLU functions. With this result, together with several tools from geometry and probability, we compare the numbers of linear regions for a wide variety of networks from both theoretical and practical perspectives, with minimal prerequisites. More specifically, on the theoretical side, we show that networks with neurons arranged as $pq\times2$ (2 hidden layers, each having $pq$ neurons) are expected to have more linear regions than those arranged as $p\times 2q$ for $p\ge 1$ and $q\ge 2$; on the empirical side, we show the validity of a Monte-Carlo approach for comparing linear regions via linear patterns, and carry out experiments for networks in various scenarios. Our results indicate that neurons closer to the input layer tend to have more impact on the number of linear regions. Moreover, along the way, we find the precise value of the expected number of linear regions for networks with 2 hidden layers, and an explicit upper bound for networks whose layer widths are non-increasing. The implementations for this paper are available through the following link: https://github.com/temp-repo-259848/Regions-ReLU-Network