论文标题
通过神经网络学习奇偶
Learning Parities with Neural Networks
论文作者
论文摘要
近年来，我们看到了一项快速增长的研究线，该研究通过常见的神经网络算法显示了各种模型的可学习性。但是，除了极少数的离群值外，这些结果还显示了可以使用线性方法学习的模型的可学习性。也就是说，这种结果表明，学习具有梯度的神经网络具有竞争力，在示例中与数据无关的表示之上学习线性分类器。由于神经网络比线性方法成功得多，因此这是不足的。此外，从更概念上讲，线性模型似乎并没有捕获深网的“深度”。在本文中，我们朝着展示固有非线性的模型的瘦弱性迈出了一步。我们表明，在某些分布中，稀疏的平族可以通过深度 - 两个网络上的体面来学习。另一方面，在相同的分布下，无法通过线性方法有效地学习这些奇偶。
In recent years we see a rapidly growing line of research which shows learnability of various models via common neural network algorithms. Yet, besides a very few outliers, these results show learnability of models that can be learned using linear methods. Namely, such results show that learning neural-networks with gradient-descent is competitive with learning a linear classifier on top of a data-independent representation of the examples. This leaves much to be desired, as neural networks are far more successful than linear methods. Furthermore, on the more conceptual level, linear models don't seem to capture the "deepness" of deep networks. In this paper we make a step towards showing leanability of models that are inherently non-linear. We show that under certain distributions, sparse parities are learnable via gradient decent on depth-two network. On the other hand, under the same distributions, these parities cannot be learned efficiently by linear methods.
