用算法思维构造深度ReLU网络，实现精确排序等任务
On the algorithmic construction of deep ReLU networks
- 将神经网络视为可构造的算法，而非数据驱动的模型
- 成功构建出能精确排序输入的深层ReLU网络，参数达数十亿
- 网络具递归与并行特性，深度决定计算能力上限
训练后的神经网络在数学上难以描述其表征内容。然而，人们对基于ReLU激活函数的前馈神经网络的表达能力已有越来越多的数学理解：它们表示连续且分段线性函数，并可逼近许多其他函数。关于其表达能力的研究核心问题在于：能表示哪些函数？本文从算法视角出发，将神经网络视为可构造的程序，而非依赖数据训练的模型。一个典型例子是：我们显式构建了一个能精确排序输入的神经网络，而非近似处理，且在输入维度较大时具备接近最优的计算复杂度。此类构造的网络可能包含数十亿参数。我们还构建并分析了多个现有及新提出的实例，发现这类作为算法的神经网络通常具有递归和并行结构。相较于传统算法，ReLU网络受限于必须保持连续性。此外，递归深度受网络层数限制，深层网络相比浅层网络表现出更优性能。
原文摘要 · Abstract (English)
It is difficult to describe in mathematical terms what a neural network trained on data represents. On the other hand, there is a growing mathematical understanding of what neural networks are in principle capable of representing. Feedforward neural networks using the ReLU activation function represent continuous and piecewise linear functions and can approximate many others. The study of their expressivity addresses the question: which ones? Contributing to the available answers, we take the perspective of a neural network as an algorithm. In this analogy, a neural network is programmed constructively, rather than trained from data. An interesting example is a sorting algorithm: we explicitly construct a neural network that sorts its inputs exactly, not approximately, and that, in a sense, has optimal computational complexity if the input dimension is large. Such constructed networks may have several billion parameters. We construct and analyze several other examples, both existing and new. We find that, in these examples, neural networks as algorithms are typically recursive and parallel. Compared to conventional algorithms, ReLU networks are restricted by having to be continuous. Moreover, the depth of recursion is limited by the depth of the network, with deep networks having superior properties over shallow ones.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。