分析了ReLU网络线性区域计数的计算复杂度，发现多数情况难以高效求解。
The Computational Complexity of Counting Linear Regions in ReLU Neural Networks
- 系统梳理不同定义下的线性区域概念及其关系
- 证明单隐层网络计数已为NP-hard，多隐层更难近似
- 提出部分定义下可在多项式空间内实现计数
衡量ReLU神经网络表达能力的一个经典指标是其将输入空间划分为多少个线性区域。现有多种互不等价的线性区域定义，本文系统梳理各论文所采用的定义并探讨其相互关系。随后分析不同定义下计数线性区域的计算复杂度：结果表明，该问题普遍难以高效求解。我们证明，即使对于仅含一个隐藏层的网络，计数也已是NP-hard和#P-hard；对于两个或更多隐藏层，还存在强近似难度结果。另一方面，在一些常见定义下，计数问题至少可在多项式空间内完成。
原文摘要 · Abstract (English)
An established measure of the expressive power of a given ReLU neural network is the number of linear regions into which it partitions the input space. There exist many different, non-equivalent definitions of what a linear region actually is. We systematically assess which papers use which definitions and discuss how they relate to each other. We then analyze the computational complexity of counting the number of such regions for the various definitions. Generally, this turns out to be an intractable problem. We prove NP- and #P-hardness results already for networks with one hidden layer and strong hardness of approximation results for two or more hidden layers. Finally, on the algorithmic side, we demonstrate that counting linear regions can at least be achieved in polynomial space for some common definitions.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。