One form of characterizing the expressiveness of a piecewise linear neural network is by the number of linear regions, or pieces, of the function modeled. We have observed substantial progress in this topic through lower and upper bounds on the maximum number of linear regions and a counting procedure. However, these bounds only account for the dimensions of the network and the exact counting may take a prohibitive amount of time, therefore making it infeasible to benchmark the expressiveness of networks. In this work, we approximate the number of linear regions of specific rectifier networks with an algorithm for probabilistic lower bounds of mixed-integer linear sets. In addition, we present a tighter upper bound that leverages network coefficients. We test both on trained networks. The algorithm for probabilistic lower bounds is several orders of magnitude faster than exact counting and the values reach similar orders of magnitude, hence making our approach a viable method to compare the expressiveness of such networks. The refined upper bound is particularly stronger on networks with narrow layers.   Neural networks with piecewise linear activations have become increasingly more common along the past decade, in particular since BID40 and BID25 . The simplest and most commonly used among such forms of activation is the Rectifier Linear Unit (ReLU), which outputs the maximum between 0 and its input argument BID30 BID35 . In the functions modeled by these networks, we can associate each part of the domain in which the network corresponds to an affine function with a particular set of units having positive outputs. We say that those are the active units for that part of the domain. Counting these "pieces" into which the domain is split, which are often denoted as linear regions or decision regions, is one way to compare the expressiveness of models defined by networks with different configurations or coefficients. The theoretical analysis of the number of input regions in deep learning dates back to at least BID8 , and more recently BID45 have shown empirical evidence that the accuracy of similar rectifier networks can be associated with the number of such regions.From the study of how many linear regions can be defined on such a rectifier network with n ReLUs, we already know that not all configurations -and in some cases none -can reach the ceiling of 2 n regions. We have learned that the number of regions may depend on the dimension of the input as well as on the number of layers and how the units are distributed among these layers. On the one hand, it is possible to obtain neural networks where the number of regions is exponential on network depth . On the other hand, there is a bottleneck effect by which the width of each layer affects how the regions are partitioned by subsequent layers due to the dimension of the space containing the image of the function, up to the point that shallow networks define the largest number of linear regions if the input dimension exceeds n BID45 .The literature on this topic has mainly focused on bounding the maximum number of linear regions. Lower bounds are obtained by constructing networks defining increasingly larger number of linear regions BID2 BID45 . Upper bounds are proven using the theory of hyperplane arrangements by BID54 along with other analytical insights BID44 BID38 BID45 . These bounds are only identical -and thus tight -in the case of one-dimensional inputs BID45 . Both of these lines have explored deepening connections with polyhedral theory, but some of these results have also been recently revisited using tropical algebra BID55 BID13 . In addition , BID45 have shown that the linear regions of a trained network correspond to a set of projected solutions of a Mixed-Integer Linear Program (MILP).Other methods to study neural network expressiveness include universal approximation theory BID16 , VC dimension BID5 , and trajectory length BID44 . Different networks can be compared by transforming one network to another with different number of layers or activation functions. For example, it has been shown that any continuous function can be modeled using a single hidden layer of sigmoid activation functions BID16 . In the context of ReLUs , BID36 have shown that the popular ResNet architecture BID31 with a single ReLU neuron in every hidden layer can be a universal approximator. Furthermore, BID2 have shown that a network with single hidden layer of ReLUs can be trained for global optimality with a runtime polynomial in the data size, but exponential in the input dimension. The use of trajectory length for expressiveness is related to linear regions, i.e., by changing the input along a one dimensional path we study the transition in the linear regions.Certain critical network architectures using leaky ReLUs (f (x) = max(x, αx), α ∈ (0, 1)) are identified to produce connected decision regions BID42 . In order to avoid such degenerate cases, we need to use sufficiently wide hidden layers. However, this result is mainly applicable for leaky ReLUs and not for the standard ReLUs BID7 .Although the number of linear regions has been long conjectured and recently shown to work for comparing similar networks, this metric would only be used in practice if we come up with faster methods to count or reasonably approximate such number. Our approach in this paper consists of introducing empirical upper and lower bounds, both of which based on the weight and bias coefficients of the networks, and thus able to compare networks having the same configuration of layers.In particular, we reframe the problem of determining the potential number of linear regions N of an architecture with that of estimating the representation efficiency η = log 2 N of a network, which can be interpreted as the minimum number of units to define as many linear regions, thereby providing a more practical and interpretable metric for expressiveness. We present the following contributions:(i ) We adapt approximate model counting methods for propositional satisfiability (SAT) to obtain probabilistic bounds on the number of solutions of MILP formulations, which we use to count regions. Interestingly, these methods are particularly simpler and faster when restricted to lower bounds on the order of magnitude. See results in FIG2 and algorithm in Section 5. (ii) We refine the best known upper bound by considering the coefficients of the trained network.With such information, we identify that unit activity further contributes to the bottleneck effect caused by narrow layers BID45 . Furthermore, we are able to compare networks with the same configuration of layers. See results in Table 1 and theory in Section 4. (iii) We also survey and contribute to the literature on MILP formulations of rectifier networks due to the impact of the formulation on obtaining better empirical bounds. See Section 3. This paper introduced methods to obtain upper and lower bounds on a rectifier network. The upper bound refines the best known result for the network configuration by taking into account the coefficients of the network. By analyzing how the network coefficients affect when each unit can be active, we break the commonly used theoretical assumption that the activation hyperplane of each unit intersects every linear region defined by the previous layers. The resulting bound is particularly stronger when the network has a narrow layer, hence evidencing that the bottleneck effected identified by BID45 can be even stronger in those cases. The lower bound is based on extending an approximate model counting algorithm of SAT formulas to MILP formulations, which can then be used on MILP formulations of rectifier networks. The resulting algorithm is orders of magnitude faster than exact counting on networks with a large number of linear regions. The probabilistic bounds obtained can be parameterized for a balance between precision and speed, but it is interesting to observe that the the bounds obtained for different networks preserve a certain ordering in their sizes as we make the estimate more precise. Hence, we have some indication that faster approximations could suffice if we just want to compare networks for their relative expressiveness.Algorithm 1 Computes probabilistic lower bounds on the number of distinct solutions on n binary variables of a formulation F using parity constraints of size k DISPLAYFORM0 end for 6:while Termination criterion not satisfied do 7:F ← F Start over with F as formulation F 8: DISPLAYFORM1 Number of times that we have made F infeasible 9:r ← 0 Number of parity constraints added this time 10:while F has some solution s do 11:repeat 12:Generate parity constraint C of size k among n variables 13: DISPLAYFORM2 r ← r + 1 15: until C removes s This loop is implemented as a lazy cut callback 16: end while 17: DISPLAYFORM3 Number of times that F is feasible after adding j constraints 19:end for 20:end while 21:for j ← 0 → n − 1 do Computes probabilities after last call to the solver 22: BID46 and BID47 used these functions to show that approximate counting can be done in polynomial time with an NP-oracle, whereas BID50 have shown that SAT formulas with unique solution are as hard as those with multiple solutions. Hence, from a theoretical standpoint, such approximations are not much harder than solving for a single solution. DISPLAYFORM4 The seminal work by BID26 introduced the MBound algorithm, where XOR constraints on sets of variables with a fixed size k are used to compute the probability that 2 r is either a lower or an upper bound. These probabilistic lower bounds are always valid but get better as k increases, whereas the probabilistic upper bound is only valid if k = |V |/2. However, BID29 have shown that these lower bounds can be very good in practice for small values of k. The same principles have also been applied to constraint satisfaction problems BID28 .With time, this topic has gradually shifted to more precise estimates and to reducing the value of k needed to obtain valid upper bounds. Some of the subsequent work has been influenced by uniform sampling results from BID27 , where the fixed size k is replaced with an independent probability p of including each variable in each XOR constraint. That work includes the ApproxMC and the WISH algorithms BID10 BID21 , which rely on finding more solutions of the restricted formulas but generate (σ, ) certificates by which, with probability 1 − σ, the result is within (1 ± )|S|. The following work by BID22 and BID56 aimed at providing upper bound guarantees when p < 1/2, showing that the size of those sets can be Θ log(|V |) . Other groups tackled this issue differently. BID11 and BID33 have limited the counting to any set of variables I for which any assignment leads to at most one solution in V , denoting those as minimal independent supports. BID0 and BID1 have broken with the independent probability p by using each variable the same number of times across the r XOR constraints.
We provide improved upper bounds for the number of linear regions used in network expressivity, and an highly efficient algorithm (w.r.t. exact counting) to obtain probabilistic lower bounds on the actual number of linear regions. Contributes to the study of the number of linear regions in RELU neural networks by using an approximate probabilistic counting algorithm and analysis Builds off previous work studying the counting of linear regions in deep neural networks, and improves the upper bound previously proposed by changing the dimensionality constraint The paper deals with expressiveness of a piecewise linear neural network, characterized by the number of linear regions of the function modeled, and leverages probabilistic algorithms to compute the bounds faster, and proves tighter bounds.