揭示深度神经网络表示分段线性函数所需的最少层数
Depth-Bounds for Neural Networks via the Braid Arrangement
- 基于辫子排列结构，推导出非恒定下界Ω(log log d)
- 证明5个数的最大值需至少3层，验证了此前复杂计算结果
- 发现三阶maxout层+二阶maxout层可表示7个数最大值
我们致力于解决一个开放问题：ReLU网络需要多少隐层才能精确表示ℝ^d上的所有连续分段线性函数。尽管在特殊情况下已有结论，但一般情况下的最佳已知下界仍为2。本文聚焦于与特定多面体复形（即辫子扇）兼容的神经网络，证明在此类约束下，精确表示d个数的最大值需要Ω(log log d)层隐层。此外，在相同假设下，我们给出一个组合证明，表明计算5个数的最大值至少需要3层隐层——此前该结论仅通过繁琐计算验证。最后，我们指出将现有最优上界推广至maxout网络不成立，通过实例证明：一个秩为3的maxout层后接一个秩为2的maxout层即可表示7个数的最大值。
原文摘要 · Abstract (English)
We contribute towards resolving the open question of how many hidden layers are required in ReLU networks for exactly representing all continuous and piecewise linear functions on $\mathbb{R}^d$. While the question has been resolved in special cases, the best known lower bound in general is still 2. We focus on neural networks that are compatible with certain polyhedral complexes, more precisely with the braid fan. For such neural networks, we prove a non-constant lower bound of $Ω(\log\log d)$ hidden layers required to exactly represent the maximum of $d$ numbers. Additionally, under our assumption, we provide a combinatorial proof that 3 hidden layers are necessary to compute the maximum of 5 numbers; this had only been verified with an excessive computation so far. Finally, we show that a natural generalization of the best known upper bound to maxout networks is not tight, by demonstrating that a rank-3 maxout layer followed by a rank-2 maxout layer is sufficient to represent the maximum of 7 numbers.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。