On the Number of Linear Functions Composing Deep Neural Network: Towards a Refined Definition of Neural Networks Complexity
This work addresses a theoretical gap in neural network expressivity analysis, offering a more precise tool for comparing architectures, though it is incremental in refining existing complexity measures.
The paper tackles the limitation of counting linear regions for comparing expressivity in deep neural networks, especially for permutation-invariant architectures, by proposing a refined complexity measure based on equivalence classes of linear functions, which distinguishes between models and shows exponential growth with depth.
The classical approach to measure the expressive power of deep neural networks with piecewise linear activations is based on counting their maximum number of linear regions. This complexity measure is quite relevant to understand general properties of the expressivity of neural networks such as the benefit of depth over width. Nevertheless, it appears limited when it comes to comparing the expressivity of different network architectures. This lack becomes particularly prominent when considering permutation-invariant networks, due to the symmetrical redundancy among the linear regions. To tackle this, we propose a refined definition of piecewise linear function complexity: instead of counting the number of linear regions directly, we first introduce an equivalence relation among the linear functions composing a piecewise linear function and then count those linear functions relative to that equivalence relation. Our new complexity measure can clearly distinguish between the two aforementioned models, is consistent with the classical measure, and increases exponentially with depth.