Improved Bounds on Neural Complexity for Representing Piecewise Linear Functions
Improved Bounds on Neural Complexity for Representing Piecewise Linear Functions
复制标题
DOI：
10.48550/arxiv.2210.07236
复制
发表时间：
2022-10
期刊：
影响因子：
--
通讯作者：
Kuan-Lin Chen;H. Garudadri;B. Rao
中科院分区：
文献类型：
--
作者：
Kuan-Lin Chen;H. Garudadri;B. Rao
使用整流线性单元的深度神经网络表示连续分段线性（CPWL）函数，反之亦然。最近的文献结果估计，精确表示任何CPWL函数所需的神经元数量随着片段的数量呈指数增长，或者根据不同线性分量的数量的阶乘呈指数增长。此外，这种增长与输入维度呈线性放大。这些现有的结果似乎表明，代表CPWL功能的成本是昂贵的。在本文中，我们提出了更严格的界限，并建立了一个多项式时间算法，找到一个网络满足这些界限，任何给定的CPWL功能。我们证明了隐藏的神经元的数量，需要准确地表示任何CPWL功能是最多的二次函数的数量件。与以前的结果相比，这个上界对输入维数是不变的。除了片的数量，我们还研究了不同的线性分量的CPWL函数的数量。当这样一个数字也给出，我们证明了二次复杂度变成双线性，这意味着较低的神经复杂度，因为不同的线性组件的数量总是不大于在CPWL函数的最小数量的件。当块的数量是未知的，我们证明，在不同的线性组件的数量方面，任何CPWL函数的神经复杂性是最多的多项式增长的低维输入和阶乘增长的最坏情况下，这是显着优于现有的结果在文献中。
A deep neural network using rectified linear units represents a continuous piecewise linear (CPWL) function and vice versa. Recent results in the literature estimated that the number of neurons needed to exactly represent any CPWL function grows exponentially with the number of pieces or exponentially in terms of the factorial of the number of distinct linear components. Moreover, such growth is amplified linearly with the input dimension. These existing results seem to indicate that the cost of representing a CPWL function is expensive. In this paper, we propose much tighter bounds and establish a polynomial time algorithm to find a network satisfying these bounds for any given CPWL function. We prove that the number of hidden neurons required to exactly represent any CPWL function is at most a quadratic function of the number of pieces. In contrast to all previous results, this upper bound is invariant to the input dimension. Besides the number of pieces, we also study the number of distinct linear components in CPWL functions. When such a number is also given, we prove that the quadratic complexity turns into bilinear, which implies a lower neural complexity because the number of distinct linear components is always not greater than the minimum number of pieces in a CPWL function. When the number of pieces is unknown, we prove that, in terms of the number of distinct linear components, the neural complexities of any CPWL function are at most polynomial growth for low-dimensional inputs and factorial growth for the worst-case scenario, which are significantly better than existing results in the literature.