两层隐藏层 ReLU 神经网络中最小化神经元数量的 NP 难性

《IEEE Transactions on Pattern Analysis and Machine Intelligence》：NP-Hardness of Minimizing Neurons in Two-Hidden-Layer ReLU Neural Networks

　　

摘要：

在神经网络中确定实现指定精度所需的最少神经元数量是一项重大挑战。本文探讨了设计具有 ReLU 激活函数的前馈神经网络的复杂性，并证明使用两层隐藏层 ReLU 网络近似一个 Lp 函数所需的最小神经元数量是 NP 难的。利用几何集合覆盖问题的多项式时间归约，证明了 ReLU 网络结构最小化的 NP 难度。结果为进一步在 ReLU 神经网络设计中采用启发式近似方法提供了理论依据，说明在多项式时间内实现最小配置在计算上是不可行的。

I. 引言

优化深度学习架构中的神经元数量对于平衡计算效率和模型性能至关重要。过大的网络增加了过拟合的风险，而过小的网络可能无法捕获基本数据结构 [1]。鉴于前馈神经网络在图像分类 [2]、[3]、自然语言处理 [4]、[5] 和科学计算 [6]、[7] 等应用中的广泛使用，需要设计既最小又有效的模型的方法 [8]、[9]。尽管通过解析方法、启发式方法和复杂度分析进行了努力，但确定最佳参数数量仍未解决。我们的研究检验了优化 ReLU 网络结构中的基本计算障碍，旨在为在网络设计中采用近似方法提供理论依据，因为找到精确最优解在计算上是不可处理的。