用最小描述长度训练的神经网络能有效泛化低复杂度数据。
Neural Networks Generalize on Low Complexity Data
- 基于简单编程语言生成数据，用最小描述长度选择网络
- 在素数检测任务中，准确率可达1−O((ln N)/n)
- 无需刻意设计，网络自动发现复杂模式，适合理论研究
我们证明了带有ReLU激活函数的前馈神经网络在适当定义的低复杂度数据上具有泛化能力。给定来自简单编程语言的独立同分布数据，能够拟合数据的最小描述长度（MDL）前馈神经网络具有高概率泛化能力。我们定义了该编程语言及网络的描述长度概念，并展示了在基础计算任务中的多个例子，如判断自然数是否为素数。对于素数检测任务，若从1到N中随机抽取n个数作为样本，每个数x_i对应标签y_i=1（素数）或0（非素数），则该插值型MDL网络对新样本的素性判断准确率可达1−O((ln N)/n)。值得注意的是，该网络并非专为识别素数而设计，而是通过最小描述长度学习自动发现这一规律。还讨论了噪声数据的扩展情况，表明MDL神经网络插值器可表现出温和的过拟合现象。
原文摘要 · Abstract (English)
We show that feedforward neural networks with ReLU activation generalize on low complexity data, suitably defined. Given i.i.d.~data generated from a simple programming language, the minimum description length (MDL) feedforward neural network which interpolates the data generalizes with high probability. We define this simple programming language, along with a notion of description length of such networks. We provide several examples on basic computational tasks, such as checking primality of a natural number. For primality testing, our theorem shows the following and more. Suppose that we draw an i.i.d.~sample of $n$ numbers uniformly at random from $1$ to $N$. For each number $x_i$, let $y_i = 1$ if $x_i$ is a prime and $0$ if it is not. Then, the interpolating MDL network accurately answers, with probability $1- O((\ln N)/n)$, whether a newly drawn number between $1$ and $N$ is a prime or not. Note that the network is not designed to detect primes; minimum description learning discovers a network which does so. Extensions to noisy data are also discussed, suggesting that MDL neural network interpolators can demonstrate tempered overfitting.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。